*One of a series of tutorials about Scheme in general and the Wraith Scheme interpreter in particular.*

Copyright © 2011
Jay Reynolds Freeman,
all rights reserved.

Personal Web Site:
http://JayReynoldsFreeman.com

EMail: Jay_Reynolds_Freeman@mac.com.

Sometimes it is useful to have an extra variable to use in the body of a procedure, that
is not one of the argument variables. You might want one to build up the result of a calculation a
piece at a time rather than doing it all at once, or perhaps for some other
purpose. Programmers call such extra variables ** local variables**, since their
intended scope is local -- the intended scope is just the body of the procedure.

Let me illustrate with our old friend the hypotenuse procedure. It is probably simple enough that it doesn't really need any local variables, but that makes it all the better for demonstrating the concept, because we are not going to get bogged down in understanding what the procedure actually does. Suppose that we would like to create two local variables for use within the procedure, one bound to the square of one of the sides of the triangle and the other to the square of the other side. We want the procedure to look sort of like the following, where I have used semicolons to comment out the part of the procedure that we don't yet know how to write.

(define (hypotenuse x y) ;; ;; Somehow create variable x-squared, bound to (* x x). ;; Somehow create variable y-squared, bound to (* y y). ;; (sqrt (+ x-squared) (y-squared)) )

We can do what we wish by using a ** let**. The name "let" is a
reserved word in Scheme. It is more or less syntactic sugar for a lambda application, so
don't worry about what gets evaluated and so on until I explain it -- let's just see what
it looks like at first. This is how I myself would write it.

(define (hypotenuse x y) (let ((x-squared (* x x)) (y-squared (* y y))) (sqrt (+ x-squared y-squared))) ) ;; ==> hypotenuse (hypotenuse 3 4) ;; ==> 5

Let me reformat that definition so that we can more easily see the separate pieces.

(define (hypotenuse x y) (let ((x-squared (* x x)) (y-squared (* y y))) (sqrt (+ x-squared y-squared)) ) )

Written out that way, it is clear that "let" can be viewed as just a list
of items. The first item in the list is "let". The second item is a list, namely
"((x-squared (* x x)) (y-squared (* y y)))", and that list is itself a list of ** binding
pairs**. This particular list of binding pairs has two elements, each itself a list, which
are "(x-squared (* x x))" and "(y-squared (* y y))". In a binding pair, the first element
in the list is the name of a local variable, which does not get evaluated, and the second
element is the value to which that local variable is to be bound. The second element does
get evaluated, so for this particular "let", the variables will be bound to the squares of
the sides of the triangle, as we wished.

A "let" can have as many binding pairs as you like, even none. That is, it is all right if the list of binding pairs is the empty list. Furthermore, the list that I am calling a binding pair can actually have more than two elements; the first must always be a variable name, but what Scheme will do with all the rest of the items is evaluate them in sequence, and bind whatever the last one returns to the variable name in question.

Everything inside the "let" after the list of binding pairs is the ** body of the
let**. In this case the body contains only one expression, but it may have more, if
you like. When the code for the "let" is evaluated, all of the expressions in the body of
the let will be evaluated in order, and the "let" will return whatever the last expression
evaluated returned. The "let" must return something, so its body must contain at least
one expression, but simple expressions, like numbers or strings, are fine.

(let () 42) ;; ==> 42

__The scope of the variables declared in a let's list of binding pairs is the body of
the let; it does not include the list of binding pairs itself.__

I said earlier that the "let" form was syntactic sugar for a lambda application. Let me expand out the present example so you can see how that works; it will probably make it a little clearer why the scope of the bound variables is what it is.

(define (hypotenuse x y) ((lambda (x-squared y-squared) (sqrt (+ x-squared y-squared))) (* x x) (* y y)) )

The "let" is turned into a procedure application, whose procedure is a lambda expression. The body of that lambda expression is the body of the let, and the argument variables of the lambda expression are the variables given in the let's binding pairs. The arguments to the lambda expression are the values we wished to have bound in the binding pairs.

