Why not letrec as fix?

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 ?

Solution

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