[R6RS] cost of letrec* semantics for internal definitions

[William D Clinger]

In one of our telephone conversations, I expressed
concern about letrec* semantics for internal definitions,
because the only way I had come up with to enforce the
letrec* restriction for letrec* semantics without losing
any post-initialization performance was to duplicate code.

Kent said it wasn't a problem, he knew how to do it, and
would send me a pointer to something he had written.  He
hasn't sent the pointer, but I suspect he was referring
to a paper I found on his website with the title "Fixing
Letrec: A Faithful Yet Efficient Implementation of Scheme's
Recursive Binding Construct".

The basic transformation, which is described by section
2.1 of that paper, is similar to what Twobit has been
doing since the early 1990s.  The generalization to
letrec* is described in section 3, and is pretty easy
to understand.  Section 4 presents an impressive array
of benchmark results.

I do not buy the paper's conclusion "that, in practice,
our implementation of letrec* is as efficient as letrec"
nor can I agree that the paper "debunks the commonly
held notion that fixing the order of evaluation hampers
production of efficient code for letrec."  The empirical
support for those claims consists of measurements made
on R5RS Scheme programs whose letrecs and internal
definitions were treated as letrec*.  Since these
programs are supposed to be R5RS-compliant, they should
not violate the R5RS letrec restriction, which means
they do not take advantage of the letrec* semantics.
This fact can be seen quite clearly in figure 12.

It is easy to construct examples for which the
transformations described by the paper do not eliminate
many of the run-time checks required to enforce the
letrec* restriction.  Had the paper used benchmarks
from MzScheme, which effectively encourages programmers
to violate the R5RS letrec restriction (by guaranteeing
letrec* semantics for internal definitions), I suspect
that the true cost of the letrec* semantics would have
become apparent.

The bottom line is that I still do not know how to
implement the letrec* semantics efficiently, while
enforcing the letrec* restriction, without duplicating
code.

Will