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
|
<HTML>
<HEAD>
<TITLE>Computer Science Logo Style vol 2:Preface</TITLE>
</HEAD>
<BODY>
<CITE>Computer Science Logo Style</CITE> volume 2:
<CITE>Advanced Techniques</CITE> 2/e Copyright (C) 1997 MIT
<H1>Preface</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../csls2.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"><BR>
<TR><TD align="right"><A HREF="../pdf/v2ch00.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../v2-toc2.html">Back to Table of Contents</A>
<TR><TD align="right">[no back]
chapter thread <A HREF="ack.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-2">MIT
Press web page for <CITE>Computer Science Logo Style</CITE></A>
</TABLE></TABLE>
<HR>
<P>This is the second volume of <EM>Computer Science Logo Style,</EM> a
three-volume series that uses the Logo programming language as the medium
for a presentation of a range of topics in computer science. The main
audience I had in mind for these books was high school students, but it's
turned out that they have also been used in teacher training, and to some
extent by independent adult learners.
<P>In the first edition, the first volume was a complete Logo tutorial,
explaining all of the features of the language; the second volume was
entirely devoted to programming projects. (The third volume, then and
now, is a sampler of topics from undergraduate computer science courses.)
My idea was that students would spend their first year in an intensive
programming course, and would then pursue their own programming projects
on an independent study basis, using my projects as examples.
<P>As it turned out, people found the first volume both too hard and too easy.
It was too hard because it arrived too soon at the more advanced and
complicated features of Logo; it was too easy because the actual programming
examples were all short enough to fit on a page. Such tiny examples didn't
help the learner extrapolate to the design of a program that could
actually do something interesting. This deficiency may have encouraged
some readers to conclude that Logo is just a toy, and that serious projects
should be done in a "serious" language such as Pascal or C++.
<P>In this second edition I've rearranged things. The first volume now teaches
only the core features of Logo, the ones every programmer must understand;
it also includes three of the projects that were originally in the second
volume. This volume is now a more advanced programming text; it alternates
tutorial chapters on advanced language features with example projects that
demonstrate those features.
<P>The project chapters serve two purposes at once. First, each project is an
example of something you might actually want to do. The emphasis
is on getting the computer to do something fun and interesting. Each of the
projects in this book is here because I thought I'd enjoy writing it
myself, not because it fit some subtle pedagogic purpose. The projects are
offered as case studies, as examples to inspire your own creative efforts.
<P>At the same time, I <EM>am</EM> a teacher, and in this book I'm trying to
teach some ideas about programming technique and programming style. Often
there is an easy way and a hard way to achieve a certain result, and you're
better off if you know the easy way. Nobody has a complete list of such
techniques; you'll be learning new ones for as long as you maintain your
interest in computer programming. The ones I discuss in this book are the
ones that came up in these particular projects. Ideally, as your teacher, I
would look over your shoulder while you're working, and I'd tell you about
the techniques that apply to <EM>your</EM> projects. I can't do that in a
book, and so instead I'm presenting some projects of my own and discussing
them as I would discuss your projects if I knew you personally.
<P>With one exception, each example chapter comes after a tutorial chapter that
has introduced a new Logo programming technique, and that technique is used
in the project. (The exception, the pattern matching project, is an advanced
programming technique in its own right, and is used in a later project.)
But the technique from the previous chapter is rarely the most important
aspect of the project! Each project exhibits many different techniques,
and the project chapters describe some of them.
<P>This book does not make much explicit reference to the first volume, but to
understand the discussion here, you should be familiar with the ideas
presented in Volume 1: evaluation, procedures, locality, iteration,
recursion, mapping, predicates, operations, and so on.
<P>Teaching and learning, by the way, don't necessarily imply a classroom in a
school. I like to imagine you curled up with this book in front of your
home computer, playing around with one of these projects just for the fun of
it. Pretend I'm a friend or relative who happens to be a professional
computer scientist. On the other hand, if you <EM>are</EM> reading this for
a course in a school, you have the advantage of a living teacher who can
provide the kind of individual attention to your specific projects that I
can't. There are advantages and disadvantages either way.
<P><H2>About the Projects</H2>
<P>Although I now have the projects linked with tutorial chapters, in the
first edition I organized them into five categories, based not on the
programming techniques used but rather on the purposes of the programs. The
projects reflect aspects of my own character: I came to computers by way of
an early interest in mathematics; my computing background is in
artificial intelligence and in systems programming; I tend
to think in words, not in pictures. I think it may give the collection of
projects a more coherent feel if I explain the categories in which they
were written, even though the book is no longer organized around
those categories.
<P>The first is cryptography. One of the first books I can
remember buying, as a child in elementary school, was about secret codes.
Besides the universal appeal of knowing a secret, cryptography was
interesting to me because it's a <EM>mathematical</EM> sort of puzzle, like
those logic problems about who lives in the yellow house. The
Cryptographer's Helper project in this volume includes a very small effort
at artificial intelligence: the program makes some guesses, on its own, to
start solving a cryptogram. The Playfair Cipher project, now moved to the
first volume, deals with a more complicated technique for encoding a
message, but it doesn't try to break such a code.
<P>The second category is games. I'm not a video game enthusiast; hand-eye
coordination isn't my strong point. (I never really learned to ride a
bicycle!) Anyway, writing video game programs depends too much on the
particular hardware of your computer, so I can't do it in this general
book.<SUP>*</SUP> Instead I've written two simple
strategy games. In the first volume is a program that plays tic-tac-toe. This game
is extremely trivial for a human being, but it's surprisingly hard to
formulate strategy rules that are simple and precise enough to embody in a
computer program. Also, it's an opportunity to throw in a little bit of
graphics programming, to draw the board and fill it with Xs and Os. In this
volume is a program that deals out a hand of solitaire and maintains the display of
the layout as you play the hand. Before I wrote this program, I had been
feeling bored and lonely for an extended period, and I was wasting a lot of
time playing solitaire myself. I figured it would be more productive to
write a computer program!
<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>You can find a video game that I wrote in the collection
<EM>LogoWorks: Challenging Programs in Logo</EM>, edited by Solomon,
Minsky, and Harvey (McGraw-Hill, 1985).</SMALL></BLOCKQUOTE></SMALL><P>The third category is mathematics. I once spent some time working as a
systems programmer at a computer music research center in Paris, and this
volume includes a project about Fourier analysis, the mathematical
basis of computer music. The project demonstrates graphically how a complex
waveform, representing the texture of a sound, can be built up from much
simpler elements. In the first volume is a program to solve the kind of
problem, often found on IQ tests, in which you are given pitchers of certain
sizes and asked to use them to measure a given amount of water by pouring
back and forth. This project illustrates the idea of searching through a
"solution space" of possible pouring steps.
<P>The fourth category is that of utility programs. This is actually
the area of programming I know best: writing things that are not complete
applications in themselves, but rather tools to help in the creation of even
larger projects. For the second edition I've replaced the original
projects in this category with two new ones. The project Finding File
Differences is a utility program that can be used to compare two versions
of a file to see what's changed from the old one to the new one. Then
there is a compiler for the BASIC programming language; besides illustrating
the idea of program as data--the compiler generates new Logo procedures
to carry out the instructions in a BASIC program--this project may help to
prepare the reader for the more complicated Pascal compiler in the third
volume.
<P>The fifth category is pattern matching. This category
combines my interests in systems programming and
artificial intelligence. The first project is a tool, like the
ones in the utilities category, but it's a tool designed specifically for
artificial intelligence applications: a pattern matcher. This program
compares a particular list with a general template, or pattern. Instead of
checking for exact equality like <CODE>equalp</CODE>, the pattern matcher checks
for a kind of "fill in the blanks" partial equality. The second project
in this category uses the pattern matcher to implement <CODE>doctor</CODE>, another famous
artificial intelligence program that simulates a conversation with the user.
<P><H2>About This Series</H2>
<P><EM>Computer Science Logo Style</EM> is intended to bring to the hobbyist
audience a particular point of view about computer science: the
artificial intelligence view. This way of looking at computers is
quite different from the more usual software engineering approach.
In that approach, you are always dealing with a
very well-defined problem, and are looking for the best way to solve it.
Software engineers like to start with a formal problem statement, and then
design a computer program to fit. They believe that the design process
should be <EM>top-down</EM>; you should start with the overall structure and
work down to the details. Their preferred programming language is
Pascal.
<P>In artificial intelligence, the problems are not usually so well
defined. Starting with a vague problem statement like "develop a good
strategy for playing chess," AI programmers can't begin with a rigid program
specification. Instead, they build <EM>tools:</EM> program fragments that
can be pieced together to form larger programs. The programming process
involves writing code, testing, coming up with new ideas, and modifying the
program interactively. This process is encouraged by an interactive
language like Lisp or Logo.
<P>Computer programming is a great intellectual hobby; it provides the same
opportunity for creative, concrete work in mathematical thinking that
drama or creative writing does for verbal thinking. A learner can have
years of intellectual adventure just learning to write better and better
programs. Finally, though, there may come a time
when the learner gets bored with just writing more and more programs, and
seeks a deeper understanding of the issues behind this practical work. The
third volume of this series, <EM>Beyond Programming,</EM> addresses
the needs of these learners by introducing them to some of the elements of
university-level computer science, still in the context of Logo programming.
<P><H2>How to Read This Book</H2>
<P>You should have each program actually available to you on a computer as you
read about it. These programs can be downloaded
<A HREF="../downloads/csls-programs">here</A>.
<P>There are many dialects of Logo; this book uses Berkeley Logo, a free
version available for PC, Macintosh, and Unix systems. The more fundamental
Logo techniques used in the first volume are more or less standard among
Logo implementations, but some of the advanced techniques in this volume
are unique to Berkeley Logo. Download Berkeley Logo
<A HREF="../logo.html">here</A>.
<P>The programs you see here are essentially the programs I wrote as I was
trying to get each project to work. I didn't start with a particular
programming style in mind and then invent an example to illustrate the
style. It's not always obvious what is the "correct" style for a given
problem; sometimes one way is much easier to understand, for example, while
a different solution may run much more efficiently. The comments in
each chapter sometimes suggest alternative ways in which I might have
written some piece of the program. I try to explain why I chose the style I
did, although sometimes the real explanation is simply that that's the first
thing I thought of. I've modified almost all of these programs for the
second edition, and some of the chapters explain my second thoughts.
<P>Each example chapter begins with an explanation of what the project is all about.
Remember that these projects were meant to be interesting in themselves, not
just as vehicles for a discussion of programming techniques! The discussion
in each chapter ends with a return to the purpose of the project, with
suggestions for how that purpose might be extended. One source of ideas for
projects of your own is to extend someone else's work, and one important
purpose of this book is to give you ideas for such starting points.
In between comes a technical discussion of the programming techniques used.
<P>What I do <EM>not</EM> provide, generally, is a guided tour of every
procedure. One of the things you should learn from this book is the ability
to read a long program on your own. You should recognize some of the
typical categories of procedures, like ones that apply a given command to
each member of a list. In the discussions, rather than explain every
detail, I try to focus your attention on the parts of the program that seem
to illuminate some more general technical issue. A complete listing of the
program is at the end of each example chapter.
<P>The programs in this book are copyright, but you can use, copy, and
redistribute them freely; the exact terms are given in the GNU General
Public License, which is distributed with the programs and is printed
in the first volume of this series. Essentially, the only restriction
is that you can't use these programs as the basis for your own commercial
programs; if you extend these projects, you can only distribute your
extensions on the same free terms. Share ideas, don't hoard them!
<P>
<P><A HREF="../v2-toc2.html">(back to Table of Contents)</A>
<P>[no back]
chapter thread <A HREF="ack.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|