List Generators

Overview

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,

(ql:quickload "glist")

To run the tests or play with them,

(in-package :glist-tests)

The source and test code is here.

The examples are described below.

List Generators

A list generator is a data structure that returns elements on demand. Those elements may not exist until asked for. The core function for creating generators is 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!

Although delay is the underlying mechanism, you normally do not need to use it. You use gcons instead.

(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) -- returns true if glist is empty
• (gpop glist) -- returns the first real element of glist and set glist to it's gcdr
• (gextract glist [n]) -- returns 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) -- returns a list generator that is the concatenation of the two glists.

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 way to calculate more.

(defun gintegers (&optional (n 0))
    (gcons n (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))
                        (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 generate values, without actually creating them until they're asked for.

Generated lists in Python

Python has had a generated list facility since version 2.4. Python has arrays rather than lists. You don't build arrays with an equivalent of cons or access with an equivalent of car and cdr. To make Python generators usable as arrays, generators are iterators. That means they support the next() method for getting the next value. That means that generated lists can be accessed with a for loop.

There are several ways to create generators. The approach similar to the Lisp code above uses functions that call yield like this:

def numberGen():
      n = 0
      while True:
        yield n
        n += 1

You can create a generator and get values with next() .

>>> x = numberGen()
    >>> x
    
    >>> next(x)
    0
    >>> next(x)
    1

Normally though you would get these values using a for...in loop. With an endless generator, you need to put in some stopping condition:

>>> for i in numberGen():
      if i > 5:
        break
      print(i)

    0
    1
    2
    3
    4
    5

Generators can be finite. The following generator returns the words in a string. A StopIteration error occurs if next() is called and there are no more values. There is no standard way to test if a generator is done. There is no error when a finite generator is run in a for...in loop.

>>> def wordGen(text):
      for word in text.split():
        yield word

    >>> x = wordGen("a simple test")
    >>> next(x)
    'a'
    >>> next(x)
    'simple'
    >>> next(x)
    'test'
    >>> next(x)
    Traceback (most recent call last):
      File "", line 1, in 
        next(x)
    StopIteration
    >>> for i in wordGen("a simple test"):
      print(i)

    a
    simple
    test
    >>>

Generated lists in JavaScript

Generators were added to JavaScript in EcmaScript 2015. JavaScript uses yield as in Python. yield can only be used in function* definitions. (There is no arrow function equivalent.)

function* numberGen () {
      let n = 0;
      while (true) {
        yield n;
        n++;
      }
    }

You bump the generator using the generator method next(). It returns an object whose value property contains the next value.

> x = numberGen()
    numberGen {}
    > x.next().value
    0
    > x.next().value
    1
    > x.next().value
    2

A generator is an iterator that can be accessed with a for...of loop.

for (let i of numberGen()) {
      if (i > 5) break;
      console.log(i);
    }

Generators can be finite. The following returns a generator for the words in a string.

function* wordGen (text) {
      for (let word of text.split(' ')) {
        yield word
      }
    }

The object returned by next() includes a done property. If next() is called when there are no more values, done will be true and value will be undefined.

x = wordGen('a simple test')
    wordGen {}
    > x.next()
    {value: 'a', done: false}
    > x.next()
    {value: 'simple', done: false}
    > x.next()
    {value: 'test', done: false}
    > x.next()
    {value: undefined, done: true}
    > for (let w of wordGen('a simple test')) console.log(w)
    a
    simple
    test