Here is another interesting use of "let" to create local variables. We can bind a
variable name to any Scheme object we like; let's use that mechanism to create a
** local procedure**. This use is important to note, because most of the
commonly used programming languages have no way to create local procedures.

(define (hypotenuse x y) (let ((square (lambda (z) (* z z)))) (sqrt (+ (square x) (square y)))) )

See how that use of let has clarified what the hypotenuse procedure does: The one-line body, "(sqrt (+ (square x) (square y)))" is very close to the verbal description of the hypotenuse as "the square root of the sum of the squares of the sides".

Unfortunately, just "let" is not enough to serve all our needs for creating local
variables. Let's see why. Suppose we wanted the creation and binding of local
variables to do even more of the work in "hypotenuse", and tried the following -- which isn't
going to work.

(define (hypotenuse x y) (let ((x-squared (* x x)) (y-squared (* y y)) (sum-of-squares (+ x-squared y-squared)) ) (sqrt sum-of-squares) ) )

Do you see why that doesn't work? As a hint, what are the scopes of "x-squared" and "y-squared"?

The problem is that the scope of "x-squared" and "y-squared" is ** only** the
body of the let. Their scope does

(define (hypotenuse x y) ((lambda (x-squared y-squared sum-of-squares) (sqrt sum-of-squares) ) (* x x) (* y y) (+ x-squared y-squared) )

The problem is with the evaluation of the third argument to the
lambda expression; it needs x-squared and y-squared, and they do not exist at
the place in the code where the value of the third argument is required. They
are argument variables of the lambda expression, and their scope
is ** only** the body of the lambda expression, which is "inside"
the place where they are needed.

Fortunately, Scheme has another form that can help here; it is
called ** let*** -- which is usually pronounced "let-star", and it too is
syntactic sugar involving lambda expressions. You use it like this, and note that
the

(define (hypotenuse x y) (let* ((x-squared (* x x)) (y-squared (* y y)) (sum-of-squares (+ x-squared y-squared)) ) (sqrt sum-of-squares) ) )

What is happening here is that the syntactic sugar does not just create one lambda expression, it creates many -- as many lambda expressions as there are binding pairs in the "let*". These lambda expressions all have one argument, and they are nested. The effect is as if you were nesting "let"s, like this.

(define (hypotenuse x y) (let ((x-squared (* x x))) (let ((y-squared (* y y))) (let ((sum-of-squares (+ x-squared y-squared))) (sqrt sum-of-squares)))) )

Now the problem is solved: The value to be bound to "sum-of-squares" is evaluated within the scope of both "y-squared" and "x-squared".

You may know that in some notations used in mathematics and in computer science, the character "*", when used as a suffix to something, means "lots of that something in a row". You might therefore remember that "let*" means "lots of lets in a row". Actually, the lets are nested, but in any case, the use of "let*" saves you from having to write out large numbers of "let" expressions, as in the preceding expanded example.

There is still one more method for creating local variables that we need to know about. It
is very useful, but it will take a bit of work to develop an example to demonstrate it, so please
bear with me for a moment.

Suppose we want to create a procedure named "tell-if-even", that will be called with one
non-negative integer, and will print "yes" if the integer is even and "no" if it is not.
Scheme already has procedures to tell whether an integer is even or odd, but let's pretend
it doesn't. Let us also decide that we want to answer the question of whether a non-negative
integer is even by using ** recursion**, and we will see what that means as we go
along.

We can imagine two auxiliary procedures that will help, one called "is-even?" and one called "is-odd?". They would look like this if we defined them at top level, but our ultimate objective is to make them local procedures for use just within "tell-if-even", using "let" or something like it to create the auxiliary procedures and bind them to these names.

(define (is-even? n) (if (= n 0) #t (is-odd? (- n 1)))) ;; ==> is-even? (define (is-odd? n) (if (= n 0) #f (is-even? (- n 1)))) ;; ==> is-even?

Do you see how that works? If we call "is-even?" with a nonnegative integer n then either n is zero -- in which case the procedure returns #t at once -- or n is non-zero. An integer n is even if, and only if, n - 1 is odd, so "(is-even? n)" will pass the buck and ask "is-odd?" about n - 1; that is, it will call "(is-odd? (- n 1))". Procedure "is-odd?" will in turn make the same kind of decision, and the two procedures will go on calling each other in alternation -- chasing each other as if they were kittens at play -- each time with a value of n that is one less than it was before, until one of the procedures finally gets called with zero. That procedure will return its answer all the way back through that long chain of procedure calls.

This technique of having the same procedures call each other repeatedly is called
** recursion**, and Scheme programmers use it a lot. You can try it with the
top-level procedures just given, but be advised that it can take a long time for the
million procedure calls involved in answering "(is-even? 1000000)": Try it with small
numbers first, and do be sure that you call these procedures with a non-negative integer.

Yet we did not want to have these two procedures exist at top-level; instead, we wanted them to be local procedures for use within the body of "tell-if-even". We want to write "tell-if-even" to look something like this.

(define (tell-if-even n) ;; ;; Create local procedures "is-even?" and "is-odd?" here, with some kind of let ... ;; (if (is-even? n) (display "yes\n") (display "no\n")))

The question is, what kind of let do we use? We know that just "let" won't work.

(define (tell-if-even n) (let ((is-even? (lambda (n) (if (= n 0) #t (is-odd? (- n 1))))) (is-odd? (lambda (n) (if (= n 0) #f (is-even? (- n 1))))) ) (if (is-even? n) (display "yes\n") (display "no\n"))))

The problem here is exactly the one that motivated our discussion of "let*"; auxiliary procedure "is-even?" needs to use "is-odd?", but the scope of "is-odd?" does not include the place where "is-even?" is defined; and similarly, the scope of "is-even?" does not include the place where "is-odd?" is defined. So let's try "let*".

(define (tell-if-even n) (let* ((is-even? (lambda (n) (if (= n 0) #t (is-odd? (- n 1))))) (is-odd? (lambda (n) (if (= n 0) #f (is-even? (- n 1))))) ) (if (is-even? n) (display "yes\n") (display "no\n"))))

That fixes half the problem: Now the definition of "is-odd?" has access to "is-even?", but the definition of "is-even?" cannot "see" "is-odd?". How about if we switch the order of the binding pairs?

(define (tell-if-even n) (let* ((is-odd? (lambda (n) (if (= n 0) #f (is-even? (- n 1))))) (is-even? (lambda (n) (if (= n 0) #t (is-odd? (- n 1))))) ) (if (is-even? n) (display "yes\n") (display "no\n"))))

That doesn't work either -- we have still only fixed half of the problem, but it is the other half. Now it is "is-odd?" that cannot see "is-even?".

There is yet another "let" construct that will deal properly with this issue. It is called
** letrec** and pronounced "let-wreck". It is again syntactic sugar over lambda
expressions. What it does is first create an environment in which all the variables in the binding
pairs exist but are not yet bound to their final values, and then "set!"s the variables as
required. The result is as if you had written

(define (tell-if-even n) (let ((is-even? '()) (is-odd? '()) ) (set! is-even? (lambda (n) (if (= n 0) #t (is-odd? (- n 1))))) (set! is-odd? (lambda (n) (if (= n 0) #f (is-even? (- n 1))))) (if (is-even? n) (display "yes\n") (display "no\n"))))

That actually works, by the way, so you don't really need to use "letrec", but it saves typing if you just write

(define (tell-if-even n) (letrec ((is-even? (lambda (n) (if (= n 0) #t (is-odd? (- n 1))))) (is-odd? (lambda (n) (if (= n 0) #f (is-even? (- n 1))))) ) (if (is-even? n) (display "yes\n") (display "no\n"))))

The "rec" in "letrec" stands for "recursive", because the primary use of "letrec" in Scheme is for situations in which local functions need to call each other recursively. We are going to learn a lot more about recursion in subsequent tutorials.

I said in an earlier tutorial that most of Scheme can be described in terms of lambda expressions, and perhaps even implemented that way. Now that you have seen how "let", "let*" and "letrec" can be described as syntactic sugar on top of lambda expressions, perhaps you are beginning to sense that I wasn't kidding.

-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)