.............................. A Library of Streams .............................. .............................. by Philip L. Bewig .............................. .............................. pbewig@swbell.net .............................. .............................. 31 January 2003 .............................. ABSTRACT ~~~~~~~~ Along with higher-order functions, one of the hallmarks of functional programming is lazy evaluation. A primary manifestation of lazy evaluation is lazy lists, generally called streams by scheme programmers, where evaluation of a list element is delayed until its value is needed. This library defines a set of procedures and syntax that allow convenient processing of streams, describes why they were written the way they were, and shows several examples of their use. RATIONALE ~~~~~~~~~ Two of the defining characteristics of functional programming languages are higher-order functions, which provide a powerful tool to allow programmers to abstract data representations away from an underlying concrete implementation, and lazy evaluation, which allows programmers to modularize a program and recombine the pieces in useful ways. Scheme provides higher-order functions through its lambda keyword and lazy evaluation through its delay keyword. A primary manifestation of lazy evaluation is lazy lists, generally called streams by scheme programmers, where evaluation of a list element is delayed until its value is needed. Streams can be used, among other things, to compute with infinities, conveniently process simulations, program with coroutines, and reduce the number of passes over data. This library defines a practical set of functions and syntax for programming with streams. Scheme has a long tradition of computing with streams. The great computer science textbook "Structure and Interpretation of Computer Programs" (known by its acronym SICP), by Harold Abelson and Gerald Jay Sussman, with Julie Sussman (1996, MIT Press, ISBN 0-262-01153-0, with full text available at www-mitpress.mit.edu/sicp), uses streams extensively. The example given in R5RS makes use of streams to integrate systems of differential equations using the method of Runge-Kutta. MIT Scheme, the original implementation of scheme, provides streams natively. "Scheme and the Art of Programming", a textbook by George Springer and Daniel P. Friedman, discusses streams. Some scheme-like languages also have traditions of using streams: Winston and Horn, in their classic lisp textbook, discuss streams, and so does Larry Paulson in his text on ML. Streams are an important and useful data structure. Basically, a stream is much like a list, and can either be null or can consist of an object (the stream element) followed by another stream; the difference to a list is that elements aren't evaluated until they are accessed. All the streams mentioned above use the same underlying representation, with the null stream represented by '() and stream pairs constructed by (cons car (delay cdr)), which must be implemented as syntax. These streams are known as head-strict, because the head of the stream is always computed, whether or not it is needed. Streams are the central data type -- just as arrays are for most imperative languages and lists are for lisp and scheme -- for the "pure" functional languages miranda and haskell. But those streams are subtly different from the traditional scheme streams of SICP et al. The difference is at the head of the stream, where miranda and haskell provide streams that are fully lazy, with even the head of the stream not computed until it is needed. We'll see in a moment the operational difference between the two types of streams. Philip Wadler, Walid Taha, and David MacQueen, in their paper "How to add laziness to a strict language without even being odd" (available at http://citeseer.nj.nec.com/102172.html in various formats), describe how they added streams to the SML/NJ compiler. They discuss two kinds of streams: odd streams, as in SICP et al, and even streams, as in haskell; the names odd and even refer to the parity of the number of constructors (delay, cons, nil) used to represent the stream. Here are the first two figures from their paper, rewritten in scheme: ;;; FIGURE 1 -- ODD ;;; FIGURE 2 -- EVEN (define nil1 '()) (define nil2 (delay '())) (define (nil1? strm) (define (nil2? strm) (null? strm)) (null? (force strm))) (define-syntax cons1 (define-syntax cons2 (syntax-rules () (syntax-rules () ((cons1 obj strm) ((cons2 obj strm) (cons obj (delay strm))))) (delay (cons obj strm))))) (define (car1 strm) (define (car2 strm) (car strm)) (car (force strm))) (define (cdr1 strm) (define (cdr2 strm) (force (cdr strm))) (cdr (force strm))) (define (map1 func strm) (define (map2 func strm) (delay (force (if (nil1? strm) (if (nil2? strm) nil1 nil2 (cons1 (cons2 (func (car1 strm)) (func (car2 strm)) (map1 func (cdr1 strm))))) (map2 func (cdr2 strm))))))) (define (countdown1 n) (define (countdown2 n) (delay (force (cons1 n (countdown1 (- n 1)))) (cons2 n (countdown2 (- n 1)))))) (define (cutoff1 n strm) (define (cutoff2 n strm) (cond (cond ((zero? n) '()) ((zero? n) '()) ((nil1? strm) '()) ((nil2? strm) '()) (else (else (cons (cons (car1 strm) (car2 strm) (cutoff (- n 1) (cutoff2 (- n 1) (cdr1 strm)))))) (cdr2 strm)))))) It is easy to see the operational difference between the two kinds of streams, using an example adapted from the paper: > (define (12div n) (/ 12 n)) > (define (12div n) (/ 12 n)) > (cutoff1 4 > (cutoff2 4 (map1 12div (countdown1 4))) (map2 12div (countdown2 4))) error: divide by zero (3 4 6 12) The problem of odd streams is that they do too much work, having an "off-by-one" error that causes them to evaluate the next element of a stream before it is needed. Mostly that's just a minor leak of space and time, but if evaluating the next element causes an error, such as dividing by zero, it's a silly, unnecessary bug. It is instructive to look at the coding differences between odd and even streams. We expect the two constructors nil and cons to be different, and they are; the odd nil and cons return a strict list, but the even nil and cons return promises. Nil?, car and cdr change to accomodate the underlying representation differences. Cutoff is identical in the two versions, because it doesn't return a stream. The subtle but critical difference is in map and countdown, the two functions that return streams. They are identical except for the (delay (force ...)) that wraps the return value in the even version. That looks odd, but is correct. It is tempting to just eliminate the (delay (force ...)), but that doesn't work, because, given a promise x, even though (delay (force x)) and x both evaluate to x when forced, their semantics are different, with x being evaluated and cached in one case but not the other. That evaluation is, of course, the same "off-by-one" error that caused the problem with odd streams. Note that (force (delay x)) is something different entirely, even though it looks much the same. Unfortunately, that (delay (force ...)) is a major notational inconvenience, because it means that the representation of streams can't be hidden inside a few primitives but must infect each function that returns a stream, making streams harder to use, harder to explain, and more prone to error. Wadler et al solve the notational inconvenience in their SML/NJ implementation by adding special syntax -- the keyword "lazy" -- within the compiler. Since scheme allows syntax to be added via a macro, it doesn't require any compiler modifications to provide streams. Shown below is a scheme implementation of figure 3 from the paper, with the (delay (force ...)) hidden within stream-define, which is the syntax used to create a function that returns a stream: ;;; FIGURE 1 -- ODD ;;; FIGURE 2 -- EVEN ;;; FIGURE 3 -- EASY (define nil1 (define nil2 (define nil3 '()) (delay '())) (delay '())) (define (nil1? strm) (define (nil2? strm) (define (nil3? strm) (null? strm)) (null? (force strm)) (null? (force strm))) (define-syntax cons1 (define-syntax cons2 (define-syntax cons3 (syntax-rules () (syntax-rules () (syntax-rules () ((cons1 obj strm) ((cons2 obj strm) ((cons3 obj strm) (cons (delay (delay obj (cons (cons (delay obj obj strm))))) strm))))) strm))))) (define (car1 strm) (define (car2 strm) (define (car3 strm) (car strm)) (car (force strm))) (car (force strm))) (define (cdr1 strm) (define (cdr2 strm) (define (cdr3 strm) (force (cdr strm))) (cdr (force strm))) (cdr (force strm))) (define-syntax stream-define (syntax-rules () ((stream-define (name args ...) body0 body1 ...) (define (name args ...) (delay (force (begin body0 body1 ...))))))) (define (map1 func strm) (define (map2 func strm) (stream-define (map3 func strm) (delay (force (if (nil1? strm) (if (nil2? strm) (if (nil3? strm) nil1 nil2 nil3 (cons1 (cons2 (cons3 (func (func (func (car1 strm)) (car2 strm)) (car3 strm)) (map1 (map2 (map3 func func func (cdr1 (cdr2 (cdr3 strm))))) strm))))))) strm))))) (define (countdown1 n) (define (countdown2 n) (stream-define (countdown3 n) (delay (force (cons1 (cons2 (cons3 n n n (countdown1 (countdown2 (countdown3 (- n 1)))) (- n 1)))))) (- n 1)))) (define (cutoff1 n strm) (define (cutoff2 n strm) (define (cutoff3 n strm) (cond (cond (cond ((zero? n) '()) ((zero? n) '()) ((zero? n) '()) ((nil1? strm) '()) ((nil2? strm) '()) ((nil3? strm) '()) (else (else (else (cons (cons (cons (car1 strm) (car2 strm) (car3 strm) (cutoff1 (cutoff2 (cutoff3 (- n 1) (- n 1) (- n 1) (cdr1 (cdr2 (cdr3 strm)))))) strm)))))) strm)))))) It is now easy to see the notational inconvenience of Figure 2, as the bodies of map1 and map3 are identical, as are countdown1 and countdown3. All of the inconvenience is hidden in the stream primitives, where it belongs, so functions that use the primitives won't be burdened. This means that users can just step up and use the library without any knowledge of how the primitives are implemented, and indeed the implementation of the primitives can change without affecting users of the primitives, which would not have been possible with the streams of Figure 2. With this implementation of streams, (cutoff3 4 (map3 12div (countdown3 4))) evaluates to (3 4 6 12), as it should. This library provides streams that are even, not odd. This decision overturns years of experience in the scheme world, but follows the traditions of the "pure" functional languages such as miranda and haskell. The primary benefit is elimination of the "off-by-one" error that odd streams suffer. Of course, it is possible to use even streams to represent odd streams, as Wadler et al show in their figure 4, so nothing is lost by choosing even streams as the default. Obviously, stream elements are evaluated when they are accessed, not when they are created; that's the definition of lazy. Additionally, stream elements must be evaluated only once, and the result cached in the event it is needed again; that's common practice in all languages that support streams. Following the rule of R5RS section 1.1 fourth paragraph, an implementation of streams is permitted to delete a stream element from the cache and reclaim the storage it occupies if it can prove that the stream element cannot possibly matter to any future computation. SPECIFICATION ~~~~~~~~~~~~~ A stream is a new data type, disjoint from all other data types, that contains a promise that, when forced, is either nil (a single object distinguishable from all other objects) or consists of an object (the stream element) followed by a stream. Each stream element is evaluated exactly once, when it is first retrieved (not when it is created); once evaluated its value is saved to be returned by subsequent retrievals without being evaluated again. Streams and stream elements are never mutated; all functions are purely applicative. Stream-define, stream-cons, and stream-of are the only syntax definitions. The various folds, append, concat, reverse, and sort only make sense with finite streams. Errors are not required to be signalled as in R5RS section 1.3.2, though implementations are encouraged to detect and report the error. Constructors: STREAM-NULL -- the nil stream STREAM-CONS object stream -- syntax to prepend object onto head of stream STREAM object ... -- a newly-allocated stream whose elements are object ... LIST->STREAM list -- a newly-allocated stream containing elements of list VECTOR->STREAM vector -- a newly-allocated stream containing elements of vector STRING->STREAM string -- newly-allocated stream containing characters of string STREAM-OF expr qualifier ... -- comprehension syntax for infinite streams STREAM-FROM start [step] -- stream of numbers from start [step=1] STREAM-FROM-TO start stop [step] -- stream from start to stop [step=1] STREAM-REPEAT obj ... -- infinite stream of obj ... STREAM-ITERATE func obj -- (stream obj (func obj) (func (func obj)) ...) Stream-null is the distinguished nil stream. Stream-cons is the primitive stream constructor, and is necessarily implemented as syntax; the result of every stream-cons must be different from the result of every other stream-cons, in the sense of eq?. Stream and list->stream both construct finite streams containing the indicated objects, differing only in how they take their arguments; when passed no objects, both stream and list->stream return stream-null. Similar conversions are provided from vectors and strings. A stream comprehension consists of the syntactic keyword "stream-of," followed by a result expression, followed by one or more qualifiers. There are three types of qualifiers: generators, declarations, and filters. A generator is distinguished by the syntactic keyword "in"; the variable name given before the keyword is bound sequentially to each element of the generator stream in subsequent qualifiers and the result expression. Additional syntactic keywords "in list", "in vector", "in string", "in port", and "in port reader" allow the generators to be lists (which generate the individual elements of the list, in order), vectors (which generate the individual elements of the vector, in order), strings (which generate the individual characters of the string), ports (which generate the individual characters from the port), or modified ports (which generate the individual elements recognized by the reader function), respectively, or an expression which evaluates to one of these types. A declaration is distinguished by the syntactic keyword "is"; the variable name given before the keyword is let-bound to the expression following the keyword in subsequent qualifiers and the result expression. A filter is a boolean expression using the previously bound variables or free variables of the expression; only expressions for which the filter is not #f are included in the result expression. The result of a stream comprehension is a stream consisting of the elements in the form of the result expression that were generated by the cross-product of the various generators and are not #f for each of the filters. A stream comprehension may appear in a program anywhere a stream may appear. The order in which generator elements appear in the result stream is unspecified. The remaining constructors compute streams on demand. Stream-from produces a stream of numbers with a specified starting point and optional step size; the start and step need not be integral, and may be negative. Stream-from-to is like stream-from, but produces finite streams; the stop value is included in the stream, and the default step is -1 if stop is less than start. Stream-repeat creates a cycle of the indicated objects, repeating from the start as necessary. Stream-iterate repeatedly evaluates the same function, first on the base object, then on the result of applying the function to the base object, and so on, with the initial base as the first element of the result stream; a simple example of stream-iterate produces random numbers, first a seed, then a linear congruential function applied to the seed, and so on. Predicates: STREAM? object -- #t if object is a stream, #f otherwise STREAM-NULL? object -- #t if object is the null stream, #f otherwise STREAM-PAIR? object -- #t if object is a non-null stream, #f otherwise These predicates recognize and categorize streams. If stream? is #f, both stream-null? and stream-pair? must also be #f. If stream? is #t, one of stream-null? and stream-pair? must be #t and the other must be #f. Selectors: STREAM-CAR stream -- first item in stream, error if empty STREAM-CDR stream -- stream containing all items in stream except first, error if empty STREAM-CAR+CDR stream -- (values (stream-car stream) (stream-cdr stream)) STREAM-LAST stream -- last item in stream, error if empty STREAM-BUTLAST stream -- stream containing all items in stream except last STREAM-CAAR to STREAM-CDDDDR -- compositions of stream-car and stream-cdr STREAM-REF stream n -- nth item in stream, counting from zero STREAM-FIRST to STREAM-TENTH -- synonym for (stream-ref stream (- nth 1)) STREAM-TAKE n stream -- stream of first n items in stream STREAM-TAKE-UNTIL pred? stream -- stream of stream prefix where pred? is #f STREAM-TAKE-WHILE pred? stream -- stream of stream prefix where pred? is not #f STREAM-DROP n stream -- nth stream-cdr of stream STREAM-DROP-UNTIL pred? stream -- stream less prefix not satisfying pred? STREAM-DROP-WHILE pred? stream -- stream less prefix satisfying pred? STREAM-SPLIT n stream -- (values (take ...) (drop ...)) STREAM-SPLIT-UNTIL pred? stream -- (values (take-until ...) (drop-until ...)) STREAM-SPLIT-WHILE pred? stream -- (values (take-while ...) (drop-while ...)) All the selector functions return either single items from a stream or a sub-stream of a stream. Stream-car is the first item in a stream, stream-cdr is the rest of the stream after the first item, and stream-car+cdr deconstructs a stream into its primitive values. Stream-last and stream-butlast are the analogous selectors at the end of a stream. There are twenty-eight functions stream-caar through stream-cddddr that compose combinations of stream-car and stream-cdr. All these functions result in an error if the indicated stream element or sub-stream doesn't exist. Stream-ref returns the nth item in the stream, counting from zero. The ten functions stream-first through stream-tenth return the nth item in the stream, counting from one. All these functions result in an error if the indicated n is out of bounds. The various stream-take functions all return a prefix of a stream, the various stream-drop functions all return a suffix of a stream, and the various stream-split functions return both. All the streams returned by these functions can be recombined with stream-append; thus, (stream-append (stream-take n stream) (stream-drop n stream)) always returns a copy of the original stream for any non-negative n and stream. None of these functions ever produce an error; if the indicated stream doesn't exist, the null stream is returned. Higher-order functions: STREAM-DEFINE (name args ...) body0 body1 ... -- create stream-valued function STREAM-MAP func stream ... -- stream produced by applying func to streams STREAM-FOR-EACH proc stream ... -- perform proc element-wise on stream ... STREAM-FILTER pred? stream -- stream containing only items with pred? not #f STREAM-REMOVE pred? stream -- stream containing only items with pred? #f STREAM-PARTITION pred? stream -- (values (pred? => not #f) (pred? => #f)) STREAM-FOLD-LEFT func base stream ... -- apply func pairwise to base and items STREAM-FOLD-LEFT-ONE func stream ... -- apply func pairwise to stream items STREAM-FOLD-RIGHT func base stream ... -- apply func pairwise to base and items STREAM-FOLD-RIGHT-ONE func base stream ... -- apply func pairwise to items STREAM-SCAN-LEFT func base stream ... -- stream of partial reductions of stream STREAM-SCAN-LEFT-ONE func stream ... -- partial reductions of stream from first STREAM-SCAN-RIGHT func stream ... -- stream of partial reductions of stream STREAM-SCAN-RIGHT-ONE func stream ... -- partial reductions of stream from first Stream-define is syntax that creates a function that returns a stream; it is used to define all the other stream-valued functions in the library. Stream-define takes an optional rest parameter and works analogously to define. There is no corresponding stream-lambda. Stream-map traverses one or more streams, creating a new stream by applying a function element-wise to the given streams; the arity of the function must match the number of streams. Stream-for-each also traverses one or more streams, performing a procedure with the appropriate arity element-wise for its side effects. Both visit the elements of a stream in order, starting from their cars. Stream-filter and stream-remove apply a predicate to each element of a stream and create a new stream containing only those elements that do, or do not, satisfy the predicate. Stream-partition returns both. The order of elements in the output stream is the same as their order in the input stream. The various folds are the fundamental iterators on finite streams, reducing one or more streams to a single value by applying a binary function pairwise to successive items. The left folds operate from the cars of the streams to the tails, and the right folds operate in the opposite direction. The -one variants take the leading elements in the streams as the base to begin pairwise operations, while the plain variants give an explicit base. There are several examples of the use of stream-fold in the examples section. The various scans accumulate partial folds in a stream, working equally well on both finite and infinite streams. The result of the scan is a stream containing the base element, followed by the result of the operation on the base and first element, followed by the result of the operation on the first result and the second element, and so on. Input and output: PORT->STREAM reader [port] -- stream of objects returned by reader from port PORT->CHAR-STREAM [port] -- stream of characters on [current input] port PORT->LINE-STREAM [port] -- stream of lines on [current input] port PORT->WORD-STREAM [port] -- stream of words on [current input] port STREAM-DISPLAY stream [port] -- display stream on [current output] port STREAM-DISPLAY-LINES stream [port] -- display newline-separated stream STREAM-WRITE stream [port] -- write stream on [current output] port Port->stream is the fundamental stream input function. The reader argument is a function that reads a port and either returns the next object of interest from the port or the eof-object when the port terminates. The other three input functions specialize port->stream as indicated; the lines of a line-stream are separated by newlines, and the words of a word-stream are maximal sequences that satisfy char-alphabetic?. All four input functions read from either the port given as their last argument or the current input port. The three output functions send each stream element to either the current output port or the port indicated in their final argument. Stream-display outputs the elements in the manner of the display function, for humans, stream-display-lines does the same but with elements separated by newlines, and stream-write outputs the elements in the manner of the write function, for computers. Other stream operations: STREAM->LIST stream [n] -- new list containing [first n] elements of stream STREAM->VECTOR stream [n] -- new vector containing [first n] elements of stream STREAM->STRING stream [n] -- new string containing [first n] stream characters STREAM-APPEND stream ... -- append one or more streams end to end STREAM-CONCAT stream -- append a stream of streams into a single stream STREAM-REVERSE stream -- new stream with elements of stream in reverse order STREAM-ZIP stream ... -- convert multiple streams to stream of lists STREAM-UNZIP stream -- convert stream of lists to multiple streams STREAM-ALTERNATE stream ... -- stream of items from streams in round-robin STREAM-INTERLEAVE stream -- stream of items from stream of streams, diagonally STREAM-MERGE lt? stream ... -- merge sorted streams into a new stream by lt? STREAM-SORT lt? stream -- newly-allocated stream with elements ordered by lt? STREAM-UNIQ eql? stream -- new stream with adjacent duplicates removed Several useful stream operations that don't fit elsewhere are described here. Stream->list returns a newly-allocated list containing the elements of the given stream, in order; similar conversions are provided for vectors and strings of characters. Stream-append and stream-concat concatenate multiple streams into one, differing only in how they take their arguments. Stream-reverse returns a newly-allocated stream with the elements of the original stream in reverse order. Stream-zip and stream-unzip are inverses, converting multiple streams to a stream of lists and back. Stream-alternate creates a newly-allocated stream containing the elements of the argument stream in "round-robin" fashion, first the car of each stream, in order, followed by the cadr of each stream, in order, and so on. Stream-interleave creates a newly-allocated stream containing the elements of the argument streams in "diagonal" order; it is used internally by the stream-of comprehensions. Stream-merge takes a less-than predicate lt? and one or more streams ordered by the less-than predicate and returns a newly-allocated stream with the elements of the original streams ordered by the less-than predicate. Stream-sort takes a less-than predicate lt? and returns a newly-allocated stream with the elements of the original stream ordered by the less-than predicate; it is required to run in O(n log n) time. Stream-merge and stream-sort must both be stable, with equal elements appearing in the output in the same order they appeared in the input. Stream-uniq creates a new stream containing the elements of the input stream with only one occurrence of adjacent duplicates, in the same order as the original stream. EXAMPLES ~~~~~~~~ Numerous examples are given below to cement the reader's understanding of streams and to show how streams can be exploited. We start with some simple examples of infinite streams shown in virtually all textbooks on functional programming: > (define ones (stream-cons 1 ones)) > (stream->list ones 10) (1 1 1 1 1 1 1 1 1 1) > (define nats (stream-map + ones (stream-cons 0 nats))) > (stream->list nats 10) (1 2 3 4 5 6 7 8 9 10) > (define facts (stream-map * nats (stream-cons 1 facts))) > (stream->list facts 10) (1 2 6 24 120 720 5040 40320 362880 3628800) It is easy to see how these expressions work, though until you master some of the stream idioms, it can be hard to create them yourself. Most imperative-style loops translate fairly directly to various maps, filters, zips, folds, and scans of streams, and if you look for them, you will be rewarded with natural and concise code. The next example generates the stream of prime numbers, based on an example by Chris Reade in his book "Elements of Functional Programming" (1989, Addison-Wesley, ISBN 0-201-12915-9), section 8.2.3. ;; PRIMES -- the stream of prime numbers (stream-define (next-prime a b strm) (let ((c (stream-car strm)) (x (stream-cdr strm))) (cond ((< b c) (next-prime a (+ a b) strm)) ((< c b) (stream-cons c (next-prime a b x))) (else (next-prime a (+ a b) x))))) (stream-define (sift a x) (next-prime a (+ a a) x)) (stream-define (sieve strm) (let ((a (stream-car strm)) (x (stream-cdr strm))) (stream-cons a (sieve (sift a x))))) (define primes (sieve (stream-from 2))) Next-prime finds the next number in strm that isn't a multiple of a. Sift initializes the b parameter of next-prime, which is always the next higher multiple of a. Sieve adds the next number in sequence to the stream of primes, then sifts; because it calls itself recursively, sieve eventually uses each prime number as the basis of a sift. Finally, primes initializes the sieve. The tree of calls grows like this: sieve <- from 2 2:: <- sieve <- sift 2 <- from 3 2:: <- sieve <- next-prime 2 4 <- 3::from 4 2::3:: <- sieve <- sift 3 <- next-prime 2 4 <- from 4 2::3:: <- sieve <- next-prime 3 6 <- next-prime 2 6 <- from 5 2::3::5:: <- sieve <- sift 5 <- next-prime 3 6 <- next-prime 2 6 <- from 6 A similar example, that appears in many texts, creates an ordered stream of the hamming numbers, defined as the numbers 2^i * 3^j * 5^k for all non-negative i, j, and k. ;; HAMMING -- stream of hamming numbers (define hamming (stream-cons 1 (stream-uniq = (stream-merge < (stream-map (lambda (x) (* x 2)) hamming) (stream-map (lambda (x) (* x 3)) hamming) (stream-map (lambda (x) (* x 5)) hamming))))) Assume that a stream of hamming numbers already exists. To get more hamming numbers, make three copies of the stream and multiply each element of the three streams by 2, 3, and 5, respectively, then merge the three copies in order, append to the original stream, and eliminate duplicates. The initial hamming stream consists only of the number 1, which is 2^0 * 3^0 * 5^0. To display the first twenty hamming numbers, say (stream->list hamming 20). Programming with streams can sometimes be tricky, with even very small changes having very large consequences. Two versions of the cutoff function described previously are shown below (all the "4" functions are identical to their "3" counterparts except cutoff): ;;; THIS ONE WORKS ;;; THIS ONE DOESN'T (define (cutoff3 n strm) (define (cutoff4 n strm) (cond (cond ((zero? n) '()) ((nil4? strm) '()) ((nil3? strm) '()) ((zero? n) '()) (else (else (cons (cons (car3 strm) (car4 strm) (cutoff3 (- n 1) (cutoff4 (- n 1) (cdr3 strm)))))) (cdr4 strm)))))) The only difference is the order of the two tests. But the difference is huge. The expression (cutoff4 4 (map4 12div (countdown4 4))) fails with a divide-by-zero error. The problem is that when countdown4 reaches zero, nil4? forces the stream and produces a divide-by-zero error; the fix is that zero? must be called first to stop the recursion and prevent the stream being forced. This kind of bug can be very hard to see. In fact, it was. This very bug bit me as I was translating the sample code from Wadler et al, and cost about a week in the development of the library. Stream comprehensions are a remarkably simple and useful notation for building streams of maps and filters invented by David Turner for his KRC language based on the set notation of Zermelo and Frankel. Here, for instance, is a classic stream comprehension for finding pythagorean triples, written in both haskell and in the notation of this library: -- pythagorean triples ;; pythagorean triples pyth n = (define (pyth n) [ (a,b,c) | (stream-of (list a b c) a <- [1 .. n], (a in (stream-from-to 1 n)) b <- [a .. n], (b in (stream-from-to a n)) c <- [b .. n], (c in (stream-from-to b n)) a*a + b*b == c*c ] (= (+ (* a a) (* b b)) (* c c)))) Stream comprehensions in this library are introduced by the stream-of syntactic keyword. Following stream-of is a result expression and a series of either generators, declarations, or filters; there must be at least one item in the series, and the first item must not be a filter. Generators are distinguished by the "in" keyword; the given variable is bound to each element of the given stream. There is also syntax to allow lists, vectors and strings to be generators; see the specification of the stream-of syntax for details. Declarations are distinguished by the "is" keyword, and function as shorthand for a let-binding that is local within the stream comprehension. Filters, generators and declarations may use any variable bound in a prior generator or declaration or free in the comprehension; filters must evaluate to a boolean. The result of a stream comprehension is a stream consisting of the elements in the form of the result expressions that were generated by the cross-product of the various generators and are not #f for each of the filters. For example, calling (pyth 15) evaluates to (stream (3 4 5) (5 12 13) (6 8 10) (9 12 15)). Beware that the order of elements in the result is undefined in the specification and not necessarily what you might expect, a consequence of the stream-interleave algorithm that allows any of the streams to be infinite. The pyth stream comprehension expands to the following code, which you can be glad was written for you by a macro: (define (pyth n) (let* ((signal (list 'signal)) (strm (let ((f (lambda (a) (let ((f (lambda (b) (let ((f (lambda (c) (if (= (+ (* a a) (* b b)) (* c c)) (stream (list a b c)) (stream signal))))) (stream-interleave (stream-map f (stream-from-to b n))))))) (stream-interleave (stream-map f (stream-from-to a n))))))) (stream-interleave (stream-map f (stream-from-to 1 n)))))) (stream-remove (lambda (x) (eq? x signal)) strm))) Here are some more examples of stream comprehensions: (stream-of (* x x) (x in (stream-from 1)) (odd? x)) => (stream 1 9 25 49 81 121 169 225 289 ...) (stream->list (stream-of x (x in (stream-zip (stream 'a 'b 'c) (stream-from 1))) => ((a 1) (b 2) (c 3)) ; parallel generators used to provide index (stream-define (qsort lt? strm) (if (stream-null? strm) stream-null (stream-append (qsort lt? (stream-of x (x in (stream-cdr strm)) (lt? x (stream-car strm)))) (stream (stream-car strm)) (qsort lt? (stream-of x (x in (stream-cdr strm)) (not (lt? x (stream-car strm)))))))) => # to sort a stream by the lt? less-than predicate (define (rember x lst) ; remove x from lst (cond ((null? lst) lst) ((equal? x (car lst)) (cdr lst)) (else (cons (car lst) (rember x (cdr lst)))))) (stream-define (perms lst) (if (null? lst) (stream '()) (stream-of (cons x perm) (x in list lst) (perm in (perms (rember x lst)))))) => # to create a stream of permutations of a list The declaration syntax is shorthand for a let expression (not letrec, as the variable named in the qualifier isn't bound until subsequent qualifiers); given a qualifier (var is declaration), var will be let-bound to declaration in subsequent qualifiers and the result expression. A simple example is (stream-of (cons x y) (x in (stream-from 1)) (y is (* x x))) which evaluates to (stream (1 . 1) (2 . 4) (3 . 9) (4 . 16) (5 . 25) ...). Be careful when writing stream comprehensions. The left example works fine, but the right example doesn't: ; THIS ONE WORKS ; THIS ONE DOESN'T (stream-of (list a b c) (stream-of (list a b c) (a in (stream-from-to 1 20)) (a in (stream-from 1)) (<= a 20) (b in (stream-from-to a 20)) (b in (stream-from a)) (<= b 20) (c in (stream-from-to b 20)) (c in (stream-from b)) (<= c 20) (= (+ (* a a) (* b b)) (* c c))) (= (+ (* a a) (* b b)) (* c c))) The reason it fails is because the first generator keeps on generating integers even after reaching the limit, testing each to see if it exceeds the limit; the one that works stops generating integers at the limit, returning the null stream. Just remember that computing with infinities can be troublesome. It is a surprise to the unwary that stream-of generates result expressions in an undefined order. The problem occurs when there are multiple infinite generators, like this: (stream-of (list i j) (i in (stream-from 1)) (j in (stream-from 1))) It makes sense to many programmers that the cross-products are generated in depth-first order, (1 1) (1 2) (1 3) (1 4) ... (2 1) (2 2) (2 3) (2 4) .... The problem is that if the generators are infinite, none of the (2 1) (2 2) ... results will ever appear in the output stream, for the same reason that (stream-append s1 s2) results in s1 if s1 is infinite; one stream keeps generating forever, and the other stream is never allowed to generate at all. The stream-interleave function fixes this problem by "diagonalizing" the order in which results are generated; for the stream comprehension shown above, the result will be (stream (1 1) (2 1) (1 2) (3 1) (1 3) (2 2) (1 4) (4 1) (1 5) (2 3) (1 6) (3 2) (1 7) (2 4) (1 8) (5 1) (1 9) (2 5) ...). This order is fixed for a given implementation of stream-interleave, but different implementations of stream-interleave could give different result orders. Haskell programmers should be aware that the stream comprehensions given here are a subtle improvement over haskell's list comprehensions. Haskell Report 1.4 section 3.11 says "a list comprehension returns the list of elements produced by evaluating [the result expression] in the successive environments created by the nested, depth-first evaluation of the generators in the qualifier list." Thus, haskell's list comprehensions fail when presented with an infinite list anywhere but the first generator. Consider this example: -- haskell fails ;; scheme succeeds, slowly [ (a,b,c) | (stream-of (list a b c) a <- [1 ..], (a in (stream-from 1)) b <- [a ..], (b in (stream-from a)) c <- [b ..], (c in (stream-from b)) a*a + b*b == c*c ] (= (+ (* a a) (* b b)) (* c c)))) The haskell definition tests the triples (1,1,1) (1,1,2) (1,1,3) ..., never finding one that succeeds. The scheme definition finds (3 4 5) (6 8 10) (5 12 13) (9 12 15) (8 15 17) ..., working slowly as it tests numerous non-pythagorean triples. These optimized versions work much more quickly, by greatly shrinking the space of search solutions using a little knowledge of geometry: -- haskell ;; scheme [ (a,b,c) | (stream-of (list a b c) a <- [1..], (a in (stream-from 1)) b <- [a..a+a], (b in (stream-from-to a (+ a a))) c <- [b..a+b], (c in (stream-from-to b (+ a b))) a*a + b*b == c*c (= (+ (* a a) (* b b)) (* c c)))) It is interesting to compare the order in which these two expressions compute results. Haskell produces results in strictly increasing order on the a parameter, with ties broken by the b parameter. Scheme streams produce results that are generally increasing on the a parameter, but with some exceptions. Look at the first several results from each: -- haskell ;; scheme (3,4,5) (3 4 5) (6,8,10) (6 8 10) (8,15,17) (8 15 17) (9,12,15) (9 12 15) (12,16,20) (12 16 20) (15,20,25) (15 20 25) (16,30,34) (16 30 34) (18,24,30) (18 24 30) (20,21,29) (20 21 29) (21,28,35) (21 28 35) (24,32,40) (24 32 40) (24,45,51) (24 45 51) (27,36,45) (27 36 45) (28,45,53) (28 45 53) (30,40,50) (30 40 50) (32,60,68) -------------- (33 44 55) (33,44,55) -------------- (32 60 68) (33,56,65) (33 56 65) (36,48,60) (36 48 60) (39,52,65) -------------- (40 42 58) (40,42,58) -------------- (39 52 65) (40,75,85) (40 75 85) (42,56,70) (42 56 70) For haskell programmers and others who might want it, it is relatively straight forward to provide a stream comprehension that generates result expressions in the same nested, depth-first order as haskell, subject to the same restriction that all generators except the first must supply a finite number of elements. The result of finite-stream-of is a lazily-computed stream, and despite its name, is infinite if the first generator is infinite: ;; FINITE-STREAM-OF expr qualifier ... -- comprehensions for finite streams (define-syntax finite-stream-of (syntax-rules () ((finite-stream-of expr qual ...) (finite-stream-of-helper expr '() qual ...)))) (define-syntax finite-stream-of-helper (syntax-rules (in list vector string port is) ((finite-stream-of-helper expr base (var in generator) qual ...) (let loop ((strm generator)) (if (stream-null? strm) base (let ((var (stream-car strm))) (finite-stream-of-helper expr (loop (stream-cdr strm)) qual ...))))) ((finite-stream-of-helper expr base (var in list generator) qual ...) (let loop ((strm (list->stream generator))) (if (stream-null? strm) base (let ((var (stream-car strm))) (finite-stream-of-helper expr (loop (stream-cdr strm)) qual ...))))) ((finite-stream-of-helper expr base (var in vector generator) qual ...) (let loop ((strm (vector->stream generator))) (if (stream-null? strm) base (let ((var (stream-car strm))) (finite-stream-of-helper expr (loop (stream-cdr strm)) qual ...))))) ((finite-stream-of-helper expr base (var in string generator) qual ...) (let loop ((strm (string->stream generator))) (if (stream-null? strm) base (let ((var (stream-car strm))) (finite-stream-of-helper expr (loop (stream-cdr strm)) qual ...))))) ((finite-stream-of-helper expr base (var in port reader generator) qual ...) (let loop ((strm (port->stream reader generator))) (if (stream-null? strm) base (let ((var (stream-car strm))) (finite-stream-of-helper expr (loop (stream-cdr strm)) qual ...))))) ((finite-stream-of-helper expr base (var in port generator) qual ...) (let loop ((strm (port->stream generator))) (if (stream-null? strm) base (let ((var (stream-car strm))) (finite-stream-of-helper expr (loop (stream-cdr strm)) qual ...))))) ((finite-stream-of-helper expr base (var is declaration) qual ...) (let ((var declaration)) (finite-stream-of-helper expr base qual ...))) ((finite-stream-of-helper expr base pred? qual ...) (if pred? (finite-stream-of-helper expr base qual ...) base)) ((finite-stream-of-helper expr base) (cons expr base)))) One final comment on stream comprehensions. It would seem that (stream-of 1 #t) should expand to the null stream, since there are no generators. However, this stream comprehension expands to (let* ((signal (list 'signal)) ((strm (if #t (stream 1) (stream signal)))) (stream-remove (lambda (x) (eq? x signal)) strm)) and thus returns (stream 1). The expression (stream-of 1) behaves the same way. This is proper behavior, even if it seems strange, a consequence of the manner in which the expansion is defined. We next look at some useful operations on finite streams: ;; STREAM-LENGTH stream -- number of elements in stream (define (stream-length strm) (let loop ((strm strm) (length 0)) (if (stream-null? strm) length (loop (stream-cdr strm) (+ 1 length))))) ;; STREAM-SUM stream -- sum of items in stream (define (stream-sum strm) (stream-fold-left + 0 strm)) ;; STREAM-PRODUCT stream -- product of items in stream (define (stream-product strm) (stream-fold-left * 1 strm)) ;; STREAM-MAXIMUM lt? stream -- largest item in stream according to lt? (define (stream-maximum lt? strm) (stream-fold-left-one (lambda (x y) (if (lt? x y) y x)) strm))) ;; STREAM-MINIMUM lt? stream -- smallest item in stream according to lt? (define (stream-minimum lt? strm) (stream-fold-left-one (lambda (x y) (if (lt? x y) x y)) strm))) ;; STREAM-SUM-IF pred? stream -- sum of stream items that satisfy pred? (define (stream-sum-if pred? strm) (stream-sum (stream-filter pred? strm))) ;; STREAM-COUNT-IF pred? stream -- number of stream items that satisfy pred? (define (stream-count-if pred? strm) (stream-length (stream-filter pred? strm))) ;; STREAM-SIGMA func stream -- apply func to each element of stream, then sum (define (stream-sigma func strm) (stream-fold-left + 0 (stream-map func strm))) ;; STREAM-CHAR-TO char1 char2 -- new stream of characters from char1 to char2 (stream-define (stream-char-to char1 char2) (stream-map integer->char (stream-from-to (char->integer char1) (char->integer char2) (if (charstring (reverse nw)))) ((not (char-whitespace? c)) (loop (read-char port) (cons c nw))) ((null? nw) (loop (read-char port) nw)) (else (list->string (reverse nw)))))) ;; BUILD-LINE width words -- build stream of words into lines of max width (stream-define (build-line width words) (let loop ((line "") (words words)) (cond ((stream-null? words) (if (string=? line "") stream-null (stream line))) ((string=? line "") (loop (stream-car words) (stream-cdr words))) ((< (+ (string-length line) (string-length (stream-car words))) width) (loop (string-append line " " (stream-car words)) (stream-cdr words))) (else (stream-cons line (loop (stream-car words) (stream-cdr words))))))) ;; FMT inp outp width -- write inp lines to outp, no line longer than width (define (fmt inp outp width) (stream-display-lines (build-line width (port->stream read-non-white inp)) outp)) Here, the three functions port->stream, build-line, and display-lines are co-routines, each programmed in a monolithic style but operating in an incremental style. Monolithic style means that the function is coded to process the entire stream as if it was all presented at once. Incremental style means that each function operates only long enough to process a single stream element, then passes control to the next function. This style of programming is useful because it is easy to insert new functions between the existing functions. If there is a new requirement to print output with page headers and footers, just replace display-lines with a function display-pages that writes page headers and footers along with text lines. If there is then another new requirement to accumulate multi-column text, just insert a function build-page between build-line and display-page that accumulates lines into columns. The end result is a rich programming style reminiscent of unix pipelines, with pre-programmed pieces that can be inserted or deleted as needed. By the way, this richness extends to the stream library itself, with port->stream and stream-display-lines already provided natively. What makes this style work is that all the functions take a stream as input and return a stream as output, analogously to unix pipelines that provide text files as both input and output. Look at the build-line function shown above for an example. If you were to replace the stream functions with their list counterparts, the function would take a list of words and return a list of lines, accumulating the entire list of lines before returning. But because build-line, and the functions around it, use streams, it only accumulates a single line before passing back to its caller, which eventually returns control so build-line can accumulate the next line, and so on until there are no more words. At the other end, build-line calls port->stream whenever it needs another word, and port->stream just accumulates a single word from the input and waits until it is called again to process the rest of the input. At any given moment, the only memory used by the streams is that required to store the words of the current line, plus the machinery to restart the streams as needed. It is useful to consider the other ways this might have been written. There are essentially three choices. The normal way is to build a single monolithic function that does the entire processing, reading input only as necessary and creating output as soon as it is ready, but such a large function is hard to modify as processing requirements change. The opposite choice is to make numerous small functions that modularize the program in a useful way, making changes relatively easy, but that requires the entire file to reside in memory all at once, since the last function in the chain can't directly call the first. A third approach keeps the modularity of small functions, but adds some control mechanism that allows them to be called as needed without storing the entire input, an approach that is isomorphic to streams. John Hughes, in his article "Why Functional Programming Matters" (The Computer Journal (32:2) 1989 pg 99-107, available electronically from www.math.chalmers.se/~rjmh/papers/whyfp.html), uses a similar example to show how laziness enables modularity. The text formatter passes streams of text from one function to the next. But it is possible to pass streams of any type. For instance, coroutines are an excellent way to organize a multi-pass compiler, with streams of the appropriate internal representation at each point of the process. Our final example is a lazy dictionary, where definitions and uses may occur in any order; in particular, uses may precede their corresponding definitions. This is a common problem. Many programming languages allow functions to be used before they are defined. Macro processors must collect definitions and emit uses of text in order. An assembler needs to know the address that a linker will subsequently give to variables. The usual method is to make two passes over the data, collecting the definitions on the first pass and emitting the uses on the second pass. But streams allow the dictionary to be built lazily, so that only a single pass is needed. This example is based on section 8.4.1 of Chris Reade's book, cited previously. Consider a stream of requests: (define requests (stream '(get 3) '(put 1 "a") ; use follows definition '(put 3 "c") ; use precedes definition '(get 1) '(get 2) '(put 2 "b") ; use precedes definition '(put 4 "d"))) ; unused definition We want a procedure that will return "cab", which is the result of (get 3), (get 1), and (get 2), in order. We need utility functions to separate the request stream into two streams, one of get requests and one of put requests: (define (get? obj) (eq? (car obj) 'get)) (stream-define (gets strm) (stream-map cadr (stream-filter get? strm))) (stream-define (puts strm) (stream-map cdr (stream-remove get? strm))) Now, run-dict inserts each element of the puts stream into a lazy dictionary, represented as an a-stream, then looks up each element of the gets stream: (stream-define (run-dict requests) (let ((dict (build-dict (puts requests)))) (stream-map (lambda (x) (stream-assoc x dict)) (gets requests)))) Dict is created in the let, but nothing is initially added to it. Each time stream-assoc performs a lookup, enough of dict is built to satisfy the lookup, but no more. We are assuming that each item is defined once and only once. All that is left is to define the function that inserts new items into the dictionary, lazily. (stream-define (build-dict puts) (if (stream-null? puts) stream-null (stream-cons (stream-car puts) (build-dict (stream-cdr puts))))) Now, run the dictionary and print the result: > (stream-display (stream-map cadr (run-dict requests))) cab> This is an astonishing result. There are less than a dozen lines of simple, even trivial, code. Three one-liners separate the request stream. The dictionary is built by the common idiom of recursion down cdrs. Processing couldn't be easier: build the dictionary, then look up each item. It all seems so simple, especially when you consider the alternatives without streams. The naive approach makes two passes over the data, collecting definitions on the first pass, saving them in some data structure, and emitting uses on the second pass. The complicated approach somehow caches the request stream as it is read, emitting uses as it finds the matching definitions. Of course, this is exactly what the stream approach does, but behind the scenes, hidden from the programmer, who needn't be concerned with the details. The '(put 4 "d") definition is never added to the dictionary. To see this, augment build-dict so it prints the key each time it is called: (stream-define (build-dict puts) (if (stream-null? puts) stream-null (begin (display (car (stream-car puts))) (stream-cons (stream-car puts) (build-dict (stream-cdr puts)))))) Now processing the request stream shows both definitions and uses: > (stream-display (stream-map cadr (run-dict requests))) 13ca2b> At each moment in the life of dict, only enough of the puts stream has been consumed to satisfy the gets that have already been seen. The 4 key is never added to the lazy dictionary. There are many other places to look for examples of programming with streams. Any textbook on functional programming provides numerous examples; SICP is a favorite, as are books by Richard Bird and Philip Wadler. The haskell standard library provided many examples used in the reference implementation. The field of functional reactive programming, in which streams represent values that react to their inputs, remaining purely functional, presents another example. Sadly, most real-world examples of programming with streams are too big to show or even discuss in the constrained space here. The final word on the utility of programming with streams comes from Abelson and Sussman (SICP section 3.5.3): Streams with delayed evaluation can be a powerful modelling tool, providing many of the benefits of local state and assignment. Moreover, they avoid some of the theoretical tangles that accompany the introduction of assignment into a programming language. The stream approach can be illuminating because it allows us to build systems with different module boundaries than systems organized around assignment to state variables. For example, we can think of an entire time series (or signal) as a focus of interest, rather than the values of the state variables at individual moments. This makes it convenient to combine and compare components of state from different moments. So be it. REFERENCE IMPLEMENTATION ~~~~~~~~~~~~~~~~~~~~~~~~ A reference implementation of streams is shown below. It strongly prefers simplicity and clarity to efficiency. The reference implementation relies on the record types of SRFI-9 and should instead use whatever mechanism the native scheme system uses to create new types. The stream-error function aborts by calling (car '()) and should be rewritten to call the native error handler. The stream-filter function presents a unique difficulty. It can be simply defined as follows: (stream-define (stream-filter pred? strm) (cond ((stream-null? strm) strm) ((pred? (stream-car strm) (stream-cons (stream-car strm) (stream-filter pred? (stream-cdr strm))) (else (stream-filter pred? (stream-cdr strm))))) But this implementation of stream-filter has a problem. Consider this example, due to Joe Marshall: (define (times3 n) (stream-ref (stream-filter (lambda (x) (zero? (modulo x n))) (stream-from 0)) 3)) Called as (times3 5), the function evaluates to 15, as desired. But called as (times3 1000000), it churns the disk, creating closures and caching each result as it counts slowly to 3,000,000; on most scheme systems, this function will run out of memory long before it computes an answer. The problem is a leaking scenario when there is a gap between elements that pass the predicate, which occurs because the naive definition hangs on to the head of the gap. The reference implementation shows one way around this problem. Native implementations of streams should "do the right thing" with regard to space consumption in stream-filter. Of course, if the stream is bound in a scope outside the stream-filter expression, there is nothing to be done except cache the elements as they are filtered. ;;; STREAM -- library of syntax and functions to manipulate streams ;;; A stream is a new data type, disjoint from all other data types, that ;;; contains a promise that, when forced, is either nil (a single object ;;; distinguishable from all other objects) or consists of an object (the ;;; stream element) followed by a stream. Each stream element is evaluated ;;; exactly once, when it is first retrieved (not when it is created); once ;;; evaluated its value is saved to be returned by subsequent retrievals ;;; without being evaluated again. ;; STREAM-ERROR message -- print message then abort execution (define (stream-error message) (display message) (newline) (car '())) ;; STREAM-TYPE -- type of streams ;; MAKE-STREAM obj -- convert object to type of streams ;; STREAM-PROMISE stream -- extract promise from stream ;; STREAM? object -- #t if object is a stream, #f otherwise (define-record-type stream-type (make-stream promise) stream? (promise stream-promise)) ;; STREAM-NULL -- the distinguished null stream (define stream-null (make-stream (delay '()))) ;; STREAM-NULL? object -- #t if object is the nil stream, #f otherwise (define (stream-null? obj) (and (stream? obj) (null? (force (stream-promise obj))))) ;; STREAM-CONS object stream -- the primitive stream constructor (define-syntax stream-cons (syntax-rules () ((stream-cons obj strm) (make-stream (delay (cons obj strm)))))) ;; STREAM-PAIR? object -- #t if object is a non-null stream, #f otherwise (define (stream-pair? obj) (and (stream? obj) (not (null? (force (stream-promise obj)))))) ;; STREAM-CAR stream -- first element of stream (define (stream-car strm) (if (not (stream? strm)) (stream-error "attempt to take car of non-stream")) (if (stream-null? strm) (stream-error "attempt to take car of null stream")) (car (force (stream-promise strm)))) ;; STREAM-CDR stream -- stream containing all elements in stream except first (define (stream-cdr strm) (if (not (stream? strm)) (stream-error "attempt to take cdr of non-stream")) (if (stream-null? strm) (stream-error "attempt to take cdr of null stream")) (cdr (force (stream-promise strm)))) ;; STREAM-DEFINE (name args ...) body ... -- define stream-valued function ;; STREAM-DEFINE (name args ... . rest) body ... -- define stream-valued func (define-syntax stream-define (syntax-rules () ((stream-define name "next" (args ...) (arg . rest) body0 body1 ...) (stream-define name "next" (args ... arg) rest body0 body1 ...)) ((stream-define name "next" (args ...) () body0 body1 ...) (stream-define name "done" (args ...) body0 body1 ...)) ((stream-define name "next" (args ...) rest body0 body1 ...) (stream-define name "rest" (args ...) rest body0 body1 ...)) ((stream-define name "done" (args ...) body0 body1 ...) (define (name args ...) (make-stream (delay (force (stream-promise (begin body0 body1 ...))))))) ((stream-define name "rest" (args ...) rest body0 body1 ...) (define (name args ... . rest) (make-stream (delay (force (stream-promise (begin body0 body1 ...))))))) ((stream-define (name . rest) body0 body1 ...) (stream-define name "next" () rest body0 body1 ...)) ((stream-define (name args ...) body0 body1 ...) (stream-define name "next" () (args ...) body0 body1 ...)))) ;; LIST->STREAM list -- new stream containing elements of list (stream-define (list->stream lst) (if (not (list? lst)) (stream-error "attempt to convert non-list to stream")) (let loop ((lst lst)) (if (null? lst) stream-null (stream-cons (car lst) (loop (cdr lst)))))) ;; VECTOR->STREAM vector -- new stream containing elements of vector (stream-define (vector->stream vec) (if (not (vector? vec)) (stream-error "attempt to convert non-vector to stream")) (list->stream (vector->list vec))) ;; STRING->STREAM string -- new stream containing characters of string (stream-define (string->stream str) (if (not (string? str)) (stream-error "attempt to convert non-string to stream")) (list->stream (string->list str))) ;; STREAM object ... -- new stream whose elements are object ... (define (stream . objs) (list->stream objs)) ;; STREAM-INTERLEAVE stream -- interleave stream of streams "diagonally" (stream-define (stream-interleave-helper s1 s2) (if (stream-null? s1) s2 (stream-cons (stream-car s1) (stream-interleave-helper s2 (stream-cdr s1))))) (stream-define (stream-interleave strm) (cond ((stream-null? strm) stream-null) ((stream-null? (stream-car strm)) (stream-interleave (stream-cdr strm))) (else (stream-cons (stream-caar strm) (stream-interleave-helper (stream-interleave (stream-cdr strm)) (stream-cdar strm)))))) ;; STREAM-OF expr qualifier ... -- stream comprehension syntax for infinite streams (define-syntax stream-of (syntax-rules () ((stream-of expr ...) (let* ((signal (list 'signal)) (strm (stream-of-tail signal expr ...))) (stream-remove (lambda (x) (eq? x signal)) strm))))) (define-syntax stream-of-tail (syntax-rules (in list vector string port is) ((stream-of-tail signal expr (var in generator) clause ...) (let ((f (lambda (var) (stream-of-tail signal expr clause ...)))) (stream-interleave (stream-map f generator)))) ((stream-of-tail signal expr (var in list generator) clause ...) (let ((f (lambda (var) (stream-of-tail signal expr clause ...)))) (stream-interleave (stream-map f (list->stream generator))))) ((stream-of-tail signal expr (var in vector generator) clause ...) (let ((f (lambda (var) (stream-of-tail signal expr clause ...)))) (stream-interleave (stream-map f (vector->stream generator))))) ((stream-of-tail signal expr (var in string generator) clause ...) (let ((f (lambda (var) (stream-of-tail signal expr clause ...)))) (stream-interleave (stream-map f (string->stream generator))))) ((stream-of-tail signal expr (var in port reader generator) clause ...) (let ((f (lambda (var) (stream-of-tail signal expr clause ...)))) (stream-interleave (stream-map f (port->stream reader generator))))) ((stream-of-tail signal expr (var in port generator) clause ...) (let ((f (lambda (var) (stream-of-tail signal expr clause ...)))) (stream-interleave (stream-map f (port->char-stream generator))))) ((stream-of-tail signal expr (var is declaration) clause ...) (let ((var declaration)) (stream-of-tail signal expr clause ...))) ((stream-of-tail signal expr pred? clause ...) (if pred? (stream-of-tail signal expr clause ...) (stream signal))) ((stream-of-tail signal expr) (stream expr)))) ;; STREAM-FROM start [step] -- new stream of numbers from start [step=1] (stream-define (stream-from start . step) (if (not (number? start)) (stream-error "non-numeric start")) (let ((delta (if (pair? step) (car step) 1))) (if (not (number? delta)) (stream-error "non-numeric step")) (stream-cons start (stream-from (+ start delta) delta)))) ;; STREAM-FROM-TO start stop [step] -- new stream from start to stop [step=1] (stream-define (stream-from-to start stop . step) (if (not (number? start)) (stream-error "non-numeric start")) (if (not (number? stop)) (stream-error "non-numeric stop")) ;(let ((delta (if (pair? step) (car step) 1))) (let ((delta (cond ((pair? step) (car step)) ((< start stop) 1) (else -1)))) (if (not (number? delta)) (stream-error "non-numeric step")) (if ((if (negative? delta) < >) start stop) stream-null (stream-cons start (stream-from-to (+ start delta) stop delta))))) ;; STREAM-REPEAT object ... -- infinite stream of object ... (stream-define (stream-repeat . objs) (if (null? objs) stream-null (stream-cons (car objs) (apply stream-repeat (append (cdr objs) (list (car objs))))))) ;; STREAM-ITERATE func obj -- (stream obj (func obj) (func (func obj)) ...) (stream-define (stream-iterate func obj) (if (procedure? func) (stream-cons obj (stream-iterate func (func obj))) (stream-error "non-functional object passed to iterate"))) ;; STREAM-CAR+CDR stream -- (values (stream-car stream) (stream-cdr stream)) (define (stream-car+cdr strm) (if (stream-pair? strm) (values (stream-car strm) (stream-cdr strm)) (stream-error "argument to car+cdr must be non-null"))) ;; STREAM-LAST stream -- last item in stream, error if empty (define (stream-last strm) (cond ((stream-null? strm) (stream-error "can't take last item in null stream")) ((stream-null? (stream-cdr strm)) (stream-car strm)) (else (stream-last (stream-cdr strm))))) ;; STREAM-BUTLAST stream -- stream containing all items in stream except last (stream-define (stream-butlast strm) (cond ((stream-null? strm) (stream-error "attempt to take butlast of null stream")) ((stream-null? (stream-cdr strm)) stream-null) (else (stream-cons (stream-car strm) (stream-butlast (stream-cdr strm)))))) ;; STREAM-CAAR to STREAM-CDDDDR -- compositions of stream-car and stream-cdr (define (stream-caar strm) (stream-car (stream-car strm))) (define (stream-cdar strm) (stream-cdr (stream-car strm))) (define (stream-cadr strm) (stream-car (stream-cdr strm))) (define (stream-cddr strm) (stream-cdr (stream-cdr strm))) (define (stream-caaar strm) (stream-car (stream-caar strm))) (define (stream-cdaar strm) (stream-cdr (stream-caar strm))) (define (stream-cadar strm) (stream-car (stream-cdar strm))) (define (stream-cddar strm) (stream-cdr (stream-cdar strm))) (define (stream-caadr strm) (stream-car (stream-cadr strm))) (define (stream-cdadr strm) (stream-cdr (stream-cadr strm))) (define (stream-caddr strm) (stream-car (stream-cddr strm))) (define (stream-cdddr strm) (stream-cdr (stream-cddr strm))) (define (stream-caaaar strm) (stream-car (stream-caaar strm))) (define (stream-cdaaar strm) (stream-cdr (stream-caaar strm))) (define (stream-cadaar strm) (stream-car (stream-cdaar strm))) (define (stream-cddaar strm) (stream-cdr (stream-cdaar strm))) (define (stream-caadar strm) (stream-car (stream-cadar strm))) (define (stream-cdadar strm) (stream-cdr (stream-cadar strm))) (define (stream-caddar strm) (stream-car (stream-cddar strm))) (define (stream-cdddar strm) (stream-cdr (stream-cddar strm))) (define (stream-caaadr strm) (stream-car (stream-caadr strm))) (define (stream-cdaadr strm) (stream-cdr (stream-caddr strm))) (define (stream-cadadr strm) (stream-car (stream-cdadr strm))) (define (stream-cddadr strm) (stream-cdr (stream-cdadr strm))) (define (stream-caaddr strm) (stream-car (stream-caddr strm))) (define (stream-cdaddr strm) (stream-cdr (stream-caddr strm))) (define (stream-cadddr strm) (stream-car (stream-cdddr strm))) (define (stream-cddddr strm) (stream-cdr (stream-cdddr strm))) ;; STREAM-REF stream n -- nth item in stream, counting from zero (define (stream-ref strm n) (if (not (stream? strm)) (stream-error "attempt to refer to non-stream")) (if (not (integer? n)) (stream-error "attempt to refer to non-integral stream position")) (if (< n 0) (stream-error "stream-ref out of bounds")) (let loop ((strm strm) (n n)) (cond ((stream-null? strm) (stream-error "stream-ref out of bounds")) ((zero? n) (stream-car strm)) (else (loop (stream-cdr strm) (- n 1)))))) ;; STREAM-FIRST to STREAM-TENTH -- synonym for (stream-ref stream (- nth 1)) (define (stream-first stream) (stream-ref stream 0)) (define (stream-second stream) (stream-ref stream 1)) (define (stream-third stream) (stream-ref stream 2)) (define (stream-fourth stream) (stream-ref stream 3)) (define (stream-fifth stream) (stream-ref stream 4)) (define (stream-sixth stream) (stream-ref stream 5)) (define (stream-seventh stream) (stream-ref stream 6)) (define (stream-eighth stream) (stream-ref stream 7)) (define (stream-ninth stream) (stream-ref stream 8)) (define (stream-tenth stream) (stream-ref stream 9)) ;; STREAM-TAKE n stream -- new stream of up to the first n items in stream (stream-define (stream-take n strm) (if (not (integer? n)) (stream-error "attempt to take non-integral number of elements")) (if (< n 0) (stream-error "attempt to take negative number of elements")) (if (not (stream? strm)) (stream-error "attempt to take elements from non-stream")) (if (or (stream-null? strm) (zero? n)) stream-null (stream-cons (stream-car strm) (stream-take (- n 1) (stream-cdr strm))))) ;; STREAM-TAKE-WHILE pred? stream -- stream of stream prefix where pred? is #t (stream-define (stream-take-while pred? strm) (if (not (procedure? pred?)) (stream-error "non-functional predicate")) (if (not (stream? strm)) (stream-error "attempt to take elements from non-stream")) (let take-while ((s strm) (r stream-null)) (if (or (stream-null? s) (not (pred? (stream-car s)))) (stream-reverse r) (take-while (stream-cdr s) (stream-cons (stream-car s) r))))) ;; STREAM-TAKE-UNTIL pred? stream -- stream of stream prefix where pred? is #f (stream-define (stream-take-until pred? strm) (if (not (procedure? pred?)) (stream-error "non-functional predicate")) (if (not (stream? strm)) (stream-error "attempt to take elements from non-stream")) (let take-until ((s strm) (r stream-null)) (if (or (stream-null? s) (pred? (stream-car s))) (stream-reverse r) (take-until (stream-cdr s) (stream-cons (stream-car s) r))))) ;; STREAM-DROP n stream -- nth cdr of stream (stream-define (stream-drop n strm) (if (not (integer? n)) (stream-error "attempt to take non-integral number of elements")) (if (< n 0) (stream-error "attempt to take negative number of elements")) (if (not (stream? strm)) (stream-error "attempt to take elements from non-stream")) (if (or (stream-null? strm) (<= n 0)) strm (stream-drop (- n 1) (stream-cdr strm)))) ;; STREAM-DROP-WHILE pred? stream -- stream less prefix satisfying pred? (stream-define (stream-drop-while pred? strm) (if (not (procedure? pred?)) (stream-error "non-functional predicate")) (if (not (stream? strm)) (stream-error "attempt to take elements from non-stream")) (if (or (stream-null? strm) (not (pred? (stream-car strm)))) strm (stream-drop-while pred? (stream-cdr strm)))) ;; STREAM-DROP-UNTIL pred? stream -- stream less prefix not satisfying pred? (stream-define (stream-drop-until pred? strm) (if (not (procedure? pred?)) (stream-error "non-functional predicate")) (if (not (stream? strm)) (stream-error "attempt to take elements from non-stream")) (if (or (stream-null? strm) (pred? (stream-car strm))) strm (stream-drop-until pred? (stream-cdr strm)))) ;; STREAM-SPLIT n stream -- (values (take ...) (drop ...)) (define (stream-split n strm) (if (not (integer? n)) (stream-error "attempt to take non-integral number of elements")) (if (< n 0) (stream-error "attempt to take negative number of elements")) (if (not (stream? strm)) (stream-error "attempt to take elements from non-stream")) (let split ((s strm) (n n) (r '())) (if (or (stream-null? s) (<= n 0)) (values (list->stream (reverse r)) s) (split (stream-cdr s) (- n 1) (cons (stream-car s) r))))) ;; STREAM-SPLIT-WHILE pred? stream -- values (take-while ...) (drop-while ...) (define (stream-split-while pred? strm) (if (not (procedure? strm)) (stream-error "non-functional predicate")) (if (not (stream? strm)) (stream-error "attempt to take elements from non-stream")) (let split-while ((s strm) (r '())) (if (or (stream-null? s) (not (pred? (stream-car s)))) (values (list->stream (reverse r)) s) (split-while (stream-cdr s) (cons (stream-car s) r))))) ;; STREAM-SPLIT-UNTIL pred? stream -- values (take-until ...) (drop-until ...) (define (stream-split-until pred? strm) (if (not (procedure? strm)) (stream-error "non-functional predicate")) (if (not (stream? strm)) (stream-error "attempt to take elements from non-stream")) (let split-until ((s strm) (r '())) (if (or (stream-null? s) (pred? (stream-car s))) (values (list->stream (reverse r)) s) (split-until (stream-cdr s) (cons (stream-car s) r))))) ;; STREAM-MAP func stream ... -- stream produced by applying func to streams (stream-define (stream-map func . strms) (if (not (all stream? strms)) (stream-error "stream-map applied to non-stream")) (if (or (null? strms) (any stream-null? strms)) stream-null (stream-cons (apply func (map stream-car strms)) (apply stream-map (cons func (map stream-cdr strms)))))) ;; STREAM-FOR-EACH proc stream ... -- apply proc elementwise on stream ... (define (stream-for-each proc . strms) (if (not (all stream? strms)) (stream-error "for-each applied to non-stream")) (let loop ((strms strms)) (if (not (any stream-null? strms)) (begin (apply proc (map stream-car strms)) (loop (map stream-cdr strms)))))) ;; STREAM-FILTER pred? stream -- new stream including only items passing pred? (define (stream-filter pred? strm) (stream-filter-aux pred? strm #f)) (define (stream-filter-aux pred? strm prom) (make-stream (delay (stream-filter-aux-1 pred? (force (stream-promise strm)) prom)))) (define (stream-filter-aux-1 pred? stuff prom) (cond ((null? stuff) '()) ((pred? (car stuff)) (cons (car stuff) (let ((prom (list #f))) (set-car! prom (stream-filter-aux-2 pred? (cdr stuff) prom)) (stream-filter-aux-3 prom)))) (else (let ((more (stream-filter-aux-2 pred? (cdr stuff) prom))) (if prom (set-car! prom more)) (more))))) (define (stream-filter-aux-2 pred? strm prom) (lambda () (stream-filter-aux-1 pred? (force (stream-promise strm)) prom))) (define (stream-filter-aux-3 prom) (make-stream (delay ((car prom))))) ;; STREAM-REMOVE pred? stream -- stream containing only items with pred? #f (stream-define (stream-remove pred? strm) (stream-filter (lambda (x) (not (pred? x))) strm)) ;; STREAM-PARTITION pred? stream -- (values (pred? => #t) (pred? => #f)) (define (stream-partition pred? strm) (if (stream-null? strm) (values stream-null stream-null) (call-with-values (lambda () (stream-partition pred? (stream-cdr strm))) (lambda (pass fail) (let ((obj (stream-car strm))) (if (pred? obj) (values (stream-cons obj pass) fail) (values pass (stream-cons obj fail)))))))) ;; STREAM-FOLD-LEFT func base stream ... -- apply func to base and items ... (define (stream-fold-left func base . strms) (cond ((not (procedure? func)) (stream-error "non-functional argument")) ((not (all stream? strms)) (stream-error "non-stream argument")) ((null? (cdr strms)) (let loop ((base base) (strm (car strms))) (if (stream-null? strm) base (loop (func base (stream-car strm)) (stream-cdr strm))))) (else (let loop ((base base) (strms strms)) (if (any stream-null? strms) base (loop (apply func (cons base (map stream-car strms))) (map stream-cdr strms))))))) ;; STREAM-FOLD-LEFT-ONE func stream ... -- apply func pairwise to stream items (define (stream-fold-left-one func . strms) (cond ((null? strms) (stream-error "no stream supplied to stream-fold-left-one")) ((any stream-null? strms) (stream-error "can't apply stream-fold-left-one to null stream")) ((null? (cdr strms)) (let ((strm (car strms))) (stream-fold-left func (stream-car strm) (stream-cdr strm)))) (else (apply stream-fold-left func (apply func (map stream-car strms)) (map stream-cdr strms))))) ;; STREAM-FOLD-RIGHT func base stream ... -- apply func pairwise to base and items (define (stream-fold-right func base . strms) (cond ((not (procedure? func)) (stream-error "non-functional argument")) ((not (all stream? strms)) (stream-error "non-stream argument")) ((null? (cdr strms)) (let loop ((base base) (strm (car strms))) (if (stream-null? strm) base (loop (func base (stream-last strm)) (stream-butlast strm))))) (else (let loop ((base base) (strms strms)) (if (any stream-null? strms) base (loop (apply func (cons base (map stream-last strms))) (map stream-butlast strms))))))) ;; STREAM-FOLD-RIGHT-ONE func base stream ... -- apply func pairwise to items (define (stream-fold-right-one func . strms) (cond ((null? strms) (stream-error "no stream supplied to stream-fold-right-one")) ((any stream-null? strms) (stream-error "can't apply stream-fold-right-one to null stream")) ((null? (cdr strms)) (let ((strm (car strms))) (stream-fold-right func (stream-last strm) (stream-butlast strm)))) (else (apply stream-fold-right func (apply func (map stream-last strms)) (map stream-butlast strms))))) ;; STREAM-SCAN-LEFT func base stream ... -- stream of partial reductions (stream-define (stream-scan-left func base . strms) (if (not (procedure? func)) (stream-error "non-functional argument")) (if (not (all stream? strms)) (stream-error "non-stream argument")) (stream-cons base (if (any stream-null? strms) stream-null (apply stream-scan-left func (apply func base (map stream-car strms)) (map stream-cdr strms))))) ;; STREAM-SCAN-LEFT-ONE func stream ... -- partial reductions, from first (stream-define (stream-scan-left-one func . strms) (if (any stream-null? strms) (stream-error "can't apply stream-scan-left-one to null stream") (apply stream-scan-left func (if (pair? (cdr strms)) (apply func (map stream-car strms)) (stream-car (car strms))) (map stream-cdr strms)))) ;; STREAM-SCAN-RIGHT func base stream ... -- stream of partial reductions (stream-define (stream-scan-right func base . strms) (if (not (procedure? func)) (stream-error "non-functional argument")) (if (not (all stream? strms)) (stream-error "non-stream argument")) (if (any stream-null? strms) (stream base) (let ((bases (apply stream-scan-right func base (map stream-cdr strms)))) (stream-cons (apply func (stream-car bases) (map stream-car strms)) bases)))) ;; STREAM-SCAN-RIGHT-ONE func stream ... -- partial reductions, from first (stream-define (stream-scan-right-one func . strms) (if (not (procedure? func)) (stream-error "non-functional argument")) (if (not (all stream? strms)) (stream-error "non-stream argument")) (if (any stream-null? strms) (stream-error "can't apply stream-scan-right-one to null stream")) (if (any stream-null? (map stream-cdr strms)) (stream (if (null? (cdr strms)) (stream-car (car strms)) (apply func (map stream-car strms)))) (let ((bases (apply stream-scan-right-one func (map stream-cdr strms)))) (stream-cons (apply func (stream-car bases) (map stream-car strms)) bases)))) ;; PORT->STREAM reader [port] -- stream of objects returned by reader from port (stream-define (port->stream reader . port) (let* ((p (if (null? port) (current-input-port) (car port))) (obj (reader p))) (if (eof-object? obj) stream-null (stream-cons obj (port->stream reader p))))) ;; PORT->CHAR-STREAM [port] -- stream of characters on [current input] port (stream-define (port->char-stream . port) (let ((p (if (null? port) (current-input-port) (car port)))) (port->stream read-char p))) ;; PORT->WORD-STREAM [port] -- stream of words on [current input] port (stream-define (port->word-stream . port) (letrec ((read-word (lambda (port) (let loop ((c (read-char port)) (word '())) (cond ((eof-object? c) (if (null? word) c (list->string (reverse word)))) ((char-alphabetic? c) (loop (read-char port) (cons c word))) ((null? word) (loop (read-char port) word)) (else (list->string (reverse word)))))))) (let ((p (if (null? port) (current-input-port) (car port)))) (port->stream read-word p)))) ;; PORT->LINE-STREAM [port] -- stream of lines on [current input] port (stream-define (port->line-stream . port) (letrec ((read-line (lambda (port) (let loop ((c (read-char port)) (line '())) (cond ((eof-object? c) (if (null? line) c (list->string (reverse line)))) ((char=? #\newline c) (list->string (reverse line))) (else (loop (read-char port) (cons c line)))))))) (let ((p (if (null? port) (current-input-port) (car port)))) (port->stream read-line p)))) ;; STREAM-DISPLAY stream [port] -- display stream on [current output] port (define (stream-display strm . port) (let ((p (if (null? port) (current-output-port) (car port)))) (stream-for-each (lambda (x) (display x p)) strm))) ;; STREAM-DISPLAY-LINES stream [port] -- display stream with newlines (define (stream-display-lines strm . port) (let ((p (if (null? port) (current-output-port) (car port)))) (stream-for-each (lambda (x) (display x p) (newline p)) strm))) ;; STREAM-WRITE stream [port] -- write stream on [current output] port (define (stream-write strm . port) (let ((p (if (null? port) (current-output-port) (car port)))) (stream-for-each (lambda (x) (write x p)) s))) ;; STREAM->LIST stream [n] -- new list containing [first n] elements of stream (define (stream->list strm . n) (if (not (stream? strm)) (stream-error "attempt to convert non-stream to list")) (let ((m (if (pair? n) (car n) -1))) (if (not (integer? m)) (stream-error "non-integral stream->list length") (let loop ((strm strm) (m m)) (if (or (zero? m) (stream-null? strm)) '() (cons (stream-car strm) (loop (stream-cdr strm) (- m 1)))))))) ;; STREAM->VECTOR stream [n] -- vector containing [first n] elements of stream (define (stream->vector strm . n) (if (not (stream? strm)) (stream-error "attempt to convert non-stream to vector")) (if (pair? n) (list->vector (stream->list strm (car n))) (list->vector (stream->list strm)))) ;; STREAM->STRING stream [n] -- string with [first n] characters of stream (define (stream->string strm . n) (if (not (stream? strm)) (stream-error "attempt to convert non-stream to string")) (if (pair? n) (list->string (stream->list strm (car n))) (list->string (stream->list strm)))) ;; STREAM-APPEND stream ... -- append one or more streams end to end (stream-define (stream-append . strms) (if (not (all stream? strms)) (stream-error "attempt to append non-stream")) (let outer-loop ((s stream-null) (strms strms)) (if (null? strms) s (let inner-loop ((s s)) (if (stream-null? s) (outer-loop (car strms) (cdr strms)) (stream-cons (stream-car s) (inner-loop (stream-cdr s)))))))) ;; STREAM-CONCAT stream -- append a stream of streams into a single stream (define (stream-concat strm) (apply stream-append (stream->list strm))) ;; STREAM-REVERSE stream -- new stream with elements of stream in reverse order (stream-define (stream-reverse strm) (if (not (stream? strm)) (stream-error "attempt to reverse non-stream")) (let reverse ((s strm) (r stream-null)) (if (stream-null? s) r (reverse (stream-cdr s) (stream-cons (stream-car s) r))))) ;; STREAM-ZIP stream ... -- convert multiple streams to stream of lists (stream-define (stream-zip . strms) (if (null? strms) (stream-error "stream-zip applied to null arguments") (if (any stream-null? strms) stream-null (stream-cons (apply list (map stream-car strms)) (apply stream-zip (map stream-cdr strms)))))) ;; STREAM-UNZIP stream -- convert stream of lists to multiple streams (define (stream-unzip strm) (if (or (null? strm) (stream-null? (stream-car strm)) (null? (stream-car strm))) (stream-error "stream-unzip applied to null arguments") (apply values (let unzip ((strm strm)) (if (null? (stream-car strm)) '() (cons (stream-map car strm) (unzip (stream-map cdr strm)))))))) ;; STREAM-MERGE lt? stream ... -- stably merge multiple streams by less-than (stream-define (stream-merge lt? . strms) (cond ((null? strms) stream-null) ((null? (cdr strms)) (car strms)) ((any stream-null? strms) (apply stream-merge (cons lt? (let loop ((strms strms) (result '())) (cond ((null? strms) (reverse result)) ((stream-null? (car strms)) (loop (cdr strms) result)) (else (loop (cdr strms) (cons (car strms) result)))))))) (else (let loop ((unexamined (cdr strms)) (min (stream-car (car strms))) (minstrm (car strms)) (beforemin '()) (aftermin '())) (cond ((null? unexamined) ; end of list (stream-cons min (apply stream-merge (cons lt? (append beforemin (list (stream-cdr minstrm)) aftermin))))) ((lt? (stream-car (car unexamined)) min) ; new minimum (loop (cdr unexamined) (stream-car (car unexamined)) (car unexamined) (append beforemin (list minstrm) aftermin) '())) (else ; same minimum (loop (cdr unexamined) min minstrm beforemin (append aftermin (list (car unexamined)))))))))) ;; STREAM-SORT lt? stream -- newly-allocated stream ordered by lt? ; smooth applicative merge sort due to Richard O'Keefe via Larry Paulson (define (stream-merge-pairs lt? list-of-runs k) (if (or (null? (cdr list-of-runs)) (odd? k)) list-of-runs (stream-merge-pairs lt? (cons (stream-merge lt? (car list-of-runs) (cadr list-of-runs)) (cddr list-of-runs)) (/ k 2)))) (define (stream-next-run lt? run strm) (if (or (stream-null? strm) (lt? (stream-car strm) (stream-car run))) (list (stream-reverse run) strm) (stream-next-run lt? (stream-cons (stream-car strm) run) (stream-cdr strm)))) (stream-define (stream-sorting lt? strm list-of-runs k) (if (stream-null? strm) (car (stream-merge-pairs lt? list-of-runs 0)) (let* ((lsts (stream-next-run lt? (stream (stream-car strm)) (stream-cdr strm))) (run (car lsts)) (tail (cadr lsts))) (stream-sorting lt? tail (stream-merge-pairs lt? (cons run list-of-runs) (+ k 1)) (+ k 1))))) (stream-define (stream-sort lt? strm) (if (stream-null? strm) strm (stream-sorting lt? strm '() 0))) ;; STREAM-UNIQ eql? stream -- new stream with adjacent duplicates removed (stream-define (stream-uniq-aux eql? strm omit) (if (stream-null? strm) stream-null (let ((first (stream-car strm))) (if (eql? omit (stream-car strm)) (stream-uniq-aux eql? (stream-cdr strm) omit) (stream-cons first (stream-uniq-aux eql? (stream-cdr strm) first)))))) (stream-define (stream-uniq eql? strm) (if (not (procedure? eql?)) (stream-error "non-functional argument to uniq")) (if (not (stream? strm)) (stream-error "non-stream argument to uniq")) (if (stream-null? strm) stream-null (let ((first (stream-car strm))) (stream-cons first (stream-uniq-aux eql? strm first))))) ;; STREAM-ALTERNATE stream ... -- stream of items from streams in round-robin (stream-define (stream-alternate . strms) (cond ((null? strms) stream-null) ((stream-null? (car strms)) (apply stream-alternate (cdr strms))) (else (stream-cons (stream-car (car strms)) (apply stream-alternate (append (cdr strms) (list (stream-cdr (car strms))))))))) ;; ALL pred? list -- #f if any (pred? list-item) is #f, or last pred? (define (all pred? lst) (cond ((null? lst) #t) ((null? (cdr lst)) (pred? (car lst))) (else (and (pred? (car lst)) (all pred? (cdr lst)))))) ;; ANY pred? list -- first non-#f (pred? list-item), else #f (define (any pred? lst) (cond ((null? lst) #f) ((null? (cdr lst)) (pred? (car lst))) (else (or (pred? (car lst)) (any pred? (cdr lst)))))) ACKNOWLEDGEMENTS ~~~~~~~~~~~~~~~~ Thanks are due to: David Rush for encouraging me to write this library. Michael Sperber for teaching me the difference between even and odd, suggesting stream-define, and patiently answering numerous questions; the entire library was much enriched by our e-mail discussions. Although he won't admit it, this library is as much his as mine. Al Petrofsky for providing early versions of the stream-unzip and stream-of functions included in the reference implementation. Richard Kelsey and Joe Marshall for providing early versions of the stream-filter function. Eli Barzilay for lessons in macrology. All those who responded to my discussions of streams on comp.lang.scheme and by private e-mail: Eli Barzilay, Matthias Blume, Andrew Cady, George Caswell, Dave Feuer, Brian Harvey, Richard Kelsey, Stephen McCracken, Joe Marshall, Al Petrofsky, David Rush, Alex Shinn, Michael Sperber, Panagiotis Vossos, and Noel Welsh. My apologies to anyone I may have missed. My daughters Anne and Kate, for tolerating my obsession during the months of writing and defending this library. It has been a far greater time sink than I ever imagined, though also far more rewarding. COPYRIGHT ~~~~~~~~~ Copyright (C) 2003 by Philip L. Bewig of Saint Louis, Missouri, United States of America. All rights reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing this copyright notice or references to the Scheme Request for Implementation process or editors, except as needed for the purpose of developing SRFIs in which case the procedures for copyrights defined in the SRFI process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the authors or their successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE AUTHORS AND THE SRFI EDITORS DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ON ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.