forked from twcamper/sicp-kindle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-10.html
1651 lines (1335 loc) · 80.6 KB
/
book-Z-H-10.html
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
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http:https://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o,
(c) Dorai Sitaram, http:https://www.cs.rice.edu/~dorai/tex2page -->
<head>
<meta name="generator" content="HTML Tidy for Linux (vers 7 December 2008), see www.w3.org" />
<title>Structure and Interpretation of Computer Programs</title>
<link href="book-Z-C.css" title="default" rel="stylesheet" type="text/css" />
<meta name="robots" content="noindex,follow" />
</head>
<body>
<mbp:pagebreak />
<p><a name="%_sec_1.1"></a></p>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_1.1">1.1 The
Elements of Programming</a></h2>
<p><a name="%_idx_118"></a> A powerful programming language is
more than just a means for instructing a computer to perform
tasks. The language also serves as a framework within which we
organize our ideas about processes. Thus, when we describe a
language, we should pay particular attention to the means that
the language provides for combining simple ideas to form more
complex ideas. Every powerful language has three mechanisms for
accomplishing this:</p>
<ul>
<li>
<strong>primitive expressions</strong>, which represent the
simplest entities the language is concerned with,
<p><a name="%_idx_122"></a><a name="%_idx_124"></a></p>
</li>
<li>
<strong>means of combination</strong>, by which compound
elements are built from simpler ones, and
<p><a name="%_idx_126"></a></p>
</li>
<li><strong>means of abstraction</strong>, by which compound
elements can be named and manipulated as units.</li>
</ul>
<p>In programming, we deal with two kinds of elements: <a name="%_idx_128"></a>procedures and <a name="%_idx_130"></a>data.
(Later we will discover that they are really not so distinct.)
Informally, data is ``stuff'' that we want to manipulate, and
procedures are descriptions of the rules for manipulating the
data. Thus, any powerful programming language should be able to
describe primitive data and primitive procedures and should have
methods for combining and abstracting procedures and data.</p>
<p>In this chapter we will deal only with simple <a name="%_idx_132"></a><a name="%_idx_134"></a>numerical data so that we
can focus on the rules for building procedures.<a href="#footnote_Temp_10" name="call_footnote_Temp_10" id="call_footnote_Temp_10"><sup><small>4</small></sup></a> In later
chapters we will see that these same rules allow us to build
procedures to manipulate compound data as well.</p>
<p><a name="%_sec_1.1.1"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.1.1">1.1.1 Expressions</a></h3>
<p>One easy way to get started at programming is to examine some
typical interactions with an interpreter for the Scheme dialect
of Lisp. Imagine that you are sitting at a computer terminal. You
type an <em>expression</em>, and the interpreter responds by
displaying the result of its <em>evaluating</em> that
expression.</p>
<p><a name="%_idx_148"></a><a name="%_idx_150"></a>One kind of
primitive expression you might type is a number. (More precisely,
the expression that you type consists of the numerals that
represent the number in base 10.) If you present Lisp with a
number</p>
<p><tt>486<br /></tt></p>
<p>the interpreter will respond by printing<a href="#footnote_Temp_11" name="call_footnote_Temp_11" id="call_footnote_Temp_11"><sup><small>5</small></sup></a></p>
<p><tt><i>486</i><br /></tt></p>
<p><a name="%_idx_154"></a><a name="%_idx_156"></a>Expressions
representing numbers may be combined with an <a name="%_idx_158"></a>expression representing a <a name="%_idx_160"></a><a name="%_idx_162"></a><a name="%_idx_164"></a><a name="%_idx_166"></a><a name="%_idx_168"></a>primitive procedure (such as <tt>+</tt> or
<tt>*</tt>) to form a compound expression that represents the
application of the procedure to those numbers. For example:</p>
<p><tt>(+ 137 349)<br />
<i>486</i><br />
<a name="%_idx_170"></a><a name="%_idx_172"></a>(- 1000 334)<br />
<i>666</i><br />
(* 5 99)<br />
<i>495</i><br />
<a name="%_idx_174"></a><a name="%_idx_176"></a>(/ 10 5)<br />
<i>2</i><br />
(+ 2.7 10)<br />
<i>12.7</i><br /></tt></p>
<p>Expressions such as these, formed by <a name="%_idx_178"></a>delimiting a list of expressions within
parentheses in order to denote <a name="%_idx_180"></a>procedure
application, are called <em>combinations</em>. The leftmost
element in the list is called the <a name="%_idx_182"></a><em>operator</em>, and the other elements are
called <a name="%_idx_184"></a><em>operands</em>. The <a name="%_idx_186"></a>value of a combination is obtained by applying
the procedure specified by the operator to the <a name="%_idx_188"></a><em>arguments</em> that are the values of the
operands.</p>
<p>The convention of placing the operator to the left of the
operands is known as <a name="%_idx_190"></a><em>prefix
notation</em>, and it may be somewhat confusing at first because
it departs significantly from the customary mathematical
convention. Prefix notation has several advantages, however. One
of them is that it can accommodate <a name="%_idx_192"></a><a name="%_idx_194"></a>procedures that may take
an arbitrary number of arguments, as in the following
examples:</p>
<p><tt>(+ 21 35 12 7)<br />
<i>75</i><br />
<br />
(* 25 4 12)<br />
<i>1200</i><br /></tt></p>
<p>No ambiguity can arise, because the operator is always the
leftmost element and the entire combination is delimited by the
parentheses.</p>
<p><a name="%_idx_196"></a>A second advantage of prefix notation
is that it extends in a straightforward way to allow combinations
to be <em>nested</em>, that is, to have combinations whose
elements are themselves combinations:</p>
<p><tt>(+ (* 3 5) (- 10 6))<br />
<i>19</i><br /></tt></p>
<p>There is no limit (in principle) to the depth of such nesting
and to the overall complexity of the expressions that the Lisp
interpreter can evaluate. It is we humans who get confused by
still relatively simple expressions such as</p>
<p>
<tt>(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))<br />
</tt></p>
<p>which the interpreter would readily evaluate to be 57. We can
help ourselves by writing such an expression in the form</p>
<p><tt>(+ (* 3<br />
(+ (* 2 4)<br />
(+ 3 5)))<br />
(+ (- 10 7)<br />
6))<br /></tt></p>
<p>following a formatting convention known as <a name="%_idx_198"></a><em>pretty-printing</em>, in which each long
combination is written so that the operands are aligned
vertically. The resulting indentations display clearly the
structure of the expression.<a href="#footnote_Temp_12" name="call_footnote_Temp_12" id="call_footnote_Temp_12"><sup><small>6</small></sup></a></p>
<p>Even with complex expressions, the interpreter always operates
in the same basic cycle: It reads an expression from the
terminal, evaluates the expression, and prints the result. This
mode of operation is often expressed by saying that the
interpreter runs in a <a name="%_idx_204"></a><a name="%_idx_206"></a><em>read-eval-print loop</em>. Observe in
particular that it is not necessary to explicitly instruct the
interpreter to print the value of the expression.<a href="#footnote_Temp_13" name="call_footnote_Temp_13" id="call_footnote_Temp_13"><sup><small>7</small></sup></a></p>
<p><a name="%_sec_1.1.2"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.1.2">1.1.2 Naming and
the Environment</a></h3>
<p>A critical aspect of a programming language is the means it
provides for using <a name="%_idx_216"></a>names to refer to
computational objects. We say that the <a name="%_idx_218"></a>name identifies a <a name="%_idx_220"></a><em>variable</em> whose <a name="%_idx_222"></a><em>value</em> is the object.</p>
<p>In the Scheme dialect of Lisp, we name things with <a name="%_idx_224"></a><a name="%_idx_226"></a><tt>define</tt>.
Typing</p>
<p><tt>(define size 2)<br /></tt></p>
<p>causes the interpreter to associate the value 2 with the name
<tt>size</tt>.<a href="#footnote_Temp_14" name="call_footnote_Temp_14" id="call_footnote_Temp_14"><sup><small>8</small></sup></a> Once the
name <tt>size</tt> has been associated with the number 2, we can
refer to the value 2 by name:</p>
<p><tt>size<br />
<i>2</i><br />
(* 5 size)<br />
<i>10</i><br /></tt></p>
<p>Here are further examples of the use of <tt>define</tt>:</p>
<p><tt>(define pi 3.14159)<br />
(define radius 10)<br />
(* pi (* radius radius))<br />
<i>314.159</i><br />
(define circumference (* 2 pi radius))<br />
circumference<br />
<i>62.8318</i><br /></tt></p>
<p><a name="%_idx_232"></a><tt>Define</tt> is our language's
simplest means of abstraction, for it allows us to use simple
names to refer to the results of compound operations, such as the
<tt>circumference</tt> computed above. In general, computational
objects may have very complex structures, and it would be
extremely inconvenient to have to remember and repeat their
details each time we want to use them. Indeed, complex programs
are constructed by building, step by step, computational objects
of increasing complexity. The interpreter makes this step-by-step
program construction particularly convenient because name-object
associations can be created incrementally in successive
interactions. This feature encourages the <a name="%_idx_234"></a><a name="%_idx_236"></a>incremental development
and testing of programs and is largely responsible for the fact
that <a name="%_idx_238"></a>a Lisp program usually consists of a
large number of relatively simple procedures.</p>
<p>It should be clear that the possibility of associating values
with symbols and later retrieving them means that the interpreter
must maintain some sort of memory that keeps track of the
name-object pairs. This memory is called the <a name="%_idx_240"></a><em>environment</em> (more precisely the <a name="%_idx_242"></a><em>global environment</em>, since we will see
later that a computation may involve a number of different
environments).<a href="#footnote_Temp_15" name="call_footnote_Temp_15" id="call_footnote_Temp_15"><sup><small>9</small></sup></a></p>
<p><a name="%_sec_1.1.3"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.1.3">1.1.3 Evaluating
Combinations</a></h3>
<p><a name="%_idx_244"></a><a name="%_idx_246"></a> One of our
goals in this chapter is to isolate issues about thinking
procedurally. As a case in point, let us consider that, in
evaluating combinations, the interpreter is itself following a
procedure.</p>
<ul>
<li>To evaluate a combination, do the following:</li>
</ul>
<blockquote>
<p>1. Evaluate the subexpressions of the
combination.</p>
<p>2. Apply the procedure that is the value of the
leftmost subexpression (the operator) to the arguments that are
the values of the other subexpressions (the operands).</p>
</blockquote>
<p>Even this simple rule illustrates some important points about
processes in general. First, observe that the first step dictates
that in order to accomplish the evaluation process for a
combination we must first perform the evaluation process on each
element of the combination. Thus, the evaluation rule is <a name="%_idx_248"></a><em>recursive</em> in nature; that is, it
includes, as one of its steps, the need to invoke the rule
itself.<a href="#footnote_Temp_16" name="call_footnote_Temp_16" id="call_footnote_Temp_16"><sup><small>10</small></sup></a></p>
<p><a name="%_idx_250"></a>Notice how succinctly the idea of
recursion can be used to express what, in the case of a deeply
nested combination, would otherwise be viewed as a rather
complicated process. For example, evaluating</p>
<p><tt>(* (+ 2 (* 4 6))<br />
(+ 3 5 7))<br /></tt></p>
<p>requires that the evaluation rule be applied to four different
combinations. We can obtain a picture of this process by <a name="%_idx_252"></a>representing the combination in the form of a
<a name="%_idx_254"></a>tree, as shown in figure <a href="#%_fig_1.1">1.1</a>. Each combination is represented by a
<a name="%_idx_256"></a>node with <a name="%_idx_258"></a>branches corresponding to the operator and the
operands of the combination stemming from it. The <a name="%_idx_260"></a>terminal nodes (that is, nodes with no branches
stemming from them) represent either operators or numbers.
Viewing evaluation in terms of the tree, we can imagine that the
values of the operands percolate upward, starting from the
terminal nodes and then combining at higher and higher levels. In
general, we shall see that recursion is a very powerful technique
for dealing with hierarchical, treelike objects. In fact, the
``percolate values upward'' form of the evaluation rule is an
example of a general kind of process known as <a name="%_idx_262"></a><em>tree accumulation</em>.</p>
<p><a name="%_fig_1.1"></a></p>
<div align="left">
<div align="left">
<b>Figure 1.1:</b> Tree representation, showing
the value of each subcombination.
</div>
<table width="100%">
<tr>
<td><img src="ch1-Z-G-1.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>Next, observe that the repeated application of the first step
brings us to the point where we need to evaluate, not
combinations, but primitive expressions such as numerals,
built-in operators, or other names. We take care of the primitive
cases by stipulating that</p>
<p><a name="%_idx_264"></a><a name="%_idx_266"></a></p>
<ul>
<li>the values of numerals are the numbers that they name,</li>
<li>the values of built-in operators are the machine
instruction sequences that carry out the corresponding
operations, and</li>
<li>the values of other names are the objects associated with
those names in the environment.</li>
</ul>
<p>We may regard the second rule as a special case of the third
one by stipulating that symbols such as <tt>+</tt> and <tt>*</tt>
are also included in the global environment, and are associated
with the sequences of machine instructions that are their
``values.'' The key point to notice is the role of the <a name="%_idx_268"></a>environment in determining the meaning of the
symbols in expressions. In an interactive language such as Lisp,
it is meaningless to speak of the value of an expression such as
<tt>(+ x 1)</tt> without specifying any information about the
environment that would provide a meaning for the
symbol <tt>x</tt> (or even for the symbol <tt>+</tt>). As we
shall see in chapter 3, the general notion of the
environment as providing a context in which evaluation takes
place will play an important role in our understanding of program
execution.</p>
<p><a name="%_idx_270"></a>Notice that the evaluation rule given
above does not handle definitions. For instance, evaluating
<tt>(define x 3)</tt> does not apply <tt>define</tt> to two
arguments, one of which is the value of the symbol <tt>x</tt> and
the other of which is 3, since the purpose of the <tt>define</tt>
is precisely to associate <tt>x</tt> with a value. (That is,
<tt>(define x 3)</tt> is not a combination.)</p>
<p><a name="%_idx_272"></a>Such exceptions to the general
evaluation rule are called <em>special forms</em>.
<tt>Define</tt> is the only example of a special form that we
have seen so far, but we will meet others shortly. <a name="%_idx_274"></a>Each special form has its own evaluation rule.
The various kinds of expressions (each with its associated
evaluation rule) constitute the <a name="%_idx_276"></a>syntax of
the programming language. In comparison with most other
programming languages, Lisp has a very simple syntax; that is,
the evaluation rule for expressions can be described by a simple
general rule together with specialized rules for a small number
of special forms.<a href="#footnote_Temp_17" name="call_footnote_Temp_17" id="call_footnote_Temp_17"><sup><small>11</small></sup></a></p>
<p><a name="%_sec_1.1.4"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.1.4">1.1.4 Compound
Procedures</a></h3>
<p>We have identified in Lisp some of the elements that must
appear in any powerful programming language:</p>
<ul>
<li>Numbers and arithmetic operations are primitive data and
procedures.</li>
<li>Nesting of combinations provides a means of combining
operations.</li>
<li>Definitions that associate names with values provide a
limited means of abstraction.</li>
</ul>
<p>Now we will learn about <a name="%_idx_292"></a><em>procedure
definitions</em>, a much more powerful abstraction technique by
which a compound operation can be given a name and then referred
to as a unit.</p>
<p>We begin by examining how to express the idea of ``squaring.''
We might say, ``To square something, multiply it by itself.''
This is expressed in our language as</p>
<p><tt><a name="%_idx_294"></a>(define (square x) (* x x))<br />
</tt></p>
<p>We can understand this in the following way:</p>
<p>
<tt>(define (square x) (* x x))<br />
<img src="book-Z-G-D-16.gif" border="0" /> <img src="book-Z-G-D-16.gif" border="0" /> <img src="book-Z-G-D-16.gif" border="0" /> <img src="book-Z-G-D-16.gif" border="0" /> <img src="book-Z-G-D-16.gif" border="0" /> <img src="book-Z-G-D-16.gif" border="0" /><br />
To square something, multiply it by itself.<br />
</tt></p>
<p><a name="%_idx_296"></a><a name="%_idx_298"></a>We have here a
<em>compound procedure</em>, which has been given the name
<tt>square</tt>. The procedure represents the operation of
multiplying something by itself. The thing to be multiplied is
given a local name, <tt>x</tt>, which plays the same role that a
pronoun plays in natural language. <a name="%_idx_300"></a><a name="%_idx_302"></a><a name="%_idx_304"></a>Evaluating the definition creates this compound
procedure and associates it with the name
<tt>square</tt>.<a href="#footnote_Temp_18" name="call_footnote_Temp_18" id="call_footnote_Temp_18"><sup><small>12</small></sup></a></p>
<p><a name="%_idx_306"></a><a name="%_idx_308"></a>The general
form of a procedure definition is</p>
<p>
<tt>(define (<<em>name</em>> <<em>formal parameters</em>>) <<em>body</em>>)<br />
</tt></p>
<p><a name="%_idx_310"></a><a name="%_idx_312"></a>The
<<em>name</em>> is a symbol to be associated with the
procedure definition in the environment.<a href="#footnote_Temp_19" name="call_footnote_Temp_19" id="call_footnote_Temp_19"><sup><small>13</small></sup></a> The
<a name="%_idx_318"></a><a name="%_idx_320"></a><<em>formal
parameters</em>> are the names used within the body of the
procedure to refer to the corresponding arguments of the
procedure. The <a name="%_idx_322"></a><a name="%_idx_324"></a><<em>body</em>> is an expression that will
yield the value of the procedure application when the formal
parameters are replaced by the actual arguments to which the
procedure is applied.<a href="#footnote_Temp_20" name="call_footnote_Temp_20" id="call_footnote_Temp_20"><sup><small>14</small></sup></a> The
<<em>name</em>> and the <<em>formal parameters</em>>
are grouped within <a name="%_idx_328"></a>parentheses, just as
they would be in an actual call to the procedure being
defined.</p>
<p>Having defined <tt>square</tt>, we can now use it:</p>
<p><tt>(square 21)<br />
<i>441</i><br />
<br />
(square (+ 2 5))<br />
<i>49</i><br />
<br />
(square (square 3))<br />
<i>81</i><br /></tt></p>
<p>We can also use <tt>square</tt> as a building block in
defining other procedures. For example, <em>x</em><sup>2</sup> +
<em>y</em><sup>2</sup> can be expressed as</p>
<p><tt>(+ (square x) (square y))<br /></tt></p>
<p>We can easily define a procedure <tt>sum-of-squares</tt> that,
given any two numbers as arguments, produces the sum of their
squares:</p>
<p><tt><a name="%_idx_330"></a>(define (sum-of-squares x y)<br />
(+ (square x) (square y)))<br />
<br />
(sum-of-squares 3 4)<br />
<i>25</i><br /></tt></p>
<p>Now we can use <tt>sum-of-squares</tt> as a building block in
constructing further procedures:</p>
<p><tt>(define (f a)<br />
(sum-of-squares (+ a 1) (* a 2)))<br />
<br />
(f 5)<br />
<i>136</i><br /></tt></p>
<p><a name="%_idx_332"></a>Compound procedures are used in
exactly the same way as primitive procedures. Indeed, one could
not tell by looking at the definition of <tt>sum-of-squares</tt>
given above whether <tt>square</tt> was built into the
interpreter, like <tt>+</tt> and <tt>*</tt>, or defined as a
compound procedure.</p>
<p><a name="%_sec_1.1.5"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.1.5">1.1.5 The
Substitution Model for Procedure Application</a></h3>
<p><a name="%_idx_334"></a> To evaluate a combination whose
operator names a compound procedure, the interpreter follows much
the same process as for combinations whose operators name
primitive procedures, which we described in section <a href="#%_sec_1.1.3">1.1.3</a>. That is, the interpreter evaluates the
elements of the combination and applies the procedure (which is
the value of the operator of the combination) to the arguments
(which are the values of the operands of the combination).</p>
<p>We can assume that the mechanism for applying primitive
procedures to arguments is built into the interpreter. For
compound procedures, the application process is as follows:</p>
<ul>
<li>To apply a compound procedure to arguments, evaluate the
body of the procedure with each formal parameter replaced by
the corresponding argument.</li>
</ul>
<p>To illustrate this process, let's evaluate the combination</p>
<p><tt>(f 5)<br /></tt></p>
<p>where <tt>f</tt> is the procedure defined in
section <a href="#%_sec_1.1.4">1.1.4</a>. We begin by
retrieving the body of <tt>f</tt>:</p>
<p>
<tt>(sum-of-squares (+ a 1) (* a 2))<br />
</tt></p>
<p>Then we replace the formal parameter <tt>a</tt> by the
argument 5:</p>
<p>
<tt>(sum-of-squares (+ 5 1) (* 5 2))<br />
</tt></p>
<p>Thus the problem reduces to the evaluation of a combination
with two operands and an operator <tt>sum-of-squares</tt>.
Evaluating this combination involves three subproblems. We must
evaluate the operator to get the procedure to be applied, and we
must evaluate the operands to get the arguments. Now <tt>(+ 5
1)</tt> produces 6 and <tt>(* 5 2)</tt> produces 10, so we must
apply the <tt>sum-of-squares</tt> procedure to 6 and 10. These
values are substituted for the formal parameters <tt>x</tt> and
<tt>y</tt> in the body of <tt>sum-of-squares</tt>, reducing the
expression to</p>
<p>
<tt>(+ (square 6) (square 10))<br /></tt></p>
<p>If we use the definition of <tt>square</tt>, this reduces
to</p>
<p>
<tt>(+ (* 6 6) (* 10 10))<br /></tt></p>
<p>which reduces by multiplication to</p>
<p><tt>(+ 36 100)<br /></tt></p>
<p>and finally to</p>
<p><tt>136<br /></tt></p>
<p>The process we have just described is called the
<em>substitution model</em> for procedure application. It can be
taken as a model that determines the ``meaning'' of procedure
application, insofar as the procedures in this chapter are
concerned. However, there are two points that should be
stressed:</p>
<ul>
<li>The purpose of the substitution is to help us think about
procedure application, not to provide a description of how the
interpreter really works. Typical interpreters do not evaluate
procedure applications by manipulating the text of a procedure
to substitute values for the formal parameters. In practice,
the ``substitution'' is accomplished by using a local
environment for the formal parameters. We will discuss this
more fully in chapters 3 and 4 when we examine the
implementation of an interpreter in detail.</li>
<li>Over the course of this book, we will present a sequence of
increasingly elaborate models of how interpreters work,
culminating with a complete implementation of an interpreter
and compiler in chapter 5. The substitution model is only
the first of these models -- a way to get started thinking
formally about the evaluation process. In general, when
<a name="%_idx_336"></a>modeling phenomena in science and
engineering, we begin with simplified, incomplete models. As we
examine things in greater detail, these simple models become
inadequate and must be replaced by more refined models. The
substitution model is no exception. In particular, when we
address in chapter 3 the use of procedures with ``mutable
data,'' we will see that the substitution model breaks down and
must be replaced by a more complicated model of procedure
application.<a href="#footnote_Temp_21" name="call_footnote_Temp_21" id="call_footnote_Temp_21"><sup><small>15</small></sup></a></li>
</ul>
<p><a name="%_sec_Temp_22"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_22">Applicative
order versus normal order</a></h4>
<p>According to the description of evaluation given in
section <a href="#%_sec_1.1.3">1.1.3</a>, the interpreter
first evaluates the operator and operands and then applies the
resulting procedure to the resulting arguments. This is not the
only way to perform evaluation. An alternative evaluation model
would not evaluate the operands until their values were needed.
Instead it would first substitute operand expressions for
parameters until it obtained an expression involving only
primitive operators, and would then perform the evaluation. If we
used this method, the evaluation of</p>
<p><tt>(f 5)<br /></tt></p>
<p>would proceed according to the sequence of expansions</p>
<p>
<tt>(sum-of-squares (+ 5 1) (* 5 2))<br />
<br />
(+ (square (+ 5 1)) (square (* 5 2)) )<br />
<br />
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))<br />
</tt></p>
<p>followed by the reductions</p>
<p>
<tt>(+ (* 6 6) (* 10 10))<br />
<br />
(+ 36 100)<br />
<br />
136<br />
</tt></p>
<p>This gives the same answer as our previous evaluation model,
but the process is different. In particular, the evaluations of
<tt>(+ 5 1)</tt> and <tt>(* 5 2)</tt> are each
performed twice here, corresponding to the reduction of the
expression</p>
<p><tt>(* x x)<br /></tt></p>
<p>with <tt>x</tt> replaced respectively by <tt>(+ 5 1)</tt> and
<tt>(* 5 2)</tt>.</p>
<p>This alternative ``fully expand and then reduce'' evaluation
method is known as <a name="%_idx_340"></a><em>normal-order
evaluation</em>, in contrast to the ``evaluate the arguments and
then apply'' method that the interpreter actually uses, which is
called <a name="%_idx_342"></a><em>applicative-order
evaluation</em>. It can be shown that, for procedure applications
that can be modeled using substitution (including all the
procedures in the first two chapters of this book) and that yield
legitimate values, normal-order and applicative-order evaluation
produce the same value. (See exercise <a href="#%_thm_1.5">1.5</a> for an instance of an ``illegitimate'' value
where normal-order and applicative-order evaluation do not give
the same result.)</p>
<p><a name="%_idx_344"></a><a name="%_idx_346"></a>Lisp uses
applicative-order evaluation, partly because of the additional
efficiency obtained from avoiding multiple evaluations of
expressions such as those illustrated with <tt>(+ 5 1)</tt> and
<tt>(* 5 2)</tt> above and, more significantly, because
normal-order evaluation becomes much more complicated to deal
with when we leave the realm of procedures that can be modeled by
substitution. On the other hand, normal-order evaluation can be
an extremely valuable tool, and we will investigate some of its
implications in chapters 3 and 4.<a href="#footnote_Temp_23" name="call_footnote_Temp_23" id="call_footnote_Temp_23"><sup><small>16</small></sup></a></p>
<p><a name="%_sec_1.1.6"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.1.6">1.1.6 Conditional
Expressions and Predicates</a></h3>
<p>The expressive power of the class of procedures that we can
define at this point is very limited, because we have no way to
make tests and to perform different operations depending on the
result of a test. For instance, we cannot define a procedure that
computes the <a name="%_idx_348"></a>absolute value of a number
by testing whether the number is positive, negative, or zero and
taking different actions in the different cases according to the
rule</p>
<div align="left"><img src="ch1-Z-G-2.gif" border="0" /></div>
<p><a name="%_idx_350"></a>This construct is called a <em>case
analysis</em>, and there is a special form in Lisp for notating
such a case analysis. It is called <a name="%_idx_352"></a><a name="%_idx_354"></a><a name="%_idx_356"></a><tt>cond</tt> (which stands for ``conditional''),
and it is used as follows:</p>
<p><tt><a name="%_idx_358"></a>(define (abs x)<br />
(cond ((> x 0) x)<br />
((= x 0) 0)<br />
((< x 0) (- x))))<br />
</tt></p>
<p>The general form of a conditional expression is</p>
<p>
<tt>(cond (<<em>p<sub>1</sub></em>> <<em>e<sub>1</sub></em>>)<br />
(<<em>p<sub>2</sub></em>> <<em>e<sub>2</sub></em>>)<br />
<img src="book-Z-G-D-18.gif" border="0" /><br />
(<<em>p<sub><em>n</em></sub></em>> <<em>e<sub><em>n</em></sub></em>>))<br />
</tt></p>
<p>consisting of the symbol <tt>cond</tt> followed by <a name="%_idx_360"></a>parenthesized pairs of expressions
<tt>(<<em>p</em>> <<em>e</em>>)</tt> called
<a name="%_idx_362"></a><a name="%_idx_364"></a><em>clauses</em>.
The first expression in each pair is a <a name="%_idx_366"></a><em>predicate</em> -- that is, an expression
whose value is interpreted as either true or false.<a href="#footnote_Temp_24" name="call_footnote_Temp_24" id="call_footnote_Temp_24"><sup><small>17</small></sup></a></p>
<p><a name="%_idx_384"></a><a name="%_idx_386"></a>Conditional
expressions are evaluated as follows. The predicate
<<em>p<sub>1</sub></em>> is evaluated first. If its value
is false, then <<em>p<sub>2</sub></em>> is evaluated. If
<<em>p<sub>2</sub></em>>'s value is also false, then
<<em>p<sub>3</sub></em>> is evaluated. This process
continues until a predicate is found whose value is true, in
which case the interpreter returns the value of the corresponding
<a name="%_idx_388"></a><em>consequent expression</em>
<<em>e</em>> of the clause as the value of the conditional
expression. If none of the <<em>p</em>>'s is found to be
true, the value of the <tt>cond</tt> is undefined.</p>
<p><a name="%_idx_390"></a>The word <em>predicate</em> is used
for procedures that return true or false, as well as for
expressions that evaluate to true or false. The absolute-value
procedure <tt>abs</tt> makes use of the <a name="%_idx_392"></a><a name="%_idx_394"></a><a name="%_idx_396"></a><a name="%_idx_398"></a><a name="%_idx_400"></a><a name="%_idx_402"></a><a name="%_idx_404"></a><a name="%_idx_406"></a><a name="%_idx_408"></a>primitive predicates <tt>></tt>,
<tt><</tt>, and <tt>=</tt>.<a href="#footnote_Temp_25" name="call_footnote_Temp_25" id="call_footnote_Temp_25"><sup><small>18</small></sup></a> These
take two numbers as arguments and test whether the first number
is, respectively, greater than, less than, or equal to the second
number, returning true or false accordingly.</p>
<p>Another way to write the absolute-value procedure is</p>
<p><tt><a name="%_idx_414"></a>(define (abs x)<br />
(cond ((< x 0) (- x))<br />
(else x)))<br />
</tt></p>
<p>which could be expressed in English as ``If <em>x</em> is less
than zero return - <em>x</em>; otherwise return <em>x</em>.''
<a name="%_idx_416"></a><tt>Else</tt> is a special symbol that
can be used in place of the <<em>p</em>> in the final
clause of a <tt>cond</tt>. This causes the <tt>cond</tt> to
return as its value the value of the corresponding
<<em>e</em>> whenever all previous clauses have been
bypassed. In fact, any expression that always evaluates to a true
value could be used as the <<em>p</em>> here.</p>
<p>Here is yet another way to write the absolute-value
procedure:</p>
<p><tt><a name="%_idx_418"></a>(define (abs x)<br />
(if (< x 0)<br />
(- x)<br />
x))<br /></tt></p>
<p><a name="%_idx_420"></a><a name="%_idx_422"></a><a name="%_idx_424"></a>This uses the special form <tt>if</tt>, a
restricted type of conditional that can be used when there are
precisely <a name="%_idx_426"></a>two cases in the case analysis.
The general form of an <tt>if</tt> expression is</p>
<p>
<tt>(if <<em>predicate</em>> <<em>consequent</em>> <<em>alternative</em>>)<br />
</tt></p>
<p><a name="%_idx_428"></a><a name="%_idx_430"></a><a name="%_idx_432"></a>To evaluate an <tt>if</tt> expression, the
interpreter starts by evaluating the <a name="%_idx_434"></a><<em>predicate</em>> part of the
expression. If the <<em>predicate</em>> evaluates to a true
value, the interpreter then evaluates the <a name="%_idx_436"></a><<em>consequent</em>> and returns its
value. Otherwise it evaluates the <a name="%_idx_438"></a><<em>alternative</em>> and returns its
value.<a href="#footnote_Temp_26" name="call_footnote_Temp_26" id="call_footnote_Temp_26"><sup><small>19</small></sup></a></p>
<p>In addition to primitive predicates such as <tt><</tt>,
<tt>=</tt>, and <tt>></tt>, there are logical composition
operations, which enable us to construct compound predicates. The
three most frequently used are these:</p>
<ul>
<li>
<tt>(and <<em>e<sub>1</sub></em>> <tt>...</tt>
<<em>e<sub><em>n</em></sub></em>>)</tt>
<p>The interpreter evaluates the expressions
<<em>e</em>> one at a time, in left-to-right order. If
any <<em>e</em>> evaluates to false, the value of the
<tt>and</tt> expression is false, and the rest of the
<<em>e</em>>'s are not evaluated. If all
<<em>e</em>>'s evaluate to true values, the value of
the <tt>and</tt> expression is the value of the last one.</p>
<p><a name="%_idx_454"></a><a name="%_idx_456"></a><a name="%_idx_458"></a><a name="%_idx_460"></a></p>
</li>
<li>
<tt>(or <<em>e<sub>1</sub></em>> <tt>...</tt>
<<em>e<sub><em>n</em></sub></em>>)</tt>
<p>The interpreter evaluates the expressions
<<em>e</em>> one at a time, in left-to-right order. If
any <<em>e</em>> evaluates to a true value, that value
is returned as the value of the <tt>or</tt> expression, and
the rest of the <<em>e</em>>'s are not evaluated. If
all <<em>e</em>>'s evaluate to false, the value of the
<tt>or</tt> expression is false.</p>
<p><a name="%_idx_462"></a><a name="%_idx_464"></a></p>
</li>
<li>
<tt>(not <<em>e</em>>)</tt>
<p>The value of a <tt>not</tt> expression is true when the
expression <<em>e</em>> evaluates to false, and false
otherwise.</p>
</li>
</ul>
<p><a name="%_idx_466"></a><a name="%_idx_468"></a>Notice that
<tt>and</tt> and <tt>or</tt> are special forms, not procedures,
because the subexpressions are not necessarily all evaluated.
<tt>Not</tt> is an ordinary procedure.</p>
<p>As an example of how these are used, the condition that a
number <em>x</em> be in the range 5 < <em>x</em> < 10 may
be expressed as</p>
<p>
<tt>(and (> x 5) (< x 10))<br />
</tt></p>
<p>As another example, we can define a predicate to test whether
one number is greater than or equal to another as</p>
<p><tt><a name="%_idx_470"></a>(define (>= x y)<br />
(or (> x y) (= x y)))<br />
</tt></p>
<p>or alternatively as</p>
<p><tt><a name="%_idx_472"></a>(define (>= x y)<br />
(not (< x y)))<br /></tt></p>
<p><a name="%_thm_1.1"></a> <b>Exercise 1.1.</b> Below
is a sequence of expressions. What is the result printed by the
interpreter in response to each expression? Assume that the
sequence is to be evaluated in the order in which it is
presented.</p>
<p><tt>10<br />
(+ 5 3 4)<br />
(- 9 1)<br />
(/ 6 2)<br />
(+ (* 2 4) (- 4 6))<br />
(define a 3)<br />
(define b (+ a 1))<br />
(+ a b (* a b))<br />
(= a b)<br />
(if (and (> b a) (< b (* a b)))<br />
b<br />
a)<br />
(cond ((= a 4) 6)<br />
((= b 4) (+ 6 7 a))<br />
(else 25))<br />
(+ 2 (if (> b a) b a))<br />
(* (cond ((> a b) a)<br />
((< a b) b)<br />
(else -1))<br />
(+ a 1))<br /></tt></p>
<p><a name="%_thm_1.2"></a> <b>Exercise
1.2.</b> Translate the following expression into
prefix form</p>
<div align="left"><img src="ch1-Z-G-3.gif" border="0" /></div>
<p><a name="%_thm_1.3"></a> <b>Exercise
1.3.</b> Define a procedure that takes three numbers
as arguments and returns the sum of the squares of the two larger
numbers.</p>
<p><a name="%_thm_1.4"></a> <b>Exercise
1.4.</b> <a name="%_idx_474"></a><a name="%_idx_476"></a><a name="%_idx_478"></a>Observe that our model of
evaluation allows for combinations whose operators are compound
expressions. Use this observation to describe the behavior of the
following procedure:</p>
<p><tt>(define (a-plus-abs-b a b)<br />
((if (> b 0) + -) a b))<br />
</tt></p>
<p><a name="%_thm_1.5"></a> <b>Exercise
1.5.</b> <a name="%_idx_480"></a><a name="%_idx_482"></a>Ben Bitdiddle has invented a test to determine
whether the interpreter he is faced with is using
applicative-order evaluation or normal-order evaluation. He
defines the following two procedures:</p>
<p><tt>(define (p) (p))<br />
<br />
(define (test x y)<br />
(if (= x 0)<br />
0<br />
y))<br /></tt></p>
<p>Then he evaluates the expression</p>
<p><tt>(test 0 (p))<br /></tt></p>
<p>What behavior will Ben observe with an interpreter that uses
applicative-order evaluation? What behavior will he observe with
an interpreter that uses normal-order evaluation? Explain your
answer. <a name="%_idx_484"></a><a name="%_idx_486"></a>(Assume
that the evaluation rule for the special form <tt>if</tt> is the
same whether the interpreter is using normal or applicative
order: The predicate expression is evaluated first, and the
result determines whether to evaluate the consequent or the
alternative expression.)</p>
<p><a name="%_sec_1.1.7"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.1.7">1.1.7 Example:
Square Roots by Newton's Method</a></h3>
<p><a name="%_idx_488"></a><a name="%_idx_490"></a>Procedures, as
introduced above, are much like ordinary mathematical functions.
They specify a value that is determined by one or more
parameters. But there is an important difference between
mathematical functions and computer procedures. Procedures must
be effective.</p>
<p>As a case in point, consider the problem of computing square
roots. We can define the square-root function as</p>
<div align="left"><img src="ch1-Z-G-4.gif" border="0" /></div>
<p>This describes a perfectly legitimate mathematical function.
We could use it to recognize whether one number is the square
root of another, or to derive facts about square roots in
general. On the other hand, the definition does not describe a
procedure. Indeed, it tells us almost nothing about how to
actually find the square root of a given number. It will not help
matters to rephrase this definition in pseudo-Lisp:</p>
<p><tt>(define (sqrt x)<br />
(the y (and (>= y 0)<br />
(= (square y) x))))<br />
</tt></p>
<p>This only begs the question.</p>
<p>The contrast between function and procedure is a reflection of
the general distinction between describing properties of things
and describing how to do things, or, as it is sometimes referred
to, the distinction between <a name="%_idx_492"></a><a name="%_idx_494"></a>declarative knowledge and imperative knowledge.
In <a name="%_idx_496"></a><a name="%_idx_498"></a>mathematics we
are usually concerned with declarative (what is) descriptions,
whereas in computer science we are usually concerned with
imperative (how to) descriptions.<a href="#footnote_Temp_32" name="call_footnote_Temp_32" id="call_footnote_Temp_32"><sup><small>20</small></sup></a></p>
<p><a name="%_idx_508"></a><a name="%_idx_510"></a>How does one
compute square roots? The most common way is to use Newton's
method of successive approximations, which says that whenever we
have a guess <em>y</em> for the value of the square root of a
number <em>x</em>, we can perform a simple manipulation to get a
better guess (one closer to the actual square root) by averaging
<em>y</em> with <em>x</em>/<em>y</em>.<a href="#footnote_Temp_33" name="call_footnote_Temp_33" id="call_footnote_Temp_33"><sup><small>21</small></sup></a> For
example, we can compute the square root of 2 as follows. Suppose
our initial guess is 1:</p>
<table border="0">
<tr>
<td valign="top">Guess</td>
<td valign="top">Quotient</td>
<td valign="top">Average</td>
</tr>
<tr>
<td valign="top"> </td>
</tr>
<tr>
<td valign="top">1</td>
<td valign="top">(2/1) = 2</td>
<td valign="top">((2 + 1)/2) = 1.5</td>
</tr>
<tr>
<td valign="top"> </td>
</tr>
<tr>
<td valign="top">1.5</td>
<td valign="top">(2/1.5) = 1.3333</td>
<td valign="top">((1.3333 + 1.5)/2) = 1.4167</td>
</tr>
<tr>
<td valign="top"> </td>
</tr>
<tr>
<td valign="top">1.4167</td>
<td valign="top">(2/1.4167) = 1.4118</td>