*

1 files changed, 573 insertions, 0 deletions

diff --git a/js/games/nluqo.github.io/~bh/ssch2/functions b/js/games/nluqo.github.io/~bh/ssch2/functions
new file mode 100644
index 0000000..19611ad
--- /dev/null
+++ b/js/games/nluqo.github.io/~bh/ssch2/functions
@@ -0,0 +1,573 @@
+\input bkmacs
+\photo{The function $f(x,y)=\sin xy$ plotted by
+computer}{\pagetag{\graph}\pspicture{4in}{plot}{plot3d}{\TrimBoundingBox{8pt}}}
+\chapter{Functions}
+\chaptag{\functions}
+
+Throughout most of this book we're going to be using a technique called {\it
+\bkidx{functional}{programming}.\/} We can't give a complete definition of
+this term yet, but in this chapter we introduce the building block of
+functional programming, the {\it \idx{function}.\/}
+
+Basically we mean by ``function'' the same thing that your high school
+algebra teacher meant, except that our functions don't necessarily relate to
+numbers.  But the essential idea is just like the kind of function described
+by $f(x)=6x-2$.  In that example, $f$ is the name of a function; that
+function takes an {\it argument\/} called $x$, which is a number, and {\it
+\idx{return}s\/} some other number.
+
+In this chapter you are going to use the computer to explore functions,
+but you are {\it not\/} going to use the standard Scheme notation as in the
+rest of the book.  That's because, in this chapter, we want to separate the
+idea of functions from the complexities of programming language notation.
+For example, real Scheme notation lets you write expressions that involve
+more than one function, but in this chapter you can only use one at a time.
+
+To get into this chapter's special computer interface, first start
+running Scheme as you did in the first chapter, then type
+
+{\prgex%
+(load "functions.scm")
+}
+
+\noindent to tell Scheme to read the program you'll be using.  (If you have
+trouble loading the program, look in Appendix A for further information
+about {\tt load}.)  Then, to start the program, type
+
+{\prgex%
+(functions)
+}
+
+\noindent You'll then be able to carry out interactions like the
+following.\footnt{If you get no response at all after you type
+{\tt (functions)}, just press the Return or Enter key
+again.  Tell your instructor to read
+Appendix A to see how to fix this.} In the text below we've
+printed what {\it you\/} type in {\tt \pmb{boldface}} and what the {\it
+computer\/} types in {\tt lightface} printing:
+
+{\prgex%
+Function: \pmb{+}
+Argument: \pmb{3}
+Argument: \pmb{5}
+
+The result is: 8
+
+Function: \pmb{sqrt}
+Argument: \pmb{144}
+
+The result is: 12
+}
+
+\noindent As you can see, different functions can have different numbers of
+arguments.  In these examples we added two numbers, and we took the square
+root of one number.  However, every function gives exactly one result each
+time we use it.
+
+To leave the {\tt functions} program, type {\tt exit} when it asks for a
+function.
+
+\subhd{Arithmetic}
+
+Experiment with these \bkidx{arithmetic}{function}s: {\tt
++}, {\tt -}, {\tt *}, {\tt
+/}, {\tt sqrt}, {\tt
+quotient}, {\tt
+remainder}, {\tt
+random}, {\tt round}, {\tt max}, and {\tt expt}.
+Try different kinds of numbers, including integers and numbers with decimal
+fractions.  What if you try to divide by zero?  Throughout this chapter we
+are going to let you experiment with functions rather than just give you a
+long, boring list of how each one works.  (The boring list is available for
+reference on page \funlist.)
+
+Try these:
+
+\vskip -5pt
+{\prgex%
+Function: /
+Argument: 1
+Argument: 987654321987654321
+
+Function: remainder 
+Argument: 12
+Argument: -5
+
+Function: round
+Argument: 17.5
+}
+
+\noindent These are just a few suggestions.  Be creative; don't just type in
+our examples.
+
+\backskipsubhd{Words}{5}
+
+Not all Scheme functions deal with numbers.  A broader category of
+argument is the {\it \idx{word},\/} including numbers but also
+including English words like {\tt spaghetti} or {\tt xylophone}.
+Even a meaningless sequence of letters and digits such as {\tt
+glo87rp} is considered a word.\footnt{Certain punctuation characters
+can also be used in words, but let's defer the details until you've
+gotten to know the word functions with simpler examples.} Try these
+functions that accept words as arguments: {\tt first}, {\tt
+butfirst}, {\tt last}, {\tt butlast}, {\tt word}, and {\tt count}.
+What happens if you use a number as the argument to one of these?
+
+{\prgex\blskip{3}%
+Function: butfirst
+Argument: a
+
+Function: count
+Argument: 765432
+}
+
+So far most of our functions fall into one of two categories:\ the
+arithmetic functions, which require numbers as arguments and return a number
+as the result; and the word functions, which accept words as
+arguments and return a word as the result.  The one exception we've seen is
+{\tt count}.  What kind of argument does {\tt count} accept?  What kind of
+value does it return?  The technical term for ``a kind of data'' is a
+{\it \idx{type}.}
+
+In principle you could think of almost anything as a type, such as ``numbers
+that contain the digit {\tt 7}.'' Such {\it ad hoc\/} types are legitimate
+and sometimes useful, but there are also official types that Scheme knows
+about.  Types can overlap; for example, numbers are also considered words.
+
+{\prgex\blskip{3}%
+Function: word
+Argument: 3.14
+Argument: 1592654
+
+Function: +
+Argument: 6
+Argument: seven
+}
+
+\subhd{Domain and Range}
+
+The technical term for ``the things that a function accepts as an argument''
+is the {\it \idx{domain}\/} of the function.  The name for ``the things that
+a function returns'' is its {\it \idx{range}.\/}  So the domain of {\tt
+count} is words, and the range of {\tt count} is numbers (in fact,
+nonnegative integers).  This example shows that the range may not be exactly
+one of our standard data types; there is no ``nonnegative integer'' type in
+Scheme.
+
+How do you talk about the domain and range of a function?  You could say, for
+example, ``The {\tt cos} function has numbers as its domain and numbers
+between $-1$ and 1 as its range.'' Or, informally, you may also say ``{\tt
+Cos} takes a number as its argument and returns a number between $-1$ and
+1.''\footnt{Unless your version of Scheme has complex numbers.}
+
+For functions of two or more arguments, the language is a little less
+straightforward.  The informal version still works: ``{\tt Remainder} takes
+two integers as arguments and returns an integer.'' But you can't say ``The
+domain of {\tt remainder} is two integers,'' because the domain of a
+function is the {\it set\/} of all possible arguments, not just a statement
+about the characteristics of legal arguments.\footnt{Real mathematicians
+say, ``The domain of {\tt remainder} is the Cartesian cross product of the
+integers and the integers.'' In order to avoid that mouthful, we'll just use
+the informal wording.}
+
+(By the way, we're making certain simplifications in this chapter.  For
+example, Scheme's {\tt +}~function can actually accept any number of
+arguments, not just two.  But we don't want to go into all the bells and
+whistles at once, so we'll start with adding two numbers at a time.)
+
+Here are examples that illustrate the domains of some functions:
+
+{\prgex%
+Function: expt
+Argument: -3
+Argument: .5
+
+Function: expt
+Argument: -3
+Argument: -3
+
+Function: remainder
+Argument: 5
+Argument: 0
+}
+
+\subhd{More Types:\ Sentences and Booleans}
+
+We're going to introduce more data types, and more functions that include
+those types in their domain or range.  The next type is the {\it
+\idx{sentence}:\/}\ a bunch of words enclosed in parentheses, such as
+
+{\prgex%
+(all you need is love)
+}
+
+\noindent (Don't include any punctuation characters within the sentence.)
+Many of the functions that accept words in their domain will also accept
+sentences.  There is also a function {\tt sentence} that accepts words and
+sentences.  Try examples like {\tt butfirst} of a sentence.
+
+{\prgex%
+Function: sentence
+Argument: (when i get)
+Argument: home
+
+Function: butfirst
+Argument: (yer blues)
+
+Function: butlast
+Argument: ()
+}
+
+Other important functions are used to ask yes-or-no questions.  That is, the
+range of these functions contains only two values, one meaning ``true'' and
+the other meaning ``false.'' Try the numeric comparisons {\tt
+=}, {\tt <}, {\tt
+>}, {\tt <=}, and {\tt
+>=}, and the functions {\tt
+equal?}\ and {\tt
+member?}\ that work on words and sentences.  (The
+question mark is part of the name of the function.)  There are also
+functions {\tt and}, {\tt or},
+and {\tt not} whose domain and range are both
+true-false values.  The two values ``true'' and ``false'' are called {\it
+\idx{Boolean}s,\/} named after \swapidx{George}{Boole} (1815--1864), who
+developed the formal tools used for true-false values in mathematics.
+
+What good are these true-false values?  Often a program must choose between
+two options:  If the number is positive, do this; if negative, do that.
+Scheme has functions to make such choices based on true-false values.  For
+now, you can experiment with the {\tt if} function.  Its first argument must
+be true or false; the others can be anything.
+
+\subhd{Our Favorite Type: Functions}
+
+So far our data types include numbers, words, sentences, and Booleans.
+\justidx{function as data}
+Scheme has several more data types, but for now we'll just consider one
+more.  A {\it function\/} can be used as data.  Here's an example:
+
+{\prgex%
+Function: number-of-arguments
+Argument: equal?
+
+The result is: 2
+}
+
+\noindent The range of {\tt number-of-arguments} is nonnegative integers.  But
+its domain is {\it functions.\/}  For example, try using it as an argument to
+itself!
+
+If you've used other computer programming languages, it may seem strange
+to use a function---that is, a part of a computer program---as data.
+Most languages make a sharp distinction between program and data.  We'll
+soon see that the ability to treat functions as data helps make Scheme
+programming very powerful and convenient.
+
+Try these examples:
+
+{\prgex%
+Function: every
+Argument: first
+Argument: (the long and winding road)
+
+Function: keep
+Argument: vowel?
+Argument: constantinople
+}
+
+\noindent Think carefully about these.  You aren't applying the function
+{\tt first} to the sentence {\tt (the long and winding road)}; you're applying
+the function {\tt every} to a function and a sentence.
+
+Other functions that can be used with {\tt keep} include {\tt even?} and
+{\tt odd?}, whose domains are the integers, and {\tt number?}, whose domain
+is everything.
+
+\subhd{Play with It}
+
+If you've been reading the book but not trying things out on the computer as
+you go along, get to work!  Spend some time getting used to these ideas and
+thinking about them.  When you're done, read ahead.
+
+\subhd{Thinking about What You've Done}
+
+The idea of {\it function\/} is at the heart of both mathematics and
+computer science.  For example, when mathematicians want to think very
+formally about the system of numbers, they use functions to create the
+integers.  They say, let's suppose we have one number, called zero; then
+let's suppose we have the {\it function\/} given by $f(x)=x+1$.  By applying
+that function repeatedly, we can create $1=f(0)$, then $2=f(1)$, and so on.
+
+Functions are important in computer science because they give us a way to
+think about {\it process\/}---in simple English, a way to think about
+something happening, something changing.  A function embodies a {\it
+transformation\/} of information, taking in something we know and returning
+something we didn't know.  That's what computers do:  They transform
+information to produce new results.
+
+A lot of the mathematics taught in school is about numbers, but
+we've seen that functions don't have to be about numbers.  We've
+used functions of words and sentences, such as {\tt first}, and even
+functions of functions, such as {\tt keep}.  You can imagine functions
+that transform information of any kind at all, such as the function
+\hbox{French(window)=fen\^etre} or the function
+\hbox{capital(California)=Sacramento}.
+
+You've done a lot of thinking about the {\it domain\/} and {\it range\/}
+of functions.  You can add two numbers, but it doesn't make sense to add
+two words that aren't numbers.  Some two-argument functions have complicated
+domains because the acceptable values for one argument depend on the
+specific value used for the other one.  (The function {\tt expt} is an
+example; make sure you've tried both positive and negative numbers, and
+fractional as well as whole-number powers.)
+
+Part of the definition of a function is that you always get the same answer
+whenever you call a function with the same argument(s).  The value returned
+by the function, in other words, shouldn't change regardless of anything
+else you may have computed meanwhile.  One of the ``functions'' you've
+explored in this chapter isn't a real function according to this rule; which
+one?  The rule may seem too restrictive, and indeed it's often convenient to
+use the name ``function'' loosely for processes that can give different
+results in different circumstances.  But we'll see that sometimes it's
+important to stick with the strict definition and refrain from using
+processes that aren't truly functions.
+
+We've hinted at two different ways of thinking about functions.  The first
+is called {\it \idx{function as process}.\/} Here, a function is a rule that
+tells us how to transform some information into some other information.  The
+function is just a rule, not a thing in its own right.  The actual
+``things'' are the words or numbers or whatever the function manipulates.
+The second way of thinking is called {\it \idx{function as object}.\/}  In
+this view, a function is a perfectly good ``thing'' in itself.  We can use a
+function as an argument to another function, for example.  Research with
+college math students shows that this second idea is hard for
+most people, but it's worth the effort because you'll see that {\it
+\bkidx{higher-order}{function}s\/} (functions of functions) like {\tt keep}
+and {\tt every} can make programs much easier to write.
+
+As a homey analogy, think about a carrot peeler.  If we focus our attention
+on the carrots---which are, after all, what we want to eat---then the peeler
+just represents a process.  We are peeling carrots.  We are applying the
+function {\tt peel} to carrots.  It's the carrot that counts.  But we can
+also think about the peeler as a thing in its own right, when we clean it,
+or worry about whether its blade is sharp enough.
+
+\looseness=-1
+The big idea that we {\it haven't\/} explored in this chapter (although we
+used it a lot in Chapter \showing) is the {\it composition\/} of functions:\
+using the result from one function as an argument to another function.  It's
+a crucial idea; we write large programs by defining a bunch of small
+functions and then composing them with each other to produce the desired
+result.  We'll start doing that in the next chapter, where we return to
+real Scheme notation.
+
+\esubhd{Exercises}
+
+{\it Use the\/} {\tt functions} {\it program for all these exercises.}
+
+{\exercise
+In each line of the following table we've left out one piece of
+information.  Fill in the missing details.
+
+\smallskip
+\def\tabRule{\noalign{\hrule}}
+\def\two#1{\omit\span #1\hfil}
+\noindent \hfil \vbox{\offinterlineskip
+\baselineskip=12pt
+\halign{\strut \vrule\enspace\hfil#\hfil & %function
+\enspace\vrule\enspace\hfil#\hfil &%arg1
+\enspace\vrule\enspace\hfil#\hfil &%arg2
+\enspace\vrule\enspace\hfil#\hfil\enspace\vrule \cr%result
+\tabRule
+function&arg 1&arg 2&result\cr
+\tabRule
+\tabRule
+{\tt word}&{\tt now}&{\tt here}&\cr
+\tabRule
+{\tt sentence}&{\tt now}&{\tt here}&\cr
+\tabRule
+{\tt first}&{\tt blackbird}&none&\cr
+\tabRule
+{\tt first}&{\tt (blackbird)}&none&\cr
+\tabRule
+&{\tt 3}&{\tt 4}&{\tt 7}\cr
+\tabRule
+{\tt every}&&{\tt (thank you girl)}&{\tt (hank ou irl)}\cr
+\tabRule
+{\tt member?}&{\tt e}&{\tt aardvark}&\cr
+\tabRule
+{\tt member?}&{\tt the}&&{\tt \#t}\cr
+\tabRule
+{\tt keep}&{\tt vowel?}&{\tt (i will)}&\cr
+\tabRule
+{\tt keep}&{\tt vowel?}&&{\tt eieio}\pgfoot\cr
+\tabRule
+{\tt last}&{\tt ()}&none&\cr
+\tabRule
+&{\tt last}&{\tt (honey pie)}&{\tt (y e)}\cr
+\tabRule
+&&{\tt taxman}&{\tt aa}\cr
+\tabRule
+}}\hfil}
+\vfootnt{Yes, there is an English
+word.  It has to do with astronomy.}
+
+\solution
+
+{\prgex%
+NOWHERE
+(NOW HERE)
+B
+BLACKBIRD
++
+BUTFIRST
+#F
+(ANY SENTENCE CONTAINING THE WORD THE)
+(I)
+PERIHELION
+{\rm{}Domain error}
+EVERY
+KEEP VOWEL?
+}
+
+Note that the parentheses matter!  For example, {\tt (I)} is different from
+{\tt I}.
+@
+
+\goodbreak
+{\exercise 
+What is the domain of the {\tt vowel?}\ function?
+}
+
+\solution
+The domain of {\tt vowel?} is anything.  (The domain is the set of arguments for
+which the function is defined---that is, it doesn't give an error---not
+the set of arguments for which it returns {\tt #t}.)
+@
+
+{\exercise
+One of the functions you can use is called {\tt appearances}.  Experiment
+with it, and then describe fully its domain and range, and what it does.
+(Make sure to try lots of cases.  Hint: Think about its name.)
+}
+
+\solution
+Domain: {\tt appearances} takes two arguments.  The second argument can be
+any word or sentence.  If the second argument is a sentence, then the first
+can be any word.  If the second argument is a word, then the first must be a
+one-letter word.
+
+Range: Nonnegative integers.
+
+{\tt Appearances} returns the number of times that the first argument appears
+as an element of the second (as a word in the sentence, or as a letter in
+the word).
+@
+
+{\exercise
+One of the functions you can use is called {\tt item}.  Experiment
+with it, and then describe fully its domain and range, and what it does.
+}
+
+\solution
+Domain: {\tt Item} takes two arguments.  The second can be any nonempty word
+or sentence.  The first must be a positive integer less than or equal to the
+number of elements in the second argument.
+
+Range:  Words.  (If the second argument is a
+sentence, then {\tt item} returns a word.  If the second argument
+is a word, then {\tt item} returns a one-letter word.)
+
+{\tt Item} returns an element of its second argument (a letter of the word,
+or a word of the sentence) chosen according to the numeric first argument.
+If the first argument is $n$, then {\tt item} returns the $n$th element of the
+second argument.
+@
+
+\vskip1cm
+
+The following exercises ask for functions that meet certain criteria.  For
+your convenience, here are the functions in this chapter:  {\tt
++}, {\tt -}, {\tt /}, {\tt <=}, {\tt <}, {\tt =}, {\tt >=}, {\tt >}, {\tt
+and}, {\tt appearances}, {\tt butfirst}, {\tt butlast}, {\tt cos}, {\tt
+count}, {\tt equal?}, {\tt every}, {\tt even?}, {\tt expt}, {\tt first},
+{\tt if}, {\tt item}, {\tt keep}, {\tt last}, {\tt max}, {\tt member?}, {\tt
+not}, {\tt number?}, {\tt number-of-arguments}, {\tt odd?}, {\tt or}, {\tt
+quotient}, {\tt random}, {\tt remainder}, {\tt round}, {\tt sentence}, {\tt
+sqrt}, {\tt vowel?}, and {\tt word}.
+
+{\exercise 
+List the one-argument functions in this chapter for which the type of the
+return value is always different from the type of the argument.
+}
+
+\solution
+The domain of {\tt number-of-arguments} is functions, while the range is
+numbers.  The domain of {\tt even?} and {\tt odd?} is numbers, while
+their range is Booleans.
+
+@
+
+{\exercise 
+List the one-argument functions in this chapter for which the type of the
+return value is sometimes different from the type of the argument.}
+
+\solution
+In addition to the above:
+
+{\parskip=0pt\parindent=0pt\obeylines
+{\tt first}: Domain includes sentences, range is words.
+{\tt last}:  (Ditto).
+{\tt count}:  Domain includes sentences, range is numbers.
+{\tt round}: Domain is all numbers, range is just integers.
+
+}
+
+Also, most of the type predicates, such as {\tt number?} and
+{\tt vowel?}, accept anything as argument, but return only
+Booleans.
+@
+
+{\exercise
+\extag{\exoperator}
+Mathematicians sometimes use the term ``operator'' to mean a function of two
+arguments, both of the same type, that returns a result of the same type.
+Which of the functions you've seen in this chapter satisfy that definition?
+}
+
+\solution
+The operators in this chapter are {\tt +}, {\tt -}, {\tt *}, {\tt /}, {\tt
+and}, {\tt expt}, {\tt max}, {\tt min}, {\tt or}, {\tt quotient}, {\tt
+remainder}, and {\tt word}.
+
+You could also conceivably count {\tt equal?}, {\tt item},
+and {\tt sentence}.  For these functions, only {\it some\/} of the
+possible arguments are in the range.
+@
+
+{\exercise
+An operator $f$ is {\it commutative\/} if
+$f(a,b)=f(b,a)$ for all possible arguments $a$ and $b$.  For example,
+{\tt +} is commutative, but {\tt word} isn't.  Which of the
+operators from Exercise \exoperator\ are commutative?
+}
+
+\solution
+The commutative operators are {\tt +}, {\tt *}, {\tt and}, {\tt max}, {\tt
+min}, and {\tt or}.  {\tt Equal?} is also commutative, if you
+count it as an operator.
+@
+
+{\exercise
+An operator $f$ is {\it associative\/} if
+$f(f(a,b),c)=f(a,f(b,c))$ for all possible arguments $a$, $b$, and $c$.
+For example, {\tt *} is associative, but not {\tt /}.
+Which of the operators from Exercise \exoperator\ are associative?
+}
+
+\solution
+The associative operators are {\tt +}, {\tt *}, {\tt and}, {\tt max}, {\tt
+min}, {\tt or}, {\tt sentence}, and {\tt word}.
+@
+
+\bye