forked from twcamper/sicp-kindle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-5.html
222 lines (202 loc) · 11.6 KB
/
book-Z-H-5.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
<!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="%_chap_Temp_2"></a></p>
<div class="chapterheading">
<h1 class="chapter"><a href="book-Z-H-4.html#%_toc_%_chap_Temp_2">Foreword</a></h1>
</div>
<p>Educators, generals, dieticians, psychologists, and parents
program. Armies, students, and some societies are programmed. An
assault on large problems employs a succession of programs, most
of which spring into existence en route. These programs are rife
with issues that appear to be particular to the problem at hand.
To appreciate programming as an intellectual activity in its own
right you must turn to computer programming; you must read and
write computer programs -- many of them. It doesn't matter much
what the programs are about or what applications they serve. What
does matter is how well they perform and how smoothly they fit
with other programs in the creation of still greater programs.
The programmer must seek both perfection of part and adequacy of
collection. In this book the use of ``program'' is focused on the
creation, execution, and study of programs written in a dialect
of Lisp for execution on a digital computer. Using Lisp we
restrict or limit not what we may program, but only the notation
for our program descriptions.</p>
<p>Our traffic with the subject matter of this book involves us
with three foci of phenomena: the human mind, collections of
computer programs, and the computer. Every computer program is a
model, hatched in the mind, of a real or mental process. These
processes, arising from human experience and thought, are huge in
number, intricate in detail, and at any time only partially
understood. They are modeled to our permanent satisfaction rarely
by our computer programs. Thus even though our programs are
carefully handcrafted discrete collections of symbols, mosaics of
interlocking functions, they continually evolve: we change them
as our perception of the model deepens, enlarges, generalizes
until the model ultimately attains a metastable place within
still another model with which we struggle. The source of the
exhilaration associated with computer programming is the
continual unfolding within the mind and on the computer of
mechanisms expressed as programs and the explosion of perception
they generate. If art interprets our dreams, the computer
executes them in the guise of programs!</p>
<p>For all its power, the computer is a harsh taskmaster. Its
programs must be correct, and what we wish to say must be said
accurately in every detail. As in every other symbolic activity,
we become convinced of program truth through argument. Lisp
itself can be assigned a semantics (another model, by the way),
and if a program's function can be specified, say, in the
predicate calculus, the proof methods of logic can be used to
make an acceptable correctness argument. Unfortunately, as
programs get large and complicated, as they almost always do, the
adequacy, consistency, and correctness of the specifications
themselves become open to doubt, so that complete formal
arguments of correctness seldom accompany large programs. Since
large programs grow from small ones, it is crucial that we
develop an arsenal of standard program structures of whose
correctness we have become sure -- we call them idioms -- and
learn to combine them into larger structures using organizational
techniques of proven value. These techniques are treated at
length in this book, and understanding them is essential to
participation in the Promethean enterprise called programming.
More than anything else, the uncovering and mastery of powerful
organizational techniques accelerates our ability to create
large, significant programs. Conversely, since writing large
programs is very taxing, we are stimulated to invent new methods
of reducing the mass of function and detail to be fitted into
large programs.</p>
<p>Unlike programs, computers must obey the laws of physics. If
they wish to perform rapidly -- a few nanoseconds per state
change -- they must transmit electrons only small distances (at
most 1 <small><sup>1</sup>/<small>2</small></small> feet). The
heat generated by the huge number of devices so concentrated in
space has to be removed. An exquisite engineering art has been
developed balancing between multiplicity of function and density
of devices. In any event, hardware always operates at a level
more primitive than that at which we care to program. The
processes that transform our Lisp programs to ``machine''
programs are themselves abstract models which we program. Their
study and creation give a great deal of insight into the
organizational programs associated with programming arbitrary
models. Of course the computer itself can be so modeled. Think of
it: the behavior of the smallest physical switching element is
modeled by quantum mechanics described by differential equations
whose detailed behavior is captured by numerical approximations
represented in computer programs executing on computers composed
of <tt>...</tt>!</p>
<p>It is not merely a matter of tactical convenience to
separately identify the three foci. Even though, as they say,
it's all in the head, this logical separation induces an
acceleration of symbolic traffic between these foci whose
richness, vitality, and potential is exceeded in human experience
only by the evolution of life itself. At best, relationships
between the foci are metastable. The computers are never large
enough or fast enough. Each breakthrough in hardware technology
leads to more massive programming enterprises, new organizational
principles, and an enrichment of abstract models. Every reader
should ask himself periodically ``Toward what end, toward what
end?'' -- but do not ask it too often lest you pass up the fun of
programming for the constipation of bittersweet philosophy.</p>
<p>Among the programs we write, some (but never enough) perform a
precise mathematical function such as sorting or finding the
maximum of a sequence of numbers, determining primality, or
finding the square root. We call such programs algorithms, and a
great deal is known of their optimal behavior, particularly with
respect to the two important parameters of execution time and
data storage requirements. A programmer should acquire good
algorithms and idioms. Even though some programs resist precise
specifications, it is the responsibility of the programmer to
estimate, and always to attempt to improve, their
performance.</p>
<p>Lisp is a survivor, having been in use for about a quarter of
a century. Among the active programming languages only Fortran
has had a longer life. Both languages have supported the
programming needs of important areas of application, Fortran for
scientific and engineering computation and Lisp for artificial
intelligence. These two areas continue to be important, and their
programmers are so devoted to these two languages that Lisp and
Fortran may well continue in active use for at least another
quarter-century.</p>
<p>Lisp changes. The Scheme dialect used in this text has evolved
from the original Lisp and differs from the latter in several
important ways, including static scoping for variable binding and
permitting functions to yield functions as values. In its
semantic structure Scheme is as closely akin to Algol 60 as to
early Lisps. Algol 60, never to be an active language again,
lives on in the genes of Scheme and Pascal. It would be difficult
to find two languages that are the communicating coin of two more
different cultures than those gathered around these two
languages. Pascal is for building pyramids -- imposing,
breathtaking, static structures built by armies pushing heavy
blocks into place. Lisp is for building organisms -- imposing,
breathtaking, dynamic structures built by squads fitting
fluctuating myriads of simpler organisms into place. The
organizing principles used are the same in both cases, except for
one extraordinarily important difference: The discretionary
exportable functionality entrusted to the individual Lisp
programmer is more than an order of magnitude greater than that
to be found within Pascal enterprises. Lisp programs inflate
libraries with functions whose utility transcends the application
that produced them. The list, Lisp's native data structure, is
largely responsible for such growth of utility. The simple
structure and natural applicability of lists are reflected in
functions that are amazingly nonidiosyncratic. In Pascal the
plethora of declarable data structures induces a specialization
within functions that inhibits and penalizes casual cooperation.
It is better to have 100 functions operate on one data structure
than to have 10 functions operate on 10 data structures. As a
result the pyramid must stand unchanged for a millennium; the
organism must evolve or perish.</p>
<p>To illustrate this difference, compare the treatment of
material and exercises within this book with that in any
first-course text using Pascal. Do not labor under the illusion
that this is a text digestible at MIT only, peculiar to the breed
found there. It is precisely what a serious book on programming
Lisp must be, no matter who the student is or where it is
used.</p>
<p>Note that this is a text about programming, unlike most Lisp
books, which are used as a preparation for work in artificial
intelligence. After all, the critical programming concerns of
software engineering and artificial intelligence tend to coalesce
as the systems under investigation become larger. This explains
why there is such growing interest in Lisp outside of artificial
intelligence.</p>
<p>As one would expect from its goals, artificial intelligence
research generates many significant programming problems. In
other programming cultures this spate of problems spawns new
languages. Indeed, in any very large programming task a useful
organizing principle is to control and isolate traffic within the
task modules via the invention of language. These languages tend
to become less primitive as one approaches the boundaries of the
system where we humans interact most often. As a result, such
systems contain complex language-processing functions replicated
many times. Lisp has such a simple syntax and semantics that
parsing can be treated as an elementary task. Thus parsing
technology plays almost no role in Lisp programs, and the
construction of language processors is rarely an impediment to
the rate of growth and change of large Lisp systems. Finally, it
is this very simplicity of syntax and semantics that is
responsible for the burden and freedom borne by all Lisp
programmers. No Lisp program of any size beyond a few lines can
be written without being saturated with discretionary functions.
Invent and fit; have fits and reinvent! We toast the Lisp
programmer who pens his thoughts within nests of parentheses.</p>
<div align="left">
<table>
<tr>
<td>Alan J. Perlis<br />
New Haven, Connecticut</td>
</tr>
</table>
</div>
</body>
</html>