Wednesday, July 6, 2011

Common Lisp currying

In Part 1 we looked at adding to the Common Lisp syntax using a reader macro. Now we are going to use a regular function to implement a technique called "currying". We do this to abstract away a function call with a common argument. So instead of calling the same function with the same argument over and over again in your code, you can curry that function call w/ argument into a symbol that can be called on its own.


Wikipedia defines currying as:

In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments (or an n-tuple of arguments) in such a way that it can be called as a chain of functions each with a single argument (partial application).

In Part1, we needed to curry the function "concatenate" with the argument "'string". There are a number of ways to do this. We are going to build a currying function called partial that approximates the Clojure function of the same name.


The example which uses the partial function in Clojure comes from here. Below is the same example using the #() reader macro from Part 1 along with a slightly more readable and compact version using partial.

user> (map #(apply str "price & tip: " %&) 
              [5000 100 50] (repeat "+") [2000 40 10])
("price & tip: 5000+2000" "price & tip: 100+40" "price & tip: 50+10")

user> (map (partial str "price & tip: ") 
              [5000 100 50] (repeat "+") [2000 40 10])
("price & tip: 5000+2000" "price & tip: 100+40" "price & tip: 50+10")

Notice how the use of partial gets us out of the prosaic work of using a reader macro and "applying" a list of arguments to the magic "%&" argument. The "%&" list argument is implied when we use partial.

Partial turns out to be another trivially easy function to write in Common Lisp.

(defun partial (f &rest args)
  "currying function"
  (lambda (&rest more-args)
    (apply f (append args more-args))))

Essentially, we are merging together the arguments we know with the arguments we will be passing into the curried function. Let's demonstrate it in action.

CL-USER> (mapcar [apply 'concatenate 'string "price & tip: " %&] 
          '("5000" "100" "50") (loop repeat 3 collect "+") '("2000" "40" "10"))
("price & tip: 5000+2000" "price & tip: 100+40" "price & tip: 50+10")

CL-USER> (mapcar (partial 'concatenate 'string "price & tip: ") 
          '("5000" "100" "50") (loop repeat 3 collect "+") '("2000" "40" "10"))
("price & tip: 5000+2000" "price & tip: 100+40" "price & tip: 50+10")

CL-USER> (setf (symbol-function 'concatenate-string) 
          (partial 'concatenate 'string))

CL-USER> (mapcar (partial 'concatenate-string "price & tip: ") 
          '("5000" "100" "50") (loop repeat 3 collect "+") '("2000" "40" "10"))
("price & tip: 5000+2000" "price & tip: 100+40" "price & tip: 50+10")

Now we are getting somewhere. Using partial we've been able to turn the symbol 'concatenate-string into almost the same thing as the Clojure function "str".

String methods

The more astute readers may notice the Common Lisp examples still contain a little extra cruft not found in the Clojure examples.

The two pieces of cruft I am referring to are:

  • The Common Lisp version contains double quotes around the price literals. Thus starting them out as strings. The Clojure version simply uses numbers and within the "str" function they get converted to strings. We'll adapt the Common Lisp version to do the same.
  • The more dastardly of the crufty items is the lack of Clojure's "repeat" function. The Clojure "repeat" function simply repeats the argument infinitely as a sequence of items. This works in our example because map stops when one of the finite list args runs out of items. Our Common Lisp version relies on us to use the "loop" macro. In using "loop", we must specify an iteration value that matches exactly the length of the longest of the other list args. Failure to do so will cause our code to short circuit. This can be the source of maintenance bugs in production code.

Let's tackle the first piece of cruft. Here's the Common Lisp code:

(defmethod to-string (arg) (string arg))
(defmethod to-string ((arg integer)) (write-to-string arg))

(defun str (&rest args)
  (apply 'concatenate-string  (mapcar #'to-string args)))

The first thing to notice is the use of "defmethod" instead of "defun". Defmethod is a way to create functions that are dispatched differently at runtime based on argument type. So if we pass an integer argument to "to-string", the result will be:

(write-to-string arg)

Whereas, if we pass an argument of any other type to "to-string" the result will be:

(string arg)

In other words, the latter "result" function is the default, whereas the former is a specific type implemenation. This gives us great flexibility to extend "to-string" in the future without redefining any current methods.

The "str" function behaves just like the Clojure equivalent. It takes in a list of arguments and turns them all into strings before sending them along to our "concatenate-string" function.

Approximating the Clojure "repeat" function is a little more tricky. It will require us to implement infinite lists. Part 3 will demonstrate how to do that.