Why is the variable undefined in the initialization form of this letrec?

Question

Scheme complains that in the code below, the x in (+ x 1) is undefined:

(letrec ((x 1)
         (y (+ x 1)))
  y)

• Chez Scheme: Exception: attempt to reference undefined variable x
• MIT Scheme: ;Unassigned variable: x

So, I defined another x:

(let ((x 999))
  (letrec ((x 1)
           (y (+ x 1)))
    y))

However, the Scheme implementations still complain that the x in (+ x 1) is undefined. What is going on? Clearly, I have already defined x.

Answer 1

That's not how letrec works. You can think of letrec as if it did something close to this (see R7RS, 4.2.2 for instance).

(letrec ((a <xpr>)
         ...inits)
  ...body)

is equivalent to

(let ((a <illegal-value>)
      ...)
  (set! a <xpr>)
  ...set other variables...
  ...body)

Where <illegal-value> is some thing you are never meant to refer to, and which implementations may make illegal to reference.

This is not quite what letrec does, because in the above expansion the assignments happen in a defined order, whereas in letrec the evaluations of the initialisation forms do not. So a fancier expansion might be using let first, since its order of evaluations is also non-defined:

(let ((a <illegal-value>)
      ...)
  (let ((<t1> <xpr>)
        ...)
    (set! a <t1>)
    ...set other variables...
    ...body))

Now we can see that

(let ((a 999))
  (letrec ((a 1)
           (b a))
    b))

will fail, because the expansion inserts another let which shadows the outer binding:

(let ((a 999))
  (let ((a <illegal>)
        (b <illegal>))
    (let ((t1 1)
          (t2 a))
      (set! a t1)
      (set! b t2)
      b)))

and you can see that what is going wrong is when t2 is bound to a which refers to the current value of the binding of a which is <illegal>, while the outer a whose value is 999 is inaccessible.

On the other hand, this:

(letrec ((a (lambda () b))
         (b (lambda () a)))
  (eq? ((b)) b))

both will work, and will return true, because in the expansion (b) will be called after the set!s.

The most common use of letrec is that it allows recursive functions to be bound: in something like

(letrec ((f (lambda (n)
              (if (<= n 2)
                  n
                  (+ (f (- n 1)) 1)))))
  ...)

Then f needs to refer to the same binding of f in order to work, but it does not actually look at the value of that binding until the function is called, by which time all is well.

See my other answer for some other possible uses of letrec however.