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.