diff options
| author | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
| commit | 562a9a52d599d9a05f871404050968a5fd282640 (patch) | |
| tree | 7d3305c1252c043bfe246ccc7deff0056aa6b5ab /js/games/nluqo.github.io/~bh/ssch1/showing.html | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch1/showing.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch1/showing.html | 549 |
1 files changed, 549 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch1/showing.html b/js/games/nluqo.github.io/~bh/ssch1/showing.html new file mode 100644 index 0000000..5cd02c5 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch1/showing.html @@ -0,0 +1,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> |