2.22.6 Related work and acknowledgements

Several other proposals related to the mechanism specified here exists. The following mechanisms are made for and in Scheme (or at least a specific dialect thereof).

First of all, the report R5RS of Scheme itself defines two constructs for writing loops: do and named let. Both constructs express a single loop (not nested), possibly with several variables running in parallel, based on explicit manipulation of the state variables. For example:

(do ([x 0 (+ x 1)])
    ([= x 10])
  (display x))

explicitly mentions how to obtain the next binding of x.

Richard Kelsey’s “Macros for writing loops”, are an extension to Scheme48 to simplify the formulation of loops. The basic idea is to stick with a do–like syntax for more sophisticated loop constructs, not necessarily manipulating a state variable explicitly. For example:

(list* x '(1 2 3))

expresses an enumeration of the variable x through the list (1 2 3) without explicit state manipulation. The iteration constructs of MWL, named iterate and reduce, express a single (not nested) loop (iterate) or comprehension (reduce) with any number of parallel enumerations.

A most important feature of the MWL–concept is a modular way to add sequence types (generators). In effect, the addition of a new sequence type does not require a modification of the existing macros. This is achieved by carefully limiting the expressive power of the loop constructs and by using the macros in Continuation Passing Style to call other macros. The MWL–concept, and its implementation, were most influential for this SRFI.

Another related mechanism is the library of streams recently submitted by Phil L. Bewig as SRFI-40 (superseded by SRFI-41). The library contains a data type to represent even streams (both car and cdr potentially delayed) and defines procedures for manipulating these streams. Moreover, the macro stream-of defines a lazy comprehension resulting in the stream of values of an expression subject to generators and filters.

A fixed set of generators (lists, vector, string, port, and naturally: streams) is supported; extending the list of generators requires changing stream-of. Nevertheless, modularity is high since it is easy to define a procedure producing a stream object and this can be used for enumeration. The order of enumeration is left unspecified to allow interleaving of generators (also refer to above).

Before Phil submitted his SRFIs, we had a short discussion in which we clarified the semantic and syntactic differences of our approaches. It turned out that the mechanisms are sufficiently different not to unify them. The most important difference is the design rationale: Phil created his library to support the stream paradigm in Scheme, inspired by the work done for Haskell and other lazy languages, and intrigued by the beauty of programming with infinite streams. My work only aims at a convenient way of expressing frequent patterns of loops in a compact way. For what it is worth, section SRFI-40-ec contains a suggestion for extending the eager comprehension mechanism for SRFI-41 streams.

Phil’s work on streams and lazy comprehensions in Scheme triggered Eli Barzilay to implement a library of eager comprehensions for PLT–Scheme. The mechanism implemented by Eli is in essence very similar to the one proposed in this SRFI, and the two efforts have been independent until recently. Syntactically, Eli uses infix operators for generators, whereas this SRFI is purely prefix, and Eli uses the:

[expr | outer .. inner]

convention for nesting, whereas this SRFI uses the:

[outer .. inner | expr]

convention. Semantically, Eli’s mechanism defines more flexible loops than this SRFI. Comprehensions are regarded as generalized collection processes like fold and reduce. The mechanism in this SRFI is more restricted with respect to control flow (there is no general while) and more extensive with respect to generators and comprehensions. Despite the strong conceptual similarity, the design rationales are different. This SRFI focuses on portability and modular extension, whatever that may cost in terms of expressive power.

Finally, I would like to thank Mike Sperber for his encouragement to proceed with the SRFI and for several discussions of the matter. In particular, the dispatching mechanism evolved rapidly during discussions with Mike.