Scheme/Racket中letrec与letrec*的含义及转换机制问询

Great questions about these Scheme/Racket binding constructs—let's break them down with clear examples and transformations.

1. How does letrec enable recursion, and what does your example convert to? #

The core superpower of letrec is that it allows bindings to reference themselves (or each other) recursively. Unlike let (which evaluates all right-hand-side expressions first, then binds them) or let* (which binds sequentially but doesn't support self-reference), letrec works by:

• First creating placeholder bindings for all variables (they start with an undefined or dummy value, like #f in Racket).
• Then assigning each variable its actual value using set!.
• Finally executing the body in this fully initialized environment.

This means even recursive functions can be defined, because the lambda in the right-hand side can reference the variable name before it's fully assigned—since the placeholder already exists.

For your example:

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

It converts to this equivalent form (using let for placeholders + set! for assignments):

(let ((x #f) (y #f))
  (set! x 1)
  (set! y 2)
  (+ x y))

To see recursion in action, consider a factorial function defined with letrec:

(letrec ((fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1)))))))
  (fact 5))

The conversion would be:

(let ((fact #f))
  (set! fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
  (fact 5))

Here, the lambda can reference fact because the placeholder binding exists when the lambda is created—even though fact isn't fully assigned until after the lambda is defined.

2. What's the difference between letrec* and letrec, and how is it transformed? #

The critical difference lies in evaluation order:

• letrec evaluates all right-hand-side expressions in an environment where all variables exist but are uninitialized (or hold dummy values). You can reference other variable names in the bindings, but you can't rely on their assigned values (except for lambdas, which delay evaluation until later).
• letrec* evaluates and assigns bindings sequentially. Each subsequent right-hand-side expression can safely reference the values of previously assigned variables, since those assignments are already complete.

For example, this letrec* expression works as expected:

(letrec* ((x 1) (y (+ x 2))) y) ; Returns 3

But the same code with letrec would have undefined behavior (in Racket, it would throw an error, since x is still a dummy value when evaluating (+ x 2)).

The transformation for letrec* reflects this sequential behavior. It uses nested let + set! blocks to ensure each assignment happens before the next binding is processed. For the example above, the conversion is:

(let ((x #f))
  (set! x 1)
  (let ((y #f))
    (set! y (+ x 2))
    y))

A more complex letrec* example:

(letrec* ((a 2) (b (* a 3)) (c (+ b 5))) c) ; Returns 11

Converts to:

(let ((a #f))
  (set! a 2)
  (let ((b #f))
    (set! b (* a 3))
    (let ((c #f))
      (set! c (+ b 5))
      c)))

内容的提问来源于stack exchange，提问作者user4285147