CSC 153: Computer Science Fundamentals | Grinnell College | Spring, 2005 |
Laboratory Exercise Reading | ||
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.
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.
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.
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. |