[plt-scheme] to define, or to let

From: Bradd W. Szonye (bradd+plt at szonye.com)
Date: Sun Mar 21 03:36:07 EST 2004

> Felix Klock wrote:
>> The MzScheme extension to the semantics of LETREC is technically
>> legal according to R5RS

Note that Felix and I discussed this off-list, where I gave a concrete
example of the problem. He suggested that it might be more accurate to
describe it as a defect in the standard than as a nonconforming
implementation, and I agree. While I am personally opposed to left-to-
right LET and LETREC, I feel that implementors should have the freedom
to implement them that way, as extensions.

Anton van Straaten wrote:
> I believe that's incorrect.  As Bradd has pointed out, this was
> discussed in depth on c.l.s.:
> [see Message-ID <3a6511f0.0312082110.5d74f4e8 at posting.google.com>]

Thanks for citing the thread! I was too lazy to dig it up.

> I'll summarize:
> The standard defines some semantics [4.2.2, after "Semantics:"], and
> then makes a strong point about a "very important restriction" which
> follows from those semantics.  It also encodes the specified semantics
> in the letrec macro in 7.3.

Specifically, the semantics require that:

    The <variable>s are bound to fresh locations holding undefined
    values, the <init>s are evaluated in the resulting environment (in
    some unspecified order), each <variable> is assigned to the result
    of the corresponding <init>, the <body> is evaluated in the
    resulting environment, and the value(s) of the last expression in
    <body> is(are) returned.

A straightforward reading implies that an implementation must evaluate
all of the <init>s first, then assign all the <variables>, and a program
can verify this by capturing and restoring a continuation within an
<init>. MzScheme interleaves the <init>s and assignments.

One could argue that the semantics don't explicitly forbid this
interleaving, but there's no real support for that reading. One could
also argue that the interleaving *should* be permissible, that R6RS
should rephrase the semantics to permit it. I'm sympathetic to that
argument, even though I personally prefer "unspecified-order LETREC."
I don't see any compelling reason to require that specific sequence of
assignment, and many users do want MzScheme's "LETREC*" semantics, so
the current spec seems overconstrained.

> To achieve the letrec extension in question, the specified semantics
> cannot reasonably be followed.

Well, you could always assign the variables twice, once during
evaluation and once afterward, but it would be a bit awkward and

> However, I found that something like 16 implementations of Scheme,
> including PLT, implement this extension.  Apparently, this was done
> for pragmatic reasons before anyone noticed that ignoring the
> specified semantics was detectable.
> Al* Petrofsky pointed out that "when this issue of widespread letrec
> non-conformance was first pointed out in 1992, Will Clinger said:
> 'There isn't any great rush to settle this, because no one in his/her
> right mind would write a program that depends on this.'"

This is why I said that it wasn't a very important violation. I think it
would be a good idea to "settle this," perhaps by permitting the
interleaved evaluation and assignment.

>> Therefore, the extension should remain as 100% legal code for the PLT
>> family of languages

> Since this non-conformance is so widespread among Scheme
> implementations, and since fixing it would break existing code, it
> will certainly remain legal for most implementations.

Agreed. Also, all that prior art is yet more evidence that it's the
standard that's defective, not the implementations.
Bradd W. Szonye

Posted on the users mailing list.