Lazy (evaluated) sequences - part 2.
In the last blog post I've talked about lazy sequences that are generated by a generator. The generator needs state to remember what number (or thing) it has generated before in order to generate the next. A consumer simply asks the generator about the next 'thing'.
This way of implementing lazy evaluated sequences has two negative consequences (thanks for pointing this out, Rainer). 1) there is not really a list or sequence data structure (not even a 'lazy' one :). The consumer generates a result data structure (a list) by repeatedly asking the generator for the requested number of items. 2) it is not possible to re-use a lexically scoped generator like below. Because it keeps state it will continue counting.
(let ((generator (range)))
(print (take 3 generator))
(print (take 2 generator)))
(0 1 2)
;; where we would expect:
(0 1 2)
So we will look at proper lazy sequences. What I'm writing about is fully handled in the book "Structure and Interpretation of Computer Programs" chapter 3.5. I have changed the names of functions slightly in order to be better comparable to the naming scheme in the last blog post.
As you might know, a
cons cell is the basis for lists. A
cons is constructed of two cells. In Lisp the left part is called
car and the right part is called
cdr (those two names still refer to (maybe obsolete) implementation details as 'address register' and 'decrement register'). With combining conses it is possible to generate linked lists when the
cdr is again a
car also represents the head of the list and the
cdr the tail.
Now, in lazy sequences the computation of the
cdr part is deferred until needed like this. (I've called this
cons wrapper just
(defmacro lazy-cons (a b)
`(cons ,a (delay ,b)))
This generates a normal
cons from two values only that the second, the
cdr, is not evaluated yet. The
delay is simply just
b wrapped into a lambda like this:
(defmacro delay (exp)
`(lambda () ,exp))
So if we would macroexpand this we would get just this:
(lambda () b))
But it is good to create a new layer of meaning so I want to create a few primitives to hide the details of this and to make working with lazy sequences more natural similar to a normal
Both of the definitions above have to be macros because otherwise both
b when passed into
lazy-cons would be evaluated immediately. But that should be delayed until wanted.
In order to access
cdr of the
lazy-cons we introduce two more primitives,
(defun lazy-car (lazy-seq)
(defun lazy-cdr (lazy-seq)
(force (cdr lazy-seq)))
lazy-car just calls
car. We could certainly just use
car directly, but to be consistent and to create a new metaphor to be used for this lazy sequence we'll add both.
lazy-cdr does somthing additional. This is a key element. When accessing the
cdr of the list we now enforce the computation of it.
force is very simple. Where
delay wrapped the expression into a lambda we now have to unwrap it by funcalling this lambda to compute the expression. So
force looks like this:
(defun force (delayed-object)
Those 5 things are the base primitives to construct lazy sequences. Now let's create a new
range function - which now is not a generator anymore.
(defun range (&key (from 0))
(range :from (1+ from))))
range implementation doesn't need state. It simply constructs and returns a
lazy-cons. The special feature is that the
cdr is again a call to
range with an incremented
from parameter. In effect, calling
force on the
lazy-cons will construct the next
lazy-cons and so on.
If we mentally go through a call chain to construct the values 0, 1, 2, 3 we'd have to:
call (range :from 0)
=> (cons 0 <delayed range call>)
=> lazy-car = 0
force lazy-cdr which calls range :from 1
=> (cons 1 <delayed range call>)
=> lazy-car = 1
force lazy-cdr which calls range :from 2
=> (cons 2 <delayed range call>)
=> lazy-car = 2
force lazy-cdr which calls range :from 3
=> (cons 3 <delayed range call>)
=> lazy-car = 3
And so on. So a consumer, like
take would have to iteratively or recursively go through this call chain to construct lazily computed values.
take generates a list, so it must collect all lazily computed values. How does it do that? By recursively creating conses.
(defun take (n lazy-seq)
(if (= n 0)
(cons (lazy-car lazy-seq)
(take (1- n) (lazy-cdr lazy-seq)))))
take creates conses from
lazy-car (the head) and a recursive call to
take with the next delayed
cdr (the tail) which then constructs the result list we're after.
(take 5 (range))
(0 1 2 3 4)
That was pretty simple so far. A library (or language) that supports lazy sequences usually provides more functionality, like filtering or mapping.
Filtering is a pretty nice and important part in this. It allows to create specialized lazy sequences. For example we could create a lazy sequence where
take collects just even numbers.
(defun even-numbers ()
(lazy-filter #'evenp (range)))
(take 5 (even-numbers))
(0 2 4 6 8)
lazy-filter function is very flexible by allowing arbitrary filter functions (just like a filter function on normal lists). The implementation of
lazy-filter must again create
lazy-cons to be completely transparent to the consumer functions. This also allows the composition of filter functions.
(defun lazy-filter (pred lazy-seq)
((funcall pred (lazy-car lazy-seq))
(lazy-cons (lazy-car lazy-seq)
(lazy-filter pred (lazy-cdr lazy-seq))))
(lazy-filter pred (lazy-cdr lazy-seq)))))
When the passed in
lazy-seq parameter (which is a
lazy-cons) is empty, just return nil (the empty list). When applying the predicate to
lazy-car is true (
t) then return a new
lazy-car as head and delayed call to
lazy-filter with the 'forced' tail. When none of the above is true. Which means that this result has to be filtered out. Then call again
lazy-filter with the next 'forced' tail.
A similar thing can be done for mapping. But I'll leave that for you to read up on in SICP.