* letrec semantics @ 2022-11-28 8:33 Alexander Asteroth 2022-11-28 9:25 ` Jean Abou Samra ` (2 more replies) 0 siblings, 3 replies; 6+ messages in thread From: Alexander Asteroth @ 2022-11-28 8:33 UTC (permalink / raw) To: guile-user 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 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: letrec semantics 2022-11-28 8:33 letrec semantics Alexander Asteroth @ 2022-11-28 9:25 ` Jean Abou Samra 2022-11-30 17:23 ` Alexander Asteroth 2022-11-28 14:07 ` Taylan Kammer 2022-12-01 9:30 ` Linus Björnstam 2 siblings, 1 reply; 6+ messages in thread From: Jean Abou Samra @ 2022-11-28 9:25 UTC (permalink / raw) To: Alexander Asteroth, guile-user [-- 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 --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: letrec semantics 2022-11-28 9:25 ` Jean Abou Samra @ 2022-11-30 17:23 ` Alexander Asteroth 0 siblings, 0 replies; 6+ messages in thread From: Alexander Asteroth @ 2022-11-30 17:23 UTC (permalink / raw) To: Jean Abou Samra; +Cc: Alexander Asteroth, guile-user 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]] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: letrec semantics 2022-11-28 8:33 letrec semantics Alexander Asteroth 2022-11-28 9:25 ` Jean Abou Samra @ 2022-11-28 14:07 ` Taylan Kammer 2022-11-30 17:24 ` Alexander Asteroth 2022-12-01 9:30 ` Linus Björnstam 2 siblings, 1 reply; 6+ messages in thread From: Taylan Kammer @ 2022-11-28 14:07 UTC (permalink / raw) To: Alexander Asteroth, guile-user 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 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: letrec semantics 2022-11-28 14:07 ` Taylan Kammer @ 2022-11-30 17:24 ` Alexander Asteroth 0 siblings, 0 replies; 6+ messages in thread From: Alexander Asteroth @ 2022-11-30 17:24 UTC (permalink / raw) To: Taylan Kammer; +Cc: Alexander Asteroth, guile-user 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. ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: letrec semantics 2022-11-28 8:33 letrec semantics Alexander Asteroth 2022-11-28 9:25 ` Jean Abou Samra 2022-11-28 14:07 ` Taylan Kammer @ 2022-12-01 9:30 ` Linus Björnstam 2 siblings, 0 replies; 6+ messages in thread From: Linus Björnstam @ 2022-12-01 9:30 UTC (permalink / raw) To: Alexander Asteroth, guile-user 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 ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2022-12-01 9:30 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-11-28 8:33 letrec semantics Alexander Asteroth 2022-11-28 9:25 ` Jean Abou Samra 2022-11-30 17:23 ` Alexander Asteroth 2022-11-28 14:07 ` Taylan Kammer 2022-11-30 17:24 ` Alexander Asteroth 2022-12-01 9:30 ` Linus Björnstam
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).