;;; -*- Mode:gate; Fonts:(HL12 HL12I HL12B CPTFONTB HL12BI HL12B HL12I ) -*- =Node: Loop Synonyms =Text: 3LOOP SYNONYMS define-loop-macro* 1keyword* 1Macro* May be used to make 1keyword*, a 2loop* keyword (such as 2for*), into a Lisp macro that may introduce a 2loop* form. For example, after evaluating 3(define-loop-macro for),* one may now write an iteration as 3(for i from 1 below n do ...)* This facility exists primarily for diehard users of a predecessor of 2loop*. Its unconstrained use is not recommended, as it tends to decrease the transportability of the code and needlessly uses up a function name. =Node: Destructuring =Text: 3DESTRUCTURING* 1Destructuring* provides one with the ability to ``simultaneously'' assign or bind multiple variables to components of some data structure. Typically this is used with list structure. For example, 3(loop with (foo . bar) = '(a b c) ...)* has the effect of binding 2foo* to 2a* and 2bar* to 2(b c)*. 2loop*'s destructuring support is intended to parallel and perhaps augment that provided by the host Lisp implementation, with a goal of minimally providing destructuring over list structure patterns. Thus, in Lisp implementations with no system destructuring support at all, one may still use list-structure patterns as 2loop* iteration variables and in 2with* bindings. One may specify the data types of the components of a pattern by using a corresponding pattern of the data type keywords in place of a single data type keyword. This syntax remains unambiguous because wherever a data type keyword is possible, a 2loop* keyword is the only other possibility. Thus, if one wants to do 3(loop for x in l* 3 as i = (car x)* 3 and j = (cadr x)* 3 and k = (cddr x)* 3 ...)* and no reference to 2x* is needed, one may instead write 3(loop for (i j . k) in l ...)* To allow some abbreviation of the data type pattern, an atomic component of the data type pattern is considered to state that all components of the corresponding part of the variable pattern are of that type. That is, the previous form could be written as 3(loop for (i j . k) in l ...)* 3(defun map-over-properties (fn symbol)* 3 (loop for (propname propval) on (plist symbol) by 'cddr* 3 do (funcall fn symbol propname propval)))* maps 1fn* over the properties on 1symbol*, giving it arguments of the symbol, the property name, and the value of that property. =Node: The Iteration Framework =Text: 3THE ITERATION FRAMEWORK* This section describes the way 2loop* constructs iterations. It is necessary if you will be writing your own iteration paths, and may be useful in clarifying what 2loop* does with its input. 2loop* considers the act of 1stepping* to have four possible parts. Each iteration-driving clause has some or all of these four parts, which are executed in this order: 1pre-step-endtest* This is an endtest which determines if it is safe to step to the next value of the iteration variable. 1steps* Variables that get stepped. This is internally manipulated as a list of the form 2(1var1** 1val12 *var22 *val22 ...)**; all of those variables are stepped in parallel, meaning that all of the 1val*s are evaluated before any of the 1var*s are set. 1post-step-endtest* Sometimes you can't see if you are done until you step to the next value; that is, the endtest is a function of the stepped-to value. 1pseudo-steps* Other things that need to be stepped. This is typically used for internal variables that are more conveniently stepped here, or to set up iteration variables that are functions of some internal variable(s) actually driving the iteration. This is a list like 1steps*, but the variables in it do not get stepped in parallel. The above alone is actually insufficient in just about all the iteration-driving clauses that 2loop* handles. What is missing is that in most cases the stepping and testing for the first time through the loop is different from that of all other times. So, what 2loop* deals with is two four-tuples as above; one for the first iteration, and one for the rest. The first may be thought of as describing code that immediately precedes the loop in the 2prog*, and the second following the body code--in fact, 2loop* does just this, but severely perturbs it in order to reduce code duplication. Two lists of forms are constructed in parallel: one is the first-iteration endtests and steps, the other the remaining-iterations endtests and steps. These lists have dummy entries in them so that identical expressions will appear in the same position in both. When 2loop* is done parsing all of the clauses, these lists get merged back together such that corresponding identical expressions in both lists are not duplicated unless they are ``simple'' and it is worth doing. Thus, one 1may* get some duplicated code if one has multiple iterations. Alternatively, 2loop* may decide to use and test a flag variable that indicates whether one iteration has been performed. In general, sequential iterations have less overhead than parallel iterations, both from the inherent overhead of stepping multiple variables in parallel, and from the standpoint of potential code duplication. One other point that must be noted about parallel stepping is that although the user iteration variables are guaranteed to be stepped in parallel, the placement of the endtest for any particular iteration may be either before or after the stepping. A notable case of this is 3(loop for i from 1 to 3 and dummy = (print 'foo)* 3 collect i)* 3 => (1 2 3)* but prints 2foo* 1four* times. Certain other constructs, such as 2for 1var* on*, may or may not do this depending on the particular construction. This problem also means that it may not be safe to examine an iteration variable in the epilogue of the loop form. As a general rule, if an iteration-driving clause implicitly supplies an endtest, then one cannot know the state of the iteration variable when the loop terminates. Although one can guess on the basis of whether the iteration variable itself holds the data upon which the endtest is based, that guess 1may* be wrong. Thus, 3(loop for subl on 1expr** 3 ...* 3 finally (f subl))* is incorrect, but 3(loop as frob = 1expr* while (g frob)* 3 ...* 3 finally (f frob))* is safe because the endtest is explicitly dissociated from the stepping. =Node: Iteration Paths =Text: 3ITERATION PATHS* Iteration paths provide a mechanism for user extension of iteration-driving clauses. The interface is constrained so that the definition of a path need not depend on much of the internals of 2loop*. The typical form of an iteration path is 3for 1var* being {each|the} 1path* {1preposition1* 1expr1*}...* 1path* is an atomic symbol which is defined as a 2loop* path function. Any number of preposition/expression pairs may be present; the prepositions allowable for any particular path are defined by that path. For example, 3(loop for x being the array-elements of my-array from 1 to 10* 3 ...)* To enhance readability, paths are usually defined in both the singular and plural forms; this particular example could have been written as 3(loop for x being each array-element of my-array from 1 to 10* 3 ...)* Another format, which is not so generally applicable, is 3for 1var* being 1expr0* and its 1path* {1preposition1* 1expr1*}...* In this format, 1var* takes on the value of 1expr0* the first time through the loop. Support for this format is usually limited to paths for which the next value is obtained by operating on the previous value. Thus, we can hypothesize the 2cdrs* path, such that 3(loop for x being the cdrs of '(a b c . d) collect x)* 3 => ((b c . d) (c . d) d)* but 3(loop for x being '(a b c . d) and its cdrs collect x)* 3 => ((a b c . d) (b c . d) (c . d) d)* To satisfy the anthropomorphic among you, 2his*, 2her*, or 2their* may be substituted for the 2its* keyword, as may 2each*. Egocentricity is not condoned. Some example uses of iteration paths are shown in section 4(LOOP-2)Pre-Defined Paths*. Very often, iteration paths step internal variables which the user does not specify, such as an index into some data-structure. Although in most cases the user does not wish to be concerned with such low-level matters, it is occasionally useful to have a handle on such things. 2loop* provides an additional syntax with which one may provide a variable name to be used as an ``internal'' variable by an iteration path, with the 2using* ``prepositional phrase''. The 2using* phrase is placed with the other phrases associated with the path, and contains any number of keyword/variable-name pairs: 3(loop for x being the array-elements of a using (index i)* 3 ...)* which says that the variable 2i* should be used to hold the index of the array being stepped through. The particular keywords which may be used are defined by the iteration path; the 2index* keyword is recognized by all 2loop* sequence paths (section 4(LOOP-2)Sequence Iteration*). Note that any individual 2using* phrase applies to only one path; it is parsed along with the ``prepositional phrases''. It is an error if the path does not call for a variable using that keyword. By special dispensation, if a 1path* is not recognized, then the 2default-loop-path* path will be invoked upon a syntactic transformation of the original input. Essentially, the 2loop* fragment 3for 1var* being 1frob** is taken as if it were 3for 1var* being default-loop-path in 1frob** and 3for 1var* being 1expr* and its 1frob* ...* is taken as if it were 3for 1var* being 1expr* and its default-loop-path in 1frob** Thus, this ``undefined path hook'' only works if the 2default-loop-path* path is defined. Obviously, the use of this ``hook'' is competitive, since only one such hook may be in use, and the potential for syntactic ambiguity exists if 1frob* is the name of a defined iteration path. This feature is not for casual use; it is intended for use by large systems that wish to use a special syntax for some feature they provide. =Node: Pre-Defined Paths =Text: 3PRE-DEFINED PATHS* 2loop* comes with two pre-defined iteration path functions; one implements a 2mapatoms*-like iteration path facility and the other is used for defining iteration paths for stepping through sequences. =Node: The Interned-symbols Path =Text: 3THE INTERNED-SYMBOLS PATH* The 2interned-symbols* iteration path is like a 2mapatoms* for 2loop*. 3(loop for sym being interned-symbols ...)* iterates over all of the symbols in the current package and its superiors. This is the same set of symbols over which 2mapatoms* iterates, although not necessarily in the same order. The particular package to look in may be specified as in 3(loop for sym being the interned-symbols in 1package* ...)* which is like giving a second argument to 2mapatoms*. You can restrict the iteration to the symbols directly present in the specified package, excluding inherited symbols, using the 2local-interned-symbols* path: 3(loop for sym being the local-interned-symbols {in 1package*}* 3 ...)* Example: 3(defun my-apropos (sub-string &optional (pkg package))* 3 (loop for x being the interned-symbols in pkg* 3 when (string-search sub-string x)* 3 when (or (boundp x) (fboundp x) (plist x))* 3 do (print-interesting-info x)))* In the Zetalisp and NIL implementations of 2loop*, a package specified with the 2in* preposition may be anything acceptable to the 2pkg-find-package* function. The code generated by this path will contain calls to internal 2loop* functions, with the effect that it will be transparent to changes to the implementation of packages. In the Maclisp implementation, the obarray 1must* be an array pointer, 1not* a symbol with an 2array* property. =Node: The Hash-Elements Path =Text: 3THE HASH-ELEMENTS PATH* The 2hash-elements* path provides an effect like that of the function 2maphash*. It can find all the occupied entries in a hash table. 3(loop for value being the hash-elements of 1hash-table* ...)* iterates over all the occupied entries in 1hash-table*. Each time, 1value* is the value stored in the entry. To examine the keys of the entries as well, write 3(loop for value being the hash-elements of 1hash-table** 3 with-key keysym ...)* and then 2keysym*'s value each will be the hash key that corresponds to 1value*. =Node: Sequence Iteration =Text: 3SEQUENCE ITERATION* One very common form of iteration is done over the elements of some object that is accessible by means of an integer index. 2loop* defines an iteration path function for doing this in a general way and provides a simple interface to allow users to define iteration paths for various kinds of ``indexable'' data. 3define-loop-sequence-path* 1path-name-or-names* 1fetch-fun* 1size-fun* 1Macro* &optional 1sequence-type* 1default-var-type* 1path-name-or-names* is either an atomic path name or list of path names. 1fetch-fun* is a function of two arguments, the sequence and the index of the item to be fetched. (Indexing is assumed to be zero-origined.) 1size-fun* is a function of one argument, the sequence; it should return the number of elements in the sequence. 1sequence-type* is the name of the data-type of the sequence, and 1default-var-type* the name of the data-type of the elements of the sequence. These are applicable to use of 2loop* in other Lisp systems; on the Lisp Machine they might as well be omitted. The Zetalisp implementation of 2loop* utilizes the Zetalisp array manipulation primitives to define both 2array-element* and 2array-elements* as iteration paths: 3(define-loop-sequence-path (array-element array-elements)* 3 aref array-active-length)* Then, the 2loop* clause 3for 1var* being the array-elements of 1array** will step 1var* over the elements of 1array*, starting from element 0. The sequence path function also accepts 2in* as a synonym for 2of*. The range and stepping of the iteration may be specified with the use of all of the same keywords which are accepted by the 2loop* arithmetic stepper (2for 1var* from ...*); they are 2by*, 2to*, 2downto*, 2from*, 2downfrom*, 2below*, and 2above*, and are interpreted in the same manner. Thus, 3(loop for 1var* being the array-elements of 1array** 3 from 1 by 2* 3 ...)* steps 1var* over all of the odd elements of 1array*, and 3(loop for 1var* being the array-elements of 1array** 3 downto 0* 3 ...)* steps in reverse order. 3(define-loop-sequence-path (vector-elements vector-element)* 3 vref vector-length notype notype)* is how the 2vector-elements* iteration path can be defined in NIL (which it is). One can then do such things as 3(defun cons-a-lot (item &restv other-items)* 3 (and other-items* 3 (loop for x being the vector-elements of other-items* 3 collect (cons item x))))* All such sequence iteration paths allow one to specify the variable to be used as the index variable, by use of the 2index* keyword with the 2using* prepositional phrase, as described (with an example) on 4(LOOP-2)Iteration Paths*. =Node: Defining Paths =Text: 3DEFINING PATHS* This section and the next may not be of interest to those not interested in defining their own iteration paths. In addition to the code which defines the iteration (section 4(LOOP-2)The Iteration Framework*), a 2loop* iteration clause (e.g. a 2for* or 2as* clause) produces variables to be bound and pre-iteration (1prologue*) code. This breakdown allows a user-interface to 2loop* which does not have to depend on or know about the internals of 2loop*. To complete this separation, the iteration path mechanism parses the clause before giving it to the user function that will return those items. A function to generate code for a path may be declared to 2loop* with the 2define-loop-path* function: 3define-loop-path* 1pathname-or-names* 1path-function* 1list-of-allowable-prepositions* &rest 1dataMacro* This defines 1path-function* to be the handler for the path(s) 1path-or-names*, which may be either a symbol or a list of symbols. Such a handler should follow the conventions described below. The 1datum-i* are optional; they are passed in to 1path-function* as a list. The handler will be called with the following arguments: 1path-name* The name of the path that caused the path function to be invoked. 1variable* The ``iteration variable''. 1data-type* The data type supplied with the iteration variable, or 2nil* if none was supplied. This is a facility of the 2loop* intended for other Lisp systems in which declaring the type of a variable produces more efficient code. It is not documented in this manual since it is never useful on the Lisp Machine. 1prepositional-phrases* This is a list with entries of the form 1(preposition expression)*, in the order in which they were collected. This may also include some supplied implicitly (e.g. an 2of* phrase when the iteration is inclusive, and an 2in* phrase for the 2default-loop-path* path); the ordering will show the order of evaluation that should be followed for the expressions. 1inclusive?* This is 2t* if 1variable* should have the starting point of the path as its value on the first iteration (by virtue of being specified with syntax like 2for 1var* being 1expr* and its 1path**), 2nil* otherwise. When 2t*, 1expr* will appear in 1prepositional-phrases* with the 2of* preposition; for example, 2for x being foo and its cdrs* gets 1prepositional-phrases* of 2((of foo))*. 1allowed-prepositions* This is the list of allowable prepositions declared for the path that caused the path function to be invoked. It and 1data* (immediately below) may be used by the path function such that a single function may handle similar paths. 1data* This is the list of ``data'' declared for the path that caused the path function to be invoked. It may, for instance, contain a canonicalized path, or a set of functions or flags to aid the path function in determining what to do. In this way, the same path function may be able to handle different paths. The handler should return a list of either six or ten elements: 1variable-bindings* This is a list of variables that need to be bound. The entries in it may be of the form 1variable* or (1variable* 1expression*). Note that it is the responsibility of the handler to make sure the iteration variable gets bound. All of these variables will be bound in parallel; if initialization of one depends on others, it should be done with a 2setq* in the 1prologue-forms*. Returning only the variable without any initialization expression is not allowed if the variable is a destructuring pattern. 1prologue-forms* This is a list of forms that should be included in the 2loop* prologue. 1the four items of the iteration specification* These are the four items described in section 4(LOOP-2)The Iteration Framework*, 4(LOOP-2)The Iteration Framework*: 1pre-step-endtest*, 1steps*, 1post-step-endtest*, and 1pseudo-steps*. 1another four items of iteration specification* If these four items are given, they apply to the first iteration, and the previous four apply to all succeeding iterations; otherwise, the previous four apply to 1all* iterations. Here are the routines that are used by 2loop* to compare keywords for equality. In all cases, a 1token* may be any Lisp object, but a 1keyword* is expected to be an atomic symbol. In certain implementations these functions may be implemented as macros. 3si:loop-tequal* 1token* 1keyword* This is the 2loop* token comparison function. 1token* is any Lisp object; 1keyword* is the keyword it is to be compared against. It returns 2t* if they represent the same token, comparing in a manner appropriate for the implementation. 3si:loop-tmember* 1token* 1keyword-list* The 2member* variant of 2si:loop-tequal*. 3si:loop-tassoc* 1token* 1keyword-alist* The 2assoc* variant of 2si:loop-tequal*. If an iteration path function desires to make an internal variable accessible to the user, it should call the following function instead of 2gensym*: 3si:loop-named-variable* 1keyword* This should only be called from within an iteration path function. If 1keyword* has been specified in a 2using* phrase for this path, the corresponding variable is returned; otherwise, 2gensym* is called and that new symbol returned. Within a given path function, this routine should only be called once for any given keyword. If the user specifies a 2using* preposition containing any keywords for which the path function does not call 2si:loop-named-variable*, 2loop* will inform the user of his error. =Node: Path Definition Example =Text: 3PATH DEFINITION EXAMPLE* Here is an example function that defines the 2string-characters* iteration path. This path steps a variable through all of the characters of a string. It accepts the format 3(loop for 1var* being the string-characters of 1str* ...)* The function is defined to handle the path by 3(define-loop-path string-characters string-chars-path (of))* Here is the function: 3(defun string-chars-path (path-name variable data-type* 3 prep-phrases inclusive?* 3 allowed-prepositions data* 3 &aux (bindings nil)* 3 (prologue nil)* 3 (string-var (gensym))* 3 (index-var (gensym))* 3 (size-var (gensym)))* 3 allowed-prepositions data 2; unused variables** 3 data-type* 3 2; To iterate over the characters of a string, we need** 3 2; to save the string, save the size of the string,** 3 2; step an index variable through that range, setting** 3 2; the user's variable to the character at that index.** 3 2; We support exactly one ``preposition'', which is required,** 3 2; so this check suffices:** 3 (cond ((null prep-phrases)* 3 (ferror nil "OF missing in ~S iteration path of ~S"* 3 path-name variable)))* 3 2; We do not support ``inclusive'' iteration:** 3 (cond ((not (null inclusive?))* 3 (ferror nil* 3 "Inclusive stepping not supported in ~S path ~* 3 of ~S (prep phrases = ~:S)"* 3 path-name variable prep-phrases)))* 3 2; Set up the bindings** 3 (setq bindings (list (list variable nil)* 3 (list string-var (cadar prep-phrases))* 3 (list index-var 0)* 3 (list size-var 0)))* 3 2; Now set the size variable** 3 (setq prologue (list `(setq ,size-var (string-length* 3 ,string-var))))* 3 2; and return the appropriate stuff, explained below.** 3 (list bindings prologue* 3 `(= ,index-var ,size-var)* 3 nil nil* 3 (list variable `(aref ,string-var ,index-var)* 3 index-var `(1+ ,index-var))))* The first element of the returned list is the bindings. The second is a list of forms to be placed in the 1prologue*. The remaining elements specify how the iteration is to be performed. This example is a particularly simple case, for two reasons: the actual ``variable of iteration'', 2index-var*, is purely internal (being 2gensym*med), and the stepping of it (21+*) is such that it may be performed safely without an endtest. Thus 2index-var* may be stepped immediately after the setting of the user's variable, causing the iteration specification for the first iteration to be identical to the iteration specification for all remaining iterations. This is advantageous from the standpoint of the optimizations 2loop* is able to perform, although it is frequently not possible due to the semantics of the iteration (e.g., 2for 1var* first 1expr1* then 1expr2**) or to subtleties of the stepping. It is safe for this path to step the user's variable in the 1pseudo-steps* (the fourth item of an iteration specification) rather than the ``real'' steps (the second), because the step value can have no dependencies on any other (user) iteration variables. Using the pseudo-steps generally results in some efficiency gains. If one desired the index variable in the above definition to be user-accessible through the 2using* phrase feature with the 2index* keyword, the function would need to be changed in two ways. First, 2index-var* should be bound to 2(si:loop-named-variable 'index)* instead of 2(gensym)*. Secondly, the efficiency hack of stepping the index variable ahead of the iteration variable must not be done. This is effected by changing the last form to be 3(list bindings prologue* 3 nil* 3 (list index-var `(1+ ,index-var))* 3 `(= ,index-var ,size-var)* 3 (list variable `(aref ,string-var ,index-var))* 3 nil* 3 nil* 3 `(= ,index-var ,size-var)* 3 (list variable `(aref ,string-var ,index-var)))* Note that although the second 2`(= ,index-var ,size-var)* could have been placed earlier (where the second 2nil* is), it is best for it to match up with the equivalent test in the first iteration specification grouping.