*

1 files changed, 533 insertions, 0 deletions

diff --git a/js/games/nluqo.github.io/~bh/ssch1/showing b/js/games/nluqo.github.io/~bh/ssch1/showing
new file mode 100644
index 0000000..22546ef
--- /dev/null
+++ b/js/games/nluqo.github.io/~bh/ssch1/showing
@@ -0,0 +1,533 @@
+\input bkmacs
+% \photo{Scheme-Brained Hare}{\pagetag{\hare}\poop{Polly Jordan drawing}}
+\photo{Scheme-Brained Hare}{\pagetag{\hare}
+\pspicture{4in}{hare}{hare}{\TrimTop{60pt}\TrimRight{15pt}}}
+\chapter{Showing Off Scheme}
+\chaptag{\showing}
+
+We are going to use the programming language Scheme to teach you some big
+ideas in computer science.  The ideas are mostly about {\it
+\bkidx{control of}{complexity}---\/}that is, about how to develop a
+large computer program without being swamped in details.
+
+For example, once you've solved part of the large problem, you can give that
+partial solution a {\it name\/} 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 {\it \idx{abstraction},\/}
+which we'll discuss in more depth throughout the book.
+
+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.)
+
+\subhd{Talking to Scheme}
+
+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 {\tt simply.scm}, which you need to make the
+examples in this book work.
+
+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:
+
+{\prgex%
+Welcome to XYZ Brand Scheme.
+>
+}
+
+\noindent The {\tt >} is a {\it \idx{prompt},\/} Scheme's way of telling you
+that it's ready for you to type something.  Scheme is an {\it interactive\/}
+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:
+
+{\prgex%
+> \pmb{6}
+6
+}
+
+\noindent We just asked Scheme, ``What is 6?'' and Scheme told us that 6 is
+6.  Most of the time we ask harder questions:
+
+{\prgex%
+> \pmb{(+ 4 7)}
+11
+> \pmb{(- 23 5)}
+18
+> \pmb{(+ 5 6 7 8)}
+26
+}
+
+\noindent Whenever something you type to Scheme is enclosed in parentheses,
+\justidx{parentheses, for procedure invocation}
+it indicates a request to carry out a {\it \idx{procedure}.\/} (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 {\it \idx{argument}s,\/} i.e., values
+that are used as data by the procedure.
+
+Scheme has non-numeric procedures, too:
+
+{\prgex%
+> \pmb{(word 'comp 'uter)}
+COMPUTER
+}
+
+\noindent (If this last example gives an error message saying
+that Scheme doesn't understand the name {\tt word}, it means that you
+didn't load the file {\tt simply.scm}.  Consult Appendix A.)
+
+In these first examples, we've shown what you type in {\tt \pmb{boldface}} and
+what the computer responds in {\tt lightface}.  Hereafter, we will rely on
+the prompt characters to help you figure out who's talking on which line.
+
+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.
+
+\subhd{Recovering from Typing Errors}
+
+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.
+
+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,
+{\tt ))))))}, and hitting the {\tt return} or {\tt enter} 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.)
+
+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
+\justidx{error messages}
+error.  Here's an example; for now, never mind exactly why this is an
+error.  We just want to talk about the result:
+
+{\prgex%
+> (+ 2 a)
+
+Unbound variable a
+;Package: (user)
+
+2 Error->
+}
+
+\noindent 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 {\it \idx{debugger}\/}
+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.)
+
+\vskip 12pt
+% kludge to prevent repagination on last-minute 2/e fix.
+
+\subhd{Exiting Scheme}
+
+Although there's no official standard way to exit Scheme, most versions
+use the notation
+
+{\prgex%
+> (\prgidx{exit})
+}
+
+\noindent 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.)
+
+\subhd{More Examples}
+
+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.
+
+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 {\tt first} and {\tt keep}, 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 {\it kinds\/} 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.
+
+Besides learning the {\it vocabulary\/} 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 {\tt print} in these examples.
+
+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.
+
+\subhd{Example:\ Acronyms}
+
+Here's our first new program.  So far we have just been using procedures
+built into Scheme: {\tt +}, {\tt -}, and {\tt word}.  When you first start
+up Scheme, it knows 100--200 procedures.  These are called {\it primitive\/}
+\justidx{procedure, primitive}
+\justidx{primitive procedure}
+\justidx{procedure, compound}
+\justidx{compound procedure}
+procedures.  Programming in Scheme means defining new procedures, called
+{\it compound\/} procedures.  Right now we're going to invent one that finds
+the acronym for a title:
+
+{\prgexskipamount=10pt\prgexbaselineamount=10.5pt
+{\prgex%
+(define (\ufun{acronym} phrase)
+  (accumulate word (every first phrase)))
+
+> (acronym '(american civil liberties union))
+ACLU
+
+> (acronym '(reduced instruction set computer))
+RISC
+
+> (acronym '(quod erat demonstrandum))
+QED
+}
+
+Did you have trouble figuring out what all the pieces do in the {\tt
+acronym} procedure?  Try these examples:
+
+{\prgex%
+> (first 'american)
+A
+
+> (every first '(american civil liberties union))
+(A C L U)
+
+> (accumulate word '(a c l u))
+ACLU
+}
+
+Notice that this simple {\tt acronym} program doesn't always do exactly what
+you might expect:
+
+{\prgex%
+> (acronym '(united states of america))
+USOA
+}
+
+\noindent We can rewrite the program to leave out certain words:
+
+{\prgex%
+(define (\ufun{acronym} phrase)
+  (accumulate word (every first (keep real-word? phrase))))
+
+(define (\ufun{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\pgfoot
+
+> (keep real-word? '(united network command for law and enforcement))
+(UNITED NETWORK COMMAND LAW ENFORCEMENT)
+}
+\vfootnt{In some versions of Scheme you might see {\tt ()} instead
+of {\tt \#F}.}
+} %%% skip kludge
+
+\subhd{Example:\ Pig Latin}
+
+Our next example translates a word into \bkidx{Pig}{Latin}.\footnt{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.}
+
+\pagetag{\pig}
+% \picture{1.9in}{Pig speaking Latin}
+% ingualay atinalay orcinapay
+\pspicture{1.9in}{pig}{pig}{\TrimBoundingBox{14pt}}
+
+{\let\goodbreak=\relax\prgex%
+(define (\ufun{pigl} wd)
+  (if (member? (first wd) 'aeiou)
+      (word wd 'ay)
+      (pigl (word (butfirst wd) (first wd)))))
+
+> (pigl 'spaghetti)
+AGHETTISPAY
+
+> (pigl 'ok)
+OKAY
+}\penalty10000\vskip 6pt
+(By the way, if you've used other programming languages before, don't fall
+\justidx{lines of a program}
+into the trap of thinking that each line of the {\tt pigl} definition is a
+``statement'' and that the\penalty-10000 statements\penalty-200\ 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 {\tt pigl} on one humongous line and it would mean the
+same thing.  Also, Scheme doesn't care about how we've indented the lines so
+\justidx{indentation in a program}
+that subexpressions line up under each other.  We do that only to make the
+program more readable for human beings.)
+
+The procedure follows one of two possible paths, depending on whether the
+first letter of the given word is a vowel.  If so, {\tt pigl} just adds
+the letters {\tt ay} at the end:
+
+{\prgex%
+> (pigl 'elephant)
+ELEPHANTAY
+}
+
+The following examples might make it a little more clear how the
+starting-consonant case works:
+
+{\prgex%
+> (first 'spaghetti)
+S
+
+> (butfirst 'spaghetti)
+PAGHETTI
+
+> (word 'paghetti 's)
+PAGHETTIS
+
+> (define (\ufun{rotate} wd)
+    (word (butfirst wd) (first wd)))
+
+> (rotate 'spaghetti)
+PAGHETTIS
+
+> (rotate 'paghettis)
+AGHETTISP
+
+> (pigl 'aghettisp)
+AGHETTISPAY
+}
+
+You've seen {\tt every} before, in the {\tt acronym} example, but we haven't
+told you what it does.  Try to guess what Scheme will respond when you type
+this:
+
+{\prgex%
+(every pigl '(the ballad of john and yoko))
+}
+
+\subhd{Example:\ Ice Cream Choices}
+
+\vskip-2pt
+Here's a somewhat more complicated program, but still pretty short
+considering what it accomplishes:
+
+\vskip-2pt
+{\prgex\blskip8%
+(define (\ufun{choices} menu)
+  (if (null? menu)
+      '(())
+      (let ((smaller (choices (cdr menu))))
+	(reduce append
+		(map (lambda (item) (prepend-every item smaller))
+		     (car menu))))))
+
+(define (\ufun{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))
+}
+
+\noindent 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.
+
+\subhd{Example:\ Combinations from a Set}
+
+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.
+
+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 \idx{algorithm}
+yet.\footnt{What's an {\it algorithm\/}?  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 {\it sequential\/} nature of a recipe---first do
+this, then do that, etc.  There can be more than one algorithm to solve the
+same problem.} Instead, we just want you to marvel at Scheme's ability to
+express difficult techniques succinctly.
+
+{\prgex%
+(define (\ufun{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))
+}
+
+\noindent (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 {\tt A} and contain two more letters; the second group has
+three letters not including {\tt A}.  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 {\tt pigl} and {\tt acronym} procedures.)
+
+If you've taken a probability course, you know that there is a formula for the
+{\it number\/} 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 {\it symbolic\/} computing.  In this example,
+listing the actual combinations instead of just counting them is part of the
+flavor of \swapidx{symbolic}{computing}, along with our earlier examples about
+\justidx{symbolic programming}
+\justidx{programming, symbolic}
+manipulating words and phrases.  We'll try to avoid numeric
+problems when possible, because symbolic computing is more fun
+for most people.
+
+\subhd{Example:\ Factorial}
+
+Scheme can handle numbers, too.  The \idx{factorial} of $n$ (usually written
+in mathematical notation as $n!$) is the product of all the numbers from 1 to
+$n$:
+\justufun{factorial}
+
+{\prgex\prgexpenalty=0%
+(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
+}
+
+\noindent If this doesn't work because your computer is too small, try a
+more reasonably sized example, such as the factorial of 200.
+
+\subhd{Play with the Procedures}
+
+This chapter has introduced a lot of new ideas at once, leaving out all the
+details.  Our hope has been to convey the {\it flavor\/} 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.
+
+\esubhd{Exercises}
+
+{\exercise  Do 20 push-ups.}
+
+{\exercise
+Calculate 1000 factorial by hand and see if the computer got the right
+answer.}
+
+{\exercise
+Create a file called {\tt acronym.scm} 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 {\tt
+acronym.log}, showing your interaction with Scheme as you test the program
+several times, and print it.
+}
+
+\bye