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

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.

To see and run some examples of list generators, load glist-tests.lisp. This defines and tests several simple examples, using the lisp-unit package. The examples are described below.

List Generators

A list generator is a data structure representing a "promise" of a list. A generator is created with the macro delay.

(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!

To get the actual elements in a generated list, use the following, all of which behave, on the surface, like their Lisp counterparts. All of them handle generators, normal lists, and lists containing generators.

Note that gappend returns a list generator. Internally, it uses delay to postpone appending until elements are accessed.

Examples

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 gcar, gcdr, gnull and 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 flatten:

(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 gappend and delay. We need the delay because, unlike gcons, 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 gpop 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

Notice that 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 gflatten recursion 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 delay, gcons, and/or gappend to create lists that promise values, without actually creating them until they're asked for.

Comments? Send mail to Chris Riesbeck.