Scheme: problem about display when using `delay` expression

Question

This is a problem related to ex3.51 in SICP, here is the code

(define (cons-stream x y)
  (cons x (delay y)))
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
(define (stream-map proc s)
  (if (stream-null? s)
      the-empty-stream
      (cons-stream
       (proc (stream-car s))
       (stream-map proc (stream-cdr s)))))
(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))
(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))
(define (show x)
  (display x)
  x)
;test
(stream-map show (stream-enumerate-interval 0 10))

the output is 012345678910(0 . #<promise>).

but I thought the delay expression in cons-stream delayed the evaluation, if i use a different processing function in stream-map like lambda (x) (+ x 1) the output (1 . #<promise>) is more reasonable, so why does display print all the numbers?

Will Ness · Accepted Answer · 2020-03-01T18:34:33.960

The problem is with this definition:

(define (cons-stream x y)
  (cons x (delay y)))

It defines cons-stream as a function, since it uses define.

Scheme's evaluation is eager: the arguments are evaluated before the function body is entered. Thus y is already fully calculated when it is passed to delay.

Instead, cons-stream should be defined as a macro, like

(define-syntax cons-stream
  (syntax-rules ()
    ((_ a b) (cons a (delay b)))))

or we can call delay explicitly, manually, like e.g.

(define (stream-map proc s)
  (if (stream-null? s)
      the-empty-stream
      (cons
       (proc (stream-car s))
       (delay
          (stream-map proc (stream-cdr s))))))

Then there'd be no calls to cons-stream in our code, only the (cons A (delay B)) calls. And delay is a macro (or special form, whatever), it does not evaluate its arguments before working but rather goes straight to manipulating the argument expressions instead.

And we could even drop the calls to delay, and replace (cons A (delay B)) with (cons A (lambda () B)). This would entail also reimplementing force (which is built-in, and goes together with the built-in delay) as simply (define (force x) (x)) or just calling the (x) manually where appropriate to force a stream's tail.

You can see such lambda-based streams code towards the end of this answer, or an ideone entry (for this RosettaCode entry) without any macros using the explicit lambdas instead. This approach can change the performance of the code though, as delay is memoizing but lambda-based streams are not. The difference will be seen if we ever try to access a stream's element more than once.

See also this answer for yet another take on streams implementation, surgically modifying list's last cons cell as a memoizing force.

Just to put this in the context of the book, 'eager' evaluation is what the book calls applicative order. The problem you encountered with the original definition is covered in footnote 56 to section 3.5.1 - at this point we don't have the tools to implement our own cons-stream, but this will be covered in section 4.1 where we learn a lot more about special forms and 4.2 where we implement the necessary normal order (lazy) evaluation. — codybartfast, Mar 01 '20 at 08:27
thank you,but (cons..delay) is the essentially the same as (cons-stream...),right? if y is already calculated when it is passed to delay,why the output is (1 . #) instead of 1234567891011 if pass lambda (x) (+ x 1) to stream-map? — codesavesworld, Mar 01 '20 at 09:27
No, if we write it out manually that way, there is no `y`. there is no *function call*, only the nested expressions, and the expression inside `delay` does get delayed. so if we do it that way, there won't be any calls to `cons-stream` in our code, just calls to `cons` and `delay` like `(cons A (delay B))`. and `delay` *is* a macro (or a special form, whatever), it does *not* evaluate its arguments before working but rather goes straight to manipulating the argument expressions instead. — Will Ness, Mar 01 '20 at 10:15

Scheme: problem about display when using `delay` expression

1 Answers1