;This is the 09/02/92 version of the on-line documentation for ;Richard C. Waters' Series macro package. ;------------------------------------------------------------------------ ;Copyright Massachusetts Institute of Technology, Cambridge, Massachusetts. ;Permission to use, copy, modify, and distribute this software and its ;documentation for any purpose and without fee is hereby granted, ;provided that this copyright and permission notice appear in all ;copies and supporting documentation, and that the name of M.I.T. not ;be used in advertising or publicity pertaining to distribution of the ;software without specific, written prior permission. M.I.T. makes no ;representations about the suitability of this software for any ;purpose. It is provided "as is" without express or implied warranty. ; M.I.T. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ; ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL ; M.I.T. BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ; ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, ; WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ; ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS ; SOFTWARE. ;------------------------------------------------------------------------ Installing Series The functions and forms discussed in this manual are defined in the package "SERIES". To make these names easily accessible, you must use the package "SERIES". The most convenient way to do this is to call the function SERIES::INSTALL, which also sets up some additional features of the series macro package. The examples in this documentation assume that the form (SERIES::INSTALL) has been evaluated. SERIES::INSTALL &key (:pkg *package*) (:macro T) (:shadow T) (:remove nil) Calling this function sets up Series for use in the package :PKG. The argument :PKG can either be a package, a package name, or a symbol whose name is the name of a package. It defaults to the current package. The package "SERIES" is used in :PKG. If :MACRO is not NIL, the # macro character syntax #Z and #M is set up. If :SHADOW is not NIL, the symbols SERIES::LET, SERIES::LET*, SERIES::MULTIPLE-VALUE-BIND, SERIES::FUNCALL, and SERIES::DEFUN are shadowing imported into :PKG. These forms are identical to their standard counterparts, except that they support various features of the Series macro package. When shadowing is not done, you have to explicitly use SERIES::LET, SERIES::LET*, and SERIES::MULTIPLE-VALUE-BIND when binding series in an expression you want optimized; SERIES::FUNCALL when funcalling a series function you want optimized; and SERIES::DEFUN when defining a series function with the declaration OPTIMIZABLE-SERIES-FUNCTION. If :REMOVE is not NIL, the effects of having previously installed the Series macro package are undone. In particular, the package is unused and any shadowing is undone. However, any changes to the readtable are left in place. The Series Macro Package 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. (COLLECT-SUM (CHOOSE-IF #'PLUSP (SCAN '(1 -2 3 -4)))) => 4 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 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. (LET ((X (SUBSERIES (SCAN-RANGE :FROM 0 :BY 2) 0 5))) (VALUES (COLLECT X) (COLLECT-SUM X))) => (0 2 4 6 8) and 20 Like sequences and unlike streams, the act of accessing the elements of a series does not alter the series. For instance, both users of 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. (LET ((SUM 0)) (DOLIST (I '(1 -2 3 -4) SUM) (IF (PLUSP I) (SETQ SUM (+ SUM I))))) => 4 A wide variety of algorithms can be expressed clearly and succinctly using 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 LOOP clauses, and the vector operations of APL. Unfortunately, some series expressions cannot be transformed into loops. This matters, 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. Based on the information in the message, it is usually easy to provide an efficient fix for the problem. 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 to simply 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. Series Functions Throughout this chapter the notation S[j] is used to denote the jth element of the series S. As in a list or vector, the first element of a series has the subscript zero. The # macro character syntax #Z(...) denotes a series that contains the elements of LIST. This syntax is also used when printing series. (CHOOSE-IF #'SYMBOLP #Z(A 2 B)) => #Z(A B) Series are self-evaluating objects and the series data type is disjoint from all other types. SERIES [Type specifier] The type specifier (SERIES ELEMENT-TYPE) denotes the set of series whose elements are all members of the type ELEMENT-TYPE. SERIES ARG &rest ARGS [Function] The function 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. (SERIES 'B 'C) => #Z(B C B C B C ...) (SCAN (LIST 'A 'B 'C)) => #Z(A B C) Scanners Scanners create series outputs based on non-series inputs. They either operate based on some formula (for example, scanning a range of integers) or enumerate the elements in an aggregate data structure (for example, scanning the elements in a list). SCAN-RANGE &key (:START 0) (:BY 1) (:TYPE 'NUMBER) [Function] :UPTO :BELOW :DOWNTO :ABOVE :LENGTH The function SCAN-RANGE returns a series of numbers starting with the :START argument (default integer 0) and counting up by the :BY argument (default integer 1). The :TYPE argument (default NUMBER) is a type specifier indicating the type of numbers in the series produced. The :TYPE argument must be a (not necessarily proper) subtype of NUMBER. The :START and :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 TERMINATION ARGUMENTS. If :UPTO is specified, counting continues only so long as the numbers generated are less than or equal to :UPTO. If :BELOW is specified, counting continues only so long as the numbers generated are less than :BELOW. If :DOWNTO is specified, counting continues only so long as the numbers generated are greater than or equal to :DOWNTO. If :ABOVE is specified, counting continues only so long as the numbers generated are greater than :ABOVE. If :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. (SCAN-RANGE :UPTO 4) => #Z(0 1 2 3 4) (SCAN-RANGE :FROM 1 :BY -1 :ABOVE -4) => #Z(1 0 -1 -2 -3) (SCAN-RANGE :FROM .5 :BY .1 :TYPE 'FLOAT) => #Z(.5 .6 .7 ...) (SCAN-RANGE) => #Z(0 1 2 3 4 5 6 ...) SCAN {TYPE} SEQUENCE [Function] SCAN returns a series containing the elements of SEQUENCE in order. The TYPE argument is a type specifier indicating the type of sequence to be scanned; it must be a (not necessarily proper) subtype of SEQUENCE. If TYPE is omitted, it defaults to LIST. If the SEQUENCE is a list, it must be a proper list ending in NIL. Scanning is significantly more efficient if it can be determined at compile time whether TYPE is a subtype of LIST or VECTOR and for vectors what the length of the vector is. (SCAN '(A B C)) => #Z(A B C) (SCAN 'STRING "BAR") => #Z(#\B #\A #\R) SCAN-SUBLISTS LIST [Function] SCAN-SUBLISTS returns a series containing the successive sublists of LIST. The LIST must be a proper list ending in NIL. (SCAN-SUBLISTS '(A B C)) => #Z((A B C) (B C) (C)) SCAN-MULTIPLE TYPE FIRST-SEQUENCE &rest MORE-SEQUENCES [Function] Several sequences can be scanned at once by using several calls on SCAN. Each call on 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 a significant source of inefficiency. In situations where it is known in advance which sequence is the shortest, SCAN-MULTIPLE can be used to obtain the same results more rapidly. SCAN-MULTIPLE is similar to SCAN except that several sequences can be scanned at once. If there are N sequence inputs, SCAN-MULTIPLE returns 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 SCAN-MULTIPLE is more efficient than using multiple instances of SCAN, because SCAN-MULTIPLE only has to check for the first input running out of elements. If TYPE is of the form (VALUES t1 ... tm), then there must be M sequence inputs and the ith sequence must have type ti. Otherwise there can be any number of sequence inputs, each of which must have type TYPE. (MULTIPLE-VALUE-BIND (DATA WEIGHTS) (SCAN-MULTIPLE 'LIST '(1 6 3 2 8) '(2 3 3 3 2)) (COLLECT (MAP-FN T #'* DATA WEIGHTS))) => (2 18 9 6 16) SCAN-LISTS-OF-LISTS LISTS-OF-LISTS &optional LEAF-TEST [Function] SCAN-LISTS-OF-LISTS-FRINGE LISTS-OF-LISTS &optional LEAF-TEST [Function] The argument LISTS-OF-LISTS is viewed as an n-ary tree where each internal node is a non-empty list and the elements of the list are the children of the node. SCAN-LISTS-OF-LISTS and SCAN-LISTS-OF-LISTS-FRINGE each scan LISTS-OF-LISTS in preorder and return a series of its nodes. SCAN-LISTS-OF-LISTS returns every node in the tree. SCAN-LISTS-OF-LISTS-FRINGE returns only the leaf nodes. The scan proceeds as follows. The argument LISTS-OF-LISTS can be any Lisp object. If LISTS-OF-LISTS is an atom or satisfies the predicate LEAF-TEST (if present), it is a leaf node. (The predicate can count on only being applied to conses.) Otherwise, LISTS-OF-LISTS is a (not necessarily proper) list. The first element of LISTS-OF-LISTS is recursively scanned in full, followed by the second and so on until a non-cons cdr is encountered. Whether or not this final cdr is NIL, it is ignored. (SCAN-LISTS-OF-LISTS '((2) (NIL))) => #Z(((2) (NIL)) (2) 2 (NIL) NIL) (SCAN-LISTS-OF-LISTS-FRINGE '((2) (NIL))) => #Z(2 NIL) (SCAN-LISTS-OF-LISTS-FRINGE '((2) (NIL)) #'(LAMBDA (E) (NUMBERP (CAR E)))) => #Z((2) NIL) SCAN-ALIST ALIST &optional (TEST #'EQL) [Function] SCAN-PLIST PLIST [Function] SCAN-HASH TABLE [Function] When given an association list, a property list, or a hash table (respectively), each of these functions produces two outputs: a series of keys K and a series of the corresponding values V. Each key in the input appears exactly once in the output, even if it appears more than once in the input. (The TEST argument of SCAN-ALIST specifies the equality test between keys; it defaults to EQL.) The two outputs have the same length. Each V[j] is the value returned by the appropriate accessing function (CDR-of-ASSOC, GETF, or GETHASH, respectively) when given K[j]. SCAN-ALIST and SCAN-PLIST scan keys in the order they appear in the underlying structure. SCAN-HASH scans keys in no particular order. (SCAN-PLIST '(A 1 B 3)) => #Z(A B) AND #Z(1 3) (SCAN-ALIST '((A . 1) NIL (A . 3) (B . 2))) => #Z(A B) AND #Z(1 2) SCAN-SYMBOLS &optional (PACKAGE *PACKAGE*) [Function] SCAN-SYMBOLS returns a series, in no particular order, and possibly containing duplicates, of the symbols accessible in PACKAGE (which defaults to the current package). SCAN-FILE FILE-NAME &optional (READER #'READ) [Function] SCAN-STREAM STREAM &optional (READER #'READ) [Function] SCAN-FILE opens the file named by the string FILE-NAME and applies the function READER to it repeatedly until the end of the file is reached. READER must accept the standard input function arguments INPUT-STREAM, EOF-ERROR-P, and EOF-VALUE as its arguments. (For instance, READER can be READ, READ-PRESERVING-WHITE-SPACE, READ-LINE, or READ-CHAR.) If omitted, READER defaults to READ. SCAN-FILE returns a series of the values returned by 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. SCAN-STREAM is like SCAN-FILE, except an open stream is given instead of a file name. This works around a defect in SCAN-FILE where additional options to OPEN cannot be specified. SCAN-FN TYPE INIT STEP &optional TEST [Function] The higher-order function SCAN-FN supports the general concept of scanning. The TYPE argument is a type specifier, which specifies the type of values returned by INIT and STEP. The VALUES type specifier can be used for this argument to indicate multiple types; however, TYPE cannot indicate zero values. If TYPE indicates M types t1, ..., tm, then SCAN-FN returns M series T1, ..., TM where TI has the type (SERIES ti). The arguments INIT, STEP, and TEST are functions. The INIT must be of type (FUNCTION () (VALUES t1 ... tm)). The STEP must be of type (FUNCTION (t1 ... tm) (VALUES t1 ... tm)). The TEST (if present) must be of type (FUNCTION (t1 ... tm) T). The elements of the TI are computed as follows: (VALUES T1[0] ... TM[0]) = (FUNCALL INIT) (VALUES T1[j] ... TM[j]) = (FUNCALL STEP T1[j-1] ... TM[j-1]) The outputs all have the same length. If there is no TEST, the outputs have unbounded length. If there is a TEST, the outputs consist of the elements up to, but not including, the first elements (with index J, say) for which the following termination test is not NIL. (FUNCALL TEST T1[j] ... TM[j]) It is guaranteed that STEP will not be applied to the elements that pass this termination test. If any of INIT, STEP, and TEST have side effects when invoked, they can count on being called in the order indicated by the equations above, with TEST called just before STEP on each cycle. However, due to 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 I integers. (SCAN-FN T #'(LAMBDA () '(A B C D)) #'CDDR #'NULL) => #Z((A B C D) (C D)) (SCAN-FN '(VALUES INTEGER INTEGER) #'(LAMBDA () (VALUES 1 0)) #'(LAMBDA (I SUM) (VALUES (+ I 1) (+ SUM I)))) => #Z(1 2 3 4 ...) AND #Z(0 1 3 6 ...) SCAN-FN-INCLUSIVE TYPE INIT STEP TEST [Function] The higher-order function SCAN-FN-INCLUSIVE is the same as SCAN-FN except that the first set of elements for which TEST returns a non-null value is included in the output. As with SCAN-FN, it is guaranteed that STEP will not be applied to the elements for which TEST is non-null. 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 (MAP-FN) and three shorthand forms that are more convenient in particular common situations. MAP-FN TYPE FUNCTION &rest SERIES-INPUTS [Function] The higher-order function MAP-FN supports the general concept of mapping. The TYPE argument is a type specifier, which specifies the type of values returned by FUNCTION. The VALUES construct can be used to indicate multiple types; however, TYPE cannot indicate zero values. If TYPE indicates M types t1, ..., tm, then MAP-FN returns M series T1, ..., TM where TI has the type (SERIES ti). The argument FUNCTION is a function. The remaining arguments (if any) are all series. Let these series be S1, ..., SN and suppose that SI has the type (SERIES si). The FUNCTION must be of type (FUNCTION (s1 ... sn) (VALUES t1 ... tm)) 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 TI are the results of applying FUNCTION to the corresponding elements of the series inputs. (VALUES T1[j] ... TM[j]) = (FUNCALL FUNCTION S1[j] ... SN[j]) If FUNCTION has side effects, it can count on being called first on the SI[0], then on the SI[1], and so on. However, due to the lazy evaluation nature of series, 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 FUNCTION with regard to execution in other parts of a given series expression. (MAP-FN 'INTEGER #'+ #Z(1 2 3) #Z(4 5)) => #Z(5 7) (MAP-FN T #'GENSYM) => #Z(#:G3 #:G4 #:G5 ...) (MAP-FN '(VALUES INTEGER RATIONAL) #'FLOOR #Z(1/4 9/5 12/3)) => #Z(0 1 4) AND #Z(1/4 4/5 0) The # macro character syntax #M makes it easy to specify uses of MAP-FN where TYPE is T and the FUNCTION is a named function. The notation (#MFUNCTION ...) is an abbreviation for (MAP-FN T #'FUNCTION ...). The form FUNCTION can be the printed representation of any Lisp object. The notation #MFUNCTION can only appear in the function position of a list. (COLLECT (#M1+ (SCAN '(1 2 3)))) => (2 3 4) MAPPING ({({VAR | ({VAR}*)} VALUE)}*) {DECLARATION}* {FORM}* [Macro] The macro mapping makes it easy to specify uses of map-fn where TYPE is T and the function a literal LAMBDA. The syntax of mapping is analogous to that of LET. The binding list specifies zero or more variables that are bound in parallel to successive values of series. The VALUE part of each pair is an expression that must produce a series. The DECLARATIONS and FORMS are treated as the body of a LAMBDA expression that is mapped over the series values. A series of the first values returned by this LAMBDA expression is returned as the result of MAPPING. (MAPPING ((X R) (Y S)) ...) == (MAP-FN T #'(LAMBDA (X Y) ...) R S) (MAPPING ((X (SCAN '(2 -2 3)))) (EXPT (ABS X) 3)) => #Z(8 8 27) The form 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 var-value-pair can be a list of variables. This list is treated the same way as the first argument to MULTIPLE-VALUE-BIND and can be used to access the elements of multiple series returned by a series function. (MAPPING (((I V) (SCAN-PLIST '(A 1 B 2)))) (LIST I V)) => #Z((A 1) (B 2)) ITERATE ({({VAR | ({VAR}*)} VALUE)}*) {DECLARATION}* {FORM}* [Macro] The form ITERATE is the same as MAPPING, except that after mapping the FORMS over the VALUES, the results are discarded and NIL is returned. (LET ((ITEM (SCAN '((1) (-2) (3))))) (ITERATE ((X (#MCAR ITEM))) (IF (PLUSP X) (PRIN1 X)))) => NIL (after printing ``13'') To a first approximation, ITERATE and MAPPING differ in the same way as MAPC and MAPCAR. In particular, like MAPC, ITERATE is intended to be used in situations where the FORMS are being evaluated for side effect rather than their results. However, due to the lazy evaluation semantics of series, the difference between ITERATE and MAPPING is more than just a question of efficiency. If MAPCAR is used in a situation where the output is not used, time is wasted unnecessarily creating the output list. However, if 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 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. 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. COTRUNCATE &rest SERIES-INPUTS [Function] UNTIL BOOLS &rest SERIES-INPUTS [Function] UNTIL-IF PRED &rest SERIES-INPUTS [Function] Each of these functions accepts one or more series inputs S1, ..., SN as its &REST argument and returns N series outputs T1, ..., TN that contain the same elements in the same order---that is, TI[j]=SI[j]. Let K be the length of the shortest input SI. COTRUNCATE truncates the series so that each output has length K. Let K' be the position of the first element in the boolean series BOOLS that is not NIL or, if every element is NIL, the length of BOOLS. UNTIL truncates the series so that each output has length (MIN K K'). Let K'' be the position of the first element in S1 such that (PRED S1[K'']) is not NIL or, if there is no such element, the length of S1. UNTIL-IF truncates the series so that each output has length (MIN K K''). (COTRUNCATE #Z(1 2 -3 4) #Z(A B C)) => #Z(1 2 -3) and #Z(A B C) (UNTIL #Z(NIL NIL T NIL) #Z(1 2 -3 4) #Z(A B C)) => #Z(1 2) and #Z(A B) (UNTIL-IF #'MINUSP #Z(1 2 -3 4) #Z(A B C)) => #Z(1 2) and #Z(A B) PREVIOUS ITEMS &optional (DEFAULT NIL) (AMOUNT 1) [Function] The series returned by PREVIOUS is the same as the input series ITEMS except that it is shifted to the right by the positive integer AMOUNT. The shifting is done by inserting AMOUNT copies of DEFAULT before ITEMS and discarding AMOUNT elements from the end of ITEMS. (PREVIOUS #Z(10 11 12) 0) => #Z(0 10 11) LATCH ITEMS &key :AFTER :BEFORE :PRE :POST [Function] The series returned by LATCH is the same as the input series ITEMS except that some of the elements are replaced by other values. LATCH acts like a 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 :AFTER and :BEFORE arguments specify the latch point. The latch point is just after the :AFTER-th non-null element in ITEMS or just before the :BEFORE-th non-null element. If neither :AFTER nor :BEFORE is specified, an :AFTER of 1 is assumed. If both are specified, it is an error. If a :PRE is specified, every element prior to the latch point is replaced by this value. If a :POST is specified, every element after the latch point is replaced by this value. If neither is specified, a :POST of NIL is assumed. (LATCH #Z(NIL C NIL D E)) => #Z(NIL C NIL NIL NIL) (LATCH #Z(NIL C NIL D E) :BEFORE 2 :POST T) => #Z(NIL C NIL T T) COLLECTING-FN TYPE INIT FUNCTION &rest SERIES-INPUTS [Function] The higher-order function COLLECTING-FN supports the general concept of a simple transducer with internal state. The TYPE argument is a type specifier, which specifies the type of values returned by FUNCTION. The VALUES construct can be used to indicate multiple types; however, TYPE cannot indicate zero values. If TYPE indicates M types t1, ..., tm, then COLLECTING-FN returns M series T1, ..., TM where TI has the type (SERIES ti). The arguments INIT and FUNCTION are functions. The remaining arguments (if any) are all series. Let these series be S1, ..., SN and suppose that SI has the type (SERIES si). The INIT must be of type (FUNCTION () (VALUES t1 ... tm)). The FUNCTION must be of type (FUNCTION (t1 ... tm s1 ... sn) (VALUES t1 ... tm)) 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 TI are computed as follows: (VALUES T1[0] ... TM[0]) = (MULTIPLE-VALUE-CALL FUNCTION (FUNCALL INIT) S1[0] ... SN[0]) (VALUES T1[j] ... TM[j]) = (FUNCALL FUNCTION T1[j-1] ... TM[j-1] S1[j] ... SN[j]) If INIT and/or FUNCTION have side effects, they can count on being called in the order indicated by the equations above. However, due to 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 computes a series of partial sums of the numbers in an input series. The second example computes two output series: the partial sums of its first input and the partial products of its second input. (COLLECTING-FN 'INTEGER #'(LAMBDA () 0) #'+ #Z(1 2 3)) => #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)) => #Z(4 10 18) AND #Z(1 2 6) Conditional and Other Complex Transducers This section presents a number of complex transducers, including ones that support conditional computation. CHOOSE BOOLS &optional (ITEMS BOOLS) [Function] CHOOSE-IF PRED ITEMS [Function] Each of these functions takes in a series of elements (ITEMS) and returns a series containing the same elements in the same order, but with some elements removed. CHOOSE removes ITEMS[j] if BOOLS[j] is NIL or J is beyond the end of BOOLS. If ITEMS is omitted, CHOOSE returns the non-null elements of BOOLS. CHOOSE-IF removes ITEMS[j] if (PRED ITEMS[j]) is NIL. (CHOOSE #Z(T NIL T NIL) #Z(A B C D)) => #Z(A C) (COLLECT-SUM (CHOOSE-IF #'PLUSP #Z(-1 2 -3 4))) => 6 EXPAND BOOLS ITEMS &optional (DEFAULT NIL) [Function] EXPAND is a quasi-inverse of CHOOSE. The output contains the elements of the input series ITEMS spread out into the positions specified by the non-null elements in BOOLS---that is, ITEMS[j] is in the position occupied by the jth non-null element in BOOLS. The other positions in the output are occupied by DEFAULT. The output stops as soon as BOOLS runs out of elements or a non-null element in BOOLS is encountered for which there is no corresponding element in ITEMS. (EXPAND #Z(NIL T NIL T T) #Z(A B C)) => #Z(NIL A NIL B C) (EXPAND #Z(NIL T NIL T T) #Z(A)) => #Z(NIL A NIL) SPREAD GAPS ITEMS &optional (DEFAULT NIL) [Function] SPREAD is quite similar to EXPAND, except instead of giving booleans on where to put the items, GAPS are specified which indicate how far apart the items should be. A gap of 0 means the items will be adjacent. (SPREAD #Z(1 1 1) #Z(A B C)) -> #Z(NIL A NIL B NIL C) (SPREAD #z(0 2 3) #z(A B C)) -> #Z(A NIL NIL B NIL NIL NIL C) SPLIT ITEMS &rest TEST-SERIES-INPUTS [Function] SPLIT-IF ITEMS &rest TEST-PREDICATES [Function] These functions are like CHOOSE and CHOOSE-IF except that instead of producing one restricted output, they partition the input series ITEMS between several outputs. If there are N test inputs following ITEMS, then there are 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 ITEMS[j] fails the first K-1 tests and passes the kth test, it is put in the kth output. If ITEMS[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 SPLIT are series of values; ITEMS[j] passes the kth test if the jth element of the kth test-series is not NIL. The test inputs to SPLIT-IF are predicates; ITEMS[j] passes the kth test if the kth test predicate returns non-null when applied to ITEMS[j]. (SPLIT #Z(-1 2 3 -4) #Z(T NIL NIL T)) => #Z(-1 -4) and #Z(2 3) (MULTIPLE-VALUE-BIND (+X -X) (SPLIT-IF #Z(-1 2 3 -4) #'PLUSP) (VALUES (COLLECT-SUM +X) (COLLECT-SUM -X))) => 5 and -5 CATENATE &rest SERIES-INPUTS [Function] 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. (CATENATE #Z(B C) #Z() #Z(D)) => #Z(B C D) SUBSERIES ITEMS START &optional BELOW [Function] SUBSERIES returns a series containing the elements of the input series ITEMS indexed by the non-negative integers from START up to, but not including, BELOW. If BELOW is omitted or greater than the length of ITEMS, the output goes all of the way to the end of ITEMS. (SUBSERIES #Z(A B C D) 1) => #Z(B C D) (SUBSERIES #Z(A B C D) 1 3) => #Z(B C) POSITIONS BOOLS [Function] POSITIONS returns a series of the indices of the non-null elements in the series input BOOLS. (POSITIONS #Z(T NIL T 44)) => #Z(0 2 3) MASK MONOTONIC-INDICES [Function] MASK is a quasi-inverse of POSITIONS. The series input MONOTONIC-INDICES must be a strictly increasing series of non-negative integers. The output, which is always unbounded, contains T in the positions specified by MONOTONIC-INDICES and NIL everywhere else. (MASK #Z()) => #Z(NIL NIL ...) (MASK #Z(0 2 3)) => #Z(T NIL T T NIL NIL ...) (MASK (POSITIONS #Z(NIL A NIL B NIL))) => #Z(NIL T NIL T NIL ...) MINGLE ITEMS1 ITEMS2 COMPARATOR [Function] The series returned by 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 COMPARATOR. The 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 COMPARATOR is used to compare the current elements in the two series. If the current element from ITEMS2 is strictly less than the current element from ITEMS1, the current element is removed from ITEMS2 and transferred to the output. Otherwise, the next output element comes from ITEMS1. (MINGLE #Z(1 3 7 9) #Z(4 5 8) #'<) => #Z(1 3 4 5 7 8 9) (MINGLE #Z(1 7 3 9) #Z(4 5 8) #'<) => #Z(1 4 5 7 3 8 9) CHUNK M N ITEMS [Function] This function has the effect of breaking up the input series ITEMS into (possibly overlapping) chunks of length M. The starting positions of successive chunks differ by N. The inputs M and N must both be positive integers. CHUNK produces M output series. The ith chunk consists of the ith elements of the M outputs. Suppose that the length of ITEMS is L. The length of each output is the floor of 1+(L-M)/N. The ith element of the kth output is the (i*n+k)th element of ITEMS (i and k counting from zero). The first example below shows CHUNK being used to compute a moving average. The second example shows CHUNK being used to convert a property list into an association list. (MAPPING (((XI XI+1 XI+2) (CHUNK 3 1 #Z(1 5 3 4 5 6)))) (/ (+ XI XI+1 XI+2) 3)) => #Z(3 4 4 5) (COLLECT (MAPPING (((PROP VAL) (CHUNK 2 2 (SCAN '(A 2 B 5 C 8))))) (CONS PROP VAL))) => ((A . 2) (B . 5) (C . 8)) 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). COLLECT-FIRST ITEMS &optional (DEFAULT NIL) [Function] COLLECT-LAST ITEMS &optional (DEFAULT NIL) [Function] COLLECT-NTH N ITEMS &optional (DEFAULT NIL) [Function] Given a series ITEMS, these functions return the first element, the last element, and the Nth element, respectively. If ITEMS has no elements (or no Nth element), DEFAULT is returned. If DEFAULT is not specified, then NIL is used for DEFAULT. (COLLECT-FIRST #Z() 'Z) => Z (COLLECT-LAST #Z(A B C)) => C (COLLECT-NTH 1 #Z(A B C)) => B COLLECT-LENGTH ITEMS [Function] COLLECT-LENGTH returns the number of elements in a series. (COLLECT-LENGTH #Z(A B C)) => 3 COLLECT-SUM NUMBERS &optional (TYPE 'NUMBER) [Function] COLLECT-SUM returns the sum of the elements in a series of numbers. The TYPE is a type specifier that indicates the type of sum to be created. If TYPE is not specified, then NUMBER is used for the TYPE. If there are no elements in the input, a zero (of the appropriate type) is returned. (COLLECT-SUM #Z(1.1 1.2 1.3)) => 3.6 (COLLECT-SUM #Z() 'COMPLEX) => #C(0 0) COLLECT-PRODUCT NUMBERS &optional (TYPE 'NUMBER) [Function] COLLECT-PRODUCT returns the product of the elements in a series of numbers. The TYPE is a type specifier that indicates the type of sum to be created. If TYPE is not specified, then NUMBER is used for the TYPE. If there are no elements in the input, one (of the appropriate type) is returned. (COLLECT-PRODUCT #Z(1.1 1.2 1.3)) => 1.716 (COLLECT-PRODUCT #Z() 'FLOAT) => 1.0 COLLECT-MAX NUMBERS &optional (ITEMS NUMBERS) (DEFAULT NIL) [Function] COLLECT-MIN NUMBERS &optional (ITEMS NUMBERS) (DEFAULT NIL) [Function] Given a series of non-complex numbers, these functions returns the element of ITEMS that corresponds to the maximum element and the minimum element of NUMBERS, respectively. If ITEMS is omitted, the the maximum or minimum of NUMBERS itself is returned. If there are no elements in the input, DEFAULT is returned. (COLLECT-MAX #Z(2 1 4 3)) => 4 (COLLECT-MIN #Z(1.2 1.1 1.4 1.3)) => 1.1 (COLLECT-MIN #Z()) => NIL COLLECT-AND BOOLS [Function] COLLECT-AND returns the AND of the elements in a series. As with the macro AND, NIL is returned if any element of BOOLS is NIL. Otherwise, the last element of BOOLS is returned. The value T is returned if there are no elements in BOOLS. (COLLECT-AND #Z(A B C)) => C (COLLECT-AND #Z(A NIL C)) => NIL COLLECT-OR BOOLS [Function] COLLECT-OR returns the OR of the elements in a series. As with the macro OR, NIL is returned if every element of BOOLS is NIL. Otherwise, the first non-null element of BOOLS is returned. The value NIL is returned if there are no elements in BOOLS. (COLLECT-OR #Z(NIL B C)) => B (COLLECT-OR #Z()) => NIL COLLECT ITEMS [Function] COLLECT TYPE ITEMS [Function] COLLECT returns a sequence containing the elements of the series ITEMS. The TYPE is a type specifier indicating the type of sequence to be created. It must be either a proper subtype of SEQUENCE or the symbol BAG. If TYPE is omitted, it defaults to 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 &OPTIONAL. It is indicated above by two definition lines, showing the two possible argument patterns.) If the TYPE is 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 ITEMS. If TYPE specifies a length (that is, of a vector) this length must be greater than or equal to the length of ITEMS. The nth element of ITEMS is placed in the nth 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 TYPE is a subtype of LIST or VECTOR and for vectors what the length of the vector is. (COLLECT #Z(A B C)) => (A B C) (COLLECT 'BAG #Z(A B C)) => (C A B) or (B A C) or ... (COLLECT '(VECTOR INTEGER 3) #Z(1 2 3)) => #(1 2 3) COLLECT-APPEND SEQUENCES [Function] COLLECT-APPEND TYPE SEQUENCES [Function] Given a series of sequences, COLLECT-APPEND returns a new sequence by concatenating these sequences together in order. The TYPE is a type specifier indicating the type of sequence created and must be a proper subtype of SEQUENCE. If TYPE is omitted, it defaults to 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 &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 TYPE. The result does not share any structure with the sequences in the input. (COLLECT-APPEND #Z((A B) NIL (C D))) => (A B C D) (COLLECT-APPEND 'STRING #Z("A " "BIG " "CAT")) => "A BIG CAT" COLLECT-IGNORE LISTS [Function] Like COLLECT, but any results that would have been returned are discarded. This also means the results are not consed. COLLECT-NCONC LISTS [Function] COLLECT-NCONC NCONCs the elements of the series LISTS together in order and returns the result. This is the same as 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. COLLECT-ALIST KEYS VALUES [Function] COLLECT-PLIST KEYS VALUES [Function] COLLECT-HASH KEYS VALUES &key :TEST :SIZE :REHASH-SIZE [Function] :REHASH-THRESHOLD 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 KEYS[j]/VALUES[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 COLLECT-HASH specify attributes of the hash table produced and have the same meanings as the arguments to MAKE-HASH-TABLE. (COLLECT-ALIST #Z(A B C) #Z(1 2)) => ((B . 2) (A . 1)) (COLLECT-HASH #Z() #Z(1 2) :TEST #'EQ) => COLLECT-FILE FILE-NAME ITEMS &optional (PRINTER #'PRINT) [Function] COLLECT-STREAM STREAM ITEMS &optional (PRINTER #'PRINT) [Function] This creates a file named FILE-NAME and writes the elements of the series ITEMS into it using the function PRINTER. PRINTER must accept two inputs: an object and an output stream. (For instance, PRINTER can be PRINT, PRIN1, PRINC, PPRINT, WRITE-CHAR, WRITE-STRING, or WRITE-LINE.) If omitted, PRINTER defaults to PRINT. The value T is returned. The file is correctly closed, even if an abort occurs. COLLECT-STREAM is idential to COLLECT-FILE, except an already open stream is used instead of creating a new file. COLLECT-FN TYPE INIT FUNCTION &rest SERIES-INPUTS [Function] The higher-order function COLLECT-FN supports the general concept of collecting. It is identical to COLLECTING-FN except that it only returns the last element of each series computed. If there are no elements in these series, the values returned by INIT are passed on directly as the output of COLLECT-FN. (COLLECT-FN 'INTEGER #'(LAMBDA () 0) #'+ #Z(1 2 3)) => 6 (COLLECT-FN 'INTEGER #'(LAMBDA () 0) #'+ #Z()) => 0 Alteration of Series Series that come from scanning data structures such as lists and vectors are closely linked to these structures. The function 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.) ALTER DESTINATIONS ITEMS [Function] ALTER changes the series DESTINATIONS so that it contains the elements in the series ITEMS. More importantly, in the manner of SETF, the data structure that underlies DESTINATIONS is changed so that if the series 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 NIL is always returned. In the example below each negative element in a list is replaced with its square. (LET* ((DATA (LIST 1 -2 3 4 -5 6)) (X (CHOOSE-IF #'MINUSP (SCAN DATA)))) (ALTER X (#M* X X)) DATA) => (1 4 3 4 25 6) ALTER can only be applied to series that are ALTERABLE. SCAN, SCAN-ALIST, SCAN-MULTIPLE, SCAN-PLIST, and SCAN-LISTS-OF-LISTS-FRINGE produce alterable series. However, the alterability of the output of SCAN-LISTS-OF-LISTS-FRINGE is incomplete. If 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 CHOOSE, CHOOSE-IF, SPLIT, SPLIT-IF, COTRUNCATE, UNTIL, UNTIL-IF, and SUBSERIES are alterable as long as the corresponding inputs are alterable. TO-ALTER ITEMS ALTER-FN &rest ARGS [Function] Given a series ITEMS, TO-ALTER returns an alterable series A containing the same elements. The argument ALTER-FN is a function. The remaining arguments are all series. Let these series be S1, ..., SN. If there are N arguments after ALTER-FN, ALTER-FN must accept N+1 inputs. If (ALTER A B) is later encountered, (MAP-FN T ALTER-FN B S1 ... SN) is implicitly evaluated. For each element in B, ALTER-FN should make appropriate changes in the data structure underlying 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. (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))) Optimization 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 looking at these restrictions, it is useful to consider a related issue. The composition of two series functions cannot be pipelined unless the destination function consumes series elements in the same order that the source function produces them. Taken together, the series functions guarantee that this will always be true, because they all follow the same fixed processing order. In particular, they are all `preorder' functions---they process the elements of their series inputs and outputs in ascending order starting with the first element. Further, while it is easy for users to define new series functions, it is impossible to define one that is not preorder. 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.) 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. *SUPPRESS-SERIES-WARNINGS* [Variable] If this variable is set (or bound) to anything other than its default value of NIL, warnings about conditions that block the optimization of series expressions are suppressed. Before discussing the restrictions on series expressions, it is useful to define precisely what is meant by the term SERIES EXPRESSION. This term is semantic rather than syntactic in nature. Given a program, imagine it 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 LET and SETQ are converted into patterns of data flow arcs. Control constructs such as IF and 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 F on a series function, the series expression E containing it is defined as follows. E contains F. Every function using a series created by a function in E is in E. Every function computing a series used by a function in E is in E. Finally, suppose that two functions G and H are in E and that there is a data flow path consisting of series and/or non-series data flow arcs from G to H. Every function touched by this path (be it a series function or not) is in E. 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 MAP-FN and COLLECTING-FN have to be quoted constants. Similarly, the numeric arguments to CHUNK have to be constants. In addition, if FUNCALL is used to call a series function, the function called has to be of the form (FUNCTION ...). 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 expressions 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 &REST arguments. Further, optimization is blocked if a series is passed as an argument to an ordinary Lisp function. Series can only be passed to the predefined series functions and to new series functions defined using the declaration OPTIMIZABLE-SERIES-FUNCTION. 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 PROGN, FUNCALL, SETQ, LAMBDA, LET, LET*, and MULTIPLE-VALUE-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 IF, COND, etc., looping constructs LOOP, DO, etc., or branching constructs TAGBODY, GO, CATCH, etc.). In the first example below, optimization is blocked, because the IF form is inside of the series expression. However, in the second example, optimization is possible, because although the IF feeds data to the series expression, it is not inside the corresponding subgraph. Both of the expressions below produce the same value, however, the second one is much more efficient. (COLLECT (IF FLAG (SCAN X) (SCAN Y))) ;warning message issued (COLLECT (SCAN (IF FLAG X Y))) 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 X of the elements in a list. It then creates a normalized series by dividing each element of X by the sum of the elements in X. Finally, the expression returns the maximum of the normalized elements. (LET ((X (SCAN '(1 2 5 2)))) ; warning message issued (COLLECT-MAX (#M/ X (SERIES (COLLECT-SUM X))))) => 1/2 The two uses of X in the expression place contradictory constraints on the way pipelined evaluation must proceed. COLLECT-SUM requires that all of the elements of X be produced before the sum can be returned and SERIES requires that its input be available before it can start to produce its output. However, #M/ requires that the first element of X be available at the same time as the first element of the output of SERIES. For pipelining to work, this implies that the first element of the output of SERIES (and therefore the output of COLLECT-SUM) must be available before the second element of 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 (see Figure 1). In Figure 1, 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. |------| /------------------------------->|-------| |------| -| scan |--- |------| |------| | #M/ |----->| max |- |------| \--->| sum |+++++>|series|----->|-------| |------| |------| |------| Figure 1: A Constraint Cycle in a Series Expression Given a data flow graph corresponding to a series expression, a CONSTRAINT CYCLE is a closed loop of data flow arcs that can be traversed in such a way that each arc is traversed exactly once and no non-series arc is traversed backwards. (Series data flow arcs can be traversed in either direction.) A constraint cycle is said to PASS THROUGH an input or output port when exactly one of the arcs in the cycle touches the port. In Figure 1, the data flow arcs touching SCAN, SUM, SERIES, and #M/ form a constraint cycle. Note that if the output of 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 SCAN. Whenever a constraint cycle passes through a non-series output, an argument analogous to the one above can be constructed and therefore pipelining is 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 SCAN, COLLECT-SUM, SERIES, and #M/ passes through the non-series output of 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. (LET ((X (SCAN '(1 2 5 2))) (SUM (COLLECT-SUM (SCAN '(1 2 5 2))))) (COLLECT-MAX (#M/ X (SERIES SUM)))) => 1/2 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. (LET ((X (SCAN '(1 2 5 2)))) (/ (COLLECT-MAX X) (COLLECT-SUM X))) => 1/2 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 OFF-LINE ports. A series input port or series output port of a series function is ON-LINE if and only if it is processed in lock step 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 `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 lock step 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 on complex transducers are off-line. In particular, the series inputs of CATENATE, CHOOSE-IF, CHUNK, EXPAND, MASK, MINGLE, POSITIONS, and SUBSERIES along with the series outputs of CHOOSE, SPLIT, and SPLIT-IF are off-line. In summary, the fourth and final restriction is that 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. 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. OPTIMIZABLE-SERIES-FUNCTION [Declaration specifier] The declaration specifier (OPTIMIZABLE-SERIES-FUNCTION 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.) 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 OPTIMIZABLE-SERIES-FUNCTION is allowed to appear is in a declaration immediately inside a DEFUN. As an example, the following shows how a simplified version of COLLECT-SUM could be defined. (DEFUN SIMPLE-COLLECT-SUM (NUMBERS) (DECLARE (OPTIMIZABLE-SERIES-FUNCTION 1)) (COLLECT-FN 'NUMBER #'(LAMBDA () 0) #'+ NUMBERS)) OFF-LINE-PORT [Declaration specifier] The declaration specifier (OFF-LINE-PORT PORT-SPEC1 PORT-SPEC2 ...) specifies that the indicated inputs and outputs are off-line. This declaration specifier is only allowed in a DEFUN that contains the declaration OPTIMIZABLE-SERIES-FUNCTION. Each PORT-SPEC must either be a symbol that is one of the inputs of the function or an integer J indicating the jth output (counting from zero). For example, (OFF-LINE-PORT X 1) indicates that the input X and the second output are off-line. Every port that is not mentioned in an 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. 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 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 LET that is part of the expression) should be given informative declarations making use of the type specifier (SERIES ELEMENT-TYPE) where appropriate. Informative types should be supplied to series functions (such as SCAN and MAP-FN) that have type arguments. When using SCAN it is important to specify the type of element in the sequence as well as the sequence itself (for example, by using (VECTOR * INTEGER) as opposed to merely VECTOR). The form (LIST 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 (SERIES T) associated with the output of #M, #Z, SCAN-ALIST, SCAN-FILE, SCAN-HASH, SCAN-LISTS-OF-LISTS-FRINGE, SCAN-LISTS-OF-LISTS, SCAN-PLIST, SERIES, LATCH, or CATENATE, then the form 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, 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. (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)))) 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 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 SERIES-ELEMENT-TYPE can be used to indicate where type propagation should occur. SERIES-ELEMENT-TYPE [Type specifier] The type specifier (SERIES-ELEMENT-TYPE VARIABLE) denotes the type of elements in the series held in VARIABLE. VARIABLE must be a variable carrying a series value (for example, a series argument of a series function). SERIES-ELEMENT-TYPE can only be used in three places: in a declaration in a LET, MAPPING, PRODUCING, or other binding form in a series expression; in a declaration in a DEFUN being used to define a series function; or in a type argument to a series function. As an example, consider that COLLECT-LAST could have been defined as follows. The use of SERIES-ELEMENT-TYPE ensures that the internal variable keeping track of the most recent item has the correct type. (DEFUN COLLECT-LAST (ITEMS &OPTIONAL (DEFAULT NIL)) (DECLARE (OPTIMIZABLE-SERIES-FUNCTION)) (COLLECT-FN '(SERIES-ELEMENT-TYPE ITEMS) #'(LAMBDA () DEFAULT) #'(LAMBDA (OLD NEW) NEW) ITEMS)) 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 are involved with supporting 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. PRODUCING OUTPUT-LIST INPUT-LIST {DECLARATION}* {FORM}* [Macro] 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 below). 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. The example above 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) TERMINATE-PRODUCING [Macro] 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. PROPAGATE-ALTERABILITY [Declaration specifier] 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 can only appear in a call on PRODUCING. INPUT and OUTPUT must be an input and an output of the PRODUCING. 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))))) ENCAPSULATED ENCAPSULATING-FN SCANNER-OR-COLLECTOR [Macro] 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)))) Generators and Gatherers Generators are generalized input streams in the sense of Smalltalk. A generator can produce a potentially unbounded number of elements of any type. Individual elements are not computed until requested by NEXT-IN. When an element is taken from a generator, it is removed by side effect. Subsequent uses of NEXT-IN obtain later elements. There is a close relationship between a generator and a series of the elements it produces. In particular, any series can be converted into a generator. As a result, all the scanner functions used for creating series can be used to create generators as well. There is no need to have a separate set of functions for creating generators. Gatherers are generalized output streams. Elements of any type can be entered into a gatherer using NEXT-OUT. The gatherer combines the elements together in time-sequence order into a net result. This result can be retrieved using RESULT-OF. There is a close relationship between a gatherer and a collector function that combines elements in the same way. In particular, any one-input one-output collector can be converted into a gatherer. As a result, all the collectors used for computing summary results from series can be used to create gatherers. There is no need to have a separate set of functions for creating gatherers. Generators GENERATOR SERIES [Function] Given a series, GENERATOR returns a generator containing the same elements. NEXT-IN GENERATOR {ACTION}* [Macro] NEXT-IN returns the next element in the generator GENERATOR. The ACTIONS can be any Lisp expressions. They are evaluated if and only if no more elements can be retrieved from GENERATOR. If there are no more elements and no actions, it is an error. It is also an error to apply NEXT-IN to a generator a second time after the generator has run out of elements. As an example of generators, consider the following. (LET ((X (GENERATOR (SCAN '(1 2 3 4))))) (WITH-OUTPUT-TO-STRING (S) (LOOP (PRIN1 (NEXT-IN X (RETURN)) S) (PRIN1 (NEXT-IN X (RETURN)) S) (PRINC "," S)))) => "12,34," Gatherers GATHERER COLLECTOR [Function] The COLLECTOR must be a function of type (FUNCTION ((SERIES t1)) t2). Given this function, GATHERER returns a gatherer that accepts elements of type t1 and returns a final result of type t2. The method for combining elements used by the gatherer is the same as the one used by the COLLECTOR. NEXT-OUT GATHERER ITEM [Function] Given a gatherer and a value, NEXT-OUT enters the value into the gatherer. RESULT-OF GATHERER [Function] RESULT-OF retrieves the net result from a gatherer. RESULT-OF can be applied at any time. However, it is an error to apply RESULT-OF twice to the same gatherer or to apply NEXT-OUT to a gatherer once RESULT-OF has been applied. (LET ((G (GATHERER #'COLLECT-SUM))) (DOLIST (I '(1 2 3 4)) (NEXT-OUT G I) (IF (EVENP I) (NEXT-OUT G (* 10 I)))) (RESULT-OF G)) => 70 GATHERING ({(VAR FN)}*) {FORM}* [Macro] The first subform must be a list of pairs. The first element of each pair, VAR, must be a variable name. The second element of each pair, FN, must be a form that when wrapped in (FUNCTION ...) is acceptable as an argument to GATHERER. Each symbol is bound to a gatherer constructed from the corresponding collector. The body (consisting of the FORMS) is evaluated in the scope of these bindings. When this evaluation is complete, GATHERING returns the RESULT-OF each gatherer. If there are N pairs in the binding list, GATHERING returns N values. For example: (DEFUN EXAMP (DATA) (GATHERING ((X COLLECT) (Y COLLECT-SUM)) (ITERATE ((I (SCAN DATA))) (CASE (FIRST I) (:SLOT (NEXT-OUT X (SECOND I))) (:PART (DOLIST (J (SECOND I)) (NEXT-OUT X J)))) (NEXT-OUT Y (THIRD I))))) (EXAMP '((:SLOT A 10) (:PART (C D) 40))) => (A C D) and 50 As a further illustration of gatherers, consider the following definition for a simplified version of GATHERING that handles only one binding pair. (DEFMACRO SIMPLE-GATHERING (((VAR COLLECTOR)) &BODY BODY) `(LET ((,VAR (GATHERER (FUNCTION ,COLLECTOR)))) ,@BODY (RESULT-OF ,VAR))) The full capabilities of GATHERING can be supported in much the same way. ;------------------------------------------------------------------------ ;Copyright Massachusetts Institute of Technology, Cambridge, Massachusetts. ;Permission to use, copy, modify, and distribute this software and its ;documentation for any purpose and without fee is hereby granted, ;provided that this copyright and permission notice appear in all ;copies and supporting documentation, and that the name of M.I.T. not ;be used in advertising or publicity pertaining to distribution of the ;software without specific, written prior permission. M.I.T. makes no ;representations about the suitability of this software for any ;purpose. It is provided "as is" without express or implied warranty. ; M.I.T. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ; ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL ; M.I.T. BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ; ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, ; WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ; ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS ; SOFTWARE. ;------------------------------------------------------------------------