Summary: Algorithm designers regularly find it useful to name the values their algorithms process. We consider why and how to name new values that are only available within a procedure.
When writing programs and algorithms, it is useful to name values we compute along the way. For example, in an algorithm that, given a color, computes a grey color with the same brightness as the original color, it is useful to name that brightness. When we associate a name with a value, we say that we bind that name to the value.
So far we've seen three ways in which names are bound to values in Scheme.
quotient, are predefined. When the Scheme interpreter starts up, these names are already bound to the procedures they denote.
As you develop more and longer procedures, you will find that there are many times you want to create local names for values that are not parameters. We will consider such names in this reading.
You may have already noted that there are times when it seems that you repeat work that should only have to be done once. For example, consider the problem of computing a grey that has the same brightness as a given color. We can certainly write the following:
;;; Procedure: ;;; rgb-greyscale ;;; Parameters: ;;; color, an RGB color ;;; Purpose: ;;; Compute a greyscale version of color. ;;; Produces: ;;; grey, an RGB color ;;; Postconditions: ;;; grey is likely to be interpreted as the same brightness as color. (define rgb-greyscale (lambda (color) (rgb-new (+ (* 0.30 (rgb-red color)) (* 0.59 (rgb-green color)) (* 0.11 (rgb-blue color))) (+ (* 0.30 (rgb-red color)) (* 0.59 (rgb-green color)) (* 0.11 (rgb-blue color))) (+ (* 0.30 (rgb-red color)) (* 0.59 (rgb-green color)) (* 0.11 (rgb-blue color))))))
However, that code has some difficulties. First, it's a bit hard to read. Why are we using those weird formulae? Are the three formulae the same? If not, why not? Second, it's hard to correct the code. If we change our formula, we'll need to change it in three places, since the formula is repeated three times. Finally, this repetition of code will lead to inefficiencies. Why should we compute the same product and the same sum three times? If we rely only on the Scheme we know so far, we can solve the first two problems by writing a separate procedure to compute the grey component.
;;; Procedure: ;;; rgb-brightness255 ;;; Parameters: ;;; color, an RGB color ;;; Purpose: ;;; Computes the brightness of color on a 0 (dark) to 255 (bright) scale. ;;; Produces: ;;; brightness, an integer ;;; Preconditions: ;;; color is a valid RGB color. That is, each component is between ;;; 0 and 255, inclusive. ;;; Postconditions: ;;; If color1 is likely to be perceived as brighter than color2, ;;; then (rgb-brightness255 color1) > (rgb-brightness255 color2). (define rgb-brightness255 (lambda (color) (+ (* .30 (rgb-red color)) (* .59 (rgb-green color)) (* .11 (rgb-blue color)))))
Once we've defined
rgb-brightness255, all we need
to do is call it three times to build a single shade of grey.
(define rgb-greyscale (lambda (color) (rgb-new (rgb-brightness255 color) (rgb-brightness255 color) (rgb-brightness255 color))))
This change certainly makes it easier to read
rgb-greyscale. In addition, the procedure easier
to update. If we decide to compute brightness differently, such as
by averaging the three components, we only need to change one piece of code.
(define rgb-brightness255 (lambda (color) (/ (+ (rgb-red color) (rgb-green color) (rgb-blue color)) 3)))
Similarly, if we want to ensure that the value produced by
rgb-brightness255 is an exact integer (the
values we expect for the components of RGB colors), we need only
make one change, rather than three.
(define rgb-brightness255 (lambda (color) (inexact->exact (round (+ (* .30 (rgb-red color)) (* .59 (rgb-green color)) (* .11 (rgb-blue color)))))))
Although we have solved the first two deficiencies of the original code, we are still repeating work. Can we avoid the repetition of work? Certainly, we can write a procedure that makes a shade of grey from a single brightness value.
;;; Procedure: ;;; rgb-grey ;;; Parameters: ;;; level, an integer ;;; Purpose: ;;; Produces a shade of grey. ;;; Produces: ;;; grey, a color. ;;; Preconditions: ;;; level is an integer between 0 and 255, inclusive. ;;; Postconditions: ;;; Each component of grey is level . (define rgb-grey (lambda (level) (rgb-new level level level)))
Now, we can simply write
(define rgb-greyscale (lambda (color) (rgb-grey (rgb-brightness255 color))))
But getting to this version took a lot of extra work. We had to write (and document!) two procedures that we may never use again.
let expressions as an alternative way
to create local bindings. A
let-expression contains a
binding list and a body.
The body can be any expression, or any sequence of expressions, to be
evaluated with the help of the local name bindings. The binding
list takes the form of a parentheses enclosing zero or more
binding expressions of the form
That precise definition may have been a bit confusing, so
here's the general form of a
exp2) ... (
When Scheme encounters a
let-expression, it begins by
evaluating all of the expressions inside its binding specifications. Then
the names in the binding specifications are bound to those values. Next,
the expressions making up the body of the
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 names are cancelled. (Names that were unbound before the
let-expression become unbound again; names that had different
bindings before the
let-expression resume those earlier
Here's how we'd solve the earlier problem with
let and without
(define rgb-greyscale (lambda (color) (let ((component (+ (* 0.30 (rgb-red color)) (* 0.59 (rgb-green color)) (* 0.11 (rgb-blue color))))) (rgb-new component component component))))
Again, if we want to make the change to the computation of the brightness component (e.g., by rounding and making it exact), we need change our code only once.
(define rgb-greyscale (lambda (color) (let ((component (inexact->exact (round (+ (* 0.30 (rgb-red color)) (* 0.59 (rgb-green color)) (* 0.11 (rgb-blue color))))))) (rgb-new component component component))))
Here's another example of a binding list, taken from a
let-expression in a real Scheme program:
(let ((black (rgb-new 0 0 0)) (complement (rgb-complement rgb))) ...)
This binding list contains two binding specifications -- one in which the
value of the expression
(rgb-new 0 0 0) is bound to the name
black, and the other in which the complement of
rgb (presumably, an RGB color) is bound to the name
Note that even though binding lists and binding specifications start
with parentheses, the are not procedure calls;
their role in a
let-expression simply to give names to
certain values while the body of the expression is being evaluated.
The outer parentheses in a binding list are “structural”
-- they are there to group the pieces of the binding list together.
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 name to it, and then use that name whenever the value
is needed again. Sometimes this speeds things up by avoiding such
redundancies as the recomputation of values. In other cases, there
is little difference in speed, but the code may be a little clearer.
You may have missed it, but there are a few subtle and
important issues with the the use of
let rather than
define to name values and procedures. One difference
has to do with the availability (or “scope”) of the
name. Values named by
define are available essentially
everywhere in your program. In contrast, values
let are available only within the let expression.
(In case you were wondering, the term “scope” has nothing
to do with the mouthwash.)
In addition, local variables (given by
let) and global
variables (given by
define) affect previous uses of
the name differently (or at least appear to). When we do a new
define, we permanently replace the old value
associated with the name. That value is no longer accessible.
In contrast, when we use
let to override the value
associated with a name, as soon as the
is finished, the previous association is restored.
Finally, there's a benefit to using
let instead of
define according to the principle of “information
hiding”. Evidence suggests that programs work better if the
various pieces do not access values relevant primarily to the internal
workings of other pieces. If you use
define for your
names, they are accessible (and therefore changable) everywhere.
Hence, you enforce this separation by policy or obscurity. In
contrast, if you use
let to define your local names,
these names are completely inaccessible to other pieces of code.
We return to this issue in our discussion of the ordering of
Sometimes we may want to name a number of interrelated things.
For example, suppose we wanted to square the average of a list
of numbers (well, it's something that people do sometimes). Since
computing the average involves summing values, we may want to name two
different things: the total and the average (mean). We can nest one
let-expression inside another to name both things.
(let ((total (+ (rgb-red color) (rgb-green color) (rgb-blue color)))) (let ((mean (/ total 3))) (* mean mean)))
One might be tempted to try to combine the binding lists for the nested
; Combining the binding lists doesn't work!
(let ((total (+ (rgb-red color) (rgb-green color) (rgb-blue color))) (mean (/ total 3))) (* mean mean))
This wouldn't work (try it and see!), and it's important to
understand why not. The problem is that, within one binding list,
all of the expressions are evaluated before
any of the names are bound. Specifically, Scheme
will try to evaluate both
(+ 8 3 4 2 7) and
total 5) before binding either of the names
(/ total 5) can't be computed
total 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* ((total (+ (rgb-red color) (rgb-green color) (rgb-blue color))) (mean (/ total 3))) (* mean mean))
The star in the keyword
let* has nothing to do
with multiplication. Just think of it as an oddly shaped letter.
It means “do things in sequence, rather than all at once”.
While someone probably knows the reason to use
* for that
meaning, the authors of this text do not.
In the examples above, we've tended to do the naming within the body of the procedure. That is, we write
params) (let (...)
However, Scheme also lets us choose an alternate ordering. We can
instead put the
let before (outside of) the
proc(let (...) (lambda (
Why would we ever choose to do so? Let us consider an example. Suppose that we regularly need to convert years to seconds. (SamR says, “When you have sons between the ages of 5 and 12, you'll understand.”) You might begin with
(define years-to-seconds (lambda (years) (return (* years 365.24 24 60 60))))
This produce does correctly compute the desired result. However, it is a bit hard to read. For clarity, you might want to name some of the values.
(define years-to-seconds (lambda (years) (let* ((days-per-year 365.24) (hours-per-day 24) (minutes-per-hour 60) (seconds-per-minute 60) (seconds-per-year (* days-per-year hours-per-day minutes-per-hour seconds-per-minute))) (* years seconds-per-year))))
We have clarified the code, although we have also lengthened it a bit.
However, as we noted before, a second goal of naming is to avoid
recomputation of values. Unfortunately, even though the number of
seconds per year never changes, we compute it every
time that someone calls
years-to-seconds. How can we
avoid this recomputation? One strategy is to move the bindings to
(define days-per-year 365.24) (define hours-per-day 24) (define minutes-per-hour 60) (define seconds-per-minute 60) (define seconds-per-year (* days-per-year hours-per-day minutes-per-hour seconds-per-minute)) (define years-to-seconds (lambda (years) (* years seconds-per-year)))
However, such a strategy is a bit dangerous. After all, there is nothing to prevent someone else from changing the values here.
(define days-per-year 360) ; Some strange calendar, perhaps in Indiana ...
What we'd like to do is to declare the values once, but keep them
years-to-seconds. The strategy is to move the
let outside the
(define years-to-seconds (let* ((days-per-year 365.24) (hours-per-day 24) (minutes-per-hour 60) (seconds-per-minute 60) (seconds-per-year (* days-per-year hours-per-day minutes-per-hour seconds-per-minute))) (lambda (years) (* years seconds-per-year))))
As you will see in the lab, it is possible to empirically verify that the bindings occur only once in this case, and each time the procedure is called in the prior case.
So, one moral of this story is whenever possible, move your
bindings outside the
lambda. For the first
example, in which we bound the name
black, one might
(let ((black (rgb-new 0 0 0))) (lambda (rgb ...) ...
However, it is not always possible to move the bindings outside of the
lambda. In particular, if your
let-bindings use parameters, then you need to keep them within the
body of the lambda. Consider the other half of the initial example.
In that case, we were computing the complement of
which we assumed was a parameter. In that case, we cannot write
(let ((black (rgb-new 0 0 0)) (complement (rgb-complement rgb))) (lambda (rgb ...) ...
but must instead write
(let ((black (rgb-new 0 0 0))) (lambda (rgb ...) (let ((complement (rgb-complement rgb))) ...
As you may have noted,
let behaves somewhat
define in that programmers can use it to
name values. But we've used
define to name more
than values; we've also used it to name procedures. Can we also use
let for procedures?
Yes, one can use a
create a local name for a procedure. And we name procedures locally
for the same reason that we name values, because it speeds and clarifies
(define hypotenuse-of-right-triangle (let ((square (lambda (n) (* n n)))) (lambda (first-leg second-leg) (sqrt (+ (square first-leg) (square second-leg))))))
Regardless of whether
square is also defined outside
this definition, the local binding gives it the appropriate
meaning within the lambda-expression that describes what
Note, once again, that there are two places one might define
square locally. We can define it before the lambda
(as above) or after the lambda (as below). In the first case,
the definition is done only once. In the second case, it is done
every time the procedure is executed.
(define hypotenuse-of-right-triangle (lambda (first-leg second-leg) (let ((square (lambda (n) (* n n)))) (sqrt (+ (square first-leg) (square second-leg))))))
So, which we should you do it? If the helper procedure you're defining
uses any of the parameters of the main procedure, it needs to come after
lambda. Otherwise, it is generally a better idea to
do it before the lambda. As you practice more with
you'll find times that each choice is appropriate.
Scheme also lets you create local bindings by nesting
define statements within each other.
We recommend that you limit your use of
to top-level definitions, using just
let* for internal definitions. While you can
define within another, the semantics are
a bit complicated, and such use can lead to unexpected results and
therefore confusion. (We also find internal
Janet Davis (firstname.lastname@example.org)