Recursive Local Procedures and letrec

Using let and lambda to define local procedures will often work, but generally we use letrec rather than let, because it supports recursive local procedures. (That's why it's called letrec---it means let with recursive definitions.)

Suppose we tried to use let and lambda to define a recursive local procedure:

(define (foo x)
   (let ((local-proc (lambda (y)
                        ...
                        (local-proc ...)   ; recursive call?  No.
                        ...))) 
      ...
      (local-proc x)
      ...)

The problem with this example is that what appears to be a recursive call to local-proc from inside local-proc actually isn't. Remember that let computes the initial values of variables, then initializes all of the variables' storage, and only then do any of the bindings become visible--when we enter the body of the let. In the example above, that means that the local variable local-proc isn't visible to the lambda expression. The procedure created by lambda will not see its own name--the name local-proc in the body of the procedure will refer to whatever binding of local-proc exists in the enclosing environment, if there is one.

A block structure diagram may make this clearer:

(define (foo x)
   (let ((local-proc (lambda (y)
                      +--------------------------+
                      | ...                scope |
                      | (local-proc ...)   of y  | 
                      | ...                      | )))
                      +--------------------------+
    +------------------------------------------+
    | ...                         scope of     |
    | (local-proc x)              local-proc   |
    | ...                                      | )
    +------------------------------------------+

Unlike let, letrec makes new bindings visible before they're initialized. Storage is allocated, and the meanings of names are changed to refer to the new local variable bindings, and then the initial values of those variables are computed and the variables are initialized.

For most purposes, this wouldn't make any sense at all--why would you want variable bindings to be visible before they have had their initial values installed? For local procedure definitions, however, it makes perfect sense--we want to use lambda to create a procedure that can operate on the variables later, when it's called.

lambda creates a procedure that will start executing in the scope where the lambda expression is evaluated, so we need to make the bindings visible before we evaluate the lambda expression.

If we use letrec in our example, instead of let, it works. The procedure local-proc can see the variable local-proc, so it can call itself by its name.

The block structure diagram looks like this:

(define (foo x)         +-----------------------------------+
   (letrec ((local-proc | (lambda (y)                       |
                        |  +--------------------------+     |
                        |  | ...                scope |     |
                        |  | (local-proc ...)   of y  |     |
                        |  | ...                      | ))) |
                        |  +--------------------------+     |
    +-------------------+                                   |
    | ...                                  scope of         |
    | (local-proc x)                       local-proc       |
    | ...)                                                  |
    +-------------------------------------------------------+

The recursive call to local-proc will work, because the call is inside the box that corresponds to the scope of the variable local-proc.

letrec works for multiple mutually recursive local procedures, too. You can define several local procedures that can call each other, like this:

(define (my-proc)
   (letrec ((local-proc-1 (lambda ()
                             ...
                             (local-proc-2)
                             ...))
            (local-proc-2 (lambda ()
                             ...
                             (local-proc-1)
                             ...)))
      (local-proc-1))) ; start off mutual recursion by calling local-proc-1

A block structure diagram shows that each local procedure definition can see the bindings of the other's names:

(define (my-proc)
             +--------------------------------------------------------+
   (letrec ( | (local-proc-1 (lambda ()        scope of local-proc-1  |
             |                ...                and local-proc-2     |
             |                (local-proc-2)                          |
             |                ...))                                   |
             | (local-proc-2 (lambda ()                               |
             |               ...                                      |
             |               (local-proc-1)                           |
    +--------+               ...)))                                   |
    | (local-proc-1)                                                  | ))
    +-----------------------------------------------------------------+

You can also define plain variables while you're at it, in the same letrec, but letrec is mostly interesting for defining local procedures.

When the initial value of a letrec variable is not a procedure, you must be careful that the expression does not depend on the values of any of the other letrec variables. Like let, the order of initialization of the variables is undefined.

For example, the following is illegal:

(letrec ((x 2)
         (y (+ x x)))
   ...)

In this case, the attempt to compute (+ x x) may fail, because the value of x may not have been computed yet. For this example, let* would do the job--the second initialization expression needs to see the result of the first, but not vice versa:

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

Be sure you understand why this is illegal, but the lambda expressions in the earlier examples are not.

When we create recursive procedures using letrec and lambda, the lambda expressions can be evaluated without actually using the values stored in the bindings they reference. We are creating procedures that will use the values in the bindings when those procedures are called, but just creating the procedure objects themselves doesn't require the bindings to have values yet. It does require that the bindings exist, because each lambda expression creates a procedure that "captures" the currently visible bindings--the procedure remembers what environment it was created in.