34.png « hills_white « MapPartsWhite « extracted-1688-map « imgs « magic-bird « js - tour

blob: df87d377385d07dc3b6d549545ea5402c2bbd9b0 (plain)

ofs	hex dump	ascii
0000	89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 00 00 00 47 00 00 00 18 08 06 00 00 00 a8 68 e0	.PNG........IHDR...G..........h.
0020	3d 00 00 04 2e 49 44 41 54 78 da ed 99 0f 68 4d 71 18 86 37 94 cd 16 b3 cc 1a 21 84 b4 2c 2b 6b	=....IDATx....hMq..7......!..,+k
0040	32 6d 59 69 a2 44 a4 89 c8 9a 44 13 69 6b 6b d1 16 89 b6 16 59 b2 b6 dc 34 b9 59 77 ad ad 69 ba	2mYi.D....D.ikk.....Y...4.Yw..i.
0060	9a 88 68 9a 88 65 91 2d 44 28 0b f9 93 8c 99 f7 ab e7 d4 b1 4c d6 d4 bd db dc 7a 3a db 39 f7 9c	..h..e.-D(..........L.....z:.9..
0080	bb f3 9e f7 7b bf ef 77 17 12 12 c0 57 6f 6f 6f 58 c8 ff d7 2f 82 4c 13 bb 85 57 f8 45 a3 a8 11	....{..w....WoooX.../.L...W.E...
00a0	a7 45 81 48 1e 69 82 4c 10 f1 62 8b 38 29 ae 88 16 d1 84 28 37 45 87 78 88 58 9b c5 62 31 7b 24	.E.H.i.L..b.8).....(7E.x.X..b1{$
00c0	88 33 45 6c 43 94 c7 a2 50 ac 12 e3 39 9e 28 f6 8b cb e2 bd e8 16 3d e2 8d d8 30 9c 85 19 ed fa	.3ElC...P...9.(.......=...0.....
00e0	39 da 84 ea e7 7d f9 e2 81 28 11 c7 c4 35 f1 51 74 b2 ff be 68 13 b7 c4 5d 5c d6 6e 22 bb ae 91	9....}...(...5.Qt...h...]\.n"...
0100	29 e6 05 bb 20 33 45 b6 38 21 56 ff e5 39 2b 45 83 38 20 72 10 c8 9c 76 5d dc 16 4f c5 57 f1 4a	)....3E.8!V..9+E.8.r...v]..O.W.J
0120	bc 74 39 ac 4a 2c 45 f8 43 e2 94 d8 29 26 06 e2 c6 c7 89 c9 ee 0f 37 77 88 18 44 49 11 fb 78 aa	.t9.J,E.C...)&........7w..DI..x.
0140	d7 ff b6 2c ac c4 c4 3a 91 45 30 97 8b 6a 9c 74 5c d4 e2 1e 3f 22 36 8b 47 e4 55 35 a2 fa c4 13	...,...:.E0..j.t\...?"6.G.U5....
0160	f1 82 f3 ad 74 63 06 7b c3 51 84 66 98 98 65 1d c5 75 cc 84 58 24 d6 f3 64 9e f3 04 df 8a 56 6c	....tc.{.Q.f..e..u..X$..d.....Vl
0180	fe 94 8c e8 e6 0f 35 81 52 06 f1 f7 9c c5 1d 76 f3 45 a2 54 54 20 52 2e e2 17 b1 cf f9 ec 1f 7c	......5.R......v.E.TT.R........\|
01a0	7e 07 e5 f7 9d 7d af 71 53 dc 60 04 8a 15 e9 e2 b0 98 f1 9b e3 63 45 b8 98 83 43 ec 49 8f 61 df	~....}.qS.`..........cE...C.I.a.
01c0	64 ba 91 09 1b 3a c8 07 15 49 39 bd 22 77 2a 69 f5 7e 02 bb 5e 9c 17 67 c4 11 b6 4d b8 b4 8d 73	d....:...I9."w*i.~..^..g...M...s
01e0	6a e1 24 42 df a0 3b 9a 9b d6 8a a9 7f 6a 1e fd 1d 88 13 69 41 90 59 eb 70 8b dd 78 1d 82 34 71	j.$B..;......j.....iA.Y.p..x..4q
0200	93 cd b4 7b 2f 4e 3a 83 58 35 94 55 15 a2 d4 d1 01 0b 79 cf 1d 4a f0 82 38 27 0e 12 e0 c9 8e d3	...{/N:.X5.U......y..J..8'......
0220	1d 53 58 7e 0d 85 61 f1 38 8e 31 21 3c 88 e4 a3 74 ab d8 5e 46 b4 26 1a 40 01 39 d5 89 08 b9 cc	.SX~..a.8.1!<...t..^F.&.@.9.....
0240	4d f9 b8 d0 3a 9d f3 b2 72 fc 2c 3e 89 2f b8 6f b9 19 c4 2a 21 98 c5 b1 a7 de 85 2b bc 38 c3 8b	M...:...r.,>./.o...*!......+.8..
0260	08 8d 08 73 18 07 1c e3 98 13 e0 c5 08 91 87 28 e5 9c 77 95 46 d1 83 38 96 57 47 45 06 dd b5 00	...s...........(..w.F..8.WGE....
0280	2c 4b 9f 07 ab 30 39 38 a4 91 32 6a c0 39 a5 88 65 37 79 8f ee 55 cf 94 ed 41 9c 13 08 e4 81 73	,K...098..2j.9..e7y..U...A.....s
02a0	9c 53 ca 75 ad cd 97 f1 5e 3f a5 d6 80 48 76 7c 17 79 f7 2c 18 85 09 e3 66 aa c8 1e 27 4b 4e 53	.S.u....^?...Hv\|.y.,....f...'KNS
02c0	66 65 74 a9 1a 84 ab 40 10 1f a2 79 b9 d1 12 8e 79 09 e7 72 c6 84 25 34 95 85 62 07 e7 35 b0 de	fet....@...y....y..r..%4..b..5..
02e0	4b 65 d9 62 9f 5d 1c 8c e2 4c 14 7b 98 51 26 30 42 94 e0 90 2b 3c dd f9 74 ca d1 88 b9 82 6e f4	Ke.b.]...L.{.Q&0B...+<..t.....n.
0300	8d d1 62 2f 83 a1 8d 20 1b 11 fb 2b 63 88 09 17 3e 14 97 1a 19 74 95 76 5c e0 c1 29 4e 07 ca 05	..b/.......+c...>....t.v\..)N...
0320	8f ab 65 a7 33 4a 4c c7 15 99 94 50 07 db 74 06 d4 49 d6 8d c4 5c b6 01 99 a0 23 07 9a f4 7a ff	..e.3JL....P..t..I...\....#...z.
0340	28 b1 89 8c 79 49 10 bf 20 57 7c b8 a2 99 b0 cc 42 a0 52 82 77 2b a2 26 21 52 14 ce 72 dc 37 27	(...yI...W\|.....B.R.w+.&!R..r.7'
0360	10 22 24 b0 9a 8e ee b3 b0 b4 ee 51 37 c0 6b 15 d0 7a 6d a1 79 91 61 ce 5a ee 25 e6 95 27 1c 37	."$........Q7.k..zm.y.a.Z.%..'.7
0380	f7 ac 21 33 c6 bb 4a 2a 0f c1 e6 f5 23 7c c4 bf bc f1 bd 8c dc 99 ae 75 cf 72 9e c6 74 a6 e2 44	..!3..J*....#\|.........u.r..t..D
03a0	ac fb 81 36 99 4a bd 77 33 ba 3f 73 ce ff cd f5 b7 72 9d 68 ce 6b 45 98 77 74 0f 2f 4b 95 dd 64	...6.J.w3.?s.....r.h.kE.wt./K..d
03c0	44 19 cb 85 6c ba 4d 3e 61 1a 11 08 57 84 52 a7 51 7d f7 f7 f9 3d 89 74 b7 e4 5f c0 d3 2b 27 23	D...l.M>a...W.R.Q}...=.t.._..+'#
03e0	2a 29 09 2f 63 7e 3a 75 1f 8f 88 7e 5c 51 cb d6 4f e9 d4 d3 a2 6f b3 af 05 07 55 f0 65 59 0c 8b	*)./c~:u...~\Q..O....o....U.eY..
0400	df 88 a1 16 a8 e1 74 9b 58 d6 5f 39 08 65 01 ba 9d c9 73 0d 53 ad f3 ed 5f 17 e1 7b 1e 61 8b 10	......t.X._9.e....s.S..._..{.a..
0420	ab 9d dc f1 b9 66 94 65 c3 fd fb e3 34 1c 97 c0 ba a7 8b 52 bc 85 30 56 66 b3 c9 a1 16 f7 22 d1	.....f.e....4......R..0Vf.....".
0440	1c 33 12 bf 74 8f 23 c3 6c 36 49 fc ff 6f 88 21 f0 fa 09 96 aa 28 f4 ea 12 64 f0 00 00 00 00 49	.3..t.#.l6I..o.!.....(...d.....I
0460	45 4e 44 ae 42 60 82	END.B`.

