From 562a9a52d599d9a05f871404050968a5fd282640 Mon Sep 17 00:00:00 2001 From: elioat Date: Wed, 23 Aug 2023 07:52:19 -0400 Subject: * --- js/games/nluqo.github.io/~bh/ssch1/showing | 533 +++++++++++++++++++++++++++++ 1 file changed, 533 insertions(+) create mode 100644 js/games/nluqo.github.io/~bh/ssch1/showing (limited to 'js/games/nluqo.github.io/~bh/ssch1/showing') 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 -- cgit 1.4.1-2-gfad0