@node Iteration, Objects, Data and Control Flow, Top @chapter Iteration @menu * The LOOP Facility:: * Iteration Dictionary:: @end menu @node The LOOP Facility, Iteration Dictionary, Iteration, Iteration @section The LOOP Facility @c including concept-loop @menu * Overview of the Loop Facility:: * Variable Initialization and Stepping Clauses:: * Value Accumulation Clauses:: * Termination Test Clauses:: * Unconditional Execution Clauses:: * Conditional Execution Clauses:: * Miscellaneous Clauses:: * Examples of Miscellaneous Loop Features:: * Notes about Loop:: @end menu @node Overview of the Loop Facility, Variable Initialization and Stepping Clauses, The LOOP Facility, The LOOP Facility @subsection Overview of the Loop Facility The @b{loop} @i{macro} performs iteration. @menu * Simple vs Extended Loop:: * Simple Loop:: * Extended Loop:: * Loop Keywords:: * Parsing Loop Clauses:: * Expanding Loop Forms:: * Summary of Loop Clauses:: * Summary of Variable Initialization and Stepping Clauses:: * Summary of Value Accumulation Clauses:: * Summary of Termination Test Clauses:: * Summary of Unconditional Execution Clauses:: * Summary of Conditional Execution Clauses:: * Summary of Miscellaneous Clauses:: * Order of Execution:: * Destructuring:: * Restrictions on Side-Effects:: @end menu @node Simple vs Extended Loop, Simple Loop, Overview of the Loop Facility, Overview of the Loop Facility @subsubsection Simple vs Extended Loop @b{loop} @i{forms} are partitioned into two categories: simple @b{loop} @i{forms} and extended @b{loop} @i{forms}. @node Simple Loop, Extended Loop, Simple vs Extended Loop, Overview of the Loop Facility @subsubsection Simple Loop A simple @b{loop} @i{form} is one that has a body containing only @i{compound forms}. Each @i{form} is @i{evaluated} in turn from left to right. When the last @i{form} has been @i{evaluated}, then the first @i{form} is evaluated again, and so on, in a never-ending cycle. A simple @b{loop} @i{form} establishes an @i{implicit block} named @b{nil}. The execution of a simple @b{loop} can be terminated by explicitly transfering control to the @i{implicit block} (using @b{return} or @b{return-from}) or to some @i{exit point} outside of the @i{block} (@i{e.g.}, using @b{throw}, @b{go}, or @b{return-from}). @node Extended Loop, Loop Keywords, Simple Loop, Overview of the Loop Facility @subsubsection Extended Loop An extended @b{loop} @i{form} is one that has a body containing @i{atomic} @i{expressions}. When the @b{loop} @i{macro} processes such a @i{form}, it invokes a facility that is commonly called ``the Loop Facility.'' The Loop Facility provides standardized access to mechanisms commonly used in iterations through Loop schemas, which are introduced by @i{loop keywords}. The body of an extended @b{loop} @i{form} is divided into @b{loop} clauses, each which is in turn made up of @i{loop keywords} and @i{forms}. @node Loop Keywords, Parsing Loop Clauses, Extended Loop, Overview of the Loop Facility @subsubsection Loop Keywords @i{Loop keywords} are not true @i{keywords}_1; they are special @i{symbols}, recognized by @i{name} rather than @i{object} identity, that are meaningful only to the @b{loop} facility. A @i{loop keyword} is a @i{symbol} but is recognized by its @i{name} (not its identity), regardless of the @i{packages} in which it is @i{accessible}. In general, @i{loop keywords} are not @i{external symbols} of the @t{COMMON-LISP} @i{package}, except in the coincidental situation that a @i{symbol} with the same name as a @i{loop keyword} was needed for some other purpose in @r{Common Lisp}. For example, there is a @i{symbol} in the @t{COMMON-LISP} @i{package} whose @i{name} is @t{"UNLESS"} but not one whose @i{name} is @t{"UNTIL"}. If no @i{loop keywords} are supplied in a @b{loop} @i{form}, the Loop Facility executes the loop body repeatedly; see @ref{Simple Loop}. @node Parsing Loop Clauses, Expanding Loop Forms, Loop Keywords, Overview of the Loop Facility @subsubsection Parsing Loop Clauses The syntactic parts of an extended @b{loop} @i{form} are called clauses; the rules for parsing are determined by that clause's keyword. The following example shows a @b{loop} @i{form} with six clauses: @example (loop for i from 1 to (compute-top-value) ; first clause while (not (unacceptable i)) ; second clause collect (square i) ; third clause do (format t "Working on ~D now" i) ; fourth clause when (evenp i) ; fifth clause do (format t "~D is a non-odd number" i) finally (format t "About to exit!")) ; sixth clause @end example Each @i{loop keyword} introduces either a compound loop clause or a simple loop clause that can consist of a @i{loop keyword} followed by a single @i{form}. The number of @i{forms} in a clause is determined by the @i{loop keyword} that begins the clause and by the auxiliary keywords in the clause. The keywords @t{do}, @t{doing}, @t{initially}, and @t{finally} are the only loop keywords that can take any number of @i{forms} and group them as an @i{implicit progn}. Loop clauses can contain auxiliary keywords, which are sometimes called prepositions. For example, the first clause in the code above includes the prepositions @t{from} and @t{to}, which mark the value from which stepping begins and the value at which stepping ends. For detailed information about @b{loop} syntax, see the @i{macro} @b{loop}. @node Expanding Loop Forms, Summary of Loop Clauses, Parsing Loop Clauses, Overview of the Loop Facility @subsubsection Expanding Loop Forms A @b{loop} @i{macro form} expands into a @i{form} containing one or more binding forms (that @i{establish} @i{bindings} of loop variables) and a @b{block} and a @b{tagbody} (that express a looping control structure). The variables established in @b{loop} are bound as if by @b{let} or @b{lambda}. Implementations can interleave the setting of initial values with the @i{bindings}. However, the assignment of the initial values is always calculated in the order specified by the user. A variable is thus sometimes bound to a meaningless value of the correct @i{type}, and then later in the prologue it is set to the true initial value by using @b{setq}. One implication of this interleaving is that it is @i{implementation-dependent} whether the @i{lexical environment} in which the initial value @i{forms} (variously called the @i{form1}, @i{form2}, @i{form3}, @i{step-fun}, @i{vector}, @i{hash-table}, and @i{package}) in any @i{for-as-subclause}, except @i{for-as-equals-then}, are @i{evaluated} includes only the loop variables preceding that @i{form} or includes more or all of the loop variables; the @i{form1} and @i{form2} in a @i{for-as-equals-then} form includes the @i{lexical environment} of all the loop variables. After the @i{form} is expanded, it consists of three basic parts in the @b{tagbody}: the loop prologue, the loop body, and the loop epilogue. @table @asis @item @b{Loop prologue} The loop prologue contains @i{forms} that are executed before iteration begins, such as any automatic variable initializations prescribed by the @i{variable} clauses, along with any @t{initially} clauses in the order they appear in the source. @item @b{Loop body} The loop body contains those @i{forms} that are executed during iteration, including application-specific calculations, termination tests, and variable @i{stepping}_1. @item @b{Loop epilogue} The loop epilogue contains @i{forms} that are executed after iteration terminates, such as @t{finally} clauses, if any, along with any implicit return value from an @i{accumulation} clause or an @i{termination-test} clause. @end table Some clauses from the source @i{form} contribute code only to the loop prologue; these clauses must come before other clauses that are in the main body of the @b{loop} form. Others contribute code only to the loop epilogue. All other clauses contribute to the final translated @i{form} in the same order given in the original source @i{form} of the @b{loop}. Expansion of the @b{loop} macro produces an @i{implicit block} named @b{nil} unless @t{named} is supplied. Thus, @b{return-from} (and sometimes @b{return}) can be used to return values from @b{loop} or to exit @b{loop}. @node Summary of Loop Clauses, Summary of Variable Initialization and Stepping Clauses, Expanding Loop Forms, Overview of the Loop Facility @subsubsection Summary of Loop Clauses Loop clauses fall into one of the following categories: @node Summary of Variable Initialization and Stepping Clauses, Summary of Value Accumulation Clauses, Summary of Loop Clauses, Overview of the Loop Facility @subsubsection Summary of Variable Initialization and Stepping Clauses The @t{for} and @t{as} constructs provide iteration control clauses that establish a variable to be initialized. @t{for} and @t{as} clauses can be combined with the loop keyword @t{and} to get @i{parallel} initialization and @i{stepping}_1. Otherwise, the initialization and @i{stepping}_1 are @i{sequential}. The @t{with} construct is similar to a single @b{let} clause. @t{with} clauses can be combined using the @i{loop keyword} @t{and} to get @i{parallel} initialization. For more information, see @ref{Variable Initialization and Stepping Clauses}. @node Summary of Value Accumulation Clauses, Summary of Termination Test Clauses, Summary of Variable Initialization and Stepping Clauses, Overview of the Loop Facility @subsubsection Summary of Value Accumulation Clauses The @t{collect} (or @t{collecting}) construct takes one @i{form} in its clause and adds the value of that @i{form} to the end of a @i{list} of values. By default, the @i{list} of values is returned when the @b{loop} finishes. The @t{append} (or @t{appending}) construct takes one @i{form} in its clause and appends the value of that @i{form} to the end of a @i{list} of values. By default, the @i{list} of values is returned when the @b{loop} finishes. The @t{nconc} (or @t{nconcing}) construct is similar to the @t{append} construct, but its @i{list} values are concatenated as if by the function @t{nconc}. By default, the @i{list} of values is returned when the @b{loop} finishes. The @t{sum} (or @t{summing}) construct takes one @i{form} in its clause that must evaluate to a @i{number} and accumulates the sum of all these @i{numbers}. By default, the cumulative sum is returned when the @b{loop} finishes. The @t{count} (or @t{counting}) construct takes one @i{form} in its clause and counts the number of times that the @i{form} evaluates to @i{true}. By default, the count is returned when the @b{loop} finishes. The @t{minimize} (or @t{minimizing}) construct takes one @i{form} in its clause and determines the minimum value obtained by evaluating that @i{form}. By default, the minimum value is returned when the @b{loop} finishes. The @t{maximize} (or @t{maximizing}) construct takes one @i{form} in its clause and determines the maximum value obtained by evaluating that @i{form}. By default, the maximum value is returned when the @b{loop} finishes. For more information, see @ref{Value Accumulation Clauses}. @node Summary of Termination Test Clauses, Summary of Unconditional Execution Clauses, Summary of Value Accumulation Clauses, Overview of the Loop Facility @subsubsection Summary of Termination Test Clauses The @t{for} and @t{as} constructs provide a termination test that is determined by the iteration control clause. The @t{repeat} construct causes termination after a specified number of iterations. (It uses an internal variable to keep track of the number of iterations.) The @t{while} construct takes one @i{form}, a @i{test}, and terminates the iteration if the @i{test} evaluates to @i{false}. A @t{while} clause is equivalent to the expression @t{(if (not @i{test}) (loop-finish))}. The @t{until} construct is the inverse of @t{while}; it terminates the iteration if the @i{test} evaluates to any @i{non-nil} value. An @t{until} clause is equivalent to the expression @t{(if @i{test} (loop-finish))}. The @t{always} construct takes one @i{form} and terminates the @b{loop} if the @i{form} ever evaluates to @i{false}; in this case, the @b{loop} @i{form} returns @b{nil}. Otherwise, it provides a default return value of @b{t}. The @t{never} construct takes one @i{form} and terminates the @b{loop} if the @i{form} ever evaluates to @i{true}; in this case, the @b{loop} @i{form} returns @b{nil}. Otherwise, it provides a default return value of @b{t}. The @t{thereis} construct takes one @i{form} and terminates the @b{loop} if the @i{form} ever evaluates to a @i{non-nil} @i{object}; in this case, the @b{loop} @i{form} returns that @i{object}. Otherwise, it provides a default return value of @b{nil}. If multiple termination test clauses are specified, the @b{loop} @i{form} terminates if any are satisfied. For more information, see @ref{Termination Test Clauses}. @node Summary of Unconditional Execution Clauses, Summary of Conditional Execution Clauses, Summary of Termination Test Clauses, Overview of the Loop Facility @subsubsection Summary of Unconditional Execution Clauses The @t{do} (or @t{doing}) construct evaluates all @i{forms} in its clause. The @t{return} construct takes one @i{form}. Any @i{values} returned by the @i{form} are immediately returned by the @b{loop} form. It is equivalent to the clause @t{do (return-from @i{block-name} @i{value})}, where @i{block-name} is the name specified in a @t{named} clause, or @b{nil} if there is no @t{named} clause. For more information, see @ref{Unconditional Execution Clauses}. @node Summary of Conditional Execution Clauses, Summary of Miscellaneous Clauses, Summary of Unconditional Execution Clauses, Overview of the Loop Facility @subsubsection Summary of Conditional Execution Clauses The @t{if} and @t{when} constructs take one @i{form} as a test and a clause that is executed when the test @i{yields} @i{true}. The clause can be a value accumulation, unconditional, or another conditional clause; it can also be any combination of such clauses connected by the @b{loop} @t{and} keyword. The @b{loop} @t{unless} construct is similar to the @b{loop} @t{when} construct except that it complements the test result. The @b{loop} @t{else} construct provides an optional component of @t{if}, @t{when}, and @t{unless} clauses that is executed when an @t{if} or @t{when} test @i{yields} @i{false} or when an @t{unless} test @i{yields} @i{true}. The component is one of the clauses described under @t{if}. The @b{loop} @t{end} construct provides an optional component to mark the end of a conditional clause. For more information, see @ref{Conditional Execution Clauses}. @node Summary of Miscellaneous Clauses, Order of Execution, Summary of Conditional Execution Clauses, Overview of the Loop Facility @subsubsection Summary of Miscellaneous Clauses The @b{loop} @t{named} construct gives a name for the @i{block} of the loop. The @b{loop} @t{initially} construct causes its @i{forms} to be evaluated in the loop prologue, which precedes all @b{loop} code except for initial settings supplied by the constructs @t{with}, @t{for}, or @t{as}. The @b{loop} @t{finally} construct causes its @i{forms} to be evaluated in the loop epilogue after normal iteration terminates. For more information, see @ref{Miscellaneous Clauses}. @node Order of Execution, Destructuring, Summary of Miscellaneous Clauses, Overview of the Loop Facility @subsubsection Order of Execution @ITindex{order of evaluation} @ITindex{evaluation order} With the exceptions listed below, clauses are executed in the loop body in the order in which they appear in the source. Execution is repeated until a clause terminates the @b{loop} or until a @b{return}, @b{go}, or @b{throw} form is encountered which transfers control to a point outside of the loop. The following actions are exceptions to the linear order of execution: @table @asis @item @t{*} All variables are initialized first, regardless of where the establishing clauses appear in the source. The order of initialization follows the order of these clauses. @item @t{*} The code for any @t{initially} clauses is collected into one @b{progn} in the order in which the clauses appear in the source. The collected code is executed once in the loop prologue after any implicit variable initializations. @item @t{*} The code for any @t{finally} clauses is collected into one @b{progn} in the order in which the clauses appear in the source. The collected code is executed once in the loop epilogue before any implicit values from the accumulation clauses are returned. Explicit returns anywhere in the source, however, will exit the @b{loop} without executing the epilogue code. @item @t{*} A @t{with} clause introduces a variable @i{binding} and an optional initial value. The initial values are calculated in the order in which the @t{with} clauses occur. @item @t{*} Iteration control clauses implicitly perform the following actions: @table @asis @item -- initialize variables; @item -- @i{step} variables, generally between each execution of the loop body; @item -- perform termination tests, generally just before the execution of the loop body. @end table @end table @node Destructuring, Restrictions on Side-Effects, Order of Execution, Overview of the Loop Facility @subsubsection Destructuring The @i{d-type-spec} argument is used for destructuring. If the @i{d-type-spec} argument consists solely of the @i{type} @b{fixnum}, @b{float}, @b{t}, or @b{nil}, the @t{of-type} keyword is optional. The @t{of-type} construct is optional in these cases to provide backwards compatibility; thus, the following two expressions are the same: @example ;;; This expression uses the old syntax for type specifiers. (loop for i fixnum upfrom 3 ...) ;;; This expression uses the new syntax for type specifiers. (loop for i of-type fixnum upfrom 3 ...) ;; Declare X and Y to be of type VECTOR and FIXNUM respectively. (loop for (x y) of-type (vector fixnum) in l do ...) @end example A @i{type specifier} for a destructuring pattern is a @i{tree} of @i{type specifiers} with the same shape as the @i{tree} of @i{variable} @i{names}, with the following exceptions: @table @asis @item @t{*} When aligning the @i{trees}, an @i{atom} in the @i{tree} of @i{type specifiers} that matches a @i{cons} in the variable tree declares the same @i{type} for each variable in the subtree rooted at the @i{cons}. @item @t{*} A @i{cons} in the @i{tree} of @i{type specifiers} that matches an @i{atom} in the @i{tree} of @i{variable} @i{names} is a @i{compound type specifer}. @end table Destructuring allows @i{binding} of a set of variables to a corresponding set of values anywhere that a value can normally be bound to a single variable. During @b{loop} expansion, each variable in the variable list is matched with the values in the values list. If there are more variables in the variable list than there are values in the values list, the remaining variables are given a value of @b{nil}. If there are more values than variables listed, the extra values are discarded. To assign values from a list to the variables @t{a}, @t{b}, and @t{c}, the @t{for} clause could be used to bind the variable @t{numlist} to the @i{car} of the supplied @i{form}, and then another @t{for} clause could be used to bind the variables @t{a}, @t{b}, and @t{c} @i{sequentially}. @example ;; Collect values by using FOR constructs. (loop for numlist in '((1 2 4.0) (5 6 8.3) (8 9 10.4)) for a of-type integer = (first numlist) and b of-type integer = (second numlist) and c of-type float = (third numlist) collect (list c b a)) @result{} ((4.0 2 1) (8.3 6 5) (10.4 9 8)) @end example Destructuring makes this process easier by allowing the variables to be bound in each loop iteration. @i{Types} can be declared by using a list of @i{type-spec} arguments. If all the @i{types} are the same, a shorthand destructuring syntax can be used, as the second example illustrates. @example ;; Destructuring simplifies the process. (loop for (a b c) of-type (integer integer float) in '((1 2 4.0) (5 6 8.3) (8 9 10.4)) collect (list c b a)) @result{} ((4.0 2 1) (8.3 6 5) (10.4 9 8)) ;; If all the types are the same, this way is even simpler. (loop for (a b c) of-type float in '((1.0 2.0 4.0) (5.0 6.0 8.3) (8.0 9.0 10.4)) collect (list c b a)) @result{} ((4.0 2.0 1.0) (8.3 6.0 5.0) (10.4 9.0 8.0)) @end example If destructuring is used to declare or initialize a number of groups of variables into @i{types}, the @i{loop keyword} @t{and} can be used to simplify the process further. @example ;; Initialize and declare variables in parallel by using the AND construct.\kern-7pt (loop with (a b) of-type float = '(1.0 2.0) and (c d) of-type integer = '(3 4) and (e f) return (list a b c d e f)) @result{} (1.0 2.0 3 4 NIL NIL) @end example If @b{nil} is used in a destructuring list, no variable is provided for its place. @example (loop for (a nil b) = '(1 2 3) do (return (list a b))) @result{} (1 3) @end example Note that @i{dotted lists} can specify destructuring. @example (loop for (x . y) = '(1 . 2) do (return y)) @result{} 2 (loop for ((a . b) (c . d)) of-type ((float . float) (integer . integer)) in '(((1.2 . 2.4) (3 . 4)) ((3.4 . 4.6) (5 . 6))) collect (list a b c d)) @result{} ((1.2 2.4 3 4) (3.4 4.6 5 6)) @end example An error of @i{type} @b{program-error} is signaled (at macro expansion time) if the same variable is bound twice in any variable-binding clause of a single @b{loop} expression. Such variables include local variables, iteration control variables, and variables found by destructuring. @node Restrictions on Side-Effects, , Destructuring, Overview of the Loop Facility @subsubsection Restrictions on Side-Effects See @ref{Traversal Rules and Side Effects}. @node Variable Initialization and Stepping Clauses, Value Accumulation Clauses, Overview of the Loop Facility, The LOOP Facility @subsection Variable Initialization and Stepping Clauses @menu * Iteration Control:: * The for-as-arithmetic subclause:: * Examples of for-as-arithmetic subclause:: * The for-as-in-list subclause:: * Examples of for-as-in-list subclause:: * The for-as-on-list subclause:: * Examples of for-as-on-list subclause:: * The for-as-equals-then subclause:: * Examples of for-as-equals-then subclause:: * The for-as-across subclause:: * Examples of for-as-across subclause:: * The for-as-hash subclause:: * The for-as-package subclause:: * Examples of for-as-package subclause:: * Local Variable Initializations:: * Examples of WITH clause:: @end menu @node Iteration Control, The for-as-arithmetic subclause, Variable Initialization and Stepping Clauses, Variable Initialization and Stepping Clauses @subsubsection Iteration Control Iteration control clauses allow direction of @b{loop} iteration. The @i{loop keywords} @t{for} and @t{as} designate iteration control clauses. Iteration control clauses differ with respect to the specification of termination tests and to the initialization and @i{stepping}_1 of loop variables. Iteration clauses by themselves do not cause the Loop Facility to return values, but they can be used in conjunction with value-accumulation clauses to return values. All variables are initialized in the loop prologue. A @i{variable} @i{binding} has @i{lexical scope} unless it is proclaimed @b{special}; thus, by default, the variable can be @i{accessed} only by @i{forms} that lie textually within the @b{loop}. Stepping assignments are made in the loop body before any other @i{forms} are evaluated in the body. The variable argument in iteration control clauses can be a destructuring list. A destructuring list is a @i{tree} whose @i{non-nil} @i{atoms} are @i{variable} @i{names}. See @ref{Destructuring}. The iteration control clauses @t{for}, @t{as}, and @t{repeat} must precede any other loop clauses, except @t{initially}, @t{with}, and @t{named}, since they establish variable @i{bindings}. When iteration control clauses are used in a @b{loop}, the corresponding termination tests in the loop body are evaluated before any other loop body code is executed. If multiple iteration clauses are used to control iteration, variable initialization and @i{stepping}_1 occur @i{sequentially} by default. The @t{and} construct can be used to connect two or more iteration clauses when @i{sequential} @i{binding} and @i{stepping}_1 are not necessary. The iteration behavior of clauses joined by @t{and} is analogous to the behavior of the macro @b{do} with respect to @b{do*}. The @t{for} and @t{as} clauses iterate by using one or more local loop variables that are initialized to some value and that can be modified or @i{stepped}_1 after each iteration. For these clauses, iteration terminates when a local variable reaches some supplied value or when some other loop clause terminates iteration. At each iteration, variables can be @i{stepped}_1 by an increment or a decrement or can be assigned a new value by the evaluation of a @i{form}). Destructuring can be used to assign values to variables during iteration. The @t{for} and @t{as} keywords are synonyms; they can be used interchangeably. There are seven syntactic formats for these constructs. In each syntactic format, the @i{type} of @i{var} can be supplied by the optional @i{type-spec} argument. If @i{var} is a destructuring list, the @i{type} supplied by the @i{type-spec} argument must appropriately match the elements of the list. By convention, @t{for} introduces new iterations and @t{as} introduces iterations that depend on a previous iteration specification. @node The for-as-arithmetic subclause, Examples of for-as-arithmetic subclause, Iteration Control, Variable Initialization and Stepping Clauses @subsubsection The for-as-arithmetic subclause In the @i{for-as-arithmetic} subclause, the @t{for} or @t{as} construct iterates from the value supplied by @i{form1} to the value supplied by @i{form2} in increments or decrements denoted by @i{form3}. Each expression is evaluated only once and must evaluate to a @i{number}. The variable @i{var} is bound to the value of @i{form1} in the first iteration and is @i{stepped}_1 by the value of @i{form3} in each succeeding iteration, or by 1 if @i{form3} is not provided. The following @i{loop keywords} serve as valid prepositions within this syntax. At least one of the prepositions must be used; and at most one from each line may be used in a single subclause. @table @asis @item from | downfrom | upfrom @item to | downto | upto | below | above @item by @end table The prepositional phrases in each subclause may appear in any order. For example, either ``@t{from x by y}'' or ``@t{by y from x}'' is permitted. However, because left-to-right order of evaluation is preserved, the effects will be different in the case of side effects. @ITindex{order of evaluation} @ITindex{evaluation order} Consider: @example (let ((x 1)) (loop for i from x by (incf x) to 10 collect i)) @result{} (1 3 5 7 9) (let ((x 1)) (loop for i by (incf x) from x to 10 collect i)) @result{} (2 4 6 8 10) @end example The descriptions of the prepositions follow: @table @asis @item from The @i{loop keyword} @t{from} specifies the value from which @i{stepping}_1 begins, as supplied by @i{form1}. @i{Stepping}_1 is incremental by default. If decremental @i{stepping}_1 is desired, the preposition @t{downto} or @t{above} must be used with @i{form2}. For incremental @i{stepping}_1, the default @t{from} value is 0. @item downfrom, upfrom The @i{loop keyword} @t{downfrom} indicates that the variable @i{var} is decreased in decrements supplied by @i{form3}; the @i{loop keyword} @t{upfrom} indicates that @i{var} is increased in increments supplied by @i{form3}. @item to The @i{loop keyword} @t{to} marks the end value for @i{stepping}_1 supplied in @i{form2}. @i{Stepping}_1 is incremental by default. If decremental @i{stepping}_1 is desired, the preposition @t{downfrom} must be used with @i{form1}, or else the preposition @t{downto} or @t{above} should be used instead of @t{to} with @i{form2}. @item downto, upto The @i{loop keyword} @t{downto} specifies decremental @i{stepping}; the @i{loop keyword} @t{upto} specifies incremental @i{stepping}. In both cases, the amount of change on each step is specified by @i{form3}, and the @b{loop} terminates when the variable @i{var} passes the value of @i{form2}. Since there is no default for @i{form1} in decremental @i{stepping}_1, a @i{form1} value must be supplied (using @t{from} or @t{downfrom}) when @t{downto} is supplied. @item below, above The @i{loop keywords} @t{below} and @t{above} are analogous to @t{upto} and @t{downto} respectively. These keywords stop iteration just before the value of the variable @i{var} reaches the value supplied by @i{form2}; the end value of @i{form2} is not included. Since there is no default for @i{form1} in decremental @i{stepping}_1, a @i{form1} value must be supplied (using @t{from} or @t{downfrom}) when @t{above} is supplied. @item by The @i{loop keyword} @t{by} marks the increment or decrement supplied by @i{form3}. The value of @i{form3} can be any positive @i{number}. The default value is 1. @end table In an iteration control clause, the @t{for} or @t{as} construct causes termination when the supplied limit is reached. That is, iteration continues until the value @i{var} is stepped to the exclusive or inclusive limit supplied by @i{form2}. The range is exclusive if @i{form3} increases or decreases @i{var} to the value of @i{form2} without reaching that value; the loop keywords @t{below} and @t{above} provide exclusive limits. An inclusive limit allows @i{var} to attain the value of @i{form2}; @t{to}, @t{downto}, and @t{upto} provide inclusive limits. @node Examples of for-as-arithmetic subclause, The for-as-in-list subclause, The for-as-arithmetic subclause, Variable Initialization and Stepping Clauses @subsubsection Examples of for-as-arithmetic subclause @example ;; Print some numbers. (loop for i from 1 to 3 do (print i)) @t{ |> } 1 @t{ |> } 2 @t{ |> } 3 @result{} NIL ;; Print every third number. (loop for i from 10 downto 1 by 3 do (print i)) @t{ |> } 10 @t{ |> } 7 @t{ |> } 4 @t{ |> } 1 @result{} NIL ;; Step incrementally from the default starting value. (loop for i below 3 do (print i)) @t{ |> } 0 @t{ |> } 1 @t{ |> } 2 @result{} NIL @end example @node The for-as-in-list subclause, Examples of for-as-in-list subclause, Examples of for-as-arithmetic subclause, Variable Initialization and Stepping Clauses @subsubsection The for-as-in-list subclause In the @i{for-as-in-list} subclause, the @t{for} or @t{as} construct iterates over the contents of a @i{list}. It checks for the end of the @i{list} as if by using @b{endp}. The variable @i{var} is bound to the successive elements of the @i{list} in @i{form1} before each iteration. At the end of each iteration, the function @i{step-fun} is applied to the @i{list}; the default value for @i{step-fun} is @b{cdr}. The @i{loop keywords} @t{in} and @t{by} serve as valid prepositions in this syntax. The @t{for} or @t{as} construct causes termination when the end of the @i{list} is reached. @node Examples of for-as-in-list subclause, The for-as-on-list subclause, The for-as-in-list subclause, Variable Initialization and Stepping Clauses @subsubsection Examples of for-as-in-list subclause @example ;; Print every item in a list. (loop for item in '(1 2 3) do (print item)) @t{ |> } 1 @t{ |> } 2 @t{ |> } 3 @result{} NIL ;; Print every other item in a list. (loop for item in '(1 2 3 4 5) by #'cddr do (print item)) @t{ |> } 1 @t{ |> } 3 @t{ |> } 5 @result{} NIL ;; Destructure a list, and sum the x values using fixnum arithmetic. (loop for (item . x) of-type (t . fixnum) in '((A . 1) (B . 2) (C . 3)) unless (eq item 'B) sum x) @result{} 4 @end example @node The for-as-on-list subclause, Examples of for-as-on-list subclause, Examples of for-as-in-list subclause, Variable Initialization and Stepping Clauses @subsubsection The for-as-on-list subclause In the @i{for-as-on-list} subclause, the @t{for} or @t{as} construct iterates over a @i{list}. It checks for the end of the @i{list} as if by using @b{atom}. The variable @i{var} is bound to the successive tails of the @i{list} in @i{form1}. At the end of each iteration, the function @i{step-fun} is applied to the @i{list}; the default value for @i{step-fun} is @b{cdr}. The @i{loop keywords} @t{on} and @t{by} serve as valid prepositions in this syntax. The @t{for} or @t{as} construct causes termination when the end of the @i{list} is reached. @node Examples of for-as-on-list subclause, The for-as-equals-then subclause, The for-as-on-list subclause, Variable Initialization and Stepping Clauses @subsubsection Examples of for-as-on-list subclause @example ;; Collect successive tails of a list. (loop for sublist on '(a b c d) collect sublist) @result{} ((A B C D) (B C D) (C D) (D)) ;; Print a list by using destructuring with the loop keyword ON. (loop for (item) on '(1 2 3) do (print item)) @t{ |> } 1 @t{ |> } 2 @t{ |> } 3 @result{} NIL @end example @node The for-as-equals-then subclause, Examples of for-as-equals-then subclause, Examples of for-as-on-list subclause, Variable Initialization and Stepping Clauses @subsubsection The for-as-equals-then subclause In the @i{for-as-equals-then} subclause the @t{for} or @t{as} construct initializes the variable @i{var} by setting it to the result of evaluating @i{form1} on the first iteration, then setting it to the result of evaluating @i{form2} on the second and subsequent iterations. If @i{form2} is omitted, the construct uses @i{form1} on the second and subsequent iterations. The @i{loop keywords} {=} and @t{then} serve as valid prepositions in this syntax. This construct does not provide any termination tests. @node Examples of for-as-equals-then subclause, The for-as-across subclause, The for-as-equals-then subclause, Variable Initialization and Stepping Clauses @subsubsection Examples of for-as-equals-then subclause @example ;; Collect some numbers. (loop for item = 1 then (+ item 10) for iteration from 1 to 5 collect item) @result{} (1 11 21 31 41) @end example @node The for-as-across subclause, Examples of for-as-across subclause, Examples of for-as-equals-then subclause, Variable Initialization and Stepping Clauses @subsubsection The for-as-across subclause In the @i{for-as-across} subclause the @t{for} or @t{as} construct binds the variable @i{var} to the value of each element in the array @i{vector}. The @i{loop keyword} @t{across} marks the array @i{vector}; @t{across} is used as a preposition in this syntax. Iteration stops when there are no more elements in the supplied @i{array} that can be referenced. Some implementations might recognize a @b{the} special form in the @i{vector} form to produce more efficient code. @node Examples of for-as-across subclause, The for-as-hash subclause, The for-as-across subclause, Variable Initialization and Stepping Clauses @subsubsection Examples of for-as-across subclause @example (loop for char across (the simple-string (find-message channel)) do (write-char char stream)) @end example @node The for-as-hash subclause, The for-as-package subclause, Examples of for-as-across subclause, Variable Initialization and Stepping Clauses @subsubsection The for-as-hash subclause In the @i{for-as-hash} subclause the @t{for} or @t{as} construct iterates over the elements, keys, and values of a @i{hash-table}. In this syntax, a compound preposition is used to designate access to a @i{hash table}. The variable @i{var} takes on the value of each hash key or hash value in the supplied @i{hash-table}. The following @i{loop keywords} serve as valid prepositions within this syntax: @table @asis @item @t{being} The keyword @t{being} introduces either the Loop schema @t{hash-key} or @t{hash-value}. @item @t{each}, @t{the} The @i{loop keyword} @t{each} follows the @i{loop keyword} @t{being} when @t{hash-key} or @t{hash-value} is used. The @i{loop keyword} @t{the} is used with @t{hash-keys} and @t{hash-values} only for ease of reading. This agreement isn't required. @item @t{hash-key}, @t{hash-keys} These @i{loop keywords} access each key entry of the @i{hash table}. If the name @t{hash-value} is supplied in a @t{using} construct with one of these Loop schemas, the iteration can optionally access the keyed value. The order in which the keys are accessed is undefined; empty slots in the @i{hash table} are ignored. @item @t{hash-value}, @t{hash-values} These @i{loop keywords} access each value entry of a @i{hash table}. If the name @t{hash-key} is supplied in a @t{using} construct with one of these Loop schemas, the iteration can optionally access the key that corresponds to the value. The order in which the keys are accessed is undefined; empty slots in the @i{hash table} are ignored. @item @t{using} The @i{loop keyword} @t{using} introduces the optional key or the keyed value to be accessed. It allows access to the hash key if iteration is over the hash values, and the hash value if iteration is over the hash keys. @item @t{in}, @t{of} These loop prepositions introduce @i{hash-table}. @end table In effect @t{being} @{{each} | @t{the}@} @{{hash-value} | @t{hash-values} | @t{hash-key} | @t{hash-keys}@} @{{in} | @t{of}@} is a compound preposition. Iteration stops when there are no more hash keys or hash values to be referenced in the supplied @i{hash-table}. @node The for-as-package subclause, Examples of for-as-package subclause, The for-as-hash subclause, Variable Initialization and Stepping Clauses @subsubsection The for-as-package subclause In the @i{for-as-package} subclause the @t{for} or @t{as} construct iterates over the @i{symbols} in a @i{package}. In this syntax, a compound preposition is used to designate access to a @i{package}. The variable @i{var} takes on the value of each @i{symbol} in the supplied @i{package}. The following @i{loop keywords} serve as valid prepositions within this syntax: @table @asis @item @t{being} The keyword @t{being} introduces either the Loop schema @t{symbol}, @t{present-symbol}, or @t{external-symbol}. @item @t{each}, @t{the} The @i{loop keyword} @t{each} follows the @i{loop keyword} @t{being} when @t{symbol}, @t{present-symbol}, or @t{external-symbol} is used. The @i{loop keyword} @t{the} is used with @t{symbols}, @t{present-symbols}, and @t{external-symbols} only for ease of reading. This agreement isn't required. @item @t{present-symbol}, @t{present-symbols} These Loop schemas iterate over the @i{symbols} that are @i{present} in a @i{package}. The @i{package} to be iterated over is supplied in the same way that @i{package} arguments to @b{find-package} are supplied. If the @i{package} for the iteration is not supplied, the @i{current package} is used. If a @i{package} that does not exist is supplied, an error of @i{type} @b{package-error} is signaled. @item @t{symbol}, @t{symbols} These Loop schemas iterate over @i{symbols} that are @i{accessible} in a given @i{package}. The @i{package} to be iterated over is supplied in the same way that @i{package} arguments to @b{find-package} are supplied. If the @i{package} for the iteration is not supplied, the @i{current package} is used. If a @i{package} that does not exist is supplied, an error of @i{type} @b{package-error} is signaled. @item @t{external-symbol}, @t{external-symbols} These Loop schemas iterate over the @i{external symbols} of a @i{package}. The @i{package} to be iterated over is supplied in the same way that @i{package} arguments to @b{find-package} are supplied. If the @i{package} for the iteration is not supplied, the @i{current package} is used. If a @i{package} that does not exist is supplied, an error of @i{type} @b{package-error} is signaled. @item @t{in}, @t{of} These loop prepositions introduce @i{package}. @end table In effect @t{being} @{{each} | @t{the}@} @{{symbol} | @t{symbols} | @t{present-symbol} | @t{present-symbols} | @t{external-symbol} | @t{external-symbols}@} @{{in} | @t{of}@} is a compound preposition. Iteration stops when there are no more @i{symbols} to be referenced in the supplied @i{package}. @node Examples of for-as-package subclause, Local Variable Initializations, The for-as-package subclause, Variable Initialization and Stepping Clauses @subsubsection Examples of for-as-package subclause @example (let ((*package* (make-package "TEST-PACKAGE-1"))) ;; For effect, intern some symbols (read-from-string "(THIS IS A TEST)") (export (intern "THIS")) (loop for x being each present-symbol of *package* do (print x))) @t{ |> } A @t{ |> } TEST @t{ |> } THIS @t{ |> } IS @result{} NIL @end example @node Local Variable Initializations, Examples of WITH clause, Examples of for-as-package subclause, Variable Initialization and Stepping Clauses @subsubsection Local Variable Initializations When a @b{loop} @i{form} is executed, the local variables are bound and are initialized to some value. These local variables exist until @b{loop} iteration terminates, at which point they cease to exist. Implicit variables are also established by iteration control clauses and the @t{into} preposition of accumulation clauses. The @t{with} construct initializes variables that are local to a loop. The variables are initialized one time only. If the optional @i{type-spec} argument is supplied for the variable @i{var}, but there is no related expression to be evaluated, @i{var} is initialized to an appropriate default value for its @i{type}. For example, for the types @b{t}, @b{number}, and @b{float}, the default values are @b{nil}, @t{0}, and @t{0.0} respectively. The consequences are undefined if a @i{type-spec} argument is supplied for @i{var} if the related expression returns a value that is not of the supplied @i{type}. By default, the @t{with} construct initializes variables @i{sequentially}; that is, one variable is assigned a value before the next expression is evaluated. However, by using the @i{loop keyword} @t{and} to join several @t{with} clauses, initializations can be forced to occur in @i{parallel}; that is, all of the supplied @i{forms} are evaluated, and the results are bound to the respective variables simultaneously. @i{Sequential} @i{binding} is used when it is desireable for the initialization of some variables to depend on the values of previously bound variables. For example, suppose the variables @t{a}, @t{b}, and @t{c} are to be bound in sequence: @example (loop with a = 1 with b = (+ a 2) with c = (+ b 3) return (list a b c)) @result{} (1 3 6) @end example The execution of the above @b{loop} is equivalent to the execution of the following code: @example (block nil (let* ((a 1) (b (+ a 2)) (c (+ b 3))) (tagbody (next-loop (return (list a b c)) (go next-loop) end-loop)))) @end example If the values of previously bound variables are not needed for the initialization of other local variables, an @t{and} clause can be used to specify that the bindings are to occur in @i{parallel}: @example (loop with a = 1 and b = 2 and c = 3 return (list a b c)) @result{} (1 2 3) @end example The execution of the above loop is equivalent to the execution of the following code: @example (block nil (let ((a 1) (b 2) (c 3)) (tagbody (next-loop (return (list a b c)) (go next-loop) end-loop)))) @end example @node Examples of WITH clause, , Local Variable Initializations, Variable Initialization and Stepping Clauses @subsubsection Examples of WITH clause @example ;; These bindings occur in sequence. (loop with a = 1 with b = (+ a 2) with c = (+ b 3) return (list a b c)) @result{} (1 3 6) ;; These bindings occur in parallel. (setq a 5 b 10) @result{} 10 (loop with a = 1 and b = (+ a 2) and c = (+ b 3) return (list a b c)) @result{} (1 7 13) ;; This example shows a shorthand way to declare local variables ;; that are of different types. (loop with (a b c) of-type (float integer float) return (format nil "~A ~A ~A" a b c)) @result{} "0.0 0 0.0" ;; This example shows a shorthand way to declare local variables ;; that are the same type. (loop with (a b c) of-type float return (format nil "~A ~A ~A" a b c)) @result{} "0.0 0.0 0.0" @end example @node Value Accumulation Clauses, Termination Test Clauses, Variable Initialization and Stepping Clauses, The LOOP Facility @subsection Value Accumulation Clauses The constructs @t{collect}, @t{collecting}, @t{append}, @t{appending}, @t{nconc}, @t{nconcing}, @t{count}, @t{counting}, @t{maximize}, @t{maximizing}, @t{minimize}, @t{minimizing}, @t{sum}, and @t{summing}, allow values to be accumulated in a @b{loop}. The constructs @t{collect}, @t{collecting}, @t{append}, @t{appending}, @t{nconc}, and @t{nconcing}, designate clauses that accumulate values in @i{lists} and return them. The constructs @t{count}, @t{counting}, @t{maximize}, @t{maximizing}, @t{minimize}, @t{minimizing}, @t{sum}, and @t{summing} designate clauses that accumulate and return numerical values. During each iteration, the constructs @t{collect} and @t{collecting} collect the value of the supplied @i{form} into a @i{list}. When iteration terminates, the @i{list} is returned. The argument @i{var} is set to the @i{list} of collected values; if @i{var} is supplied, the @b{loop} does not return the final @i{list} automatically. If @i{var} is not supplied, it is equivalent to supplying an internal name for @i{var} and returning its value in a @t{finally} clause. The @i{var} argument is bound as if by the construct @t{with}. No mechanism is provided for declaring the @i{type} of @i{var}; it must be of @i{type} @b{list}. The constructs @t{append}, @t{appending}, @t{nconc}, and @t{nconcing} are similar to @t{collect} except that the values of the supplied @i{form} must be @i{lists}. @table @asis @item @t{*} The @t{append} keyword causes its @i{list} values to be concatenated into a single @i{list}, as if they were arguments to the @i{function} @b{append}. @item @t{*} The @t{nconc} keyword causes its @i{list} values to be concatenated into a single @i{list}, as if they were arguments to the @i{function} @b{nconc}. @end table The argument @i{var} is set to the @i{list} of concatenated values; if @i{var} is supplied, @b{loop} does not return the final @i{list} automatically. The @i{var} argument is bound as if by the construct @t{with}. A @i{type} cannot be supplied for @i{var}; it must be of @i{type} @b{list}. The construct @t{nconc} destructively modifies its argument @i{lists}. The @t{count} construct counts the number of times that the supplied @i{form} returns @i{true}. The argument @i{var} accumulates the number of occurrences; if @i{var} is supplied, @b{loop} does not return the final count automatically. The @i{var} argument is bound as if by the construct @t{with} to a zero of the appropriate type. Subsequent values (including any necessary coercions) are computed as if by the function @b{1+}. If @t{into} @i{var} is used, a @i{type} can be supplied for @i{var} with the @i{type-spec} argument; the consequences are unspecified if a nonnumeric @i{type} is supplied. If there is no @t{into} variable, the optional @i{type-spec} argument applies to the internal variable that is keeping the count. The default @i{type} is @i{implementation-dependent}; but it must be a @i{supertype} of @i{type} @b{fixnum}. The @t{maximize} and @t{minimize} constructs compare the value of the supplied @i{form} obtained during the first iteration with values obtained in successive iterations. The maximum (for @t{maximize}) or minimum (for @t{minimize}) value encountered is determined (as if by the @i{function} @b{max} for @t{maximize} and as if by the @i{function} @b{min} for @t{minimize}) and returned. If the @t{maximize} or @t{minimize} clause is never executed, the accumulated value is unspecified. The argument @i{var} accumulates the maximum or minimum value; if @i{var} is supplied, @b{loop} does not return the maximum or minimum automatically. The @i{var} argument is bound as if by the construct @t{with}. If @t{into} @i{var} is used, a @i{type} can be supplied for @i{var} with the @i{type-spec} argument; the consequences are unspecified if a nonnumeric @i{type} is supplied. If there is no @t{into} variable, the optional @i{type-spec} argument applies to the internal variable that is keeping the maximum or minimum value. The default @i{type} is @i{implementation-dependent}; but it must be a @i{supertype} of @i{type} @b{real}. The @t{sum} construct forms a cumulative sum of the successive @i{primary values} of the supplied @i{form} at each iteration. The argument @i{var} is used to accumulate the sum; if @i{var} is supplied, @b{loop} does not return the final sum automatically. The @i{var} argument is bound as if by the construct @t{with} to a zero of the appropriate type. Subsequent values (including any necessary coercions) are computed as if by the @i{function} @b{+}. If @t{into} @i{var} is used, a @i{type} can be supplied for @i{var} with the @i{type-spec} argument; the consequences are unspecified if a nonnumeric @i{type} is supplied. If there is no @t{into} variable, the optional @i{type-spec} argument applies to the internal variable that is keeping the sum. The default @i{type} is @i{implementation-dependent}; but it must be a @i{supertype} of @i{type} @b{number}. If @t{into} is used, the construct does not provide a default return value; however, the variable is available for use in any @t{finally} clause. Certain kinds of accumulation clauses can be combined in a @b{loop} if their destination is the same (the result of @b{loop} or an @t{into} @i{var}) because they are considered to accumulate conceptually compatible quantities. In particular, any elements of following sets of accumulation clauses can be mixed with other elements of the same set for the same destination in a @b{loop} @i{form}: @table @asis @item @t{*} @t{collect}, @t{append}, @t{nconc} @item @t{*} @t{sum}, @t{count} @item @t{*} @t{maximize}, @t{minimize} @end table @example ;; Collect every name and the kids in one list by using ;; COLLECT and APPEND. (loop for name in '(fred sue alice joe june) for kids in '((bob ken) () () (kris sunshine) ()) collect name append kids) @result{} (FRED BOB KEN SUE ALICE JOE KRIS SUNSHINE JUNE) @end example Any two clauses that do not accumulate the same @i{type} of @i{object} can coexist in a @b{loop} only if each clause accumulates its values into a different @i{variable}. @menu * Examples of COLLECT clause:: * Examples of APPEND and NCONC clauses:: * Examples of COUNT clause:: * Examples of MAXIMIZE and MINIMIZE clauses:: * Examples of SUM clause:: @end menu @node Examples of COLLECT clause, Examples of APPEND and NCONC clauses, Value Accumulation Clauses, Value Accumulation Clauses @subsubsection Examples of COLLECT clause @example ;; Collect all the symbols in a list. (loop for i in '(bird 3 4 turtle (1 . 4) horse cat) when (symbolp i) collect i) @result{} (BIRD TURTLE HORSE CAT) ;; Collect and return odd numbers. (loop for i from 1 to 10 if (oddp i) collect i) @result{} (1 3 5 7 9) ;; Collect items into local variable, but don't return them. (loop for i in '(a b c d) by #'cddr collect i into my-list finally (print my-list)) @t{ |> } (A C) @result{} NIL @end example @node Examples of APPEND and NCONC clauses, Examples of COUNT clause, Examples of COLLECT clause, Value Accumulation Clauses @subsubsection Examples of APPEND and NCONC clauses @example ;; Use APPEND to concatenate some sublists. (loop for x in '((a) (b) ((c))) append x) @result{} (A B (C)) ;; NCONC some sublists together. Note that only lists made by the ;; call to LIST are modified. (loop for i upfrom 0 as x in '(a b (c)) nconc (if (evenp i) (list x) nil)) @result{} (A (C)) @end example @node Examples of COUNT clause, Examples of MAXIMIZE and MINIMIZE clauses, Examples of APPEND and NCONC clauses, Value Accumulation Clauses @subsubsection Examples of COUNT clause @example (loop for i in '(a b nil c nil d e) count i) @result{} 5 @end example @node Examples of MAXIMIZE and MINIMIZE clauses, Examples of SUM clause, Examples of COUNT clause, Value Accumulation Clauses @subsubsection Examples of MAXIMIZE and MINIMIZE clauses @example (loop for i in '(2 1 5 3 4) maximize i) @result{} 5 (loop for i in '(2 1 5 3 4) minimize i) @result{} 1 ;; In this example, FIXNUM applies to the internal variable that holds ;; the maximum value. (setq series '(1.2 4.3 5.7)) @result{} (1.2 4.3 5.7) (loop for v in series maximize (round v) of-type fixnum) @result{} 6 ;; In this example, FIXNUM applies to the variable RESULT. (loop for v of-type float in series minimize (round v) into result of-type fixnum finally (return result)) @result{} 1 @end example @node Examples of SUM clause, , Examples of MAXIMIZE and MINIMIZE clauses, Value Accumulation Clauses @subsubsection Examples of SUM clause @example (loop for i of-type fixnum in '(1 2 3 4 5) sum i) @result{} 15 (setq series '(1.2 4.3 5.7)) @result{} (1.2 4.3 5.7) (loop for v in series sum (* 2.0 v)) @result{} 22.4 @end example @node Termination Test Clauses, Unconditional Execution Clauses, Value Accumulation Clauses, The LOOP Facility @subsection Termination Test Clauses The @t{repeat} construct causes iteration to terminate after a specified number of times. The loop body executes @i{n} times, where @i{n} is the value of the expression @i{form}. The @i{form} argument is evaluated one time in the loop prologue. If the expression evaluates to 0 or to a negative @i{number}, the loop body is not evaluated. The constructs @t{always}, @t{never}, @t{thereis}, @t{while}, @t{until}, and the macro @b{loop-finish} allow conditional termination of iteration within a @b{loop}. The constructs @t{always}, @t{never}, and @t{thereis} provide specific values to be returned when a @b{loop} terminates. Using @t{always}, @t{never}, or @t{thereis} in a loop with value accumulation clauses that are not @t{into} causes an error of @i{type} @b{program-error} to be signaled (at macro expansion time). Since @t{always}, @t{never}, and @t{thereis} use the @b{return-from} @i{special operator} to terminate iteration, any @t{finally} clause that is supplied is not evaluated when exit occurs due to any of these constructs. In all other respects these constructs behave like the @t{while} and @t{until} constructs. The @t{always} construct takes one @i{form} and terminates the @b{loop} if the @i{form} ever evaluates to @b{nil}; in this case, it returns @b{nil}. Otherwise, it provides a default return value of @b{t}. If the value of the supplied @i{form} is never @b{nil}, some other construct can terminate the iteration. The @t{never} construct terminates iteration the first time that the value of the supplied @i{form} is @i{non-nil}; the @b{loop} returns @b{nil}. If the value of the supplied @i{form} is always @b{nil}, some other construct can terminate the iteration. Unless some other clause contributes a return value, the default value returned is @b{t}. The @t{thereis} construct terminates iteration the first time that the value of the supplied @i{form} is @i{non-nil}; the @b{loop} returns the value of the supplied @i{form}. If the value of the supplied @i{form} is always @b{nil}, some other construct can terminate the iteration. Unless some other clause contributes a return value, the default value returned is @b{nil}. There are two differences between the @t{thereis} and @t{until} constructs: @table @asis @item @t{*} The @t{until} construct does not return a value or @b{nil} based on the value of the supplied @i{form}. @item @t{*} The @t{until} construct executes any @t{finally} clause. Since @t{thereis} uses the @b{return-from} @i{special operator} to terminate iteration, any @t{finally} clause that is supplied is not evaluated when exit occurs due to @t{thereis}. @end table The @t{while} construct allows iteration to continue until the supplied @i{form} evaluates to @i{false}. The supplied @i{form} is reevaluated at the location of the @t{while} clause. The @t{until} construct is equivalent to @t{while (not @i{form})\dots}. If the value of the supplied @i{form} is @i{non-nil}, iteration terminates. Termination-test control constructs can be used anywhere within the loop body. The termination tests are used in the order in which they appear. If an @t{until} or @t{while} clause causes termination, any clauses that precede it in the source are still evaluated. If the @t{until} and @t{while} constructs cause termination, control is passed to the loop epilogue, where any @t{finally} clauses will be executed. There are two differences between the @t{never} and @t{until} constructs: @table @asis @item @t{*} The @t{until} construct does not return @b{t} or @b{nil} based on the value of the supplied @i{form}. @item @t{*} The @t{until} construct does not bypass any @t{finally} clauses. Since @t{never} uses the @b{return-from} @i{special operator} to terminate iteration, any @t{finally} clause that is supplied is not evaluated when exit occurs due to @t{never}. @end table In most cases it is not necessary to use @b{loop-finish} because other loop control clauses terminate the @b{loop}. The macro @b{loop-finish} is used to provide a normal exit from a nested conditional inside a @b{loop}. Since @b{loop-finish} transfers control to the loop epilogue, using @b{loop-finish} within a @t{finally} expression can cause infinite looping. @menu * Examples of REPEAT clause:: * Examples of ALWAYS:: * Examples of WHILE and UNTIL clauses:: @end menu @node Examples of REPEAT clause, Examples of ALWAYS, Termination Test Clauses, Termination Test Clauses @subsubsection Examples of REPEAT clause @example (loop repeat 3 do (format t "~&What I say three times is true.~ @t{ |> } What I say three times is true. @t{ |> } What I say three times is true. @t{ |> } What I say three times is true. @result{} NIL (loop repeat -15 do (format t "What you see is what you expect~ @result{} NIL @end example @node Examples of ALWAYS, Examples of WHILE and UNTIL clauses, Examples of REPEAT clause, Termination Test Clauses @subsubsection Examples of ALWAYS, NEVER, and THEREIS clauses @example ;; Make sure I is always less than 11 (two ways). ;; The FOR construct terminates these loops. (loop for i from 0 to 10 always (< i 11)) @result{} T (loop for i from 0 to 10 never (> i 11)) @result{} T ;; If I exceeds 10 return I; otherwise, return NIL. ;; The THEREIS construct terminates this loop. (loop for i from 0 thereis (when (> i 10) i) ) @result{} 11 ;;; The FINALLY clause is not evaluated in these examples. (loop for i from 0 to 10 always (< i 9) finally (print "you won't see this")) @result{} NIL (loop never t finally (print "you won't see this")) @result{} NIL (loop thereis "Here is my value" finally (print "you won't see this")) @result{} "Here is my value" ;; The FOR construct terminates this loop, so the FINALLY clause ;; is evaluated. (loop for i from 1 to 10 thereis (> i 11) finally (prin1 'got-here)) @t{ |> } GOT-HERE @result{} NIL ;; If this code could be used to find a counterexample to Fermat's ;; last theorem, it would still not return the value of the ;; counterexample because all of the THEREIS clauses in this example ;; only return T. But if Fermat is right, that won't matter ;; because this won't terminate. (loop for z upfrom 2 thereis (loop for n upfrom 3 below (log z 2) thereis (loop for x below z thereis (loop for y below z thereis (= (+ (expt x n) (expt y n)) (expt z n)))))) @end example @node Examples of WHILE and UNTIL clauses, , Examples of ALWAYS, Termination Test Clauses @subsubsection Examples of WHILE and UNTIL clauses @example (loop while (hungry-p) do (eat)) ;; UNTIL NOT is equivalent to WHILE. (loop until (not (hungry-p)) do (eat)) ;; Collect the length and the items of STACK. (let ((stack '(a b c d e f))) (loop for item = (length stack) then (pop stack) collect item while stack)) @result{} (6 A B C D E F) ;; Use WHILE to terminate a loop that otherwise wouldn't terminate. ;; Note that WHILE occurs after the WHEN. (loop for i fixnum from 3 when (oddp i) collect i while (< i 5)) @result{} (3 5) @end example @node Unconditional Execution Clauses, Conditional Execution Clauses, Termination Test Clauses, The LOOP Facility @subsection Unconditional Execution Clauses The @t{do} and @t{doing} constructs evaluate the supplied @i{forms} wherever they occur in the expanded form of @b{loop}. The @i{form} argument can be any @i{compound form}. Each @i{form} is evaluated in every iteration. Because every loop clause must begin with a @i{loop keyword}, the keyword @t{do} is used when no control action other than execution is required. The @t{return} construct takes one @i{form}. Any @i{values} returned by the @i{form} are immediately returned by the @b{loop} form. It is equivalent to the clause @t{do (return-from @i{block-name} @i{value})}, where @i{block-name} is the name specified in a @t{named} clause, or @b{nil} if there is no @t{named} clause. @menu * Examples of unconditional execution:: @end menu @node Examples of unconditional execution, , Unconditional Execution Clauses, Unconditional Execution Clauses @subsubsection Examples of unconditional execution @example ;; Print numbers and their squares. ;; The DO construct applies to multiple forms. (loop for i from 1 to 3 do (print i) (print (* i i))) @t{ |> } 1 @t{ |> } 1 @t{ |> } 2 @t{ |> } 4 @t{ |> } 3 @t{ |> } 9 @result{} NIL @end example @node Conditional Execution Clauses, Miscellaneous Clauses, Unconditional Execution Clauses, The LOOP Facility @subsection Conditional Execution Clauses The @t{if}, @t{when}, and @t{unless} constructs establish conditional control in a @b{loop}. If the test passes, the succeeding loop clause is executed. If the test does not pass, the succeeding clause is skipped, and program control moves to the clause that follows the @i{loop keyword} @t{else}. If the test does not pass and no @t{else} clause is supplied, control is transferred to the clause or construct following the entire conditional clause. If conditional clauses are nested, each @t{else} is paired with the closest preceding conditional clause that has no associated @t{else} or @t{end}. In the @t{if} and @t{when} clauses, which are synonymous, the test passes if the value of @i{form} is @i{true}. In the @t{unless} clause, the test passes if the value of @i{form} is @i{false}. Clauses that follow the test expression can be grouped by using the @i{loop keyword} @t{and} to produce a conditional block consisting of a compound clause. The @i{loop keyword} @t{it} can be used to refer to the result of the test expression in a clause. Use the @i{loop keyword} @t{it} in place of the form in a @t{return} clause or an @i{accumulation} clause that is inside a conditional execution clause. If multiple clauses are connected with @t{and}, the @t{it} construct must be in the first clause in the block. The optional @i{loop keyword} @t{end} marks the end of the clause. If this keyword is not supplied, the next @i{loop keyword} marks the end. The construct @t{end} can be used to distinguish the scoping of compound clauses. @menu * Examples of WHEN clause:: @end menu @node Examples of WHEN clause, , Conditional Execution Clauses, Conditional Execution Clauses @subsubsection Examples of WHEN clause @example ;; Signal an exceptional condition. (loop for item in '(1 2 3 a 4 5) when (not (numberp item)) return (cerror "enter new value" "non-numeric value: ~s" item)) Error: non-numeric value: A ;; The previous example is equivalent to the following one. (loop for item in '(1 2 3 a 4 5) when (not (numberp item)) do (return (cerror "Enter new value" "non-numeric value: ~s" item))) Error: non-numeric value: A @end example @example ;; This example parses a simple printed string representation from ;; BUFFER (which is itself a string) and returns the index of the ;; closing double-quote character. (let ((buffer "\"a\" \"b\"")) (loop initially (unless (char= (char buffer 0) #\") (loop-finish)) for i of-type fixnum from 1 below (length (the string buffer)) when (char= (char buffer i) #\") return i)) @result{} 2 ;; The collected value is returned. (loop for i from 1 to 10 when (> i 5) collect i finally (prin1 'got-here)) @t{ |> } GOT-HERE @result{} (6 7 8 9 10) ;; Return both the count of collected numbers and the numbers. (loop for i from 1 to 10 when (> i 5) collect i into number-list and count i into number-count finally (return (values number-count number-list))) @result{} 5, (6 7 8 9 10) @end example @node Miscellaneous Clauses, Examples of Miscellaneous Loop Features, Conditional Execution Clauses, The LOOP Facility @subsection Miscellaneous Clauses @menu * Control Transfer Clauses:: * Examples of NAMED clause:: * Initial and Final Execution:: @end menu @node Control Transfer Clauses, Examples of NAMED clause, Miscellaneous Clauses, Miscellaneous Clauses @subsubsection Control Transfer Clauses The @t{named} construct establishes a name for an @i{implicit block} surrounding the entire @b{loop} so that the @b{return-from} @i{special operator} can be used to return values from or to exit @b{loop}. Only one name per @b{loop} @i{form} can be assigned. If used, the @t{named} construct must be the first clause in the loop expression. The @t{return} construct takes one @i{form}. Any @i{values} returned by the @i{form} are immediately returned by the @b{loop} form. This construct is similar to the @b{return-from} @i{special operator} and the @b{return} @i{macro}. The @t{return} construct does not execute any @t{finally} clause that the @b{loop} @i{form} is given. @node Examples of NAMED clause, Initial and Final Execution, Control Transfer Clauses, Miscellaneous Clauses @subsubsection Examples of NAMED clause @example ;; Just name and return. (loop named max for i from 1 to 10 do (print i) do (return-from max 'done)) @t{ |> } 1 @result{} DONE @end example @node Initial and Final Execution, , Examples of NAMED clause, Miscellaneous Clauses @subsubsection Initial and Final Execution The @t{initially} and @t{finally} constructs evaluate forms that occur before and after the loop body. The @t{initially} construct causes the supplied @i{compound-forms} to be evaluated in the loop prologue, which precedes all loop code except for initial settings supplied by constructs @t{with}, @t{for}, or @t{as}. The code for any @t{initially} clauses is executed in the order in which the clauses appeared in the @b{loop}. The @t{finally} construct causes the supplied @i{compound-forms} to be evaluated in the loop epilogue after normal iteration terminates. The code for any @t{finally} clauses is executed in the order in which the clauses appeared in the @b{loop}. The collected code is executed once in the loop epilogue before any implicit values are returned from the accumulation clauses. An explicit transfer of control (@i{e.g.}, by @b{return}, @b{go}, or @b{throw}) from the loop body, however, will exit the @b{loop} without executing the epilogue code. Clauses such as @t{return}, @t{always}, @t{never}, and @t{thereis} can bypass the @t{finally} clause. @b{return} (or @b{return-from}, if the @t{named} option was supplied) can be used after @t{finally} to return values from a @b{loop}. Such an @i{explicit return} inside the @t{finally} clause takes precedence over returning the accumulation from clauses supplied by such keywords as @t{collect}, @t{nconc}, @t{append}, @t{sum}, @t{count}, @t{maximize}, and @t{minimize}; the accumulation values for these preempted clauses are not returned by @b{loop} if @b{return} or @b{return-from} is used. @node Examples of Miscellaneous Loop Features, Notes about Loop, Miscellaneous Clauses, The LOOP Facility @subsection Examples of Miscellaneous Loop Features @example (let ((i 0)) ; no loop keywords are used (loop (incf i) (if (= i 3) (return i)))) @result{} 3 (let ((i 0)(j 0)) (tagbody (loop (incf j 3) (incf i) (if (= i 3) (go exit))) exit) j) @result{} 9 @end example In the following example, the variable @t{x} is stepped before @t{y} is stepped; thus, the value of @t{y} reflects the updated value of @t{x}: @example (loop for x from 1 to 10 for y = nil then x collect (list x y)) @result{} ((1 NIL) (2 2) (3 3) (4 4) (5 5) (6 6) (7 7) (8 8) (9 9) (10 10)) @end example In this example, @t{x} and @t{y} are stepped in @i{parallel}: @example (loop for x from 1 to 10 and y = nil then x collect (list x y)) @result{} ((1 NIL) (2 1) (3 2) (4 3) (5 4) (6 5) (7 6) (8 7) (9 8) (10 9)) @end example @menu * Examples of clause grouping:: @end menu @node Examples of clause grouping, , Examples of Miscellaneous Loop Features, Examples of Miscellaneous Loop Features @subsubsection Examples of clause grouping @example ;; Group conditional clauses. (loop for i in '(1 324 2345 323 2 4 235 252) when (oddp i) do (print i) and collect i into odd-numbers and do (terpri) else ; I is even. collect i into even-numbers finally (return (values odd-numbers even-numbers))) @t{ |> } 1 @t{ |> } @t{ |> } 2345 @t{ |> } @t{ |> } 323 @t{ |> } @t{ |> } 235 @result{} (1 2345 323 235), (324 2 4 252) ;; Collect numbers larger than 3. (loop for i in '(1 2 3 4 5 6) when (and (> i 3) i) collect it) ; IT refers to (and (> i 3) i). @result{} (4 5 6) ;; Find a number in a list. (loop for i in '(1 2 3 4 5 6) when (and (> i 3) i) return it) @result{} 4 ;; The above example is similar to the following one. (loop for i in '(1 2 3 4 5 6) thereis (and (> i 3) i)) @result{} 4 ;; Nest conditional clauses. (let ((list '(0 3.0 apple 4 5 9.8 orange banana))) (loop for i in list when (numberp i) when (floatp i) collect i into float-numbers else ; Not (floatp i) collect i into other-numbers else ; Not (numberp i) when (symbolp i) collect i into symbol-list else ; Not (symbolp i) do (error "found a funny value in list ~S, value ~S~ finally (return (values float-numbers other-numbers symbol-list)))) @result{} (3.0 9.8), (0 4 5), (APPLE ORANGE BANANA) ;; Without the END preposition, the last AND would apply to the ;; inner IF rather than the outer one. (loop for x from 0 to 3 do (print x) if (zerop (mod x 2)) do (princ " a") and if (zerop (floor x 2)) do (princ " b") end and do (princ " c")) @t{ |> } 0 a b c @t{ |> } 1 @t{ |> } 2 a c @t{ |> } 3 @result{} NIL @end example @node Notes about Loop, , Examples of Miscellaneous Loop Features, The LOOP Facility @subsection Notes about Loop @i{Types} can be supplied for loop variables. It is not necessary to supply a @i{type} for any variable, but supplying the @i{type} can ensure that the variable has a correctly typed initial value, and it can also enable compiler optimizations (depending on the @i{implementation}). The clause @t{repeat} @i{n} ... is roughly equivalent to a clause such as @example (loop for @i{internal-variable} downfrom (- @i{n} 1) to 0 ...) @end example but in some @i{implementations}, the @t{repeat} construct might be more efficient. Within the executable parts of the loop clauses and around the entire @b{loop} form, variables can be bound by using @b{let}. Use caution when using a variable named @t{IT} (in any @i{package}) in connection with @b{loop}, since @t{it} is a @i{loop keyword} that can be used in place of a @i{form} in certain contexts. There is no @i{standardized} mechanism for users to add extensions to @b{loop}. @c end of including concept-loop @node Iteration Dictionary, , The LOOP Facility, Iteration @section Iteration Dictionary @c including dict-iteration @menu * do:: * dotimes:: * dolist:: * loop:: * loop-finish:: @end menu @node do, dotimes, Iteration Dictionary, Iteration Dictionary @subsection do, do* [Macro] @code{do} @i{@r{(}@{@i{var} | @r{(}@i{var} @r{[}init-form @r{[}step-form@r{]}@r{]}@r{)}@}{*}@r{)} @r{(}end-test-form @{@i{result-form}@}{*}@r{)} @{@i{declaration}@}{*} @{tag | statement@}{*}}@* @result{} @i{@{@i{result}@}{*}} @code{do*} @i{@r{(}@{@i{var} | @r{(}@i{var} @r{[}init-form @r{[}step-form@r{]}@r{]}@r{)}@}{*}@r{)} @r{(}end-test-form {@{@i{result-form}@}{*}}@r{)} @{@i{declaration}@}{*} @{tag | statement@}{*}}@* @result{} @i{@{@i{result}@}{*}} @subsubheading Arguments and Values:: @i{var}---a @i{symbol}. @i{init-form}---a @i{form}. @i{step-form}---a @i{form}. @i{end-test-form}---a @i{form}. @i{result-forms}---an @i{implicit progn}. @i{declaration}---a @b{declare} @i{expression}; not evaluated. @i{tag}---a @i{go tag}; not evaluated. @i{statement}---a @i{compound form}; evaluated as described below. @i{results}---if a @b{return} or @b{return-from} form is executed, the @i{values} passed from that @i{form}; otherwise, the @i{values} returned by the @i{result-forms}. @subsubheading Description:: @b{do} iterates over a group of @i{statements} while a test condition holds. @b{do} accepts an arbitrary number of iteration @i{vars} which are bound within the iteration and stepped in parallel. An initial value may be supplied for each iteration variable by use of an @i{init-form}. @i{Step-forms} may be used to specify how the @i{vars} should be updated on succeeding iterations through the loop. @i{Step-forms} may be used both to generate successive values or to accumulate results. If the @i{end-test-form} condition is met prior to an execution of the body, the iteration terminates. @i{Tags} label @i{statements}. @b{do*} is exactly like @b{do} except that the @i{bindings} and steppings of the @i{vars} are performed sequentially rather than in parallel. Before the first iteration, all the @i{init-forms} are evaluated, and each @i{var} is bound to the value of its respective @i{init-form}, if supplied. This is a @i{binding}, not an assignment; when the loop terminates, the old values of those variables will be restored. For @b{do}, all of the @i{init-forms} are evaluated before any @i{var} is bound. The @i{init-forms} can refer to the @i{bindings} of the @i{vars} visible before beginning execution of @b{do}. For @b{do*}, the first @i{init-form} is evaluated, then the first @i{var} is bound to that value, then the second @i{init-form} is evaluated, then the second @i{var} is bound, and so on; in general, the @i{k}th @i{init-form} can refer to the new binding of the @i{j}th @i{var} if @i{j} < @i{k}, and otherwise to the old binding of the @i{j}th @i{var}. At the beginning of each iteration, after processing the variables, the @i{end-test-form} is evaluated. If the result is @i{false}, execution proceeds with the body of the @b{do} (or @b{do*}) form. If the result is @i{true}, the @i{result-forms} are evaluated in order as an @i{implicit progn}, and then @b{do} or @b{do*} returns. At the beginning of each iteration other than the first, @i{vars} are updated as follows. All the @i{step-forms}, if supplied, are evaluated, from left to right, and the resulting values are assigned to the respective @i{vars}. Any @i{var} that has no associated @i{step-form} is not assigned to. For @b{do}, all the @i{step-forms} are evaluated before any @i{var} is updated; the assignment of values to @i{vars} is done in parallel, as if by @b{psetq}. Because all of the @i{step-forms} are evaluated before any of the @i{vars} are altered, a @i{step-form} when evaluated always has access to the old values of all the @i{vars}, even if other @i{step-forms} precede it. For @b{do*}, the first @i{step-form} is evaluated, then the value is assigned to the first @i{var}, then the second @i{step-form} is evaluated, then the value is assigned to the second @i{var}, and so on; the assignment of values to variables is done sequentially, as if by @b{setq}. For either @b{do} or @b{do*}, after the @i{vars} have been updated, the @i{end-test-form} is evaluated as described above, and the iteration continues. The remainder of the @b{do} (or @b{do*}) form constitutes an @i{implicit tagbody}. @i{Tags} may appear within the body of a @b{do} loop for use by @b{go} statements appearing in the body (but such @b{go} statements may not appear in the variable specifiers, the @i{end-test-form}, or the @i{result-forms}). When the end of a @b{do} body is reached, the next iteration cycle (beginning with the evaluation of @i{step-forms}) occurs. An @i{implicit block} named @b{nil} surrounds the entire @b{do} (or @b{do*}) form. A @b{return} statement may be used at any point to exit the loop immediately. @i{Init-form} is an initial value for the @i{var} with which it is associated. If @i{init-form} is omitted, the initial value of @i{var} is @b{nil}. If a @i{declaration} is supplied for a @i{var}, @i{init-form} must be consistent with the @i{declaration}. @i{Declarations} can appear at the beginning of a @b{do} (or @b{do*}) body. They apply to code in the @b{do} (or @b{do*}) body, to the @i{bindings} of the @b{do} (or @b{do*}) @i{vars}, to the @i{step-forms}, to the @i{end-test-form}, and to the @i{result-forms}. @subsubheading Examples:: @example (do ((temp-one 1 (1+ temp-one)) (temp-two 0 (1- temp-two))) ((> (- temp-one temp-two) 5) temp-one)) @result{} 4 (do ((temp-one 1 (1+ temp-one)) (temp-two 0 (1+ temp-one))) ((= 3 temp-two) temp-one)) @result{} 3 (do* ((temp-one 1 (1+ temp-one)) (temp-two 0 (1+ temp-one))) ((= 3 temp-two) temp-one)) @result{} 2 (do ((j 0 (+ j 1))) (nil) ;Do forever. (format t "~ (let ((item (read))) (if (null item) (return) ;Process items until NIL seen. (format t "~&Output ~D: ~S" j item)))) @t{ |> } Input 0: @b{|>>}@t{banana}@b{<<|} @t{ |> } Output 0: BANANA @t{ |> } Input 1: @b{|>>}@t{(57 boxes)}@b{<<|} @t{ |> } Output 1: (57 BOXES) @t{ |> } Input 2: @b{|>>}@t{NIL}@b{<<|} @result{} NIL (setq a-vector (vector 1 nil 3 nil)) (do ((i 0 (+ i 1)) ;Sets every null element of a-vector to zero. (n (array-dimension a-vector 0))) ((= i n)) (when (null (aref a-vector i)) (setf (aref a-vector i) 0))) @result{} NIL a-vector @result{} #(1 0 3 0) @end example @example (do ((x e (cdr x)) (oldx x x)) ((null x)) body) @end example is an example of parallel assignment to index variables. On the first iteration, the value of @t{oldx} is whatever value @t{x} had before the @b{do} was entered. On succeeding iterations, @t{oldx} contains the value that @t{x} had on the previous iteration. @example (do ((x foo (cdr x)) (y bar (cdr y)) (z '() (cons (f (car x) (car y)) z))) ((or (null x) (null y)) (nreverse z))) @end example does the same thing as @t{(mapcar #'f foo bar)}. The step computation for @t{z} is an example of the fact that variables are stepped in parallel. Also, the body of the loop is empty. @example (defun list-reverse (list) (do ((x list (cdr x)) (y '() (cons (car x) y))) ((endp x) y))) @end example As an example of nested iterations, consider a data structure that is a @i{list} of @i{conses}. The @i{car} of each @i{cons} is a @i{list} of @i{symbols}, and the @i{cdr} of each @i{cons} is a @i{list} of equal length containing corresponding values. Such a data structure is similar to an association list, but is divided into ``frames''; the overall structure resembles a rib-cage. A lookup function on such a data structure might be: @example (defun ribcage-lookup (sym ribcage) (do ((r ribcage (cdr r))) ((null r) nil) (do ((s (caar r) (cdr s)) (v (cdar r) (cdr v))) ((null s)) (when (eq (car s) sym) (return-from ribcage-lookup (car v)))))) @result{} RIBCAGE-LOOKUP @end example @subsubheading See Also:: other iteration functions ( @ref{dolist} , @ref{dotimes} , and @ref{loop} ) and more primitive functionality ( @ref{tagbody} , @ref{go} , @ref{block} , @ref{return} , @ref{let; let*} , and @ref{setq} ) @subsubheading Notes:: If @i{end-test-form} is @b{nil}, the test will never succeed. This provides an idiom for ``do forever'': the body of the @b{do} or @b{do*} is executed repeatedly. The infinite loop can be terminated by the use of @b{return}, @b{return-from}, @b{go} to an outer level, or @b{throw}. A @b{do} @i{form} may be explained in terms of the more primitive @i{forms} @b{block}, @b{return}, @b{let}, @b{loop}, @b{tagbody}, and @b{psetq} as follows: @example (block nil (let ((var1 init1) (var2 init2) ... (varn initn)) @i{declarations} (loop (when end-test (return (progn . result))) (tagbody . tagbody) (psetq var1 step1 var2 step2 ... varn stepn)))) @end example @b{do*} is similar, except that @b{let*} and @b{setq} replace the @b{let} and @b{psetq}, respectively. @node dotimes, dolist, do, Iteration Dictionary @subsection dotimes [Macro] @code{dotimes} @i{@r{(}var count-form @r{[}result-form@r{]}@r{)} @{@i{declaration}@}{*} @{tag | statement@}{*}}@* @result{} @i{@{@i{result}@}{*}} @subsubheading Arguments and Values:: @i{var}---a @i{symbol}. @i{count-form}---a @i{form}. @i{result-form}---a @i{form}. @i{declaration}---a @b{declare} @i{expression}; not evaluated. @i{tag}---a @i{go tag}; not evaluated. @i{statement}---a @i{compound form}; evaluated as described below. @i{results}---if a @b{return} or @b{return-from} form is executed, the @i{values} passed from that @i{form}; otherwise, the @i{values} returned by the @i{result-form} or @b{nil} if there is no @i{result-form}. @subsubheading Description:: @b{dotimes} iterates over a series of @i{integers}. @b{dotimes} evaluates @i{count-form}, which should produce an @i{integer}. If @i{count-form} is zero or negative, the body is not executed. @b{dotimes} then executes the body once for each @i{integer} from 0 up to but not including the value of @i{count-form}, in the order in which the @i{tags} and @i{statements} occur, with @i{var} bound to each @i{integer}. Then @i{result-form} is evaluated. At the time @i{result-form} is processed, @i{var} is bound to the number of times the body was executed. @i{Tags} label @i{statements}. An @i{implicit block} named @b{nil} surrounds @b{dotimes}. @b{return} may be used to terminate the loop immediately without performing any further iterations, returning zero or more @i{values}. The body of the loop is an @i{implicit tagbody}; it may contain tags to serve as the targets of @b{go} statements. Declarations may appear before the body of the loop. The @i{scope} of the binding of @i{var} does not include the @i{count-form}, but the @i{result-form} is included. It is @i{implementation-dependent} whether @b{dotimes} @i{establishes} a new @i{binding} of @i{var} on each iteration or whether it @i{establishes} a binding for @i{var} once at the beginning and then @i{assigns} it on any subsequent iterations. @subsubheading Examples:: @example (dotimes (temp-one 10 temp-one)) @result{} 10 (setq temp-two 0) @result{} 0 (dotimes (temp-one 10 t) (incf temp-two)) @result{} T temp-two @result{} 10 @end example Here is an example of the use of @t{dotimes} in processing strings: @example ;;; True if the specified subsequence of the string is a ;;; palindrome (reads the same forwards and backwards). (defun palindromep (string @t{&optional} (start 0) (end (length string))) (dotimes (k (floor (- end start) 2) t) (unless (char-equal (char string (+ start k)) (char string (- end k 1))) (return nil)))) (palindromep "Able was I ere I saw Elba") @result{} T (palindromep "A man, a plan, a canal--Panama!") @result{} NIL (remove-if-not #'alpha-char-p ;Remove punctuation. "A man, a plan, a canal--Panama!") @result{} "AmanaplanacanalPanama" (palindromep (remove-if-not #'alpha-char-p "A man, a plan, a canal--Panama!")) @result{} T (palindromep (remove-if-not #'alpha-char-p "Unremarkable was I ere I saw Elba Kramer, nu?")) @result{} T (palindromep (remove-if-not #'alpha-char-p "A man, a plan, a cat, a ham, a yak, a yam, a hat, a canal--Panama!")) @result{} T @end example @subsubheading See Also:: @ref{do; do*} , @ref{dolist} , @ref{tagbody} @subsubheading Notes:: @b{go} may be used within the body of @b{dotimes} to transfer control to a statement labeled by a @i{tag}. @node dolist, loop, dotimes, Iteration Dictionary @subsection dolist [Macro] @code{dolist} @i{@r{(}var list-form @r{[}result-form@r{]}@r{)} @{@i{declaration}@}{*} @{tag | statement@}{*}}@* @result{} @i{@{@i{result}@}{*}} @subsubheading Arguments and Values:: @i{var}---a @i{symbol}. @i{list-form}---a @i{form}. @i{result-form}---a @i{form}. @i{declaration}---a @b{declare} @i{expression}; not evaluated. @i{tag}---a @i{go tag}; not evaluated. @i{statement}---a @i{compound form}; evaluated as described below. @i{results}---if a @b{return} or @b{return-from} form is executed, the @i{values} passed from that @i{form}; otherwise, the @i{values} returned by the @i{result-form} or @b{nil} if there is no @i{result-form}. @subsubheading Description:: @b{dolist} iterates over the elements of a @i{list}. The body of @b{dolist} is like a @b{tagbody}. It consists of a series of @i{tags} and @i{statements}. @b{dolist} evaluates @i{list-form}, which should produce a @i{list}. It then executes the body once for each element in the @i{list}, in the order in which the @i{tags} and @i{statements} occur, with @i{var} bound to the element. Then @i{result-form} is evaluated. @i{tags} label @i{statements}. At the time @i{result-form} is processed, @i{var} is bound to @b{nil}. An @i{implicit block} named @b{nil} surrounds @b{dolist}. @b{return} may be used to terminate the loop immediately without performing any further iterations, returning zero or more @i{values}. The @i{scope} of the binding of @i{var} does not include the @i{list-form}, but the @i{result-form} is included. It is @i{implementation-dependent} whether @b{dolist} @i{establishes} a new @i{binding} of @i{var} on each iteration or whether it @i{establishes} a binding for @i{var} once at the beginning and then @i{assigns} it on any subsequent iterations. @subsubheading Examples:: @example (setq temp-two '()) @result{} NIL (dolist (temp-one '(1 2 3 4) temp-two) (push temp-one temp-two)) @result{} (4 3 2 1) (setq temp-two 0) @result{} 0 (dolist (temp-one '(1 2 3 4)) (incf temp-two)) @result{} NIL temp-two @result{} 4 (dolist (x '(a b c d)) (prin1 x) (princ " ")) @t{ |> } A B C D @result{} NIL @end example @subsubheading See Also:: @ref{do; do*} , @ref{dotimes} , @ref{tagbody} , @ref{Traversal Rules and Side Effects} @subsubheading Notes:: @b{go} may be used within the body of @b{dolist} to transfer control to a statement labeled by a @i{tag}. @node loop, loop-finish, dolist, Iteration Dictionary @subsection loop [Macro] The ``simple'' @b{loop} @i{form}: @code{loop} @i{@{@i{compound-form}@}{*}} @result{} @i{@{@i{result}@}{*}} The ``extended'' @b{loop} @i{form}: @code{loop} @i{@r{[}!@i{name-clause}@r{]} @{!@i{variable-clause}@}{*} @{!@i{main-clause}@}{*}} @result{} @i{@{@i{result}@}{*}} @w{@i{name-clause} ::=@t{named} @i{name}} @w{@i{variable-clause} ::=!@i{with-clause} | !@i{initial-final} | !@i{for-as-clause}} @w{@i{with-clause} ::=@t{with} @i{var1} @r{[}@i{type-spec}@r{]} @r{[}= @i{form1}@r{]} @{{and} @i{var2} @r{[}@i{type-spec}@r{]} @r{[}= @i{form2}@r{]}@}{*}} @w{@i{main-clause} ::=!@i{unconditional} | !@i{accumulation} | !@i{conditional} | !@i{termination-test} | !@i{initial-final}} @w{@i{initial-final} ::=@t{initially} @{@i{compound-form}@}^+ | @t{finally} @{@i{compound-form}@}^+} @w{@i{unconditional} ::=@{{do} | @t{doing}@} @{@i{compound-form}@}^+ | @t{return} @{@i{form} | @t{it}@}} @w{@i{accumulation} ::=!@i{list-accumulation} | !@i{numeric-accumulation}} @w{@i{list-accumulation} ::=@{{collect} | @t{collecting} | @t{append} | @t{appending} | @t{nconc} | @t{nconcing}@} @{@i{form} | @t{it}@} } @w{ @r{[}@t{into} @i{simple-var}@r{]}} @w{@i{numeric-accumulation} ::=@{{count} | @t{counting} | @t{sum} | @t{summing} | @} @w{ @t{maximize} | @t{maximizing} | @t{minimize} | @t{minimizing}} @{@i{form} | @t{it}@} } @w{ @r{[}@t{into} @i{simple-var}@r{]} @r{[}@i{type-spec}@r{]}} @w{@i{conditional} ::=@{{if} | @t{when} | @t{unless}@} @i{form} !@i{selectable-clause} @{{and} !@i{selectable-clause}@}{*} } @w{ @r{[}@t{else} !@i{selectable-clause} @{{and} !@i{selectable-clause}@}{*}@r{]} } @w{ @r{[}@t{end}@r{]}} @w{@i{selectable-clause} ::=!@i{unconditional} | !@i{accumulation} | !@i{conditional}} @w{@i{termination-test} ::=@t{while} @i{form} | @t{until} @i{form} | @t{repeat} @i{form} | @t{always} @i{form} | @t{never} @i{form} | @t{thereis} @i{form}} @w{@i{for-as-clause} ::=@{{for} | @t{as}@} !@i{for-as-subclause} @{{and} !@i{for-as-subclause}@}{*}} @w{@i{for-as-subclause} ::=!@i{for-as-arithmetic} | !@i{for-as-in-list} | !@i{for-as-on-list} | !@i{for-as-equals-then} |} @w{ !@i{for-as-across} | !@i{for-as-hash} | !@i{for-as-package}} @w{@i{for-as-arithmetic} ::=@i{var} @r{[}@i{type-spec}@r{]} !@i{for-as-arithmetic-subclause}} @w{@i{for-as-arithmetic-subclause} ::=!@i{arithmetic-up} | !@i{arithmetic-downto} | !@i{arithmetic-downfrom}} @w{@i{arithmetic-up} ::=[[@{{from} | @t{upfrom}@} @i{form1} | @{{to} | @t{upto} | @t{below}@} @i{form2} | @t{by} @i{form3}]]^+} @w{@i{arithmetic-downto} ::=[[@{{from} @i{form1}@}^1 | @{@{{downto} | @t{above}@} @i{form2}@}^1 | @t{by} @i{form3}]]} @w{@i{arithmetic-downfrom} ::=[[@{{downfrom} @i{form1}@}^1 | @{{to} | @t{downto} | @t{above}@} @i{form2} | @t{by} @i{form3}]]} @w{@i{for-as-in-list} ::=@i{var} @r{[}@i{type-spec}@r{]} @t{in} @i{form1} @r{[}@t{by} @i{step-fun}@r{]}} @w{@i{for-as-on-list} ::=@i{var} @r{[}@i{type-spec}@r{]} @t{on} @i{form1} @r{[}@t{by} @i{step-fun}@r{]}} @w{@i{for-as-equals-then} ::=@i{var} @r{[}@i{type-spec}@r{]} = @i{form1} @r{[}@t{then} @i{form2}@r{]}} @w{@i{for-as-across} ::=@i{var} @r{[}@i{type-spec}@r{]} @t{across} @i{vector}} @w{@i{for-as-hash} ::=@i{var} @r{[}@i{type-spec}@r{]} @t{being} @{{each} | @t{the}@} } @w{ @{@{{hash-key} | @t{hash-keys}@} @{{in} | @t{of}@} @i{hash-table} } @w{ @r{[}@t{using} @r{(}@t{hash-value} @i{other-var}@r{)}@r{]} | } @w{ @{{hash-value} | @t{hash-values}@} @{{in} | @t{of}@} @i{hash-table} } @w{ @r{[}@t{using} @r{(}@t{hash-key} @i{other-var}@r{)}@r{]}@}} @w{@i{for-as-package} ::=@i{var} @r{[}@i{type-spec}@r{]} @t{being} @{{each} | @t{the}@} } @w{ @{{symbol} | @t{symbols} |} @w{ @t{present-symbol} | @t{present-symbols} |} @w{ @t{external-symbol} | @t{external-symbols}@} } @w{ @r{[}@{{in} | @t{of}@} @i{package}@r{]}} @w{@i{type-spec} ::=!@i{simple-type-spec} | !@i{destructured-type-spec}} @w{@i{simple-type-spec} ::=@b{fixnum} | @b{float} | @b{t} | @b{nil}} @w{@i{destructured-type-spec} ::=@t{of-type} @i{d-type-spec}} @w{@i{d-type-spec} ::=@i{type-specifier} | @t{(@i{d-type-spec} . @i{d-type-spec})}} @w{@i{var} ::=!@i{d-var-spec}} @w{@i{var1} ::=!@i{d-var-spec}} @w{@i{var2} ::=!@i{d-var-spec}} @w{@i{other-var} ::=!@i{d-var-spec}} @w{@i{d-var-spec} ::=@i{simple-var} | @b{nil} | @r{(}!@i{d-var-spec} @t{.} !@i{d-var-spec}@r{)}} @subsubheading Arguments and Values:: @i{compound-form}---a @i{compound form}. @i{name}---a @i{symbol}. @i{simple-var}---a @i{symbol} (a @i{variable} name). @i{form}, @i{form1}, @i{form2}, @i{form3}---a @i{form}. @i{step-fun}---a @i{form} that evaluates to a @i{function} of one @i{argument}. @i{vector}---a @i{form} that evaluates to a @i{vector}. @i{hash-table}---a @i{form} that evaluates to a @i{hash table}. @i{package}---a @i{form} that evaluates to a @i{package designator}. @i{type-specifier}---a @i{type specifier}. This might be either an @i{atomic type specifier} or a @i{compound type specifier}, which introduces some additional complications to proper parsing in the face of destructuring; for further information, see @ref{Destructuring}. @i{result}---an @i{object}. @subsubheading Description:: For details, see @ref{The LOOP Facility}. @subsubheading Examples:: @example ;; An example of the simple form of LOOP. (defun sqrt-advisor () (loop (format t "~&Number: ") (let ((n (parse-integer (read-line) :junk-allowed t))) (when (not n) (return)) (format t "~&The square root of ~D is ~D.~ @result{} SQRT-ADVISOR (sqrt-advisor) @t{ |> } Number: @b{|>>}@t{5{@i{[<--}~]}}@b{<<|} @t{ |> } The square root of 5 is 2.236068. @t{ |> } Number: @b{|>>}@t{4{@i{[<--}~]}}@b{<<|} @t{ |> } The square root of 4 is 2. @t{ |> } Number: @b{|>>}@t{done{@i{[<--}~]}}@b{<<|} @result{} NIL ;; An example of the extended form of LOOP. (defun square-advisor () (loop as n = (progn (format t "~&Number: ") (parse-integer (read-line) :junk-allowed t)) while n do (format t "~&The square of ~D is ~D.~ @result{} SQUARE-ADVISOR (square-advisor) @t{ |> } Number: @b{|>>}@t{4{@i{[<--}~]}}@b{<<|} @t{ |> } The square of 4 is 16. @t{ |> } Number: @b{|>>}@t{23{@i{[<--}~]}}@b{<<|} @t{ |> } The square of 23 is 529. @t{ |> } Number: @b{|>>}@t{done{@i{[<--}~]}}@b{<<|} @result{} NIL ;; Another example of the extended form of LOOP. (loop for n from 1 to 10 when (oddp n) collect n) @result{} (1 3 5 7 9) @end example @subsubheading See Also:: @ref{do; do*} , @ref{dolist} , @ref{dotimes} , @ref{return} , @ref{go} , @ref{throw} , @ref{Destructuring} @subsubheading Notes:: Except that @b{loop-finish} cannot be used within a simple @b{loop} @i{form}, a simple @b{loop} @i{form} is related to an extended @b{loop} @i{form} in the following way: @example (loop @{@i{compound-form}@}{*}) @equiv{} (loop do @{@i{compound-form}@}{*}) @end example @node loop-finish, , loop, Iteration Dictionary @subsection loop-finish [Local Macro] @subsubheading Syntax:: @code{loop-finish} @i{<@i{no @i{arguments}}>} @result{} # @subsubheading Description:: The @b{loop-finish} @i{macro} can be used lexically within an extended @b{loop} @i{form} to terminate that @i{form} ``normally.'' That is, it transfers control to the loop epilogue of the lexically innermost extended @b{loop} @i{form}. This permits execution of any @b{finally} clause (for effect) and the return of any accumulated result. @subsubheading Examples:: @example ;; Terminate the loop, but return the accumulated count. (loop for i in '(1 2 3 stop-here 4 5 6) when (symbolp i) do (loop-finish) count i) @result{} 3 ;; The preceding loop is equivalent to: (loop for i in '(1 2 3 stop-here 4 5 6) until (symbolp i) count i) @result{} 3 ;; While LOOP-FINISH can be used can be used in a variety of ;; situations it is really most needed in a situation where a need ;; to exit is detected at other than the loop's `top level' ;; (where UNTIL or WHEN often work just as well), or where some ;; computation must occur between the point where a need to exit is ;; detected and the point where the exit actually occurs. For example: (defun tokenize-sentence (string) (macrolet ((add-word (wvar svar) `(when ,wvar (push (coerce (nreverse ,wvar) 'string) ,svar) (setq ,wvar nil)))) (loop with word = '() and sentence = '() and endpos = nil for i below (length string) do (let ((char (aref string i))) (case char (#\Space (add-word word sentence)) (#\. (setq endpos (1+ i)) (loop-finish)) (otherwise (push char word)))) finally (add-word word sentence) (return (values (nreverse sentence) endpos))))) @result{} TOKENIZE-SENTENCE (tokenize-sentence "this is a sentence. this is another sentence.") @result{} ("this" "is" "a" "sentence"), 19 (tokenize-sentence "this is a sentence") @result{} ("this" "is" "a" "sentence"), NIL @end example @subsubheading Side Effects:: Transfers control. @subsubheading Exceptional Situations:: Whether or not @b{loop-finish} is @i{fbound} in the @i{global environment} is @i{implementation-dependent}; however, the restrictions on redefinition and @i{shadowing} of @b{loop-finish} are the same as for @i{symbols} in the @t{COMMON-LISP} @i{package} which are @i{fbound} in the @i{global environment}. The consequences of attempting to use @b{loop-finish} outside of @b{loop} are undefined. @subsubheading See Also:: @ref{loop} , @ref{The LOOP Facility} @subsubheading Notes:: @c end of including dict-iteration @c %**end of chapter