Why not letrec as fix?

Question

In the paper Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme’s Recursive Binding Construct by Dybvig et al. it is said that (emphasis mine):

A theoretical solution to these problems is to restrict letrec so that its left-hand sides are unassigned and right-hand sides are lambda expressions. We refer to this form of letrec as fix, since it amounts to a generalized form of fixpoint operator. The compiler can handle fix expressions efficiently, and there can be no violations of the letrec restriction with fix. Unfortunately, restricting letrec in this manner is not an option for the implementor and would in any case reduce the generality and convenience of the construct.

I have not scrutinized the R5RS report, but I have used letrec and the equivalent "named let" in Scheme programs and the unfortunate consequences mentioned in the paper are not clear to me, can someone enlighten me ?

Answer 1

With equational syntax,

letrec x = init-x
       y = init-y
  body....

the restriction is that no RHS init... expression can cause evaluation of (or assignment to) any of the LHS variables, because all init...s are evaluated while all the variables are still unassigned. IOW no init... should reference any of the variables directly and immediately. It is OK of course for any of the init...s to contain lambda-expressions which can indeed reference any of the variables (that's the purpose of letrec after all). When these lambda-expressions will be evaluated, the variables will be already assigned the values of the evaluated init... expressions.

The authors say, to require all the RHSes to be lambda-expressions would simplify the implementation, because there's no chance for misbehaving code causing premature evaluation of LHS variables inside some RHS. But unfortunately, this changes letrec's semantics and thus is not an option. It would also prohibit simple use of outer variables in RHSes and thus this new cut-down letrec would also be less general and less convenient.

---

You also mention named let but it is not equivalent to letrec: its variables are bound as-if by let, only the looping function itself is bound via letrec:

(let ((x 1)(y 2))
  (let g ((x x) (y x))
    (if (> x 0) (g (- x y) y) (display x)))
  (display x))
01
;Unspecified return value

(let ((x 1)(y 2))
  (letrec ((g (lambda (x y) 
                (if (> x 0) (g (- x y) y) (display x)))))
     (g x x))  ; no 'x' in letrec's frame, so refer to outer frame
  (display x))
01
;Unspecified return value

Answer 2

The R5RS letrec restriction says something like these are in violation:

(let ((x 10))
  (letrec ((x x))
    x))

(letrec ((y (+ x 5)) 
         (x 5)) 
  (list x y))

Thus, it's not specified what would happen and it would certainly not be portable Scheme. It may evaluate to 10 and (5 10), the implementation might signal an error or you get an undefined value that might result in an error getting signaled. I have tested Racket, Gambit, Chicken and Ikarus and not one of them signal anything in the first case and they all evaluate to an unspecified value. Ikarus is the only one that returned (5 10) in the latter while the others all got contract errors since an unspecified value as argument violates +'s contract. (Ikarus always evaluates operands right to left)

The R[567]RS reports all state that if all expressions are lambda expressions you have nothing to worry about and I think that is the clue. Another is that you should not try to shadow like you would do with (named) let.

There is a follow up on the original paper that is entitled Fixing letrec (reloaded) that has macros that implements the "fix".