the zero bit stream

programmer things

Lazy Sequences in Common Lisp

0. Delayed Evaluation with Closures

Last week I expressed some anti-lazy sentiment, or at least it was perceived as such. Really, I am just not a fan of laziness by default. Common Lisp is decidedly not lazy by default, but it is easy to defer or avoid computation with closures. With macros, we can add it to the language in an easy-to-use form.

Common Lisp is not a lazy language, but it is easy enough to add lazy sequences. We can model them after the normal list which is constructed piecemeal with the cons operator. The following recursive function builds a list of numbers counting down to 0 using cons.

(defun countdown (n)
  (if (>= n 0)
    (cons n (countdown (1- n)))))

(countdown 10)
;;--> (10 9 8 7 6 5 4 3 2 1 0)

(reduce #'+ (countdown 100))
;;--> 5050

This is a common pattern, but there are some shortcomings. First of all, it’s not a tail recursive function, so this call will always build the stack since tail call optimization or tail recursion elimination does not apply, and will do so linearly with the argument n. Also, it constructs the entire list. You may want this list of numbers, but you don’t need all of them right away sitting in memory. In the example above, the call to reduce gets a full list of 101 elements, from 100 to 0 before processing. Depending on the length of the sequence, a different algorithm might work better.

One way (of many) to construct lazy sequences in Common Lisp is to store the CDR (second part) of the CONS cell as a thunk, or a closure that takes no argument and computes the next CONS in the list.

(defun lazy-countdown (n)
  (if (>= n 0)
    (cons n (lambda () (lazy-countdown (1- n))))))

(lazy-countdown 10)
;;--> (10 . #<CCL:COMPILED-LEXICAL-CLOSURE (:INTERNAL LAZY-COUNTDOWN) #x30200F59400F>)

We can grab the first element of the lazy list with CAR per normal, but to get the next CONS cell, we need a version of CDR which FUNCALLs the thunk. That will call LAZY-COUNTDOWN which will return another CONS cell.

(defun lazy-cdr (lazylist) (funcall (cdr lazylist)))

(lazy-cdr (lazy-countdown 10))
;;--> (9 . #<CCL:COMPILED-LEXICAL-CLOSURE (:INTERNAL LAZY-COUNTDOWN) #x30200F55B7BF>)

So far, so good. Now we need a version of REDUCE which uses LAZY-CDR instead of CDR, and can reduce a lazy list for us.

(defun lazy-reduce (f lazylist)
  (labels ((inner-reduce (lazylist acc)
             (if lazylist
               (inner-reduce (lazy-cdr lazylist) (funcall f acc (car lazylist)))
               acc)))
    (inner-reduce (lazy-cdr lazylist) (car lazylist))))

(lazy-reduce #'+ (lazy-countdown 1000))
;;--> 500500

1. Use CLOS and Macros for a Nice Interface

In order to use this pattern easily, we will create a nice interface. We’ll package up the lazy list into its own class, which I will call LCONS and use a macro of the same name to construct lazy lists by automatically wrapping the second argument in a thunk.

(defclass lcons ()
  ((val :initarg :val)))

(defmacro lcons (head tail)
  `(make-instance 'lcons
                  :val (cons ,head (lambda () ,tail))))

For our interface, I am going to use methods HEAD, TAIL and EMPTY? to approximate CAR, CDR, and NULL and make them compatible with normal lists.

(defgeneric empty? (lcons))
(defgeneric head (lcons))
(defgeneric tail (lcons))

(defmethod empty? ((lcons lcons))
  nil)

(defmethod empty? ((lcons list))
  (null lcons))

(defmethod head ((lcons lcons))
  (car (slot-value lcons 'val)))

(defmethod head ((lcons list))
  (car lcons))

(defmethod tail ((lcons lcons))
  (funcall (cdr (slot-value lcons 'val))))

(defmethod tail ((lcons list))
  (cdr lcons))

Now, we can redefine LAZY-COUNTDOWN, just the same as the original COUNTDOWN but use LCONS instead of CONS.

(defun countdown (n)
  (if (>= n 0)
    (cons n (countdown (1- n)))))

(car (cdr (countdown 10)))
;;--> 9

(defun lazy-countdown (n)
  (if (>= n 0)
    (lcons n (countdown (1- n)))))

(head (tail (lazy-countdown 10)))
;;--> 9

Now, we can define functions to do things that are normally only for regular lists that work with lazy lists, also. A good candidate is MAPCAR. Here’s a version that works with lazy lists:

(defun lmapcar (f &rest lists)
  (if (notany #'empty? lists)
    (lcons (apply f (mapcar #'head lists))
           (apply #'lmapcar f (mapcar #'tail lists)))))

(head (lmapcar #'+ (lazy-countdown 10) (countdown 10)))
;;--> 20

Notice that LMAPCAR is lazy, too. It returns an LCONS (lazy list). In this way we can build up a collection of functions just like the normal functions on lists in Common Lisp, but ones that take and return lazy lists.

Just like lazy sequences in other languages, these sequences can be infinite. Here’s a function INTEGERS which builds an infinite lazy list of integers.

(defun integers (n) (lcons n (integers (1+ n))))

(head (tail (tail (integers 0))))
;;--> 2

I have encoded this into a project which is available on github: slow-jam . It is the above code with a few extra functions that take and/or return lazy sequences. Here are a few examples of things you can do with the library:

;; infinite sequences that print nicely on the REPL
(range)
;;--> (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ETC...)

(take 10 (range))
;;--> (0 1 2 3 4 5 6 7 8 9)

;; FILTER is lazy
(take 5 (filter #'evenp (range)))
(0 2 4 6 8)

One advantage of this approach is that the tail of the lazy list is never cached which means that, unless you use the TO-LIST function provided in the library to turn a lazy list into a normal list, all the elements of your lazylists (except the first) can be garbage collected. These lists never take much permanent memory. The downside is that results are not cached, and you may end up recalculating the same list elements more than once. For that reason, these lists should be built in using side-effect-free functions. If you do want to cache the contents of a lazy list, just call TO-LIST which returns real list and keep a reference to that.

This is just one implementation of lazy sequences in Common Lisp. It is partially inspired by Clojure, Haskell, and SICP. If you like the slow-jam library and want it to be better, report an issue or make a pull request at github.