Macros for writing loops
========================

(This section was derived from work copyrighted © 1993--2005 by Richard Kelsey, Jonathan Rees, and Mike Sperber.)

Iterate & reduce are extensions of named-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. Iterate & reduce are exported by the structure reduce.

Main looping macros
-------------------

 -- syntax: iterate

          (iterate LOOP-NAME ((SEQ-TYPE ELT-VAR ARG ...)
                              ...)
              ((STATE-VAR INIT)
               ...)
            BODY
            [TAIL-EXP]) lisp
          Iterate steps the ELT-VARs in parallel through the
          sequences, while each STATE-VAR has the corresponding INIT
          for the first iteration and later values supplied by the body.  If any
          sequence has reached the limit, the value of the iterate
          expression is the value of TAIL-EXP, if present, or the current
          values of the STATE-VARs, returned as multiple values. If no
          sequence has reached its limit, BODY is evaluated and either
          calls LOOP-NAME with new values for the STATE-VARs or
          returns some other value(s).

          The LOOP-NAME and the STATE-VARs & INITs behave
          exactly as in named-let, in that LOOP-NAME is bound only
          in the scope of BODY, and each 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-let expression

               (let LOOP-NAME ((STATE-VAR INIT) ...)
                 BODY
                 ...) lisp

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

                    (iterate LOOP-NAME ()
                        ((STATE-VAR INIT) ...)
                      (let () BODY ...)) lisp

                    The SEQ-TYPEs are keywords (actually, macros of a particular
                    form, which makes it easy to add additional types of sequences; see
                    below).  Examples are list*, which walks down the elements of a
                    list, and vector*, which does the same for vectors.  For each
                    iteration, each ELT-VAR is bound to the next element of the
                    sequence.  The ARGs are supplied to the sequence processors as
                    other inputs, such as the list or vector to walk down.

                    If there is a TAIL-EXP, it is evaluated when the end of one or
                    more sequences is reached.  If the body does not call LOOP-NAME,
                    however, the TAIL-EXP is not evaluated.  Unlike named-let,
                    the behaviour of a non-tail-recursive call to LOOP-NAME is
                    unspecified, because iterating down a sequence may involve side
                    effects, such as reading characters from a port.

 -- syntax: reduce

          (reduce ((SEQ-TYPE ELT-VAR ARG ...)
                   ...)
              ((STATE-VAR INIT)
               ...)
            BODY
            [TAIL-EXP]) lisp
          If an iterate expression is not meant to terminate before a
          sequence has reached its end, the body will always end with a tail call
          to LOOP-NAME.  Reduce is a convenient macro that makes
          this common case explicit.  The syntax of reduce is the same as
          that of iterate, except that there is no LOOP-NAME, and
          the body updates the state variables by returning multiple values in
          the stead of passing the new values to 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 reduce is (are) the
          value(s) returned by the TAIL-EXP, if present, or the current
          value(s) of the state variables when the end of one or more sequences
          is reached.

          A reduce expression can be rewritten as an equivalent
          iterate expression by adding a LOOP-NAME and a wrapper for
          the body that calls the LOOP-NAME:

               (iterate loop ((SEQ-TYPE ELT-VAR ARG ...)
                              ...)
                   ((STATE-VAR INIT)
                    ...)
                 (call-with-values (lambda () BODY)
                   loop)
                 [TAIL-EXP]) lisp

Sequence types
--------------

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

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

     For input*, the elements are the results of successive applications of READER-PROC to INPUT-PORT.  The sequence ends when the READER-PROC returns an end-of-file object, ie a value that satisfies eof-object?.

     For stream*, the 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 #f, then the previous element was the last one.  For example, (list* elt list) is the same as

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

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

 -- synchronous sequence type: list% elt-var list
 -- synchronous sequence type: vector% elt-var vector
 -- synchronous sequence type: string% elt-var string
 -- synchronous sequence type: count% elt-var start end [step]
 -- synchronous sequence type: input% elt-var input-port reader-proc
 -- 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 count%'s END argument is required, unlike count*'s, because it would be nonsensical to check for termination of a sequence that does not terminate.

Examples
--------

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

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

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

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

          Reading one line of text from an input port.

               (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))))) lisp

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

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

Defining sequence types
-----------------------

The sequence types are object-oriented macros similar to enumerations. An asynchronous sequence macro needs to supply three values: #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 sync method receives no extra arguments.  The 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 list* is:

     (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))))) 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:

          (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)))) lisp

Loop macro expansion
--------------------

Here is an example of the expansion of the reduce macro:

     (reduce ((list* x '(1 2 3)))
         ((r '()))
       (cons x r))
         ==>
     (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))))))) lisp

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