Common Lisp the Language, 2nd Edition
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.
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.
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 collecting-fn, until can be used to define scan-fn, which can be used as the basis for defining all the other scanners.
collect-last embodies the fundamental idea of producing a non-series value from a series. Together with collecting-fn, it can be used to define collect-fn, which (with the occasional assistance of until) can be used as the basis for defining all the other collectors.
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 to-alter and the declaration propagate-alterability. The propagation of type information is supported by the type specifier series-element-type. The best implementation of certain series functions requires the form encapsulated.
[Macro]
producing output-list input-list {declaration}* {form}*
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 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 forms) is performed from the perspective of generators and gatherers (see appendix B). 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 output-list has the same syntax as the binding list of a let. The names of the variables must be distinct from each other and from the names of the variables in the input-list. If there are n variables in the output-list, producing computes 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 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 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 next-out. The output returned is a series containing these elements. If the body never terminates, this series is unbounded.
The input-list also has the same syntax as the binding list of a let. The names of the variables must be distinct from each other and the names of the variables in the output-list. The values can be series or non-series. If the value is not explicitly specified, it defaults to 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 next-in.
There can be declarations at the start of the body. However, the only declarations allowed are ignore declarations, type declarations, and 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 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 (loop (tagbody ...)). The following example shows how producing could be used to implement a scanner creating an unbounded series of integers.
(producing (nums) ((num 0))
(declare (integer num) (type (series integer) nums))
(loop
(tagbody
(setq num (1+ num))
(next-out nums num))))
=> #Z(1 2 3 4 ...)
The second limitation is that the form terminate-producing must be used to terminate the execution of the body. Any other method of terminating the body (with return, for example) is an error. The following example shows how producing could be used to implement the operation of summing a series. The function terminate-producing is used to stop the computation when numbers runs out of elements.
(producing ((sum 0)) ((numbers #Z(1 2 3)) num)
(loop
(tagbody
(setq num (next-in numbers (terminate-producing)))
(setq sum (+ sum num)))))
=> 6
The third limitation is that calls on next-out associated with output variables must appear at top level in the 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 next-out and if it is the destination of a next-out, it cannot be used in any other way.
If the call on next-out for a given output appears in the final part of the tagbody in the body, after everything other than other calls on 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 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 next-out at top level. Both outputs are off-line. The first example above shows an on-line output.
(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 )))
=> #Z(1 3) and #Z(-2 -4)
The fourth limitation is that the calls on next-in associated with an input variable v must appear at top level in the tagbody in the body, nested in assignments of the form (setq 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 next-in and if it is the source for a next-in, it cannot be used in any other way.
If the call on next-in for a given input has as its sole termination action (terminate-producing) and appears in the initial part of the tagbody in the body, before anything other than similar calls on 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 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.)
(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))))
=> #Z(1 2 3 4)
[Macro]
terminate-producing
This form (which takes no arguments) is used to terminate execution of (the expansion of) the producing macro.
As with the form go, terminate-producing does not return any values; rather, control immediately leaves the current context.
The form terminate-producing is allowed to appear only in a producing body and causes the termination of the enclosing call on producing.
[Declaration specifier]
propagate-alterability
The declaration specifier (propagate-alterability input output) indicates that attempts to alter an element of output should be satisfied by altering the corresponding element of input. (The corresponding element of 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 producing. The input and output arguments must be an input and an output, respectively, of the producing macro. The example below shows how the propagation of alterability could be supported in a simplified version of until.
(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)))))
[Macro]
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 unwind-protect. encapsulated makes it possible to take advantage of forms such as unwind-protect when defining a series function.
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 scan-fn, scan-fn-inclusive, or 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 encapsulated. The following shows how encapsulated could be used to define a simplified version of collect-file.
(defun collect-file-wrap (file name body) `(with-open-file (,file ,name :direction :output) ,body))
(defmacro simple-collect-file (name items) (let ((file (gensym))) `(encapsulated #'(lambda (body) (collect-file-wrap ',file ',name body)) (collect-fn t #'(lambda () t) #'(lambda (state item) (print item ,file) state) ,items))))
