Wednesday, July 6, 2011

Common Lisp lazy sequences

When we left things in Part 2, we needed a function that would return an infinite sequence of the same argument. In Clojure, we saw that function is used like so:

(repeat "+") ;; "+" is the argument to repeat infinitely

Common Lisp does not have infinite sequences built in, but they are easy to implement. The Common Lisp library clazy is an implementation of them. For the sake of demonstration, we will sort of reinvent that implemenation in a simpler fashion.

Lazy sequences

Without further ado, here is the code to implement a very rudimentary lazy sequence library:

(defpackage my-lazy
  (:use :cl)
  (:shadow cl:cdr cl:mapcar)
  (:export "CDR" "MAPCAR" "DELAY" "FORCE" "REPEAT"))

(in-package :my-lazy)

(defstruct thunk
  body)

(defun thunkp (arg)
  (eq (type-of arg) 'thunk))

(defmacro my-lazy:delay (expr)
  `(make-thunk
   :body (lambda () ,expr)))

(defun my-lazy:force (thunk)
  (if (thunkp thunk)
      (funcall (thunk-body thunk))
      thunk))

(defun my-lazy:repeat (arg)
  (cons arg
    (delay (repeat arg))))

(defun my-lazy:cdr (cons)
  "cdr for lists, force cdr for thunks"
  (force (cl:cdr cons)))

(defun my-lazy:mapcar (f list &rest more-lists)
  "Apply FUNCTION to successive elements of LIST. 
Return list of FUNCTION return values.
lists can be lazy"
  (cons (apply f
           (car list)
           (cl:mapcar 'car more-lists))
    (when (and (cdr list) (every #'identity more-lists))
      (apply 'mapcar
         f
         (cdr list)
         (cl:mapcar 'cdr more-lists)))))

The first thing you'll notice is that we create a lazy package called "my-lazy" that when used will shadow some core functions (cdr and mapcar). This shadowing is necessary because we need these functions to operate similarly regardless of if the sequence is a list or a lazy list.

Also, you'll notice that we create a structure called a "thunk" (eg defstruct thunk). Wikipedia defines a thunk as:

In computer science, a thunk (also suspension, suspended computation or delayed computation) is a parameterless closure created to prevent the evaluation of an expression until forced at a later time.

We define a thunk as a structure instead of simply a parameterless lambda so that our thunks have a type unique from any other parameterless function.

The two key items here are delay and force. Delay is a macro that creates a thunk from an expression. Force is a function that forces the evaluation of a thunk.

Cdr is redefined to "force" evaluation of the core cdr of a cons cell if the core cdr is a thunk. Otherwise, our cdr simply returns the core cdr of the cons cell.

Mapcar is also redefined. Basically, it is only redefined to use our version of cdr. Besides that, it does basically the same thing as the core mapcar.

Now let's check our example. First in Clojure:

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")

Next using our new package in Common Lisp:

CL-USER> (in-package :my-lazy)
#<PACKAGE "MY-LAZY">

MY-LAZY> (mapcar (partial 'str "price & tip: ") 
          '(5000 100 50) (repeat "+") '(2000 40 10))
("price & tip: 5000+2000" "price & tip: 100+40" "price & tip: 50+10")

Huzzah! We have successfully replicated standard Clojure functionality in Common Lisp.

Conclusion

In Part 1 we looked at modifying the Common Lisp syntax using reader macros. In Part 2 we looked at simplifying function calls using currying techniques. Here, in Part 3, we implemented infinite sequences which eliminated a (sometimes) hard to find bug.

The great thing about Common Lisp is that it is extremely easy to implement all of these concepts. In most other languages, implementing these concepts would almost definitely be either more difficult or not possible. The only drawback is that often there is too much freedom. The Common Lisp ethos is such that developers are encoraged to implement these concepts on their own. The result is, unlike the Clojure world, often there is no cannonical answer to these problems (such as lazy sequences). As a fan of Common Lisp, I'd like to see it gain more traction. Perhaps that will take one killer application (like Rails for the Ruby language). For that to happen, it will probably also need more coherance across the community. Regardless, because of its flexibility, it is still, in my opinion, the ultimate hacker language.