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
|
<P>
<P><A NAME="bucket"></A><CENTER><IMG SRC="../ss-pics/bucket.jpg" ALT="figure: bucket"></CENTER><P><CENTER>In a bucket brigade, each person hands a result to the
next.
</CENTER><P>
<HTML>
<HEAD>
<TITLE>Simply Scheme: Introducing Computer Science ch 3: Expressions</TITLE>
</HEAD>
<BODY>
<HR>
<CITE>Simply Scheme:</CITE>
<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT
<H2>Chapter 3</H2>
<H1>Expressions</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/ssch03.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="part2.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch4/defining.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>The interaction between you and Scheme is called the
"read-eval-print loop." Scheme reads what you type, <EM>evaluates</EM>
it, and prints the answer, and then does the same thing over again. We're
emphasizing the word "evaluates" because the essence of understanding
Scheme is knowing what it means to evaluate something.
<P>Each question you type is called an <EM>expression.</EM><A NAME="text1" HREF="people.html#ft1">[1]</A> The
expression can be a single value, such as <CODE>26</CODE>, or something more
complicated in parentheses, such as <CODE>(+ 14 7)</CODE>. The first kind of
expression is called an <EM>atom</EM> (or <EM><A NAME="g1"></A><A NAME="g2"></A>atomic expression</EM>), while the second kind of expression is
called a <EM><A NAME="g3"></A><A NAME="g4"></A>compound expression,</EM> because it's made out of the
smaller expressions <CODE>+</CODE>, <CODE>14</CODE>, and <CODE>7</CODE>. The metaphor is from
chemistry, where atoms of single elements are combined to form chemical
compounds. We sometimes call the expressions within a compound expression
its <EM>subexpressions.</EM>
<P>Compound expressions tell Scheme to "do" a procedure. This idea is so
important that it has a lot of names. You can <EM>call</EM> a procedure; you
can <EM>invoke</EM> a procedure; or you can <EM>apply</EM> a procedure to some
numbers or other values. All of these mean the same thing.
<P>If you've programmed before in some other language, you're probably
accustomed to the idea of several different types of statements for
different purposes. For example, a "print statement" may look very
different from an "assignment statement." In Scheme, everything is done by
calling procedures, just as we've been doing here. Whatever you want to do,
there's only one notation: the compound expression.
<P>Notice that we said a compound expression contains expressions. This means
that you can't understand what an expression is until you already understand
what an expression is. This sort of circularity comes up again and again
and again and again<A NAME="text2" HREF="people.html#ft2">[2]</A> in Scheme programming. How do
you ever get a handle on this self-referential idea? The secret is that
there has to be some simple kind of expression that <EM>doesn't</EM> have
smaller expressions inside it—the atomic expressions.
<P>It's easy to understand an expression that just contains one number.
Numbers are <EM>self-evaluating;</EM> that is, when you evaluate a
<A NAME="g5"></A>
<A NAME="g6"></A>
number, you just get the same number back.
<P>Once you understand <EM>numbers,</EM> you can understand <EM>expressions
that add up</EM> numbers. And once you understand <EM>those</EM> expressions,
you can use that knowledge to figure out <EM>expressions that add up</EM>
expressions-that-add-up-numbers. Then and so on. In practice, you
don't usually think about all these levels of complexity separately. You
just think, "I know what a number is, and I know what it means to add up
<EM>any</EM> expressions."
<P>
So, for example, to understand the expression
<P><PRE>(+ (+ 2 3) (+ 4 5))
</PRE>
<P>you must first understand <CODE>2</CODE> and <CODE>3</CODE> as self-evaluating
numbers, then understand <CODE>(+ 2 3)</CODE> as an expression that adds those
numbers, then understand how the sum, 5, contributes to the overall
expression.
<P>
By the way, in ordinary arithmetic you've gotten used to the idea that
parentheses can be optional; 3+4×5 means the same as 3+(4×5).
But in Scheme, parentheses are <EM>never</EM> optional. Every procedure call
must be enclosed in parentheses.
<P><H2>Little People</H2>
<P>You may not have realized it, but inside your computer there are thousands
of little people. Each of them is a specialist in one particular
Scheme procedure. The head little person, Alonzo, is in charge of the
read-eval-print loop.
<P>
When you enter an expression, such as
<P><PRE>(- (+ 5 8) (+ 2 4))
</PRE>
<P>Alonzo reads it, hires other little people to help him evaluate
it, and finally prints <CODE>7</CODE>, its value. We're going to focus on the
evaluation step.
<P>
Three little people work together to evaluate the expression: a minus person
and two plus people. (To make this account easier to read, we're using the
ordinary English words "minus" and "plus" to refer to the procedures
whose Scheme names are <CODE>-</CODE> and <CODE>+</CODE>. Don't be confused by this and
try to type <CODE>minus</CODE> to Scheme.)
<P>Since the overall expression is a subtraction, Alonzo hires Alice, the first
available minus specialist. Here's how the little people evaluate the
expression:
<P><P><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Alice wants to be given some numbers, so before she can do any work, she
complains to Alonzo that she wants to know which numbers to subtract.
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Alonzo looks at the subexpressions that should provide Alice's
arguments, namely, <CODE>(+ 5 8)</CODE> and <CODE>(+ 2 4)</CODE>. Since both of these are
addition problems, Alonzo hires two plus specialists, Bernie and Cordelia,
and tells them to report their results to Alice.
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The first plus person, Bernie, also wants some numbers, so he asks
Alonzo for them.
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Alonzo looks at the subexpressions of <CODE>(+ 5 8)</CODE> that should provide
Bernie's arguments, namely, <CODE>5</CODE> and <CODE>8</CODE>. Since these are both
atomic, Alonzo can give them directly to Bernie.
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Bernie adds his arguments, <CODE>5</CODE> and <CODE>8</CODE>, to get <CODE>13</CODE>. He
does this in his head—we don't have to worry about how he knows how to
add; that's his job.
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The second plus person, Cordelia, wants some arguments; Alonzo looks at
the subexpressions of <CODE>(+ 2 4)</CODE> and gives the <CODE>2</CODE> and <CODE>4</CODE> to
Cordelia. She adds them, getting <CODE>6</CODE>.
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Bernie and Cordelia hand their results to the waiting Alice, who can now
subtract them to get <CODE>7</CODE>. She hands that result to Alonzo, who prints
it.
</TABLE><P>
How does Alonzo know what's the argument to what? That's what the grouping
of subexpressions with parentheses is about. Since the plus expressions are
inside the minus expression, the plus people have to give their results to
the minus person.
<P>We've made it seem as if Bernie does his work before Cordelia does hers. In
fact, the <EM><A NAME="g7"></A><A NAME="g8"></A>order of evaluation</EM> of the argument subexpressions
is not specified in Scheme; different implementations may do it in different
orders. In particular, Cordelia might do her work before Bernie, or they
might even do their work at the same time, if we're using a <EM>parallel
processing</EM> computer. However, it <EM>is</EM> important that both Bernie
and Cordelia finish their work before Alice can do hers.
<P>The entire call to <CODE>-</CODE> is itself a single expression; it could be a
part of an even larger expression:
<P><PRE>> (* (- (+ 5 8) (+ 2 4))
(/ 10 2))
35
</PRE>
<P>This says to multiply the numbers 7 and 5, except that instead of
saying 7 and 5 explicitly, we wrote expressions whose values are 7 and 5.
(By the way, we would say that the above expression has three
subexpressions, the <CODE>*</CODE> and the two arguments. The argument
subexpressions, in turn, have their own subexpressions. However, these
sub-subexpressions, such as <CODE>(+ 5 8)</CODE>, don't count as
subexpressions of the whole thing.)
<P>We can express this organization of little people more formally. If
an expression is atomic, Scheme just knows the value.<A NAME="text3" HREF="people.html#ft3">[3]</A> Otherwise, it is a compound
expression, so Scheme first evaluates all the subexpressions (in some
unspecified order) and then applies the value of the first one,
which had better be a procedure, to the values of the rest of them.
Those other subexpressions are the arguments.
<P>We can use this rule to evaluate arbitrarily complex expressions, and
Scheme won't get confused. No matter how long the expression is, it's made
up of smaller subexpressions to which the same rule applies.
Look at this long, messy example:
<A NAME="g9"></A>
<P><PRE>> (+ (* 2 (/ 14 7) 3)
(/ (* (- (* 3 5) 3) (+ 1 1))
(- (* 4 3) (* 3 2)))
(- 15 18))
13
</PRE>
<P>Scheme understands this by looking for the subexpressions of the overall
expression, like this:
<P><PRE>(+ ()
( ; One of them takes two lines but you can tell by
) ; matching parentheses that they're one expression.
())
</PRE>
<P>(Scheme ignores everything to the right of a semicolon, so
semicolons can be used to indicate comments, as above.)
<P>
Notice that in the example above we asked <CODE>+</CODE> to add <EM>three</EM>
numbers. In the <CODE>functions</CODE> program of Chapter 2 we
pretended that every Scheme function accepts a fixed number of arguments,
but actually, some functions can accept any number. These include <CODE>+</CODE>,
<CODE>*</CODE>, <CODE>word</CODE>, and <CODE>sentence</CODE>.
<P><H2>Result Replacement</H2>
<P><A NAME="g10"></A>
<A NAME="g11"></A>
Since a little person can't do his or her job until all of the necessary
subexpressions have been evaluated by other little people, we can "fast
forward" this process by skipping the parts about "Alice waits for Bernie
and Cordelia" and starting with the completion of the smaller tasks by the
lesser little people.
<P>To keep track of which result goes into which larger computation, you can
write down a complicated expression and then <EM>rewrite</EM> it repeatedly,
each time replacing some small expression with a simpler expression
that has the same value.
<P><PRE>(+ (* <CODE STYLE="border:solid">(- 10 7)</code> (+ 4 1)) (- 15 (/ 12 3)) 17)
(+ (* 3 <CODE STYLE="border:solid">(+ 4 1)</code>) (- 15 (/ 12 3)) 17)
(+ <CODE STYLE="border:solid">(* 3 5 )</code> (- 15 (/ 12 3)) 17)
(+ 15 (- 15 <CODE STYLE="border:solid">(/ 12 3)</code>) 17)
(+ 15 <CODE STYLE="border:solid">(- 15 4 )</code> 17)
<CODE STYLE="border:solid">(+ 15 11 17)</code>
43
</PRE>
<P>In each line of the diagram, the boxed expression
is the one that will be replaced with its value on the following line.
<P>If you like, you can save some steps by evaluating <EM>several</EM> small
expressions from one line to the next:
<P><PRE>(+ (* <CODE STYLE="border:solid">(- 10 7)</code> <CODE STYLE="border:solid">(+ 4 1)</code>) (- 15 <CODE STYLE="border:solid">(/ 12 3)</code>) 17)
(+ <CODE STYLE="border:solid">(* 3 5 )</code> <CODE STYLE="border:solid">(- 15 4 )</code> 17)
<CODE STYLE="border:solid">(+ 15 11 17)</code>
43
</PRE>
<P><H2>Plumbing Diagrams</H2>
<A NAME="crank"></A>
<P>Some people find it helpful to look at a pictorial form of the connections
among subexpressions. You can think of each procedure as a machine, like the
<A NAME="g12"></A>
<A NAME="g13"></A>
ones they drew on the chalkboard in junior high school.
<P><CENTER><IMG SRC="../ss-pics/function.jpg" ALT="figure: function"></CENTER>
<P>Each machine has some number of input hoppers on the top and one chute at the
bottom. You put something in each hopper, turn the crank, and something else
comes out the bottom. For a complicated expression, you hook up the output
chute of one machine to the input hopper of another. These combinations are
called "plumbing diagrams." Let's look at the <A NAME="g14"></A><A NAME="g15"></A>plumbing diagram
for <CODE>(- (+ 5 8) (+ 2 4))</CODE>:
<CENTER><IMG SRC="../ss-pics/plumbing.jpg" ALT="figure: plumbing"></CENTER>
<P>You can annotate the diagram by indicating the actual information that flows
through each pipe. Here's how that would look for this expression:
<P><CENTER><IMG SRC="../ss-pics/annotated.jpg" ALT="figure: annotated"></CENTER>
<P><H2>Pitfalls</H2>
<P>One of the biggest problems that beginning Lisp programmers have comes
from trying to read a program from left to right, rather than thinking about
it in terms of expressions and subexpressions. For example,
<P><PRE>(square (cos 3))
</PRE>
<P><EM>doesn't</EM> mean "square three, then take the cosine of
the answer you get." Instead, as you know, it means that the argument to
<CODE>square</CODE> is the return value from <CODE>(cos 3)</CODE>.
<P>Another big problem that people have is thinking that Scheme cares
about the spaces, tabs, line breaks, and other "white space" in their
Scheme programs. We've been indenting our expressions to illustrate the way
that subexpressions line up underneath each other. But to Scheme,
<A NAME="g16"></A>
<P><PRE>(+ (* 2 (/ 14 7) 3) (/ (* (- (* 3 5) 3) (+ 1
1)) (- (* 4 3) (* 3 2))) (- 15 18))
</PRE>
<P>means the same thing as
<P><PRE>(+ (* 2 (/ 14 7) 3)
(/ (* (- (* 3 5) 3) (+ 1 1))
(- (* 4 3) (* 3 2)))
(- 15 18))
</PRE>
<P>So in this expression:
<P><PRE>(+ (* 3 (sqrt 49) ;; weirdly formatted
(/ 12 4)))
</PRE>
<P>there aren't two arguments to <CODE>+</CODE>, even though it looks that
way if you think about the indenting. What Scheme does is look at the
parentheses, and if you examine these carefully, you'll see that there are
three arguments to <CODE>*</CODE>: the atom <CODE>3</CODE>, the compound expression <CODE>(sqrt 49)</CODE>, and the compound expression <CODE>(/ 12 4)</CODE>. (And there's only one
argument to <CODE>+</CODE>.)
<P>A consequence of Scheme's not caring about white space is that when you
hit the return key, Scheme might not do anything. If you're in the middle
of an expression, Scheme waits until you're done typing the entire thing
before it evaluates what you've typed. This is fine if your program is
correct, but if you type this in:
<P><PRE>(+ (* 3 4)
(/ 8 2) ; note missing right paren
</PRE>
<P>then <EM>nothing</EM> will happen. Even if you type forever, until
you close the open parenthesis next to the <CODE>+</CODE> sign, Scheme will still
be reading an expression. So if Scheme seems to be ignoring you, try typing
a zillion close parentheses. (You'll probably get an error message about
too many parentheses, but after that, Scheme should start paying attention
again.)
<P>You might get into the same sort of trouble if you have a double-quote
mark (<CODE>"</CODE>) in your program. Everything inside a pair of quotation marks
is treated as one single <EM>string.</EM> We'll explain more about
strings later. For now, if your program has a stray quotation mark, like
this:
<P><PRE>(+ (* 3 " 4) ; note extra quote mark
(/ 8 2))
</PRE>
<P>then you can get into the same predicament of typing and having
Scheme ignore you. (Once you type the second quotation mark, you may still
need some close parentheses, since the ones you type inside a string
don't count.)
<P>One other way that Scheme might seem to be ignoring you comes from the
fact that you don't get a new Scheme prompt until you type in an expression
and it's evaluated. So if you just hit the <CODE>return</CODE> or <CODE>enter</CODE> key
without typing anything, most versions of Scheme won't print a new prompt.
<P><H2>Boring Exercises</H2>
<P><B>3.1</B> Translate the arithmetic expressions (3+4)×5 and 3+(4×5)
into Scheme expressions, and into plumbing diagrams.
<P>
<B>3.2</B> How many little people does Alonzo hire in evaluating each
of the following expressions:
<PRE>(+ 3 (* 4 5) (- 10 4))
(+ (* (- (/ 8 2) 1) 5) 2)
(* (+ (- 3 (/ 4 2))
(sin (* 3 2))
(- 8 (sqrt 5)))
(- (/ 2 3)
4))
</PRE>
<P>
<B>3.3</B> Each of the expressions in the previous exercise is compound. How many
subexpressions (not including subexpressions of subexpressions) does each
one have?
<P>For example,
<P><PRE>(* (- 1 (+ 3 4)) 8)
</PRE>
<P>has three subexpressions; you wouldn't count <CODE>(+ 3 4)</CODE>.
<P>
<B>3.4</B> Five little people are hired in evaluating the following expression:
<PRE>(+ (* 3 (- 4 7))
(- 8 (- 3 5)))
</PRE>
Give each little person a name and list her specialty, the argument values
she receives, her return value, and the name of the little person to whom
she tells her result.
<P>
<B>3.5</B> Evaluate each of the following expressions using the result replacement
technique:
<P><PRE>(sqrt (+ 6 (* 5 2)))
(+ (+ (+ 1 2) 3) 4)
</PRE>
<P>
<B>3.6</B> Draw a plumbing diagram for each of the following expressions:
<PRE>(+ 3 4 5 6 7)
(+ (+ 3 4) (+ 5 6 7))
(+ (+ 3 (+ 4 5) 6) 7)
</PRE>
<P>
<B>3.7</B> What value is returned by <CODE>(/ 1 3)</CODE> in your version of
Scheme? (Some Schemes return a decimal fraction like <CODE>0.33333</CODE>, while
others have exact fractional values like <CODE>1/3</CODE> built in.)
<P><B>3.8</B> Which of the functions that you explored in Chapter 2 will
accept variable numbers of arguments?
<P>
<H2>Real Exercises</H2>
<P><B>3.9</B> The expression <CODE>(+ 8 2)</CODE> has the value <CODE>10</CODE>. It is a compound
expression made up of three atoms. For this problem, write five other
Scheme expressions whose values are also the number ten:
<P><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">An atom
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Another compound expression made up of three atoms
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">A compound expression made up of four atoms
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">A compound expression made up of an atom and two compound subexpressions
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Any other kind of expression
</TABLE><P>
<P>
<HR>
<A NAME="ft1" HREF="people.html#text1">[1]</A> In
other programming languages, the name for what you type might be a
"command" or an "instruction." The name "expression" is meant to
emphasize that we are talking about the notation in which you ask the
question, as distinct from the idea in your head, just as in English you
express an idea in words. Also, in Scheme we are more often asking
questions rather than telling the computer to take some action.<P>
<A NAME="ft2" HREF="people.html#text2">[2]</A> and again<P>
<A NAME="ft3" HREF="people.html#text3">[3]</A> We'll
explain this part in more detail later.<P>
<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P>
<A HREF="part2.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch4/defining.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|