lazy evaluation in Common Lisp

One of interesting features of Haskell is a lazy evaluation. This is not always desirable but sometimes it allows to implement some tricks which are not obvious for someone with eager language experience.

If you started to learn Haskell with "Gentle introduction in Haskell" (BTW, I feel your pain) one of the first examples is calculating list of well known Fibonacci numbers. In Haskell it looks like this:

fib = 1 : 1 : [ x + y | (x,y) <- zip fib (tail fib) ] 

If you are not familiar with Haskell it looks like complete Vodoo magic. Something like if you are a mathematician and you see expression like

x = x + 1

Surely, it it is never true!

Anyway, this function goes like this:

• First two numbers of the result list are the ones
• The rest values are the sum of previous value of the list and one preceding that value. zip fib (tail fib) does the trick.
  

Lazy evaluation here make sure fib is not evaluated fully. It might be called "greedy" because it gives values up only when necessary.

Anyway, lazy evaluation can be replicated by Lisp if you hide values in lambda. It won't be evaluated unless you explicitly asked it to do so by funcall.

For conses it can be presented like this:

(defmacro fcons (first list)
  (let ((f-var (gensym)))
    `(let (,f-var)
       (lambda ()
  (if (null ,f-var)
      (progn (setf ,f-var ,list)
      ,first)
      (funcall ,f-var))))))

Define zip function:

(defun zip (l1 l2)
  (lambda ()
    (list (funcall l1) (funcall l2))))

We also need a special map function which "lift" some function into our lazy lists:

(defun fmap (f iter)
  (lambda ()
    (funcall f (funcall iter))))

This function transforms lazy list into it's tail:

(defun ftail (list)
  (funcall list)
  list)

So, finally we can write a Fibonacci numbers function:

(defun fib ()
  (fcons 1
  (fcons 1
  (fmap (lambda (x)
   (+ (first x) (second x)))
        (zip (fib) (ftail (fib)))))))

Try it in REPL:

CL-USER> (setq *fib-function* (fib))

CL-USER> (funcall *fib-function*)
1
CL-USER> (funcall *fib-function*)
1
CL-USER> (funcall *fib-function*)
2
CL-USER> (funcall *fib-function*)
3
CL-USER> (funcall *fib-function*)
5

Or even better:

(defun take (n list)
  (loop repeat n
 collect (funcall list)))

(take 100 (fmap #'print (fib)))
...

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946