@node Macros for writing loops
@section Macros for writing loops

@i{(This section was derived from work copyrighted (C) 1993-2005 by
Richard Kelsey, Jonathan Rees, and Mike Sperber.)}

@texonlyindent
@stindex reduce
@code{Iterate} & @code{reduce} are extensions of named-@code{let} for
writing loops that walk down one or more sequences, such as the
elements of a list or vector, the characters read from a port, or an
arithmetic series.  Additional sequences can be defined by the user.
@code{Iterate} & @code{reduce} are exported by the structure
@code{reduce}.

@menu

* Main looping macros::
* Sequence types::
* Synchronous sequences::
* Examples::
* Defining sequence types::
* Loop macro expansion::

@end menu

@node Main looping macros
@subsection Main looping macros

@deffn syntax iterate
@lisp
(iterate @var{loop-name} ((@var{seq-type} @var{elt-var} @var{arg} @dots{})
                    @dots{})
    ((@var{state-var} @var{init})
     @dots{})
  @var{body}
  [@var{tail-exp}])@end lisp
@code{Iterate} steps the @var{elt-var}s in parallel through the
sequences, while each @var{state-var} has the corresponding @var{init}
for the first iteration and later values supplied by the body.  If any
sequence has reached the limit, the value of the @code{iterate}
expression is the value of @var{tail-exp}, if present, or the current
values of the @var{state-var}s, returned as multiple values. If no
sequence has reached its limit, @var{body} is evaluated and either
calls @var{loop-name} with new values for the @var{state-var}s or
returns some other value(s).

The @var{loop-name} and the @var{state-var}s & @var{init}s behave
exactly as in named-@code{let}, in that @var{loop-name} is bound only
in the scope of @var{body}, and each @var{init} is evaluated parallel
in the enclosing scope of the whole expression.  Also, the arguments
to the sequence constructors will be evaluated in the enclosing scope
of the whole expression, or in an extension of that scope peculiar to
the sequence type.  The named-@code{let} expression

@lisp
(let @var{loop-name} ((@var{state-var} @var{init}) @dots{})
  @var{body}
  @dots{})@end lisp

@noindent
is equivalent to an iterate expression with no sequences (and with an
explicit @code{let} wrapped around the body expressions to take care of
any internal definitions):

@lisp
(iterate @var{loop-name} ()
    ((@var{state-var} @var{init}) @dots{})
  (let () @var{body} @dots{}))@end lisp

The @var{seq-type}s are keywords (actually, macros of a particular
form, which makes it easy to add additional types of sequences; see
below).  Examples are @code{list*}, which walks down the elements of a
list, and @code{vector*}, which does the same for vectors.  For each
iteration, each @var{elt-var} is bound to the next element of the
sequence.  The @var{arg}s are supplied to the sequence processors as
other inputs, such as the list or vector to walk down.

If there is a @var{tail-exp}, it is evaluated when the end of one or
more sequences is reached.  If the body does not call @var{loop-name},
however, the @var{tail-exp} is not evaluated.  Unlike named-@code{let},
the behaviour of a non-tail-recursive call to @var{loop-name} is
unspecified, because iterating down a sequence may involve side
effects, such as reading characters from a port.
@end deffn

@deffn syntax reduce
@lisp
(reduce ((@var{seq-type} @var{elt-var} @var{arg} @dots{})
         @dots{})
    ((@var{state-var} @var{init})
     @dots{})
  @var{body}
  [@var{tail-exp}])@end lisp
If an @code{iterate} expression is not meant to terminate before a
sequence has reached its end, the body will always end with a tail call
to @var{loop-name}.  @code{Reduce} is a convenient macro that makes
this common case explicit.  The syntax of @code{reduce} is the same as
that of @code{iterate}, except that there is no @var{loop-name}, and
the body updates the state variables by returning multiple values in
the stead of passing the new values to @var{loop-name}: the body must
return as many values as there are state variables.  By special
dispension, if there are no state variables, then the body may return
any number of values, all of which are ignored.

The value(s) returned by an instance of @code{reduce} is (are) the
value(s) returned by the @var{tail-exp}, if present, or the current
value(s) of the state variables when the end of one or more sequences
is reached.

A @code{reduce} expression can be rewritten as an equivalent
@code{iterate} expression by adding a @var{loop-name} and a wrapper for
the body that calls the @var{loop-name}:

@lisp
(iterate loop ((@var{seq-type} @var{elt-var} @var{arg} @dots{})
               @dots{})
    ((@var{state-var} @var{init})
     @dots{})
  (call-with-values (lambda () @var{body})
    loop)
  [@var{tail-exp}])@end lisp
@end deffn

@node Sequence types
@subsection Sequence types

@deffn {sequence type} list* elt-var list
@deffnx {sequence type} vector* elt-var vector
@deffnx {sequence type} string* elt-var string
@deffnx {sequence type} count* elt-var start [end [step]]
@deffnx {sequence type} input* elt-var input-port reader-proc
@deffnx {sequence type} stream* elt-var proc initial-seed
For lists, vectors, & strings, the @var{elt-var} is bound to the
successive elements of the list or vector, or the successive characters
of the string.

For @code{count*}, the @var{elt-var} is bound to the elements of the
sequence @code{start, start + step, start + 2*step, @dots{}, end},
inclusive of @var{start} and exclusive of @var{end}.  The default
@var{step} is @code{1}, and the sequence does not terminate if no
@var{end} is given or if there is no @var{N} > 0 such that @var{end} =
@var{start} + @var{N}@var{step}.  (@code{=} is used to test for
termination.)  For example, @code{(count* i 0 -1)} does not terminate
because it begins past the @var{end} value, and @code{(count* i 0 1 2)}
does not terminate because it skips over the @var{end} value.

