Let’s start by defining a transaction as an update to some state using a protocol :-

(defprotocol Transaction (update [_ state]))

Here’s some example transactions we want to perform. For this article let’s imagine we’re creating a database of user accounts. We’ll just create two transaction types- creating users and deleting them. Let’s record the name and email address, plus the date they joined or left.

(defrecord CreateUser [name email start-date]
  Transaction
  (update [this db]
    (update-in db [:users] conj
      {:name name :email email :start-date start-date})))

(defrecord DeleteUser [email remove-date]
  Transaction
  (update [this db]
    (update-in db [:users]
      (fn [coll] (remove (fn [r] (= (:email r) email)) coll)))))

Data is important. We’ll want to keep records of these transactions.

(defprotocol TransactionLog (record [_ tx]))

Here’s an implementation that uses an agent to write the records to a print-stream.

(defrecord DefaultTransactionLog [ag]
  TransactionLog
  (record [this tx]
    (send-off ag
      (fn [out]
        (binding [*out* out *flush-on-newline* true]
          (io! (prn tx)) out)))))

The agent will hold the print-stream. Agents are good for I/O because messages to them only get delivered if the transaction completes its update succesfully. If a retry is needed the message doesn’t get delivered. We let the Clojure prn function figure out how to serialize it. It’s optional, but I’ve wrapped the actual print statement in an io! wrapper as a safety check.

Having written the records we’ll need some way of reading them back. We’ll just use the standard Clojure reader for this. This function returns a list of all the transactions in a file.

(defn read-transactions [f]
  (if-not (.exists f) []
    (let [rdr (java.io.PushbackReader. (clojure.java.io/reader f))]
      (take-while identity
        (repeatedly
          (fn [] (read rdr false nil)))))))

Now we move on to the database state. Let’s decorate the transaction log with something that will hold this state. As transactions are added to it they will update the in-memory state and be recorded on disk. This can support the TransactionLog protocol as well. The state will be a Clojure ref. The delegate will be a backing transaction log.

(defrecord Database [state delegate]
  TransactionLog
  (record [this tx]
    (dosync
     (alter state (partial update tx))
     (record delegate tx))))

Now we’re ready to create our database with the Clojure ref and backing transaction log. We’ll initialize the ref with a result of updating an empty map with a series of transactions read from our file.

(def db
   (Database.
     (ref (reduce (fn [db tx] (update tx db)) {}
                    (read-transactions
                      (clojure.java.io/file "my.db.clj"))))
     (DefaultTransactionLog.
       (agent (clojure.java.io/writer
                (clojure.java.io/file "my.db.clj")
                :append true)))))

Remember those transactions we coded earlier? Let’s add some convenience functions that will create and apply these transactions :-

(defn create-user [name email]
    (record db (CreateUser. name email (java.util.Date.))))

(defn delete-user [email]
    (record db (DeleteUser. email (java.util.Date.))))

Notice how we’re creating java.util.Date instances.

Now, let’s test it.

(create-user "Bob" "bob@example.org")
(create-user "Alice" "alice@example.org")
(create-user "Carol" "carol@example.org")
(delete-user "alice@example.org")

What’s the state of the database?

(deref (:state db))

You should see something like this :-

{:users
  ({:name "Carol",
    :email "carol@example.org",
    :start-date #inst "2012-04-19T16:00:35.903-00:00"}
   {:name "Bob",
    :email "bob@example.org",
    :start-date #inst "2012-04-19T16:00:35.901-00:00"})}

What’s in our database file? Below is the raw content. Unlike some database files it’s quite easy to read and even possible to edit by hand if the need arises.

#blog.CreateUser{:name "Bob", :email
"bob@example.org", :start-date #inst
"2012-04-19T16:00:35.901-00:00"}
#blog.CreateUser{:name "Alice", :email
"alice@example.org", :start-date #inst
"2012-04-19T16:00:35.903-00:00"}
#blog.CreateUser{:name "Carol", :email
"carol@example.org", :start-date #inst
"2012-04-19T16:00:35.903-00:00"}
#blog.DeleteUser{:email "alice@example.org",
:remove-date #inst
"2012-04-19T16:00:35.904-00:00"}

Note, unless you aren’t using Clojure 1.4 or above you won’t see the #inst tags!

Notice how Clojure is writing out and reading back the java.util.Date instance. You can also register your own Java types to it through the *data-readers* dynamic binding (more details in the Clojure 1.4 release notes). This makes things really easy to create some fairly complex atomic transactions.

Now try recompiling – you should find the database is restored. You can also try removing the user. The transaction log will store both the create-user event and the delete-user event, both with timings.

That’s around 30 lines of code to code a transactional database, and a few more lines to code some custom transactions.

You don’t have to limit yourself to a map as your state. At Deutsche Bank we’ve used a similar design but with RDF triple-stores that are queryable in a datalog syntax. A key benefit with using Clojure’s persistent data-structures for simple in-memory datastores is that you don’t have to worry about locks or concurrent updates.

There were a lot of questions during the Q&A at the end which I did my best to answer at the time. Now I’ve had some more thinking time I’d like to add a few extra comments.

