Can every letrec be replaced with letrec*?

Question

For every 100% compliant R7RS-small program that does not rely on any implementation-specific or undefined behavior, is it true that every instance of letrec in the program can be replaced with letrec* without causing any change in behavior? In other words, is there any R7RS-small program where an appearance of letrec cannot be substituted with letrec*?

Answer 1

I think that the answer is yes, it can, assuming that the form is not 'an error' in R7RS terminology (but see note at end). In particular I think that if there's a form like

(letrec ((v1 <e1>) (v2 <e2>)) ...)

Then it must be possible to evaluate <e2> without referring to the value of v1, but that binding does actually exist when <e2> is evaluated: it is just an error to refer to it. So in particular this is not allowed:

(let ((a 1)) (letrec ((a 2) (b a)) ...))

because the binding that the init for b refers to is that established by the letrec, not that established by the let, but it is not yet legal to refer to the value of that binding.

That being the case then if you simply replace letrec by letrec* then <e2> still will not refer to the value of v1 and thus the results will be the same.

The converse is not true:

(letrec* ((a 1) (b a)) ...)

is fine, but you can't replace the letrec* by letrec there.

That being the case I'm unclear what useful purpose letrec serves (perhaps this is why Racket's letrec has the semantics of Scheme's letrec*).

---

Note an earlier version of this answer came to the opposite conclusion. I am now not convinced I understand things well enough.