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

While I don't see any mistakes in the specific equivalences below,
there are not generalizable as suggested. For example,

  (letrec* ([x e1][y e2]) e3)

is not the same as

  (letrec* ([x e1]) (letrec* ([x e2]) e3))

Let me encourage interested parties to try out the semantics to better
understand letrec and letrec* It runs in PLT Redex, so you can see how
examples behave.

Robby

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?
>
> I find it's helpful to expand (let) expressions as lambdas to see what's
> going on. It shows up how each variable is scoped and also shows where
> execution order is important.
>
> (let) simply makes a lambda in the current scope and calls it with the given
> arguments:
>
> (let ([x 1]
>       [y 2])
>   (+ x y))
>
> is equivalent to:
>
> ((lambda (x y)
>    (+ x y))
>  1 2)
>
> So the values of x,y are evaluated *outside* the scope of the lambda. (let*)
> is a shorthand for nesting (let)s, so each value is evaluated in the scope
> of the previous enclosing (let). Here execution order is important because
> each evaluation must have access to the value of the preceeding evaluations.
>
> (let* ([x 1]
>        [y 2])
>   (+ x y))
>
> is equivalent to:
>
> (let ([x 1])
>   (let ([y 2])
>     (+ x y)))
>
> (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)))
>
> 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)))
>
>
> Hopefully you can see how if we replaced 1,2 in these examples with
> expressions, lambdas, etc, the differences in scoping affect the outcomes.
> (let*) and (letrec*) impose an evaluation order because they imply a fixed
> nesting order for scopes and thus affect the visibilty of variables within
> lambdas assigned to other variables.
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>