If you couldn’t attend the talk you can catch it here.

Below is the original presentation in blog form (thank you Markdown!). My extra comments can be found in the epilogue – feel free to ask further questions in the comments area.

Reflections on a real-world Clojure application-

Background

• Java background, especially early J2EE circa 1999-2002
• Test Driven Development – ran 20 courses
• Mastering TDD helped me to write Java using values rather than objects
• Began to write Java in a more functional way – but much more verbose!!
• Started using Clojure at work for user web interfaces in November 2009
• Began to attend Clojure Dojos in London
• February 2011 – Clojure used extensively on a new application, now 16K LOCs!

The ‘main’ function

Developer bootstrap

For developers

$ mvn dependency:copy-dependencies
$ ./run

which does this :-

#!/bin/sh
echo "Starting Fandango run script..."

export PATH=$PATH:target/bin

# Set debug to nil to disable JVM debugging.
classpath='src/main/clojure:target/dependency/*'
main=src/main/clojure/com/db/mis4/fandango/main.clj

java -cp ${classpath} clojure.main ${main}

Then slime in with Emacs!

(Let’s look at configuration in more detail)

Configuration

Requirements of a configuration system

• Flexibility – we should be able to add configuration where we need it
• Distributed ownership – we shouldn’t have to know the live passwords
• Source agnostic – we’d like to be able to use local files and centralised storage.

Candidates?

• Java properties files
• JSON/YAML
• XML – tree based, schemas enforces structure rather than value
• Databases – records for configuration are too diverse
• RDF – graph based, queryable

Clojure as configuration?

“Protocols and file formats that are Turing-complete input languages are the worst offenders, because for them, recognizing valid or expected inputs is UNDECIDABLE: no amount of programming or testing will get it right… A Turing-complete input language destroys security for generations of users. Avoid Turing-complete input languages! ” — Corey Doctorow

So…

Be careful if you choose Clojure as your configuration format!!

‘Open Data’

All our data (application & environment configuration, report definitions, user details & entitlements, etc.) are stored as RDF statements

• “The cat sat on the mat”
  • Subject: the cat
  • Predicate (also known as property): sat on
  • Object: the mat

• Relations are at an individual level rather than at a set (ie. table) level.

• More intro to RDF here:
  • http://www.bbc.co.uk/blogs/radiolabs/s5/linked-data/s5.html
  • http://linkeddatabook.com

Our configuration system

• RDF files (mostly Turtle format)
• SPARQL queries
• Uses a dynamic var: (with-config ...)
• Delays to avoid unnecessary queries

Example

create-assocations :-

