LispKit Stream

Streams are a sequential data structure containing elements computed only on demand. They are sometimes also called lazy lists.

Streams get constructed with list-like constructors. A stream is either null or is a pair with a stream in its cdr. Since elements of a stream are computed only when accessed, streams can be infinite. Once computed, the value of a stream element is cached in case it is needed again.

Benefits of using streams

When used effectively, the primary benefit of streams is improved modularity. Consider a process that takes a sequence of items, operating on each in turn. If the operation is complex, it may be useful to split it into two or more procedures in which the partially-processed sequence is an intermediate result. If that sequence is stored as a list, the entire intermediate result must reside in memory all at once; however, if the intermediate result is stored as a stream, it can be generated piecemeal, using only as much memory as required by a single item. This leads to a programming style that uses many small operators, each operating on the sequence of items as a whole, similar to a pipeline of unix commands.

In addition to improved modularity, streams permit a clear exposition of backtracking algorithms using the “stream of successes” technique, and they can be used to model generators and co-routines. The implicit memoization of streams makes them useful for building persistent data structures, and the laziness of streams permits some multi-pass algorithms to be executed in a single pass. Savvy programmers use streams to enhance their programs in countless ways.

There is an obvious space/time trade-off between lists and streams; lists take more space, but streams take more time (to see why, look at all the type conversions in the implementation of the stream primitives). Streams are appropriate when the sequence is truly infinite, when the space savings are needed, or when they offer a clearer exposition of the algorithms that operate on the sequence.

Stream abstractions

The (lispkit stream) library provides two mutually-recursive abstract data types: An object of type stream is a promise that, when forced, is either stream-null or is an object of type stream-pair. An object of the stream-pair type contains a stream-car and a stream-cdr, which must be a stream. The essential feature of streams is the systematic suspensions of the recursive promises between the two data types.

The object stored in the stream-car of a stream-pair is a promise that is forced the first time the stream-car is accessed; its value is cached in case it is needed again. The object may have any type, and different stream elements may have different types. If the stream-car is never accessed, the object stored there is never evaluated. Likewise, the stream-cdr is a promise to return a stream, and is only forced on demand.

Stream API

The design of the API of library (lispkit stream) is based on Philip Bewig's SRFI 41. The implementation of the library is LispKit-specific.

stream-null [object]

stream-null is a stream that, when forced, is a single object, distinguishable from all other objects, that represents the null stream. stream-null is immutable and unique.

(stream? obj) [procedure]

Returns #t if obj is a stream; otherwise #f is returned.

(stream-null? obj) [procedure]

stream-null? is a procedure that takes an object obj and returns #t if the object is the distinguished null stream and #f otherwise. If object obj is a stream, stream-null? must force its promise in order to distinguish stream-null from stream-pair.

(stream-pair? obj) [procedure]

stream-pair? is a procedure that takes an object and returns #t if the object is a stream-pair constructed by stream-cons and #f otherwise. If object is a stream, stream-pair? must force its promise in order to distinguish stream-null from stream-pair.

(stream-cons obj strm) [syntax]

stream-cons is a special form that accepts an object obj and a stream strm and creates a newly-allocated stream containing a stream that, when forced, is a stream-pair with the object in its stream-car and the stream in its stream-cdr. stream-cons must be syntactic, not procedural, because neither object obj nor stream is evaluated when stream-cons is called. Since strm is not evaluated, when the stream-pair is created, it is not an error to call stream-cons with a stream that is not of type stream; however, doing so will cause an error later when the stream-cdr of the stream-pair is accessed. Once created, a stream-pair is immutable.

(define s (stream-cons 1 (stream-cons 2 (stream-cons 3 stream-null))))
(stream-car s)               ⇒  1
(stream-car (stream-cdr s))  ⇒  2

(stream-car strm) [procedure]

stream-car is a procedure that takes a stream strm and returns the object stored in the stream-car of the stream. stream-car signals an error if the object passed to it is not a stream-pair. Calling stream-car causes the object stored there to be evaluated if it has not yet been; the object’s value is cached in case it is needed again.

