Local Bindings

Abstract

So far we've seen three ways in which a value can be associated with a variable in Scheme:

• Some variables, such as the names of built-in procedures, are predefined. When Chez Scheme starts up, these variables (cons and quotient, for example) are already bound to the procedures they denote.

• The programmer can introduce a new binding by means of a definition. A definition may introduce a new name for a previously computed value, or it may give a name to a newly constructed value.

• When a programmer-defined procedure is called, the parameters of the procedure are bound to the values of the corresponding arguments in the procedure call. Unlike the other two kinds of bindings, parameter bindings are local -- they apply only within the body of the procedure. Scheme discards these bindings when it leaves the procedure and returns to the point at which it was called.

• Let associates variables with values in parallel.
• Let* associates variables with values sequentially.
• Letrec associates variables with values in the context of recursion.

Let

A let-expression in Scheme is an alternative way to create local bindings. A let-expression contains a binding list and a body. The body can be any expression, or sequence of expressions, to be evaluated with the help of the local variable bindings. The binding list is a pair of parentheses enclosing zero or more binding specifications; a binding specification, in turn, is a pair of parentheses enclosing a variable and an expression. Here's an example of a binding list:

((next (car source)) (char-list '()))

This binding list contains two binding specifications -- one in which the value of the expression (car source) is bound to the symbol next, and the other in which the empty list is bound to the symbol char-list. Notice that binding lists and binding specifications are not procedure calls; their role in a let-expression is structural.

When a let-expression is evaluated, the first thing that happens is that the expressions in all of its binding specifications are evaluated and collected. Then the symbols in the binding specifications are bound to those values. Next, the expressions making up the body of the let-expression are evaluated, in order; the value of the last expression in the body becomes the value of the entire let-expression. Finally, the local bindings of the variables are canceled. (Variables that were unbound before the let-expression become unbound again; variables that had different bindings before the let-expression resume those earlier bindings.)

Using a let-expression often simplifies an expression that contains two or more occurrences of the same subexpression. The programmer can compute the value of the subexpression just once, bind a variable to it, and then use that variable whenever the value is needed again. Sometimes this speeds things up by avoiding redundancies; in other cases, there is little difference in speed, but the code may be a little clearer. For instance,consider the following remove-all procedure that deletes all occurrences of an item from a list:

(define remove-all
  (lambda (item ls)
  ;Pre-condition:  ls is a list
  ;Post-condition:  removes all occurrences of item from ls
    (if (null? ls)
        '()
        (let ((first-element (car ls))
              (rest-of-result (remove-all item (cdr ls))))
          (cond ((equal? first-element item) rest-of-result)
                ((pair? first-element)
                 (cons (remove-all item first-element) rest-of-result))
                (else (cons first-element rest-of-result)))))))

In this procedure, the let allows us to evaluate (car ls) and (remove-all item (cdr ls)) just once. Giving each value a name also makes it a little easier to understand what the three cond-clauses are doing.

It is possible to nest one let-expression inside another, using the variables from an outer list inside the next:

(let ((a 1)
      (b 2)
      (c 3))
  (let ((sum (+ a b c)))
    (* sum sum)
  )
)

Here values are bound to variables a, b and c in the first (outer) let-expression, and these values are used in computing a value for sum in the second (inner) let-expression.

Let*

Since it is possible to nest one let-expression inside another, one might be tempted to try to combine the binding lists for the nested let-expressions, thus:

;; Combining the binding lists doesn't work!
;;
(let ((sum (+ 8 3 4 2 7))
      (mean (/ sum 5)))
  (* mean mean))

This wouldn't work (try it and see!), because, within a let-expression, all of the expressions are evaluated before any of the variables are bound. Specifically, Scheme will try to evaluate both (+ 8 3 4 2 7) and (/ sum 5) before binding either of the variables sum and mean; since (/ sum 5) can't be computed until sum has a value, an error occurs. You have to think of the local bindings coming into existence simultaneously rather than one at a time.

Because one often needs sequential rather than simultaneous binding, Scheme provides a variant of the let-expression that rearranges the order of events: If one writes let* rather than let, each binding specification in the binding list is completely processed before the next one is taken up:

;; Using let* instead of let works!
;;
(let* ((sum (+ 8 3 4 2 7))
       (mean (/ sum 5)))
  (* mean mean))

The star in the symbol let* has nothing to do with multiplication; just think of it as an oddly shaped letter.

One can use a let- or let*-expression to create a local name for a procedure:

(define hypotenuse-of-right-triangle
  (lambda (first-leg second-leg)
  ;Pre-condition:  first-leg and second-leg are non-negative numbers
  ;Post-condition:  returns hypotenuse of right triangle with given legs
    (let ((square (lambda (n)
                    (* n n))))
      (sqrt (+ (square first-leg) (square second-leg))))))

Regardless of whether square is defined outside this procedure, the local binding gives it the appropriate meaning in the body of the let-expression.

It is possible for a let-expression to bind a variable to a procedure:

(let ((square (lambda (n) (* n n))))
  (square 12))

===> 144

Like any other binding that is introduced in a let-expression, this binding is local. Within the body of the let-expression, it supersedes any previous binding of the same variable, but as soon as the value of the let-expression has been computed, the local binding evaporates.

Letrec

It is not possible to bind a variable to a recursively defined procedure with either let or let*:

(let ((countdown (lambda (n)
                   (if (zero? n)
                       '()
                       (cons n (countdown (- n 1)))))))
  (countdown 10))

===> Error: variable countdown is not bound.

The difficulty is that when the lambda-expression is evaluated, the variable countdown has not yet been bound, so the value of the lambda-expression is a procedure that includes an unbound variable. Binding this procedure value to the variable countdown creates a new environment, but does not affect the behavior of procedures that were constructed in the old environment. So, when the body of the let-expression invokes this procedure, we get the unbound-variable error. Even under let* the lambda-expression would be completely evaluated before the binding is established.

What we need is some variant of let that binds the variable to some kind of a place holder and adds the binding to the environment first, then computes the value of the lambda-expression in the new environment, and then finally substitutes that value for the place holder. This will work in Scheme, so long as the procedure is not actually invoked until we get into the body of the expression. The keyword associated with this "recursive binding" variant of let is letrec:

(letrec ((countdown (lambda (n)
                      (if (zero? n)
                          '()
                          (cons n (countdown (- n 1)))))))
  (countdown 10))

===> (10 9 8 7 6 5 4 3 2 1)

A letrec-expression constructs all of its place holder bindings simultaneously (in effect), then evaluates all of the lambda-expressions simultaneously, and finally replaces all of the place holders simultaneously. This makes it possible to include binding specifications for mutually recursive procedures in the same binding list:

(letrec ((up-sum
          (lambda (ls)
            (if (null? ls)
                0
                (+ (down-sum (cdr ls)) (car ls)))))
         (down-sum
          (lambda (ls)
            (if (null? ls)
                0
                (- (up-sum (cdr ls)) (car ls))))))
  (up-sum '(1 23 6 12 7))
)
===> -21

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/readings/reading-local-bindings.shtml

created February 26, 1997 last revised February 1, 2005
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.