series.tex

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

%  +++  Final version of chapter  +++

\clearpage\def\pagestatus{FINAL PROOF}

\chapter{Series}
\label{SERIES}

\def\SU#1{${}_{#1}$}

\def\fooprime#1{#1'}

Author: Richard C. Waters

\begin{new}
\prefaceword A series is a data structure much like a sequence, with similar
kinds of operations.  The difference is that in many situations, operations
on series may be composed functionally and yet execute iteratively, without
the need to construct intermediate series values explicitly.  In this
manner, series provide both the clarity of a functional programming style
and the efficiency of an iterative programming style.

The remainder of this chapter consists of a description by Richard
C.~Waters of his work on an existing implementation of series.
This is the culmination of many years of design and use of this approach,
during which some 100,000 lines of application code have been written (by
about half a dozen people over the course of seven years) using the series
facility in nearly all iteration situations.  This includes one large
system (\cdf{KBEmacs}) of over 40,000 lines of code.

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 series approach and its relationship to the work
of X3J13.
\end{new}


\noindent\hbox to \textwidth{\hss---Guy L. Steele Jr.}
\vskip 8pt plus 3pt minus 2pt

\section{Introduction}

Series combine aspects of sequences, streams, and loops.  Like sequences,
series represent totally ordered multi-sets.  In addition, the series
functions have the same flavor as the sequence functions---namely, they
operate on whole series, rather than extracting elements to be
processed by other functions.  For instance, the series expression below
computes the sum of the positive elements in a list.
\begin{lisp}
(collect-sum (choose-if \#'plusp (scan '(1 -2 3 -4)))) {\EV} 4
\end{lisp}

Like streams, series can represent unbounded sets of elements and are
supported by lazy evaluation: each element of a series is not
computed until it is needed.  For instance, the series expression below
returns a list of the first five even natural numbers and their sum.  The
call on \cdf{scan-range} returns a series of all the even natural numbers.
However, since no elements beyond the first five are ever used, no elements
beyond the first five are ever computed.
\begin{lisp}
(let ((x (subseries (scan-range :from 0 :by 2) 0 5))) \\*
~~(values (collect x) (collect-sum x))) \\*
~~{\EV} (0 2 4 6 8) {\rm and} 20
\end{lisp}

Like sequences and unlike streams, a series is not altered
when its elements are accessed.  For instance, both users of \cdf{x}
above receive the same elements.

A totally ordered multi-set of elements can be represented in a loop by the
successive values of a variable.  This is extremely efficient, because it
avoids the need to store the elements as a group in any kind of data
structure.  In most situations, series expressions achieve this same high
level of efficiency, because they are automatically transformed into loops
before being evaluated or compiled.  For instance, the first expression
above is transformed into a loop like the following.
\begin{lisp}
(let ((sum 0)) \\*
~~(dolist (i '(1 -2  3 -4) sum) \\*
~~~~(when (plusp i) (setq sum (+ sum i))))) {\EV} 4
\end{lisp}

A wide variety of algorithms can be expressed clearly and succinctly with
series expressions.  In particular, at least 90 percent of the loops
programmers typically write can be replaced by series expressions that are
much easier to understand and modify, and just as efficient.   From this
perspective, the key feature of series is that they are supported by a rich
set of functions.  These functions more or less correspond to the union of
the operations provided by the sequence functions, the \cdf{loop} clauses,
and the vector operations of APL.

Some series expressions cannot be transformed into loops.
This is unfortunate, because while transformable series expressions are much more
efficient than equivalent expressions involving sequences or streams,
non-transformable series expressions are much less efficient.  Whenever a
problem comes up that blocks the transformation of a series expression, a
warning message is issued.  On the basis of information in the message, it is
usually easy to provide an efficient fix for the problem (see
section~\ref{SERIES-E-SECTION}).

Fortunately, most series expressions can be transformed into loops.  In
particular, pure expressions (ones that do not store series in variables)
can always be transformed.  As a result, the best approach for programmers
to take is simply to write series expressions without worrying about
transformability.  When problems come up, they can be ignored (since they
cannot lead to the computation of incorrect results) or dealt with on an
individual basis.

\beforenoterule
\begin{implementation}
The series functions and the theory
underlying them are described in greater detail
in~\cite{WATERS-SERIES-DESIGN,WATERS-SERIES-IMPLEMENTATION}.
These reports also discuss the algorithms required to transform series
expressions into loops and explain how to obtain a portable implementation.
\end{implementation}
\afternoterule

\section{Series Functions}
\label{SERIES-F-SECTION}

Throughout this chapter the notation \cd{S\SU{j}} is used to
denote the \emph{j\/}th element of the series \cdf{S}.  As in a list or
vector, the first element of a series has the subscript zero.

The \cd{\#} macro character syntax \cd{\#Z\emph{list}} denotes a series that contains
the elements of \emph{list}.  This syntax is also used when series are printed.
\begin{lisp}
(choose-if \#'symbolp \#Z(a 2 b)) {\EV} \#Z(a b)
\end{lisp}
Series are self-evaluating objects and the series data type is disjoint
from all other types.


\begin{defun}[Type specifier]
series element-type

The type specifier \cd{(series \emph{element-type})}
denotes the set of series whose elements are all
members of the type \emph{element-type}.
\end{defun}


\begin{defun}[Function]
series arg &rest args

The function \cdf{series} returns an unbounded series that endlessly repeats the
values of the arguments.  The second example below shows the preferred
method for constructing a bounded series.
\begin{lisp}
(series 'b 'c) {\EV} \#Z(b c b c b c ...) \\
(scan (list 'a 'b 'c)) {\EV} \#Z(a b c)
\end{lisp}
\end{defun}

\subsection{Scanners}

Scanners create series outputs based on non-series inputs.  Either they
operate based on some formula (for example, scanning a range of integers) or they
enumerate the elements in an aggregate data structure (for example, scanning the
elements in a list or array).


\begin{defun}[Function]
scan-range &key (:start 0) (:by 1) (:type 'number)
    :upto :below :downto :above :length

The function \cdf{scan-range} returns a series of numbers starting with the
\cd{:start} argument
(default integer \cd{0}) and counting up by the \cd{:by} argument (default
integer \cd{1}).  The \cd{:type} argument (default \cdf{number}) is
a type specifier indicating the type of numbers in the series
produced.  The \cd{:type} argument must be a (not necessarily proper) subtype of
\cdf{number}.  The \cd{:start} and \cd{:by} arguments must be of that type.

One of the last five arguments may be used
to specify the kind of end test to be used;
these are called \emph{termination arguments}.
If \cd{:upto} is specified, counting continues only so long as the
numbers generated are less than or equal to \cd{:upto}.  If 
\cd{:below} is specified, counting continues only so long as the numbers
generated are less than \cd{:below}.  If \cd{:downto} is specified,
counting continues only so long as the numbers generated are greater
than or equal to \cd{:downto}.  If \cd{:above} is specified,
counting continues only so long as the numbers generated are greater
than \cd{:above}.  If \cd{:length} is specified, it must be a
non-negative integer and the output series has this length.

If none
of the termination arguments are specified, the output has unbounded
length.  If more than one termination argument is specified, it is an error.

\begin{lisp}
(scan-range :upto 4) {\EV} \#Z(0 1 2 3 4) \\*
(scan-range :from 1 :by -1 :above -4) {\EV} \#Z(1 0 -1 -2 -3) \\
(scan-range :from .5 :by .1 :type 'float) {\EV} \#Z(.5 .6 .7 ...) \\*
(scan-range) {\EV} \#Z(0 1 2 3 4 5 6 ...)
\end{lisp}
\end{defun}

\begin{defun}[Function]
scan sequence \\
scan type sequence

\cdf{scan} returns a series containing the elements of \emph{sequence} in
order.  The \emph{type} argument is a type specifier indicating the type of
sequence to be scanned; it must be a (not necessarily proper) subtype of
\cdf{sequence}.  If \emph{type} is omitted, it defaults to \cdf{list}.
(This function exhibits an argument pattern that is unusual for Common
Lisp:  an ``optional'' argument preceding a required argument.  This
pattern cannot be expressed in the usual manner with \cd{\&optional}.  It
is indicated above by two definition lines, showing the two possible
argument patterns.)

If the \emph{sequence} is a list, it must be a proper list ending in \cdf{nil}.
Scanning is significantly more efficient if it can be determined at compile
time whether \emph{type} is a subtype of \cdf{list} or \cdf{vector} and for
vectors what the length of the vector is.
\begin{lisp}
(scan '(a b c)) {\EV} \#Z(a b c) \\*
(scan 'string "BAR") {\EV} \#Z(\#{\Xbackslash}B \#{\Xbackslash}A \#{\Xbackslash}R)
\end{lisp}
\end{defun}

\begin{defun}[Function]
scan-sublists list

\cdf{scan-sublists} returns a series containing the successive sublists of
\emph{list}.  The \emph{list} must be a proper list ending in \cdf{nil}.
\begin{lisp}
(scan-sublists '(a b c)) {\EV} \#Z((a b c) (b c) (c))
\end{lisp}
\end{defun}

\begin{defun}[Function]
scan-multiple type first-sequence &rest more-sequences

Several sequences can be scanned at once by using several calls on
\cdf{scan}.  Each call on \cdf{scan} will test to see when its sequence runs
out of elements and execution will stop as soon as any of the sequences are
exhausted.  Although very robust, this approach to scanning can be
inefficient.  In situations where it is known in
advance which sequence is the shortest, \cdf{scan-multiple} can be used to
obtain the same results more rapidly.
  
\cdf{scan-multiple} is similar to \cdf{scan} except that several sequences
can be scanned at once.  If there are \emph{n} sequence inputs,
\cdf{scan-multiple} returns \emph{n} series containing the elements of these
sequences.  It must be the case that none of the sequence inputs is shorter
than the first sequence.  All of the output series are the same length as
the first input sequence.  Extra elements in the other input sequences are
ignored.  Using \cdf{scan-multiple} is more efficient than using multiple
instances of \cdf{scan}, because \cdf{scan-multiple} only has to check for
the first input running out of elements.

If \emph{type} is of the form \cd{(values~$\emph{t}_1$~$\ldots$~$\emph{t}x_m$)}, then
there must be $\emph{m}$ sequence inputs and the \emph{i\/}th sequence must have type
$\emph{t}_{i}$.  Otherwise there can be any number of sequence inputs, each of which
must have type \emph{type}.
\begin{lisp}
(multiple-value-bind (data weights) \\*
~~~~(scan-multiple 'list '(1 6 3 2 8) '(2 3 3 3 2)) \\*
~~(collect (map-fn t \#'* data weights))) \\*
~~{\EV} (2 18 9 6 16)
\end{lisp}
\end{defun}

\begin{defun}[Function]
scan-lists-of-lists lists-of-lists &optional leaf-test \\
scan-lists-of-lists-fringe lists-of-lists &optional leaf-test

The argument \emph{lists-of-lists} is viewed as a tree where each
internal node is a non-empty list and the elements of the list are the
children of the node.  \cdf{scan-lists-of-lists} and
\cdf{scan-lists-of-lists-fringe} each scan \emph{lists-of-lists} in preorder
and return a series of its nodes.  \cdf{scan-lists-of-lists} returns every
node in the tree.  \cdf{scan-lists-of-lists-fringe} returns only the leaf
nodes.  

The scan proceeds as follows.  The argument \emph{lists-of-lists} can be any
Lisp object.  If \emph{lists-of-lists} is an atom or satisfies the predicate
\emph{leaf-test} (if present), it is a leaf node.  (The predicate can count
on being applied only to conses.) Otherwise, \emph{lists-of-lists} is a (not
necessarily proper) list.  The first element of \emph{lists-of-lists} is
recursively scanned in full, followed by the second and so on until a
non-cons \emph{cdr} is encountered.  Whether or not this final \emph{cdr} is
\cdf{nil}, it is ignored.
\begin{lisp}
(scan-lists-of-lists '((2) (nil))) \\*
~~{\EV} \#Z(((2) (nil)) (2) 2 (nil) nil) \\*
(scan-lists-of-lists-fringe '((2) (nil))) {\EV} \#Z(2 nil) \\*
(scan-lists-of-lists-fringe '((2) (nil)) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~\#'(lambda (e) (numberp (car e)))) \\*
~~{\EV} \#Z((2) nil)
\end{lisp}
\end{defun}

\begin{defun}[Function]
scan-alist a-list &optional (test \#'eql) \\
scan-plist plist \\
scan-hash table

When given an association list, a property list, or a hash table
(respectively), each of these functions produces two outputs:  a series of keys
\emph{K} and a series of the corresponding values \emph{V}.  Each key in the
input appears exactly once in the output, even if it appears more than once
in the input.  (The \emph{test} argument of \cdf{scan-alist} specifies the
equality test between keys; it defaults to \cdf{eql}.)
The two outputs have the same length.  Each
\emph{V}\SU{j} is the value returned by the appropriate accessing function
(\cdf{cdr} of \cdf{assoc}, \cdf{getf}, or \cdf{gethash}, respectively)
when given \emph{K}\SU{j}.  \cdf{scan-alist} and \cdf{scan-plist} scan keys
in the order
they appear in the underlying structure.  \cdf{scan-hash} scans keys in no
particular order.
\begin{lisp}
(scan-plist '(a 1 b 3)) {\EV} \#Z(a b) {\rm and} \#Z(1 3) \\*
(scan-alist '((a . 1) nil (a . 3) (b . 2))) \\*
~~{\EV} \#Z(a b) {\rm and} \#Z(1 2)
\end{lisp}
\end{defun}

\begin{defun}[Function]
scan-symbols &optional (package *package*)

\cdf{scan-symbols} returns a series, in no particular order, and possibly
containing duplicates, of the symbols accessible in \emph{package} (which
defaults to the current package).
\end{defun}

\begin{defun}[Function]
scan-file file-name &optional (reader \#'read)

\cdf{scan-file} opens the file named by the string \emph{file-name}
and applies the function \emph{reader} to it repeatedly until the end of the
file is reached.  \emph{Reader} must accept the standard input function
arguments \emph{input-stream}, \emph{eof-error-p}, and \emph{eof-value} as its
arguments.  (For instance, \emph{reader} can be \cdf{read},
\cdf{read-preserving-white-space}, \cdf{read-line}, or
\cdf{read-char}.) If omitted, \emph{reader} defaults to \cdf{read}.
\cdf{scan-file} returns a series of the values returned
by \emph{reader}, up to but not including the value returned
when the end of the file is reached.  The
file is correctly closed, even if an abort occurs. \end{defun}

\begin{defun}[Function]
scan-fn type init step &optional test

The higher-order function \cdf{scan-fn} supports the general concept of
scanning.  The \emph{type} argument is a type specifier indicating
the type of values returned by \emph{init} and \emph{step}.  The \cdf{values}
type specifier can be used for this argument
to indicate multiple types; however, \emph{type} cannot
indicate zero values.  If \emph{type} indicates $\emph{m}$ types
$\emph{t}_1, \ldots\,, \emph{t}_{m}$,
then \cdf{scan-fn} returns $\emph{m}$ series
\emph{T1}, $\ldots\,$, \emph{Tm}, where \emph{Ti} has
the type \cd{(series $\emph{t}_{i}$)}.
The arguments \emph{init}, \emph{step}, and \emph{test} are functions.

The \emph{init} must be of type 
\cd{(function () (values $\emph{t}_1$ ... $\emph{t}_{m}$))}.

The \emph{step} must be of type 
\cd{(function ($\emph{t}_1$ ... $\emph{t}_{m}$) (values $\emph{t}_1$ ... $\emph{t}_{m}$))}.

The \emph{test} (if present) must be of type 
\cd{(function ($\emph{t}_1$ ... $\emph{t}_{m}$) t)}.

The elements of the \emph{Ti} are computed as follows:
\begin{lisp}
(values \emph{T1}\SU{0} ... \emph{Tm}\SU{0}) = (funcall \emph{init}) \\*
(values \emph{T1}\SU{j} ... \emph{Tm}\SU{j}) = (funcall \emph{step} \emph{T1}\SU{(j-1)} ... \emph{Tm}\SU{(j-1)})
\end{lisp}

The outputs all have the same length.  If there is no \emph{test}, the
outputs have unbounded length.  If there is a \emph{test}, the outputs
consist of the elements up to, but not including, the first elements (with
index \emph{j}, say) for which the following termination test is not \cdf{nil}.
\begin{lisp}
(funcall \emph{test} \emph{T1}\SU{j} ... \emph{Tm}\SU{j})
\end{lisp}
It is guaranteed that \emph{step} will
not be applied to the elements that pass this termination test.

If \emph{init}, \emph{step}, or \emph{test} has side effects when
invoked, it can count on being called in the order indicated by the
equations above, with \emph{test} called just before \emph{step} on each
cycle.  However, given the lazy evaluation nature of series, these
functions will not be called until their outputs are actually used (if
ever).  In addition, no assumptions can be made about the relative order of
evaluation of these calls with regard to execution in other parts of a
given series expression.  The first example below scans down a list
stepping two elements at a time.  The second example generates two unbounded
series: the integers counting up from 1 and the sequence of partial
sums of the first \emph{i} integers.
\begin{lisp}
(scan-fn t \#'(lambda () '(a b c d)) \#'cddr \#'null) \\*
~~{\EV} \#Z((a b c d) (c d)) \\
\\
(scan-fn '(values integer integer) \\*
~~~~~~~~~\#'(lambda () (values 1 0)) \\*
~~~~~~~~~\#'(lambda (i sum) (values (+ i 1) (+ sum i)))) \\*
~~{\EV} \#Z(1 2 3 4 ...) {\rm and} \#Z(0 1 3 6 ...)
\end{lisp}
\end{defun}

\begin{defun}[Function]
scan-fn-inclusive type init step test

The higher-order function \cdf{scan-fn-inclusive} is the same as 
\cdf{scan-fn} except that the first set of elements for which \emph{test}
returns a non-null value is included in the output.  As with
\cdf{scan-fn}, it is guaranteed that \emph{step} will not be applied to the
elements for which \emph{test} is non-null.
\end{defun}

\subsection{Mapping}

By far the most common kind of series operation is mapping.  In cognizance
of this fact, four different ways are provided for specifying mapping:  one
fundamental form (\cdf{map-fn}) and three shorthand forms that are more
convenient in particular common situations.

\begin{defun}[Function]
map-fn type function &rest series-inputs

The higher-order function \cdf{map-fn} supports the general concept of
mapping.   The \emph{type} argument is a type specifier indicating
the type of values returned by \emph{function}.  The \cdf{values}
construct can be used to indicate multiple types; however, \emph{type}
cannot indicate zero values.  If \emph{type} indicates $m$ types
$t_1, \ldots\,, t_m$,
then \cdf{map-fn} returns $m$ series
\emph{T1},~$\ldots\,$,~\emph{Tm}, where \emph{Ti} has the
type \cd{(series~$t_i$)}.
The argument
\emph{function} is a function.   The remaining arguments (if any) are all
series.  Let these series be \emph{S1},~$\ldots\,$,~\emph{Sn} and suppose that
\emph{Si} has the type \cd{(series~$\emph{s}_{i}$)}.

The \emph{function} must be of type
\begin{lisp}
(function ($\emph{s}_1$ ... $\emph{s}_{n}$) (values $\emph{t}_1$ ... $\emph{t}_{m}$))
\end{lisp}

The length of each output is the same as the length of the shortest input.
If there are no bounded series inputs, the outputs are unbounded.
The elements of the \emph{Ti} are the results of applying \emph{function} to
the corresponding elements of the series inputs.
\begin{lisp}
(values \emph{T1}\SU{j} ... \emph{Tm}\SU{j}) {\EQ} (funcall \emph{function} \emph{S1}\SU{j} ... \emph{Sn}\SU{j})
\end{lisp}

If \emph{function} has side effects, it can count on being called first on
the \emph{Si}\SU{0}, then on the \emph{Si}\SU{1}, and so on.  However, given
the lazy evaluation nature of series, \emph{function} will not be called on
any group of input elements until the result is actually used (if ever).
In addition, no assumptions can be made about the relative order of
evaluation of the calls on \emph{function} with regard to execution in other parts of a
given series expression.
\begin{lisp}
(map-fn 'integer \#'+ \#Z(1 2 3) \#Z(4 5)) {\EV} \#Z(5 7) \\*
(map-fn t \#'gensym) {\EV} \#Z(\#:G3 \#:G4 \#:G5 ...) \\
(map-fn '(values integer rational) \#'floor \#Z(1/4 9/5 12/3)) \\*
~~{\EV} \#Z(0 1 4) {\rm and} \#Z(1/4 4/5 0)
\end{lisp}

The \cd{\#} macro character syntax \cd{\#M} makes it easy to specify uses of \cdf{map-fn}
where \emph{type} is \cdf{t} and the \emph{function} is a named
function.  The notation \cd{(\#M\emph{function}~...)} is an
abbreviation for \cd{(map-fn~t~\#'\emph{function}~...)}.  The form \emph{function} can
be the printed representation of any Lisp object.  The notation
\cd{\#M}\emph{function} can appear only in the
function position of a list.
\begin{lisp}
(collect (\#M1+ (scan '(1 2 3)))) {\EV} (2 3 4)
\end{lisp}
\end{defun}

\begin{defmac}
mapping ({({var | ({var}*)} value)}*) {declaration}* {form}*

The macro \cdf{mapping} makes it easy to specify uses of \cdf{map-fn}
where \emph{type} is \cdf{t} and the \emph{function} is a literal 
\cdf{lambda}.  The syntax of \cdf{mapping} is analogous to that of \cdf{let}.
The binding list specifies zero or more variables that are bound in parallel to
successive values of series.  The \emph{value} part of each pair is
an expression that must produce a
series.  The \emph{declarations} and \emph{forms} are
treated as the body of a \cdf{lambda} expression
that is mapped over the series values.  A series of the first values
returned by this \cdf{lambda} expression is returned as the result of 
\cdf{mapping}.
\begin{lisp}
(mapping ((x r) (y s)) ...) {\EQ} \\*
~~(map-fn t \#'(lambda (x y) ...) r s) \\
\\
(mapping ((x (scan '(2 -2 3)))) \\*
~~(expt (abs x) 3)) \\*
~~{\EV} \#Z(8 8 27)
\end{lisp}

The form \cdf{mapping} supports a special syntax that facilitates the
use of series functions returning multiple values.  Instead of being
a single variable, the variable part of a \emph{var-value} pair can be a list of
variables.  This list is treated the same way as the first argument to
\cdf{multiple-value-bind} and can be used to access the elements of
multiple series returned by a series function.
\begin{lisp}
(mapping (((i v) (scan-plist '(a 1 b 2)))) \\*
~~(list i v)) \\*
~~{\EV} \#Z((a 1) (b 2))
\end{lisp}
\end{defmac}

\begin{defmac}
iterate ({({var | ({var}*)} value)}*) {declaration}* {form}*

The form \cdf{iterate} is the same as \cdf{mapping}, except that after
mapping the \emph{forms} over the \emph{values}, the results are discarded and
\cdf{nil} is returned.
\begin{lisp}
(let ((item (scan '((1) (-2) (3))))) \\*
~~(iterate ((x (\#Mcar item))) \\*
~~~~(if (plusp x) (prin1 x)))) \\*
~~{\EV} nil {\rm (after printing ``\cd{13}'')}
\end{lisp}

To a first approximation, \cdf{iterate} and \cdf{mapping} differ in the same
way as \cdf{mapc} and \cdf{mapcar}.  In particular, like \cdf{mapc},
\cdf{iterate} is intended to be used in situations where the \emph{forms} are
being evaluated for side effects rather than for their results.  However, given
the lazy evaluation semantics of series, the difference between
\cdf{iterate} and \cdf{mapping} is more than just a question of efficiency.

If \cdf{mapcar} is used in a situation where the output is not used, time is
wasted unnecessarily creating the output list.  However, if \cdf{mapping} is
used in a situation where the output is not used, no computation is
performed, because series elements are not computed until they are used.
Thus \cdf{iterate} can be thought of as a declaration that the indicated
computation is to be performed even though the output is not used for
anything.
\end{defmac}

\subsection{Truncation and Other Simple Transducers}

Transducers compute series from series and form the heart of most series
expressions.  Mapping is by far the most common transducer.   This section
presents a number of additional simple transducers.


\begin{defun}[Function]
cotruncate &rest series-inputs \\
until bools &rest series-inputs \\
until-if pred &rest series-inputs

Each of these functions accepts one or more series inputs {\it
S1},~$\ldots\,$,~\emph{Sn} as its \cd{\&rest} argument and returns $\emph{n}$ series
outputs \emph{T1},~$\ldots\,$,~\emph{Tn} that contain the same elements in the same
order---that is, \emph{Ti\SU{j}=Si\SU{j}}.
Let $\emph{k}$ be the length of the
shortest input \emph{Si}.  \cdf{cotruncate} truncates the series so that
each output has length $\emph{k}$.  Let $\emph{k}'$ be the position of the first element
in the boolean series \emph{bools} that is not \cdf{nil} or, if every
element is \cdf{nil}, the length of \emph{bools}.  \cdf{until} truncates the
series so that each output has length \cd{(min~\emph{k}~$\fooprime{\emph{k}}$)}.
Let ${it k}''$ be the position of the first element in \emph{S1} such that 
\cd{(\emph{pred}~\emph{S1\SU{\fooprime{\fooprime{k}}}})}
is not \cdf{nil} or, if there is no such
element, the length of \emph{S1}.  \cdf{until-if} truncates the series so
that each output has length \cd{(min~\emph{k}~$\fooprime{\fooprime{\emph{k}}}$)}.
\begin{lisp}
(cotruncate \#Z(1 2 -3 4) \#Z(a b c)) \\*
~~{\EV} \#Z(1 2 -3) {\rm and} \#Z(a b c) \\
(until \#Z(nil nil t nil) \#Z(1 2 -3 4) \#Z(a b c)) \\*
~~{\EV} \#Z(1 2) {\rm and} \#Z(a b) \\
(until-if \#'minusp \#Z(1 2 -3 4) \#Z(a b c)) \\*
~~{\EV} \#Z(1 2) {\rm and} \#Z(a b)
\end{lisp}
\end{defun}

\begin{defun}[Function]
previous items &optional (default nil) (amount 1)

The series returned by \cdf{previous} is the same as the input series
\emph{items} except that it is shifted to the right by the positive
integer \emph{amount}.  The shifting is done by inserting \emph{amount}
copies of \emph{default} before \emph{items} and discarding \emph{amount}
elements from the end of \emph{items}.
\begin{lisp}
(previous \#Z(10 11 12) 0) {\EV} \#Z(0 10 11)
\end{lisp}
\end{defun}

\begin{defun}[Function]
latch items &key :after :before :pre :post

The series returned by \cdf{latch} is the same as the input series
\emph{items} except that some of the elements are replaced by other
values.  \cdf{latch} acts like a \emph{latch} electronic circuit
component.  Each input element causes the creation of a corresponding
output element.  After a specified number of non-null input elements
have been encountered, the latch is triggered and the output mode is
permanently changed.

The \cd{:after} and \cd{:before} arguments specify the latch point.
The latch point is just after the \cd{:after}-th non-null element in
\emph{items} or just before the \cd{:before}-th non-null element.  If
neither \cd{:after} nor \cd{:before} is specified, an \cd{:after}
of \cd{1} is assumed.  If both are specified, it is an error.

If a \cd{:pre} is specified, every element prior to the latch point
is replaced by this value.  If a \cd{:post} is specified, every element
after the latch point is replaced by this value.  If neither is
specified, a \cd{:post} of \cdf{nil} is assumed.
\begin{lisp}
(latch \#Z(nil c nil d e)) {\EV} \#Z(nil c nil nil nil) \\*
(latch \#Z(nil c nil d e) :before 2 :post t) {\EV} \#Z(nil c nil t t)
\end{lisp}
\end{defun}

\begin{defun}[Function]
collecting-fn type init function &rest series-inputs

The higher-order function \cdf{collecting-fn} supports the general concept of
a simple transducer with internal state.  The \emph{type} argument is a type
specifier indicating the type of values returned by \emph{function}.
The \cdf{values} construct can be used to indicate multiple types; however,
\emph{type} cannot indicate zero values.  If \emph{type} indicates $\emph{m}$ types
$\emph{t}_1, \ldots\,, \emph{t}_{m}$,
then \cdf{collecting-fn} returns $\emph{m}$ series {\it
T1},~$\ldots\,$,~\emph{Tm}, where \emph{Ti} has the
type \cd{(series~$\emph{t}_{i}$)}.  The
arguments \emph{init} and \emph{function} are functions.  The remaining
arguments (if any) are all series.  Let these series be {\it
S1},~$\ldots\,$,~\emph{Sn} and suppose that \emph{Si} has the type
\cd{(series~$\emph{s}_{i}$)}.

The \emph{init} must be of type 
\cd{(function () (values $\emph{t}_1$ ... $\emph{t}_{m}$))}.

The \emph{function} must be of type
\begin{lisp}
(function ($\emph{t}_1$ ... $\emph{t}_{m}$ $\emph{s}_1$ ... $\emph{s}_{n}$) (values $\emph{t}_1$ ... $\emph{t}_{m}$))
\end{lisp}

The length of each output is the same as the length of the shortest input.
If there are no bounded series inputs, the outputs are unbounded.
The elements of the \emph{Ti} are computed as follows:
\begin{lisp}
(values \emph{T1}\SU{0} ... \emph{Tm}\SU{0}) {\EQ} \\*
~~(multiple-value-call \emph{function} (funcall  \emph{init}) \emph{S1}\SU{0} ... \emph{Sn}\SU{0}) \\
\\
(values \emph{T1}\SU{j} ... \emph{Tm}\SU{j}) {\EQ} \\*
~~(funcall \emph{function} \emph{T1}\SU{(j-1)} ... \emph{Tm}\SU{(j-1)} \emph{S1}\SU{j} ... \emph{Sn}\SU{j}) 
\end{lisp}

If \emph{init} or \emph{function} has side effects, it can count on
being called in the order indicated by the equations above.  However,
given the lazy evaluation nature of series, these functions will not be called
until their outputs are actually used (if ever).  In addition, no
assumptions can be made about the relative order of evaluation of these
calls with regard to execution in other parts of a given series expression.
The second example below computes a series of partial sums of the numbers in
an input series.  The third example computes two output series: the
partial sums of its first input and the partial products of its second
input.
\begin{lisp}
(defun running-averages (float-list) \\*
~~(multiple-value-call \#'map-fn \\*
~~~~'float \#'/ \\*
~~~~(collecting-fn '(values float integer) \\*
~~~~~~~~~~~~~~~~~~~\#'(lambda () (values 0.0 0) \\*
~~~~~~~~~~~~~~~~~~~\#'(lambda (s n x) (values (+ s x) (+ n 1)))) \\*
~~~~~~~~~~~~~~~~~~~float-list)))
\end{lisp}
\begin{lisp}
(collecting-fn 'integer \#'(lambda () 0) \#'+ \#Z(1 2 3)) \\*
~~{\EV} \#Z(1 3 6) \\
\\
(collecting-fn '(values integer integer) \\*
~~~~~~~~~~~~~~~\#'(lambda () (values 0 1)) \\*
~~~~~~~~~~~~~~~\#'(lambda (sum prod x y) \\*
~~~~~~~~~~~~~~~~~~~(values (+ sum x) (* prod y))) \\*
~~~~~~~~~~~~~~~\#Z(4 6 8)  \\*
~~~~~~~~~~~~~~~\#Z(1 2 3)) \\*
~~{\EV} \#Z(4 10 18) {\rm and} \#Z(1 2 6)
\end{lisp}
\end{defun}

\subsection{Conditional and Other Complex Transducers}
\label{SERIES-OL-SECTION}

This section presents a number of complex transducers, including ones that
support conditional computation.


\begin{defun}[Function]
choose bools &optional (items bools) \\
choose-if pred items

Each of these functions takes in a series of elements (\emph{items}) and
returns a series containing the same elements in the same order, but with
some elements removed.  \cdf{choose} removes \emph{items}\SU{j} if {\it
bools}\SU{j} is \cdf{nil} or $\emph{j}$ is beyond the end of \emph{bools}.  If {\it
items} is omitted, \cdf{choose} returns the non-null elements of {\it
bools}.  \cdf{choose-if} removes \emph{items}\SU{j} if 
\cd{(\emph{pred}~\emph{items}\SU{j})} is \cdf{nil}.
\begin{lisp}
(choose \#Z(t nil t nil) \#Z(a b c d)) {\EV} \#Z(a c) \\*
(collect-sum (choose-if \#'plusp \#Z(-1 2 -3 4))) {\EV} 6
\end{lisp}
\end{defun}

\begin{defun}[Function]
expand bools items &optional (default nil)

\cdf{expand} is a quasi-inverse of \cdf{choose}.  The output contains the
elements of the input series \emph{items} spread out into the positions
specified by the non-null elements
in \emph{bools}---that is, \emph{items}\SU{j}
is in the position occupied by the \emph{j\/}th non-null element in \emph{bools}.
The other positions in the output are occupied by \emph{default}.  The
output stops as soon as \emph{bools} runs out of elements or a non-null
element in \emph{bools} is encountered for which there is no corresponding
element in \emph{items}.
\begin{lisp}
(expand \#Z(nil t nil t t) \#Z(a b c)) {\EV} \#Z(nil a nil b c) \\*
(expand \#Z(nil t nil t t) \#Z(a)) {\EV} \#Z(nil a nil)
\end{lisp}
\end{defun}

\begin{defun}[Function]
split items &rest test-series-inputs \\
split-if items &rest test-predicates

These functions are like \cdf{choose} and \cdf{choose-if} except that
instead of producing one restricted output, they partition the input series
\emph{items} between several outputs.  If there are $\emph{n}$ test inputs
following \emph{items}, then there are $\emph{n}+1$ outputs.  Each input element is
placed in exactly one output series, depending on the outcome of a sequence
of tests.  If the element \emph{items}\SU{j} fails the first $\emph{k}-1$ tests and
passes the \emph{k\/}h test, it is put in the \emph{k\/}th output.
If \emph{items}\SU{j}
fails every test, it is placed in the last output.  In addition, all output
stops as soon as any series input runs out of elements.  The test inputs to
\cdf{split} are series of values; \emph{items}\SU{j} passes the \emph{k\/}th test
if the \emph{j\/}th element of the \emph{k\/}th test series is not \cdf{nil}.  The test
inputs to \cdf{split-if} are predicates; \emph{items}\SU{j} passes the \emph{k\/}th
test if the \emph{k\/}th test predicate returns non-null when applied to {\it
items}\SU{j}.
\begin{lisp}
(split \#Z(-1 2 3 -4) \#Z(t nil nil t)) \\*
~~{\EV} \#Z(-1 -4) {\rm and} \#Z(2 3) \\
(multiple-value-bind (+x -x) (split-if  \#Z(-1 2 3 -4) \#'plusp) \\*
~~(values (collect-sum +x) (collect-sum -x))) \\*
~~{\EV} 5 {\rm and} -5
\end{lisp}
\end{defun}

\begin{defun}[Function]
catenate &rest series-inputs

\cdf{catenate} combines two or more series into one long series by appending
them end to end.  The length of the output is the sum of the lengths of the
inputs.
\begin{lisp}
(catenate \#Z(b c) \#Z() \#Z(d)) {\EV} \#Z(b c d)
\end{lisp}
\end{defun}

\begin{defun}[Function]
subseries items start &optional below

\cdf{subseries} returns a series containing the elements of the input
series \emph{items} indexed by the non-negative integers from \emph{start} up
to, but not including, \emph{below}.  If \emph{below} is omitted or greater
than the length of \emph{items}, the output goes all the way to the end
of \emph{items}.
\begin{lisp}
(subseries \#Z(a b c d) 1) {\EV} \#Z(b c d) \\*
(subseries \#Z(a b c d) 1 3) {\EV} \#Z(b c)
\end{lisp}
\end{defun}

\begin{defun}[Function]
positions bools

\cdf{positions} returns a series of the indices of the non-null elements in
the series input \emph{bools}.
\begin{lisp}
(positions \#Z(t nil t 44)) {\EV} \#Z(0 2 3)
\end{lisp}
\end{defun}

\begin{defun}[Function]
mask monotonic-indices

\cdf{mask} is a quasi-inverse of \cdf{positions}.  The series input {\it
monotonic-indices} must be a strictly increasing series of non-negative
integers.  The output, which is always unbounded, contains \cdf{t} in the
positions specified by \emph{monotonic-indices} and \cdf{nil} everywhere else.
\begin{lisp}
(mask \#Z(0 2 3)) {\EV} \#Z(t nil t t nil nil ...) \\*
(mask \#Z()) {\EV} \#Z(nil nil ...) \\*
(mask (positions \#Z(nil a nil b nil))) \\*
~~{\EV} \#Z(nil t nil t nil ...)
\end{lisp}
\end{defun}


\begin{defun}[Function]
mingle items1 items2 comparator

The series returned by \cdf{mingle} contains all and only the elements of
the two input series.  The length of the output is the sum of the lengths
of the inputs and is unbounded if either input is unbounded.  The order of
the elements remains unchanged; however, the elements from the two inputs
are stably intermixed under the control of the \emph{comparator}.

The \emph{comparator} must accept two arguments and return non-null if and only
if its first argument is strictly less than its second argument (in some
appropriate sense).  At each step, the \emph{comparator} is used to compare
the current elements in the two series.  If the current element from {\it
items2} is strictly less than the current element from \emph{items1}, the
current element is removed from \emph{items2} and transferred to the output.
Otherwise, the next output element comes from \emph{items1}.
\begin{lisp}
(mingle \#Z(1 3 7 9) \#Z(4 5 8) \#'<) {\EV} \#Z(1 3 4 5 7 8 9) \\*
(mingle \#Z(1 7 3 9) \#Z(4 5 8) \#'<) {\EV} \#Z(1 4 5 7 3 8 9)
\end{lisp}
\end{defun}

\begin{defun}[Function]
chunk m n items

This function has the effect of breaking up the input series \emph{items} into
(possibly overlapping) chunks of length \emph{m}.  The starting positions of successive chunks differ
by \emph{n}.  The inputs \emph{m} and \emph{n} must both be positive integers.

\cdf{chunk} produces \emph{m} output series.  The \emph{i\/}th chunk provides
the \emph{i\/}th element for
each of  the \emph{m} outputs.  Suppose that the length of \emph{items} is \emph{l}.
The length of
each output is $\lfloor1+(\emph{l}-\emph{m})/\emph{n}\rfloor$.
The \emph{i\/}th element of the \emph{k\/}th output is the
$(\emph{i}*\emph{n}+\emph{k})$th element of \emph{items} (\emph{i} and $\emph{k}$ counting from zero).  

Note that if $\emph{l}<\emph{m}$, there will be no
output elements, and if $\emph{l}-\emph{m}$ is not a multiple of \emph{n},
the last few input elements will
not appear in the output.  If $\emph{m}\ge \emph{n}$,
one can guarantee that the last chunk will contain the last
element of \emph{items} by catenating $\emph{n}-1$
copies of an appropriate padding value to the end of \emph{items}.

The first example below shows \cdf{chunk}
being used to compute a moving average.  The second example shows
\cdf{chunk} being used to convert a property list into an association list.
\begin{lisp}
(mapping (((xi xi+1 xi+2) (chunk 3 1 \#Z(1 5 3 4 5 6)))) \\* 
~~(/ (+ xi xi+1 xi+2) 3)) \\*
~~{\EV} \#Z(3 4 4 5)
\\
(collect \\*
~~(mapping (((prop val) (chunk 2 2 (scan '(a 2 b 5 c 8))))) \\*
~~~~(cons prop val))) \\*
~~{\EV} ((a . 2) (b . 5) (c . 8))
\end{lisp}
\end{defun}

\subsection{Collectors}

Collectors produce non-series outputs based on series inputs.  They either
create a summary value based on some formula (the sum, for example) or collect the
elements of a series in an aggregate data structure (such as a list).

\begin{defun}[Function]
collect-first items &optional (default nil) \\
collect-last items &optional (default nil) \\
collect-nth n items &optional (default nil)

Given a series \emph{items}, these functions return the first element, the
last element, and the \emph{n\/}th element, respectively.  If \emph{items} has
no elements (or no \emph{n\/}th element), \emph{default} is returned.
If \emph{default} is not specified, then \cdf{nil} is used for \emph{default}.
\begin{lisp}
(collect-first \#Z() 'z) {\EV} z \\*
(collect-last \#Z(a b c)) {\EV} c \\*
(collect-nth 1 \#Z(a b c)) {\EV} b
\end{lisp}
\end{defun}

\begin{defun}[Function]
collect-length items

\cdf{collect-length} returns the number of elements in a series.
\begin{lisp}
(collect-length \#Z(a b c)) {\EV} 3
\end{lisp}
\end{defun}


\begin{defun}[Function]
collect-sum numbers &optional (type 'number)

\cdf{collect-sum} returns the sum of the elements in a series of numbers.
The \emph{type} is a type specifier that indicates the type of sum
to be created.  If \emph{type} is not specified, then \cdf{number} is used for
the \emph{type}.
If there are no elements in the input, a zero (of the
appropriate type) is returned.
\begin{lisp}
(collect-sum \#Z(1.1 1.2 1.3)) {\EV} 3.6 \\*
(collect-sum \#Z() 'complex) {\EV} \#C(0 0)
\end{lisp}
\end{defun}


\begin{defun}[Function]
collect-max numbers \\
collect-min numbers

Given a series of non-complex numbers, these functions compute the maximum
element and the minimum element, respectively.  If there are no elements in
the input, \cdf{nil} is returned.
\begin{lisp}
(collect-max \#Z(2 1 4 3)) {\EV} 4 \\*
(collect-min \#Z(1.2 1.1 1.4 1.3)) {\EV} 1.1 \\*
(collect-min \#Z()) {\EV} nil
\end{lisp}
\end{defun}


\begin{defun}[Function]
collect-and bools

\cdf{collect-and} returns the \cdf{and} of the elements in a series.  As
with the macro \cdf{and}, \cdf{nil} is returned if any element of {\it
bools} is \cdf{nil}.  Otherwise, the last element of \emph{bools} is
returned.  The value \cdf{t} is returned if there are no elements in {\it
bools}.
\begin{lisp}
(collect-and \#Z(a b c)) {\EV} c \\*
(collect-and \#Z(a nil c)) {\EV} nil
\end{lisp}
\end{defun}

\begin{defun}[Function]
collect-or bools

\cdf{collect-or} returns the \cdf{or} of the elements in a series.  As with
the macro \cdf{or}, \cdf{nil} is returned if every element of {\it
bools} is \cdf{nil}.  Otherwise, the first non-null element of \emph{bools}
is returned.  The value \cdf{nil} is returned if there are no elements in
\emph{bools}.
\begin{lisp}
(collect-or \#Z(nil b c)) {\EV} b \\*
(collect-or \#Z()) {\EV} nil
\end{lisp}
\end{defun}

\begin{defun}[Function]
collect items \\
collect type items

\cdf{collect} returns a sequence containing the elements of the series {\it
items}.  The \emph{type} is a type specifier indicating the type of sequence
to be created.  It must be either a proper subtype of \cdf{sequence} or the
symbol \cdf{bag}.  If \emph{type} is omitted, it defaults to \cdf{list}.
(This function exhibits an argument pattern that is unusual for Common
Lisp:  an ``optional'' argument preceding a required argument.  This
pattern cannot be expressed in the usual manner with \cd{\&optional}.  It
is indicated above by two definition lines, showing the two possible
argument patterns.)

If the \emph{type} is \cdf{bag}, a list is created with the elements in
whatever order can be most efficiently obtained.  Otherwise, the order of
the elements in the sequence is the same as the order in \emph{items}.  If
\emph{type} specifies a length (that is, of a vector) this length must be
greater than or equal to the length of \emph{items}.

The \emph{n\/}th element of \emph{items} is
placed in the \emph{n\/}th slot of the sequence produced.  Any unneeded slots are
left in their initial state.  Collecting is significantly more efficient if
it can be determined at compile time whether \emph{type} is a subtype of
\cdf{list} or \cdf{vector} and for vectors what the length of the vector is.
\begin{lisp}
(collect \#Z(a b c)) {\EV} (a b c) \\*
(collect 'bag \#Z(a b c)) {\EV} (c a b) {\rm or} (b a c) {\rm or $\ldots$} \\*
(collect '(vector integer 3) \#Z(1 2 3)) {\EV} \#(1 2 3)
\end{lisp}
\end{defun}

\begin{defun}[Function]
collect-append sequences \\
collect-append type sequences

Given a series of sequences, \cdf{collect-append} returns a new sequence by
concatenating these sequences together in order.  The \emph{type} is a type
specifier indicating the type of sequence created and must be a proper
subtype of \cdf{sequence}.  If \emph{type} is omitted, it defaults to
\cdf{list}.  (This function exhibits an argument pattern that is unusual for Common
Lisp:  an ``optional'' argument preceding a required argument.  This
pattern cannot be expressed in the usual manner with \cd{\&optional}.  It
is indicated above by two definition lines, showing the two possible
argument patterns.)

It must be possible for every element of every sequence in the input series
to be an element of a sequence of type \emph{type}.  The result does not
share any structure with the sequences in the input.
\begin{lisp}
(collect-append \#Z((a b) nil (c d))) {\EV} (a b c d) \\*
(collect-append 'string \#Z("a " "big " "cat")) {\EV} "a big cat"
\end{lisp}
\end{defun}

\begin{defun}[Function]
collect-nconc lists

\cdf{collect-nconc} \cdf{nconc}s the elements of the series {\it
lists} together in order and returns the result.  This is the same as
\cdf{collect-append} except that the input must be a series of lists,
the output is always a list, the concatenation is done rapidly by
destructively modifying the input elements, and therefore the output
shares all of its structure with the input elements.
\end{defun}

\begin{defun}[Function]
collect-alist keys values \\
collect-plist keys values \\
collect-hash keys values &key :test :size :rehash-size :rehash-threshold

\noindent Given a series of keys and a series of corresponding values, these
functions return an association list, a property list, and a hash table,
respectively.  Following the order of the input, each \emph{keys}\SU{j}-{\it
values}\SU{j} pair is entered into the output so that it overrides all
earlier associations.  If one of the input series is longer than the other,
the extra elements are ignored.  The keyword arguments of 
\cdf{collect-hash} specify attributes of the hash table produced and have the
same meanings as the arguments to \cdf{make-hash-table}.
\begin{lisp}
(collect-alist \#Z(a b c) \#Z(1 2)) {\EV} ((b . 2) (a . 1)) \\*
(collect-plist \#Z(a b c) \#Z(1 2)) {\EV} (b 2 a 1) \\*
(collect-hash \#Z() \#Z(1 2) :test \#'eq) {\EV} {\rm $\langle$an empty hash table$\rangle$}
\end{lisp}
\end{defun}

\begin{defun}[Function]
collect-file file-name items &optional (printer \#'print)

This creates a file named \emph{file-name} and writes the
elements of the series \emph{items} into it using the function {\it
printer}.  \emph{Printer} must accept two inputs: an object
and an output stream.  (For instance, \emph{printer} can be \cdf{print},
\cd{prin1}, \cdf{princ}, \cdf{pprint}, \cdf{write-char},
\cdf{write-string}, or \cdf{write-line}.)
If omitted, \emph{printer} defaults to \cdf{print}.  The value \cdf{t} is
returned.  The file is correctly closed, even if an abort occurs.
\end{defun}


\begin{defun}[Function]
collect-fn type init function &rest series-inputs

The higher-order function \cdf{collect-fn} supports the general concept of
collecting.  It is identical to \cdf{collecting-fn} except that it
returns only the last element of each series computed.  If there are no elements
in these series, the values returned by \emph{init} are passed on directly
as the output of \cdf{collect-fn}.
\begin{lisp}
(collect-fn 'integer \#'(lambda () 0) \#'+ \#Z(1 2 3)) {\EV} 6 \\*
(collect-fn 'integer \#'(lambda () 0) \#'+ \#Z()) {\EV} 0 \\*
(collect-fn 'integer \#'(lambda () 1) \#'* \#Z(1 2 3 4 5)) {\EV} 120
\end{lisp}
\end{defun}

\subsection{Alteration of Series}

Series that come from scanning data structures such as lists and vectors
are closely linked to these structures.  The function 
\cdf{alter} can be used to modify the underlying data structure with
reference to the series derived from it. (Conversely, it is possible to
modify a series by destructively modifying the data structure it is derived
from.  However, given the lazy evaluation nature of series, the effects of
such modifications can be very hard to predict.  As a result, this kind of
modification is inadvisable.)

\begin{defun}[Function]
alter destinations items

\cdf{alter} changes the series \emph{destinations} so that it contains
the elements in the series \emph{items}.  More importantly, in the
manner of \cdf{setf}, the data structure that underlies {\it
destinations} is changed so that if the series \emph{destinations} were
to be regenerated, the new values would be obtained.  The alteration
process stops as soon as either input runs out of elements.  The value
\cdf{nil} is always returned. In the example below each negative element in
a list is replaced with its square.
\begin{lisp}
(let* ((data (list 1 -2 3 4 -5 6)) \\*
~~~~~~~(x (choose-if \#'minusp (scan data)))) \\*
~~(alter x (\#M* x x)) \\*
~~data) \\*
~~{\EV} (1 4 3 4 25 6)
\end{lisp}

\cdf{alter} can be applied only to series that are \emph{alterable}.  
\cdf{scan}, \cdf{scan-alist}, \cdf{scan-multiple}, \cdf{scan-plist}, and
\cdf{scan-lists-of-lists-fringe} produce alterable series.  
However, the alterability of
the output of
\cdf{scan-lists-of-lists-fringe}
is incomplete.  If
\cdf{scan-lists-of-lists-fringe}
is applied to an object that is a leaf,
altering the output series does not change the object.

In general, the output of a transducer is alterable as long as the elements
of the output come directly from the elements of an input that is
alterable.  In particular, the outputs of \cdf{choose}, \cdf{choose-if},
\cdf{split}, \cdf{split-if}, \cdf{cotruncate}, \cdf{until}, \cdf{until-if},
and \cdf{subseries} are alterable as long as the corresponding inputs are
alterable.
\end{defun}


\begin{defun}[Function]
to-alter items alter-fn &rest args

Given a series \emph{items}, \cdf{to-alter} returns an alterable series {\it
A} containing the same elements.  The argument \emph{alter-fn} is a
function.  The remaining arguments are all series.  Let these series be
\emph{S1},~$\ldots\,$,~\emph{Sn}.  If there are $\emph{n}$ arguments after \emph{alter-fn},
\emph{alter-fn} must accept $\emph{n}+1$ inputs.  If \cd{(alter~\emph{A}~\emph{B})} is
later encountered, the expression
\cd{(map-fn~t~\emph{alter-fn}~\emph{B}~\emph{S1}~...~\emph{Sn})} is implicitly
evaluated.  For each
element in \emph{B}, \emph{alter-fn} should make appropriate changes in the
data structure underlying \emph{A}.

As an example, consider the following definition of a series function
that scans the elements of a list.  Alteration is performed by
changing cons cells in the list being scanned.
\begin{lisp}
(defun scan-list (list) \\*
~~(declare (optimizable-series-function)) \\*
~~(let ((sublists (scan-sublists list))) \\*
~~~~(to-alter (\#Mcar sublists) \\*
~~~~~~~~~~~~~~\#'(lambda (new parent) (setf (car parent) new)) \\*
~~~~~~~~~~~~~~sublists)))
\end{lisp}
\end{defun}

\section{Optimization}\label{SERIES-E-SECTION}

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 \emph{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.)

\subsection{Basic Restrictions}

The transformation of series expressions into loops is required to occur at
some time before compiled code is actually run.  Optimization may or may
not be applied to interpreted code.  If any of the restrictions described
below are violated, optimization is not possible.  In this situation, a
warning message is issued at the time optimization is attempted and the
code is left unoptimized.  This is not a fatal error and does not prevent
the correct results from being computed.  However, given the large
improvements in efficiency to be gained, it is well worth fixing any
violations that occur.  This is usually easy to do.

\begin{defun}[Variable]
*suppress-series-warnings*

If this variable is set (or bound) to anything other than its default
value of \cdf{nil}, warnings about conditions that block the optimization
of series expressions are suppressed.
\end{defun}

Before the restrictions on series expressions are discussed, it will be useful to
define precisely what is meant by the term \emph{series expression}.  This
term is semantic rather than syntactic in nature. Imagine a program
converted from Lisp code into a data flow graph.  In a data flow graph,
functions are represented as boxes, and both control flow and data flow are
represented as arrows between the boxes.  Constructs such as \cdf{let} and
\cdf{setq} are converted into patterns of data flow arcs.  Control
constructs such as \cdf{if} and \cdf{loop} are converted into patterns of
control flow arcs.  Suppose further that all loops have been converted
into tail recursions so that the graph is acyclic.

A series expression is a subgraph of the data flow graph for a program that
contains a group of interacting series functions.  More specifically, given
a call \emph{f} on a series function, the series expression \emph{E} containing it is
defined as follows.  \emph{E} contains \emph{f}.  Every function using a series
created by a function in \emph{E} is in \emph{E}.  Every function computing a series
used by a function in \emph{E} is in \emph{E}.  Finally, suppose that two functions
\emph{g} and \emph{h} are in \emph{E} and that there is a data flow path consisting of
series and/or non-series data flow arcs from \emph{g} to \emph{h}.  Every function
touched by this path (be it a series function or not) is in~\emph{E}.

{\bf For optimization to be possible, series expressions have to be
statically analyzable}.  As with most other optimization processes, a
series expression cannot be transformed into a loop at compile time, unless
it can be determined at compile time exactly what computation is being
performed.  This places a number of relatively minor limits on what can be
written.  For example, for optimization to be possible the type arguments
to higher-order functions such as \cdf{map-fn} and \cdf{collecting-fn} have
to be quoted constants.  Similarly, the numeric arguments to \cdf{chunk}
have to be constants.  In addition, if \cdf{funcall} is used to call a
series function, the function called has to be of the
form \cd{(function~...)}.

{\bf For optimization to be possible, every series created within a series
expression must be used solely inside the expression}.  If a series is
transmitted outside of the expression that creates it, it has to be
physically represented as a whole.  This is incompatible with the
transformations required to pipeline the creating expression. To avoid this
problem, a series must not be returned as a result of a series expression
as a whole, assigned to a free variable, assigned to a special variable, or
stored in a data structure.  A corollary of the last point is that when
defining new optimizable series functions, series cannot be passed into
\cd{\&rest} arguments.  Further, optimization is blocked if a series is
passed as an argument to an ordinary Lisp function.  Series can be
passed only to the series functions in section~\ref{SERIES-F-SECTION} and to new series
functions defined using the declaration \cdf{optimizable-series-function}.

{\bf For optimization to be possible, series expressions must correspond to
straight-line computations}.  That is to say, the data flow graph
corresponding to a series expression cannot contain any conditional
branches.  (Complex control flow is incompatible with pipelining.)
Optimization is possible in the presence of standard straight-line forms
such as \cdf{progn}, \cdf{funcall}, \cdf{setq}, \cdf{lambda}, \cdf{let},
\cdf{let*}, and \cd{multiple-{\allowbreak}value-{\allowbreak}bind} as long
as none of the variables bound are special.  There is also no problem with
macros as long as they expand into series functions and straight-line forms.
However, optimization is blocked by forms that specify complex control flow
(i.e., conditionals \cdf{if}, \cdf{cond}, etc., looping constructs \cdf{loop},
\cdf{do}, etc., or branching constructs \cdf{tagbody}, \cdf{go}, \cdf{catch},
etc.).

In the first example below, optimization is blocked, because the \cdf{if}
form is inside the series expression.  In the second example, however,
optimization is possible, because although the \cdf{if} feeds data to the
series expression, it is not inside the corresponding subgraph.  Both of
the expressions below produce the same value, but the second one is
much more efficient.
\begin{lisp}
(collect (if flag (scan x) (scan y)))~~;{\rm Warning message issued} \\*
(collect (scan (if flag x y))) 
\end{lisp}

\subsection{Constraint Cycles}

Even if a series expression satisfies all of the restrictions above, it
still may not be possible to transform the expression into a loop.  The
sole remaining problem is that if a series is used in two places, the
two uses may place incompatible constraints on the times at which series
elements should be produced.

The series expression below shows a situation where this problem arises.
The expression creates a series \cdf{x} of the elements in a list. It then
creates a normalized series by dividing each element of \cdf{x} by the sum
of the elements in \cdf{x}.  Finally, the expression returns the maximum of
the normalized elements.
\begin{lisp}
(let ((x (scan '(1 2 5 2))))~~~~~~~~~~~;{\rm Warning message issued} \\*
~~(collect-max (\#M/ x (series (collect-sum x))))) {\EV} 1/2
\end{lisp}

The two uses of \cdf{x} in the expression place contradictory
constraints on the way pipelined evaluation must proceed;  \cdf{collect-sum}
requires that all of the elements of \cdf{x} be produced before the sum can
be returned, and \cdf{series} requires that its input be available before it
can start to produce its output.  However, \cd{\#M/} requires that the
first element of \cdf{x} be available at the same time as the first element
of the output of \cdf{series}.  For pipelining to work,
the first element of the output of \cdf{series} (and therefore the output
of \cdf{collect-sum}) must be available before the second element of 
\cdf{x} is produced.  Unfortunately, this is impossible.

The essence of the inconsistency above is the cycle of constraints used in
the argument.  This in turn stems from a cycle in the data flow graph
underlying the expression.  In
figure~\ref{SERIES-F1-FIGURE} function calls are represented by boxes and data
flow is represented by arrows.  Simple arrows indicate the flow of series
values and cross-hatched arrows indicate the flow of non-series values.

\begin{figure}[t]
\caption{A Constraint Cycle in a Series Expression}\label{SERIES-F1-FIGURE}
\vskip 5pc
\PostScriptFile{series-plot.ps}\relax
\hbox{\relax
\def\foo#1#2#3{\vbox to 0pt{\vskip #2\vskip 3pt\hbox to 0pt{\hskip #1\hskip -3pt\vbox to 0pt{\vss
   \hbox to 0pt{\hss \tt #3\hss}\vss}\hss}\vss}}
\foo{2.5pc}{-3.5pc}{scan}\relax
\foo{8.5pc}{-2.5pc}{sum}\relax
\foo{14pc}{-2.5pc}{series}\relax
\foo{19.5pc}{-3.5pc}{\#M/}\relax
\foo{25pc}{-3.5pc}{max}}
\end{figure}

Given a data flow graph corresponding to a series expression, a {\it
constraint cycle} is a closed oriented loop of data flow arcs such
that each arc is traversed exactly once and no non-series arc
is traversed backward.  (Series data flow arcs can be traversed in either
direction.)  A constraint cycle is said to \emph{pass through} an input or
output port when exactly one of the arcs in the cycle touches the port.  In
figure~\ref{SERIES-F1-FIGURE} the data flow arcs touching \cdf{scan}, \cdf{sum},
\cdf{series}, and \cd{\#M/} form a constraint cycle.  Note that if the
output of \cdf{scan} were not a series, this loop would not be a constraint
cycle, because there would be no valid way to traverse it.  Also note that
while the constraint cycle passes through all the other ports it touches,
it does not pass through the output of \cdf{scan}.

Whenever a constraint cycle passes through a non-series output, an argument
analogous to the one above can be constructed and therefore pipelining will be
impossible.  When this situation arises, a warning message is issued
identifying the problematical port and the cycle passing through it.  For
instance, the warning triggered by the example above states that the
constraint cycle associated with \cdf{scan}, \cdf{collect-sum}, 
\cdf{series}, and \cd{\#M/} passes through the non-series output of 
\cdf{collect-sum}.

Given this kind of detailed information, it is easy to alleviate the
problem.  To start with, every cycle must contain at least one function
that has two series data flows leaving it.  At worst, the cycle can be broken by
duplicating this function (and any functions computing series used by it).
For instance, the example above can be
rewritten as shown below.
\begin{lisp}
(let ((x (scan '(1 2 5 2))) \\*
~~~~~~(sum (collect-sum (scan '(1 2 5 2))))) \\*
~~(collect-max (\#M/ x (series sum)))) \\*
~~{\EV} 1/2
\end{lisp}

It would be easy enough to automatically apply code copying to break
problematical constraint cycles.  However, this is not done for two
reasons.  First, there is considerable virtue in maintaining the property
that each function in a series expression turns into one piece of
computation in the loop produced.  Users can be confident that series
expressions that look simple and efficient actually are simple and
efficient.  Second, with a little creativity, constraint problems can often
be resolved in ways that are much more efficient than copying code.  In the
example above, the conflict can be eliminated efficiently by interchanging
the operation of computing the maximum with the operation of normalizing an
element.
\begin{lisp}
(let ((x (scan '(1 2 5 2)))) \\*
~~(/ (collect-max x) (collect-sum x))) {\EV} 1/2
\end{lisp}

The restriction that optimizable series expressions cannot contain
constraint cycles that pass through non-series outputs places limitations on
the qualitative character of optimizable series expressions.  In particular,
they all must have the general form of creating some number of series using
scanners, computing various intermediate series using transducers, and then
computing one or more summary results using collectors.  The output of a
collector cannot be used in the intermediate computation unless it is the
output of a separate subexpression.

It is worthy of note that the last expression above fixes the constraint
conflict by moving the non-series output out of the cycle, rather than by
breaking the cycle.  This illustrates the fact that constraint cycles that
do not pass through non-series outputs do not necessarily cause problems.
They cause problems only if they pass through \emph{off-line} ports.

A series input port or series output port of a series function is \emph{on-line}
if and only if it is processed in lockstep with all the other on-line
ports as follows:  the initial element of each on-line input is
read, then the initial element of each on-line output is written, then the
second element of each on-line input is read, then the second element of
each on-line output is written, and so on.  Ports that are not on-line are
off-line.  If all of the series ports of a function are on-line, the
function is said to be on-line; otherwise, it is off-line.  (The above
extends the standard definition of the term \emph{on-line} so that it applies
to individual ports as well as whole functions.)

If all of the ports a cycle passes through are on-line, the lockstep
processing of these ports guarantees that there cannot be any conflicts
between the constraints associated with the cycle.  However, passing
through an off-line port leads to the same kinds of problems as passing
through a non-series output.

Most of the series functions are on-line.  In particular, scanners and
collectors are all on-line as are many transducers.  However, the
transducers in section~\ref{SERIES-OL-SECTION} are off-line.  In particular, the
series inputs of \cdf{catenate}, \cdf{choose-if}, \cdf{chunk}, \cdf{expand}, \cdf{mask},
\cdf{mingle}, \cdf{positions}, and \cdf{subseries} along with the
series outputs of \cdf{choose}, \cdf{split}, and \cdf{split-if} are off-line.

In summary, the fourth and final restriction is that {\bf for optimization
to be possible, a series expression cannot contain a constraint cycle that
passes through a non-series output or an off-line port}.  Whenever this
restriction is violated a warning message is issued.  Violations can be
fixed either by breaking the cycle or restructuring the computation so that
the offending port is removed from the cycle.

\subsection{Defining New Series Functions}

New functions operating on series can be defined just as easily as new
functions operating on any other data type.  However, expressions
containing these new functions cannot be transformed into loops unless a
complete analysis of the functions is available.  Among other things,
this implies that the definition of a new series function must appear
before its first use.


\begin{defun}[Declaration specifier]
optimizable-series-function

The declaration specifier \cd{(optimizable-series-function~\emph{integer})} indicates
that the function being defined is a series function that needs to be
analyzed so that it can be optimized when it appears in series expressions.
(A warning is issued if the function being defined neither takes a series
as input nor produces a series as output.)  \emph{Integer} (default 1)
specifies the number of values returned by the function being defined.
(This cannot necessarily be determined by local analysis.)  The only place
\cdf{optimizable-series-function} is allowed to appear is in a declaration
immediately inside a \cdf{defun}.  As an example, the following shows how a
simplified version of \cdf{collect-sum} could be defined.
\begin{lisp}
(defun simple-collect-sum (numbers) \\*
~~(declare (optimizable-series-function 1)) \\*
~~(collect-fn 'number \#'(lambda () 0) \#'+ numbers))
\end{lisp}
\end{defun}

\begin{defun}[Declaration specifier]
off-line-port

The declaration specifier
\cd{(off-line-port~\emph{port-spec1}~\emph{port-spec2}~...)} specifies that the
indicated inputs and outputs are off-line.  This declaration
specifier is only allowed in a \cdf{defun} that contains the declaration 
\cdf{optimizable-series-function}.  Each \emph{port-spec} must either be a symbol
that is one of the inputs of the function or an integer \emph{j} indicating the
\emph{j\/}th output (counting from zero).  For example, \cd{(off-line-port~x~1)}
indicates that the input \cdf{x} and the second output are off-line.
Every port that is not mentioned in an \cdf{off-line-port}
declaration is assumed to be on-line.  A warning is issued whenever a
port's actual on-line/off-line status does not agree with its declared
status.  This makes it easier to keep track of which ports are off-line and
which are not.  Note that off-line ports virtually never arise when
defining scanners or reducers.
\end{defun}

\subsection{Declarations}

A key feature of Lisp is that variable declarations are strictly optional.
Nevertheless, it is often the case that they are necessary in situations
where efficiency matters.  Therefore, it is important that it be {\it
possible} for programmers to provide declarations for every variable in a
program.  The transformation of series expressions into loops presents
certain problems in this regard, because the loops created contain
variables not evident in the original code.  However, if the information
described below is supplied by the user, appropriate declarations can be
generated for all of the loop variables created.

All the explicit variables that are bound in a series expression (for example, by a 
\cdf{let} that is part of the expression) should be given informative
declarations making use of the type specifier \cd{(series~\emph{element-type})}
where appropriate.

Informative types should be supplied to series functions (such as 
\cdf{scan} and \cdf{map-fn}) that have type arguments.  When using 
\cdf{scan} it is important to specify the type of element in the sequence as
well as the sequence itself (for example, by using \cd{(vector~*~integer)} as
opposed to merely \cdf{vector}).  The form \cd{(list~\emph{element-type})}
can be used to specify the type of elements in a list.

If it is appropriate to have a type more specific than \cd{(series~t)}
associated with the output of \cd{\#M}, \cd{\#Z}, \cdf{scan-alist}, 
\cdf{scan-file}, \cdf{scan-hash}, \cdf{scan-lists-of-lists-fringe}, 
\cdf{scan-lists-of-lists}, \cdf{scan-plist},
\cdf{series}, \cdf{latch}, or \cdf{catenate}, then the form
\cdf{the} must be used to specify this type.

Finally, if the expression computing a non-series argument to a series
variable is neither a variable nor a constant, \cdf{the} must be used to
specify the type of its result.

For example, the declarations in the series expressions below are
sufficient to ensure that every loop variable will have an accurate
declaration.
\begin{lisp}
(collect-last (choose-if \#'plusp (scan '(list integer) data))) \\
\\
(collect '(vector * float) \\*
~~~~~~~~~(map-fn 'float \#'/ \\*
~~~~~~~~~~~~~~~~~(series (the integer (car data))) \\*
~~~~~~~~~~~~~~~~~(the (series integer) (scan-file f))))
\end{lisp}

The amount of information the user has to provide is reduced by the fact
that this information can be propagated from place to place.  For instance,
the variable holding the output of \cdf{choose-if} holds a subset of the
elements held by the input variable.  As a result, it is appropriate for it
to have the same type.  When defining a new series function, the type
specifier \cdf{series-element-type} can be used to indicate where type
propagation should occur.

\begin{defun}[Type specifier]
series-element-type

The type specifier \cd{(series-element-type~\emph{variable})} denotes the
type of elements in the series held in \emph{variable}.  \emph{Variable} must
be a variable carrying a series value (for example, a series argument of a series
function).  \cdf{series-element-type} can be used only in three places: in
a declaration in a \cdf{let}, \cdf{mapping}, \cdf{producing}, or other
binding form in a series expression; in a declaration in a \cdf{defun}
being used to define a series function; or in a type argument to a series
function.  As an example, consider that \cdf{collect-last} could have been
defined as follows.  The use of \cdf{series-element-type} ensures that the
internal variable keeping track of the most recent item has the correct
type.
\begin{lisp}
(defun collect-last (items \&optional (default nil)) \\*
~~(declare (optimizable-series-function)) \\*
~~(collect-fn '(series-element-type items) \\*
~~~~~~~~~~~~~~\#'(lambda () default) \\*
~~~~~~~~~~~~~~\#'(lambda (old new) new) \\*
~~~~~~~~~~~~~~items))
\end{lisp}
\end{defun}

\section{Primitives}

A large number of series functions are provided, because there are a
large number of useful operations that can be performed on series.
However, this functionality can be boiled down to a small
number of primitive constructs.

\cdf{collecting-fn} embodies the fundamental idea of series computations
that utilize internal state.  It can be used as the basis for defining any
on-line transducer.

\cdf{until} embodies the fundamental idea of producing a series that is
shorter than the shortest input series.  In particular, it embodies the
idea of computing a bounded series from non-series inputs.  Together with
\cdf{collecting-fn}, \cdf{until} can be used to define \cdf{scan-fn}, which
can be used as the basis for defining all the other scanners.

\cdf{collect-last} embodies the fundamental idea of producing a
non-series value from a series.  Together with \cdf{collecting-fn}, it
can be used to define \cdf{collect-fn}, which (with the occasional
assistance of \cdf{until}) can be used as the basis for defining all the other
collectors. 

\cdf{producing} embodies the fundamental idea of preorder computation.  It
can be used as the basis for defining all the other series functions,
including the off-line transducers.

In addition to the above, four primitives support
various specialized aspects of series functions.  Alterability is
supported by the function \cdf{to-alter} and the declaration 
\cdf{propagate-alterability}.  The propagation of type information is
supported by the type specifier \cdf{series-element-type}.  The best
implementation of certain series functions requires the form 
\cdf{encapsulated}.

\begin{defmac}
producing output-list input-list {declaration}* {form}*

\cdf{producing} computes and returns a group of series and non-series
outputs given a group of series and non-series inputs.  The key feature of
\cdf{producing} is that some or all of the series inputs and outputs can be
processed in an off-line way.  To support this, the processing in the
body (consisting of the \emph{forms}) is performed from the perspective
of generators and gatherers (see
appendix~\ref{GENERATORS}).  Each series input is converted to a generator
before being used in the body.  Each series output is associated with
a gatherer in the body.

The \emph{output-list} has the same syntax as the binding list of a 
\cdf{let}.  The names of the variables must be distinct from each other and
from the names of the variables in the \cdf{input-list}.  If there are \emph{n}
variables in the \emph{output-list}, \cdf{producing} computes \emph{n}
outputs.  There must be at least one output variable.  The variables act as
the names for the outputs and can be used in either of two ways.  First, if
an output variable has a value associated with it in the \emph{output-list},
then the variable is treated as holding a non-series value.  The variable
is initialized to the indicated value and can be used in any way desired in
the body. The eventual output value is whatever value is in the variable
when the execution of the body terminates.  Second, if an output variable
does not have a value associated with it in the \emph{output-list}, the
variable is given as its value a gatherer that collects elements.  The only
valid way to use the variable in the body is in a call on \cdf{next-out}.
The output returned is a series containing these elements.  If the body
never terminates, this series is unbounded.

The \emph{input-list} also has the same syntax as the binding list of a 
\cdf{let}.   The names of the variables must be distinct from each other and
the names of the variables in the \emph{output-list}.  The values can be
series or non-series.  If the value is not explicitly specified, it
defaults to \cdf{nil}.  The variables act logically both as inputs and
state variables and can be used in one of two ways.  First, if an input
variable is associated with a non-series value, then it is given this value
before the evaluation of the body begins and can be used in any way desired
in the body.   Second, if an input variable is associated with a series,
then the variable is given a generator corresponding to this series as its
initial value.  The only valid way to use the variable in the body is in a
call on \cdf{next-in}.

There can be declarations at the start of the body.  However,
the only declarations allowed are \cdf{ignore} declarations, type
declarations, and \cdf{propagate-alterability} declarations (see
below).  In particular, it is an error for any of the input or output
variables to be special.

In conception, the body can contain arbitrary Lisp expressions.
After the appropriate generators and gatherers have been set up, the
body is executed until it terminates.  If the body never
terminates, the series outputs (if any) are unbounded in length and
the non-series outputs (if any) are never produced.

Although easy to understand, this view of what can happen in the
body presents severe difficulties when optimizing (and even when
evaluating) series expressions that contain calls on \cdf{producing}.
As a result, several limitations are imposed on the form of the
body to simplify the processing required.

The first limitation is that, exclusive of any declarations, the
body must have the form \cd{(loop~(tagbody~...))}.  The following
example shows how \cdf{producing} could be used to implement a
scanner creating an unbounded series of integers.
\begin{lisp}
(producing (nums) ((num 0)) \\*
~~(declare (integer num) (type (series integer) nums)) \\*
~~(loop \\*
~~~~(tagbody \\*
~~~~~~(setq num (1+ num)) \\*
~~~~~~(next-out nums num)))) \\*
~~{\EV} \#Z(1 2 3 4 ...)
\end{lisp}

The second limitation is that the form \cdf{terminate-producing} must be
used to terminate the execution of the body.  Any other method of
terminating the body (with \cdf{return}, for example) is an error.
The following example shows how \cdf{producing} could be used to
implement the operation of summing a series.  The function 
\cdf{terminate-producing} is used to stop the computation when \cdf{numbers}
runs out of elements.
\begin{lisp}
(producing ((sum 0)) ((numbers \#Z(1 2 3)) num) \\* 
~~(loop \\*
~~~~(tagbody \\*
~~~~~~(setq num (next-in numbers (terminate-producing))) \\*
~~~~~~(setq sum (+ sum num))))) \\*
~~{\EV} 6
\end{lisp}

The third limitation is that calls on \cdf{next-out} associated with
output variables must appear at top level in the \cdf{tagbody} in the
body.  They cannot be nested in other forms.  In addition, an
output variable can be the destination of at most one call on 
\cdf{next-out} and if it is the destination of a \cdf{next-out}, it cannot
be used in any other way.

If the call on \cdf{next-out} for a given output appears in the
final part of the \cdf{tagbody} in the body, after everything
other than other calls on \cdf{next-out}, then the output is an
on-line output---a new value is written on every cycle of the
body.  Otherwise the output is off-line.

The following example shows how \cdf{producing} could be used to split
a series into two parts.  Items are read in one at a time and tested.
Depending on the test, they are written to one of two outputs.  Note
the use of labels and branches to keep the calls on 
\cdf{next-out} at top level.  Both outputs are off-line.  The first example
above shows an on-line output.
\begin{lisp}
(producing (items-1 items-2) ((items \#Z(1 -2 3 -4)) item) \\*
~~(loop \\*
~~~~(tagbody (setq item (next-in items (terminate-producing))) \\*
~~~~~~~~~~~~~(if (not (plusp item)) (go D)) \\*
~~~~~~~~~~~~~(next-out items-1 item) \\*
~~~~~~~~~~~~~(go F) \\*
~~~~~~D~~~~~~(next-out items-2 item) \\*
~~~~~~F~~~~~~))) \\*
~~{\EV} \#Z(1 3) {\rm and} \#Z(-2 -4)
\end{lisp}

The fourth limitation is that the calls on \cdf{next-in} associated with an
input variable \cdf{v} must appear at top level in the \cdf{tagbody} in the
body, nested in assignments of the form 
\cd{(setq~\emph{var}~(next-in~v~...))}.  They cannot be nested in other
forms.  In addition, an input variable can be the source for at most one
call on \cdf{next-in} and if it is the source for a \cdf{next-in}, it
cannot be used in any other way.

If the call on \cdf{next-in} for a given input has as its sole
termination action \cd{(terminate-producing)} and
appears in the initial part of the \cdf{tagbody} in the body,
before anything other than similar calls on \cdf{next-in}, then the
input is an on-line input---a new value is read on every cycle of the
body.  Otherwise the input is off-line.

The example below shows how \cdf{producing} could be used to
concatenate two series.  To start with, elements are read from the
first input series.  When this runs out, a flag is set and reading
begins from the second input.  Both inputs are off-line.
(Compare this to the example
above, which shows an on-line input.)
\begin{lisp}
(producing (items) ((item-1 \#Z(1 2)) \\*
~~~~~~~~~~~~~~~~~~~~(item-2 \#Z(3 4)) \\*
~~~~~~~~~~~~~~~~~~~~(in-2 nil) \\*
~~~~~~~~~~~~~~~~~~~~item) \\*
~~(loop \\*
~~~~(tagbody (if in-2 (go D)) \\*
~~~~~~~~~~~~~(setq item (next-in item-1 (setq in-2 t) (go D))) \\*
~~~~~~~~~~~~~(go F) \\*
~~~~~~D~~~~~~(setq item (next-in item-2 (terminate-producing))) \\*
~~~~~~F~~~~~~(next-out items item)))) \\*
~~{\EV} \#Z(1 2 3 4)
\end{lisp}
\end{defmac}

\begin{defmac}
terminate-producing \!!

This form (which takes no arguments) is used to terminate execution of
(the expansion of) the \cdf{producing} macro.

As with the form \cdf{go},
\cdf{terminate-producing} does not return any values; rather, control
immediately leaves the current context.

The form \cdf{terminate-producing}
is allowed to appear only in a \cdf{producing} body and causes the
termination of the enclosing call on \cdf{producing}.
\end{defmac}

\begin{defun}[Declaration specifier]
propagate-alterability

The declaration specifier
\cd{(propagate-alterability~\emph{input}~\emph{output})}
indicates that attempts to alter an element of \emph{output} should be
satisfied by altering the corresponding element of \emph{input}.    (The
corresponding element of \emph{input} is the one most recently read at the
moment when the output element is written.)

This declaration may
appear only in a call on \cdf{producing}.  The \emph{input} and \emph{output} arguments must be
an input and an output, respectively, of the \cdf{producing} macro.  The example below shows how
the propagation of alterability could be supported in a simplified version
of \cdf{until}.
\begin{lisp}
(defun simple-until (bools items) \\*
~~(declare (optimizable-series-function)) \\*
~~(producing (z) ((x bools) (y items) bool item) \\*
~~~~(declare (propagate-alterability y z)) \\*
~~~~(loop \\*
~~~~~~(tagbody \\*
~~~~~~~~(setq bool (next-in x (terminate-producing))) \\*
~~~~~~~~(setq item (next-in y (terminate-producing))) \\*
~~~~~~~~(if bool (terminate-producing)) \\*
~~~~~~~~(next-out z item)))))
\end{lisp}
\end{defun}

\begin{defmac}
encapsulated encapsulating-fn scanner-or-collector

Some of the features provided by Common Lisp are supported solely by encapsulating forms.
For example, there is no way to specify a cleanup expression that will always be run, even
when an abort occurs, without using \cdf{unwind-protect}.  \cdf{encapsulated} makes it possible
to take advantage of forms such as \cdf{unwind-protect} when defining a series function.

\cdf{encapsulated} specifies a function that places an encapsulating
form around the computation performed by its second argument.  The first argument must be a
quoted function that takes a Lisp expression and wraps the appropriate encapsulating form
around it, returning the resulting code.
The second input must be a literal call on \cdf{scan-fn}, 
\cdf{scan-fn-inclusive}, or \cdf{collect-fn}.  The second argument can count on being evaluated in the
scope of the encapsulating form.  The values returned by the second argument are returned as the
values of \cdf{encapsulated}.  The following shows how 
\cdf{encapsulated} could be used to define a simplified version of \cdf{collect-file}.
\begin{lisp}
(defun collect-file-wrap (file name body) \\*
~~`(with-open-file (,file ,name :direction :output) ,body)) \\
\\
(defmacro simple-collect-file (name items) \\*
~~(let ((file (gensym))) \\*
~~~~{\Xbq}(encapsulated \#'(lambda (body) \\*
~~~~~~~~~~~~~~~~~~~~~~~(collect-file-wrap ',file ',name body)) \\*
~~~~~~~~~~~~~~~~~~~(collect-fn t \#'(lambda () t) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\#'(lambda (state item) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(print item ,file) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~state) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~,items))))
\end{lisp}
\end{defmac}
\newpage%manual