generators.tex

%%%Chapter of Common Lisp Manual.  Copyright 1989 Guy L. Steele Jr.

%  +++  Final version of chapter  +++

\clearpage\def\pagestatus{FINAL PROOF}

\chapter{Generators and Gatherers}
\label{GENERATORS}

Authors: Crispin Perdue and Richard C. Waters

\begin{new}
\prefaceword  Generators and gatherers are yet another
approach, closely related to series,
to providing iteration in a functional style.

The remainder of this chapter consists of a description by Crispin Perdue
and Richard C.~Waters of their work on an existing implementation of
generators and gatherers.  I have edited the chapter only very lightly to
conform to the overall style of this book.  Please see the Preface to this
book for more information about the genesis of the generators/gatherers
approach and its relationship to the work of X3J13. Guy L. Steele Jr.

\section{Introduction}

Generators are generalized input streams in the sense of
Smalltalk~\cite{SMALLTALK-80-BOOK}.  A generator can produce a potentially
unbounded number of elements of any type.  Individual elements are not
computed until requested by \cdf{next-in}.  When an element is taken from
a generator, it is removed by side effect.  Subsequent uses of 
\cdf{next-in} obtain later elements.

There is a close relationship between a generator and a series of the
elements it produces.  In particular, any series can be converted into
a generator.  As a result, all the scanner functions used for
creating series (see appendix~\ref{SERIES}) can be used to create
generators as well.  There is no need to have a separate
set of functions for creating generators.

Gatherers are generalized output streams.  Elements of any type can be
entered into a gatherer using \cdf{next-out}.  The gatherer combines the
elements together in time-sequence order into a net result.  This result can
be retrieved using \cdf{result-of}.

There is a close relationship between a gatherer and a collector function
that combines elements in the same way.  In particular, any one-input
one-output collector can be converted into a gatherer.  As a result, all
the collectors used for computing summary results from series can be used to
create gatherers.  There is no need to have a separate set of functions for
creating gatherers.


\section{Generators}

These functions create and process generators.

\begin{defun}[Function]
generator series

Given a series, \cdf{generator} returns a generator containing the same
elements.
\end{defun}


\begin{defmac}
next-in generator {action}*

\cdf{next-in} returns the next element in the generator {\it generator}.
The {\it actions} can be any Lisp expressions.  They are evaluated if and
only if no more elements can be retrieved from {\it generator}.  If there
are no more elements and no actions, it is an error.  It is also an error
to apply \cdf{next-in} to a generator a second time after the generator has
run out of elements.  As an example of generators, consider the following.
\begin{lisp}
(let ((x (generator (scan '(1 2 3 4))))) \\*
~~(with-output-to-string (s) \\*
~~~~(loop (prin1 (next-in x (return)) s) \\*
~~~~~~~~~~(prin1 (next-in x (return)) s) \\*
~~~~~~~~~~(princ "," s)))) \\*
~{\EV} "12,34,"
\end{lisp}
\end{defmac}

\section{Gatherers}

These functions create and process gatherers.

\begin{defun}[Function]
gatherer collector

The {\it collector} must be a function of type 
\cd{(function~((series~$t_1$))~$t_2$)}.  Given this function, \cdf{gatherer}
returns a gatherer that accepts elements of type $t_1$ and returns a final
result of type $t_2$.  The method for combining elements used by the
gatherer is the same as the one used by the {\it collector}.
\end{defun}


\begin{defun}[Function]
next-out gatherer item

Given a gatherer and a value, \cdf{next-out} enters the value into the
gatherer.
\end{defun}


\begin{defun}[Function]
result-of gatherer

\cdf{result-of} retrieves the net result from a gatherer.  \cdf{result-of}
can be applied at any time.  However, it is an error to apply 
\cdf{result-of} twice to the same gatherer or to apply \cdf{next-out} to a
gatherer once \cdf{result-of} has been applied.
\begin{lisp}
(let ((g (gatherer \#'collect-sum))) \\*
~~(dolist (i '(1 2 3 4)) \\*
~~~~(next-out g i) \\*
~~~~(if (evenp i) (next-out g (* 10 i)))) \\*
~~(result-of g)) \\*
~{\EV} 70
\end{lisp}
\end{defun}

\begin{defmac}
gathering ({(var fn)}*) {form}*

The first subform must be a list of pairs.  The first
element of each pair, {\it var}, must be a variable name.
The second element of each pair, {\it fn},
must be a form that when wrapped in \cd{(function~...)} is
acceptable as an argument to \cdf{gatherer}.  Each symbol is bound to a
gatherer constructed from the corresponding collector.  The body
(consisting of the {\it forms}) is evaluated in the scope of these bindings. 
When this evaluation is complete, \cdf{gathering} returns the \cdf{result-of} each
gatherer.  If there are $n$ pairs in the binding list,
\cdf{gathering} returns $n$ values.  For example:
\begin{lisp}
(defun examp (data) \\*
~~(gathering ((x collect) (y collect-sum)) \\*
~~~~(iterate ((i (scan data))) \\*
~~~~~~(case (first i) \\*
~~~~~~~~(:slot (next-out x (second i))) \\*
~~~~~~~~(:part (dolist (j (second i)) (next-out x j)))) \\*
~~~~~~(next-out y (third i))))) \\
\\
(examp '((:slot a 10) (:part (c d) 40))) {\EV} (a c d) {\rm and} 50
\end{lisp}

As a further illustration of gatherers, consider the following definition for a
simplified version of \cdf{gathering} that handles only one binding pair.
\begin{lisp}
(defmacro simple-gathering (((var collector)) \&body body) \\*
~~{\Xbq}(let ((,var (gatherer (function ,collector)))) \\*
~~~~~,{\Xatsign}body \\*
~~~~~(result-of ,var)))
\end{lisp}
The full capabilities of 
\cdf{gathering} can be supported in much the same way.
\end{defmac}

\section{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
``\cdf{let} eversion'' in addition to the optimization methods presented
in~\cite{RABBIT}.  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 \cdf{next-in}, 
\cdf{next-out}, and \cdf{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 \cdf{gathering} and \cdf{iterate} have been
optimized, the body of \cdf{examp} is as efficient as any loop
performing the same computation.

The implementation discussed in~\cite{WATERS-SERIES-DESIGN} includes a
portable Common Lisp implementation of generators and gatherers.  Although
the implementation does not support optimizations of the kind discussed
in~\cite{RABBIT}, it fully optimizes uses of \cdf{gathering}.
\end{new}