You are looking at historical revision 2536 of this page. It may differ significantly from its current revision.

loopy-loop

Introduction

LOOP is a generalized iteration form supporting extensible iterator macros, keyword updates, and full recursion. The idea is to create a loop as simple and close to natural Scheme as possible, while still being extensible.

See the article with message-id <1157562097.001179.11470@i42g2000cwa.googlegroups.com> posted on comp.lang.scheme in September of 2006 for the original version and a brief history of Lisp iteration constructs.

In its most basic usage, LOOP can be used as a drop-in replacement for named let (assuming the let name isn't passed as a first class value). So, for example, the following definitions

 (define (fold kons knil ls)
   (let lp ((ls ls) (knil knil))
     (if (pair? ls)
       (lp (cdr ls) (kons (car ls) knil))
       knil)))

and

 (define (fold kons knil ls)
   (loop lp ((ls ls) (knil knil))
     (if (pair? ls)
       (lp (cdr ls) (kons (car ls) knil))
       knil)))

are equivalent. We further allow automatic stepping of variables, as in the DO macro:

 (define (fold kons knil ls)
   (loop lp ((ls ls (cdr ls)) (knil knil (kons (car ls) knil)))
     (if (pair? ls)
       (lp)
       knil)))

The parameters have default steps, so we don't need to pass them explicitly anymore (though we can still do so if we wanted to override the defaults).

In addition, we provide extensible iterators to automatically handle the logic of stepping, fetching, and checking termination on sequence types. To use an iterator, specify one or more variable names followed by `<-' followed by the iterator and any parameters:

 (x <- in-foo bar baz qux)

To iterate over a list, use the IN-LIST macro:

 (x <- in-list ls)

This will bind X to the succesive elements of LS in the body of the loop.

Now, when iterating automatically, the loop will also terminate automatically if it encounters the end of its input. In such a case you may want to specify a return value. You can do this by putting

 => <expr>

right at the start of the loop body. So our example now becomes:

 (define (fold kons knil ls)
   (loop lp ((x <- in-list ls) (knil knil (kons x knil)))
       => knil
     (lp)))

Note we can still call, or not call, the loop itself in the body according to whatever logic we want, and re-enter it possibly multiple times. However, in this common case where the entire body is reduced to just calling the loop again, we can ommit it by using an anonymous loop:

 (define (fold kons knil ls)
   (loop ((x <- in-list ls) (knil knil (kons x knil)))
      => knil))

No flexibility is lost over named let, yet we've gained the convenience of iterators. If you wanted to change the above to work on vectors, all you would need to do is change the iterator:

 (x <- in-vector vec)

and it works as expected.

Bindings and scope

Iterator macros may introduce variables in three different lexical scopes:

 * Loop variables - analogous to the variables in a named let, these
   are initialized once and updated on each iteration through the
   loop.  In the example above, KNIL is a loop variable (as are all
   named let and DO-style variables).
 * Body variables - bound in the body, these are usually derived
   directly from loop variables.  They can't be overridden (see
   below) and are not available in the final expression.  In the
   example above, X is a body variable.
 * Final variables - bound once in the return expression, these are
   sometimes used for some final computation such as reversing a
   consed up list.

Within each of these three lexical scopes, all variables are updated in parallel, and none are ever mutated (unless the programmer does so manually). This referential transparency is important to achieve full non-tail recursion and re-entrancy.

In many cases the loop variables will be implicit and unnamed. For instance, IN-LIST uses a loop variable to cdr down the list of pairs, binding X to the successive cars. However, in such cases the iterator usually lets you explicitly name the loop variable if you want access to it.

Loop variables may be manually overriden on a recursive call. You can either use the original positional arguments, or specify individual values by name with the <- syntax, punning the initial binding. Thus in

  (loop lp ((x ls <- in-list ls)) ...)

the recursive calls

  (lp)
  (lp (cdr ls))
  (lp ls <- (cdr ls))

are all the same. Note that we are binding the loop variable LS, not X which is considered to be always derived from the loop variable. Note also that there is no need to recurse on CDR - we could use CDDR, or a completely unrelated list, or '() to force an early termination.

The following example flattens a tree into a list, using minimal conses and stack. This serves as an example of naming implicit loop variables, binding loop variables, and non-tail recursion.

 (define (flatten ls)
   (reverse
    (loop lp ((x ls <- in-list ls) (res '()))
        => res
      (if (pair? x)
          (lp res <- (lp ls <- x))
          (lp res <- (cons x res))))))

The scope of the final expression will include all the final loop variables, at least one of which will correspond to a true termination condition. The body variables are not bound, however the loop itself, if named, is available so that you can restart the loop with all new initial values if you want.

Iterators

 ;;; Simple loop
 > (loop ((x <- in-list '(a b c))) (write x) (newline))
 a
 b
 c
 ;;; Reverse a list destructively.
 (define (reverse! list)
   (loop ((for elt pair (in-list list))
          (let tail '() pair))
     => tail
     (set-cdr! pair tail)))
 ;;; Test for circularity
 (define (cddr* ls) ; CL's cddr
   (let ((x (cdr ls))) (if (pair? x) (cdr x) '())))
 (define (circular-list? ls)
   (and (pair? ls)
        (loop race ((tortoise <- in-list ls)
                    (hare <- in-list (cdr ls) cddr*))
            => #f
          (or (eq? hare tortoise) (race)))))

Extending

You can add your own iterators, for example to loop over rows of a database select, or over elements of your own custom data structure. [Pending further documentation, you'll need to read the source or contact the author.]

License

public domain

History

1.0
initial release