reduceare extensions of named-
letfor 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.
reduceare in structure
The syntax of
sequence-data...) ...) ((
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
If any sequence has reached its limit the value of the
the value of
final-expression, if present, or the current values of
state-variables, returned as multiple values.
If no sequence has reached
body-expression is evaluated and either calls
new values for the
state-variables, or returns some other value(s).
loop-name and the
exactly as in named-
let. The named-
is equivalent to an(let loop-name ((state-variable initial-value) ...) body ...)
iterateexpression with no sequences (and with an explicit
letwrapped around the body expressions to take care of any internal
(iterate loop-name () ((state-variable initial-value) ...) (let () body ...))
sequence-types are keywords (they are actually macros of a particular
form; it is easy to add additional types of sequences).
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.
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.
body-expression does not call
final-expression is not evaluated.
state-variables are visible in
final-expression but the
sequence-variables are not.
body-expression and the
final-expression are in tail-position within
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).
iterate expression is not meant to terminate before a sequence
has reached its end,
body-expression will always end with a tail call to
Reduce is a macro that makes this common case explicit.
The syntax of
the same as that of
iterate, except that there is no
body-expression returns new values of the
instead of passing them to
body-expression must return as many values as there are state
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
sequence-data...) ...) ((
The value(s) returned by an instance of
reduce is the value(s) returned
final-expression, if present, or the current value(s) of the state
variables when the end of one or more sequences is reached.
reduce expression can be rewritten as an equivalent
expression by adding a
loop-var and a wrapper for the
body-expression that calls the
(iterate loop ((
sequence-data...) ...) ((
initial-value) ...) (call-with-values (lambda ()
body-expression) loop) [
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.
count* the element variable is bound to the elements of the sequence
startand exclusive of
end. The default
stepis 1. The sequence does not terminate if no
endis given or if there is no N > 0 such that
=is used to test for termination). For example,
(count* i 0 -1)doesn't terminate because it begins past the
(count* i 0 1 2)doesn't terminate because it skips over the
input* the elements are the results of successive applications
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,
is the same as(list* elt my-list)
where(stream* elt list->stream my-list)
(lambda (list) (if (null? list) (values 'ignored #f) (values (car list) (cdr list))))
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
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)))))
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.
two methods are CPS'ed: they take another macro and argument to
which to pass their result.
synchronized? method gets no additional arguments.
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
The definition of
(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 ...))))
The expansion of
is(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)))))))
The only inefficiencies in this code are the
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: Macros for writing loops | Next: Macros for writing loops