Tuesday, August 29, 2006

Even may not be odd after all

Yesterday I complained that even streams can lead to unenforced dependencies between computations. In fact, I think there isn't a problem, at least in the usual implementation strategy. As long as you implement a non-empty stream as a promise of a pair, rather than a pair of promises (or a promise of a pair of promises), you can guarantee the right order of evaluation.

Let me actually test my point this time. First we need an effectful stream computation:
(define (make-reader in)
(stream-delay
(let ([first (read in)])
(if (eof-object? first)
stream-null
(stream-cons first (make-reader in))))))
This function creates a stream by reading from an input port, so the order in which its cells are computed is significant. Now here are two different implementations of stream-map:
(define (stream-map1 proc str)
(stream-delay
(if (stream-null? str)
stream-null
(stream-cons (proc (stream-car str))
(stream-map1 proc (stream-cdr str))))))

(define (stream-map2 proc str)
(stream-delay
(if (stream-null? str)
stream-null
(let ([rest (stream-map2 proc (stream-cdr str))])
(stream-cons (proc (stream-car str)) rest)))))
The second implementation forces the tail of the list before the head. When I tried these both in PLT Scheme, they evaluated the same:
> (stream→list
(stream-map1 add1 (make-reader
(open-input-string "0 1 2 3 4"))))
(1 2 3 4 5)
> (stream→list
(stream-map2 add1 (make-reader
(open-input-string "0 1 2 3 4"))))
(1 2 3 4 5)
There you have it: the SRFI 40 implementation of even streams (at least the reference implementation and PLT Scheme implementation) doesn't exhibit a sensitivity to the order of observation of elements of a lazy pair.

Now, to make this falsifiable, I should demonstrate a broken implementation of even streams, to watch the same test fail. Uh... exercise for the reader.

No comments: