How to rewrite `let*` in terms of `lambda`?

Question

I understand how (let ((x v1) (y v2)) e) can be rewritten as ((lambda (x y) e) v1 v2). But I'm not too familiar with let*.

How can we rewrite (let* ((x v1) (y v2) (z v3)) e) in terms of lambda and function applications?

Answer 1

This let expression:

(let ((x v1)
      (y v2))
  e)

Is equivalent to the following lambda application, noticing that in here the variables can be evaluated in any order (no strict left-to-right order is enforced) and the definition of one variable can not reference the variables before it:

((lambda (x y)
   e)
 v1 v2)

On the other hand, this let* expression:

(let* ((x v1)
       (y v2)
       (z v3))
  e)

Can be transformed into a series of nested lambdas, in a way that ensures that the variables are evaluated in the same order that was used to define them, and the ones defined first can be referenced in all subsequent definitions:

((lambda (x)
   ((lambda (y)
      ((lambda (z)
         e)
       v3))
    v2))
 v1)

Another example: this code will only work if we use the second transformation:

(let* ((x 1)
       (y (+ x 1)))
  (+ x y))

As you can see, the definition of y references x, only in this way will it work:

((lambda (x)
   ((lambda (y)
      (+ x y))
    (+ x 1)))
 1)

Finally, here are two great online books for learning Scheme:

• How to Design Programs
• Structure and Interpretation of Computer Programs

Answer 2

let* is simply nested let instances. For example,

(let* ((x v1)
       (y v2)
       (z v3))
  e)

is the same as

(let ((x v1))
  (let ((y v2))
    (let ((z v3))
      e)))

Does that help with your understanding of let*? :-)

Update: The OP is asking (in comments to Óscar's post) how let* is different from let. Here is an example: first, let's use let*:

(let ((x 42))
  (let* ((x 10)
         (y (+ x 13)))
    y))

This returns 23 (10 + 13). The value of the inner x is used, and the value of the outer x is shadowed.

Now, let's look at what happens if we used let instead of let*:

(let ((x 42))
  (let ((x 10)
        (y (+ x 13)))
    y))

This returns 55 (42 + 13). The value of the inner x is not used in computing the value of y; it only takes effect inside the body of the let.