Prev Index

Model data as streams

Work in progress.

It may surprise some readers that I wish to talk about streams next. I feel now is the best chapter to do so, because it naturally answers a simple question.

With (cons 1 (cons 2 (cons 3 ... it feels as if you can construct something that never ends, and indeed that is true. In Scheme, a never ending sequence is called a stream. If you come from a C background, do not confuse a C stream, a FILE pointer, with a Scheme stream.

stream-cons

I am going to take it slow and in four steps show how to make streams. The steps are:

  1. cons with a procedure call;
  2. cons with a recursive procedure;
  3. cons with a procedure that calls a recursive procedure;
  4. a procedure with a cons that calls a recursive procedure.

Here is what you know so far. Recall that a cons evaluates into a pair. Recall the form of the cons expression: (cons <exp-1> <exp-2>). This is a compound expression, which evaluates in applicative order, meaning that both <exp-1> and <exp-2> are evaluated.

  1. cons with a procedure call

The first step is easy. You can make a pair that has procedures. To see this, recall that a lambda expression evaluates into a procedure. Thus:

> (cons 1 (lambda (x) x))
$1 = (1. #<procedure 55e75ecd06c0 at <unknown port>:2:8 (x)>)

results in a valid pair. Ignore the 55e75.... This is just Guile saying that the second element of this pair is a procedure that accepts one argument. Now you can call this procedure:

> (cons 1 ((lambda (x) x) 1))
$2 = (1 . 1)
  1. cons with a recursive procedure

You are not limited to using cons as the root expression. Sometimes cons is needed within a define. Here is an example of a procedure named p which contains itself.

> (define (p x) (cons x p))
> (p 1)
$3 = (1 . #<procedure p (x)>)

For the second step, note that p can be recursive:

> (define (p x) (cons x (p (+ x 1))))
> (p 1)

What happened? Well, the program never returned. I had to ctrl-C to force Guile to stop evaluating this expression. It is interesting that the program did not crash. However, the Guile memory usage went over 4 GB, severly slowing down my system. This example illustrates that Scheme handles a lot of memory well. You can have very long, but finite, pairs. Streams on the other hand we do not know how far we wish to go.

So, you likely want the program to return. Here is the magic trick.

  1. cons with a procedure that calls a recursive procedure

The solution is to use a lambda expression.

> (define (p x)
    (cons x (lambda (x) (p (+ x 1)))))

> (p 1)
$4 = (1 . #<procedure 557abc5e4ca8 at <unknown port>:4:22 (x)>)
  1. a procedure with acons calls a recursive procedure.

The alternative solution is to move the lambda expression before the cons.

> (define (stream-cons x)
    (lambda () (cons x (stream-cons (+ x 1)))))

> (stream-cons 1)
$6 = #<procedure 7f886d46d140 at <unknown port>:6:24 ()>
> ((stream-cons 1))
$7 = (1 . #<procedure 7f886ed1e0c0 at <unknown port>:6:24 ()>)

even odd streams

Delayed evaluation

Consider wrapping an expression within a procedure with no arguments: (lambda () (expression...)). Suppose, we desired that the expresion in the body of the procedure is evaluated when the procedure is called. This is called delayed evaluation, which is also known as delayed evaluation or call-by-need. The evaluation of an expression is delayed until its value is needed.

We have shown how we implemented streams – potentially infinite data structures – using delayed evaluation.

In Scheme, delayed evaluation includes one more idea: memoization. Once an expression is evaluated, its value is stored, such that repeated requests for the same value are returned without re-evaluating the expression. This idea is based on the hope that the expression, to be evaluated, results in the same output, when the input is unchanged.

The delay syntax returns a promise object which holds an expression to be evaluated by a call to the force procedure.

In Scheme, delay is implemented as a macro. A complex definition of delay is provided in the RNRS standards, as it has to deal with memoization.

> force
$1 = #<procedure force (_)>

The Scheme procedure force

> promise?
$2 = #<procedure promise? (_)>

> (define p (delay (begin (display "print once ") (+ 1 2))))
> (force p)
print once $3 = 3
> (force p)
$4 - 3

Guile streams and examples

(use-modules (srfi srfi-41))

Fibonnaci

(define (fib-stream a b)
  (stream-cons a (fib-stream b (+ a b))))

> (stream->list 10 (fib-stream 1 1))
$1 = (1 1 2 3 5 8 13 21 34 55)

I was blown away by the stream version of and. Unlike the and, which required macros, the stream-and is a procedure. It operates on streams.

(define (stream-and strm)
  (let loop ((strm strm))
    (cond ((stream-null? strm) #t)
          ((not (stream-car strm)) #f)
          (else (loop (stream-cdr strm))))))

> (stream-and (stream 1 2 3))
$2 = #t
scheme@(guile-user)> (stream-and (stream 1 2 3 #f 5))
$3 = #f


> (stream->list (stream-zip (stream 1 2 3) (stream 4 5 6)))
$1 = ((1 4) (2 5) (3 6))

> (stream->list
    (stream-of (* x x)
               (x in (stream-range 0 10))
               (even? x)))
$2 = (0 4 16 36 64)

Convert a string into a stream

(define (string->stream str)
  (define (f len i)
    (if (eqv? i len)
        empty-stream
        (stream-cons (string-ref str i) (f len (+ i 1)))))
  (f (string-length str) 0))

Prev Index