Search code examples
lambdaschemelispracketlet

Confused by let to lambda conversion


I am currently, going through this great article on Y-combinator by Mike Vanier. Along the explanation the following line is dropped:

It turns out that any let expression can be converted into an equivalent lambda expression using this equation:

(let ((x <expr1>)) <expr2>) ==> ((lambda (x) <expr2>) <expr1>)

The article illustrates this statement by converting:

(define (part-factorial self)
  (let ((f (self self)))
    (lambda (n)
      (if (= n 0)
        1
        (* n (f (- n 1)))))))

to:

(define (part-factorial self)
  ((lambda (f)
    (lambda (n)
      (if (= n 0)
        1
        (* n (f (- n 1))))))
  (self self)))

Now, I understand how and why two code snippets above are identical, though I can't get my head around the fact that general equation for converting let to lambda is:

(let ((x <expr1>)) <expr2>)
==> ((lambda (x) <expr2>) <expr1>)

I'd appreciate the elaborate explanation.


Solution

  • let lets you open a new environment in which variables are available. In programming language terms we say it "opens a new frame".

    When you write (let ((x 42)) <body>) you create a frame in which x is available inside <body>, and assign it the value 42.

    Well, there is another tool that lets you open new frames. In fact, it's usually the basic brick with which you can build more abstract constructs: it is called lambda.

    lambda opens a new frame in which its arguments are available to its body. When you write (lambda (x) <body>) you make x available to the <body> of the function.

    The only difference between lambda and let is that let immediately assigns a value to x, while lambda awaits the value as an argument.

    Therefore, if you want to wrap a <body> with a directly assigned value using lambda, you just have to pass that value!

    ((lambda (x) <body>) 42)
    

    Which makes it exactly equivalent to:

    (let ((x 42)) <body>)