Inconsistent handling of letrec
Tzvetan Mikov
I am relatively new to Scheme programming, so excuse me if this
question is something obvious.
Are the following statements (which should be equivalent) invalid ?
According to my reading of R6RS they should generate an error either
at compile time or at execution time.
(letrec ((a 10) (b a)) b)
(let ()
(define a 10)
(define b a)
b)
I experimented with different Scheme implementations and I am getting
inconsistent results:
* Scheme48 (which I have come to regard as the golden standard) and
Guile generate an error "LETREC variable used before its value has
been produced". This is the correct behavior, AFAICT.
* Gambit Scheme returns an "#!unbound" value. Not ideal, but still
correct in some sense.
* RScheme, Kawa and MzScheme return a value of 10. I presume they
simply translate the statement into something like this, without any
checks:
(let ((a #!undefined) (b #!undefined)
(set! a 10)
(set! b a)
b))
Now, it seems to me that this is a pretty major aspect of the language
and I am surprised that it is handled so inconsistently. As far as I
can tell, MzScheme is a major Scheme implementation, but even it gets
it wrong according to my understanding.
I am working on my Scheme compiler (a simple one) as a way to learn
the language. Do you have any advise on which behavior I should
implement ? Clearly it is the easiest to ignore the issue like
RScheme, Kawa ansd MZScheme (and probably others) - tthis is in fact
what my implementation is currently doing , but am I deliberately be
introducing a standard violation ?
Thanks in advance for any clarification,
regards,
Tzvetan
Abdulaziz Ghuloum
> Hi,
> I am relatively new to Scheme programming, so excuse me if this
> question is something obvious.
>
> Are the following statements (which should be equivalent) invalid ?
> According to my reading of R6RS they should generate an error either
> at compile time or at execution time.
>
> (letrec ((a 10) (b a)) b)
This is not a valid letrec expression.
> (let ()
> (define a 10)
> (define b a)
> b)
This expression is valid and is not equivalent to the first
expression. This expression is equivalent to
(letrec* ([a 10] [b a]) b)
which performs a left-to-right evaluation and assignment of
the letrec*-bound variables.
In R5RS, the two expressions you listed are equivalent since
internal definitions were the same as letrec in R5RS, but were
made into letrec* in R6RS.
> I experimented with different Scheme implementations and I am getting
> inconsistent results:
That's expected since the expression is invalid and thus the
behavior is undefined for R5RS. :-)
> * Scheme48 (which I have come to regard as the golden standard) and
> Guile generate an error "LETREC variable used before its value has
> been produced". This is the correct behavior, AFAICT.
That's a correct behavior for R5RS, yes.
> * Gambit Scheme returns an "#!unbound" value. Not ideal, but still
> correct in some sense.
That too is a correct behavior for R5RS, yes.
> * RScheme, Kawa and MzScheme return a value of 10. I presume they
> simply translate the statement into something like this, without any
> checks:
> (let ((a #!undefined) (b #!undefined)
> (set! a 10)
> (set! b a)
> b))
That's an incorrect transformation for R5RS in general, but *is*
the correct transformation for R6RS. This is what letrec* does:
bind the variables first, then evaluate and assign from left to
right. Some R5RS systems used letrec* semantics for letrec simply
because it's a simpler transformation (in some sense). The letrec
transformation of the previous example is:
(let ([a #!undefined] [b #!undefined])
(let ([t0 10] [t1 a])
(set! a t0)
(set! b t1))
b)
> I am working on my Scheme compiler (a simple one) as a way to learn
> the language. Do you have any advise on which behavior I should
> implement ? Clearly it is the easiest to ignore the issue like
> RScheme, Kawa ansd MZScheme (and probably others) - this is in fact
> what my implementation is currently doing , but am I deliberately be
> introducing a standard violation ?
If you're learning about compilers and Scheme by writing a simple
Scheme compiler, I think you should ignore this issue for now,
move on to do the more interesting aspects of the compiler, and
come back to this issue at a later time (if ever). This should be
easy to fix later as long as you don't take advantage of the fact
that you're ignoring such errors.
Aziz,,,
Tzvetan Mikov
>
> > (let ()
> > (define a 10)
> > (define b a)
> > b)
>
> This expression is valid and is not equivalent to the first
> expression. This expression is equivalent to
>
> (letrec* ([a 10] [b a]) b)
>
> which performs a left-to-right evaluation and assignment of
> the letrec*-bound variables.
>
> In R5RS, the two expressions you listed are equivalent since
> internal definitions were the same as letrec in R5RS, but were
> made into letrec* in R6RS.
Thanks a lot for pointing that! I am looking at R6RS now and it
clearly says "letrec*" - I have no idea why I saw it as "letrec".
All implementations I tried did produce the same result for the two
expressions, but they are all R5RS.
> > * RScheme, Kawa and MzScheme return a value of 10. I presume they
> > simply translate the statement into something like this, without any
> > checks:
> > (let ((a #!undefined) (b #!undefined)
> > (set! a 10)
> > (set! b a)
> > b))
>
> That's an incorrect transformation for R5RS in general, but *is*
> the correct transformation for R6RS. This is what letrec* does:
> bind the variables first, then evaluate and assign from left to
> right. Some R5RS systems used letrec* semantics for letrec simply
> because it's a simpler transformation (in some sense). The letrec
> transformation of the previous example is:
>
> (let ([a #!undefined] [b #!undefined])
> (let ([t0 10] [t1 a])
> (set! a t0)
> (set! b t1))
> b)
Thanks, that's what I thought.
So, are RScheme, Kawa and MzScheme, all broken then ? They all accept
(letrec ((a 10) (b a)) b) without complaining.
> If you're learning about compilers and Scheme by writing a simple
> Scheme compiler, I think you should ignore this issue for now,
> move on to do the more interesting aspects of the compiler, and
> come back to this issue at a later time (if ever). This should be
> easy to fix later as long as you don't take advantage of the fact
> that you're ignoring such errors.
Well, I have experience with compilers, just not with Scheme.
Generating (terribly) unoptimized bytecode for Scheme is trivial, so
it is exactly these language details that are the most interesting to
me. Well, that and "define-syntax" :-) Plus, I think it is important
to try be fully compliant with the spec at every stage; later it is
extremely hard to retrofit compliance, especially if there isn't a set
of standardized tests.
On that subject, is there anywhere a set of tests for Scheme
implementation compliance ?
regards,
Tzvetan
Abdulaziz Ghuloum
> So, are RScheme, Kawa and MzScheme, all broken then ? They all accept
> (letrec ((a 10) (b a)) b) without complaining.
R5RS does not require that the implementations complain. R6RS, IIRC,
says that implementations *should* raise an exception, but they don't
have to.
According to R5RS however, such transformation is incorrect and you can
devise a test (using call/cc) to uncover whether an implementation is
performing the correct or the incorrect letrec transformation. These
implementations may fail that test. But as far as failing to raise an
error in these cases, they're perfectly fine as far as R5RS goes.
> Well, I have experience with compilers, just not with Scheme.
> Generating (terribly) unoptimized bytecode for Scheme is trivial, so
> it is exactly these language details that are the most interesting to
> me.
You might want to read ``Fixing Letrec: A Faithful Yet Efficient
Implementation of Scheme's Recursive Binding Construct'' by Waddell,
Sarkar, and Dybvig, available online at:
http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf
They basically break the issues with letrec into three categories:
1. Detecting violations of "the letrec restriction": this is the
issue that you're raising in this thread.
2. Performing the correct letrec transformation as specified in R5RS.
3. Efficiency concerning the naieve transformation (binding the
variables, evaluating the expressions, then set!ing the variables)
versus a more clever transformation that is both correct (as far
as R5RS requires) and at the same time generates better code.
> On that subject, is there anywhere a set of tests for Scheme
> implementation compliance ?
Nothing that I know of qualifies as a compliance test. Sorry.
Aziz,,,
Abdulaziz Ghuloum
> So, are RScheme, Kawa and MzScheme, all broken then ? They all accept
> (letrec ((a 10) (b a)) b) without complaining.
It may be worth noting that Ikarus (by yours truly) has a more
elaborate transformation that the one in ``Fixing Letrec'' that
reorders the clauses in a way that almost always hides such errors.
The transformation is correct for R6RS (R6RS's letrec is slightly
different from R5RS's), but due to not checking and enforcing the
letrec restriction, the programmer who is not aware of the problem
may be in trouble since such errors may lay dormant for long times
and would break when later used in a system that does enforce this
restriction.
Here is an transcript showing 6 permutations of the same letrec
bindings. Ikarus, sadly, generates the exact same code for all 6
expressions and never signals an error.
Ikarus Scheme version 0.0.3+ (revision 1446, build 2008-04-11)
Copyright (c) 2006-2008 Abdulaziz Ghuloum
> (letrec ([a 12] [b a] [c b]) c)
12
> (letrec ([b a] [a 12] [c b]) c)
12
> (letrec ([a 12] [c b] [b a]) c)
12
> (letrec ([b a] [c b] [a 12]) c)
12
> (letrec ([c b] [a 12] [b a]) c)
12
> (letrec ([c b] [b a] [a 12]) c)
12
>
Aziz,,,
Max Hailperin
...
> So, are RScheme, Kawa and MzScheme, all broken then ? They all accept
Aziz has given you very good, detailed technical information about
letrec and letrec*, but hasn't directly responded to this question, so
I'll do it.
The problem seems to be that you misunderstand what R5RS means when it
says that the above letrec "is an error". (In Section 4.2.2: "If
this restriction is violated, then it is an error.")
At the start of the R5RS, in Section 1.3.2, it stipulates:
"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.'"
As such, each R5RS-compliant Scheme implementation is free to behave
in any way whatsoever when presented with an erroneous letrec such as
you show above. None of the behaviors you observed were broken
(relative to R5RS), nor for that matter would any other behavior have
been, even a totally inexplicable one like evaluating to 42 or
reporting a division by zero error (with no division visible). -max
William D Clinger
> The transformation is correct for R6RS (R6RS's letrec is slightly
> different from R5RS's), but due to not checking and enforcing the
> letrec restriction, the programmer who is not aware of the problem
> may be in trouble since such errors may lay dormant for long times
> and would break when later used in a system that does enforce this
> restriction.
I don't think that's true. R6RS 11.4.6 says:
Implementation responsibilities: Implementations
must detect 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. Implementations may or may not
detect that the continuation of each <init> is
invoked more than once. However, if an implementation
detects this, it must raise an exception with
condition type &assertion.
Aziz must be interpreting the parenthetical phrase
as an exception to the general rule that implementations
"must detect references to a <variable> during the
evaluation of the <init> expressions", but the
parenthetical phrase is a clarification of the
general rule, not an exception to it. The purpose of
the parenthetical phrase is to avoid undecidability
for examples such as
(let ((cell #f))
(letrec ((a (begin (set! cell #t) 10))
(b (if cell a 10)))
b))
If implementations were required to determine whether
there exists an order of evaluation that would avoid
"references to a <variable> during the evaluation of
the <init> expressions" for examples like that, then
R6RS Scheme would not be implementable (by reduction
to the halting problem). This was pointed out by
formal comment #146 [2], and the parenthetical phrase
was added to fix the problems raised by that formal
comment.
The fact that neither Ikarus nor Larceny enforce this
mustard does not change the fact that it "must" be
enforced by all R6RS-conforming implementations.
Larceny's documentation correctly identifies this as
one of the reasons Larceny is merely R6RS-compatible,
not R6RS-conforming.
Will
[1] R6RS 11.4.6, specification of letrec.
http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_idx_402
[2] Formal comment #146. Mustard must not be preposterous.
http://www.r6rs.org/formal-comments/comment-146.txt
Abdulaziz Ghuloum
> The fact that neither Ikarus nor Larceny enforce this
> mustard does not change the fact that it "must" be
> enforced by all R6RS-conforming implementations.
Right. I stand corrected. I thought that the requirement
to detect the error was a "should" rather than a "must".
Thanks for the correction.
Aziz,,,
leppie
wrote:
> Right. I stand corrected. I thought that the requirement
> to detect the error was a "should" rather than a "must".
> Thanks for the correction.
>
> Aziz,,,
I think it's a typo in the spec then because mine says:
For letrec:
It should be possible to evaluate each <init> without assigning
or referring to the value of any <variable>.
For letrec*:
It must be possible to evaluate each <init> without assigning
or referring to the value of the corresponding <variable> or the
<variable> of any of the bindings that follow it in
<bindings>.
The implementation responsibilities of either implies 'must'.
Cheers
leppie
Abdulaziz Ghuloum
> I think it's a typo in the spec then because mine says:
>
> For letrec:
> It should be possible to evaluate each <init> without assigning
> or referring to the value of any <variable>.
>
> For letrec*:
> It must be possible to evaluate each <init> without assigning
> or referring to the value of the corresponding <variable> or the
> <variable> of any of the bindings that follow it in
> <bindings>.
These are the programmer's responsibility. The implementation's
responsibility is to detect violations of these requirements.
The wording may be poor since "should be possible" and "must be
possible" do not make much sense in this context. Better way to
say the first may be "Evaluation of each <init> must not reference
or assign to any of the <variable>s", but I forgot my lawyer hat
at home today.
Aziz,,,
Tzvetan Mikov
> Aziz has given you very good, detailed technical information about
> letrec and letrec*, but hasn't directly responded to this question, so
> I'll do it.
>
> The problem seems to be that you misunderstand what R5RS means when it
> says that the above letrec "is an error". (In Section 4.2.2: "If
> this restriction is violated, then it is an error.")
> As such, each R5RS-compliant Scheme implementation is free to behave
> in any way whatsoever when presented with an erroneous letrec such as
> you show above. None of the behaviors you observed were broken
> (relative to R5RS), nor for that matter would any other behavior have
> been, even a totally inexplicable one like evaluating to 42 or
> reporting a division by zero error (with no division visible). -max
Thanks for the detailed explanations from everybody. I think I wasn't
prepared for the subtleties in what seemed a clear matter (it is a
fundamental language form, after all): differences between R5RS and
R6RS, between "must" and "should", etc :-)
I admit I have only quickly browsed R5RS. I assumed that starting now
R6RS should be all I need. It appears that even in R6RS I have not
been as careful as I should (e.g. I missed the fact that define-s are
translated to letrec*, not letrec).
As for letrec, I assumed that any Scheme implementation is absolutely
required to report init errors. Many can be caught at compile time,
100% of the the rest should be caught at runtime. It appears that this
is the case for R6RS anyway.
To be honest, as a Scheme newbie, I find the state of affairs in R5RS
a bit surprising. So implementations are tolerated to accept erroneous
use letrec. This is especially troublesome because the erroneous form
can be genuinely useful (e.g. "(define a 10)(define b a)" ).
Practically speaking, how have you dealt with this ?
regards,
Tzvetan
Tzvetan Mikov
> [...]
> You might want to read ``Fixing Letrec: A Faithful Yet Efficient
> Implementation of Scheme's Recursive Binding Construct'' by Waddell,
> Sarkar, and Dybvig, available online at:
> http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf
Thanks for the link! It was very interesting. I think I could use
their validity checks technique relatively easily. I already had a
vague idea that many violations can be caught at compile time.
> > On that subject, is there anywhere a set of tests for Scheme
> > implementation compliance ?
>
> Nothing that I know of qualifies as a compliance test. Sorry.
I probably will try to gather a list of some popular Scheme programs
like the benchmarks used in the paper above. I am still too new to
know which ones are popular, though. Not real compliance, but should
go a long way towards validating the compiler.
I think using the r6rs libraries which I just found on your Ikarus
page will be extremely helpful.
> It may be worth noting that Ikarus (by yours truly) has a more
> elaborate transformation that the one in ``Fixing Letrec'' that
> reorders the clauses in a way that almost always hides such errors.
> The transformation is correct for R6RS (R6RS's letrec is slightly
> different from R5RS's), but due to not checking and enforcing the
> letrec restriction, the programmer who is not aware of the problem
> may be in trouble since such errors may lay dormant for long times
> and would break when later used in a system that does enforce this
> restriction.
I had seen Ikarus referenced several times, but I hadn't tried it
because it wasn't available in Debian's repositories. Now I have
quickly rectified that on my system though :-) I think I will start
using it as a reference implementation; none of the others in Debian
are R6RS.
> Here is an transcript showing 6 permutations of the same letrec
> bindings. Ikarus, sadly, generates the exact same code for all 6
> expressions and never signals an error.
>
> Ikarus Scheme version 0.0.3+ (revision 1446, build 2008-04-11)
> Copyright (c) 2006-2008 Abdulaziz Ghuloum
>
> > (letrec ([a 12] [b a] [c b]) c)
> 12
> > (letrec ([b a] [a 12] [c b]) c)
> 12
> > (letrec ([a 12] [c b] [b a]) c)
> 12
> > (letrec ([b a] [c b] [a 12]) c)
> 12
> > (letrec ([c b] [a 12] [b a]) c)
> 12
> > (letrec ([c b] [b a] [a 12]) c)
> 12
I am not getting the same results here.
Ikarus Scheme version 0.0.3
Copyright (c) 2006-2008 Abdulaziz Ghuloum
> (display (letrec ([c b] [b a] [a 12]) c))
#<void>
I assume you have changed this in the newer builds. Don't you consider
it a regression ?
regards,
Tzvetan
leppie
> To be honest, as a Scheme newbie, I find the state of affairs in R5RS
> a bit surprising. So implementations are tolerated to accept erroneous
> use letrec. This is especially troublesome because the erroneous form
> can be genuinely useful (e.g. "(define a 10)(define b a)" ).
>
> Practically speaking, how have you dealt with this ?
(define a 10)(define b a) ...
is
(letrec* ((a 10)(b a)) ... )
where the define occurs in a method body, a library body, or few other
mentioned places. (R6RS 11.2. Definitions)
Cheers
leppie
Tzvetan Mikov
Sorry that I wasn't clear. What I meant was, how do you deal with
writing portable applications in R5RS Scheme ? It appears that the
major implementations allow (and encourage?) the non-portable
behavior. This is not some obscure library function - it is at the
very core of the language.
regards,
Tzvetan
Andrew Reilly
I'm new to the game, but as near as I can tell, all (or at least most)
scheme implementations have not yet twigged to the merits of standards-
enforcing compilation modes (like -Werror -pedantic -std=c99 in gcc).
This is a fairly recent innovation in gcc too. Just like most scheme
implementations, for a long time gcc was really a language unto itself
that just happened to be able to compile standards-conforming source code
properly. It has many extensions, and various groups of people have used
these from time to time.
Add to this the fact that scheme's user base is smaller, and the history
of experimentation and evolution, and you'll find that several popular
implementations don't even have the weak form of standards compliance
described above, so it's not too likely that they'll be checking
pedantically. As William Clinger mentioned in an earlier post, it's
possible that pedantic standards checking is currently impossible, in
general (or at least equivalent to the halting problem in that it might
work in any given situation.)
People make portable scheme programs (as near as I can tell) by making
sure (testing) that they run on all of the implementations that they care
about.
Many other people (myself included) are not too concerned about
portability, and are happy just to use a single implementation. (But
even that requires version-to-version porting, some of which can be non-
trivial.)
Cheers,
--
Andrew
Ray Dillinger
> I am not getting the same results here.
> Ikarus Scheme version 0.0.3
> Copyright (c) 2006-2008 Abdulaziz Ghuloum
>
> > (display (letrec ([c b] [b a] [a 12]) c))
> #<void>
>
> I assume you have changed this in the newer builds. Don't you consider
> it a regression ?
The expression violates the letrec constraint and is therefore
an error. The result the compiler gave you (or any other result
for that matter) isn't wrong.
The problem is that in a letrec you have to be able to bind
everything before you actually evaluate any of the things that
get bound. In the above expression you're counting on letrec
to evaluate b before binding c, and to evaluate a before binding
b. This is considered "an error" in your program as far as
R5RS is concerned - standard compliance does not provide any
reason to give it any particular semantics.
Bear
leppie
> Sorry that I wasn't clear. What I meant was, how do you deal with
> writing portable applications in R5RS Scheme ? It appears that the
> major implementations allow (and encourage?) the non-portable
> behavior. This is not some obscure library function - it is at the
> very core of the language.
Sorry, I wasnt sure either :)
I agree with you on the R5RS issues, and that's why I decided to
implement R6RS instead (IronScheme).
Cheers
leppie
Tzvetan Mikov
> Tzvetan Mikov wrote:
> > I am not getting the same results here.
> > Ikarus Scheme version 0.0.3
> > Copyright (c) 2006-2008 Abdulaziz Ghuloum
>
> > > (display (letrec ([c b] [b a] [a 12]) c))
> > #<void>
>
> > I assume you have changed this in the newer builds. Don't you consider
> > it a regression ?
>
> The expression violates the letrec constraint and is therefore
> an error. The result the compiler gave you (or any other result
> for that matter) isn't wrong.
Well, that's what we have been discussing. I think the consensus is
that R6RS implementations are required to report it as an error in one
way or another. In this case #<void> is not really signaling an error,
but is probably better than returning 12.
regards,
Tzvetan
Ray Dillinger
>
> Well, that's what we have been discussing. I think the consensus is
> that R6RS implementations are required to report it as an error in one
> way or another. In this case #<void> is not really signaling an error,
> but is probably better than returning 12.
ignoring it.
Bear
Abdulaziz Ghuloum
> I am not getting the same results here.
> Ikarus Scheme version 0.0.3
> Copyright (c) 2006-2008 Abdulaziz Ghuloum
>
> > (display (letrec ([c b] [b a] [a 12]) c))
> #<void>
>
> I assume you have changed this in the newer builds. Don't you consider
> it a regression ?
As was said, there are two issues here: (1) checking for violations of
the letrec restriction, and (2) performing a transformation that allows
for compiling letrec correctly and efficiently. The two issues are
orthogonal in that you can transform the letrec using any one of many
possible transformations independently of inserting the checks.
Ikarus does not insert the letrec violation checks, and that's why you
don't get an error for these expressions. So, no, I don't consider it
a regression since it didn't do the checks then and it doesn't do it
now. The checks will have to be inserted anyways, regardless of what
letrec transformation I choose to do later.
Aziz,,,
George Neuner
<andrew-...@areilly.bpc-users.org> wrote:
>I'm new to the game, but as near as I can tell, all (or at least most)
>scheme implementations have not yet twigged to the merits of standards-
>enforcing compilation modes (like -Werror -pedantic -std=c99 in gcc).
The -std flag is recent, the others go back at least 15 years (to my
first use of GCC).
>This is a fairly recent innovation in gcc too. Just like most scheme
>implementations, for a long time gcc was really a language unto itself
>that just happened to be able to compile standards-conforming source code
>properly. It has many extensions, and various groups of people have used
>these from time to time.
The major difference is that Scheme, as defined by RnRS, is supposed
to be mostly portable among conforming compilers. In contrast, large
portions of the C standard are defined to be implementation specific
and may be non-portable even among supposedly conforming compilers.
GCC is in a bad spot ... versions of it support many different
architectures. Any particular target processor may _require_
extensions to C and/or standard features of the language may not even
make sense to support (think about coding for DSPs and GPUs for
example).
George
--
for email reply remove "/" from address