path: root/js/games/nluqo.github.io/~bh/ssch2/functions

\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