1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
|
<P>
<P><A NAME="trombone"></A><CENTER><IMG SRC="../ss-pics/trombone.jpg" ALT="figure: trombone"></CENTER><P><CENTER>Trombone players produce different pitches partly
by varying the length of a tube.
</CENTER><P>
<HTML>
<HEAD>
<TITLE>Simply Scheme: Introducing Computer Science ch 7: Variables</TITLE>
</HEAD>
<BODY>
<HR>
<CITE>Simply Scheme:</CITE>
<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT
<H2>Chapter 7</H2>
<H1>Variables</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../simply.jpg" ALT="cover photo">
<TD><TABLE>
<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian
Harvey</A><BR>University of California, Berkeley</CITE>
<TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew
Wright</A><BR>University of California, Santa Barbara</CITE>
<TR><TD align="right"><BR>
<TR><TD align="right"><A HREF="../pdf/ssch07.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../ss-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="../ssch6/true.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch8/part3.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="http://mitpress.mit.edu/0262082810">MIT
Press web page for <CITE>Simply Scheme</CITE></A>
</TABLE></TABLE>
<HR>
<P>A <EM>variable</EM> is a connection between a name and a
<A NAME="g1"></A> value.<A NAME="text1" HREF="variables.html#ft1">[1]</A> 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.
<P>The name <EM>variable</EM> comes from algebra. Many people are introduced to
variables in high school algebra classes, where the emphasis is on solving
equations. "If <EM>x</EM><SUP>3</SUP>−8=0, what is the value of <EM>x</EM>?" In
problems like these, although we call <EM>x</EM> a variable, it's really a <EM><A NAME="g2"></A><A NAME="g3"></A>named constant!</EM> In this particular problem, <EM>x</EM> has the
value 2. In any such problem, at first we don't know the value of <EM>x</EM>, but
we understand that it does have some particular value, and that value isn't
going to change in the middle of the problem.
<P>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 <EM>new</EM> variable is created, perhaps
with a different value.
<P>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 <EM>does</EM> 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 "<CODE>X = X + 1</CODE>." Back in Chapter 2 we told
you that this book is about something called
"<A NAME="g4"></A><A NAME="g5"></A>functional programming," but we haven't yet explained exactly
what that means. (Of course we <EM>have</EM> 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 <EM>change</EM> the value of that variable.
<P>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 <CODE>x</CODE> with
the value 7, and another variable named <CODE>x</CODE> with the value 51, at the
same time. The pitfall to avoid is thinking "<CODE>x</CODE> has changed its value
from 7 to 51."
<P>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."
<P><H2>How Little People Do Variables</H2>
<P><A NAME="g6"></A> 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 <CODE>(square 5)</CODE>, we
hire Srini and tell him his argument is 5. Srini therefore substitutes 5
for <CODE>x</CODE> in the body of <CODE>square</CODE>. 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 <CODE>x</CODE>.
<P><A NAME="srini"></A>
<CENTER><IMG SRC="../ss-pics/srini.jpg" ALT="figure: srini"></CENTER>
<P>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 <CODE>x</CODE> at the same time:
<P><PRE>(define (square x) (* x x))
(define (<A NAME="g7"></A>hypotenuse x y)
(sqrt (+ (square x) (square y))))
> (hypotenuse 3 4)
5
</PRE>
<P>Consider the situation when we've hired Hortense to evaluate that
expression. Hortense associates the name <CODE>x</CODE> with the value 3 (and also
the name <CODE>y</CODE> with the value 4, but we're going to pay attention to <CODE>x</CODE>). She has to compute two <CODE>square</CODE>s. She hires Solomon to compute
<CODE>(square 3)</CODE>. Solomon associates the name <CODE>x</CODE> 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 <CODE>(square 4)</CODE>. Now, simultaneously, Hortense
thinks <CODE>x</CODE> is 3 and Sheba thinks <CODE>x</CODE> is 4.
<P><A NAME="sheba"></A>
<CENTER><IMG SRC="../ss-pics/hortense.jpg" ALT="figure: hortense"></CENTER>
<P>(Remember that we said a variable is a connection between a name and a
value. So <CODE>x</CODE> isn't a variable! The association of the name <CODE>x</CODE>
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 "<CODE>x</CODE> is a variable"
when we mean "there is some variable whose name is <CODE>x</CODE>.")
<P>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:
<P><PRE>(define (f x)
(g 6))
(define (g y)
(+ x y))
> (f 4)
ERROR - VARIABLE X IS UNBOUND.
</PRE>
<P>We hire Franz to compute <CODE>(f 4)</CODE>. He associates <CODE>x</CODE> with
4 and evaluates <CODE>(g 6)</CODE> by hiring Gloria. Gloria associates <CODE>y</CODE>
with 6, but she doesn't have any value for <CODE>x</CODE>, so she's in trouble.
The solution is for Franz to tell Gloria that <CODE>x</CODE> is <CODE>4</CODE>:
<P><PRE>(define (f x)
(g x 6))
(define (g x y)
(+ x y))
> (f 4)
10
</PRE>
<P><H2>Global and Local Variables</H2>
<P>Until now, we've been using two very different kinds of naming. We have
names for procedures, which are created permanently by <CODE>define</CODE> 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.
<P>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 <EM>usually</EM> 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.
<P>Just as we've been using <CODE>define</CODE> to associate names with procedures
globally, we can also use it for other kinds of data:
<P><PRE>> (define pi 3.141592654)
> (+ pi 5)
8.141592654
> (define song '(I am the walrus))
> (last song)
WALRUS
</PRE>
<P>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 <CODE>pi</CODE> is the name of a
variable whose value is 3.141592654, <CODE>last</CODE> 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.
<P>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.)
<P>How does this little person know what values to substitute for global
variable names?
<A NAME="g8"></A>
<A NAME="g9"></A>
What makes a variable "global" in the little-people model
is that <EM>every</EM> 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 <CODE>define</CODE> specialist climbs up a huge ladder, picks up a megaphone,
and yells something like "Now hear this! <CODE>Pi</CODE> is 3.141592654!"
<P>The association of a formal parameter (a name) with an actual argument (a
value) is called a <EM><A NAME="g10"></A><A NAME="g11"></A>local variable.</EM>
<P>It's awkward to have to say "Harry associates the value 7 with the name
<CODE>foo</CODE>" all the time. Most of the time we just say "<CODE>foo</CODE> has the
value 7," paying no attention to whether this association is in some
particular little person's head or if everybody knows it.
<P><H2>The Truth about Substitution</H2>
<P>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
<A NAME="g12"></A>
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.
<P>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.<A NAME="text2" HREF="variables.html#ft2">[2]</A>
<P><H2><CODE>Let</CODE></H2>
<P>We'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.)
<P>We'll use the quadratic formula that you learned in high school
algebra class:
<P><P><CENTER><IMG SRC="math1.gif" ALT="math display"></CENTER><P>
<P><PRE>(define (roots a b c)
(se (/ (+ (- b) (sqrt (- (* b b) (* 4 a c))))
(* 2 a))
(/ (- (- b) (sqrt (- (* b b) (* 4 a c))))
(* 2 a))))
</PRE>
<P>Since there are two possible solutions, we return a sentence containing two
numbers. This procedure works fine,<A NAME="text3" HREF="variables.html#ft3">[3]</A> 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.
<P>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:
<P><PRE>(define (roots a b c)
(roots1 a b c (sqrt (- (* b b) (* 4 a c)))))
(define (roots1 a b c discriminant)
(se (/ (+ (- b) discriminant) (* 2 a))
(/ (- (- b) discriminant) (* 2 a))))
</PRE>
<P>This version evaluates the square root only once. The resulting
value is used as the argument named <CODE>discriminant</CODE> in <CODE>roots1</CODE>.
<P>We've solved the problem we posed for ourselves initially: avoiding the
redundant computation of the discriminant (the square-root part of the
formula). The cost, though, is that we had to define an auxiliary procedure
<CODE>roots1</CODE> that doesn't make much sense on its own. (That is, you'd never
invoke <CODE>roots1</CODE> for its own sake; only <CODE>roots</CODE> uses it.)
<P>Scheme provides a notation to express a computation of this kind more
<A NAME="splet"></A>
conveniently. It's called <A NAME="g13"></A><CODE>let</CODE>:
<P><PRE>(define (roots a b c)
(let ((discriminant (sqrt (- (* b b) (* 4 a c)))))
(se (/ (+ (- b) discriminant) (* 2 a))
(/ (- (- b) discriminant) (* 2 a)))))
</PRE>
<P>Our new program is just an abbreviation for the previous version:
In effect, it creates a temporary procedure just like <CODE>roots1</CODE>, but
without a name, and invokes it with the specified argument value. But the
<CODE>let</CODE> notation rearranges things so that we can say, in the right order,
"let the variable <CODE>discriminant</CODE> have the value <CODE>(sqrt&hellip)</CODE>
and, using that variable, compute the body."
<P><CODE>Let</CODE> is a <A NAME="g14"></A><A NAME="g15"></A>special form that takes two arguments. The first is
a sequence of name-value pairs enclosed in parentheses. (In this example,
there is only one name-value pair.) The second argument, the <EM>body</EM>
of the <CODE>let</CODE>, is the expression to evaluate.
<P>
Now that we have this notation, we can use it with more than one name-value
connection to eliminate even more redundant computation:
<P><PRE>(define (<A NAME="g16"></A>roots a b c)
(let ((discriminant (sqrt (- (* b b) (* 4 a c))))
(minus-b (- b))
(two-a (* 2 a)))
(se (/ (+ minus-b discriminant) two-a)
(/ (- minus-b discriminant) two-a))))
</PRE>
<P>In this example, the first argument to <CODE>let</CODE> includes three
name-value pairs. It's as if we'd defined and invoked a procedure like
the following:
<P><PRE>(define (roots1 discriminant minus-b two-a) ...)
</PRE>
<P>Like <CODE>cond</CODE>, <CODE>let</CODE> uses parentheses both with the usual meaning
(invoking a procedure) and to group sub-arguments that belong together. This
<A NAME="g17"></A>
grouping happens in two ways. Parentheses are used to group a name and the
expression that provides its value. Also, an additional pair of parentheses
surrounds the entire collection of name-value pairs.
<P>
<P><H2>Pitfalls</H2>
<P>If you've programmed before in other languages, you may be accustomed
to a style of programming in which you <EM>change</EM> the value of a
variable by assigning it a new value. You may be tempted to write
<P><PRE>> (define x (+ x 3)) ;; no-no
</PRE>
<P>Although some versions of Scheme do allow such redefinitions, so
that you can correct errors in your procedures, they're not strictly legal.
A definition is meant to be <EM>permanent</EM> in functional programming.
(Scheme does include other mechanisms for non-functional programming, but
we're not studying them in this book because once you allow reassignment you
need a more complex model of the evaluation process.)
<P>When you create more than one temporary variable at once using <CODE>let</CODE>, all of the expressions that provide the values are computed before any
of the variables are created. Therefore, you can't have one expression
depend on another:
<P><PRE>> (let ((a (+ 4 7)) ;; wrong!
(b (* a 5)))
(+ a b))
</PRE>
<P>Don't think that <CODE>a</CODE> gets the value 11 and therefore <CODE>b</CODE>
gets the value 55. That <CODE>let</CODE> expression is equivalent to defining a
helper procedure
<P><PRE>(define (helper a b)
(+ a b))
</PRE>
<P>and then invoking it:
<P><PRE>(helper (+ 4 7) (* a 5))
</PRE>
<P>The argument expressions, as always, are evaluated <EM>before</EM>
the function is invoked. The expression <CODE>(* a 5)</CODE> will be evaluated
using the <EM>global</EM> value of <CODE>a</CODE>, if there is one. If not, an
error will result. If you want to use <CODE>a</CODE> in computing <CODE>b</CODE>, you
must say
<P><PRE>> (let ((a (+ 4 7)))
(let ((b (* a 5)))
(+ a b)))
66
</PRE>
<P><CODE>Let</CODE>'s notation is tricky because, like <CODE>cond</CODE>, it uses
parentheses that don't mean procedure invocation. Don't teach yourself magic
formulas like "two open parentheses before the <CODE>let</CODE> variable and three
close parentheses at the end of its value." Instead, think about the
overall structure:
<P><PRE>(let variables body)
</PRE>
<P><CODE>Let</CODE> takes exactly two arguments. The first argument to <CODE>let</CODE> is one or more name-value groupings, all in parentheses:
<P><PRE>((name1 value1) (name2 value2) (name3 value3) &hellip)
</PRE>
<P>Each <CODE>name</CODE> is a single word; each <CODE>value</CODE> can be any
expression, usually a procedure invocation. If it's a procedure invocation,
then parentheses are used with their usual meaning.
<P>The second argument to <CODE>let</CODE> is the expression to be evaluated using
those variables.
<P>Now put all the pieces together:
<P><PRE>(let <STRONG><BIG>((</BIG></STRONG>name1 (fn1 arg1)<STRONG><BIG>)</BIG></STRONG>
<STRONG><BIG> (</BIG></STRONG>name2 (fn2 arg2)<STRONG><BIG>)</BIG></STRONG>
<STRONG><BIG> (</BIG></STRONG>name3 (fn3 arg3)<STRONG><BIG>))</BIG></STRONG>
body)
</PRE>
<P>
<H2>Boring Exercises</H2>
<P><B>7.1</B> The following procedure does some redundant computation.
<P><PRE>(define (<A NAME="g18"></A>gertrude wd)
(se (if (vowel? (first wd)) 'an 'a)
wd
'is
(if (vowel? (first wd)) 'an 'a)
wd
'is
(if (vowel? (first wd)) 'an 'a)
wd))
> (gertrude 'rose)
(A ROSE IS A ROSE IS A ROSE)
> (gertrude 'iguana)
(AN IGUANA IS AN IGUANA IS AN IGUANA)
</PRE>
<P>Use <CODE>let</CODE> to avoid the redundant work.
<P>
<B>7.2</B> Put in the missing parentheses:
<P><PRE>> (let pi 3.14159
pie 'lemon meringue
se 'pi is pi 'but pie is pie)
(PI IS 3.14159 BUT PIE IS LEMON MERINGUE)
</PRE>
<P>
<H2>Real Exercises</H2>
<P><B>7.3</B> The following program doesn't work. Why not? Fix it.
<P><PRE>(define (<A NAME="g19"></A>superlative adjective word)
(se (word adjective 'est) word))
</PRE>
<P>It's supposed to work like this:
<P><PRE>> (superlative 'dumb 'exercise)
(DUMBEST EXERCISE)
</PRE>
<P>
<B>7.4</B> What does this procedure do? Explain how it manages to work.
<P><PRE>(define (<A NAME="g20"></A>sum-square a b)
(let ((+ *)
(* +))
(* (+ a a) (+ b b))))
</PRE>
<P>
<HR>
<A NAME="ft1" HREF="variables.html#text1">[1]</A> The term "variable" is used by
computer scientists to mean several subtly different things. For example,
some people use "variable" to mean just a holder for a value, without a
name. But what we said is what <EM>we</EM> mean by "variable."<P>
<A NAME="ft2" HREF="variables.html#text2">[2]</A> The reason that all of our
examples work with the substitution model is that this book uses only
functional programming, in the sense that we never change the value of a
variable. If we started doing the <CODE>X = X + 1</CODE> style of programming, we
would need the more complicated chalkboard model.<P>
<A NAME="ft3" HREF="variables.html#text3">[3]</A> That is, it works if the equation
has real roots, or if your version of Scheme has complex numbers. Also, the
limited precision with which computers can represent irrational numbers can
make this particular algorithm give wrong answers in practice even though
it's correct in theory.<P>
<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P>
<A HREF="../ssch6/true.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch8/part3.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|