[plt-scheme] How is letrec different from letrec* in its use?

According to the R6RS docs,

(letrec* ([x 1]
          [y 2])
  (+ x y))

is NOT equivalent to

(letrec ([x 1])
  (letrec ([y 2])
    (+ x y)))

It is equivalent with:
(let ((x #f) (y #f))
 (set! x 1)
 (set! y 2)
 (+ x y))

The difference between letrec and letrec* is that the letrec does not 
specify the order in which the values to be bound are evaluated and 
assigned, whereas letrec* does guarantee that the values are computed and 
assigned from left to right. Letrec* is not a nested letrec, whereas let* 
may be regarded as a nested let. Hence the correspondence between letrec and 
letrec* is quite different from that between let and let*. Notice that in 
PLT-scheme's letrec is like letrec*, but according to R6RS it might have 
been different as follows:

(letrec ((x 1) (y 2)) (+ x y)) -->

(let ((x undefined) (y undefined))
 (let ((tempx 1) (tempy 2)) ; in arbitrary order
  (set! x tempx) (set! y tempy) ; in arbitrary order
  (+ x y)))

and

(letrec* ((x 1) (y 2)) (+ x y)) -->

(let ((x undefined) (y undefined))
  (set! x 1) (set! y 2) ; from left to right
  (+ x y))

Jos

----- Original Message ----- 
From: "Grant Rettke" <grettke at acm.org>
To: "James Coglan" <jcoglan at googlemail.com>
Cc: "PLT-Scheme List" <plt-scheme at list.cs.brown.edu>
Sent: Saturday, February 14, 2009 6:01 AM
Subject: Re: [plt-scheme] How is letrec different from letrec* in its use?


> On Fri, Feb 13, 2009 at 6:35 AM, James Coglan <jcoglan at googlemail.com> 
> wrote:
>>> I just read the spec for both letrec and letrec* and I see that the
>>> former is not evaluted in any other but the latter is evaluted from
>>> left to right. I am not getting the difference in their use. May
>>> someone please provide an illuminating example?
>
>> (letrec) is like (let), but the evaluations take place *inside* the 
>> lambda,
>> changing their scope. The evaluations are not supposed to depend on each
>> other so evaluation order is not important (like for (let)).
>>
>> (letrec ([x 1]
>>          [y 2])
>>   (+ x y))
>>
>> is equivalent to:
>>
>> ((lambda ()
>>   (define x 1)
>>   (define y 2)
>>   (+ x y)))
>
> This is how I interpreted its behavior from the spec:
>
> (define-syntax my-letrec
>  (syntax-rules ()
>    ((_ ((var init) ...) body)
>     (let ((var #f) ...)
>       (set! var init) ...
>       body))))
>
> (my-letrec
> ((a (lambda (n) (when (< n 5) (b (add1 n)))))
>  (b (lambda (n) (when (< n 5) (a (add1 n))))))
> (a 0))
>
> #;(let ((a #f)
>        (b #f))
>    (set! a (lambda (n) (when (< n 5) (b (add1 n)))))
>    (set! b (lambda (n) (when (< n 5) (a (add1 n)))))
>    (a 0))
>
> Are we saying the same thing? Is this right?
>
>> Finally, (letrec*) is like (let*) but it uses (letrec).
>>
>> (letrec* ([x 1]
>>           [y 2])
>>   (+ x y))
>>
>> is equivalent to:
>>
>> (letrec ([x 1])
>>   (letrec ([y 2])
>>     (+ x y)))
>
> I see. This allow for mutually recursive definitions; but as Sam said
> you can predict about behavior in situations when you are not *only*
> binding lambda expressions.
>
> I am wondering why would people use letrec for anything other than
> binding lambda expressions if it is impossible to reason about its
> behavior? Or rather, why would it allow anything other than lambda
> expressions to be bound if you can't predict the behavior?
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme