Scheme 48 Manual | Contents | In Chapter: Libraries
Previous: Sockets | Next: Regular expressions

Macros for writing loops

Iterate and 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 and reduce are in structure reduce.

Iterate

The syntax of iterate is: 

  (iterate loop-name
           ((sequence-type element-variable sequence-data ...)
            ...)
           ((state-variable initial-value)
            ...)
    body-expression
    [final-expression])

Iterate steps the element-variables in parallel through the sequences, while each state-variable has the corresponding initial-value for the first iteration and have later values supplied by body-expression. If any sequence has reached its limit the value of the iterate expression is the value of final-expression, if present, or the current values of the state-variables, returned as multiple values. If no sequence has reached its limit, body-expression is evaluated and either calls loop-name with new values for the state-variables, or returns some other value(s).

The loop-name and the state-variables and initial-values behave exactly as in named-let. The named-let expression 

  (let loop-name ((state-variable initial-value) ...)
    body ...)
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 defines): 
  (iterate loop-name
           ()
           ((state-variable initial-value) ...)
    (let () body ...))

The sequence-types are keywords (they are actually macros of a particular form; it is easy to add additional types of sequences). Examples are list* which walks down the elements of a list and vector* which does the same for vectors. For each iteration, each element-variable is bound to the next element of the sequence. The sequence-data gives the actual list or vector or whatever.

If there is a final-expression, it is evaluated when the end of one or more sequences is reached. If the body-expression does not call loop-name the final-expression is not evaluated. The state-variables are visible in final-expression but the sequence-variables are not.

The body-expression and the final-expression are in tail-position within the iterate. Unlike named-let, the behavior 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).

Reduce

If an iterate expression is not meant to terminate before a sequence has reached its end, body-expression will always end with a tail call to loop-name. Reduce is a 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. The body-expression returns new values of the state-variables instead of passing them to loop-name. Thus body-expression must return as many values as there are state variables. By special dispensation, if there are no state variables then body-expression may return any number of values, all of which are ignored.

The syntax of reduce is: 

  (reduce ((sequence-type element-variable sequence-data ...)
            ...)
           ((state-variable initial-value)
            ...)
    body-expression
    [final-expression])

The value(s) returned by an instance of reduce is the value(s) returned by the final-expression, 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-var and a wrapper for the body-expression that calls the loop-var. 

(iterate loop
         ((sequence-type element-variable sequence-data ...)
          ...)
         ((state-variable initial-value)
          ...)
  (call-with-values (lambda ()
                      body-expression)
                    loop)
  [final-expression])

Sequence types

The predefined sequence types are:

For lists, vectors, and strings the element variable is bound to the successive elements of the list or vector, or the characters in the string.

For count* the element variable is bound to the elements of the sequence 

 start, start + step, start + 2step, ..., end
inclusive of start and exclusive of end. The default step is 1. 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) doesn't terminate because it begins past the end value and (count* i 0 1 2) doesn't terminate because it skips over the end value.

For input* the elements are the results of successive applications of read-procedure to input-port. The sequence ends when read-procedure returns an end-of-file object.

For a stream, the procedure takes the current data value as an argument and returns two values, the next value of the sequence and a new data value. If the new data is #f then the previous element was the last one. For example, 

  (list* elt my-list)
is the same as 
  (stream* elt list->stream my-list)
where list->stream is 
  (lambda (list)
    (if (null? list)
        (values 'ignored #f)
        (values (car list) (cdr list))))

Synchronous sequences

When using the sequence types described above, a loop terminates when any of its sequences reaches its end. To help detect bugs it is useful to have sequence types that check to see if two or more sequences end on the same iteration. For this purpose there is second set of sequence types called synchronous sequences. These are identical to the ones listed above 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 a non-synchronous sequence no further checking is done.

The synchronous sequences are:

Note that the synchronous count% must have an end, unlike the nonsynchronous count%.

Examples

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

(lambda (my-list predicate)
  (reduce ((list* elt my-list)
           (count* i 0))
          ((hits '()))
    (if (predicate elt)
        (cons i hits)
        hits)
    (reverse hits))

Looking for the index of an element of a list. 

(lambda (my-list predicate)
  (iterate loop
           ((list* elt my-list)
            (count* i 0))
           ()                                ; no state
    (if (predicate elt)
        i
        (loop))))

Reading one line. 

(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)
        ; no newline at end of file
        (list->string (reverse chars)))))

Counting the lines in a file. We can't use count* because we need the value of the count after the loop has finished. 

(define (line-count name)
  (call-with-input-file name
    (lambda (in)
      (reduce ((input* l in read-line))
              ((i 0))
        (+ i 1)))))

Defining sequence types

The sequence types are object-oriented macros similar to enumerations. A non-synchronous sequence macro needs to supply three values: #f to indicate that it isn't synchronous, a list of state variables and their initializers, and the code for one iteration. The first two methods are CPS'ed: they take another macro and argument to which to pass their result. The synchronized? method gets no additional arguments. The state-vars method is passed a list of names which will be bound to the arguments to the sequence. The final method, for the step, 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.

The definition of list* is 

(define-syntax list*
  (syntax-rules (synchronized? state-vars step)
    ((list* synchronized? (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 final-exp)
     (if (null? list-var)
         final-exp
         (let ((value-var (car list-var))
               (list-var (cdr list-var)))
           loop-body)))))

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

(define-syntax list%
  (syntax-rules (sync done)
    ((list% sync (next more))
     (next #t more))
    ((list% done (start-list) (list-var))
     (null? list-var))
    ((list% stuff ...)
     (list* stuff ...))))

Expanded code

The expansion of 

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

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

Previous: Sockets | Next: Regular expressions