SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.  Consider an alternative strategy for scanning out definitions that translates the example in the text to

(lambda <vars>
  (let ((u '*unassigned*)
        (v '*unassigned*))
    (let ((a <e1>)
          (b <e2>))
      (set! u a)
      (set! v b))
    <e3>))

Here a and b are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the solve procedure from section 3.5.4:

(define (solve f y0 dt)
  (define y (integral (delay dy) y0 dt))
  (define dy (stream-map f y))
  y)

Will this procedure work if internal definitions are scanned out as shown in this exercise? What if they are scanned out as shown in the text? Explain.

SOLUTION & DISCUSSION

The streams based procedure 'solve' in this exercise exposed several issues in my metacircular evaluator implementation. I discovered that streams are not at all handled properly by my evaluator. Moreover, the 'solve' procedure contains an explicit call to 'delay'. I was not able to rely on the underlying Racket implementation of delay and force (I saw some strange errors). So I had to modify my evaluator to recognize 'delay' as a special form and ensure that its predicate is not evaluated while processing the 'delay' expression. Consequently, I had to implement 'force' also as a special form. This took quite a bit of effort and finally I was able to make expressions like these behave properly:

(define b 69)

(force (delay b))

(delay ((lambda (x) (* x x x)) 11))

((lambda () ((lambda (x) (* x x x)) 11)))

(delay ((lambda (x) (* x x x)) 11))

(force (delay ((lambda (x) (* x x x)) 11)))

(force (delay (force (delay b))))

The metacircular evaluator wraps delayed expressions in lambda expressions for later evaluation by 'force'. (The preceding statement is not true any more. See my August 14th updates below.) The implementation of 'force' i.e. the procedure EVAL-force needed much more thought than I expected since the predicate of force can be a 'delay' expression, a 'delayed-expression', a variable or a lambda expression.

Then I had to deal with "cons-stream" (sicp) or "stream-cons" (Racket). Initially, I tried to use the Racket implementation of this procedure as a primitive procedure inside the evaluator (just like other primitives like cons, car etc.). This did not work since Racket does not even let me add "stream-cons" to my list of primitive procedures. (Racket produces a compilation error when I do this. This must be because "stream-cons" is a special form within Racket too).

This compelled me to implement "cons-stream", "stream-car" and "stream-cdr" also as special forms within my evaluator.

The implementation of "cons-stream" is where I am facing a lot of difficulty. In my implementation, "cons-stream" uses the Racket primitive "cons" in which the first argument is evaluated immediately and the second argument is lambda'ed (i.e. delayed). Later, when the delayed expression is forced, it does not have the right environment and access to variables that it references. So it fails. Still trying to figure out the right way to implement it.

Aug 14th, 2021: I finally implemented stream-management and it works well! cons-stream, stream-car, stream-cdr and add-streams behave properly and consistently. See my code and especially the comments inline to know more. (I have commented out the call to scan-out-defines. I will get to it once I have all the stream management behavior including the solve procedure working properly.) The major change I made here is that instead of using lambda to wrap delayed expressions, I introduced a new special form within my evaluator called 'delayed-expression'. When expressions of the form (delay ...) are encountered, EVAL-delay converts them in 'delayed-expressions' that contain both the expression to evaluate later and also the current environment. I realized that it is necessary to preserve the environment for proper evaluation later. By getting rid of the lambda mechanism, I also avoid creating a new frame when the delayed expression is forced later.

Aug 17th, 2021: A lot happened since my last update. With cons-stream, stream-car, stream-cdr and add-streams working properly, I turned my attention to stream-map, scale-stream and stream-ref. From the start, my intention was to not implement any of these as special forms in my evaluator. Rather, I wanted these to be ordinary compound procedures. When I coded these and fed them to the evaluator, they did not work properly. This particular exercise has conditioned me to not expect anything to work the first time I run it. I debugged each of these failures and found bugs in my implementation of cons-stream, stream-car, stream-cdr and also EVAL-force. I fixed these one by one, found more issues, fixed those and now am thrilled to say that all these procedures work including 'integral', and 'solve'!! 

Procedure 'solve' faithfully produces a stream that computes the numbers leading up to 'e'. But the program runs out of memory if I try to fetch too many elements. I realize that my implementation efficiency can improve but I am not going to tackle that problem right now since the purpose of this exercise is to try different strategies for scanning out defines. Now on to the scanning out part.