[R6RS] cost of letrec* semantics for internal definitions

William D Clinger will at ccs.neu.edu
Wed Jan 31 22:23:44 EST 2007

Kent wrote:
> 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.

Good point, although "one or more" sounds like not many.
The paper definitely showed that programs do not have to
pay for the letrec* semantics if they don't rely on it.

The only question is how much they will pay if they rely
on it.  The paper's results suggest that the cost could
be high in systems whose compilers do not optimize this.

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

Yes.  That may involve some major re-education.  I became
concerned about this because Andre van Tonder's first two
reference implementations for libraries and syntax-case,
which were supposed to be written in R5RS Scheme, contain
quite a few violations of the R5RS letrec restriction, and
also contain at least some forward references of the kind
that make optimization of the letrec* semantics (on which
the code relies) non-trivial.

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

Out of curiosity concerning current practice, I ran a
very simple test case using the interactive REPL of the
usual suspects.  SCM and Scheme48 detected the violation
of the letrec restriction.  Gambit, Larceny, and Chez
Scheme 6.1 (Sparc) detected it, but only by accident:
the + procedure complained about a non-numeric argument.
The following systems did not detect the violation at
all: Bigloo, Chicken, Kawa, MIT Scheme, MzScheme, and
Petite Chez 7.0a.


More information about the R6RS mailing list