Go to the first, previous, next, last section, table of contents.

Variants of let: letrec and let*

Scheme provides two useful variants of let. letrec supports the creation of recursive local procedures, including mutually recursive sets of procedures. let* supports the sequenced binding of variables, where each initial value expression can use the previous bindings.

Understanding letrec

When a normal let is evaluated, the initial value expressions are evaluated before binding is done. The initial value expressions execute in the environment outside the let, and then the bindings are created and initialized with those values.

Often, we want the initial value expression for a binding to be able to create a procedure that will see the new bindings. For example, suppose we want to create a local procedure which is recursive. We might try this:

;; buggy example with (non-)tail-recursive local procedure
(define (some-procedure...)
   (let ((helper (lambda (x) 
                    ...
                    (if some-test?
                        (helper ...))))) ;; broken recursive call
     ...
     (helper ...)  ;; call to (non-)recursive local procedure
     ...))

The problem with this example is that when the let is evaluated, the lambda expression will create the helper procedure in the wrong environment--before the variable helper is bound. The resulting procedure will be scoped in the environment outside the let, not the new environment where helper is visible. When the procedure calls helper---which we had intended to be a recursive call--it will not use new binding of helper that we created. Inside the lambda body, helper will still refer to whatever binding of helper was visible before intering the let. (Very likely, that's no variable at all, and this will cause an unbound variable error.)

letrec lets us create an environment before evaluating the initial value expressions, so that the initial value computions execute inside the new environment. We can fix the problem by using a letrec instead of a let:

(define (some-procedure...)
   (letrec ((helper (lambda (x) 
                       ...
                       (if some-test?
                           (helper ...))))) ;; recursive call
     ...
     (helper ...)  ;; call to recursive local procedure
     ...))

Now the procedure helper can "see its own name," since the lambda expression is evaluated in the environment where helper is bound.

More concretely, notice that when this procedure is run, it creates an environment and closure that are linked circularly. The environment contains a binding of helper that holds a pointer to the closure created by lambda. The closure, in turn, contains a pointer back to that same environment, which is where it was created. It is this circularity that makes the procedure recursive; when it refers to helper, it fetches the value of this binding, which points to itself.

We can get the same effect using let and set!.

A letrec expression is equivalent to a let where the bindings are initialized with dummy values, and then the initial values are computed and assigned into the bindings. The above example is equivalent to:

(define (some-procedure ...)
   (let ((helper '*dummy-value*))
      (set! helper (lambda (x)
                      ...
                      (if some-test?
                          (helper ...))))) ; recursive call
     ...
     (helper ...)  ; call to recursive local procedure
     ...))

Here the let creates a binding, initializing it with an arbitary value that isn't actually used--it's just a placeholder. Then, once the let is entered and the binding is visible, a closure is created (in that environment) and a pointer to it is installed in that binding. letrec can be used when defining mutually recursive procedures, each of which can see the others' names and call them.

(define (some procedure ...)
   (letrec ((helper1 (lambda ()
                        ... (helper2) ...))
            (helper2 (lambda ()
                        ... (helper1) ...)))
     ...
     (helper1)  ; start up mutual recursion
     ...))

Notice that all letrec does is bind variables and (re-)initialize them. You can use it to define plain variables as well as procedure variables. For example, if the recursive procedures above need to reference a shared variable, you can do this:

(define (some procedure ...)
   (letrec ((helper1 (lambda ()
                        ... var1 ... (helper2) ...))
            (helper2 (lambda ()
                        ... (helper1) ... var1 ...))
            (var1 #f))
     ...
     (helper1)  ;; start up mutual recursion
     ...))

[ should come up with some simple concrete examples...]

As with let, the order of evaluation of a letrec's initial value expressions is undefined. For example, the above letrec might be compiled as though it were a let like this:

(define (some procedure ...)
   (let ((helper1 '*dummy-value*)
         (helper2 '*dummy-value*)
         (var1 '*dummy-value*))
      (set! helper2 (lambda ()
                        ... (helper1) ... var1 ...))
   
      (set! var1 #f)
      (set! helper1 (lambda ()
                       ... var1 ... (helper2) ...))
     ...
     (helper1)  ;; start up mutual recursion
     ...))

When using letrec and lambda to define local procedures, in the usual way, the order of evaluation is irrelevant--the lambda expressions can be executed in any order, because they only refer to the bindings of the letrec variables, not their values. The values are only used when the resulting procedures are called. The following would be an error, however:

(define (some procedure ...)
   (letrec ((helper1 ...)
            (helper2 ...)
            (var1 (list helper1 helper2)))
      ...
      ((car (var1 helper1)))  ; start up mutual recursion
      ...))

Here the initialization of var1 depends on the values of helper1 and helper2, which may not have been computed yet.

Using letrec and lambda to Implement Modules

Standard Scheme does not have a module system, but letrec and lambda are powerful enough to implement modules in portable Scheme.

Suppose we would like to define a module that encapsulates a set of procedures and variables, but only exports a subset of those procedures.

We can represent the module as a letrec environment which exports an association list of of procedures.

Here we'll create a module called foo, which defines four procedures and two variables, and exports two of the procedures, foo and bar.

(define foo-module
   ;; create a letrec environment with internal definitions
   ;; of some variables and procedures
   (letrec ((private-proc1 (lambda (...) ...))
            (private-proc2 (lambda (...) ...))
            (private-var1 ...)
            (private-var2 ...)
            (foo (lambda (...) ...))
            (bar (lambda (...) ...)))
      ;; return an association list of "exported" closures
      (list (list 'foo foo)
            (list 'bar bar))))

The letrec expression will create an environment, and within that environment it will evaluate the initial value expressions to initialize the bindings. All of the procedures in the letrec can see each other's names, and call each other freely. Procedures outside the letrec cannot.

The only procedures that can be called from outside the letrec are foo and bar, which are returned from the letrec in an association list. We've saved this list in the binding of foo-module, so that we can look those procedures up and call them.

We can clean this up a little by providing an accessor function that will extract a single procedure from a module, by using assq to find the appropriate closure:

(define (module-get mod name)
   (cadr (assq mod name)))

To import a procedure and give it a name in another environment, we can do this:

(define foo (module-get foo-module 'foo))

If we want to, we can give it a different name in the environment we're "importing" it into.

(define quux (module-get foo-module 'foo))

This lets us rename a procedure imported from a module, to avoid naming conflicts. quux is exactly the same procedure as foo, but by a different name in a different scope. When we call it, it will execute in the environment where it was defined, namely the "private" environment of the module we created with letrec.

let*

For situations where the order of initialization is important, Scheme provides a variant of let called let*.

Suppose we tried the following using let:

(define (foo epsilon)
   (let ((a 0)
         (upper (+ a epsilon))
         (lower (- a epsilon)))
     ...))

This will not do what we probably meant, because the initial values of upper and lower will be computed before a is bound. We could fix this by using nested let's, to force evaluation and binding to happen in the desired order:

(define (foo epsilon)
   (let ((a 0))
      (let ((lower (- a epsilon))
            (upper (+ a epsilon)))
     ...))

This ensures that a is bound before we evaluate the initial value expressions for upper and lower.

Scheme provides let* to avoid needing lots of nested lets when initilizing a series of bindings, each of which may depend ont the previous ones, e.g.,

(define (bar x y)
   (let* ((diff (- x y))
          (diff-squared (* diff diff))
          (diff-cubed (* diff-squared diff)))
     ...)

is exactly equivalent to

(define (bar x y)
   (let ((diff (- x y)))
      (let ((diff-squared (* diff diff)))
         (let ((diff-cubed (* diff-squared diff)))
            ...))))

Iteration Constructs

Named let

Named let is a general and flexible iteration construct that is really just syntactic sugar for a letrec and one or more lambda's. It looks like a let, but it's usually used as a loop.

Named let implements iteration as recursion. If you use it in normal ways, you write loops that act as tail-recursive procedures. You can also use it to write "loops" that aren't tail recursive, but that's uncommon.

Named let binds loop variables, and executes the loop body. Anywhere in the loop body, you can call a procedure to iterate the loop.

Here's an example loop, which prints out the integers from 0 to 9:

(let loop ((i 0))
   (display i)
   (if (< i 10)
       (loop (+ i 1))))

Here we've written a loop and given it an identifier, loop; that's just a name we chose for this particular loop--we could have used any identifier.

This loop binds the loop variable i, giving it the intial value 0. Then it enters the body of the loop, which prints out i using display, and evaluates the if expression. If the if condition returns a true value, it evaluates the expression (loop (+ i 1)), which iterates the loop. This looks like a call to a procedure named loop, which iterates the loop. The argument passed is the new value of the loop variable for the next iteration.

The reason that the expression that iterates a loop looks like a procedure call is that it is a procedure call. A named let is exactly equivalent to a letrec that defines a named procedure, whose body is the body of the named let, and then calls that procedure to start the recursion. When you write a "loop" with named let, you're really writing a recursive procedure and a call to that procedure. The loop variable(s) are really arguments to the procedure, and the initial values of the loop variables are just the first argument passed to the procedure to start the recursion.

The above example is exactly equivalent to:

(letrec ((loop (lambda (i)      ; define a recursive
                  (display i)   ; procedure whose body
                  (if (< i 10)  ; is the loop body
                      (loop (+ i 1))))))
   (loop 0)) ;; start the recursion with 0 as arg i

When you supply the name of a named let, you're really supplying the name of a letrec variable that will name a procedure. When you supply the body of the named let, you're really supplying the body of the named procedure. When it iterates the loop, it is calling itself recursively, passing the new invocation the new value of the loop variable as an argument.

To start off the loop, named let passes this procedure the initial value expression for the loop variable.

We can provide any expression we want to compute the new value of the loop variable--we don't have to increment it by one. We can also provide any test we want to decide whether to iterate the loop.

For example, here's procedure which uses a loop to search a list of alternating key/value pairs. (This is not an association list, but a linear list of alternating keys and values, called a property list.) It iterates through the list two elements at a time. If it finds an odd-numbered element that's eq? to what it's looking for, it returns the next (even-numbered) element; otherwise, it continues through the loop.

(define (property-list-search lis target)
   (let loop ((l lis))
      (cond ((null? l)
             #f)
            ((eq? (car l) target)
             (cadr l))
            (#t
             (loop (cddr l))))))

[ same as: ]

(define (property-list-search lis target)
   (letrec ((loop (lambda (l)
                     (cond ((null? l)
                            #f
                           ((eq? (car l) target)
                            (cadr l))
                           (#t
                            (loop (cddr l))))))))
      (loop lis)))   ;; start the recursion

The reason we supply a name for a loop in a named let is so that we can have nested loops with different names, and we can iterate any of the loops by calling it by name.

For example, suppose we want to have a nested pair of loops, but want to be able to bail out of the iteration of the inner loop, and go directly to the next iteration of the outer loop. We can do this:

[ need example here ]

(let outer-loop ((i ...))
   (let inner-loop ((j ...))
      (if (should-abort-inner-loop)
          (outer-loop ...))  ;; go directly to next iteration of outer loop
      ...  ; do normal inner loop action
      ...(inner-loop ...)  ;; iterate inner loop normally
   ...
   ... (outer-loop ...))   ; iterate outer loop normally

Some things to notice about Scheme loops:

Programming with Procedures and Environments

Exercises


Go to the first, previous, next, last section, table of contents.