<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> <IMG SRC="../simply.jpg" ALT="cover photo"> <TD valign="center"> <CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian Harvey</A> <A HREF="http://www.cnmat.berkeley.edu/~matt">Matthew Wright</A> University of California, Berkeley</CITE> <A HREF="http://www-mitpress.mit.edu/book-home.tcl?isbn=0262082810">MIT Press web page for Simply Scheme</A> </TABLE> <A HREF="../simply-toc.html">(back to Table of Contents)</A> <HR> 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. 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 such and such!" 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. <H2>Lists and Sentences</H2> 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. 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. We prefer to have it both ways. We want to spare beginning students the risk of accidentally constructing ill-formed lists such as <PRE>((((() . D) . C) . B) . A) </PRE> 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 sentence abstract data type.* 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. <BLOCKQUOTE>*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.</BLOCKQUOTE>We defer structured lists until we have higher-order functions and recursion, the tools we need to be able to use the structure effectively.* 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. <BLOCKQUOTE>*Even then, we take lists as a primitive data type. We don't teach about pairs or improper lists, except as a potential pitfall.</BLOCKQUOTE><H2>Sentences and Words</H2> We haven't said what a word 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.* 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.) <BLOCKQUOTE>*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.</BLOCKQUOTE>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. <H2>Overloading in the Text Abstraction</H2> 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.) 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.) 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>. 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. 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. <H2>Higher-Order Procedures, Lambda, and Recursion</H2> 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. 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. <H2>Mutators and Environments</H2> 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 SICP.) 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.* 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. <BLOCKQUOTE>*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.</BLOCKQUOTE>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. <A HREF="../simply-toc.html">(back to Table of Contents)</A> </HTML>