30. "Iteration Paths"
.setq iteration-path-page page
Iteration paths provide a mechanism for user extension of
iteration-driving clauses. The interface is constrained so that the
definition of a path need not depend on much of the internals of
loop. The typical form of an iteration path is
| for var {data-type} being {each|the} pathname {preposition1 expr1}...
|
pathname is an atomic symbol which is defined as a loop path
function. The usage and defaulting of data-type is up to the
path function. Any number of preposition/expression pairs may be
present; the prepositions allowable for any particular path are
defined by that path. For example,
| (loop for x being the array-elements of my-array from 1 to 10
...)
|
To enhance readability, pathnames are usually defined in both the
singular and plural forms; this particular example could have been
written as
| (loop for x being each array-element of my-array from 1 to 10
...)
|
Another format, which is not so generally applicable, is
| for var {data-type} being expr0 and its pathname {preposition1 expr1}...
|
In this format, var takes on the value of expr0 the first
time through the loop. Support for this format is usually limited to
paths which step through some data structure, such as the "superiors"
of something. Thus, we can hypothesize the cdrs path, such that
| (loop for x being the cdrs of '(a b c . d) collect x)
=> ((b c . d) (c . d) d)
|
but
| (loop for x being '(a b c . d) and its cdrs collect x)
=> ((a b c . d) (b c . d) (c . d) d)
|
To satisfy the anthropomorphic among you, his, her, or
their may be substituted for the its keyword, as may
each. Egocentricity is not condoned. Some example uses of
iteration paths are shown in section (predefined-paths-section).
Very often, iteration paths step internal variables which the
@setq loop-using-crock page
user does not specify, such as an index into some data-structure.
Although in most cases the user does not wish to be concerned with
such low-level matters, it is occasionally useful to have a handle on
such things. loop provides an additional syntax with which one
may provide a variable name to be used as an "internal" variable by an
iteration path, with the using "prepositional phrase".
The using phrase is placed with the other phrases associated
with the path, and contains any number of keyword/variable-name pairs:
| (loop for x being the array-elements of a using (index i)
...)
|
which says that the variable i should be used to hold the index
of the array being stepped through. The particular keywords which may
be used are defined by the iteration path; the index keyword is
recognized by all loop sequence paths (section
(loop-sequence-section)). Note that any individual using
phrase applies to only one path; it is parsed along with the
"prepositional phrases". It is an error if the path does not call for
a variable using that keyword.
By special dispensation, if a pathname is not recognized,
then the default-loop-path path will be invoked upon a syntactic
transformation of the original input. Essentially, the loop fragment
is taken as if it were
| for var being default-loop-path in frob
|
and
| for var being expr and its frob ...
|
is taken as if it were
| for var being expr and its default-loop-path in frob
|
Thus, this "undefined pathname hook" only works if the
default-loop-path path is defined. Obviously, the use of this
"hook" is competitive, since only one such hook may be in use, and the
potential for syntactic ambiguity exists if frob is the name of
a defined iteration path. This feature is not for casual use; it is
intended for use by large systems which wish to use a special
syntax for some feature they provide.
30.1 "Pre-Defined Paths"
.setq predefined-paths-section css-number
loop comes with two pre-defined iteration path
functions; one implements a mapatoms-like iteration path
facility, and the other is used for defining iteration paths for
stepping through sequences.
30.1.1 "The Interned-Symbols Path"
.path_index interned-symbols
The interned-symbols iteration path is like a
mapatoms for loop.
| (loop for sym being interned-symbols ...)
|
iterates over all of the symbols in the current package and its
superiors (or, in Maclisp, the current obarray). This is the same set
of symbols which mapatoms iterates over, although not
necessarily in the same order. The particular package to look in may
be specified as in
| (loop for sym being the interned-symbols in package ...)
|
which is like giving a second argument to mapatoms.
In Lisp implementations with some sort of hierarchical package
structure such as Zetalisp, one may restrict the iteration to
be over just the package specified and not its superiors, by using the
local-interned-symbols path:
| (loop for sym being the local-interned-symbols {in package}
...)
|
Example:
| (defun my-apropos (sub-string &optional (pkg package))
(loop for x being the interned-symbols in pkg
when (string-search sub-string x)
when (or (boundp x) (fboundp x) (plist x))
do (print-interesting-info x)))
|
In the Zetalisp and NIL implementations of loop, a package
specified with the in preposition may be anything acceptable to
the pkg-find-package function. The code generated by this path
will contain calls to internal loop functions, with the effect
that it will be transparent to changes to the implementation of
packages. In the Maclisp implementation, the obarray must be an
array pointer, not a symbol with an array property.
30.1.2 "Sequence Iteration"
.setq loop-sequence-section css-number
.setq loop-sequence-page page
One very common form of iteration is that over the elements
of some object which is accessible by means of an integer index.
loop defines an iteration path function for doing this in a
general way, and provides a simple interface to allow users to define
iteration paths for various kinds of "indexable" data.
- Macro: define-loop-sequence-path
| 7(define-loop-sequence-path path-name-or-names
fetch-fun size-fun
sequence-type default-var-type)
|
path-name-or-names is either an atomic path name or list of path
names. fetch-fun is a function of two arguments: the sequence,
and the index of the item to be fetched. (Indexing is assumed to be
zero-origined.) size-fun is a function of one argument, the
sequence; it should return the number of elements in the sequence.
sequence-type is the name of the data-type of the sequence, and
default-var-type the name of the data-type of the elements of
the sequence. These last two items are optional.
.group
The Zetalisp implementation of loop utilizes the
Zetalisp array manipulation primitives to define both
array-element and array-elements as iteration paths:
| 7(define-loop-sequence-path (array-element array-elements)
aref array-active-length)
|
.unbreak
Then, the loop clause
| for var being the array-elements of array
|
will step var over the elements of array, starting from
0. The sequence path function also accepts in as a
synonym for of.
.end_group
The range and stepping of the iteration may be specified with
the use of all of the same keywords which are accepted by the loop
arithmetic stepper (for var from ...); they are
by, to, downto, from, downfrom,
below, and above, and are interpreted in the same manner.
Thus,
| (loop for var being the array-elements of array
from 1 by 2
...)
|
steps var over all of the odd elements of array, and
| (loop for var being the array-elements of array
downto 0
...)
|
steps in "reverse" order.
| (define-loop-sequence-path (vector-elements vector-element)
vref vector-length notype notype)
|
is how the vector-elements iteration path can be defined in NIL
(which it is). One can then do such things as
| (defun cons-a-lot (item &restv other-items)
(and other-items
(loop for x being the vector-elements of other-items
collect (cons item x))))
|
All such sequence iteration paths allow one to specify the
variable to be used as the index variable, by use of the index
keyword with the using prepositional phrase, as described (with
an example) on (loop-using-crock).
.insert_for_NIL "lsbdoc;()path >"
30.2 "Defining Paths"
This section and the next may not be of interest to those
not interested in defining their own iteration paths.
A loop iteration clause (e.g. a for or as
clause) produces, in addition to the code which defines the iteration
(section (loop-iteration-framework-section)), variables which must
be bound, and pre-iteration (prologue) code. This breakdown
allows a user-interface to loop which does not have to depend on
or know about the internals of loop. To complete this
separation, the iteration path mechanism parses the clause before
giving it to the user function which will return those items. A
function to generate code for a path may be declared to loop
with the define-loop-path function:
- Macro: define-loop-path
| 7(define-loop-path pathname-or-names path-function
list-of-allowable-prepositions
datum-1 datum-2 ...)
|
This defines path-function to be the handler for the path(s)
pathname-or-names, which may be either a symbol or a list of
symbols. Such a handler should follow the conventions described
below. The datum-i are optional; they are passed in to
path-function as a list.
The handler will be called with the following arguments:
path-name
- The name of the path which caused the path function to be invoked.
variable
- The "iteration variable".
data-type
- The data type supplied with the iteration variable, or nil if
none was supplied.
prepositional-phrases
- This is a list with entries of the form (preposition
expression), in the order in which they were collected. This may
also include some supplied implicitly (e.g. an of phrase when
the iteration is inclusive, and an in phrase for the
default-loop-path path); the ordering will show the order of
evaluation which should be followed for the expressions.
inclusive?
- This is t if variable should have the starting point of
the path as its value on the first iteration (by virtue of being
specified with syntax like for var being expr and its
pathname), nil otherwise. When t, expr
will appear in prepositional-phrases with the of
preposition; for example, for x being foo and its cdrs gets
prepositional-phrases of ((of foo)).
allowed-prepositions
- This is the list of allowable prepositions declared for the pathname
that caused the path function to be invoked. It and data
(immediately below) may be used by the path function such that a
single function may handle similar paths.
data
- This is the list of "data" declared for the pathname that caused the
path function to be invoked. It may, for instance, contain a
canonicalized pathname, or a set of functions or flags to aid the
path function in determining what to do. In this way, the same
path function may be able to handle different paths.
The handler should return a list of either six or ten
elements:
variable-bindings
- This is a list of variables which need to be bound. The entries in it
may be of the form variable, (variable expression),
or (variable expression data-type). Note that it is
the responsibility of the handler to make sure the iteration variable
gets bound. All of these variables will be bound in parallel;
if initialization of one depends on others, it should be done with a
setq in the prologue-forms. Returning only the variable
without any initialization expression is not allowed if the variable
is a destructuring pattern.
prologue-forms
- This is a list of forms which should be included in the loop
prologue.
the four items of the iteration specification
- These are the four items described in section
(loop-iteration-framework-section),
(loop-iteration-framework-page): pre-step-endtest,
steps, post-step-endtest, and pseudo-steps.
another four items of iteration specification
- If these four items are given, they apply to the first iteration, and
the previous four apply to all succeeding iterations; otherwise, the
previous four apply to all iterations.
Here are the routines which are used by loop to compare
keywords for equality. In all cases, a token may be any Lisp
object, but a keyword is expected to be an atomic symbol. In
certain implementations these functions may be implemented as macros.
- Function: si:loop-tequal token keyword
- This is the loop token comparison function. token is any Lisp
object; keyword is the keyword it is to be compared
against. It returns t if they represent the same token,
comparing in a manner appropriate for the implementation.
- Function: si:loop-tmember token keyword-list
- The member variant of si:loop-tequal.
- Function: si:loop-tassoc token keyword-alist
- The assoc variant of si:loop-tequal.
If an iteration path function desires to make an internal
variable accessible to the user, it should call the following function
instead of gensym:
- Function: si:loop-named-variable keyword
- This should only be called from within an iteration path function. If
keyword has been specified in a using phrase for this
path, the corresponding variable is returned; otherwise, gensym
is called and that new symbol returned. Within a given path function,
this routine should only be called once for any given keyword.
If the user specifies a using preposition containing any keywords
for which the path function does not call si:loop-named-variable,
loop will inform the user of his error.
30.2.1 "An Example Path Definition"
Here is an example function which defines the
string-characters iteration path. This path steps a variable
through all of the characters of a string. It accepts the format
| (loop for var being the string-characters of str ...)
|
The function is defined to handle the path by
| (define-loop-path string-characters string-chars-path
(of))
|
Here is the function:
| (defun string-chars-path (path-name variable data-type
prep-phrases inclusive?
allowed-prepositions data
&aux (bindings nil)
(prologue nil)
(string-var (gensym))
(index-var (gensym))
(size-var (gensym)))
allowed-prepositions data ; unused variables
; To iterate over the characters of a string, we need
; to save the string, save the size of the string,
; step an index variable through that range, setting
; the user's variable to the character at that index.
; Default the data-type of the user's variable:
(cond ((null data-type) (setq data-type 'fixnum)))
; We support exactly one "preposition", which is
; required, so this check suffices:
(cond ((null prep-phrases)
(ferror nil "OF missing in ~S iteration path of ~S"
path-name variable)))
; We do not support "inclusive" iteration:
(cond ((not (null inclusive?))
(ferror nil
"Inclusive stepping not supported in ~S path ~
of ~S (prep phrases = ~:S)"
path-name variable prep-phrases)))
; Set up the bindings
(setq bindings (list (list variable nil data-type)
(list string-var (cadar prep-phrases))
(list index-var 0 'fixnum)
(list size-var 0 'fixnum)))
; Now set the size variable
(setq prologue (list `(setq ,size-var (string-length
,string-var))))
; and return the appropriate stuff, explained below.
(list bindings
prologue
`(= ,index-var ,size-var)
nil
nil
; char-n is the NIL string referencing primitive.
; In Zetalisp, aref could be used instead.
(list variable `(char-n ,string-var ,index-var)
index-var `(1+ ,index-var))))
|
The first element of the returned list is the bindings. The
second is a list of forms to be placed in the prologue. The
remaining elements specify how the iteration is to be performed. This
example is a particularly simple case, for two reasons: the actual
"variable of iteration", index-var, is purely internal
(being gensymmed), and the stepping of it (1+) is such
that it may be performed safely without an endtest. Thus
index-var may be stepped immediately after the setting of the
user's variable, causing the iteration specification for the first
iteration to be identical to the iteration specification for all
remaining iterations. This is advantageous from the standpoint of the
optimizations loop is able to perform, although it is frequently
not possible due to the semantics of the iteration (e.g., for
var first expr1 then expr2) or to subtleties of
the stepping. It is safe for this path to step the user's variable in
the pseudo-steps (the fourth item of an iteration specification)
rather than the "real" steps (the second), because the step value can
have no dependencies on any other (user) iteration variables. Using
the pseudo-steps generally results in some efficiency gains.
If one desired the index variable in the above definition to
be user-accessible through the using phrase feature with the
index keyword, the function would need to be changed in two
ways. First, index-var should be bound to
(si:loop-named-variable 'index) instead of (gensym).
Secondly, the efficiency hack of stepping the index variable ahead of
the iteration variable must not be done. This is effected by changing
the last form to be
| (list bindings prologue
nil
(list index-var `(1+ ,index-var))
`(= ,index-var ,size-var)
(list variable `(char-n ,string-var ,index-var))
nil
nil
`(= ,index-var ,size-var)
(list variable `(char-n ,string-var ,index-var)))
|
Note that although the second `(= ,index-var ,size-var) could
have been placed earlier (where the second nil is), it is best
for it to match up with the equivalent test in the first iteration
specification grouping.
This document was generated
by Brad Parker on June, 13 2006
using texi2html