letrec implementation question
Ashley Yakeley
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
If my Scheme implementation relaxes this (using the magic of fixed-point
operators), can I still claim to be R5RS-compliant? For instance:
(define hello-goodbyes
(letrec
((x
`(hello goodbye . ,x)
))
x
)
)
(list-head hello-goodbyes 30)
=>
(hello goodbye hello goodbye hello goodbye hello goodbye hello goodbye
hello goodbye hello goodbye hello goodbye hello goodbye hello goodbye
hello goodbye hello goodbye hello goodbye hello goodbye hello goodbye)
At the moment I have a fixed-point function:
(define hello-goodbyes
(call-with-result (lambda (x) `(hello goodbye . ,x) ))
)
...see <http://hscheme.sourceforge.net/examples.html>. But simply using
letrec would be nicer.
--
Ashley Yakeley, Seattle WA
be...@sonic.net
>
> R5RS (sec. 4.2.2) says this:
>
> 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
>
> If my Scheme implementation relaxes this (using the magic of fixed-point
> operators), can I still claim to be R5RS-compliant? For instance:
>
> (define hello-goodbyes
> (letrec
> ((x
> `(hello goodbye . ,x)
> ))
> x
> )
> )
> (list-head hello-goodbyes 30)
If people can still write correct scheme and it will be interpreted
in the correct way, you can claim R5RS compliance. You're talking
about adding a non-r5rs capability, which will make it possible to
run code on your system which "is an error" according to R5RS.
But R5RS does not require your implementation to report this error.
Given code that is "an error" according to R5RS, a compliant
implementation is free to do anything, including halting with an
error message, ignoring it altogether, launching a debugger,
executing your proposed semantics of fixed-point operations, or
making demons fly out of your nose.
Bear
ol...@pobox.com
via a fixpoint combinator. Otherwise, the difference from the
R5RS-prescribed letrec will become observable. This topic has been
discussed in great detail in the following threads:
http://google.com/groups?threadm=200102210355.TAA75256%40adric.cs.nps.navy.mil
http://google.com/groups?threadm=200102220358.TAA77339%40adric.cs.nps.navy.mil
Dorai Setaram's message shows the test. We can re-write this test is in
OCaml. The test shows that OCaml implements letrec the way R5RS does
(rather than via a fixpoint iteration). Incidentally, surprisingly many
Scheme systems don't implement letrec correctly, as discussed in
http://google.com/groups?selm=87d793aacz.fsf_-_%40app.dial.idiom.com
http://google.com/groups?selm=7eb8ac3e.0105210930.21542605%40posting.google.com
ol...@pobox.com
> If my Scheme implementation relaxes this (using the magic of fixed-point
> operators), can I still claim to be R5RS-compliant? For instance:
>
> (define hello-goodbyes
> (letrec
> ((x
> `(hello goodbye . ,x)
> ))
> x
> )
> )
> (list-head hello-goodbyes 30)
specifically allows an implementation to implicitly force
arguments. Although I know of only one implementation that does
implicit forcing: Gambit-C in a compile mode in the presence of an
undocumented flag. We can program the forcing explicitly, as the code
below shows.
; R5RS permits (force x) to return x even if x is not the result
; of a delay. Some Scheme implementations (e.g., Gambit), do
; that. Some others (e.g., Scheme48 or SCM or Bigloo), do not.
; Use the following statement for the latter systems:
(let ((old-force force))
(set! force (lambda (x) (if (procedure? x) (old-force x) x))))
; Some Scheme implementations provide for automatic forcing of
; car, cdr, etc. arguments (as R5RS permits). The following definitions
; would be unnecessary then.
(define (fcar x) (car (force x)))
(define (fcdr x) (cdr (force x)))
(define (fnull? x) (null? (force x)))
; Print at most n elements from the list x
(define (print-n n x)
(do ((i 0 (+ 1 i)) (x x (fcdr x)))
((or (>= i n) (fnull? x)) (newline))
(for-each display (list i ": " (fcar x) #\newline))))
(define hello-goodbyes
(letrec
((x
`(hello goodbye . ,(delay x))
))
x))
(print-n 30 hello-goodbyes)
; Result (on Gambit, Bigloo, Scheme48):
> (print-n 30 hello-goodbyes)
0: hello
1: goodbye
2: hello
3: goodbye
4: hello
5: goodbye
...
Max Hailperin
> I'm afraid letrec in Scheme may not be implemented pure functionally
> via a fixpoint combinator. Otherwise, the difference from the
> R5RS-prescribed letrec will become observable. ...
However, there is no reason why an implementation couldn't use the
standard Scheme approach (based on set!) for all R5RS-compliant
programs, and use the fixpoint approach for non-R5RS-compliant code
such as the cyclic list example. As has been pointed out before, all
bets are off in that case, since it "is an error." So switching from
set! to fixpoint there would be perfectly legal. Doing that switching
correctly in every case (including in presence of side effects,
first class continuations, etc.) would be quite a trick to pull off.
But I don't see any obvious proof that it would be impossible -- and
if it were possible, and if it were done, it would be
R5RS-compliant. -max
Matthias Blume
<duck>
Another solution is to simply ignore R5RS in this regard.
Anyone whose code depends on the fine points of how letrec is
implemented deserves what they gets. Moreover, I don't believe
for a second that the AUTHORS have intended the observed distinction
to be present...
</duck>
Matthias
Joe Marshall
> <duck>
>
> Another solution is to simply ignore R5RS in this regard.
>
> Anyone whose code depends on the fine points of how letrec is
> implemented deserves what they gets. Moreover, I don't believe
> for a second that the AUTHORS have intended the observed distinction
> to be present...
>
> </duck>
I agree completely. (wow! is this weird or what)