diff options
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch2/functions.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch2/functions.html | 459 |
1 files changed, 459 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch2/functions.html b/js/games/nluqo.github.io/~bh/ssch2/functions.html new file mode 100644 index 0000000..dd62b25 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch2/functions.html @@ -0,0 +1,459 @@ +<P> + +<P><A NAME="graph"></A><CENTER><IMG SRC="../ss-pics/plot3d.jpg" ALT="figure: plot3d"></CENTER><P><CENTER>The function <EM>f</EM>(<EM>x,y</EM>)=sin <EM>xy</EM> plotted by +computer +</CENTER><P> + +<HTML> +<HEAD> +<TITLE>Simply Scheme: Introducing Computer Science ch 2: Functions</TITLE> +</HEAD> +<BODY> +<HR> +<CITE>Simply Scheme:</CITE> +<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT +<H2>Chapter 2</H2> +<H1>Functions</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/ssch02.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="../ssch1/showing.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch3/part2.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>Throughout most of this book we're going to be using a technique called <EM><A NAME="g1"></A><A NAME="g2"></A>functional programming.</EM> We can't give a complete definition of +this term yet, but in this chapter we introduce the building block of +functional programming, the <EM>function.</EM> + +<P>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 <EM>f</EM>(<EM>x</EM>)=6<EM>x</EM>−2. In that example, <EM>f</EM> is the name of a function; that +function takes an <EM>argument</EM> called <EM>x</EM>, which is a number, and <EM>returns</EM> some other number. + +<P>In this chapter you are going to use the computer to explore functions, +but you are <EM>not</EM> 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. + +<P>To get into this chapter's special computer interface, first start +running Scheme as you did in the first chapter, then type + +<P><PRE>(load "functions.scm") +</PRE> + +<P>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 <CODE>load</CODE>.) Then, to start the program, type + +<P><PRE>(functions) +</PRE> + +<P>You'll then be able to carry out interactions like the +following.<A NAME="text1" HREF="functions.html#ft1">[1]</A> In the text below we've +printed what <EM>you</EM> type in <CODE><B>boldface</B></CODE> and what the <EM>computer</EM> types in <CODE>lightface</CODE> printing: + +<P><PRE>Function: <B>+</B> +Argument: <B>3</B> +Argument: <B>5</B> + +The result is: 8 + +Function: <B>sqrt</B> +Argument: <B>144</B> + +The result is: 12 +</PRE> + +<P>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. + +<P>To leave the <CODE>functions</CODE> program, type <CODE>exit</CODE> when it asks for a +function. + +<P><H2>Arithmetic</H2> + +<P>Experiment with these <A NAME="g3"></A><A NAME="g4"></A>arithmetic functions: <CODE>+</CODE>, <CODE>-</CODE>, <CODE>*</CODE>, <CODE>/</CODE>, <CODE>sqrt</CODE>, <CODE>quotient</CODE>, <CODE>remainder</CODE>, <CODE>random</CODE>, <CODE>round</CODE>, <CODE>max</CODE>, and <CODE>expt</CODE>. +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 <A HREF="../ssch27/appendix-funlist.html#funlist">funlist</A>.) + +<P>Try these: + +<P> +<PRE>Function: / +Argument: 1 +Argument: 987654321987654321 + +Function: remainder +Argument: 12 +Argument: -5 + +Function: round +Argument: 17.5 +</PRE> + +<P>These are just a few suggestions. Be creative; don't just type in +our examples. + +<P><H2>Words</H2> + +<P>Not all Scheme functions deal with numbers. A broader category of +argument is the <EM>word,</EM> including numbers but also +including English words like <CODE>spaghetti</CODE> or <CODE>xylophone</CODE>. +Even a meaningless sequence of letters and digits such as <CODE>glo87rp</CODE> is considered a word.<A NAME="text2" HREF="functions.html#ft2">[2]</A> Try these +functions that accept words as arguments: <CODE>first</CODE>, <CODE>butfirst</CODE>, <CODE>last</CODE>, <CODE>butlast</CODE>, <CODE>word</CODE>, and <CODE>count</CODE>. +What happens if you use a number as the argument to one of these? + +<P><PRE>Function: butfirst +Argument: a + +Function: count +Argument: 765432 +</PRE> + +<P>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 +<CODE>count</CODE>. What kind of argument does <CODE>count</CODE> accept? What kind of +value does it return? The technical term for "a kind of data" is a +<EM>type.</EM> + +<P>In principle you could think of almost anything as a type, such as "numbers +that contain the digit <CODE>7</CODE>." Such <EM>ad hoc</EM> 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. + +<P><PRE>Function: word +Argument: 3.14 +Argument: 1592654 + +Function: + +Argument: 6 +Argument: seven +</PRE> + +<P><H2>Domain and Range</H2> + +<P>The technical term for "the things that a function accepts as an argument" +is the <EM>domain</EM> of the function. The name for "the things that +a function returns" is its <EM>range.</EM> So the domain of <CODE>count</CODE> is words, and the range of <CODE>count</CODE> 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. + +<P>How do you talk about the domain and range of a function? You could say, for +example, "The <CODE>cos</CODE> function has numbers as its domain and numbers +between −1 and 1 as its range." Or, informally, you may also say "<CODE>Cos</CODE> takes a number as its argument and returns a number between −1 and +1."<A NAME="text3" HREF="functions.html#ft3">[3]</A> + +<P>For functions of two or more arguments, the language is a little less +straightforward. The informal version still works: "<CODE>Remainder</CODE> takes +two integers as arguments and returns an integer." But you can't say "The +domain of <CODE>remainder</CODE> is two integers," because the domain of a +function is the <EM>set</EM> of all possible arguments, not just a statement +about the characteristics of legal arguments.<A NAME="text4" HREF="functions.html#ft4">[4]</A> + +<P>(By the way, we're making certain simplifications in this chapter. For +example, Scheme's <CODE>+</CODE> 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.) + +<P>Here are examples that illustrate the domains of some functions: + +<P><PRE>Function: expt +Argument: -3 +Argument: .5 + +Function: expt +Argument: -3 +Argument: -3 + +Function: remainder +Argument: 5 +Argument: 0 +</PRE> + +<P><H2>More Types: Sentences and Booleans</H2> + +<P>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 <EM>sentence:</EM> a bunch of words enclosed in parentheses, such as + +<P><PRE>(all you need is love) +</PRE> + +<P>(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 <CODE>sentence</CODE> that accepts words and +sentences. Try examples like <CODE>butfirst</CODE> of a sentence. + +<P><PRE>Function: sentence +Argument: (when i get) +Argument: home + +Function: butfirst +Argument: (yer blues) + +Function: butlast +Argument: () +</PRE> + +<P>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 <CODE>=</CODE>, <CODE><</CODE>, <CODE>></CODE>, <CODE><=</CODE>, and <CODE>>=</CODE>, and the functions <CODE>equal?</CODE> and <CODE>member?</CODE> that work on words and sentences. (The +question mark is part of the name of the function.) There are also +functions <CODE>and</CODE>, <CODE>or</CODE>, +and <CODE>not</CODE> whose domain and range are both +true-false values. The two values "true" and "false" are called <EM>Booleans,</EM> named after <A NAME="g5"></A>George Boole (1815-1864), who +developed the formal tools used for true-false values in mathematics. + +<P>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 <CODE>if</CODE> function. Its first argument must +be true or false; the others can be anything. + +<P><H2>Our Favorite Type: Functions</H2> + +<P>So far our data types include numbers, words, sentences, and Booleans. +<A NAME="g6"></A> +Scheme has several more data types, but for now we'll just consider one +more. A <EM>function</EM> can be used as data. Here's an example: + +<P><PRE>Function: number-of-arguments +Argument: equal? + +The result is: 2 +</PRE> + +<P>The range of <CODE>number-of-arguments</CODE> is nonnegative integers. But +its domain is <EM>functions.</EM> For example, try using it as an argument to +itself! + +<P>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. + +<P>Try these examples: + +<P><PRE>Function: every +Argument: first +Argument: (the long and winding road) + +Function: keep +Argument: vowel? +Argument: constantinople +</PRE> + +<P>Think carefully about these. You aren't applying the function +<CODE>first</CODE> to the sentence <CODE>(the long and winding road)</CODE>; you're applying +the function <CODE>every</CODE> to a function and a sentence. + +<P>Other functions that can be used with <CODE>keep</CODE> include <CODE>even?</CODE> and +<CODE>odd?</CODE>, whose domains are the integers, and <CODE>number?</CODE>, whose domain +is everything. + +<P><H2>Play with It</H2> + +<P>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. + +<P><H2>Thinking about What You've Done</H2> + +<P>The idea of <EM>function</EM> 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 <EM>function</EM> given by <EM>f</EM>(<EM>x</EM>)=<EM>x</EM>+1. By applying +that function repeatedly, we can create 1=<EM>f</EM>(0), then 2=<EM>f</EM>(1), and so on. + +<P>Functions are important in computer science because they give us a way to +think about <EM>process</EM>—in simple English, a way to think about +something happening, something changing. A function embodies a <EM>transformation</EM> 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. + +<P>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 <CODE>first</CODE>, and even +functions of functions, such as <CODE>keep</CODE>. You can imagine functions +that transform information of any kind at all, such as the function +French(window)=fenêtre or the function +capital(California)=Sacramento. + +<P>You've done a lot of thinking about the <EM>domain</EM> and <EM>range</EM> +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 <CODE>expt</CODE> is an +example; make sure you've tried both positive and negative numbers, and +fractional as well as whole-number powers.) + +<P>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. + +<P>We've hinted at two different ways of thinking about functions. The first +is called <EM>function as process.</EM> 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 <EM>function as object.</EM> 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 <EM><A NAME="g7"></A><A NAME="g8"></A>higher-order functions</EM> (functions of functions) like <CODE>keep</CODE> +and <CODE>every</CODE> can make programs much easier to write. + +<P>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 <CODE>peel</CODE> 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. + +<P>The big idea that we <EM>haven't</EM> explored in this chapter (although we +used it a lot in Chapter 1) is the <EM>composition</EM> 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. + +<P><H2>Exercises</H2> + +<P><EM>Use the</EM> <CODE>functions</CODE> <EM>program for all these exercises.</EM> + +<P><B>2.1</B> In each line of the following table we've left out +one piece of information. Fill in the missing details. + +<P><P> + +<TABLE FRAME=BOX RULES=ALL> +<TR><TH>function<TH>arg 1<TH>arg 2<TH>result +<TR><TD><CODE> word</CODE><TD><CODE> now</CODE><TD><CODE> here</CODE> +<TR><TD><CODE> sentence </CODE><TD><CODE> now</CODE><TD><CODE> here</CODE> +<TR><TD><CODE> first</CODE><TD><CODE> blackbird</CODE><TD><CODE> </CODE>none +<TR><TD><CODE> first</CODE><TD><CODE> (blackbird) </CODE><TD><CODE> </CODE>none +<TR><TD><TD><CODE> 3</CODE><TD><CODE> 4</CODE><TD><CODE> 7</CODE> +<TR><TD><CODE> every</CODE><TD><TD><CODE> (thank you girl) </CODE><TD><CODE> (hank ou irl) </CODE> +<TR><TD><CODE> member?</CODE><TD><CODE> e</CODE><TD><CODE> aardvark</CODE> +<TR><TD><CODE> member?</CODE><TD><CODE> the</CODE><TD><TD><CODE> #t</CODE> +<TR><TD><CODE> keep</CODE><TD><CODE> vowel?</CODE><TD><CODE> (i will)</CODE> +<TR><TD><CODE> keep</CODE><TD><CODE> vowel?</CODE><TD><TD><CODE> eieio</CODE><A NAME="text5" HREF="functions.html#ft5">[5]</A> +<TR><TD><CODE> last</CODE><TD><CODE> ()</CODE><TD><CODE> </CODE>none<TD> +<TR><TD><TD><CODE> last</CODE><TD><CODE> (honey pie)</CODE><TD><CODE> (y e)</CODE> +<TR><TD><TD><TD><CODE> taxman</CODE><TD><CODE> aa</CODE> +</TABLE> + +<P> +<B>2.2</B> +What is the domain of the <CODE>vowel?</CODE> function? + + +<P> +<B>2.3</B> One of the functions you can use is called <CODE>appearances</CODE>. 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.) + + +<P> +<B>2.4</B> One of the functions you can use is called <CODE>item</CODE>. Experiment +with it, and then describe fully its domain and range, and what it does. + + +<P> + +The following exercises ask for functions that meet certain criteria. For +your convenience, here are the functions in this chapter: <CODE>+</CODE>, <CODE>-</CODE>, <CODE>/</CODE>, <CODE><=</CODE>, <CODE><</CODE>, <CODE>=</CODE>, <CODE>>=</CODE>, <CODE>></CODE>, <CODE>and</CODE>, <CODE>appearances</CODE>, <CODE>butfirst</CODE>, <CODE>butlast</CODE>, <CODE>cos</CODE>, <CODE>count</CODE>, <CODE>equal?</CODE>, <CODE>every</CODE>, <CODE>even?</CODE>, <CODE>expt</CODE>, <CODE>first</CODE>, +<CODE>if</CODE>, <CODE>item</CODE>, <CODE>keep</CODE>, <CODE>last</CODE>, <CODE>max</CODE>, <CODE>member?</CODE>, <CODE>not</CODE>, <CODE>number?</CODE>, <CODE>number-of-arguments</CODE>, <CODE>odd?</CODE>, <CODE>or</CODE>, <CODE>quotient</CODE>, <CODE>random</CODE>, <CODE>remainder</CODE>, <CODE>round</CODE>, <CODE>sentence</CODE>, <CODE>sqrt</CODE>, <CODE>vowel?</CODE>, and <CODE>word</CODE>. + +<P><B>2.5</B> +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. + + +<P> +<B>2.6</B> +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. + +<P> +<B>2.7</B> <A NAME="exoperator"></A> +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? + + +<P> +<B>2.8</B> An operator <EM>f</EM> is <EM>commutative</EM> if +<EM>f</EM>(<EM>a,b</EM>)=<EM>f</EM>(<EM>b,a</EM>) for all possible arguments <EM>A</EM> and <EM>B</EM>. For example, +<CODE>+</CODE> is commutative, but <CODE>word</CODE> isn't. Which of the +operators from Exercise 2.7 are commutative? + + +<P> +<B>2.9</B> An operator <EM>f</EM> is <EM>associative</EM> if +<EM>f</EM>(<EM>f</EM>(<EM>a,b</EM>)<EM>,c</EM>)=<EM>f</EM>(<EM>a,f</EM>(<EM>f</EM>(<EM>b,c</EM>)) for all possible arguments <EM>A</EM>, <EM>B</EM>, and <EM>C</EM>. +For example, <CODE>*</CODE> is associative, but not <CODE>/</CODE>. +Which of the operators from Exercise 2.7 are associative? + + +<P> + +<HR> +<A NAME="ft1" HREF="functions.html#text1">[1]</A> If you get no response at all after you type +<CODE>(functions)</CODE>, just press the Return or Enter key +again. Tell your instructor to read +Appendix A to see how to fix this.<P> +<A NAME="ft2" HREF="functions.html#text2">[2]</A> 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.<P> +<A NAME="ft3" HREF="functions.html#text3">[3]</A> Unless your version of Scheme has complex numbers.<P> +<A NAME="ft4" HREF="functions.html#text4">[4]</A> Real mathematicians +say, "The domain of <CODE>remainder</CODE> is the Cartesian cross product of the +integers and the integers." In order to avoid that mouthful, we'll just use +the informal wording.<P> +<A NAME="ft5" HREF="functions.html#text5">[5]</A> Yes, there is an English +word. It has to do with astronomy.<P> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="../ssch1/showing.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch3/part2.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |