Meaning of letrec in Scheme/Racket

Question

So as far as I understand, the following: let, let*, letrec and letrec* are synthetics sugars used in Scheme/Racket.

Now, if I have a simple program:

(let ((x 1)
      (y 2))
     (+ x y))

It is translated into:

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

If I have:

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

It is translated into:

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

Now, for my first question, I understand the meaning of a letrec expression, which enables one to use recursion inside a let, but I do not understand how exactly it is done. What is letrec translated to?

For example, what will

(letrec ((x 1)
      (y 2))
     (+ x y)) 

be translated into?

The second question is similar about letrec* - But for letrec* I do not understand how exactly it differs from letrec? And also, what will a letrec* expression be translated into?

Answer 1

See the paper "Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme’s Recursive Binding Construct" by Oscar Waddell, Dipanwita Sarkar, and, R. Kent Dybvig.

The paper starts with a simple version and proceeds to explain a more sophisticated expansion:

https://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf

Answer 2

Since you example does not have any procedures and no real expressions I'd say you could implement it as:

(let ((x 1) (y 2))
  (+ x y)) 

But to support the intention of the form a basic implementaiton might do something like this:

(let ((x 'undefined) (y 'undefined))
  (let ((tmpx 1) (tmpy 2))
    (set! x tmpx)
    (set! y tmpy))
  (+ x y))

Now. letrec is for lambdas to be able to call themselves by the name. So imagine this:

(let ((fib (lambda (n) 
             (if (< n 2) n 
                 (+ (fib (- n 1)) (fib (- n 2)))))))
      (fib 10))

It's important to understand that this does not work and why. Transforming it into a lambda call makes it so easy to see:

((lambda (fib)
   (fib 10))
 (lambda (n) 
   (if (< n 2) n 
       (+ (fib (- n 1)) (fib (- n 2))))))

Somehow you need to evaluate the lambda after fib is created. Lets imagine we do this:

(let ((fib 'undefined))
  (set! fib (lambda (n) 
              (if (< n 2) n 
                  (+ (fib (- n 1)) (fib (- n 2))))))
  (fib 10))

Alternatively you can do it with a Z combinator to make it pure:

(let ((fib (Z (lambda (fib)
                (lambda (n) 
                  (if (< n 2) n 
                      (+ (fib (- n 1)) (fib (- n 2)))))))))  
  (fib 10))

This requires more work by the implementation, but at least you do without mutation. To make it work with several mutual recursive bindings probably takes some more work but I'm convinced its doable.

These are the only two ways to do this properly. I know clojure has a recur which imitates recursion but in reality is a a goto.

For variables that do not make closures from the letrec bindings they work as let and later more like let* since Soegaards answer about fix is backwards compatible and some has adapted it. If you write compatible code though you should not be tempted to assume this.