;;; -*- Mode:gate; Fonts:(HL12 HL12I HL12B CPTFONTB HL12BI HL12B HL12I ) -*- =Node: Introduction =Text: 3INTRODUCTION* 2loop* is a Lisp macro that provides a programmable iteration facility. The same 2loop* module operates compatibly in Zetalisp, Maclisp (PDP-10 and Multics), and NIL, and a moderately compatible package is under development for the MDL programming environment. 2loop* was inspired by the FOR facility of CLISP in InterLisp; however, it is not compatible and differs in several details. The general approach is that a form introduced by the word 2loop* generates a single program loop, into which a large variety of features can be incorporated. The loop consists of some initialization (1prologue*) code, a body that may be executed several times, and some exit (1epilogue*) code. Variables may be declared local to the loop. The special features of 2loop* are concerned with loop variables, deciding when to end the iteration, putting user-written code into the loop, returning a value from the construct, and iterating a variable through various real or virtual sets of values. The 2loop* form consists of a series of clauses, each introduced by a ``keyword'' symbol. These symbols are keywords from 2loop*'s point of view; they are not keywords in the usual sense (symbols in the 2keyword* package). 2loop* ignores the package when it compares a symbol against the known keywords. Forms appearing in or implied by the clauses of a 2loop* form are classed as those to be executed as initialization code, body code, and/or exit code; within each part of the template filled in by 2loop*, they are executed strictly in the order implied by the original composition. Thus, just as in ordinary Lisp code, side-effects may be used, and one piece of code may depend on following another for its proper operation. This is the principal philosophic difference from InterLisp's FOR facility. Note that 2loop* forms are intended to look like stylized English rather than Lisp code. There is a notably low density of parentheses, and many of the keywords are accepted in several synonymous forms to allow writing of more euphonious and grammatical English. Some find this notation verbose and distasteful, while others find it flexible and convenient. The former are invited to stick to 2do*. Here are some examples to illustrate the use of 2loop*. 3(defun print-elements-of-list (list-of-elements)* 3 (loop for element in list-of-elements* 3 do (print element)))* prints each element in its argument, which should be a list. It returns 2nil*. 3(defun gather-alist-entries (list-of-pairs)* 3 (loop for pair in list-of-pairs* 3 collect (car pair)))* takes an association list and returns a list of the keys; that is, 2(gather-alist-entries '((foo 1 2) (bar 259) (baz)))* returns 2(foo bar baz)*. 3(defun extract-interesting-numbers (start-value end-value)* 3 (loop for number from start-value to end-value* 3 when (interesting-p number) collect number))* takes two arguments, which should be integers, and returns a list of all the numbers in that range (inclusive) which satisfy the predicate 2interesting-p*. 3(defun find-maximum-element (an-array)* 3 (loop for i from 0 below (array-dimension-n 1 an-array)* 3 maximize (aref an-array i)))* returns the maximum of the elements of its argument, a one-dimensional array. 3(defun my-remove (object list)* 3 (loop for element in list* 3 unless (equal object element) collect element))* is like the standard function 2remove*, except that it copies the entire list. 3(defun find-frob (list)* 3 (loop for element in list* 3 when (frobp element) return element* 3 finally (ferror nil "No frob found in the list ~S"* 3 list)))* returns the first element of its list argument which satisfies the predicate 2frobp*. If none is found, an error is signaled. Common Lisp defines 2loop* as equivalent to 2do-forever*: it is used with a body consisting only of forms to be evaluated until a nonlocal exit happens. This is incompatible with the traditional 2loop* macro which this chapter is about. However, it is possible to tell which meaning of 2loop* the programmer intended: in the traditional 2loop* macro, it must be a symbol, while in the Common Lisp 2loop* it is useless to use a symbol there. Therefore, if the first argument of a 2loop* form is not a symbol, it is treated as a Common Lisp 2loop*. =Node: Clauses =Text: 3CLAUSES* Internally, 2loop* constructs a 2prog* which includes variable bindings, pre-iteration (initialization) code, post-iteration (exit) code, the body of the iteration, and stepping of variables of iteration to their next values (which happens on every iteration after the body is executed). A 1clause* consists of a keyword symbol and any Lisp forms and keywords that it deals with. For example, 3(loop for x in l do (print x)),* contains two clauses, 3for x in l* and 3do (print x)*. Certain of the parts of the clause will be described as being 1expressions*, e.g. 2(print x)* in the above. An expression can be a single Lisp form, or a series of forms implicitly collected with 2progn*. An expression is terminated by the next following atom, which is taken to be a keyword. This syntax allows only the first form in an expression to be atomic, but makes misspelled keywords more easily detectable. 2loop* uses print-name equality to compare keywords so that 2loop* forms may be written without package prefixes; in Lisp implementations that do not have packages, 2eq* is used for comparison. Bindings and iteration variable steppings may be performed either sequentially or in parallel. This affects how the stepping of one iteration variable may depend on the value of another. The syntax for distinguishing the two will be described with the corresponding clauses. When a set of variables are to be bound in parallel, all of the initial values are computed and then all the bindings are established. Subsequent bindings will be performed inside of that binding environment. When the same variables are stepped, all the new values are computed and then the variables are set. =Node: Iteration-Driving Clauses =Text: 3ITERATION-DRIVING CLAUSES* These clauses all create a 1variable of iteration*, which is bound locally to the loop and takes on a new value on each successive iteration. Note that if more than one iteration-driving clause is used in the same loop, several variables are created that all step together through their values; when any of the iterations terminates, the entire loop terminates. Nested iterations are not generated; for those, you need a second 2loop* form in the body of the loop. In order not to produce strange interactions, iteration-driving clauses are required to precede any clauses that produce body code: that is, all except those that produce prologue or epilogue code (2initially* and 2finally*), bindings (2with*), the 2named* clause, and the iteration termination clauses (2while* and 2until*). Clauses which drive the iteration may be arranged to perform their testing and stepping either in series or in parallel. They are by default grouped in series, which allows the stepping computation of one clause to use the just-computed values of the iteration variables of previous clauses. They may be made to step in parallel, as is the case with the 2do* special form, by ``joining'' the iteration clauses with the keyword 2and*. The form this typically takes is something like 3(loop ... for x = (f) and for y = 1init* then (g x) ...)* which sets 2x* to 2(f)* on every iteration, and binds 2y* to the value of 1init* for the first iteration, and on every iteration thereafter sets it to 2(g x)*, where 2x* still has the value from the 1previous* iteration. Thus, if the calls to 2f* and 2g* are not order-dependent, this would be best written as 3(loop ... for y = 1init* then (g x) for x = (f) ...)* because, as a general rule, parallel stepping has more overhead than sequential stepping. Similarly, the example 3(loop for sublist on some-list* 3 and for previous = 'undefined then sublist* 3 ...)* which is equivalent to the 2do* construct 3(do ((sublist some-list (cdr sublist))* 3 (previous 'undefined sublist))* 3 ((null sublist) ...)* 3 ...)* in terms of stepping, would be better written as 3(loop for previous = 'undefined then sublist* 3 for sublist on some-list* 3 ...)* When iteration-driving clauses are joined with 2and*, if the token following the 2and* is not a keyword that introduces an iteration driving clause, it is assumed to be the same as the keyword that introduced the most recent clause; thus, the above example showing parallel stepping could have been written as 3(loop for sublist on some-list* 3 and previous = 'undefined then sublist* 3 ...)* The order of evaluation in iteration-driving clauses is as follows: those expressions that are only evaluated once are evaluated in order at the beginning of the form, during the variable-binding phase, while those expressions that are evaluated each time around the loop are evaluated in order in the body. One common and simple iteration-driving clause is 2repeat*: 2repeat 1expression** Evaluates 1expression* (during the variable binding phase), and causes the 2loop* to iterate that many times. 1expression* is expected to evaluate to an integer. If 1expression* evaluates to a zero or negative result, the body code will not be executed. All remaining iteration-driving clauses are subdispatches of the keyword 2for*, which is synonomous with 2as*. In all of them a 1variable of iteration* is specified. Note that, in general, if an iteration-driving clause implicitly supplies an endtest, the value of this iteration variable is undefined as the loop is exited (i.e., when the epilogue code is run). This is discussed in more detail in section 4(LOOP-2)The Iteration Framework*. Here are all of the varieties of 2for* clauses. Optional parts are enclosed in curly brackets. 2for 1var* in 1expr1* {by 1expr2*}* Iterates over each of the elements in the list 1expr1*. If the 2by* subclause is present, 1expr2* is evaluated once on entry to the loop to supply the function to be used to fetch successive sublists, instead of 2cdr*. 2for 1var* on 1expr1* {by 1expr2*}* Like the previous 2for* format, except that 1var* is set to successive sublists of the list instead of successive elements. Note that 2loop* uses a 2null* rather than an 2atom* test to implement both this and the preceding clause. 2for 1var* = 1expr** On each iteration, 1expr* is evaluated and 1var* is set to the result. 2for 1var* = 1expr1* then 1expr2** 1var* is bound to 1expr1* when the loop is entered, and set to 1expr2* (re-evaluated) at all but the first iteration. Since 1expr1* is evaluated during the binding phase, it cannot reference other iteration variables set before it; for that, use the following: 2for 1var* first 1expr1* then 1expr2** Sets 1var* to 1expr1* on the first iteration, and to 1expr2* (re-evaluated) on each succeeding iteration. The evaluation of both expressions is performed 1inside* of the 2loop* binding environment, before the 2loop* body. This allows the first value of 1var* to come from the first value of some other iteration variable, allowing such constructs as 3(loop for term in poly* 3 for ans first (car term) * 3 then (gcd ans (car term))* 3 finally (return ans)) 2for 1var* from 1expr1* {to 1expr2*} {by 1expr3*}** This performs numeric iteration. 1var* is initialized to 1expr1*, and on each succeeding iteration is incremented by 1expr3* (default 21*). If the 2to* phrase is given, the iteration terminates when 1var* becomes greater than 1expr2*. Each of the expressions is evaluated only once, and the 2to* and 2by* phrases may be written in either order. Alternative keywords may be used in place of 2to*; this choice controls the direction of stepping and the step at which the loop terminates. 2downto* instead of 2to* says that 1var* is decremented by the step value, and the endtest is adjusted accordingly. If 2below* is used instead of 2to*, or 2above* instead of 2downto*, the iteration terminates before 1expr2* is reached, rather than after. Note that the 2to* variant appropriate for the direction of stepping must be used for the endtest to be formed correctly; i.e. the code will not work if 1expr3* is negative or zero. If no limit-specifying clause is given, then the direction of the stepping may be specified as decreasing by using 2downfrom* instead of 2from*. 2upfrom* may also be used instead of 2from*; it forces the stepping direction to be increasing. 2for 1var* being 1expr* and its 1path* ...* 2for 1var* being {each|the} 1path* ...*Provides a user-definable iteration facility. 1path* names the manner in which the iteration is to be performed. The ellipsis indicates where various path dependent preposition/expression pairs may appear. See the section on Iteration Paths (4(LOOP-2)Iteration Paths*) for complete documentation. =Node: Bindings =Text: 3BINDINGS* The 2with* keyword may be used to establish initial bindings, that is, variables that are local to the loop but are only set once, rather than on each iteration. The 2with* clause looks like: 2with 1var1* {= 1expr1*}* 2 {and 1var2* {= 1expr2*}}...* If no 1expr* is given, the variable is initialized to 2nil*. 2with* bindings linked by 2and* are performed in parallel; those not linked are performed sequentially. That is, 3(loop with a = (foo) and b = (bar) and c* 3 ...)* binds the variables like 3(let ((a (foo)) (b (bar)) c) ...)* whereas 3(loop with a = (foo) with b = (bar a) with c ...)* binds the variables like 3(let ((a (foo)))* 3 (let ((b (bar)))* 3 (let (c) ...)))* All 1expr*'s in 2with* clauses are evaluated in the order they are written, in lambda expressions surrounding the generated 2prog*. The 2loop* expression 3(loop with a = 1xa* and b = 1xb** 3 with c = 1xc** 3 for d = 1xd* then (f d)* 3 and e = 1xe* then (g e d)* 3 for p in 1xp** 3 with q = 1xq** 3 ...)* produces the following binding contour, where 2t1* is a 2loop*-generated temporary: 3(let ((a xa) (b xb))* 3 (let ((c xc))* 3 (let ((d xd) (e xe))* 3 (let ((p nil) (t1 xp))* 3 (let ((q xq))* 3 ...)))))* Because all expressions in 2with* clauses are evaluated during the variable binding phase, they are best placed near the front of the 2loop* form for stylistic reasons. For binding more than one variable with no particular initialization, one may use the construct 2with 1variable-list* {and ...}* as in 3with (i j k t1 t2) ...* These are cases of 1destructuring* which 2loop* handles specially; destructuring and data type keywords are discussed in section 4(LOOP-2)Destructuring*. =Node: Entrance and Exit =Text: 3ENTRANCE AND EXIT 2initially 1expression*** Puts 1expression* into the 1prologue* of the iteration. It will be evaluated before any other initialization code except for initial bindings. For the sake of good style, the 2initially* clause should therefore be placed after any 2with* clauses but before the main body of the loop. 2finally 1expression** Puts 1expression* into the 1epilogue* of the loop, which is evaluated when the iteration terminates (other than by an explicit 2return*). For stylistic reasons, then, this clause should appear last in the loop body. Note that certain clauses may generate code which terminates the iteration without running the epilogue code; this behavior is noted with those clauses. Most notable of these are those described in the section 4(LOOP-1)Aggregated Boolean Tests*, Aggregated Boolean Tests. This clause may be used to cause the loop to return values in a non-standard way: 3(loop for n in l* 3 sum n into the-sum* 3 count t into the-count* 3 finally (return (quotient the-sum the-count)))* =Node: Side Effects =Text: 3SIDE EFFECTS 2do 1expression*** 2doing 1expressionexpression** is evaluated each time through the loop, as shown in the 2print-elements-of-list* example on 4(ASSEMBLER-1)Introduction*. =Node: Values =Text: 3VALUES* The following clauses accumulate a return value for the iteration in some manner. The general form is 1type-of-collection expr2 {into *var2}** where 1type-of-collection* is a 2loop* keyword, and 1expr* is the thing being accumulated somehow. If no 2into* is specified, then the accumulation will be returned when the 2loop* terminates. If there is an 2into*, then when the epilogue of the 2loop* is reached, 1var* (a variable automatically bound locally in the loop) will have been set to the accumulated result and may be used by the epilogue code. In this way, a user may accumulate and somehow pass back multiple values from a single 2loop*, or use them during the loop. It is safe to reference these variables during the loop, but they should not be modified until the epilogue code of the loop is reached. For example, 3(loop for x in list* 3 collect (foo x) into foo-list* 3 collect (bar x) into bar-list* 3 collect (baz x) into baz-list* 3 finally (return (list foo-list bar-list baz-list)))* has the same effect as 3(do ((#:g0001 list (cdr #:g0001))* 3 (x) (foo-list) (bar-list) (baz-list))* 3 ((null #:g0001)* 3 (list (nreverse foo-list)* 3 (nreverse bar-list)* 3 (nreverse baz-list)))* 3 (setq x (car #:g0001))* 3 (setq foo-list (cons (foo x) foo-list))* 3 (setq bar-list (cons (bar x) bar-list))* 3 (setq baz-list (cons (baz x) baz-list)))* except that 2loop* arranges to form the lists in the correct order, obviating the 2nreverse*s at the end, and allowing the lists to be examined during the computation. (This is how the expression would print; this text would not read in properly because a new uninterned symbol would be created by each use of 3#:*.) 2collect 1expr* {into 1var*}* 2collecting ...*Causes the values of 1expr* on each iteration to be collected into a list. 2nconc 1expr* {into 1var*}* 2nconcing ... append ... appending ...*Like 2collect*, but the results are 2nconc*'ed or 2append*'ed together as appropriate. 3(loop for i from 1 to 3* 3 nconc (list i (* i i)))* 3 => (1 1 2 4 3 9) 2count 1expr* {into 1var*}** 2counting ...*If 1expr* evaluates non-2nil*, a counter is incremented. 2sum 1expr* {into 1var*}* 2summing ...*Evaluates 1expr* on each iteration and accumulates the sum of all the values. 2maximize 1expr* {into 1var*}* 2minimize ...*Computes the maximum (or minimum) of 1expr* over all iterations. Note that if the loop iterates zero times, or if conditionalization prevents the code of this clause from being executed, the result will be meaningless. Not only may there be multiple accumulations in a 2loop*, but a single accumulation may come from multiple places 1within the same 2loop* form*. Obviously, the types of the collection must be compatible. 2collect*, 2nconc*, and 2append* may all be mixed, as may 2sum* and 2count*, and 2maximize* and 2minimize*. For example, 3(loop for x in '(a b c) for y in '((1 2) (3 4) (5 6))* 3 collect x* 3 append y)* 3 => (a 1 2 b 3 4 c 5 6)* The following computes the average of the entries in the list 1list-of-frobs*: 3(loop for x in list-of-frobs* 3 count t into count-var* 3 sum x into sum-var* 3 finally (return (cli:// sum-var count-var)))* =Node: Endtests =Text: 3ENDTESTS* The following clauses may be used to provide additional control over when the iteration gets terminated, possibly causing exit code (due to 2finally*) to be performed and possibly returning a value (e.g., from 2collect*). 2while 1expr** If 1expr* evaluates to 2nil*, the loop is exited, performing exit code (if any) and returning any accumulated value. The test is placed in the body of the loop where it is written. It may appear between sequential 2for* clauses. 2until 1expr** Identical to 2while (not 1expr*)*. This may be needed, for example, to step through a strange data structure, as in 3(loop until (top-of-concept-tree? concept)* 3 for concept = 1expr* then (superior-concept concept)* 3 ...)* Note that the placement of the 2until* clause before the 2for* clause is valid in this case because of the definition of this particular variant of 2for*, which 1binds* 2concept* to its first value rather than setting it from inside the 2loop*. The following may also be of use in terminating the iteration: 3loop-finish* 1Macro* 2(loop-finish)* causes the iteration to terminate ``normally'', like implicit termination by an iteration-driving clause, or by the use of 2while* or 2until*--the epilogue code (if any) will be run, and any implicitly collected result will be returned as the value of the 2loop*. For example, 3(loop for x in '(1 2 3 4 5 6)* 3 collect x* 3 do (cond ((= x 4) (loop-finish))))* 3 => (1 2 3 4)* This particular example would be better written as 2until (= x 4)* in place of the 2do* clause. =Node: Aggregated Boolean Tests =Text: 3AGGREGATED BOOLEAN TESTS* All of these clauses perform some test and may immediately terminate the iteration depending on the result of that test. 2always 1expr** Causes the loop to return 2t* if 1expr* 2always* evaluates non-2null*. If 1expr* evaluates to 2nil* the loop immediately returns 2nil*, without running the epilogue code (if any, as specified with the 2finally* clause); otherwise, 2t* will be returned when the loop finishes, after the epilogue code has been run. 2never 1expr** Causes the loop to return 2t* if 1expr* 2never* evaluates non-2null*. This is equivalent to 2always (not 1expr*)*. 2thereis 1expr** If 1expr* evaluates non-2nil*, then the iteration is terminated, and that value is returned without running the epilogue code. =Node: Conditionalization =Text: 3CONDITIONALIZATION* These clauses may be used to ``conditionalize'' the following clause. They may precede any of the side-effecting or value-producing clauses, such as 2do*, 2collect*, 2always*, or 2return*. 2when 1expr** 2if 1expr** If 1expr* evaluates to 2nil*, the following clause will be skipped, otherwise not. 2unless 1expr** This is equivalent to 2when (not 1expr*))*. Multiple conditionalization clauses may appear in sequence. If one test fails, then any following tests in the immediate sequence, as well as the clause being conditionalized, are skipped. Multiple clauses may be conditionalized under the same test by joining them with 2and*, as in 3(loop for i from a to b* 3 when (zerop (remainder i 3))* 3 collect i and do (print i))* which returns a list of all multiples of 23* from 2a* to 2b* (inclusive) and prints them as they are being collected. If-then-else conditionals may be written using the 2else* keyword, as in 3(loop for i from a to b* 3 when (oddp i)* 3 collect i into odd-numbers* 3 else collect i into even-numbers)* Multiple clauses may appear in an 2else*-phrase, using 2and* to join them in the same way as above. Conditionals may be nested. For example, 3(loop for i from a to b* 3 when (zerop (remainder i 3))* 3 do (print i)* 3 and when (zerop (remainder i 2))* 3 collect i)* returns a list of all multiples of 26* from 2a* to 2b*, and prints all multiples of 23* from 2a* to 2b*. When 2else* is used with nested conditionals, the ``dangling else'' ambiguity is resolved by matching the 2else* with the innermost 2when* not already matched with an 2else*. Here is a complicated example. 3(loop for x in l* 3 when (atom x)* 3 when (memq x *distinguished-symbols*)* 3 do (process1 x)* 3 else do (process2 x)* 3 else when (memq (car x) *special-prefixes*)* 3 collect (process3 (car x) (cdr x))* 3 and do (memoize x)* 3 else do (process4 x))* Useful with the conditionalization clauses is the 2return* clause, which causes an explicit return of its argument as the value of the iteration, bypassing any epilogue code. That is, 2when 1expr1* return 1expr2** is equivalent to 2when 1expr1* do (return 1expr2*)* Conditionalization of one of the ``aggregated boolean value'' clauses simply causes the test that would cause the iteration to terminate early not to be performed unless the condition succeeds. For example, 3(loop for x in l* 3 when (significant-p x)* 3 do (print x) (princ "is significant.")* 3 and thereis (extra-special-significant-p x))* does not make the 2extra-special-significant-p* check unless the 2significant-p* check succeeds. The format of a conditionalized clause is typically something like 2when 1expr1* 1keyword* 1expr2** If 1expr2* is the keyword 2it*, then a variable is generated to hold the value of 1expr1*, and that variable gets substituted for 1expr2*. Thus, the composition 2when 1expr* return it* is equivalent to the clause 2thereis 1expr** and one may collect all non-null values in an iteration by saying 2when 1expression* collect it* If multiple clauses are joined with 2and*, the 2it* keyword may only be used in the first. If multiple 2when*s, 2unless*es, and/or 2if*s occur in sequence, the value substituted for 2it* will be that of the last test performed. The 2it* keyword is not recognized in an 2else*-phrase. =Node: Miscellaneous Other Clauses =Text: 3MISCELLANEOUS OTHER CLAUSES 2named 1name*** Defines a 2block* named 1name* around the code for the 2loop*, so that one may use 2return-from* to return explicitly out of this particular 2loop*. This is obsolete now that 2block* exists; it is cleaner to write 2(block 1name* ...)* around the 2loop*. Note that every 2loop* generates a 2block* named 2nil*, so the function 2return* can always be used to exit the innermost 2loop* (assuming no other construct generating a 2block* 2nil* intervenes). 2return 1expression** Immediately returns the value of 1expression* as the value of the loop, without running the epilogue code. This is most useful with some sort of conditionalization, as discussed in the previous section. Unlike most of the other clauses, 2return* is not considered to ``generate body code'', so it is allowed to occur between iteration clauses, as in 3(loop for entry in list* 3 when (not (numberp entry))* 3 return (ferror ...)* 3 as frob = (times entry 2)* 3 ...)* Although 2ferror* is called only for effect, 2return* is used so that it can be called from that point in the 2loop*. If one instead desires the loop to have some return value when it finishes normally, one may place a call to the 2return* function in the epilogue (with the 2finally* clause, 4(LOOP-1)Entrance and Exit*).