glist is a tiny Common Lisp library that supports list generators, also known as "lazy lists." This particular implementation is derived from that in Charniak, Riesbeck, McDermott and Meehan's Artificial Intelligence Programming, 2nd ed. Similar libraries can be found by searching the web for "Lisp lazy lists." A good discussion with advanced examples, using Scheme, can be found in Section 3.5 of Abelson and Sussman's The Structure and Interpretation of Computer Programs. They're called "streams" there. The original idea for lazy lists appeared in Friedman and Wise's "CONS should not Evaluate its Arguments."
Generated lists are useful for
- working with infinite lists -- see the gintegers example
- converting code that generates a list of answers into code that generates answers one at a time -- see the gflatten example
How to use glist
To get the glist functions, load
glist.lisp. The functions are in the package
glist. Therefore you either need to put
glist: before any glist
function name, or evaluate
(use-package :glist) first.
A list generator is a data structure representing a "promise" of
a list. A generator is created with the macro
(delay exp1 exp2 ...)
returns a generator that, when accessed by the glist functions described below, will return a list. The first time the generator is accessed, the expressions are evaluated, left to right, and the value of the last is stored as the generated list. Subsequent accesses retrieved that list.
Errors will occur if a delay doesn't return either a list or another generator!
Most often you will not use gcons or one of the functions below to create list generators, rather than delay.
(gcons x y)
is a macro that expands into
(cons x (delay y)).
Hence it creates a list generator with x as the first element,
and a form that will create the next part of the list when required.
To get the actual elements in a generated list, use the following functions. All behave on the surface like their normal Lisp counterparts. All of them accept normal lists, generators, and lists containing generators.
(gcar glist)-- returns the first real element, if any, of glist
(gcdr glist)-- returns the tail, if any, of glist; this might be a list or a list generator
(gnull glist)-- return true if glist is empty
(gpop glist)-- return the first real element of glist and set glist to it's gcdr
(gextract glist [n])-- return a list of the first n elements of glist. If n is not given, returns all the elements, so don't call this on an infinite list!
(gappend glist1 glist2)-- return a list generator that is the concatenation of the two glists.
gappend returns a list generator. Internally, it uses
delay to postpone appending until elements are accessed.
Using generated lists is easy, but it can take a while to get used to creating them. A trivial but not very useful example is
(defun silly-example () (let ((gl (delay '(a b)))) (format t "~%GCAR = ~S GCDR = ~S" (gcar gl) (gcdr gl)) (do () ((gnull gl)) (format t "~%GPOP = ~S" (gpop gl))))) > (silly-example) GCAR = A GCDR = (B) GPOP = A GPOP = B NIL
The call to
delay in this code creates a list generator that,
when accessed, will return the list
(a b). The code then shows
what happens when using
gpop on the generator. This is just to demonstrate these functions.
There's no real reason for this kind of code.
More useful is creating infinite lists. For example, suppose we wanted to have a source of all the integers from N on. The key is to define a recursive function that return a list with one number plus a promise for more.
(defun gintegers (&optional (n 0)) (cons n (delay (gintegers (1+ n)))))
To see how to use this list, here's a function that prints the first 5 elements in the generated list. It returns the list so that you can see that it's ready to generate more values.
(defun show-gintegers () (let ((gl (gintegers 3))) (dotimes (n 5 gl) (format t "~S " (gpop gl))))) > (show-gintegers) 3 4 5 6 7 (8 . #<gen #<closure (LAMBDA NIL (GINTEGERS (1+ N)))>>)
Now let's consider converting some code that returns
a list of answers to code that returns answers one at a time. A classic simple
Lisp function is
flatten which returns a "flattened"
list, or, seen another way, a list of all the atoms nested anywhere in a list.
First, here's the normal
(defun flatten (x) (cond ((null x) nil) ((atom x) (list x)) (t (append (flatten (car x)) (flatten (cdr x)))))) > (flatten '(((a b) c d) e f)) (A B C D E F)
Now, here's the one-at-a-time version. It's identical except for the use of
delay. We need
delay because, unlike
gappend is a function, so both of its arguments are evaluated.
(defun gflatten (x) (cond ((null x) nil) ((atom x) (list x)) (t (gappend (gflatten (car x)) (delay (gflatten (cdr x)))))))
Here's an example call to
gflatten. We use
to get the elements one at a time. We trace
gflatten so that you
can see that exploration of the later parts of the list occur incrementally.
> (setq l (gflatten '(((a) b) ((c) (d) e)))) (GFLATTEN (((A) B) ((C) (D) E))) (GFLATTEN ((A) B)) (GFLATTEN (A)) (GFLATTEN A) returned (A) returned (A . #<gen #<Interpreted Closure (:INTERNAL GAPPEND) @ #x20f79dea>>) returned (A . #<gen #<Interpreted Closure (:INTERNAL GAPPEND) @ #x20f7dcc2>>) returned (A . #<gen #<Interpreted Closure (:INTERNAL GAPPEND) @ #x20f81b6a>>) (A . #<gen #<Interpreted Closure (:INTERNAL GAPPEND) @ #x20f81b6a>>) < (gpop l) A
gflatten recursively descended to the
first atom, then stopped.
> (gpop l) (GFLATTEN NIL) returned NIL (GFLATTEN (B)) (GFLATTEN B) returned (B) returned (B . #<gen #<Interpreted Closure (:INTERNAL GAPPEND) @ #x20fad50a>>) B
Asking for the second element picked up the
from where it left off. Notice that this means the recursive search went into
the CDR of
(A), found nothing, backed up, and when down to find
the B. All of this just worked, thanks to the magic of closures.
> (gpop l) (GFLATTEN NIL) returned NIL (GFLATTEN (((C) (D) E))) (GFLATTEN ((C) (D) E)) (GFLATTEN (C)) (GFLATTEN C) returned (C) returned (C . #<gen #<Interpreted Closure (:INTERNAL GAPPEND) @ #x20fc5562>>) returned (C . #<gen #<Interpreted Closure (:INTERNAL GAPPEND) @ #x20fc940a>>) returned (C . #<gen #<Interpreted Closure (:INTERNAL GAPPEND) @ #x20fcd2b2>>) C
In general, any generator you design will use either
gappend to create lists that promise values, without
actually creating them until they're asked for.