|
|
A variable is a connection between a name and a value.[1] That sounds simple enough, but some complexities arise in practice. To avoid confusion later, we'll spend some time now looking at the idea of "variable" in more detail.
The name variable comes from algebra. Many people are introduced to variables in high school algebra classes, where the emphasis is on solving equations. "If x3−8=0, what is the value of x?" In problems like these, although we call x a variable, it's really a named constant! In this particular problem, x has the value 2. In any such problem, at first we don't know the value of x, but we understand that it does have some particular value, and that value isn't going to change in the middle of the problem.
In functional programming, what we mean by "variable" is like a named constant in mathematics. Since a variable is the connection between a name and a value, a formal parameter in a procedure definition isn't a variable; it's just a name. But when we invoke the procedure with a particular argument, that name is associated with a value, and a variable is created. If we invoke the procedure again, a new variable is created, perhaps with a different value.
There are two possible sources of confusion about this. One is that you may
have programmed before in a programming language like BASIC or Pascal, in
which a variable often does get a new value, even after it's already
had a previous value assigned to it. Programs in those languages tend to be
full of things like "X = X + 1." Back in Chapter 2 we told
you that this book is about something called
"functional programming," but we haven't yet explained exactly
what that means. (Of course we have introduced a lot of functions,
and that is an important part of it.) Part of what we mean by functional
programming is that once a variable exists, we aren't going to change the value of that variable.
The other possible source of confusion is that in Scheme, unlike the
situation in algebra, we may have more than one variable with the same name
at the same time. That's because we may invoke one procedure, and the body
of that procedure may invoke another procedure, and each of them might use the
same formal parameter name. There might be one variable named x with
the value 7, and another variable named x with the value 51, at the
same time. The pitfall to avoid is thinking "x has changed its value
from 7 to 51."
As an analogy, imagine that you are at a party along with Mick Jagger, Mick Wilson, Mick Avory, and Mick Dolenz. If you're having a conversation with one of them, the name "Mick" means a particular person to you. If you notice someone else talking with a different Mick, you wouldn't think "Mick has become a different person." Instead, you'd think "there are several people here all with the name Mick."
You can understand variables in terms of the
little-people model. A variable, in this model, is the association in the
little person's mind between a formal parameter (name) and the actual
argument (value) she was given. When we want to know (square 5), we
hire Srini and tell him his argument is 5. Srini therefore substitutes 5
for x in the body of square. Later, when we want to know the
square of 6, we hire Samantha and tell her that her argument is 6. Srini and
Samantha have two different variables, both named x.
Srini and Samantha do their work separately, one after the other. But
in a more complicated example, there could even be more than
one value called x at the same time:
(define (square x) (* x x)) (define (hypotenuse x y) (sqrt (+ (square x) (square y)))) > (hypotenuse 3 4) 5
Consider the situation when we've hired Hortense to evaluate that
expression. Hortense associates the name x with the value 3 (and also
the name y with the value 4, but we're going to pay attention to x). She has to compute two squares. She hires Solomon to compute
(square 3). Solomon associates the name x with the value 3.
This happens to be the same as Hortense's value, but it's still a separate
variable that could have had a different value—as we see when Hortense
hires Sheba to compute (square 4). Now, simultaneously, Hortense
thinks x is 3 and Sheba thinks x is 4.
(Remember that we said a variable is a connection between a name and a
value. So x isn't a variable! The association of the name x
with the value 5 is a variable. The reason we're being so fussy about this
terminology is that it helps clarify the case in which several variables
have the same name. But in practice people are generally sloppy about this
fine point; we can usually get away with saying "x is a variable"
when we mean "there is some variable whose name is x.")
Another important point about the way little people do variables is that they can't read each others' minds. In particular, they don't know about the values of the local variables that belong to the little people who hired them. For example, the following attempt to compute the value 10 won't work:
(define (f x) (g 6)) (define (g y) (+ x y)) > (f 4) ERROR - VARIABLE X IS UNBOUND.
We hire Franz to compute (f 4). He associates x with
4 and evaluates (g 6) by hiring Gloria. Gloria associates y
with 6, but she doesn't have any value for x, so she's in trouble.
The solution is for Franz to tell Gloria that x is 4:
(define (f x) (g x 6)) (define (g x y) (+ x y)) > (f 4) 10
Until now, we've been using two very different kinds of naming. We have
names for procedures, which are created permanently by define and are
usable throughout our programs; and we have names for procedure arguments,
which are associated with values temporarily when we call a
procedure and are usable only inside that procedure.
These two kinds of naming seem to be different in every way. One is for procedures, one for data; the one for procedures makes a permanent, global name, while the one for data makes a temporary, local name. That picture does reflect the way that procedures and other data are usually used, but we'll see that really there is only one kind of naming. The boundaries can be crossed: Procedures can be arguments to other procedures, and any kind of data can have a permanent, global name. Right now we'll look at that last point, about global variables.
Just as we've been using define to associate names with procedures
globally, we can also use it for other kinds of data:
> (define pi 3.141592654) > (+ pi 5) 8.141592654 > (define song '(I am the walrus)) > (last song) WALRUS
Once defined, a global variable can be used anywhere, just as a defined
procedure can be used anywhere. (In fact, defining a procedure creates a
variable whose value is the procedure. Just as pi is the name of a
variable whose value is 3.141592654, last is the name of a variable
whose value is a primitive procedure. We'll come back to this
point in Chapter 9.) When the name of a global variable
appears in an expression, the corresponding value must be substituted, just
as actual argument values are substituted for formal parameters.
When a little person is hired to carry out a compound procedure, his or her first step is to substitute actual argument values for formal parameters in the body. The same little person substitutes values for global variable names also. (What if there is a global variable whose name happens to be used as a formal parameter in this procedure? Scheme's rule is that the formal parameter takes precedence, but even though Scheme knows what to do, conflicts like this make your program harder to read.)
How does this little person know what values to substitute for global
variable names?
What makes a variable "global" in the little-people model
is that every little person knows its value. You can imagine that
there's a big chalkboard, with all the global definitions written on it, that
all the little people can see.
If you prefer, you could imagine that whenever a global variable is defined,
the define specialist climbs up a huge ladder, picks up a megaphone,
and yells something like "Now hear this! Pi is 3.141592654!"
The association of a formal parameter (a name) with an actual argument (a value) is called a local variable.
It's awkward to have to say "Harry associates the value 7 with the name
foo" all the time. Most of the time we just say "foo has the
value 7," paying no attention to whether this association is in some
particular little person's head or if everybody knows it.
We said earlier in a footnote that Scheme doesn't actually do all the copying and substituting we've been talking about. What actually happens is more like our model of global variables, in which there is a chalkboard somewhere that associates names with values—except that instead of making a new copy of every expression with values substituted for names, Scheme works with the original expression and looks up the value for each name at the moment when that value is needed. To make local variables work, there are several chalkboards: a global one and one for each little person.
The fully detailed model of variables using several chalkboards is what many people find hardest about learning Scheme. That's why we've chosen to use the simpler substitution model.[2]
LetWe're going to write a procedure that solves quadratic equations. (We know this is the prototypical boring programming problem, but it illustrates clearly the point we're about to make.)
We'll use the quadratic formula that you learned in high school algebra class:
(define (roots a b c)
(se (/ (+ (- b) (sqrt (- (* b b) (* 4 a c))))
(* 2 a))
(/ (- (- b) (sqrt (- (* b b) (* 4 a c))))
(* 2 a))))
Since there are two possible solutions, we return a sentence containing two numbers. This procedure works fine,[3] but it does have the disadvantage of repeating a lot of the work. It computes the square root part of the formula twice. We'd like to avoid that inefficiency.
One thing we can do is to compute the square root and use that as the actual argument to a helper procedure that does the rest of the job:
(def1,2c1,2 < ;;;;METACIRCULAR EVALUATOR THAT SEPARATES ANALYSIS FROM EXECUTION < ;;;; FROM SECTION 4.1.7 OF STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS --- > ;;;;AMB EVALUATOR FROM SECTION 4.3 OF > ;;;; STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS 4c4,7 < ;;;;Matches code in ch4.scm --- > ;;;;Matches code in ch4.scm. > ;;;; To run the sample programs and exercises, code below also includes > ;;;; -- enlarged primitive-procedures list > ;;;; -- support for Let (as noted in footnote 56, p.428) 18c21 < ;;Note: It is loaded first so that the section 4.1.7 definition --- > ;;Note: It is loaded first so that the section 4.2 definition 20c23 < (load "61a/lib/mceval.scm") --- > (load "~/61a/lib/mceval.scm") 22d24 < ;;;SECTION 4.1.7 24,25d25 < (define (mc-eval exp env) < ((analyze exp) env)) 26a27,33 > ;;;Code from SECTION 4.3.3, modified as needed to run it > > (define (amb? exp) (tagged-list? exp 'amb)) > (define (amb-choices exp) (cdr exp)) > > ;; analyze from 4.1.6, with clause from 4.3.3 added > ;; and also support for Let 37a45,46 > ((let? exp) (analyze (let->combination exp))) ;** > ((amb? exp) (analyze-amb exp)) ;** 41a51,55 > (define (ambeval exp env succeed fail) > ((analyze exp) env succeed fail)) > > ;;;Simple expressions > 43c57,58 < (lambda (env) exp)) --- > (lambda (env succeed fail) > (succeed exp fail))) 47c62,63 < (lambda (env) qval))) --- > (lambda (env succeed fail) > (succeed qval fail)))) 50c66,68 < (lambda (env) (lookup-variable-value exp env))) --- > (lambda (env succeed fail) > (succeed (lookup-variable-value exp env) > fail))) 52,57c70,75 < (define (analyze-assignment exp) < (let ((var (assignment-variable exp)) < (vproc (analyze (assignment-value exp)))) < (lambda (env) < (set-variable-value! var (vproc env) env) < 'ok))) --- > (define (analyze-lambda exp) > (let ((vars (lambda-parameters exp)) > (bproc (analyze-sequence (lambda-body exp)))) > (lambda (env succeed fail) > (succeed (make-procedure vars bproc env) > fail)))) 59,64c77 < (define (analyze-definition exp) < (let ((var (definition-variable exp)) < (vproc (analyze (definition-value exp)))) < (lambda (env) < (define-variable! var (vproc env) env) < 'ok))) --- > ;;;Conditionals and sequences 70,73c83,92 < (lambda (env) < (if (true? (pproc env)) < (cproc env) < (aproc env))))) --- > (lambda (env succeed fail) > (pproc env > ;; success continuation for evaluating the predicate > ;; to obtain pred-value > (lambda (pred-value fail2) > (if (true? pred-value) > (cproc env succeed fail2) >