(defn create-associations [model]
  {::directories
   (delay
    (sparql/select1-map
     model
     [:proc cmdb/host :host]
     [:proc cmdb/install-dir (as-uri (format "file://%s" (or (System/getenv "FANDANGO_INSTALL_DIR")
                                                             (System/getProperty "user.dir"))))]
     [:host a cmdb/Host]
     [:host cmdb/hostname (get-hostname)]
     [:proc cmdb/userid (System/getProperty "user.name")]
     [:proc ["http://mis4.gto.intranet.db.com/fandango/" "dataDirectory"] :data-dir]
     [:proc ["http://mis4.gto.intranet.db.com/fandango/" "logDirectory"] :log-dir]
     [:proc ["http://mis4.gto.intranet.db.com/fandango/" "workDirectory"] :work-dir]
     [:proc ["http://mis4.gto.intranet.db.com/fandango/" "pidDirectory"] :pid-dir]
     [:optional [:proc cmdb/source-dir :source-dir]]

Security

Entitlements

All users are given FOAF ‘profiles’, with added VCARD and other statements.

Given these prefixes

@prefix foaf: <http://xmlns.com/foaf/0.1/> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .

This statement (in the configuration) gives all users a ‘Guest’ role.

foaf:Person rdfs:subClassOf <Guest> .

N-triples

Statements are then added to create users, request roles, approve or reject roles

Creating a user

<events/5afcf604-16c0-4cab-a6d1-656ed3f3420c> <time> "2011-12-25T12:00Z"^^<http://www.w3.org/2001/XMLSchema#dateTime> .
<events/5afcf604-16c0-4cab-a6d1-656ed3f3420c> rdfs:type <CreateUser> .
<events/5afcf604-16c0-4cab-a6d1-656ed3f3420c> <eventfor> <users/malcolm.sparks%40db.com> .

Request a role

<events/b5bed531-a324-4aec-9ace-2785c65a19b7> <time> "2011-12-25T14:00Z"^^<http://www.w3.org/2001/XMLSchema#dateTime> .
<events/b5bed531-a324-4aec-9ace-2785c65a19b7> rdfs:type <RequestRole> .
<events/b5bed531-a324-4aec-9ace-2785c65a19b7> <role> <Administrator> .
<events/b5bed531-a324-4aec-9ace-2785c65a19b7> <eventfor> <users/malcolm.sparks%40db.com> .

Language integrated query

Data can be queried directly from Clojure

(defn get-approved-roles-for-user [user]
  (sparql/select-map
   [(get-combined-model) (config/get-config-model)]
   [:approval a events-ns/RoleApproved]
   [:approval events-ns/time :approval-time]
   [:approval roles/approver :approver]
   [:approver foaf/name :approver-name]
   [:optional [:approver foaf/homepage :approver-homepage]]
   [:approval roles/cause :request]
   [:request roles/requester user]
   [:request events-ns/time :request-time]
   [:request roles/role :role]
   [:role rdfs/label :role-name]))

Deployment

Releasing to production

$ git clone http://github....db.com/.../fandango.git
$ git verify-tag 4.5.0
$ git checkout tags/4.5.0
$ make release

Derive the version from git!

GNU Make incantation …

describe := $(subst -, ,$(shell git describe --tags --long HEAD))
version := $(word 1,$(subst -, ,$(describe)))
release := $(shell expr 1 + $(word 2,$(describe)))

And generate the pom.xml – ie. in Make :-

pom.xml:    pom.template.xml
            cat $< | sed -e "s/@VERSION@/$(version)/g" >$@

mvn dependency:copy-dependencies
cp -r src/ dest/

We use RPM but the principle of copying the source and dependency jars over is the same.

Installation

Installation is easy

$ rpm --dbpath /opt/privatedb -Uvh fandango-4.5.0-1-x86_64.rpm

Production bootstrap

$ fandango start

A lot more complex than the developer bootstrap.

• Init script (from Java Service Wrapper – enhanced with roqet to read environment variables from configuration)
• Init script generates the wrapper.conf, then calls Java Service Wrapper native executable
• Native binary spawns JVM with 2 args clojure.main boot.clj
• boot.clj sets up a classloader which pulls in the dependency jars
• boot.clj hands off to main.clj, rest is as the developer bootstrap.

But source code is still copied onto the system as is.

Logging

Getting started

Logging is important because it’s what everyone expects to find.

These will get you started :-

(clojure.core/println)
(clojure.pprint/pprint)

However, as your application grows you will eventually need a more sophisticated logging system. We use Log4J and configure it with clj-logging-config.

You’ll need the following packages to do this :-”

(use 'clojure.tools.logging)
(use 'clj-logging-config/log4j)

(with-logging-config)

(with-logging-config
  [:root {:level :debug
          :out (io/file workdir "job.log")}]
  ...

(with-logging-context)

For using the NDC and MDC of Log4J.

(with-logging-config
  [:root {:pattern "%d [%p] (for Customer %X{customer}) %m%n"}]
   ...

   (with-logging-context {"customer" "John Smith"}
     ...

Reflections

The Good

• Retain the JVM
• No class files, yippee!
• Sliming in! EDD: Eval Driven Development!
• Separation of value, identity, state: State is a timeline of changing values.
• Learning time – even our DBA is now comfortable with Clojure.

The Bad

• People are justifiably afraid of new things
• Tooling (for those not comfortable with Emacs)
• Java interop can bite you

The Ugly

• Stack traces
• Debugging

Quality versus value

“Value is what you are trying to produce, and quality is only one aspect of it, intermixed with cost, features, and other factors.” — John Carmack, http://altdevblogaday.com/2011/12/24/static-code-analysis/

cf. ‘Agile’ absolutes

• Always write the tests first
• Tests should always pass
• Always fix the build before working on new features
• Integrate continuously
• Refactor prior to adding new features
• Consistent code style

More info

http://blog.malcolmsparks.com

Q & A

Over to you…

Epilogue

Many of the questions related to the RDF portion of my presentation. There were a lot of others, I can’t remember all now.

How big is your team and how did it grow?

We started with 2 developers and grew to 4. Forcing Clojure on developers is unwise. I know that was tried somewhere else and most developers only used the Java interop!

Why do you use RDF for configuration rather than XML or JSON or even Clojure itself?

JSON is certainly more conventional as a configuration format (or XML in the Java world)
There isn’t a strong reason not to use Clojure itself (I had a slide warning of the dangers of Turing complete input languages but the point stands nevertheless). I don’t think my answer was very good last night so here are some advantages of RDF :-

• Meaning – RDF allows you to make logic set-based statements to classes of what are otherwise straight name/values pairs.
• Metadata – RDF allows you to make statements about statements. You can use metadata to label configuration values, add annotations (in multiple languages if you like), or constrain the values to some valid range or set, or say something about the nature of the property. You can do this in a very limited way with XML (perhaps with attributes) but with JSON there’s nothing built-in or idiomatic.
• Mergeability – RDF allows you to source statements from a wide variety of sources and merge the models together, whereas there’s nothing built-in or idiomatic in XML or JSON. In tree formats config statements have to group inside each other in a single hierarchy – designing this hierarchy is a job in itself. Graphs are more flexible since nodes can exist in multiple hierarchies if needs be.
• Inference – in RDF, having some data allows you to infer other data which you would otherwise have to make explicitly. This has the potential to reduce data discrepancies. For example, given a database name, listener host and port you can ‘infer’ a database connection string.

That said, I’m not really pushing RDF as a config format. We took a gamble on it and it paid off in our case. Other projects are different. JSON is a great format that enables fast and simple data exchange (when you control both ends).

I also suggested that a domain model is more valuable for persistent data than for transient data structures. Object oriented languages encourage you to design the domain model internal to a program. But in my view there is more value in a domain model you can communicate between systems, and keep for longer periods, than in a domain model that you can only use privately (ie. in a single memory address space) and only while your application is running. This is the exact opposite of designing domain models in Java/C# classes and serializing out to a database or JSON/XML files, hence the need to illustrate with a real-world example (in this case, configuration).

What other Clojure frameworks do you use?

• Compojure/Ring/Hiccup/Clout for web pages.
• Plugboard for REST but the intention is to move towards something like compojure-rest
• Swank – couldn’t manage without it!

It’s a surprise to me how much we manage to do with just the standard Clojure libraries.

Do you think functionality rises linearly or exponentially with lines of code?

I thought this was a great question because it points to the huge amount of algorithmic re-use that we enjoy in Clojure.

Did you have a specific business problem that led you to Clojure?

Honestly, no. In my case it was a growing frustration with large Java systems. But since we’ve been using Clojure in our team there have been a number of business problems that have cropped up that are ideally suited to Clojure. Certainly in my industry (banking) the business is built on mathematical functions and data transformations for which functional languages like Clojure are ideal.

Do you think Clojure be around in 5 years time?

This final question was asked by someone sitting in the front row. I don’t think they would have asked this if they’d seen how many people were in the room! Clojure is building momentum, at least in London, and as I said in my talk I think it’s beyond the point of critical mass now.

But on reflection I think it’s an important question. Why should anyone invest a lot of time in learning something that isn’t going to be around in a few years? However, technology is always about betting on certain horses (VHS or Betamax?) and you can never be 100% certain. LISP is a good bet though, it’s survived over 50 years and people keep rediscovering it. So even if Clojure doesn’t survive, I’m confident the knowledge you get from learning it will remain relevant.

In our use RDF at work we have been developing on Jena, a Java library for processing and querying RDF triples. Overall, Jena is an excellent library and has powerful inference capabilities. While Clojure has great interop support for Java sometimes you find some mismatches between the two paradigms.

For example, Jena being a Java library supports concurrency via read/write locks rather than Clojure’s Software Transactional Memory. In practise this mismatch disrupts Clojure’s preference for lazy sequences – results have to be read in entirety to avoid concurrent modification errors. Jena’s concurrency model is also confusing to use, and we’ve had to fix a number of deadlocks in our code which have been hard to diagnose. Since we only use a small subset of OWL logical predicates in our dataset it may be possible to replace Jena with something that worked better with Clojure.

Both the RDFS and OWL inference engines in Jena work by extending the graph with additional links called ‘entailments’ which reflect the possible inferences that can be made, using both forward and backward chaining strategies. Creating an inference graph can be expensive and not something you want to do on every query. However, if your data model isn’t static you have to re-create the inference graph every time it changes. While there are inference engines that support such incremental updates efficiently, I was intrigued by core.logic to see if it was possible extending the data model and rather to put inferencing in the relations themselves.

Here’s an example. RDFS declares a subclass predicate which declares one class to be a subclass of another. Any instances of the subclass are, by inference, also instances of the superclass.

We can declare this relation in core.logic like so.

(defrel subclass-of p1 p2)

Here are some facts to illustrate the example.

(fact subclass-of "Royal Bengal Tiger" "Tiger")
(fact subclass-of "Tiger" "Cat")
(fact subclass-of "Cat" "Mammal")
(fact subclass-of "Mammal" "Animal")

Now we can get all the graph links with this query.

(run* [q]
      (fresh [a b]
             (subclass-of a b)
             (== q [a b])))

But rdfs:subclass-of is a owl:transitive. Never mind, we can transform the relation to act transitively. Here’s the transformer function :-

(defn transitive [r]
  (letfn [(t [p1 p2]
            (fresh [between]
                   (conde
                    ((r p1 p2))
                    ((r p1 between)
                     (t between p2)))))]
    t))

Now we can use it to get all the entailments as well.

;; This transforms the relation into a transitive relation
(run* [q]
      (fresh [a b]
             ((transitive subclass-of) a b)
             (== q [a b])))

Most Clojure sort algorithms you’ll find on the web assume you can fit all the items to sort into the memory of a single JVM instance. For example, many merge sorts will use partition to split the data set into 2 halves.

Where I work we frequently have to deal with large volumes of data where the data sets we deal with are far too large for these algos. Instead we have to find alternatives.

Here’s our approach to sorting large data. Although we did spend some time researching the problem, there’s bound to be more better algorithms out there. Please let me know if you find one!

Divide and conquer

To sort a large dataset we break it into smaller ‘bite-sized’ chunks which we can sort in memory, and write these sorted chunks to disk. Then we can run a lazy merge sort against these chunks. Although we currently run this on one node the nature of merge sort is that it can scale-out recursively and is compatible with map-reduce. In production use we’ve found that even on a single node huge datasets need a small degree of recursion just to avoid having too many chunks and running out of file handles. However, we’ll ignore recursion for the purposes of this discussion (we can always add it later).

A simple merge-sort function

First, let me print our merge-sort function minus the requisite doc-strings and comments.

(defn merge-sort
  ([^java.util.Comparator comp colls]
     (letfn [(next-item [[_ colls]]
               (if (nil? colls)
                 [:end nil]
                 (let [[[yield & p] & q]
                       (sort-by first comp colls)]
                   [yield (if p (cons p q) q)])))]
           (->> colls
                (vector :begin)
                (iterate next-item)
                (drop 1)
                (map first)
                (take-while (partial not= :end)))))
  ([colls]
     (merge-sort compare colls)))

Firstly, note the main function overload takes 2 arguments. The first is the Java comparator we’ll use to sort the data, the second is a collection of sorted sequences. These sequences don’t have to be in memory, they are lazy and their elements can be read in as we need them (from disk, network, etc.). However, we do assume the sequences have already been sorted with the same Java comparator given in the first argument. At the lowest level of recursion these sequences will be small enough to be sortable in memory and written out to disk – this is fairly trivial so we won’t cover it here.

We define a function called next-item which takes the collection sequences and returns a pair:

• the first value is the next result in the merge-sorted sequence. This is called the yield.
• the second value is the same collection of sequences we started with minus the yielded value. This is called the remainder and is used to calculate the next result.

Here’s the next-item function (first draft) :-

(fn [colls]
    (let [[[yield & p] & q]
          (sort-by first comp colls)]
        [yield (cons p q))]))

The first job of the function is to sort the collections of sequences by their first values.

(sort-by first comp colls)

Here, comp is just the Java comparator that dictates the order of the sort.

Now we destructure. Since the item we want is the first item of the first sequence, we destructure like this :-

[[yield & p] & q]

• yield is the item we are saying is the next item in the merged sorted sequence.
• p is the rest of the sequence which contained yield.
• q is the collection of all the other sequences.

(A nice ‘by-product’ of the sort-by is that q is already sorted. Even if the contents of p demand that we sort again, it won’t be an expensive operation. In fact, my own tests have shown that little or no performance improvement can be made by avoiding the use of Java’s sort by moving the head collection down the list – Java’s sort is very efficient for sets that are either ‘already sorted’ or ‘almost sorted’.)

Now we need to form our pair…

The first item is yield. That’s easy.

The second item is the collection of sequences with yield removed. That’s p joined onto the head of q, so we use cons.

(cons p q)

Remember that q is a collection of sequences sorted by ‘first item’. We don’t know that (cons p q) is sorted according to first item. It’s likely that the next result is in p or in (first q). However, we defer this sort operation to the next iteration, because re-sorting is the first thing we do in each iteration.

By the way, if p is nil then p is exhausted and we’ll just take q, hence this tweak :-

(if p (cons p q) q)

Putting this altogether, our final next-item function is as follows :-

(fn [colls]
    (let [[[yield & p] & q]
          (sort-by first comp colls)]
        [yield (if p (cons p q) q)]]))

Repeat as necessary

Each time we run the next-item function we’ll get the next result in our merged sorted sequence. Sounds like another job for Clojure’s iterate function!

Our next-item function needs to be amend slightly so that it can work iteratively – it needs to accept the same kind of structure that it produces. We amend the function signature so it can take a pair as the argument, and we destructure to ignore the first item and label the second.

(fn [[_ colls]]
    (let [[[yield & p] & q]
          (sort-by first comp colls)]
        [yield (if p (cons p q) q)]])

We’ll just have to initiate the iteration with a fake pair.

[:begin colls]

And we’ll have to ensure the iteration can tell the caller when to stop.

[:end nil]

Let’s build that ‘stop’ into our function :-

(next-item [[_ colls]]
  (if (nil? colls) [:end nil]
    (let [[[yield & p] & q]
          (sort-by first comp colls)]
      [yield (if p (cons p q) q)])))

Now the inner function is finished let’s move onto the main body of the merge-sort function.

 (->> colls
     (vector :begin)
     (iterate next-item)
     (drop 1)
     (map first)
     (take-while (partial not= :end))
     (lazy-seq))

We start by taking the colls argument and apply the ->> threading operator to it. This means that the result of each step will be added as the last argument of the next step.

(->> colls
    ... )

As we discussed earlier, we have to compose the first ‘fake’ pair to get the first iteration to work.

(vector :begin)

This creates [:begin colls]. We should remember this is also the first item that iterate will yield so we’ll have to drop it later.

Now let’s run our next-item function (infinitely)

(iterate next-item)

We don’t want the first ‘fake’ result – it was just to help the iterate function, let’s drop it :-

(drop 1)

We’re only interested in the yield values (the first in each pair) :-

(map first)

And we need to continue until the stop marker :-

(take-while (partial not= :end))

Finally we overload the merge-sort function to use a default comparator where it isn’t specified.

Testing

Let’s define a function that can create n collections of m size populated with random numbers.

user> (defn make-colls [n m]
  (for [i (range n)]
    (sort
     (for [j (range m)]
       (rand-int 1000000)))))

Let’s evaluate now so this structure in in memory and its creation doesn’t affect our merge-sort performance measurements.

user> (def colls (make-colls 100 20000))

Let’s test it to ensure that it’s working. We expect the first collection to be sorted.

user> (take 10 (first colls))

(15 33 88 94 114 119 148 164 189 190)

However, when we merge sort, the numbers from all the collections are merged so we get a less rapidly incrementing sequence of numbers.

user> (take 10 (merge-sort colls))    

(1 1 1 2 2 5 6 7 7 8)

Actually merge-sorting is quite useful

Sort algorithms are often used as a learning guide, especially for functional languages. But how useful is sorting for tackling business problems?

It turns out we use merge-sort in multiple places in our Clojure system. The first use was for grouping of risk data so it can be collated on a trade-by-trade basis. Then we decided to rewrite an old Java-based scheduler that was expensive to maintain. We now have a lazy scheduler (we call it ‘Chime’) that uses this lazy merge-sort to merge together multiple schedules of repeating tasks into a single schedule. I’ll discuss more about Chime in a future post.

It’s quite surprising to think that Java didn’t have an official logging API in the JDK until its fifth major release (1.4).

The sad history of Java logging

In the beginning there was System.out.println which writes out to the console. Many still use that today.

For those who needed more sophisticated logging, a package called log4j emerged in 1999 from IBM ‘alphaworks’. This steadily grew in popularity until it became the de-facto standard. Then Sun decided to write their own logging package and include it in the JDK, as java.util.logging. Not that there was anything significantly wrong with log4j, it was simply an example of the ‘not-invented-here’ syndrome that Sun was suffering from at the time. Despite a hard fought campaign to persuade Sun to incorporate log4j into the platform. Soon after, Sun realised that this sort of thing was damaging to Java’s reputation and created the JSR process to incorporate the wider Java community in decision making.

But the fact that Java had 2 near-identical logging packages led to further complexity. Apache created a facade called commons-logging that attempted to wrap both packages. By deciding to use a Java interface, Apache commons-logging negated the carefully crafted performance of the log4j package it was wrapping.

There have been attempts in the Java world to improve matters. One notable example is slf4j.

Logging in Clojure

Clojure logging neatly solves the problems of Java logging.

First, there’s a single API to use: clojure.tools.logging. Thank Alex Taggart and others for this. Second, it integrates with all the important logging frameworks: log4j, java.util.logging, Apache’s commons-logging and now slf4j. Finally, it side-steps many of the performance penalties associated with logging.

If you have a lot of logging statements in your code-base, you only want to pay the performance penalty for logging statements that are actually being written to the log file. However, too often CPU is wasted in creating a logging message only for that message to be filtered out later on. The conventional workaround in Java is to wrap every complex logging statement with a conditional.

if (logger.isDebugEnabled()) {
    logger.debug(x + " plus " + y + " is " + (x + y));
}

Without the conditional wrapper, the String concatenation would be quite expensive if it was ultimately unnecessary (for example, if the logger in question was configured to output warnings only). But the workaround is obviously cumbersome, implemented inconsistently and adds noise to the code’s readability. (Being the new(est) kid on the block, slf4j is able to make use of the JDK 1.5 varargs feature to avoid common string concatenation until after the message has made it through the filters).

Fortunately for Clojure programmer, the clojure.tools.logging takes care of this for them by using macros. As a Clojure programmer you get the benefit of optimized performance without the unsightly code-bloat.

Configuration

Unfortunately the Clojure logging facility doesn’t offer anything to help configure the logging package being used underneath.

Typically, Java logging is configured using configuration files. As you’d expect from Java, every configuration file is different, each one balancing flexibility with complexity. This is a horrible Java legacy to subject Clojure programmers to. An alternative approach is needed, so I’ve written a library: clj-logging-config.

You start by using requiring the library with :use (or :require) in your namespace declaration. In these examples I assume you are using log4j configuration, but you can configure java.util.logging in a similar way.

(ns my-ns
  (:use clojure.tools.logging
        clj-logging-config.log4j))

Then you configure the logging system declaring a logger with set-logger!

(set-logger!)

and just start logging :-

(info "Just a plain logging message")

Check your console (not the REPL).

console> INFO - Just a plain logging message

In log4j it is common to set a pattern against the logger. Full syntax can be found in org.apache.log4j.EnhancedPatternLayout. For example, to set a pattern which just displays the message, do this:

(set-logger! :pattern "%m%n")
(info "Just the message this time")

console> Just the message this time

Or this.

(set-logger! :pattern "%d - %m%n")
(info "A logging message with the date in front")

console> 2011-08-07 10:58:21,084 - A logging message with the date in front

In the same way you can set the level of the logger. For example, so that the logger only prints warnings, you can do this :-

(set-logger! :level :warn)

Or if you want to use the log4j Java class, you can do that as well :-

(set-logger! :level org.apache.log4j.Level/WARN)

You can also set the appender to one of the appenders provided by the logging package you are using. For example, you can do this :-

(set-logger! :out (org.apache.log4j.DailyRollingFileAppender.))

Or even provide your own appender function.

(set-logger! :out (fn [ev] (println (:message ev))))

You can also set filters in the same way. Filters are useful but rarely used in log4j because they’re fundamentally a function, and log4j configurations formats don’t support writing functions – perhaps they should have used LISP!

(set-logger! :filter (fn [ev] (not (re-seq #"password" (:message ev)))))

For filters and appenders the underlying logging event is converted to a Clojure map (with the original event bound to the :event key, should you need it)

You can also set the additivity of the logger – the default is true but you can set it to false. Addivity is described in the Log4J user-guide – so we won’t repeat it here.

(set-logger! :additivity false)

It (almost) goes without saying that you can combine all these options together :-

(set-logger! :level :warn
             :additivity false
             :pattern "%p - %m%n"
             :filter (constantly true))

There are some combinations that doesn’t make sense (such as using :pattern and :layout together). In these cases an exception will be thrown.

So much for getting started. In a real system you’ll want to configure multiple loggers in the same place :-

(set-loggers! 

    "com.malcolmsparks.foo"
    {:level :info :pattern "%m"}

    ["com.malcolmsparks.bar" "com.malcolmsparks.zip"]
    {:level :debug})

You’ll find a lot more in this package, including support for per-thread (per-agent) logging which is useful in certain situations. One of the design goals of this library is that it ‘does the right thing’ most of the time. The aim is to prevent the common experience in log4j where you can’t figure out why you can’t see your logging statements and revert to println in frustration.

I do hope that Clojure programmers find this library useful. The only way to find out is to ask people to use it. It definitely needs more exposure to real projects but I wanted to release it now to get more feedback. The library is licensed under the EPL (same as Clojure’s) and available here.

Processing files as a stream is a good strategy. It minimizes ‘out of memory’ errors by utilizing a plentiful supply of disk space. How do you process a large file as a stream in Clojure?

We start by breaking the file up into a lazy sequence of tokens. The Clojure core library contains a function called line-seq that breaks a file into individual lines. Or you can use the input-stream or reader functions in the clojure.java.io namespace to turn a file into a lazy sequence of bytes or characters if you need finer granularity to form your own tokens depending on the nature of the data you are reading.

(ns example
  (:require [clojure.java.io :as io]))

(line-seq (io/reader "bigfile"))

This is simplified for the purposes of this article. In real-world scenarios you may choose to improve performance by using NIO memory-mapped files. These techniques utilize main memory when it’s available without breaking the system when it isn’t.

Tokenizing

Invaribly you will form a lazy sequence of tokens in some way. How should we go about processing these tokens? I’ve found that using a state machine is a useful approach. We first define some initial state. Our tokens are fed to a function (which we’ll call f) along with the existing state. The function returns a new state, possibly changed.

Pacman

There are lots of other uses for this idea. Imagine we are asked to re-create the game of Pacman. We can list all the elements of the Pacman world :-

• Our hero, Pacman
• The positions of the ghosts
• The maze
• The pills
• The magic pills
• The existence of fruit
• Whether the ghosts are afraid of Pacman or not
• The player’s score
• The number of lives the player has left
• The state of the player’s joystick

We can store all this data in a single data-structure we call ‘the state’. We define a function, f, which is given the current world as an argument and which computes the new world we would expect to see on the screen one frame later. The job of programming the game of Pacman is then greatly simplified – we just call f iteratively and letting the game run as a ‘feedback loop’. All we have to do is implement the function f. (That job is left to the reader!)

How to apply the state-machine pattern in Clojure

There are a number of ways you can apply the state-machine method in Clojure. One simple way is to use the ‘second form’ of the reduce function in the Clojure core library (that’s the one that takes some initial state).

 (reduce f {} coll)

This first calls the function f with two arguments- an initial state (we used an empty map here) and the first element of the collection. The result of this becomes the first argument of another invocation of the same function, while the second argument is the next element of the collection. This repeated function application continues until the collection is exhausted.

Let’s pretend our tokens are ‘H’, ‘A’, ‘L’. This would be the result of applying reduce :-

 (f (f (f {} 'H') 'A') 'L')

The reduce function is a good starting point but it usually the wrong choice of function for parsing token streams :-

• It is not possible to look-ahead to know what subsequent tokens will be
• The function must always consume each token and cannot push the token back onto the stream.

Many parsers need both these features. So we need a refinement.

There’s also another subtler problem with reduce that we’ll come on to :-

• We can’t inspect the operation of reduce while it is running, we have to wait for it to complete.

Using iterate

Fortunately the Clojure core library contains a more general method for the repetitive application of a function: iterate.

Here’s how we can use iterate to replace reduce.

(iterate f {:remaining coll})

Our state is initialized with the stream itself. The function has the responsibility for taking the first element and processing it. It returns a new state with a new entry representing the remaining elements. Usually the function will replace the :remaining element with remaining elements of the collection once the first element has been processed. However, it can do anything it chooses with this element, including looking ahead for future tokens and pushing back old ones.

The function is repeatedly applied with the map. The map can contain any state that is necessary for the processing of the stream. Often this includes stacks (vectors) to retain state at each level of context.

For the purposes of the rest of this article we’ll rewrite this using the ->> threading macro. We use this macro a lot when manpulating sequences.

(->> {:remaining coll}
     (iterate f))

Preventing infinite application

The problem with iterate is that it tends to go on forever. We can avoid this by adding an :end into our map when we detect the end of the stream. We can then make the resulting sequence finite by using take-while.

(->> {:remaining coll}
     (iterate f)
     (take-while #(not (contains? :end %))))

Since iterate returns a sequence of states we can choose to inspect any single state

Yielding

Often we want to parse a stream of tokens into a stream of something else, usually something more concrete and coarse-grained.

For example, huge XML files are often the result of repeated structures. In my case, this could be the calculated risk for every trade in a book. The structure itself for each trade isn’t complicated, but a large number of trades can make the resulting file very large. We have an algorithm for turning a stream of XML events into a stream of ‘virtual’ XML documents, each representing the entire XML file as it would look like if it contained just a single trade. The ‘stream’ is made up of these virtual XML documents, one of each trade. This allows us to tame the size of the file and avoid reading the entire file into memory.

The way to solve this problem is to allow our function to ‘yield’ whenever it has enough information to return a new data structure. We use the key :yield in the returned map to indicate this.

We use filter to filter out interrim states.

(->> {:remaining coll}
     (iterate f)
     (take-while #(not (contains? :end %)))
     (map :yield)
     (filter #(not (nil? %))))

Factoring out the pattern

It’s time to put all this together in its own function.

(defn parse [f coll]
  (->> {:remaining coll}
       (iterate f)
       (take-while #(not (contains? :end %)))
       (map :yield)
       (filter #(not (nil? %)))))

Destructuring

We now discuss the function f. Before we provide examples, let’s explain the structure of these functions a little more. The function f is given a map as its only parameter.

This example function does nothing except consume the first token. It does this by applying next to the :remaining entry in the map.

(fn [m]
    {:remaining (next (:remaining m))})

This is less convenient than if we had named arguments for everything in the map, but we can use destructuring to get close to this.
So here’s our function we some destructuring :-

(fn [{remaining :remaining}]
    {:remaining (next remaining)})

But usually we want to do something with each token in the stream. Let’s destructure a little more.

(fn [{[token & remaining :as stream] :remaining}]
    {:remaining remaining})

This sets token to the token in the stream we shall process, remaining as the collection of tokens that remain in stream after the token and stream as the collection of remaining tokens includinng the token. This last setting is achieved using the :as keyword. This is useful when we want to return a new state but without consuming the token, equivalent to a pushback. There are certain cases where this is useful.

Notice also how destructuring allows us to balance the complexity of the function body with the function signature. Let’s digress while we’re discussing destructuring to show how far we can go.

Extreme destructuring

Jay Fields provides a good overview of the destructuring ‘mini-language’ inside Clojure. At the time of writing there aren’t many other good web resources so I’ll show how useful destructuring can be for our example.

[jf]: http://blog.jayfields.com/2010/07/clojure-destructuring.html “Jay Fields”

In a real-world situation our function will need to make use of other entries in the map. Let’s assume our map also contains entries for :stack, :indent and :count. We can destructure these in one go using the :keys keyword :-

(fn [{[token & remaining :as stream] :remaining
                 :keys [stack indent count]
                 :or {indent 0}}]
    {:remaining remaining})

In the case of indent we have also indicated a default value of 0. Variables that do not have corresponding keys in the map argument and which do not have defaults get the value of nil.

Footnotes

The pattern described involes a lot of map manipulation. Of course, thanks to Clojure’s STM (Software Transactional Memory) we can mutate the map without worrying about where else we’ve referenced the map, since those values won’t change. However, since we often want to change multiple values in the map it would be useful to have a helper function.

(defn
  ^{:doc "Apply functions to values in a map."}
  mapply
  [m & kfs]
  (apply hash-map
         (mapcat (fn [[k f]] [k (f (get m k))])
                 (partition 2 kfs))))

In some situations mapply has certain advantages over assoc. With assoc we have to get the data value out of the map, apply a function to it and then put it back in the map. We have to be careful to use the same key for the access and overwrite operations. By contrast, with mapply we send the function straight to the map entry.

With mapply, keys that are not specified are removed from the map. This is usually the safest thing to do to prevent temporary entries from bleeding across multiple state transitions. But it is easy to retain existing values in the map by specifying the key with the value of identity.

;; Increment :count and retain the value of :foo.
(mapply {:count 1 :foo "foo"} :count inc :foo identity)

Finally, mapply can insert a new value, just like assoc does, by applying the constantly function.

;; Remove :count and set the :foo to "bar".
(mapply {:count 1 :foo "foo"} :foo (constantly "bar"))