letrec semantics

letrec semantics

[Alexander Asteroth]

Dear all,

I know this topic has been discussed in the past. I found at least one
discussion in 2003 in guile-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?

Cheers,
Alex

Re: letrec semantics

[Jean Abou Samra]

[-- Attachment #1.1: Type: text/plain, Size: 3084 bytes --]

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



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 236 bytes --]

Re: letrec semantics

[Taylan Kammer]

On 28.11.2022 09:33, Alexander Asteroth wrote:
> 
>> 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
> 

Hi Alex,

The only reason the first example returns 7 is because Guile *happens* to
bind a to 7 before it binds b to the value of a.  The code could have as
well returned another value (IIRC Guile uses #<unspecified>) had Guile
decided to evaluate the arms of the letrec in a different order.

As per the part of the standard you quoted:

> the 〈init〉s are evaluated [...] (in some unspecified order)

That's what the "unspecified order" in the parentheses is referring to.

On the other hand, in your second code example, there's a strict order
in which the various expressions will be evaluated.  In the moment you
type in (set! b a), the value of a has not yet been changed to 7.

If you want to use letrec but with a specific order of evaluation of the
arms, then you can use the letrec* variant:

> (letrec* ((a 7) (b a)) b)
> $1 = 7

This will definitely work, without relying on chance or an implementation
detail of Guile.

-- 
Taylan

Re: letrec semantics

[Alexander Asteroth]

Dear Jean,

thanks for pointing that out which confirmed my interpretation of the
R5RS. 

Cheers,
Alex

On Mon, Nov 28 2022, 10:25:46, Jean Abou Samra <jean@abou-samra.fr> wrote:

> [[PGP Signed Part:Undecided]]
> 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 in guile-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
>
> [[End of PGP Signed Part]]

Re: letrec semantics

[Alexander Asteroth]

Dear Taylan,

thanks for pointing me to the use of letrec* in this case. The case
though was meant as an example to illustrate the problem. I'm currently
implementing an R5RS interpreter and was unsure if I can handle letrec
as illustrated below in the second case or if I need to implement it as
guile does.

Cheers,
Alex

On Mon, Nov 28 2022, 15:07:39, Taylan Kammer <taylan.kammer@gmail.com> wrote:

> On 28.11.2022 09:33, Alexander Asteroth wrote:
>> 
>>> 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
>> 
>
> Hi Alex,
>
> The only reason the first example returns 7 is because Guile *happens* to
> bind a to 7 before it binds b to the value of a.  The code could have as
> well returned another value (IIRC Guile uses #<unspecified>) had Guile
> decided to evaluate the arms of the letrec in a different order.
>
> As per the part of the standard you quoted:
>
>> the 〈init〉s are evaluated [...] (in some unspecified order)
>
> That's what the "unspecified order" in the parentheses is referring to.
>
> On the other hand, in your second code example, there's a strict order
> in which the various expressions will be evaluated.  In the moment you
> type in (set! b a), the value of a has not yet been changed to 7.
>
> If you want to use letrec but with a specific order of evaluation of the
> arms, then you can use the letrec* variant:
>
>> (letrec* ((a 7) (b a)) b)
>> $1 = 7
>
> This will definitely work, without relying on chance or an implementation
> detail of Guile.

Re: letrec semantics

[Linus Björnstam]

Guile implements letrec using letrec*, which most schemes always did, but it wasn't specified due to people wanting to leave possible optimisations on the table. 

The order of letrec is unspecified and schemes are allowed to do whatever order they like. Guile uses the algorithm described in "fixing letrec(reloaded)".

-- 
  Linus Björnstam

On Mon, 28 Nov 2022, at 09:33, Alexander Asteroth wrote:
> Dear all,
>
> I know this topic has been discussed in the past. I found at least one
> discussion in 2003 in guile-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?
>
> Cheers,
> Alex