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/ssch3/people.html | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch3/people.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch3/people.html | 486 |
1 files changed, 486 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch3/people.html b/js/games/nluqo.github.io/~bh/ssch3/people.html new file mode 100644 index 0000000..a4d75ab --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch3/people.html @@ -0,0 +1,486 @@ +<P> + +<P><A NAME="bucket"></A><CENTER><IMG SRC="../ss-pics/bucket.jpg" ALT="figure: bucket"></CENTER><P><CENTER>In a bucket brigade, each person hands a result to the +next. +</CENTER><P> + +<HTML> +<HEAD> +<TITLE>Simply Scheme: Introducing Computer Science ch 3: Expressions</TITLE> +</HEAD> +<BODY> +<HR> +<CITE>Simply Scheme:</CITE> +<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT +<H2>Chapter 3</H2> +<H1>Expressions</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/ssch03.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="part2.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch4/defining.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>The interaction between you and Scheme is called the +"read-eval-print loop." Scheme reads what you type, <EM>evaluates</EM> +it, and prints the answer, and then does the same thing over again. We're +emphasizing the word "evaluates" because the essence of understanding +Scheme is knowing what it means to evaluate something. + +<P>Each question you type is called an <EM>expression.</EM><A NAME="text1" HREF="people.html#ft1">[1]</A> The +expression can be a single value, such as <CODE>26</CODE>, or something more +complicated in parentheses, such as <CODE>(+ 14 7)</CODE>. The first kind of +expression is called an <EM>atom</EM> (or <EM><A NAME="g1"></A><A NAME="g2"></A>atomic expression</EM>), while the second kind of expression is +called a <EM><A NAME="g3"></A><A NAME="g4"></A>compound expression,</EM> because it's made out of the +smaller expressions <CODE>+</CODE>, <CODE>14</CODE>, and <CODE>7</CODE>. The metaphor is from +chemistry, where atoms of single elements are combined to form chemical +compounds. We sometimes call the expressions within a compound expression +its <EM>subexpressions.</EM> + +<P>Compound expressions tell Scheme to "do" a procedure. This idea is so +important that it has a lot of names. You can <EM>call</EM> a procedure; you +can <EM>invoke</EM> a procedure; or you can <EM>apply</EM> a procedure to some +numbers or other values. All of these mean the same thing. + +<P>If you've programmed before in some other language, you're probably +accustomed to the idea of several different types of statements for +different purposes. For example, a "print statement" may look very +different from an "assignment statement." In Scheme, everything is done by +calling procedures, just as we've been doing here. Whatever you want to do, +there's only one notation: the compound expression. + +<P>Notice that we said a compound expression contains expressions. This means +that you can't understand what an expression is until you already understand +what an expression is. This sort of circularity comes up again and again +and again and again<A NAME="text2" HREF="people.html#ft2">[2]</A> in Scheme programming. How do +you ever get a handle on this self-referential idea? The secret is that +there has to be some simple kind of expression that <EM>doesn't</EM> have +smaller expressions inside it—the atomic expressions. + +<P>It's easy to understand an expression that just contains one number. +Numbers are <EM>self-evaluating;</EM> that is, when you evaluate a +<A NAME="g5"></A> +<A NAME="g6"></A> +number, you just get the same number back. + +<P>Once you understand <EM>numbers,</EM> you can understand <EM>expressions +that add up</EM> numbers. And once you understand <EM>those</EM> expressions, +you can use that knowledge to figure out <EM>expressions that add up</EM> +expressions-that-add-up-numbers. Then and so on. In practice, you +don't usually think about all these levels of complexity separately. You +just think, "I know what a number is, and I know what it means to add up +<EM>any</EM> expressions." + +<P> +So, for example, to understand the expression + +<P><PRE>(+ (+ 2 3) (+ 4 5)) +</PRE> + +<P>you must first understand <CODE>2</CODE> and <CODE>3</CODE> as self-evaluating +numbers, then understand <CODE>(+ 2 3)</CODE> as an expression that adds those +numbers, then understand how the sum, 5, contributes to the overall +expression. + +<P> +By the way, in ordinary arithmetic you've gotten used to the idea that +parentheses can be optional; 3+4×5 means the same as 3+(4×5). +But in Scheme, parentheses are <EM>never</EM> optional. Every procedure call +must be enclosed in parentheses. + +<P><H2>Little People</H2> + +<P>You may not have realized it, but inside your computer there are thousands +of little people. Each of them is a specialist in one particular +Scheme procedure. The head little person, Alonzo, is in charge of the +read-eval-print loop. + +<P> +When you enter an expression, such as + +<P><PRE>(- (+ 5 8) (+ 2 4)) +</PRE> + +<P>Alonzo reads it, hires other little people to help him evaluate +it, and finally prints <CODE>7</CODE>, its value. We're going to focus on the +evaluation step. + +<P> +Three little people work together to evaluate the expression: a minus person +and two plus people. (To make this account easier to read, we're using the +ordinary English words "minus" and "plus" to refer to the procedures +whose Scheme names are <CODE>-</CODE> and <CODE>+</CODE>. Don't be confused by this and +try to type <CODE>minus</CODE> to Scheme.) + +<P>Since the overall expression is a subtraction, Alonzo hires Alice, the first +available minus specialist. Here's how the little people evaluate the +expression: + +<P><P><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Alice wants to be given some numbers, so before she can do any work, she +complains to Alonzo that she wants to know which numbers to subtract. + +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Alonzo looks at the subexpressions that should provide Alice's +arguments, namely, <CODE>(+ 5 8)</CODE> and <CODE>(+ 2 4)</CODE>. Since both of these are +addition problems, Alonzo hires two plus specialists, Bernie and Cordelia, +and tells them to report their results to Alice. + +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The first plus person, Bernie, also wants some numbers, so he asks +Alonzo for them. + +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Alonzo looks at the subexpressions of <CODE>(+ 5 8)</CODE> that should provide +Bernie's arguments, namely, <CODE>5</CODE> and <CODE>8</CODE>. Since these are both +atomic, Alonzo can give them directly to Bernie. + +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Bernie adds his arguments, <CODE>5</CODE> and <CODE>8</CODE>, to get <CODE>13</CODE>. He +does this in his head—we don't have to worry about how he knows how to +add; that's his job. + +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The second plus person, Cordelia, wants some arguments; Alonzo looks at +the subexpressions of <CODE>(+ 2 4)</CODE> and gives the <CODE>2</CODE> and <CODE>4</CODE> to +Cordelia. She adds them, getting <CODE>6</CODE>. + +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Bernie and Cordelia hand their results to the waiting Alice, who can now +subtract them to get <CODE>7</CODE>. She hands that result to Alonzo, who prints +it. + +</TABLE><P> +How does Alonzo know what's the argument to what? That's what the grouping +of subexpressions with parentheses is about. Since the plus expressions are +inside the minus expression, the plus people have to give their results to +the minus person. + +<P>We've made it seem as if Bernie does his work before Cordelia does hers. In +fact, the <EM><A NAME="g7"></A><A NAME="g8"></A>order of evaluation</EM> of the argument subexpressions +is not specified in Scheme; different implementations may do it in different +orders. In particular, Cordelia might do her work before Bernie, or they +might even do their work at the same time, if we're using a <EM>parallel +processing</EM> computer. However, it <EM>is</EM> important that both Bernie +and Cordelia finish their work before Alice can do hers. + +<P>The entire call to <CODE>-</CODE> is itself a single expression; it could be a +part of an even larger expression: + +<P><PRE>> (* (- (+ 5 8) (+ 2 4)) + (/ 10 2)) +35 +</PRE> + +<P>This says to multiply the numbers 7 and 5, except that instead of +saying 7 and 5 explicitly, we wrote expressions whose values are 7 and 5. +(By the way, we would say that the above expression has three +subexpressions, the <CODE>*</CODE> and the two arguments. The argument +subexpressions, in turn, have their own subexpressions. However, these +sub-subexpressions, such as <CODE>(+ 5 8)</CODE>, don't count as +subexpressions of the whole thing.) + +<P>We can express this organization of little people more formally. If +an expression is atomic, Scheme just knows the value.<A NAME="text3" HREF="people.html#ft3">[3]</A> Otherwise, it is a compound +expression, so Scheme first evaluates all the subexpressions (in some +unspecified order) and then applies the value of the first one, +which had better be a procedure, to the values of the rest of them. +Those other subexpressions are the arguments. + +<P>We can use this rule to evaluate arbitrarily complex expressions, and +Scheme won't get confused. No matter how long the expression is, it's made +up of smaller subexpressions to which the same rule applies. +Look at this long, messy example: +<A NAME="g9"></A> + +<P><PRE>> (+ (* 2 (/ 14 7) 3) + (/ (* (- (* 3 5) 3) (+ 1 1)) + (- (* 4 3) (* 3 2))) + (- 15 18)) +13 +</PRE> + +<P>Scheme understands this by looking for the subexpressions of the overall +expression, like this: + +<P><PRE>(+ () + ( ; One of them takes two lines but you can tell by + ) ; matching parentheses that they're one expression. + ()) +</PRE> + +<P>(Scheme ignores everything to the right of a semicolon, so +semicolons can be used to indicate comments, as above.) + +<P> +Notice that in the example above we asked <CODE>+</CODE> to add <EM>three</EM> +numbers. In the <CODE>functions</CODE> program of Chapter 2 we +pretended that every Scheme function accepts a fixed number of arguments, +but actually, some functions can accept any number. These include <CODE>+</CODE>, +<CODE>*</CODE>, <CODE>word</CODE>, and <CODE>sentence</CODE>. + +<P><H2>Result Replacement</H2> + +<P><A NAME="g10"></A> +<A NAME="g11"></A> +Since a little person can't do his or her job until all of the necessary +subexpressions have been evaluated by other little people, we can "fast +forward" this process by skipping the parts about "Alice waits for Bernie +and Cordelia" and starting with the completion of the smaller tasks by the +lesser little people. + +<P>To keep track of which result goes into which larger computation, you can +write down a complicated expression and then <EM>rewrite</EM> it repeatedly, +each time replacing some small expression with a simpler expression +that has the same value. + +<P><PRE>(+ (* <CODE STYLE="border:solid">(- 10 7)</code> (+ 4 1)) (- 15 (/ 12 3)) 17) +(+ (* 3 <CODE STYLE="border:solid">(+ 4 1)</code>) (- 15 (/ 12 3)) 17) +(+ <CODE STYLE="border:solid">(* 3 5 )</code> (- 15 (/ 12 3)) 17) +(+ 15 (- 15 <CODE STYLE="border:solid">(/ 12 3)</code>) 17) +(+ 15 <CODE STYLE="border:solid">(- 15 4 )</code> 17) +<CODE STYLE="border:solid">(+ 15 11 17)</code> +43 +</PRE> + +<P>In each line of the diagram, the boxed expression +is the one that will be replaced with its value on the following line. + +<P>If you like, you can save some steps by evaluating <EM>several</EM> small +expressions from one line to the next: + +<P><PRE>(+ (* <CODE STYLE="border:solid">(- 10 7)</code> <CODE STYLE="border:solid">(+ 4 1)</code>) (- 15 <CODE STYLE="border:solid">(/ 12 3)</code>) 17) +(+ <CODE STYLE="border:solid">(* 3 5 )</code> <CODE STYLE="border:solid">(- 15 4 )</code> 17) +<CODE STYLE="border:solid">(+ 15 11 17)</code> +43 +</PRE> + +<P><H2>Plumbing Diagrams</H2> +<A NAME="crank"></A> + +<P>Some people find it helpful to look at a pictorial form of the connections +among subexpressions. You can think of each procedure as a machine, like the +<A NAME="g12"></A> +<A NAME="g13"></A> +ones they drew on the chalkboard in junior high school. + +<P><CENTER><IMG SRC="../ss-pics/function.jpg" ALT="figure: function"></CENTER> + +<P>Each machine has some number of input hoppers on the top and one chute at the +bottom. You put something in each hopper, turn the crank, and something else +comes out the bottom. For a complicated expression, you hook up the output +chute of one machine to the input hopper of another. These combinations are +called "plumbing diagrams." Let's look at the <A NAME="g14"></A><A NAME="g15"></A>plumbing diagram +for <CODE>(- (+ 5 8) (+ 2 4))</CODE>: +<CENTER><IMG SRC="../ss-pics/plumbing.jpg" ALT="figure: plumbing"></CENTER> + +<P>You can annotate the diagram by indicating the actual information that flows +through each pipe. Here's how that would look for this expression: + +<P><CENTER><IMG SRC="../ss-pics/annotated.jpg" ALT="figure: annotated"></CENTER> + +<P><H2>Pitfalls</H2> + +<P>One of the biggest problems that beginning Lisp programmers have comes +from trying to read a program from left to right, rather than thinking about +it in terms of expressions and subexpressions. For example, + +<P><PRE>(square (cos 3)) +</PRE> + +<P><EM>doesn't</EM> mean "square three, then take the cosine of +the answer you get." Instead, as you know, it means that the argument to +<CODE>square</CODE> is the return value from <CODE>(cos 3)</CODE>. + +<P>Another big problem that people have is thinking that Scheme cares +about the spaces, tabs, line breaks, and other "white space" in their +Scheme programs. We've been indenting our expressions to illustrate the way +that subexpressions line up underneath each other. But to Scheme, +<A NAME="g16"></A> + +<P><PRE>(+ (* 2 (/ 14 7) 3) (/ (* (- (* 3 5) 3) (+ 1 +1)) (- (* 4 3) (* 3 2))) (- 15 18)) +</PRE> + +<P>means the same thing as + +<P><PRE>(+ (* 2 (/ 14 7) 3) + (/ (* (- (* 3 5) 3) (+ 1 1)) + (- (* 4 3) (* 3 2))) + (- 15 18)) +</PRE> + +<P>So in this expression: + +<P><PRE>(+ (* 3 (sqrt 49) ;; weirdly formatted + (/ 12 4))) +</PRE> + +<P>there aren't two arguments to <CODE>+</CODE>, even though it looks that +way if you think about the indenting. What Scheme does is look at the +parentheses, and if you examine these carefully, you'll see that there are +three arguments to <CODE>*</CODE>: the atom <CODE>3</CODE>, the compound expression <CODE>(sqrt 49)</CODE>, and the compound expression <CODE>(/ 12 4)</CODE>. (And there's only one +argument to <CODE>+</CODE>.) + +<P>A consequence of Scheme's not caring about white space is that when you +hit the return key, Scheme might not do anything. If you're in the middle +of an expression, Scheme waits until you're done typing the entire thing +before it evaluates what you've typed. This is fine if your program is +correct, but if you type this in: + +<P><PRE>(+ (* 3 4) + (/ 8 2) ; note missing right paren +</PRE> + +<P>then <EM>nothing</EM> will happen. Even if you type forever, until +you close the open parenthesis next to the <CODE>+</CODE> sign, Scheme will still +be reading an expression. So if Scheme seems to be ignoring you, try typing +a zillion close parentheses. (You'll probably get an error message about +too many parentheses, but after that, Scheme should start paying attention +again.) + +<P>You might get into the same sort of trouble if you have a double-quote +mark (<CODE>"</CODE>) in your program. Everything inside a pair of quotation marks +is treated as one single <EM>string.</EM> We'll explain more about +strings later. For now, if your program has a stray quotation mark, like +this: + +<P><PRE>(+ (* 3 " 4) ; note extra quote mark + (/ 8 2)) +</PRE> + +<P>then you can get into the same predicament of typing and having +Scheme ignore you. (Once you type the second quotation mark, you may still +need some close parentheses, since the ones you type inside a string +don't count.) + +<P>One other way that Scheme might seem to be ignoring you comes from the +fact that you don't get a new Scheme prompt until you type in an expression +and it's evaluated. So if you just hit the <CODE>return</CODE> or <CODE>enter</CODE> key +without typing anything, most versions of Scheme won't print a new prompt. + +<P><H2>Boring Exercises</H2> + +<P><B>3.1</B> Translate the arithmetic expressions (3+4)×5 and 3+(4×5) +into Scheme expressions, and into plumbing diagrams. + + +<P> +<B>3.2</B> How many little people does Alonzo hire in evaluating each +of the following expressions: + +<PRE>(+ 3 (* 4 5) (- 10 4)) + +(+ (* (- (/ 8 2) 1) 5) 2) + +(* (+ (- 3 (/ 4 2)) + (sin (* 3 2)) + (- 8 (sqrt 5))) + (- (/ 2 3) + 4)) +</PRE> + +<P> +<B>3.3</B> Each of the expressions in the previous exercise is compound. How many +subexpressions (not including subexpressions of subexpressions) does each +one have? + +<P>For example, + +<P><PRE>(* (- 1 (+ 3 4)) 8) +</PRE> + +<P>has three subexpressions; you wouldn't count <CODE>(+ 3 4)</CODE>. + + +<P> + +<B>3.4</B> Five little people are hired in evaluating the following expression: + +<PRE>(+ (* 3 (- 4 7)) + (- 8 (- 3 5))) +</PRE> + +Give each little person a name and list her specialty, the argument values +she receives, her return value, and the name of the little person to whom +she tells her result. + +<P> +<B>3.5</B> Evaluate each of the following expressions using the result replacement +technique: + +<P><PRE>(sqrt (+ 6 (* 5 2))) + +(+ (+ (+ 1 2) 3) 4) +</PRE> + + +<P> +<B>3.6</B> Draw a plumbing diagram for each of the following expressions: + +<PRE>(+ 3 4 5 6 7) + +(+ (+ 3 4) (+ 5 6 7)) + +(+ (+ 3 (+ 4 5) 6) 7) +</PRE> + +<P> +<B>3.7</B> What value is returned by <CODE>(/ 1 3)</CODE> in your version of +Scheme? (Some Schemes return a decimal fraction like <CODE>0.33333</CODE>, while +others have exact fractional values like <CODE>1/3</CODE> built in.) + + +<P><B>3.8</B> Which of the functions that you explored in Chapter 2 will +accept variable numbers of arguments? + + +<P> +<H2>Real Exercises</H2> + +<P><B>3.9</B> The expression <CODE>(+ 8 2)</CODE> has the value <CODE>10</CODE>. It is a compound +expression made up of three atoms. For this problem, write five other +Scheme expressions whose values are also the number ten: + +<P><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">An atom + +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Another compound expression made up of three atoms + +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">A compound expression made up of four atoms + +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">A compound expression made up of an atom and two compound subexpressions + +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Any other kind of expression + +</TABLE><P> + +<P> + +<HR> +<A NAME="ft1" HREF="people.html#text1">[1]</A> In +other programming languages, the name for what you type might be a +"command" or an "instruction." The name "expression" is meant to +emphasize that we are talking about the notation in which you ask the +question, as distinct from the idea in your head, just as in English you +express an idea in words. Also, in Scheme we are more often asking +questions rather than telling the computer to take some action.<P> +<A NAME="ft2" HREF="people.html#text2">[2]</A> and again<P> +<A NAME="ft3" HREF="people.html#text3">[3]</A> We'll +explain this part in more detail later.<P> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="part2.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch4/defining.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |