((( [logo]Racket )))Need Help?
AboutDownloadDocumentationPLaneTCommunityLearning

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

> 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
http://www.szonye.com/bradd
Posted on the users mailing list.