Problem with circular definition in Scheme

Question

I am currently working through SICP using Guile as my primary language for the exercises. I have found a strange behavior while implementing the exercises in chapter 3.5. I have reproduced this behavior using Guile 1.4, Guile 1.8.6 and Guile 1.8.7 on a variety of platforms and am certain it is not specific to my setup.

This code works fine (and computes e):

  (define y (integral (delay dy) 1 0.001))
  (define dy (stream-map (lambda (x) x) y))
  (stream-ref y 1000)

The following code should give an identical result:

  (define (solve f y0 dt)
    (define y (integral (delay dy) y0 dt))
    (define dy (stream-map f y))
    y)
  (stream-ref (solve (lambda (x) x) 1 0.001) 1000)

But it yields the error message:

standard input:7:14: While evaluating arguments to stream-map in expression (stream-map f y):
standard input:7:14: Unbound variable:
y ABORT: (unbound-variable)

So when embedded in a procedure definition, the (define y ...) does not work, whereas outside the procedure in the global environment at the REPL it works fine.

What am I doing wrong here? I can post the auxiliary code (i.e., the definitions of integral, stream-map etc.) if necessary, too. With the exception of the system-dependent code for cons-stream, they are all in the book. My own implementation of cons-stream for Guile is as follows:

(define-macro (cons-stream a b)
  `(cons ,a (delay ,b)))

Answer 1

The key difference between what happens when you evaluate the definitions one by one at the REPL and when you place them inside solve is that in the first case, they are evaluated sequentially, thus the y the expression (stream-map <some-function> y) refers to is already in scope, whereas with internal definitions or letrec, it is not yet available.

Funnily enough, MIT Scheme, which I used when going through SICP, had no such problem back then and still treats letrec and internal defines differently:

;; this is an error
(letrec ((xs '(1 2 3)) (ys (map (lambda (x) (+ x 1)) xs))) ys)

;; this is still an error (and is treated as such by Guile),
;; yet evaluates to (2 3 4) in MIT Scheme
(let () (define xs '(1 2 3)) (define ys (map (lambda (x) (+ x 1)) xs)) ys)

I'm not sure about the original "Revised Report On Algorithmic Language Scheme" or R2RS, but at least from R3RS on internal defines were supposed to be equivalent to letrec. Apparently this peculiarity of MIT's environment influenced the book... or perhaps it's the other way around.

Answer 2

You can't have internal DEFINEs that depend on one another; the language spec explicitly states this (R5RS 5.2.2):

... it must be possible to evaluate each expression of every internal definition in a body without assigning or referring to the value of any variable being defined.

You can think of this as though the interpreter is collecting all the DEFINES and evaluating them prior to the body in a random order. Because the order is random, there can't be any interdependencies if you expect it to work.

There's even a footnote attached to the SOLVE definition (#71) that says it's not going to work on all Schemes.

You have to write the code so that one definition is very clearly in the scope of the other, like with nested LETs:

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

Answer 3

Following the idea in the comments (referring to the quote from R5RS 4.2.2) I have now wrapped the definitions of "y" and "dy" into (lambda () ...)s:

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

This makes sure that that the <init> part of each definition can be evaluated without referring to the circular defined variables since the definitions are procedures rather than expressions with other variables like in the original case.

Now the code is certainly much slower (since the functions will get wrapped recursively) and the stack size needs to be increased, but the following works and produces the correct result:

  (debug-set! stack 2000000)
  (stream-ref (solve (lambda (x) x) 1 0.001) 1000)

---

With a similar modification, Michał's example code works as soon as one defines procedures rather than variables:

  (let ()
    (define (xs) '(1 2 3))
    (define (ys) (map (lambda (x) (+ x 1)) (xs)))
    (ys))

works on Guile 1.8.6.