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
|
<HTML>
<HEAD>
<TITLE>Simply Scheme: To the Instructor</TITLE>
</HEAD>
<BODY>
<CITE>Simply Scheme</CITE> 2/e Copyright (C) 1999 MIT
<H1>To the Instructor</H1>
<TABLE><TR><TD>
<P><IMG SRC="../simply.jpg" ALT="cover photo">
<TD valign="center">
<CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian
Harvey</A><BR><A HREF="http://www.cnmat.berkeley.edu/~matt">Matthew
Wright</A><BR>University of California, Berkeley</CITE>
<BR><BR><A HREF="http://www-mitpress.mit.edu/book-home.tcl?isbn=0262082810">MIT
Press web page for Simply Scheme</A>
</TABLE>
<P><A HREF="../simply-toc.html">(back to Table of Contents)</A>
<HR>
<P>The language that we use in this book isn't exactly standard Scheme. We've
provided several extensions that may seem unusual to an experienced Scheme
programmer. This may make the book feel weird at first, but there's a
pedagogic reason for each extension.
<P>Along with our slightly strange version of Scheme, our book has a slightly
unusual order of topics. Several ideas that are introduced very early in
the typical Scheme-based text are delayed in ours, most notably recursion.
Quite a few people have looked at our table of contents, noted some
particular big idea of computer science, and remarked, "I can't believe
you wait so long before getting to <EM>such and such</EM>!"
<P>In this preface for instructors, we describe and explain the unusual
elements of our approach. Other teaching issues, including the timing and
ordering of topics, are discussed in the Instructor's Manual.
<P><H2>Lists and Sentences</H2>
<P>The chapter named "Lists" in this book is Chapter 17, about halfway
through the book. But really we use lists much earlier than that, almost
from the beginning.
<P>Teachers of Lisp have always had trouble deciding when and how to introduce
lists. The advantage of an early introduction is that students can then
write interesting symbolic programs instead of boring numeric ones. The
disadvantage is that students must struggle with the complexity of the
implementation, such as the asymmetry between the two ends of a list, while
still also struggling with the idea of composition of functions and Lisp's
prefix notation.
<P>We prefer to have it both ways. We want to spare beginning students the
risk of accidentally constructing ill-formed lists such as
<P><PRE>((((() . D) . C) . B) . A)
</PRE>
<P>but we also want to write natural-language programs from the
beginning of the book. Our solution is to borrow from Logo the idea of a
<EM>sentence</EM> abstract data type.<SUP>*</SUP> Sentences are
guaranteed to be flat, proper lists, and they appear to be symmetrical to
the user of the abstraction. (That is, it's as easy to ask for the last
word of a sentence as to ask for the first word.) The <CODE>sentence</CODE>
constructor accepts either a word or a sentence in any argument position.
<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>Speaking of abstraction, even
though that's the name of Part V, we do make an occasion in each of the
earlier parts to talk about abstraction as examples come up.</SMALL></BLOCKQUOTE></SMALL><P>We defer <EM>structured</EM> lists until we have higher-order functions and
recursion, the tools we need to be able to use the structure
effectively.<SUP>*</SUP> A
structured list can be understood as a tree, and Lisp programmers generally
use that understanding implicitly. We create an explicit abstract data type
for trees and use it for a thorough exploration of tree structure, without
reference to the implementation of trees. We then explicitly connect the
usual informal tree recursion on structured lists to our more formal version.
<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>Even then, we take lists as a primitive data type. We
don't teach about pairs or improper lists, except as a potential pitfall.</SMALL></BLOCKQUOTE></SMALL><P><H2>Sentences and Words</H2>
<P>We haven't said what a <EM>word</EM> is. Scheme includes separate data types
for characters, symbols, strings, and numbers. We want to be able to
dissect words into letters, just as we can dissect sentences into words, so
that we can write programs like <CODE>plural</CODE> and <CODE>pig-latin</CODE>. Orthodox
Scheme style would use strings for such purposes, but we want a sentence to
look <CODE>(like this)</CODE> and not <CODE>("like" "this")</CODE>. We've arranged that
in most contexts symbols, strings, and numbers can be used interchangeably;
our readers never see Scheme characters at all.<SUP>*</SUP>
Although a word made of letters is represented internally as a symbol, while
a word made of digits is represented as a number, above the abstraction line
they're both words. (A word that standard Scheme won't accept as a symbol
nor as a number is represented as a string.)
<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>Scheme's primitive
I/O facility gives you the choice of expressions or characters. Instead of
using <CODE>read-char</CODE>, we invent <CODE>read-line</CODE>, which reads a line as a
sentence, and <CODE>read-string</CODE>, which returns the line as one long word.</SMALL></BLOCKQUOTE></SMALL><P>There is an efficiency cost to treating both words and sentences as abstract
aggregates, since it's slow to disassemble a sentence from right to left and
slow to disassemble a word in either direction. Many simple procedures that
seem linear actually behave quadratically. Luckily, words aren't usually
very long, and the applications we undertake in the early chapters don't use
large amounts of data in any form. We write our large projects as
efficiently as we can without making the programs unreadable, but we
generally don't make a fuss about it. Near the end of the book we discuss
explicitly the efficient use of data structures.
<P><H2>Overloading in the Text Abstraction</H2>
<P>Even though computers represent numbers internally in many different ways
(fixed point, bignum, floating point, exact rational, complex), when people
visit mathland, they expect to meet numbers there, and they expect that all
the numbers will understand how to add, subtract, multiply, and divide with
each other. (The exception is dividing by zero, but that's because of the
inherent rules of mathematics, not because of the separation of numbers into
categories by representation format.)
<P>We feel the same way about visiting textland. We expect to meet English
text there. It takes the form of words and sentences. The operations that
text understands include <CODE>first</CODE>, <CODE>last</CODE>, <CODE>butfirst</CODE>, and <CODE>
butlast</CODE> to divide the text into its component parts. You can't divide an
empty word or sentence into parts, but it's just as natural to divide a word
into letters as to divide a sentence into words. (The ideas of mathland and
textland, as well as the details of the word and sentence procedures, come
from Logo.)
<P>Some people who are accustomed to Scheme's view of data types consider <CODE>
first</CODE> to be badly "overloaded"; they feel that a procedure that selects an
element from a list shouldn't also extract a letter from a symbol. Some of
them would prefer that we use <CODE>car</CODE> for lists, use <CODE>substring</CODE> for
strings, and not disassemble symbols at all. Others want us to define <CODE>
word-first</CODE> and <CODE>sentence-first</CODE>.
<P>To us, <CODE>word-first</CODE> and <CODE>sentence-first</CODE> sound no less awkward than
<CODE>fixnum-+</CODE> and <CODE>bignum-+</CODE>. Everyone agrees that it's reasonable to
overload the name <CODE>+</CODE> because the purposes are so similar. Our students
find it just as reasonable that <CODE>first</CODE> works for words as well as for
sentences; they don't get confused by this.
<P>As for the inviolability of symbols--the wall between names and data--we
are following an older Lisp tradition, in which it was commonplace to <CODE>
explode</CODE> symbols and to construct new names within a program. Practically
speaking, all that prevents us from representing words as strings is that
Scheme requires quotation marks around them. But in any case, the
abstraction we're presenting is that the data we're dissecting are neither
strings nor symbols, but words.
<P><H2>Higher-Order Procedures, Lambda, and Recursion</H2>
<P>Scheme relies on procedure invocation as virtually its only control
mechanism. In order to write interesting programs, a Scheme user must
understand at least one of two hard ideas: recursion or procedure as object
(in order to use higher-order procedures). We believe that higher-order
procedures are easier to learn, especially because we begin in Chapter
8 by applying them only to named procedures. Using a named procedure
as an argument to another procedure is the way to use procedures as objects
that's least upsetting to a beginner. After the reader is comfortable with
higher-order procedures, we introduce <CODE>lambda</CODE>; after that we introduce
recursion. We do the tic-tac-toe example with higher-order procedures and
<CODE>lambda</CODE>, but not recursion.
<P>When we get to recursion, we begin with an example of embedded recursion.
Many books begin with the simplest possible recursive procedure, which turns
out to be a simple sequential recursion, or even a tail recursion. We feel
that starting with such examples allows students to invent the "go back"
model of recursion as looping.
<P><H2>Mutators and Environments</H2>
<P>One of the most unusual characteristics of this book is that there is no
assignment to variables in it. The reason we avoid <CODE>set!</CODE> is that the
environment model of evaluation is very hard for most students. We use a
pure substitution model throughout most of the book. (With the background
they get from this book, students should be ready for the environment model
when they see a rigorous presentation, as they will, for example, in Chapter
3 of <EM>SICP.</EM>)
<P>As the last topic in the book, we do introduce a form of mutation, namely
<CODE>vector-set!</CODE>. Mutation of vectors is less problematic than mutation of
lists, because lists naturally share storage. You really have to go out of
your way to get two pointers to the same vector.<SUP>*</SUP> Mutation of data
structures is less problematic than assignment to variables because it
separates the issue of mutation from the issues of binding and scope. Using
vectors raises no new questions about the evaluation process, so we present
mutation without reference to any formal model of evaluation. We
acknowledge that we're on thin ice here, but it seems to work for our
students.
<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>We don't talk about
<CODE>eq?</CODE> at all. We're careful to write our programs in such a way that
the issue of identity doesn't arise for the reader.</SMALL></BLOCKQUOTE></SMALL><P>In effect, our model of mutation is the "shoebox" model that you'd find in
a mainstream programming language text. Before we get to mutation, we use
input/output programming to introduce the ideas of effect and sequence;
assigning a value to a vector element introduces the important idea of
state. We use the sequential model to write two more or less practical
programs, a spreadsheet and a database system. A more traditional approach
to assignment in Scheme would be to build an object-oriented language
extension, but the use of local state variables would definitely force us to
pay attention to environments.
<P><A HREF="../simply-toc.html">(back to Table of Contents)</A>
</HTML>
|