« OINK = GROK | Main | In Paris »

## 2006-05-03

### Fun with Lazy Evaluation

I was a bit bored and decided to play with lazy evaluation in Common Lisp. This has been done before in various publications about functional programming (including some of my own...), but I had fun doing this (read: don't flame me).

Common Lisp lists lend themselves well to lazy evaluation: we can make list construction (function `cons`

) lazy wrt. the tail of the constructed list. This means that we only construct the list as far as the first element goes, and *delay* the construction of the tail. Functions that traverse lists (mainly, `cdr`

) will *force* the construction of the remaining list, typically just one element at a time.

So here goes: First, we need a package for our new fun functions. Let's call it "LAZY". We need to shadow those CL functions we intend to redefine in our lazy framework.

```
(defpackage lazy
(:use :cl)
(:shadow cl:cdr cl:cons cl:mapcar cl:list-length cl:dolist)
(:export "CDR" "CONS" "MAPCAR" "LIST-LENGTH" "DOLIST"))
(in-package :lazy)
```

Then, we need a basic mechanism for delayed evaluation, as follows:

```
(defstruct (delay
(:constructor make-delay (closure))
(:predicate delayp))
closure)
(defmethod print-object ((self delay) stream)
(princ "..." stream))
(defmacro delay (form)
`(make-delay #'(lambda () ,form)))
(defun force (thing)
(if (delayp thing)
(funcall (delay-closure thing))
thing))
```

Basically, instances of `delay`

are encapsulations of delayed evaluation, implemented using the lexical closure mechanism of CL. The macro `delay`

will delay any form, and the function `force`

will force the evaluation of a delayed form. If the argument passed to `force`

is not delay, `force`

effectively acts as the `identity`

function.

Now, we can define our basic lazy functions (and one macro):

```
(defun lazy:cdr (cons)
(setf (cl:cdr cons) (force (cl:cdr cons))))
(defmacro lazy:cons (head tail)
`(cl:cons ,head (delay ,tail)))
(defun lazy:mapcar (function list &rest more-lists)
(cons (apply function (car list) (cl:mapcar #'car more-lists))
(apply #'lazy:mapcar function (cdr list) (cl:mapcar #'cdr more-lists))))
(defun lazy:list-length (list)
(labels ((ll (list n)
(cond ((consp list) (ll (cl:cdr list) (1+ n)))
((null list) n)
(t nil))))
(ll list 0)))
(defmacro lazy:dolist ((var list &optional value) &body body)
(let ((s (gentemp)))
`(do* ((,s ,list (cdr ,s))
(,var (car ,s) (car ,s)))
((null ,s) ,value)
,@body)))
```

The explicit `lazy:`

package prefixes are not necessary but I put them there for clarity. Notice that `cdr`

is essentially the only function that calls `force`

, and it will replace the forced delay with the result in the data structure; that way delays are not forced multiple times. We could have built this into the `delay`

class of course, but I feel this is more elegant.

Next, we define some "helper" functions:

```
(defun first-n (list n)
(and list
(plusp n)
(cl:cons (car list) (first-n (cdr list) (1- n)))))
(defun numbers (&optional (start 1) (end nil))
(unless (and end (> start end))
(cons start (numbers (1+ start) end))))
```

The function `first-n`

will force the construction of a lazy list for the first (at most) *n* elements. The function `numbers`

allows one to construct lists of consecutive integers, optionally specifying an end. Notice that the end is not necessary, we can construct infinite lists. The new definition of `dolist`

will not do well with infinite lists, since it eagerly traverses the entire list it is given. I suppose

```
(dolist (i (numbers 1))
...)
```

is one way of doing an infinite loop now.

Finally, we get to the "showing off" part. The idea is borrowed from Henderson's book on functional programming: We will define a function that computes a list of all primes. Yes, all of them, since the list will be lazy. Here goes:

```
(defun primes ()
(labels ((filter-multiples-of (n list)
(if (zerop (mod (car list) n))
(filter-multiples-of n (cdr list))
(cons (car list) (filter-multiples-of n (cdr list)))))
(primes-from (n)
(cons n (filter-multiples-of n (primes-from (1+ n))))))
(cons 1 (primes-from 2))))
```

This function will construct the list of primes as a cascade of filters, each filtering away the multiples of the previous prime in the list.

Posted by ora at 14:10