(stream-cdr strm) [procedure]

stream-cdr is a procedure that takes a stream strm and returns the stream stored in the stream-cdr of the stream. stream-cdr signals an error if the object passed to it is not a stream-pair. Calling stream-cdr does not force the promise containing the stream stored in the stream-cdr of the stream.

(stream obj ...) [syntax]

stream is syntax that takes zero or more objects obj and creates a newly-allocated stream containing in its elements the objects, in order. Since stream is syntactic, the objects are evaluated when they are accessed, not when the stream is created. If no objects are given, as in (stream), the null stream is returned.

(stream-lambda formals expr0 expr1 ...) [syntax]

stream-lambda creates a procedure that returns a stream to evaluate the body of the procedure. The last body expression to be evaluated must yield a stream. As with the regular lambda, formals may be a single variable name, in which case all the formal arguments are collected into a single list, or it is a list of variable names, which may be null if there are no arguments, proper if there are an exact number of arguments, or dotted, if a fixed number of arguments is to be followed by zero or more arguments collected into a list. The body expr0 expr1 ... must contain at least one expression, and may contain internal definitions preceding any expressions to be evaluated.

(define iter (stream-lambda (f x) (stream-cons x (iter f (f x)))))
(define nats (iter (lambda (x) (+ x 1)) 0))
(stream-car (stream-cdr nats))               ⇒  1

(define stream-add
  (stream-lambda (s1 s2)
    (stream-cons (+ (stream-car s1) (stream-car s2))
                 (stream-add (stream-cdr s1) (stream-cdr s2)))))
(define evens (stream-add nats nats))

(stream-car evens)                           ⇒  0
(stream-car (stream-cdr evens))              ⇒  2
(stream-car (stream-cdr (stream-cdr evens))) ⇒  4

(define-stream (name arg ...) expr0 expr1 ...) [syntax]

define-stream creates a procedure name that returns a stream, and may appear anywhere a normal define may appear, including as an internal definition, and may have internal definitions of its own, including other define-streams. The defined procedure takes arguments arg ... in the same way as stream-lambda. define-stream is syntactic sugar on stream-lambda.

(stream-let tag ((var val) ...) expr1 expr2 ...) [syntax]

stream-let creates a local scope that binds each variable var to the value of its corresponding expression val. It additionally binds tag to a procedure which takes the bound variables as arguments and body as its defining expressions, binding the tag with stream-lambda. tag is in scope within body, and may be called recursively. When the expanded expression defined by the stream-let is evaluated, stream-let evaluates the expressions expr1 expr2 ... in its body in an environment containing the newly-bound variables, returning the value of the last expression evaluated, which must yield a stream.

stream-let provides syntactic sugar on stream-lambda, in the same manner as normal let provides syntactic sugar on normal lambda. However, unlike normal let, the tag is required, not optional, because unnamed stream-let is meaningless.

(display-stream strm) [procedure]
(display-stream strm n)
(display-stream strm n sep)
(display-stream strm n sep port)

display-stream displays the first n elements of stream strm on port port using string sep as a separator string. If n is not provided, all elements are getting displayed. If sep is not provided, ", " is used as a default. If port is not provided, the current output port is used.

(list->stream lst) [procedure]

