Common Lisp the Language, 2nd Edition

Next: Generators and Gatherers Up: Series Previous: Declarations

# A.4. 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.

`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))))

Next: Generators and Gatherers Up: Series Previous: Declarations