forked from twcamper/sicp-kindle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-25.html
218 lines (195 loc) · 11.8 KB
/
book-Z-H-25.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
<!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_4"></a></p>
<div class="chapterheading">
<h3 class="chapter"><a href="book-Z-H-4.html#%_toc_%_chap_4">Chapter 4</a></h3>
<h1>Metalinguistic Abstraction</h1>
</div>
<div align="right">
<table width="60%">
<tr>
<td>
<div><span class="epigraph">"<tt>...</tt> It's in words that the magic is -- Abracadabra, Open Sesame, and the rest --
but the magic words in one story aren't magical in the next. The real magic is to understand which words work,
and when, and for what; the trick is to learn the trick.<br />
<tt>...</tt> And those words are made from the letters of our alphabet: a couple-dozen squiggles we can draw with
the pen. This is the key! And the treasure, too, if we can only get our hands on it! It's as if -- as if the key
to the treasure <em>is</em> the treasure!"</span></div>
<div><span class="epigraph attrib"><a name="%_idx_4188"></a>John Barth, <em>Chimera</em></span></div>
</td>
</tr>
</table>
</div>
<p>In our study of program design, we have seen that expert
programmers control the complexity of their designs with the same
general techniques used by designers of all complex systems. They
combine primitive elements to form compound objects, they
abstract compound objects to form higher-level building blocks,
and they preserve modularity by adopting appropriate large-scale
views of system structure. In illustrating these techniques, we
have used Lisp as a language for describing processes and for
constructing computational data objects and processes to model
complex phenomena in the real world. However, as we confront
increasingly complex problems, we will find that Lisp, or indeed
any fixed programming language, is not sufficient for our needs.
We must constantly turn to new languages in order to express our
ideas more effectively. Establishing new languages is a powerful
strategy for controlling complexity in engineering design; we can
often enhance our ability to deal with a complex problem by
adopting a new language that enables us to describe (and hence to
think about) the problem in a different way, using primitives,
means of combination, and means of abstraction that are
particularly well suited to the problem at hand.<a href="#footnote_Temp_508" name="call_footnote_Temp_508" id="call_footnote_Temp_508"><sup><small>1</small></sup></a></p>
<p><a name="%_idx_4190"></a><a name="%_idx_4192"></a>Programming
is endowed with a multitude of languages. There are physical
languages, such as the machine languages for particular
computers. These languages are concerned with the representation
of data and control in terms of individual bits of storage and
primitive machine instructions. The machine-language programmer
is concerned with using the given hardware to erect systems and
utilities for the efficient implementation of resource-limited
computations. High-level languages, erected on a machine-language
substrate, hide concerns about the representation of data as
collections of bits and the representation of programs as
sequences of primitive instructions. These languages have means
of combination and abstraction, such as procedure definition,
that are appropriate to the larger-scale organization of
systems.</p>
<p><a name="%_idx_4194"></a><a name="%_idx_4196"></a><em>Metalinguistic abstraction</em> --
establishing new languages -- plays an important role in all
branches of engineering design. It is particularly important to
computer programming, because in programming not only can we
formulate new languages but we can also implement these languages
by constructing evaluators. An <a name="%_idx_4198"></a><em>evaluator</em> (or <em>interpreter</em>) for
a programming language is a procedure that, when applied to an
expression of the language, performs the actions required to
evaluate that expression.</p>
<p>It is no exaggeration to regard this as the most fundamental
idea in programming:</p>
<blockquote>
The evaluator, which determines the meaning of expressions in a
programming language, is just another program.
</blockquote>To appreciate this point is to change our images of
ourselves as programmers. We come to see ourselves as designers
of languages, rather than only users of languages designed by
others.
<p>In fact, we can regard almost any program as the evaluator for
some language. For instance, the polynomial manipulation system
of section <a href="book-Z-H-18.html#%_sec_2.5.3">2.5.3</a>
embodies the rules of polynomial arithmetic and implements them
in terms of operations on list-structured data. If we augment
this system with procedures to read and print polynomial
expressions, we have the core of a special-purpose language for
dealing with problems in symbolic mathematics. The digital-logic
simulator of section <a href="book-Z-H-22.html#%_sec_3.3.4">3.3.4</a> and the constraint
propagator of section <a href="book-Z-H-22.html#%_sec_3.3.5">3.3.5</a> are legitimate languages
in their own right, each with its own primitives, means of
combination, and means of abstraction. Seen from this
perspective, the technology for coping with large-scale computer
systems merges with the technology for building new computer
languages, and <a name="%_idx_4200"></a>computer science itself
becomes no more (and no less) than the discipline of constructing
appropriate descriptive languages.</p>
<p>We now embark on a tour of the technology by which languages
are established in terms of other languages. In this chapter we
shall use Lisp as a base, implementing evaluators as Lisp
procedures. <a name="%_idx_4202"></a>Lisp is particularly well
suited to this task, because of its ability to represent and
manipulate symbolic expressions. We will take the first step in
understanding how languages are implemented by building an
evaluator for Lisp itself. The language implemented by our
evaluator will be a subset of the Scheme dialect of Lisp that we
use in this book. Although the evaluator described in this
chapter is written for a particular dialect of Lisp, it contains
the essential structure of an evaluator for any
expression-oriented language designed for writing programs for a
sequential machine. (In fact, most language processors contain,
deep within them, a little ``Lisp'' evaluator.) The evaluator has
been simplified for the purposes of illustration and discussion,
and some features have been left out that would be important to
include in a production-quality Lisp system. Nevertheless, this
simple evaluator is adequate to execute most of the programs in
this book.<a href="#footnote_Temp_509" name="call_footnote_Temp_509" id="call_footnote_Temp_509"><sup><small>2</small></sup></a></p>
<p>An important advantage of making the evaluator accessible as a
Lisp program is that we can implement alternative evaluation
rules by describing these as modifications to the evaluator
program. One place where we can use this power to good effect is
to gain extra control over the ways in which computational models
embody the notion of time, which was so central to the discussion
in chapter 3. There, we mitigated some of the complexities
of state and assignment by using streams to decouple the
representation of time in the world from time in the computer.
Our stream programs, however, were sometimes cumbersome, because
they were constrained by the applicative-order evaluation of
Scheme. In section <a href="book-Z-H-27.html#%_sec_4.2">4.2</a>, we'll change the underlying
language to provide for a more elegant approach, by modifying the
evaluator to provide for <em>normal-order evaluation</em>.</p>
<p>Section <a href="book-Z-H-28.html#%_sec_4.3">4.3</a>
implements a more ambitious linguistic change, whereby
expressions have many values, rather than just a single value. In
this language of <em>nondeterministic computing</em>, it is
natural to express processes that generate all possible values
for expressions and then search for those values that satisfy
certain constraints. In terms of models of computation and time,
this is like having time branch into a set of ``possible
futures'' and then searching for appropriate time lines. With our
nondeterministic evaluator, keeping track of multiple values and
performing searches are handled automatically by the underlying
mechanism of the language.</p>
<p>In section <a href="book-Z-H-29.html#%_sec_4.4">4.4</a>
we implement a <em>logic-programming</em> language in which
knowledge is expressed in terms of relations, rather than in
terms of computations with inputs and outputs. Even though this
makes the language drastically different from Lisp, or indeed
from any conventional language, we will see that the
logic-programming evaluator shares the essential structure of the
Lisp evaluator.</p>
<div class="smallprint">
<hr />
</div>
<div class="footnote">
<p><a href="#call_footnote_Temp_508" name="footnote_Temp_508" id="footnote_Temp_508"><sup><small>1</small></sup></a> The same
idea is pervasive throughout all of engineering. For example,
electrical engineers use many different languages for
describing circuits. Two of these are the language of
electrical <em>networks</em> and the language of electrical
<em>systems</em>. The network language emphasizes the physical
modeling of devices in terms of discrete electrical elements.
The primitive objects of the network language are primitive
electrical components such as resistors, capacitors, inductors,
and transistors, which are characterized in terms of physical
variables called voltage and current. When describing circuits
in the network language, the engineer is concerned with the
physical characteristics of a design. In contrast, the
primitive objects of the system language are signal-processing
modules such as filters and amplifiers. Only the functional
behavior of the modules is relevant, and signals are
manipulated without concern for their physical realization as
voltages and currents. The system language is erected on the
network language, in the sense that the elements of
signal-processing systems are constructed from electrical
networks. Here, however, the concerns are with the large-scale
organization of electrical devices to solve a given application
problem; the physical feasibility of the parts is assumed. This
layered collection of languages is another example of the
stratified design technique illustrated by the picture language
of section <a href="book-Z-H-15.html#%_sec_2.2.4">2.2.4</a>.</p>
<p><a href="#call_footnote_Temp_509" name="footnote_Temp_509" id="footnote_Temp_509"><sup><small>2</small></sup></a> The most
important features that our evaluator leaves out are mechanisms
for handling errors and supporting debugging. For a more
extensive discussion of evaluators, see <a name="%_idx_4204"></a><a name="%_idx_4206"></a><a name="%_idx_4208"></a>Friedman, Wand, and Haynes 1992, which gives
an exposition of programming languages that proceeds via a
sequence of evaluators written in Scheme.</p>
</div>
</body>
</html>