Delayed "let" in SICP

Question

SICP indicates cdr is opened up:

In section 3.5.4 , i saw this block:

(define (integral delayed-integrand initial-value dt)
 (define int
  (cons-stream initial-value
             (let ((integrand (force delayed-integrand)))
               (add-streams (scale-stream integrand dt)
                            int))))
int)

Normally if this was something like:

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

The stream-cdr s would be evaluated as (cons-stream (stream-car (cdr s)) delay<>) even when the actual call would be in a delay. ie even though the stream-map function itself is delayed, the arguments are pre-computed. [Is this correct? - By the applicative model, the arguments should be substituted for ,before the function is "called", but is the call evaluation when delay is forced or when it's just specified]

Then why is let not pre-computed?

What i think? I think let is a lambda function with the variable as the arguments, so it's execution is delayed

(let ((var1 e1) (var2 e2)) e3)

is same as

 Lambda (var1 var2) e3 (with var1 bound to e1 and var2 bound to e2)

Can someone please help me confirm this? Thanks

score 1 · Answer 1 · answered May 31 '21 at 23:11

1

In SICP type streams the car of a stream is not delayed, but the cdr is. The whole expression,

(let ((integrand (force delayed-integrand)))
  (add-streams (scale-stream integrand dt)
               int))

, is delayed since it is the second argument to cons-stream. What kind of expression is delayed doesn't matter so you can have a call, evaluation of variable or even a let there.

answered May 31 '21 at 23:11

Sylwester

47,942
4
47
79

If this expression was a function call where an argument like stream-cdr is there, i saw that the argument is computed , just the call is delayed. This is like a lambda function, is it the reason the let is not computed? eg. in (cons-stream a (func (stream-cdr b))) , func is delayed but stream-cdr is pre-computed – user10206517 Jun 01 '21 at 04:34
@user10206517 `stream-cdr` will force the code of the next element, but only when the expression itself gets run. If it is code in the second argument to `cons-stream` it will be delayed. It doesn't matter what is there so `stream-cdr` is not pre-computed unless the stream is forced with `stream-cdr` and then `func` would be called as well. The head of the streams are not delayed so the SICP streams actually compute one step further than needed. This is fixed in the SRFI version. – Sylwester Jun 02 '21 at 01:46
I have an example form the book, in which this is done. Page 322 where it computes (stream-filter prime?) Here they have a delay in the expression but the cdr is materialized. I added the image to the question – user10206517 Jun 02 '21 at 22:07
@user10206517 Even if the book does that it doesn't happen like that. The whole code with environment is captured in a lambda. However it is difficult to show how the expansion is without the environment so I guess they replaced closure variables in their explanation. – Sylwester Jun 03 '21 at 14:23
Not only that an exercise in the book with `set` side effects also is executed . you can check it out Ex.3.51 the part where they ask to print value of sum after (define y (stream-filter even? seq)) . If what you say is correct, the value should be 3 but it is 6. Is the exercise wrong? – user10206517 Jun 03 '21 at 23:20
@user10206517 As I said in 3.51 the `car` is not delayed so show will print the first value. Then it will not print anything until `(stream-ref x 5)` where it will print the next generated values. Since its memoized `(stream-ref x 7)` will only print the 2 last. – Sylwester Jun 04 '21 at 00:12
Sorry i meant 3.52 where `set` side effect is there and the part where (define y (stream-filter even? seq)) is done. Before this the (define seq...) gets (1 delay (..)). Then when we do stream filter. we move to 2 directly (not using cons-stream). Then there (stream-cdr) is calculated which makes to add 3 as well. (even though it was in a cons-stream in the cdr part). The delayed cdr is responsible for the side effect here. Please clarify this so i can accept your answer and sorry if i didn't argue correctly – user10206517 Jun 04 '21 at 00:34
@user10206517 could you please make a new post with your new question with all the specifics and all that it references so we can answer it properly? – Will Ness Jun 04 '21 at 11:18
1

@WillNess done - https://stackoverflow.com/questions/67845454/sicp-3-52-delayed-cdr – user10206517 Jun 05 '21 at 01:09

Will Ness · Accepted Answer · 2021-06-04T11:54:53.933

"the arguments are pre-computed. is this correct?"

No. (cons-stream a (func (stream-cdr b))) is just like

(cons-stream a    
    (lambda ()     
       ;; our code is placed here, verbatim, as a whole:
       (func (stream-cdr b))  
    )  
  )

const-stream is a macro, it just moves pieces of code around.

The lambda might be enclosed in a memo-proc call for the memoization, to do call-by-need, but it'll still have the code we wrote, like (func (stream-cdr b)), placed inside the lambda, "textually", by cons-stream. Which is a macro, just moving pieces of code around.

Regarding the snippet which you've added to the question, the authors were just being imprecise. What is meant there is, when (stream-cdr stream) in (stream-filter pred (stream-cdr stream)) will be called, it will produce (cons 10008 (delay .... )), as shown. Not before.

Where it says "which in this case is" is should have said "which in this case is the same as".

In section 3.5.1 Streams Are Delayed Lists the book says:

To make the stream implementation automatically and transparently interleave the construction of a stream with its use, we will arrange for the cdr of a stream to be evaluated when it is accessed by the stream-cdr procedure rather than when the stream is constructed by cons-stream.

I have an example form the book, in which this is done. Page 322 where it computes (stream-filter prime?) — user10206517, Jun 02 '21 at 21:54
@user10206517 I have edited in response. if you want specific line-by-line proof, do post a new question with [mcve] with emphasis on *complete* (i.e. include all code). also make it focused please, this question now is all over the place. — Will Ness, Jun 04 '21 at 18:16

Delayed "let" in SICP

2 Answers2