« 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