Confused by the difference between let and let* in Scheme

Let is parallel, (kind of; see below) let* is sequential. Let translates as

((lambda(a b c)  ... body ...)
  a-value
  b-value
  c-value)

but let* as

((lambda(a)
    ((lambda(b)
       ((lambda(c) ... body ...)
        c-value))
     b-value))
  a-value)

and is thus creating nested scope blocks where b-value expression can refer to a, and c-value expression can refer to both b and a. a-value belongs to the outer scope. This is also equivalent to

(let ((a a-value))
  (let ((b b-value))
    (let ((c c-value))
      ... body ... )))

There is also letrec, allowing for recursive bindings, where all variables and expressions belong to one shared scope and can refer to each other (with some caveats pertaining to initialization). It is equivalent either to

(let ((a *undefined*) (b *undefined*) (c *undefined*))
  (set! a a-value)
  (set! b b-value)
  (set! c c-value)
  ... body ... )

(in Racket, also available as letrec* in Scheme, since R6RS), or to

(let ((a *undefined*) (b *undefined*) (c *undefined*))
  (let ((_x_ a-value) (_y_ b-value) (_z_ c-value))   ; unique identifiers
    (set! a _x_)
    (set! b _y_)
    (set! c _z_)
    ... body ... ))

(in Scheme).

update: let does not actually evaluate its value-expressions in parallel, it’s just that they are all evaluated in the same initial environment where the let form appears. This is also clear from the lambda-based translation: first the value expressions are evaluated each in the same, outer environment, and the resulting values are collected, and only then new locations are created for each id and the values are put each in its location. We can still see the sequentiality if one of value-expressions mutates a storage (i.e. data, like a list or a struct) accessed by a subsequent one.

Leave a Comment