list->stream takes a list of objects lst and returns a newly-allocated stream containing in its elements the objects in the list. Since the objects are given in a list, they are evaluated when list->stream is called, before the stream is created. If the list of objects is null, as in (list->stream '()), the null stream is returned.

(port->stream) [procedure]
(port->stream port)

port->stream takes a port port and returns a newly-allocated stream containing in its elements the characters on the port. If the port is not given, it defaults to the current input port. The returned stream has finite length and is terminated by stream-null.

(stream->list strm) [procedure]
(stream->list strm n)

stream->list takes a natural number n and a stream strm and returns a newly-allocated list containing in its elements the first n items in the stream. If the stream has less than n items, all the items in the stream will be included in the returned list. If n is not given, it defaults to infinity, which means that unless the stream is finite, stream->list will never return.

(stream-append strm ...) [procedure]

stream-append returns a newly-allocated stream containing in its elements those elements contained in its argument streams strm ..., in order of input. If any of the input streams is infinite, no elements of any of the succeeding input streams will appear in the output stream; thus, if x is infinite, (stream-append x y) ≡ x.

(stream-concat strms) [procedure]

stream-concat takes a stream strms consisting of one or more streams and returns a newly-allocated stream containing all the elements of the input streams. If any of the streams in the input stream is infinite, any remaining streams in the input stream will never appear in the output stream.

(stream-constant obj ...) [procedure]

stream-constant takes one or more objects obj ... and returns a newly-allocated stream containing in its elements the objects, repeating the objects in succession forever.

(stream-drop strm n) [procedure]

stream-drop returns the suffix of the input stream strm that starts at the next element after the first n elements. The output stream shares structure with the input stream; thus, promises forced in one instance of the stream are also forced in the other instance of the stream. If the input stream has less than n elements, stream-drop returns the null stream.

(stream-drop-while pred? strm) [procedure]

stream-drop-while returns the suffix of the input stream that starts at the first element x for which (pred? x) is #f. The output stream shares structure with the input stream.

(stream-filter pred? strm) [procedure]

stream-filter returns a newly-allocated stream that contains only those elements x of the input stream for which (pred? x) is non-#f.

(stream-fold proc base strm) [procedure]

stream-fold applies a binary procedure proc to base and the first element of stream strm to compute a new base, then applies the procedure proc to the new base (1st argument of proc) and the next element of stream (2nd argument of proc) to compute a succeeding base, and so on, accumulating a value that is finally returned as the value of stream-fold when the end of the stream is reached. strm must be finite, or stream-fold will enter an infinite loop.

See also stream-scan, which is similar to stream-fold, but useful for infinite streams. stream-fold is a left-fold; there is no corresponding right-fold, since right-fold relies on finite streams that are fully-evaluated, at which time they may as well be converted to a list.

(stream-for-each proc strm ...) [procedure]

stream-for-each applies a procedure proc elementwise to corresponding elements of the input streams strm ... for its side-effects. stream-for-each stops as soon as any of its input streams is exhausted.

(stream-from first) [procedure]
(stream-from first delta)

stream-from creates a newly-allocated stream that contains first as its first element and increments each succeeding element by delta. If delta is not given it defaults to 1. first and delta may be of any numeric type. stream-from is frequently useful as a generator in stream-of expressions. See also stream-range for a similar procedure that creates finite streams.

(stream-iterate proc base) [procedure]

stream-iterate creates a newly-allocated stream containing base in its first element and applies proc to each element in turn to determine the succeeding element.

(stream-length strm) [procedure]

stream-length takes an input stream strm and returns the number of elements in the stream. It does not evaluate its elements. stream-length may only be used on finite streams as it enters an infinite loop with infinite streams.

(stream-map proc strm ...) [procedure]

stream-map applies a procedure proc elementwise to corresponding elements of the input streams strm ..., returning a newly-allocated stream containing elements that are the results of those procedure applications. The output stream has as many elements as the minimum-length input stream, and may be infinite.

(stream-match strm-expr (pattern [fender] expr) ...) [syntax]

stream-match provides the syntax of pattern-matching for streams. The input stream strm-expr is an expression that evaluates to a stream and is matched against a number of clauses. Each clause (pattern [fender] expr) consists of a pattern that matches a stream of a particular shape, an optional fender that must succeed if the pattern is to match, and an expression that is evaluated if the pattern matches.

There are four types of patterns:

• (): Matches the null stream
• (pat0 pat1 ...): Matches a finite stream with length exactly equal to the number of pattern elements
• (pat0 pat1 ... . patrest): Matches an infinite stream, or a finite stream with length at least as great as the number of pattern elements before the literal dot
• pat: Matches an entire stream. Should always appear last in the list of clauses; it’s not an error to appear elsewhere, but subsequent clauses could never match

Each pattern element pati may be either:

• An identifier: Matches any stream element. Additionally, the value of the stream element is bound to the variable named by the identifier, which is in scope in the fender and expression of the corresponding clause. Each identifier in a single pattern must be unique.
• A literal underscore: Matches any stream element, but creates no bindings.

The patterns are tested in order, left-to-right, until a matching pattern is found. If fender is present, it must evaluate as non-#f for the match to be successful. Pattern variables are bound in the corresponding fender and expression. Once the matching pattern is found, the corresponding expression is evaluated and returned as the result of the match. An error is signaled if no pattern matches the input stream.

(stream-of expr rest ...) [syntax]

stream-of provides the syntax of stream comprehensions, which generate streams by means of looping expressions. The result is a stream of objects of the type returned by expr. There are four types of clauses:

• (var in stream-expr): Loop over the elements of stream-expr, in order from the start of the stream, binding each element of the stream in turn to var. stream-from and stream-range are frequently useful as generators.
• (var is expr): Bind var to the value obtained by evaluating expr.
• (pred? expr): Include in the output stream only those elements x for which (pred? x) is non-#f.

The scope of variables bound in the stream comprehension is the clauses to the right of the binding clause (but not the binding clause itself) plus the result expression. When two or more generators are present, the loops are processed as if they are nested from left to right; i.e. the rightmost generator varies fastest. A consequence of this is that only the first generator may be infinite and all subsequent generators must be finite. If no generators are present, the result of a stream comprehension is a stream containing the result expression; thus, (stream-of 1) produces a finite stream containing only the element 1.

(stream-range first past) [procedure]
(stream-range first past delta)

stream-range creates a newly-allocated stream that contains first as its first element and increments each succeeding element by step. The stream is finite and ends before past, which is not an element of the stream. If step is not given it defaults to 1 if first is less than past and -1 otherwise. First, past and step may be of any numeric type. stream-range is frequently useful as a generator in stream-of expressions.

(stream-ref strm n) [procedure]

stream-ref returns the n-th element of stream, counting from zero. An error is signaled if n is greater than or equal to the length of stream.

(stream-reverse strm) [procedure]

stream-reverse returns a newly-allocated stream containing the elements of the input stream strm but in reverse order. stream-reverse may only be used with finite streams; it enters an infinite loop with infinite streams. stream-reverse does not force evaluation of the elements of the stream.

(stream-scan proc base strm) [procedure]

stream-scan accumulates the partial folds of an input stream strm into a newly-allocated output stream. The output stream is the base followed by (stream-fold proc base (stream-take i stream)) for each of the first i elements of stream.

(stream-take strm n) [procedure]

stream-take takes a non-negative integer n and a stream and returns a newly-allocated stream containing the first n elements of the input stream. If the input stream has less than n elements, so does the output stream.

(stream-take-while pred? strm) [procedure]

stream-take-while takes a predicate pred? and a stream strm and returns a newly-allocated stream containing those elements x that form the maximal prefix of the input stream for which (pred? x) is non-#f.

(stream-unfold mapper pred? generator base) [procedure]

stream-unfold is the fundamental recursive stream constructor. It constructs a stream by repeatedly applying generator to successive values of base, in the manner of stream-iterate, then applying mapper to each of the values so generated, appending each of the mapped values to the output stream as long as (pred? base) is non-#f.

(stream-unfolds proc seed) [procedure]

stream-unfolds returns n newly-allocated streams containing those elements produced by successive calls to the generator proc, which takes the current seed as its argument and returns n+1 values:

    (proc seed)   →   seed result0 ... resultn-1

where the returned seed is the input seed to the next call to the generator and resulti indicates how to produce the next element of the i-th result stream:

• (value): value is the next car of the result stream
• #f: no value produced by this iteration of the generator proc for the result stream
• (): the end of the result stream

It may require multiple calls of proc to produce the next element of any particular result stream.

(stream-zip strm ...) [procedure]

stream-zip takes one or more input streams strm ... and returns a newly-allocated stream in which each element is a list (not a stream) of the corresponding elements of the input streams. The output stream is as long as the shortest input stream, if any of the input streams is finite, or is infinite if all the input streams are infinite.