*

1 files changed, 566 insertions, 0 deletions

diff --git a/js/games/nluqo.github.io/~bh/ssch3/people b/js/games/nluqo.github.io/~bh/ssch3/people
new file mode 100644
index 0000000..5e02f9e
--- /dev/null
+++ b/js/games/nluqo.github.io/~bh/ssch3/people
@@ -0,0 +1,566 @@
+\input bkmacs
+\photo{In a bucket brigade, each person hands a result to the
+next.}{\pagetag{\bucket}\pspicture{4in}{bucket}{bucket}{\TrimBoundingBox{8pt}}}
+\chapter{Expressions}
+\chaptag{\people}
+
+The interaction between you and Scheme is called the
+``\idx{read-eval-print loop}.'' Scheme reads what you type, {\it evaluates\/}
+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.
+
+Each question you type is called an {\it \idx{expression}.}\footnt{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.} The
+expression can be a single value, such as {\tt 26}, or something more
+complicated in parentheses, such as {\tt (+ 14 7)}.  The first kind of
+expression is called an {\it atom\/} (or {\it
+\bkidx{atomic}{expression}\/}), while the second kind of expression is
+called a {\it \bkidx{compound}{expression},\/} because it's made out of the
+smaller expressions {\tt +}, {\tt 14}, and {\tt 7}.  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 {\it \idx{subexpression}s.}
+
+Compound expressions tell Scheme to ``do'' a procedure.  This idea is so
+important that it has a lot of names.  You can {\it call\/} a procedure; you
+can {\it invoke\/} a procedure; or you can {\it apply\/} a procedure to some
+numbers or other values.  All of these mean the same thing.
+
+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.
+
+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\footnt{and again} 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 {\it doesn't\/} have
+smaller expressions inside it---the atomic expressions.
+
+It's easy to understand an expression that just contains one number.
+Numbers are {\it self-evaluating;\/} that is, when you evaluate a
+\justidx{expression, self-evaluating}
+\justidx{self-evaluating expression}
+number, you just get the same number back.
+
+Once you understand {\it numbers,\/} you can understand {\it expressions
+that add up\/} numbers.  And once you understand {\it those\/} expressions,
+you can use that knowledge to figure out {\it expressions that add up\/}
+expressions-that-add-up-numbers.  Then \ellipsis\ 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
+{\it any\/} expressions.''
+
+{\advance\medskipamount by -3pt
+
+So, for example, to understand the expression
+
+{\prgex%
+(+ (+ 2 3) (+ 4 5))
+}
+
+\noindent you must first understand {\tt 2} and {\tt 3} as self-evaluating
+numbers, then understand {\tt (+~2~3)} as an expression that adds those
+numbers, then understand how the sum, 5, contributes to the overall
+expression.
+
+} % medskipamount
+
+By the way, in ordinary arithmetic you've gotten used to the idea that
+parentheses can be optional; $3+4\times 5$ means the same as $3+(4\times 5)$.
+But in Scheme, parentheses are {\it never\/} optional.  Every procedure call
+must be enclosed in parentheses.
+
+\subhd{Little People}
+
+You may not have realized it, but inside your computer there are thousands
+of \idx{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.
+
+{\advance\medskipamount by -3pt
+
+When you enter an expression, such as
+
+{\prgex%
+(- (+ 5 8) (+ 2 4))
+}
+
+\noindent Alonzo reads it, hires other little people to help him evaluate
+it, and finally prints {\tt 7}, its value.  We're going to focus on the
+evaluation step.
+
+} % medskipamount
+
+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 {\tt -} and {\tt +}.  Don't be confused by this and
+try to type {\tt minus} to Scheme.)
+
+Since the overall expression is a subtraction, Alonzo hires Alice, the first
+available minus specialist.  Here's how the little people evaluate the
+expression:
+
+\medskip
+{\parindent=1em
+\bb 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.
+
+\bb Alonzo looks at the subexpressions that should provide Alice's
+arguments, namely, {\tt (+~5~8)} and {\tt (+~2~4)}.  Since both of these are
+addition problems, Alonzo hires two plus specialists, Bernie and Cordelia,
+and tells them to report their results to Alice.
+
+\bb The first plus person, Bernie, also wants some numbers, so he asks
+Alonzo for them.
+
+\bb Alonzo looks at the subexpressions of {\tt (+~5~8)} that should provide
+Bernie's arguments, namely, {\tt 5} and {\tt 8}.  Since these are both
+atomic, Alonzo can give them directly to Bernie.
+
+\bb Bernie adds his arguments, {\tt 5} and {\tt 8}, to get {\tt 13}.  He
+does this in his head---we don't have to worry about how he knows how to
+add; that's his job.
+
+\bb The second plus person, Cordelia, wants some arguments; Alonzo looks at
+the subexpressions of {\tt (+~2~4)} and gives the {\tt 2} and {\tt 4} to
+Cordelia.  She adds them, getting {\tt 6}.
+
+\bb Bernie and Cordelia hand their results to the waiting Alice, who can now
+subtract them to get {\tt 7}.  She hands that result to Alonzo, who prints
+it.
+
+}\medskip
+
+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.
+
+We've made it seem as if Bernie does his work before Cordelia does hers.  In
+fact, the {\it \bkidx{order of}{evaluation}\/} 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 {\it parallel
+processing\/} computer.  However, it {\it is\/} important that both Bernie
+and Cordelia finish their work before Alice can do hers.
+
+The entire call to {\tt -} is itself a single expression; it could be a
+part of an even larger expression:
+
+{\prgex%
+> (* (- (+ 5 8) (+ 2 4))
+     (/ 10 2))
+35
+}
+
+\noindent 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 {\tt *} and the two arguments.  The argument
+subexpressions, in turn, have their own subexpressions.  However, these
+sub-subexpressions, such as {\tt (+~5~8)}, don't count as
+subexpressions of the whole thing.)
+
+We can express this organization of little people more formally.  If
+an expression is atomic, Scheme just knows the value.\footnt{We'll
+explain this part in more detail later.} 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 \idx{argument}s.
+
+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:
+\justidx{parentheses, for procedure invocation}
+
+{\advance\medskipamount by -1pt
+{\prgex%
+> (+ (* 2 (/ 14 7) 3)
+     (/ (* (- (* 3 5) 3) (+ 1 1))
+        (- (* 4 3) (* 3 2)))
+     (- 15 18))
+13
+}
+
+Scheme understands this by looking for the subexpressions of the overall
+expression, like this:
+
+{\prgex%
+(+ (\ellipsis)
+   (\ellipsis         ; One of them takes two lines but you can tell by
+      \ellipsis)     ; matching parentheses that they're one expression.
+   (\ellipsis))
+}
+
+\noindent (Scheme ignores everything to the right of a \idx{semicolon}, so
+semicolons can be used to indicate \idx{comments}, as above.)
+
+} % medskipamount
+
+Notice that in the example above we asked {\tt +} to add {\it three\/}
+numbers.  In the {\tt functions} program of Chapter~\functions\ we
+pretended that every Scheme function accepts a fixed number of arguments,
+but actually, some functions can accept any number.  These include {\tt +},
+{\tt *}, {\tt word}, and {\tt sentence}.
+
+\subhd{Result Replacement}
+
+\justidx{result replacement}
+\justidx{replacement, result}
+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.
+
+To keep track of which result goes into which larger computation, you can
+write down a complicated expression and then {\it rewrite\/} it repeatedly,
+each time replacing some small expression with a simpler expression
+that has the same value.
+
+{\prgex%
+(+ (* \zboxit{(- 10 7)} (+ 4 1)) (- 15 (/ 12 3)) 17)
+(+ (* 3        \zboxit{(+ 4 1)}) (- 15 (/ 12 3)) 17)
+(+ \zboxit{(* 3        5      )} (- 15 (/ 12 3)) 17)
+(+ 15                   (- 15 \zboxit{(/ 12 3)}) 17)
+(+ 15                   \zboxit{(- 15 4       )} 17)
+\zboxit{(+ 15                   11              17)}
+43
+}
+
+\noindent In each line of the diagram, the boxed expression
+is the one that will be replaced with its value on the following line.
+
+If you like, you can save some steps by evaluating {\it several\/} small
+expressions from one line to the next:
+
+{\prgex%
+(+ (* \zboxit{(- 10 7)} \zboxit{(+ 4 1)}) (- 15 \zboxit{(/ 12 3)}) 17)
+(+ \zboxit{(* 3        5      )} \zboxit{(- 15 4       )} 17)
+\zboxit{(+ 15                   11              17)}
+43
+}
+
+\subhd{Plumbing Diagrams}
+
+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
+\justidx{function machine}
+\justidx{machine, function}
+ones they drew on the chalkboard in junior high school.  
+
+\pspicture{1.4in}{function}{function}{}
+
+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 \bkidx{plumbing}{diagram}
+for {\tt (- (+ 5 8) (+ 2 4))}:
+\pagetag{\crank}  %% Matt thinks this is a kludge but Brian...
+
+\pspicture{2.5in}{Plumbing Diagram}{plumbing}{\TrimTop{0.5truein}}
+
+You can annotate the diagram by indicating the actual information that flows
+through each pipe.  Here's how that would look for this expression:
+
+\pspicture{2.5in}{Annotated Plumbing Diagram}{annotated}{\TrimTop{0.5truein}
+\TrimBottom{0.15truein}}
+
+\subhd{Pitfalls}
+
+\pit 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,
+
+{\prgex%
+(square (cos 3))
+}
+
+\noindent {\it doesn't\/} mean ``square three, then take the cosine of
+the answer you get.'' Instead, as you know, it means that the argument to
+{\tt square} is the return value from {\tt (cos~3)}.
+
+\pit 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,
+\justidx{indentation}
+
+{\prgex%
+(+ (* 2 (/ 14 7) 3) (/ (* (- (* 3 5) 3) (+ 1
+1)) (- (* 4 3) (* 3 2))) (- 15 18))
+}
+
+\noindent means the same thing as
+
+{\prgex%
+(+ (* 2 (/ 14 7) 3)
+   (/ (* (- (* 3 5) 3) (+ 1 1))
+      (- (* 4 3) (* 3 2)))
+   (- 15 18))
+}
+
+\noindent So in this expression:
+
+{\prgex%
+(+ (* 3 (sqrt 49)                            ;; weirdly formatted
+   (/ 12 4)))
+}
+
+\noindent there aren't two arguments to {\tt +}, 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 {\tt *}:\ the atom {\tt 3}, the compound expression {\tt
+(sqrt~49)}, and the compound expression {\tt (/~12~4)}.  (And there's only one
+argument to {\tt +}.)
+
+\pit 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:
+
+{\prgex%
+(+ (* 3 4)
+   (/ 8 2)                              ; note missing right paren
+}
+
+\noindent then {\it nothing\/} will happen.  Even if you type forever, until
+you close the open parenthesis next to the {\tt +} sign, Scheme will still
+be reading an expression.  So if Scheme seems to be ignoring you, try typing
+a zillion close \idx{parentheses}.  (You'll probably get an error message about
+too many parentheses, but after that, Scheme should start paying attention
+again.)
+
+\pit You might get into the same sort of trouble if you have a double-quote
+mark ({\tt "}) in your program.  Everything inside a pair of quotation marks
+is treated as one single {\it \idx{string}.\/} We'll explain more about
+strings later.  For now, if your program has a stray quotation mark, like
+this:
+
+{\prgex%
+(+ (* 3 " 4)                            ; note extra quote mark
+   (/ 8 2))
+}
+
+\noindent 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.)
+
+\pit 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 {\tt return} or {\tt enter} key
+without typing anything, most versions of Scheme won't print a new prompt.
+
+\esubhd{Boring Exercises}
+
+{\exercise
+Translate the arithmetic expressions $(3+4) \times 5$ and $3+(4 \times 5)$
+into Scheme expressions, and into plumbing diagrams.
+}
+
+\solution
+$(3+4) \times 5$ becomes {\tt (*~(+~3~4)~5)} and $3+(4 \times 5)$ becomes
+{\tt (+~3~(*~4~5))}.
+
+Here are the plumbing diagrams:
+
+\pspicture{1.5in}{Plumbing diagram}{ex3.1}{\TrimTop{0.5truein}}
+@
+
+{\exercise
+How many little people does Alonzo hire in evaluating each
+of the following expressions:
+ 
+{\prgex%
+(+ 3 (* 4 5) (- 10 4))
+ 
+(+ (* (- (/ 8 2) 1) 5) 2)
+ 
+(* (+ (- 3 (/ 4 2))
+      (sin (* 3 2))
+      (- 8 (sqrt 5)))
+   (- (/ 2 3)
+      4))
+}}
+
+\solution
+The number of little people is equal to the number of functions invoked,
+i.e., 3, 4, and 10 for the three examples.
+@
+
+{\exercise
+Each of the expressions in the previous exercise is compound.  How many
+subexpressions (not including subexpressions of subexpressions) does each
+one have?
+
+For example,
+
+{\prgex%
+(* (- 1 (+ 3 4)) 8)
+}
+
+\noindent has three subexpressions; you wouldn't count {\tt (+~3~4)}.
+}
+
+\solution
+4, 3, and 3.  Remember that the name of the function is one of the
+subexpressions!  So for the first expression the four
+subexpressions are:
+
+{\prgex%
++
+3
+(* 4 5)
+(- 10 4)
+}
+@
+
+ 
+{\exercise
+Five little people are hired in evaluating the following expression:
+ 
+{\prgex%
+(+ (* 3 (- 4 7))
+   (- 8 (- 3 5)))
+}
+ 
+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.  }
+
+\solution
+Working from inside out:
+
+{\parskip=0pt\parindent=0pt
+Marvin's specialty is {\tt -}, gets arguments {\tt 4} and {\tt 7}, returns
+{\tt -3} to Tenar.
+
+Tenar's specialty is {\tt *}, gets arguments {\tt 3} and {\tt -3}, returns
+{\tt -9} to Piemur.
+
+Malvina's specialty is {\tt -}, gets arguments {\tt 3} and {\tt 5}, returns
+{\tt -2} to Manfred.
+
+Manfred's specialty is {\tt -}, gets arguments {\tt 8} and {\tt -2}, returns
+{\tt 10} to Piemur.
+
+Piemur's specialty is {\tt +}, gets arguments {\tt -9} and {\tt 10}, returns
+{\tt 1} to Alonzo.
+
+}
+@
+
+{\exercise
+Evaluate each of the following expressions using the result replacement
+technique:
+
+{\prgex%
+(sqrt (+ 6 (* 5 2)))
+
+(+ (+ (+ 1 2) 3) 4)
+}
+}
+
+\solution
+{\prgex%
+(sqrt (+ 6 (* 5 2)))
+(sqrt (+ 6 10))
+(sqrt 16)
+4
+
+(+ (+ (+ 1 2) 3) 4)
+(+ (+ 3 3) 4)
+(+ 6 4)
+10
+}
+@
+
+{\exercise
+Draw a plumbing diagram for each of the following expressions:
+ 
+{\prgex%
+(+ 3 4 5 6 7)
+ 
+(+ (+ 3 4) (+ 5 6 7))
+ 
+(+ (+ 3 (+ 4 5) 6) 7)
+}}
+
+\solution
+\pspicture{1.5in}{Plumbing diagrams}{ex3.6}{\TrimTop{1.5truein}}
+@
+
+{\exercise
+What value is returned by {\tt (/ 1 3)} in your version of
+Scheme?  (Some Schemes return a decimal fraction like {\tt 0.33333}, while
+others have exact fractional values like {\tt 1/3} built in.)
+}
+
+{\exercise
+Which of the functions that you explored in Chapter \functions\ will
+accept variable numbers of arguments?
+}
+
+\solution
+All the following functions take an arbitrary number of arguments:
+{\tt *}, {\tt +}, {\tt <=}, {\tt <}, {\tt =}, {\tt >=}, {\tt >}, {\tt and},
+{\tt max}, {\tt min}, {\tt or}, {\tt sentence}, and {\tt word}.
+
+Also, {\tt -} and {\tt /} take variable numbers of arguments in some
+versions of Scheme.
+@
+
+\esubhd{Real Exercises}
+
+{\exercise
+The expression {\tt (+~8~2)} has the value {\tt 10}.  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:
+ 
+\medskip
+{\parindent=1em
+\bb An atom
+
+\bb Another compound expression made up of three atoms
+
+\bb A compound expression made up of four atoms
+
+\bb A compound expression made up of an atom and two compound subexpressions
+
+\bb Any other kind of expression
+
+}\medskip
+}
+
+\solution
+{\parindent=1em
+\bb {\tt 10} is the only possible answer.
+\bb {\tt (+ 4 6)}, or any appropriate two-argument function with atomic
+arguments.
+\bb {\tt (+ 2 3 5)}, or any appropriate three-argument function with atomic
+arguments.
+\bb {\tt (* (+ 1 1) (- 9 4))}, or any two-argument function whose arguments
+are provided by function calls.
+\bb {\tt (sqrt 100)}, or many more complicated possibilities.
+
+}
+@
+
+\bye