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

From: Jos Koot (jos.koot at telefonica.net)
Date: Sat Feb 14 09:33:07 EST 2009

----- Original Message ----- 
From: <hendrik at topoi.pooq.com>
> Might there be constructions like
> (letrec ([f (cons (lambda() foo) (lambda() bar))]
>         [foo (lambda() ...f...)]
>         [bar ...]
>        )
> )
> -- hendrik

Yes. Letrec (in R6RS) assumes that each value to be bound to a variable can 
be computed without reference to the value of any of the variables. However, 
the bindings are already available (although possibly without values being 
stored yet) Now consider:

 ((odd? (lambda (n) (and (not (zero? n)) (even? (- n 1))))
  (even? (lambda (n) (or (zero? n) (odd? (- n 1))))))
 (even? 5))

The two values to be bound are the values of the two lambda forms. The first 
one requires the binding (but not the value) of the second one and 

Compare this with:

 ((x 1) (y (add1 x)))
 (list x y))

R6RS does not specify the behaviour of this letrec form. It may be the case 
that (add1 x) is computed and hence the value of x is needed before x has 
received its value. That's why there is also letrec*

 ((x 1) (y (+ x 1))) ; values computed and stored from left to right.
 (list x y)) ; correct --> (1 2)

With this letrec* the value to be assigned to y may refer to the value of x 
(but not reversely!)

We can rewrite let, let*, letrec and letrec* as follows:

(let ((var value-expr) ...) definition ... body-expr ...) ==>
((lambda (var ...) definition ... body-expr ...) value-expr ...)

(let* ((var1 value-expr1) (var1 value-expr1)) definition ... body-expr ...) 
((lambda (var1)
  ((lambda (var2) definition ... body-expr ...)

(letrec ((var value-expr) ...) definition ... body-expr ...) ==>
(let ((var undefined) ...)
 (let ((temp value-expr) ...) in arbitrary order
  (set! var temp) ... in arbitrary order
  (let ( ) definition ... body-expr ...)))

(letrec* ((var value-expr) ...) definition ... body-expr ...) ==>
(let ((var undefined) ...)
  (set! var value-expr) ... from left tio right
  (let ( ) definition ... body-expr ...))


> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme 

Posted on the users mailing list.