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

Question

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

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

Answer 1

This is let expression:

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

It is equivalent to the following lambda application, noting that here the variables can be evaluated in any order (strict order is not applied from left to right), and the definition of one variable cannot refer to variables before it

 ((lambda (xy) e) v1 v2) 

On the other hand, this is the expression let* :

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

It can be converted to a series of nested lambda s, so as to ensure that the variables are evaluated in the same order that was used to define them, and those that were defined at the beginning can be referenced in all of the following 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))) (+ xy)) 

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

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

Finally, here are two great online books for exploring the Scheme:

• How to develop a program
• The structure and interpretation of computer programs

Answer 2

let* are just nested instances of let . For example,

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

coincides with

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

Does this help with understanding let* ? let*

Update: The OP asks (in the comments for the Óscar post) how let* differs from let . Here is an example: first, use let* :

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

This returns 23 (10 + 13). The value of internal x , and the value of external x obscured.

Now let's see 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 internal x value is not used in calculating the y value; it acts only inside the body of let .

Answer 3

What let* expands to

It:

 (let* ([a 1] [b (* 2 a)]) (cons ab)) 

expands to this:

 ((lambda (a) ((lambda (b) (cons ab)) (* 2 a))) 1) 

Here is a good way to think about what lambda means in the Scheme (good, because it is both simple and accurate): it is both a label for a place in the program and an area for related variables. In Scheme, a label for a place in a program (for example, that you can goto in other languages ​​or branches for a machine language) always has an area for related variables. You can "settle" in the program by adding values ​​to bind to variables bound within your area.

The let schema is a way of saying: "I want to create an area in which these variables are bound, but I don't want to wait until I say their values ​​later. I want to specify their values ​​right here." So let is just a macro that makes a lambda and then provides values ​​right there.

If you want the values ​​of one of the variables to be an expression that uses another variable, for example, as b is expressed in terms of a above, then b must be defined within the scope of a . Therefore, the let* macro, which defines each next variable in the scope that includes the previous variable. Since we have a bunch of nested areas, they are implemented by a bunch of nested lambda.

Macro

Here's how to talk about how to rewrite let* as a collection of lambdas nested applications and functions:

 (define-syntax let* (syntax-rules () [(__ () body ...) (begin body ...)] [(__ ([ve] [v* e*] ...) body ...) ((lambda (v) (let* ([v* e*] ...) body ...)) e)])) (let* ([a 1] [b (* 2 a)]) (cons ab)) => (1 . 2) 

In Chez Scheme, you can play with this in REPL by typing (expand '(let* ([a 1] [b (* 2 a)]) (cons ab)) and seeing what happens. This is what happens when I try :

 (let ([#:a 1]) (let ([#:b (#2%* 2 #:a)]) (#2%cons #:a #:b)))