Re: letrec semantics

[Jean Abou Samra]

Le 28/11/2022 à 09:33, Alexander Asteroth a écrit :
> Dear all,
>
> I know this topic has been discussed in the past. I found at least one
> discussion in 2003 inguile-user@gnu.org  which in the end referred to
> even earlier discussions in comp.lang.scheme. But still I'm confused
> about this and wonder if someone could help with this or point me to a
> discussion that resolves the following issue.
>
> In R5RS it sais about letrec:
>
> > Semantics: 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 environmet [...]
> As I (and others) understand
>
> > scheme@(guile-user)> (letrec ((b a)(a 7)) b)
> > $1 = 7
> should be equivalent (of course in a new scope) to:
>
> > scheme@(guile-user)> (define b #nil)
> > scheme@(guile-user)> (define a #nil)
> > scheme@(guile-user)> (set! b a)
> > scheme@(guile-user)> (set! a 7)
> > scheme@(guile-user)> b
> > $2 = #nil
> but obviously it is't. Why is b assigned to a's reference rather than
> it's value in letrec? ... and would it be a correct implementation of
> R5RS-letrec to return #nil from the letrec above?




Interesting. R5RS says:

“One restriction on letrec is very important: it must be possible
to evaluate each <init> without assigning or referring to the value of
any <variable>. If this restriction is violated, then it is an error.
The restriction is necessary because Scheme passes arguments by value
rather than by name. In the most common uses of letrec, all the <init>s
are lambda expressions and the restriction is satisfied automatically.”

Note that “it is an error” does not mean that an error must be raised.
This is clarified in the section “Error situations and unspecified 
behavior”:

“When speaking of an error situation, this report uses the phrase ``an error
is signalled'' to indicate that implementations must detect and report the
error. If such wording does not appear in the discussion of an error,
then implementations are not required to detect or report the error, though
they are encouraged to do so. An error situation that implementations are
not required to detect is usually referred to simply as ``an error.''”

Therefore, your program is buggy, and what Guile does is R5RS-conformant 
because
R5RS does not define this case.

However, R6RS differs from R5RS on this point:

“Implementation responsibilities: Implementations must de-
tect references to a 〈variable〉 during the evaluation of 
the〈init〉expressions
(using one particular evaluation order and order of evaluating the 〈init〉
expressions).If an implementation detects such a violation of the 
restriction,
it must raise an exception with condition type &assertion.”


Therefore, according to R6RS, Guile is buggy because it should raise
an error in this case.


Best,
Jean

OpenPGP_signature
Description: OpenPGP digital signature