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
|
<P>
<P><A NAME="hare"></A>
<CENTER><IMG SRC="../ss-pics/hare.jpg" ALT="figure: hare"></CENTER><P><CENTER>Scheme-Brained Hare
</CENTER><P>
<HTML>
<HEAD>
<TITLE>Simply Scheme: Introducing Computer Science ch 1: Showing Off Scheme</TITLE>
</HEAD>
<BODY>
<HR>
<CITE>Simply Scheme:</CITE>
<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT
<H2>Chapter 1</H2>
<H1>Showing Off Scheme</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../simply.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"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew
Wright</A><BR>University of California, Santa Barbara</CITE>
<TR><TD align="right"><BR>
<TR><TD align="right"><A HREF="../pdf/ssch01.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../ss-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="part1.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch2/functions.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="http://mitpress.mit.edu/0262082810">MIT
Press web page for <CITE>Simply Scheme</CITE></A>
</TABLE></TABLE>
<HR>
<P>We are going to use the programming language Scheme to teach you some big
ideas in computer science. The ideas are mostly about <EM><A NAME="g1"></A><A NAME="g2"></A>control of complexity—</EM>that is, about how to develop a
large computer program without being swamped in details.
<P>For example, once you've solved part of the large problem, you can give that
partial solution a <EM>name</EM> and then you can use the named subprogram as
if it were an indivisible operation, just like the ones that are built into
the computer. Thereafter, you can forget about the details of that
subprogram. This is the beginning of the idea of <EM>abstraction,</EM>
which we'll discuss in more depth throughout the book.
<P>The big ideas are what this book is about, but first we're going to
introduce you to Scheme. (Scheme is a dialect of Lisp, a family of computer
programming languages invented for computing with words, sentences, and
ideas instead of just numbers.)
<P><H2>Talking to Scheme</H2>
<P>The incantations to get Scheme running will be different for each model of
computer. Appendix A talks about these details; you can look up the
particular version of Scheme that you're using. That appendix will also
tell you how to load the file <CODE>simply.scm</CODE>, which you need to make the
examples in this book work.
<P>When Scheme has started up and is ready for you to interact with it,
you'll see a message on the screen, something like this:
<P><PRE>Welcome to XYZ Brand Scheme.
>
</PRE>
<P>The <CODE>></CODE> is a <EM>prompt,</EM> Scheme's way of telling you
that it's ready for you to type something. Scheme is an <EM>interactive</EM>
programming language. In other words, you type a request to Scheme, then
Scheme prints the answer, and then you get another prompt. Try it out:
<P><PRE>> <B>6</B>
6
</PRE>
<P>We just asked Scheme, "What is 6?" and Scheme told us that 6 is
6. Most of the time we ask harder questions:
<P><PRE>> <B>(+ 4 7)</B>
11
> <B>(- 23 5)</B>
18
> <B>(+ 5 6 7 8)</B>
26
</PRE>
<P>Whenever something you type to Scheme is enclosed in parentheses,
<A NAME="g3"></A>
it indicates a request to carry out a <EM>procedure.</EM> (We'll define
"procedure" more formally later, but for now it means something that
Scheme knows how to do. A procedure tells Scheme how to compute
a particular function.) The first thing inside the parentheses indicates
what procedure to use; the others are <EM>arguments,</EM> i.e., values
that are used as data by the procedure.
<P>Scheme has non-numeric procedures, too:
<P><PRE>> <B>(word 'comp 'uter)</B>
COMPUTER
</PRE>
<P>(If this last example gives an error message saying
that Scheme doesn't understand the name <CODE>word</CODE>, it means that you
didn't load the file <CODE>simply.scm</CODE>. Consult Appendix A.)
<P>In these first examples, we've shown what you type in <CODE><B>boldface</B></CODE> and
what the computer responds in <CODE>lightface</CODE>. Hereafter, we will rely on
the prompt characters to help you figure out who's talking on which line.
<P>For the most part, Scheme doesn't care about whether you type in UPPER CASE
or lower case. For the examples in this book, we'll assume that you always
type in lower case and that the computer prints in upper case. Your Scheme
might print in lower case; it doesn't matter.
<P><H2>Recovering from Typing Errors</H2>
<P>Don't worry if you make a mistake typing these examples in; you can just try
again. One of the great things about interactive programming languages is
that you can experiment in them.
<P>The parentheses and single quote marks are important; don't leave them out.
If Scheme seems to be ignoring you, try typing a bunch of right parentheses,
<CODE>))))))</CODE>, and hitting the <CODE>return</CODE> or <CODE>enter</CODE> key. (That's
because Scheme doesn't do anything until you've closed all the parentheses
you've opened, so if you have an extra left parenthesis, you can keep typing
forever with no response.)
<P>Another problem you might encounter is seeing a long message that you don't
understand and then finding yourself with something other than a Scheme
prompt. This happens when Scheme considers what you typed as an
<A NAME="g4"></A>
error. Here's an example; for now, never mind exactly why this is an
error. We just want to talk about the result:
<P><PRE>> (+ 2 a)
Unbound variable a
;Package: (user)
2 Error->
</PRE>
<P>The exact form of the message you get will depend on the version
of Scheme that you're using. For now, the important point is that some
versions deal with errors by leaving you talking to a <EM>debugger</EM>
instead of to Scheme itself. The debugger may have a completely different
language. It's meant to help you figure out what's wrong in a large program
you've written. For a beginner, though, it's more likely to get in the way.
Read the documentation for your particular Scheme dialect to learn how to
escape from the debugger. (In some versions you don't get trapped in a
debugger when you make an error, so this problem may not arise.)
<P>
<P><H2>Exiting Scheme</H2>
<P>Although there's no official standard way to exit Scheme, most versions
use the notation
<P><PRE>> (<A NAME="g5"></A>exit)
</PRE>
<P>for this purpose. If you type in some of the examples that
follow and then exit from Scheme, what you type won't be remembered the
next time you use Scheme. (Appendix A talks about how to use a text editor
along with Scheme to make a permanent record of your work.)
<P><H2>More Examples</H2>
<P>We're about to show you a few examples of (we hope) interesting programs in
Scheme. Play with them! Type them into your computer and try invoking them
with different data. Again, don't worry too much if something doesn't
work—it probably just means that you left out a parenthesis, or some such
thing.
<P>While you're going through these examples, see how much you can figure out
for yourself about how they work. In particular, try guessing what the
names of procedures, such as <CODE>first</CODE> and <CODE>keep</CODE>, mean. Some of them
will probably be obvious, some of them harder. The point isn't to see how
smart you are, but to get you thinking about the <EM>kinds</EM> of things you
want to be able to do in a computer program. Later on we'll go through
these examples in excruciating detail and tell you the official meanings of all
the pieces.
<P>Besides learning the <EM>vocabulary</EM> of Scheme, another point of
this activity is to give you a feeling for the ways in which we put these
names together in a program. Every programming language has its own flavor.
For example, if you've programmed before in other languages, you may be
surprised not to find anything that says <CODE>print</CODE> in these examples.
<P>On the other hand, some of these examples are programs that we won't
expect you to understand fully until most of the way through this
book. So don't worry if something doesn't make sense; just try to
get some of the flavor of Scheme programming.
<P><H2>Example: Acronyms</H2>
<P>Here's our first new program. So far we have just been using procedures
built into Scheme: <CODE>+</CODE>, <CODE>-</CODE>, and <CODE>word</CODE>. When you first start
up Scheme, it knows 100-200 procedures. These are called <EM>primitive</EM>
<A NAME="g6"></A>
<A NAME="g7"></A>
<A NAME="g8"></A>
<A NAME="g9"></A>
procedures. Programming in Scheme means defining new procedures, called
<EM>compound</EM> procedures. Right now we're going to invent one that finds
the acronym for a title:
<P><PRE>(define (<A NAME="g10"></A>acronym phrase)
(accumulate word (every first phrase)))
> (acronym '(american civil liberties union))
ACLU
> (acronym '(reduced instruction set computer))
RISC
> (acronym '(quod erat demonstrandum))
QED
</PRE>
<P>Did you have trouble figuring out what all the pieces do in the <CODE>acronym</CODE> procedure? Try these examples:
<P><PRE>> (first 'american)
A
> (every first '(american civil liberties union))
(A C L U)
> (accumulate word '(a c l u))
ACLU
</PRE>
<P>Notice that this simple <CODE>acronym</CODE> program doesn't always do exactly what
you might expect:
<P><PRE>> (acronym '(united states of america))
USOA
</PRE>
<P>We can rewrite the program to leave out certain words:
<P><PRE>(define (<A NAME="g11"></A>acronym phrase)
(accumulate word (every first (keep real-word? phrase))))
(define (<A NAME="g12"></A>real-word? wd)
(not (member? wd '(a the an in of and for to with))))
> (acronym '(united states of america))
USA
> (acronym '(structure and interpretation of computer programs))
SICP
> (acronym '(association for computing machinery))
ACM
> (real-word? 'structure)
#T
> (real-word? 'of)
#F<A NAME="text1" HREF="showing.html#ft1">[1]</A>
> (keep real-word? '(united network command for law and enforcement))
(UNITED NETWORK COMMAND LAW ENFORCEMENT)
</PRE>
<H2>Example: Pig Latin</H2>
<P>Our next example translates a word into <A NAME="g13"></A><A NAME="g14"></A>Pig Latin.<A NAME="text2" HREF="showing.html#ft2">[2]</A>
<P><A NAME="pig"></A>
<CENTER><IMG SRC="../ss-pics/pig.jpg" ALT="figure: pig"></CENTER>
<P><PRE>(define (<A NAME="g15"></A>pigl wd)
(if (member? (first wd) 'aeiou)
(word wd 'ay)
(pigl (word (butfirst wd) (first wd)))))
> (pigl 'spaghetti)
AGHETTISPAY
> (pigl 'ok)
OKAY
</PRE>
(By the way, if you've used other programming languages before, don't fall
<A NAME="g16"></A>
<A NAME="g17"></A>
into the trap of thinking that each line of the <CODE>pigl</CODE> definition is a
"statement" and that they are executed one after the other.
That's not how it works in Scheme. The entire thing is a single expression,
and what counts is the grouping with parentheses. Starting a new line is no
different from a space between words as far as Scheme is concerned. We
could have defined <CODE>pigl</CODE> on one humongous line and it would mean the
same thing. Also, Scheme doesn't care about how we've indented the lines so
that subexpressions line up under each other. We do that only to make the
program more readable for human beings.)
<P>The procedure follows one of two possible paths, depending on whether the
first letter of the given word is a vowel. If so, <CODE>pigl</CODE> just adds
the letters <CODE>ay</CODE> at the end:
<P><PRE>> (pigl 'elephant)
ELEPHANTAY
</PRE>
<P>The following examples might make it a little more clear how the
starting-consonant case works:
<P><PRE>> (first 'spaghetti)
S
> (butfirst 'spaghetti)
PAGHETTI
> (word 'paghetti 's)
PAGHETTIS
> (define (<A NAME="g18"></A>rotate wd)
(word (butfirst wd) (first wd)))
> (rotate 'spaghetti)
PAGHETTIS
> (rotate 'paghettis)
AGHETTISP
> (pigl 'aghettisp)
AGHETTISPAY
</PRE>
<P>You've seen <CODE>every</CODE> before, in the <CODE>acronym</CODE> example, but we haven't
told you what it does. Try to guess what Scheme will respond when you type
this:
<P><PRE>(every pigl '(the ballad of john and yoko))
</PRE>
<P><H2>Example: Ice Cream Choices</H2>
<P>
Here's a somewhat more complicated program, but still pretty short
considering what it accomplishes:
<P>
<PRE>(define (<A NAME="g19"></A>choices menu)
(if (null? menu)
'(())
(let ((smaller (choices (cdr menu))))
(reduce append
(map (lambda (item) (prepend-every item smaller))
(car menu))))))
(define (<A NAME="g20"></A>prepend-every item lst)
(map (lambda (choice) (se item choice)) lst))
> (choices '((small medium large)
(vanilla (ultra chocolate) (rum raisin) ginger)
(cone cup)))
((SMALL VANILLA CONE)
(SMALL VANILLA CUP)
(SMALL ULTRA CHOCOLATE CONE)
(SMALL ULTRA CHOCOLATE CUP)
(SMALL RUM RAISIN CONE)
(SMALL RUM RAISIN CUP)
(SMALL GINGER CONE)
(SMALL GINGER CUP)
(MEDIUM VANILLA CONE)
(MEDIUM VANILLA CUP)
(MEDIUM ULTRA CHOCOLATE CONE)
(MEDIUM ULTRA CHOCOLATE CUP)
(MEDIUM RUM RAISIN CONE)
(MEDIUM RUM RAISIN CUP)
(MEDIUM GINGER CONE)
(MEDIUM GINGER CUP)
(LARGE VANILLA CONE)
(LARGE VANILLA CUP)
(LARGE ULTRA CHOCOLATE CONE)
(LARGE ULTRA CHOCOLATE CUP)
(LARGE RUM RAISIN CONE)
(LARGE RUM RAISIN CUP)
(LARGE GINGER CONE)
(LARGE GINGER CUP))
</PRE>
<P>Notice that in writing the program we didn't have to say how
many menu categories there are, or how many choices in each category.
This one program will work with any menu—try it out yourself.
<P><H2>Example: Combinations from a Set</H2>
<P>Here's a more mathematical example. We want to know all the possible
combinations of, let's say, three things from a list of five possibilities.
For example, we want to know all the teams of three people that can
be chosen from a group of five people. "Dozy, Beaky, and Tich" counts as
the same team as "Beaky, Tich, and Dozy"; the order within a team doesn't
matter.
<P>Although this will be a pretty short program, it's more complicated than it
looks. We don't expect you to be able to figure out the algorithm
yet.<A NAME="text3" HREF="showing.html#ft3">[3]</A> Instead, we just want you to marvel at Scheme's ability to
express difficult techniques succinctly.
<P><PRE>(define (<A NAME="g21"></A>combinations size set)
(cond ((= size 0) '(()))
((empty? set) '())
(else (append (prepend-every (first set)
(combinations (- size 1)
(butfirst set)))
(combinations size (butfirst set))))))
> (combinations 3 '(a b c d e))
((A B C) (A B D) (A B E) (A C D) (A C E)
(A D E) (B C D) (B C E) (B D E) (C D E))
> (combinations 2 '(john paul george ringo))
((JOHN PAUL) (JOHN GEORGE) (JOHN RINGO)
(PAUL GEORGE) (PAUL RINGO) (GEORGE RINGO))
</PRE>
<P>(If you're trying to figure out the algorithm despite our warning,
here's a hint: All the combinations of three letters shown above can be
divided into two groups. The first group consists of the ones that start
with the letter <CODE>A</CODE> and contain two more letters; the second group has
three letters not including <CODE>A</CODE>. The procedure finds these two groups
separately and combines them into one. If you want to try to understand all
the pieces, try playing with them separately, as we encouraged you to do
with the <CODE>pigl</CODE> and <CODE>acronym</CODE> procedures.)
<P>If you've taken a probability course, you know that there is a formula for the
<EM>number</EM> of possible combinations. The most
traditional use of computers is to work through such formulas and compute
numbers. However, not all problems are numeric.
Lisp, the programming language family of which Scheme is a member, is
unusual in its emphasis on <EM>symbolic</EM> computing. In this example,
listing the actual combinations instead of just counting them is part of the
flavor of <A NAME="g22"></A>symbolic computing, along with our earlier examples about
<A NAME="g23"></A>
<A NAME="g24"></A>
manipulating words and phrases. We'll try to avoid numeric
problems when possible, because symbolic computing is more fun
for most people.
<P><H2>Example: Factorial</H2>
<P>Scheme can handle numbers, too. The factorial of <EM>n</EM> (usually written
in mathematical notation as <EM>n</EM>!) is the product of all the numbers from 1 to
<EM>n</EM>:
<A NAME="g25"></A>
<P><PRE>(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
> (factorial 4)
24
> (factorial 1000)
4023872600770937735437024339230039857193748642107146325437999104299385
1239862902059204420848696940480047998861019719605863166687299480855890
1323829669944590997424504087073759918823627727188732519779505950995276
1208749754624970436014182780946464962910563938874378864873371191810458
2578364784997701247663288983595573543251318532395846307555740911426241
7474349347553428646576611667797396668820291207379143853719588249808126
8678383745597317461360853795345242215865932019280908782973084313928444
0328123155861103697680135730421616874760967587134831202547858932076716
9132448426236131412508780208000261683151027341827977704784635868170164
3650241536913982812648102130927612448963599287051149649754199093422215
6683257208082133318611681155361583654698404670897560290095053761647584
7728421889679646244945160765353408198901385442487984959953319101723355
5566021394503997362807501378376153071277619268490343526252000158885351
4733161170210396817592151090778801939317811419454525722386554146106289
2187960223838971476088506276862967146674697562911234082439208160153780
8898939645182632436716167621791689097799119037540312746222899880051954
4441428201218736174599264295658174662830295557029902432415318161721046
5832036786906117260158783520751516284225540265170483304226143974286933
0616908979684825901254583271682264580665267699586526822728070757813918
5817888965220816434834482599326604336766017699961283186078838615027946
5955131156552036093988180612138558600301435694527224206344631797460594
6825731037900840244324384656572450144028218852524709351906209290231364
9327349756551395872055965422874977401141334696271542284586237738753823
0483865688976461927383814900140767310446640259899490222221765904339901
8860185665264850617997023561938970178600408118897299183110211712298459
0164192106888438712185564612496079872290851929681937238864261483965738
2291123125024186649353143970137428531926649875337218940694281434118520
1580141233448280150513996942901534830776445690990731524332782882698646
0278986432113908350621709500259738986355427719674282224875758676575234
4220207573630569498825087968928162753848863396909959826280956121450994
8717012445164612603790293091208890869420285106401821543994571568059418
7274899809425474217358240106367740459574178516082923013535808184009699
6372524230560855903700624271243416909004153690105933983835777939410970
0277534720000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
</PRE>
<P>If this doesn't work because your computer is too small, try a
more reasonably sized example, such as the factorial of 200.
<P><H2>Play with the Procedures</H2>
<P>This chapter has introduced a lot of new ideas at once, leaving out all the
details. Our hope has been to convey the <EM>flavor</EM> of Scheme
programming, before we get into Chapter 2, which is full of those missing
details. But you can't absorb the flavor just by reading;
take some time out to play with these examples before you go on.
<P><H2>Exercises</H2>
<P><B>1.1</B> Do 20 push-ups.
<P><B>1.2</B> Calculate 1000 factorial by hand and see if the computer got the right
answer.
<P><B>1.3</B> Create a file called <CODE>acronym.scm</CODE> containing our acronym program, using
the text editor provided for use with your version of Scheme. Load the file
into Scheme and run the program. Produce a transcript file called <CODE>acronym.log</CODE>, showing your interaction with Scheme as you test the program
several times, and print it.
<P>
<HR>
<A NAME="ft1" HREF="showing.html#text1">[1]</A> In some versions of Scheme you might see <CODE>()</CODE> instead
of <CODE>#F</CODE>.<P>
<A NAME="ft2" HREF="showing.html#text2">[2]</A> Pig
Latin is a not-very-secret secret language that many little kids learn.
Each word is translated by moving all the initial consonants to the end of
the word, and adding "ay" at the end. It's usually spoken rather than
written, but that's a little harder to do on a computer.<P>
<A NAME="ft3" HREF="showing.html#text3">[3]</A> What's an <EM>algorithm</EM>? It's a method for solving a
problem. The usual analogy is to a recipe in cooking, although you'll see
throughout this book that we want to get away from the aspect of that
analogy that emphasizes the <EM>sequential</EM> nature of a recipe—first do
this, then do that, etc. There can be more than one algorithm to solve the
same problem.<P>
<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P>
<A HREF="part1.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch2/functions.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|