Next: Generators and Gatherers Up: Series Previous: Declarations
Common Lisp the Language, 2nd Edition
Next: Generators and
Gatherers Up: Series
Previous: Declarations
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]
producingoutput-listinput-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)))))
=> 6The 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
(setqvar(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-alterabilityinputoutput)
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]
encapsulatedencapsulating-fnscanner-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))))
Next: Generators and
Gatherers Up: Series
Previous: Declarations
AI.Repository@cs.cmu.edu