Common Lisp the Language, 2nd Edition
Series
expressions are transformed into loops by pipelining them-the
computation is converted from a form where entire series are computed one
after the other to a form where the series are incrementally computed in
parallel. In the resulting loop, each individual element is computed just
once, used, and then discarded before the next element is computed. For
this pipelining to be possible, a number of restrictions have to be
satisfied. Before these restrictions are explained, it will be useful to consider
a related issue.
The composition of two series functions cannot be pipelined unless the destination function consumes series elements in the same order that the source function produces them. Taken together, the series functions guarantee that this will always be true, because they all follow the same fixed processing order. In particular, they are all preorder functions-they process the elements of their series inputs and outputs in ascending order starting with the first element. Further, while it is easy for users to define new series functions, it is impossible to define one that is not a preorder function.
It turns out that most series operations can easily be implemented in a
preorder fashion, the most notable exceptions being reversal and sorting. As
a result, little is lost by outlawing non-preorder series functions. If some
non-preorder operation has to be applied to a series, the series can be
collected into a list or vector and the operation applied to this new data
structure. (This is inefficient, but no less efficient than what would be
required if non-preorder series functions were supported.)
