Streams in Common Lisp

One of nicest techniques from Scheme is the idea of streams. Streams¹ let you create a virtually infinite list. For example, we can compute the square roots of the first 5 Fibonacci numbers with

(mapcar #'sqrt '(0 1 1 2 3))

But suppose we want to print the square roots of an arbitrary number of Fibonacci numbers. We’d like something like

(setq list-of-fibonacci-numbers '(0 1 1 2 3 5 8 13 21 34))
(defun sq-roots (n l)
  (when (> n 0)
    (print (sqrt (car l)))
    (sq-roots (1- n) (cdr l))))

(sq-roots 5 list-of-fibonacci-numbers)

0.0 
1.0 
1.0 
1.4142135 
1.7320508 

where list-of-fibonacci-numbers has at least \(n\) members. Of course we don’t know what \(n\) will be so we really need a infinite list of Fibonacci numbers. That’s what streams do. They simulate an infinite list by calculating the members of the list on-the-fly as needed.

Atabey Kaygun has a nice post that considers how to implement Scheme streams in Common Lisp. Rather than simply duplicate the Scheme implementation, which, as I show below, is relatively easy, Atabey produces two different implementations. One, that he describes as “stateful,” uses a closure to remember the state of the stream and calculate the next value.

The other method is more functional and builds an actual list as the calculation proceeds. He uses this method to build a stream, fibonacci, that returns the Fibonacci numbers. Using that we can solve our problem as

(defun sq-roots (n)
  (labels ((roots (i l)
             (while (> i 0)
               (print (sqrt (car l)))
               (roots (1- i) (cdr l)))))
    (roots n (f-take n fibonacci))))

We can’t express the Fibonacci numbers with Atabey’s stateful implementation but it could be trivially modified to permit it. The trouble with the stateful solution, as Atabey tells us, is that it’s use-once. Even if we hold its head, any use of the stream modifies its internal state so that further uses reflect what has already happened.

These examples are instructive but notice that we must build the list of \(n\) Fibonacci numbers before we can start the calculations. What if \(n=10^{10}\)? That’s a pretty big list and will almost surely exceed the memory of most computers. What we’d like is a “lazy list” that calculates its elements on-the-fly. That’s what streams do.

Here’s a Common Lisp implementation based on the Scheme from Section 3.5 of SICP. The real implementation builds memoization into delay but we ignore that for simplicity. See SICP’s implementation or Atabey’s memoization post for details. The basic building blocks are given below:

(defmacro delay (expr)
  `(lambda () ,expr))

(defun force (delayed-object)
  (funcall delayed-object))

(defmacro cons-stream (x y)
  `(cons ,x (delay ,y)))

(defun stream-car (s)
  (car s))

(defun stream-cdr (s)
  (force (cdr s)))

The delay macro delays the evaluation of expr by wrapping it in a function. The force function evaluates the delayed expression by calling the function that it got wrapped in. The cons-stream builds a cons from \(x\) and \(y\) but arranges to delay the evaluation of \(y\). The last two functions are direct analogues of their list counterparts but operate on streams instead. Notice that we can do without stream-car since it merely calls car. See SICP for further explanation.

Now, we can build some infinite lists (streams). Suppose we want an infinite list of integers. Here it is:

(defun integers (&optional (n 1))
  (cons-stream n (integers (1+ n))))

The first time it’s called, integers returns

(1 . (lambda () (integers (1+ n))))

where \(n=1\) and \(n\) is held in integers‘ closure. When stream-cdr is called on this, the call to integers will be evaluated and return

(2 . (lambda () (integers (1+ n))))

with \(n=2\). Thus, the physical stream is just a single cons but it acts as an infinite list of integers.

Let’s take the square root of the first \(n\) integers. First we define a function to take the square root of the first \(n\) elements of a stream:

(defun sq-roots-of-stream (n s)
  (when (> n 0)
    (print (sqrt (stream-car s)))
    (sq-roots-of-stream (1- n) (stream-cdr s))))

and then pass it a steam of integers:

(sq-roots-of-stream 10 (integers))

1.0 
1.4142135 
1.7320508 
2.0 
2.236068 
2.4494898 
2.6457512 
2.828427 
3.0 
3.1622777

Notice that the list of integers is not calculated in advance.

Here’s the solution to our original problem. First, a stream of Fibonacci numubers:

(defun fibs (&optional (a 0) (b 1))
  (cons-stream a (fibs b (+ a b))))

and then we reuse sq-roots-of-stream to calculate the results:

(sq-roots-of-stream 10 (fibs))

0.0 
1.0 
1.0 
1.4142135 
1.7320508 
2.236068 
2.828427 
3.6055512 
4.582576 
5.8309517

Once you get the hang of it, it’s really easy to work with streams and it avoids having to precalculate large lists of intermediate results.