Common Lisp the Language, 2nd Edition

Next: Backquote Up: Generators and Gatherers Previous: Gatherers

B.4. Discussion

The idea of generators and gatherers was first proposed by Pavel Curtis. A key aspect of his proposal was the realization that generators and gatherers can be implemented simply and elegantly as closures and that these closures can be compiled very efficiently if certain conditions are met.

First, the compiler must support an optimization Curtis calls ``let eversion’’ in addition to the optimization methods presented in [45]. If a closure is created and used entirely within a limited lexical scope, the scopes of any bound variables nested in the closure can be enlarged (everted) to enclose all the uses of the closure. This allows the variables to be allocated on the stack rather than the heap.

Second, for a generator/gatherer closure to be compiled efficiently, it must be possible to determine at compile time exactly what closure is involved and exactly what the scope of use of the closure is. There are several aspects to this. The expression creating the generator/gatherer cannot refer to a free series variable. The generator/gatherer must be stored in a local variable. This variable must be used only in calls of next-in, next-out, and result-of, and not inside a closure. In particular the generator/gatherer cannot be stored in a data structure, stored in a special variable, or returned as a result value.

All of the examples above satisfy these restrictions. For instance, once the uses of gathering and iterate have been optimized, the body of examp is as efficient as any loop performing the same computation.

The implementation discussed in [52] includes a portable Common Lisp implementation of generators and gatherers. Although the implementation does not support optimizations of the kind discussed in [45], it fully optimizes uses of gathering.

Next: Backquote Up: Generators and Gatherers Previous: Gatherers

AI.Repository@cs.cmu.edu