[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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
 
for var being frob
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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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 >"


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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.


[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

This document was generated by Brad Parker on June, 13 2006 using texi2html