For @code{input*}, the elements are the results of successive
applications of @var{reader-proc} to @var{input-port}.  The sequence
ends when the @var{reader-proc} returns an end-of-file object, @ie{}
a value that satisfies @code{eof-object?}.

For @code{stream*}, the @var{proc} receives the current seed as an
argument and must return two values, the next value of the sequence &
the next seed.  If the new seed is @code{#f}, then the previous element
was the last one.  For example, @code{(list* elt list)} is the same as

@lisp
(stream* elt
         (lambda (list)
           (if (null? list)
               (values 'ignored #f)
               (values (car list) (cdr list))))
         list)@end lisp
@end deffn

@node Synchronous sequences
@subsection Synchronous sequences

When using the sequence types described above, a loop terminates when
any of its sequences terminate.  To help detect bugs, it is useful to
also have sequence types that check whether two or more sequences end
on the same iteration.  For this purpose, there is a second set of
sequence types called @dfn{synchronous sequences}.  Synchronous
sequences are like ordinary asynchronous sequences in every respect
except that they cause an error to be signalled if a loop is terminated
by a synchronous sequence and some other synchronous sequence did not
reach its end on the same iteration.

Sequences are checked for termination in order from left to right, and
if a loop is terminated by an asynchronous sequence no further checking
is done.

@deffn {synchronous sequence type} list% elt-var list
@deffnx {synchronous sequence type} vector% elt-var vector
@deffnx {synchronous sequence type} string% elt-var string
@deffnx {synchronous sequence type} count% elt-var start end [step]
@deffnx {synchronous sequence type} input% elt-var input-port reader-proc
@deffnx {synchronous sequence type} stream% elt-var proc initial-seed
These are all identical to their asynchronous equivalents above, except
that they are synchronous.  Note that @code{count%}'s @var{end}
argument is required, unlike @code{count*}'s, because it would be
nonsensical to check for termination of a sequence that does not
terminate.
@end deffn

@node Examples
@subsection Examples

Gathering the indices of list elements that answer true to some
predicate.

@lisp
(define (select-matching-items list pred)
  (reduce ((list* elt list)
           (count* i 0))
      ((hits '()))
    (if (pred elt)
        (cons i hits)
        hits)
    (reverse hits)))@end lisp

Finding the index of an element of a list that satisfies a predicate.

@lisp
(define (find-matching-item list pred)
  (iterate loop ((list* elt list)
                 (count* i 0))
      ()                                ; no state variables
    (if (pred elt)
        i
        (loop))))@end lisp

Reading one line of text from an input port.

@lisp
(define (read-line port)
  (iterate loop ((input* c port read-char))
      ((chars '()))
    (if (char=? c #\newline)
        (list->string (reverse chars))
        (loop (cons c chars)))
    (if (null? chars)
        (eof-object)                    ; from the PRIMITIVES structure
        (list->string (reverse chars)))))@end lisp

Counting the lines in a file.  This must be written in a way other than
with @code{count*} because it needs the value of the count after the
loop has finished, but the count variable would not be bound then.

@lisp
(define (line-count filename)
  (call-with-input-file filename
    (lambda (inport)
      (reduce ((input* line inport read-line))
          ((count 0))
        (+ count 1)))))@end lisp

@node Defining sequence types
@subsection Defining sequence types

The sequence types are object-oriented macros similar to enumerations.
An asynchronous sequence macro needs to supply three values: @code{#f}
to indicate that it is not synchronous, a list of state variables and
their initializers, and the code for one iteration.  The first two
methods are written in continuation-passing style: they take another
macro and argument to which to pass their result.  See [Friedman 00]
for more details on the theory behind how CPS macros work.  The
@code{sync} method receives no extra arguments.  The @code{state-vars}
method is passed a list of names that will be bound to the arguments of
the sequence.  The final method, for stepping the sequence forward, is
passed the list of names bound to the arguments and the list of state
variables.  In addition, there is a variable to be bound to the next
element of the sequence, the body expression for the loop, and an
expression for terminating the loop.

As an example, the definition of @code{list*} is:

@lisp
(define-syntax list*
  (syntax-rules (SYNC STATE-VARS STEP)
    ((LIST* SYNC (next more))
     (next #F more))
    ((LIST* STATE-VARS (start-list) (next more))
     (next ((list-var start-list)) more))
    ((LIST* STEP (start-list) (list-var) value-var loop-body tail-exp)
     (IF (NULL? list-var)
         tail-exp
         (LET ((value-var (CAR list-var))
               (list-var  (CDR list-var)))
           loop-body)))))@end lisp

Synchronized sequences are similar, except that they need to provide a
termination test to be used when some other synchronized method
terminates the loop.  To continue the example:

@lisp
(define-syntax list%
  (syntax-rules (SYNC DONE)
    ((LIST% SYNC (next more))
     (next #T more))
    ((LIST% DONE (start-list) (list-var))
     (NULL? list-var))
    ((LIST% . anything-else)
     (LIST* . anything-else))))@end lisp

@node Loop macro expansion
@subsection Loop macro expansion

Here is an example of the expansion of the @code{reduce} macro:

@lisp
(reduce ((list* x '(1 2 3)))
    ((r '()))
  (cons x r))
    @expansion{}
(let ((final (lambda (r) (values r)))
      (list '(1 2 3))
      (r '()))
  (let loop ((list list) (r r))
    (if (null? list)
        (final r)
        (let ((x    (car list))
              (list (cdr list)))
          (let ((continue (lambda (r)
                            (loop list r))))
            (continue (cons x r)))))))@end lisp

The only mild inefficiencies in this code are the @code{final} &
@code{continue} procedures, both of which could trivially be
substituted in-line.  The macro expander could easily perform the
substitution for @code{continue} when there is no explicit proceed
variable, as in this case, but not in general.