How is delay implemented?

Question

I have a firm understanding of how lazy evaluation and streams work.

However I'm having some trouble simply following the book at this point. I don't really undrestand what it is trying to tell me about delay, and here is why.

At page 321 it reads

Cons-stream is a special form defined so that

(cons-stream 〈a〉 〈b〉)

is equivalent to

(cons 〈a〉 (delay 〈b〉))

and a related footnote

[…] If cons-stream were a procedure, then […] evaluating (cons-stream 〈a〉 〈b〉) would automatically cause 〈b〉 to be evaluated, which is precisely what we do not want to happen. For the same reason, delay must be a special form […]

So I conclude that I can't implement cons-stream nor delay, at least not with the tools I have been given at this stage in the book, so I don't understand what the quote above is trying to tell me, beside "it's kinda this, but not quite".

Later, though, there's a "section" of the book titled

Implementing delay and force

Which says something similar to before:

Delay can be a special form such that

(delay 〈exp〉)

is syntactic sugar for

(lambda () 〈exp〉)

But again, how do I define delay if I don't know how to define a special form?

Paradoxically, immediately after one finds that

This implementation suffices for delay and force to work as advertised, but […]

(and the "but" has nothing to do with special forms but just with performance), but how can it work if it's not a special form, defined like this?

And even if I wanted to assume that delay is already defined in whatever Scheme interpreter I'm using (which is the case for this online compiler), I would still be unable to define a special form that makes use of it, such as cons-stream.

Bottom line, I don't know how to write anything for making the exercises.

Eventually, I found this answer showing how to define a special form, but the point is that the define-syntax used therein is not even mentioned in the whole book.

So how was I supposed to do the exercises?

Answer 1

You were supposed to just write the code explicitly according to the syntactical definitions, either as

   (cons A (delay B))

or

   (cons A (lambda () B))

or even

   (cons A (memo (lambda () B)))

instead of

   (cons-stream A B)

everywhere. It's not that bad. I did it once or twice, too. memo can even be defined as a function pretty straightforwardly.

In fact, this is how the text can plausibly be interpreted anyway. It is saying to you, if delay and stream-cons were defined, then writing this would be exactly the same as writing that .... well then, just go head and write that in the first place!

---

The longer way is to define your own interpreter, and have it handle those additional special forms - not "macros" - for you as needed.

You would write your programs as quoted lists, and use them as an input to the interpreter.

You can also fake it by doing whole program transformations, writing new source files out, and loading these transformed source files back with the same interpreter you're already using.

---

An intermediate way is to define your streams as stateful objects with explicit pull requests etc., have the constructor store the lambda function(s) inside, and build the rest on top of that.

Trying to define e.g. Hamming sequence with this kind of streams is actually an interesting exercise, forces you to deal with various issues explicitly that might otherwise remain implicit.

Answer 2

The way you were were supposed to do the exercises was by using the implementation of the language that the authors of the book intended you to use, rather than some other one which has a different set of features. That implementation is, I presume, MIT Scheme.

Sorry to be so blunt, but it is unreasonable to expect that the authors of SICP should have written it in such a way that it is possible to use the book directly for any number of a wide variety of implementations of differing versions of Scheme. People who use such implementations (which is fine) are inevitably going to run into some places where what SICP talks about requires some work to support. This is one.

However, what they do say is that, if you simply manually replace every occurrence of (cons-stream a b) by (cons a (delay b)) and every occurrence of (delay x) by (lambda () x) and then define force: (define (force p) (p)) then things will work, with some caveats.

They are not expecting you to actually have to do this, because they're expecting you to be using an implementation where these things are defined by the implementation. But you could.

---

Of course, pretty soon you discover that if you take a program which makes use of, say, cons-stream then you could (a) notice that the source of that program is expressed as something which is equivalent to a Scheme data structure, and (b) therefore write a program, in Scheme, which would mechanically turn that source into the source of another program which did not use cons-stream, by making the substitutions they suggest. And you can do the same thing for delay. (There is no need to do the same for force however: why?)

Well, the idea of writing such program-transforming programs is something that happened pretty early in the history of Lisp-family languages. Getting such a thing really correct is fairly painful however, and there has been a great deal of history and argument around this.

But in modern Scheme there is an interface to this program-transforming process which lets you define things like cons-stream:

(define-syntax delay
  (syntax-rules ()
    ((_ form)
     (lambda () form))))

(define (force p)
  ;; Assumption: force is only ever called on promises!
  (p))

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

Or you could feel your oats and write

(define-syntax delay
  (syntax-rules ()
    ((_ form)
     (let ((v #f) (forced #f))
       (lambda ()
         (if forced
             v
             (begin
               (set! v form)
               (set! forced #t)
               v)))))))