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
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 not include the place where "sum-of-squares" is being defined. To make that clearer, let's expand the last definition into a lambda expression.
(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 only difference between this expression and the one that didn't work is the substitution of "let*" for "let".
(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)