[R6RS] cost of letrec* semantics for internal definitions

[R. Kent Dybvig]

> 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".

That's correct.  I thought I mentioned that the paper was available on my
web site.  I apologize if I promised to send a pointer and failed to do
so.

> 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.

As I recall, many of these programs were written with definitions at top
level and were converted to use letrec* and that one or more did take
advantage of the essentially letrec* semantics of the top level.

> 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.

Perhaps, but it is at least apparent that for programs exhibiting letrec
semantics, letrec* semantics doesn't cause any harm.  Text books and
implementation manuals can advertise the fact that sticking with lambda
expressions or at least letrec semantics is most likely to give the best
results.

> 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.

Given our retro-looseness in error-checking requirements, I have no
problem changing the implementation requirement to "should raise" rather
than "must raise".

Kent