diff options
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch8/higher')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch8/higher | 1108 |
1 files changed, 1108 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch8/higher b/js/games/nluqo.github.io/~bh/ssch8/higher new file mode 100644 index 0000000..b2f5fd8 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch8/higher @@ -0,0 +1,1108 @@ +<P> + +<P><A NAME="plowshares"></A> +<CENTER><IMG SRC="../ss-pics/plowshare.jpg" ALT="figure: plowshare"></CENTER><P><CENTER>Turning function machines into plowshares +</CENTER><P> + +<HTML> +<HEAD> +<TITLE>Simply Scheme: Introducing Computer Science ch 8: Higher-Order Functions</TITLE> +</HEAD> +<BODY> +<HR> +<CITE>Simply Scheme:</CITE> +<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT +<H2>Chapter 8</H2> +<H1>Higher-Order 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/ssch08.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="part3.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch9/lambda.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><EM>Note: If you read Part IV before this one, pretend you didn't; we are +going to develop a different technique for solving similar problems.</EM> + +<P> +You can use the function <CODE>first</CODE> to find the first letter +of a word. What if you want to find the first letters of several words? You +did this in the first chapter, as part of the process of finding acronyms. + +<P> +To start with a simple case, suppose you have two words (that is, a sentence +of length two). You could apply the <CODE>first</CODE> procedure to each of them and +combine the results: + +<PRE>(define (<A NAME="g1"></A>two-firsts sent) + (se (first (first sent)) + (first (last sent)))) + +> (two-firsts '(john lennon)) +(J L) + +> (two-firsts '(george harrison)) +(G H) +</PRE> + +Similarly, here's the version for three words: + +<PRE>(define (<A NAME="g2"></A>three-firsts sent) + (se (first (first sent)) + (first (first (bf sent))) + (first (last sent)))) + +> (three-firsts '(james paul mccartney)) +(J P M) +</PRE> + +But this approach would get tiresome if you had a sentence of five +words—you'd have to write a procedure specifically for the case of exactly +five words, and that procedure would have five separate subexpressions to +extract the first word, the second word, and so on. Also, you don't +want a separate procedure for every sentence length; you want one function +that works no matter how long the sentence is. Using the tools you've +already learned about, the only possible way to do that would be pretty +hideous: + + + +<P><PRE>(define (first-letters sent) + (cond ((= (count sent) 1) (one-first sent)) + ((= (count sent) 2) (two-firsts sent)) + ((= (count sent) 3) (three-firsts sent)) + … and so on …)) +</PRE> + +<P> + +<P>But even this won't work because there's no way to say +"and so on" in Scheme. You could write a version that works for all +sentences up to, let's say, length 23, but you'd be in trouble if someone +tried to use your procedure on a 24-word sentence. + +<P><H2><CODE><B>Every</B></CODE></H2> +<A NAME="every"></A> +<A NAME="g3"></A> + +To write a better any-length first-letter procedure, you need to be able to say +"apply the function <CODE>first</CODE> to <EM>every</EM> word in the sentence, no +matter how long the sentence is." Scheme provides a way to do +this:<A NAME="text1" HREF="higher#ft1">[1]</A> + +<PRE>(define (<A NAME="g4"></A>first-letters sent) + (every first sent)) + +> (first-letters '(here comes the sun)) +(H C T S) + +> (first-letters '(lucy in the sky with diamonds)) +(L I T S W D) +</PRE> + +<CODE>Every</CODE> takes two arguments. The second argument is a sentence, but the +first is something new: a <EM>procedure</EM> used as an +<A NAME="g5"></A> +<A NAME="g6"></A> +<A NAME="g7"></A> +<A NAME="g8"></A> +argument to another procedure.<A NAME="text2" HREF="higher#ft2">[2]</A> Notice that there are no parentheses around the word <CODE>first</CODE> +in the body of <CODE>first-letters</CODE>! By now you've gotten accustomed to +seeing parentheses whenever you see the name of a function. But parentheses +indicate an <EM>invocation</EM> of a function, and we aren't invoking <CODE>first</CODE> here. We're using <CODE>first</CODE>, the procedure itself, as an argument +to <CODE>every</CODE>. + +<P><PRE>> (every last '(while my guitar gently weeps)) +(E Y R Y S) + +> (every - '(4 5 7 8 9)) +(-4 -5 -7 -8 -9) +</PRE> + +These examples use <CODE>every</CODE> with primitive procedures, but of +course you can also define procedures of your own and apply them to <CODE>every</CODE> +word of a sentence: + +<PRE>(define (<A NAME="g9"></A>plural noun) + (if (equal? (last noun) 'y) + (word (bl noun) 'ies) + (word noun 's))) + +> (every plural '(beatle turtle holly kink zombie)) +(BEATLES TURTLES HOLLIES KINKS ZOMBIES) +</PRE> + +<P>You can also use a word as the second argument to <CODE>every</CODE>. In this case, +the first-argument procedure is applied to every letter of the word. The +results are collected in a sentence. + +<P><PRE>(define (<A NAME="g10"></A>double letter) (word letter letter)) + +> (every double 'girl) +(GG II RR LL) + +> (every square 547) +(25 16 49) +</PRE> + +<P>In all these examples so far, the first argument to <CODE>every</CODE> was a +function that returned a <EM>word,</EM> and the value returned by <CODE>every</CODE> +was a sentence containing all the returned words. +The first argument to <CODE>every</CODE> can also be a function that returns a +<EM>sentence.</EM> In this case, <CODE>every</CODE> returns one long sentence: + +<P><PRE>(define (<A NAME="g11"></A>sent-of-first-two wd) + (se (first wd) (first (bf wd)))) + +> (every sent-of-first-two '(the inner light)) +(T H I N L I) + +> (every sent-of-first-two '(tell me what you see)) +(T E M E W H Y O S E) + +> (define (g wd) + (se (word 'with wd) 'you)) + +> (every g '(in out)) +(WITHIN YOU WITHOUT YOU) +</PRE> + +<P>A function that takes another function as one of its arguments, as +<CODE>every</CODE> does, is called a <EM><A NAME="g12"></A><A NAME="g13"></A>higher-order function.</EM> +If we focus our attention on procedures, the mechanism through which +Scheme computes functions, we think of <CODE>every</CODE> as a procedure +that takes another procedure as an argument—a <EM>higher-order +procedure.</EM> + +<P><H2>A Pause for Reflection</H2> + +<P>Earlier we used the metaphor of the "<A NAME="g14"></A><A NAME="g15"></A>function machine," with a +hopper at the top into which we throw data, and a chute at the +bottom from which the result falls, like a meat grinder. Well, +<CODE>every</CODE> is a function machine into whose hopper we throw <EM>another +function machine!</EM> Instead of a meat grinder, we have a metal +grinder.<A NAME="text3" HREF="higher#ft3">[3]</A> + +<P>Do you see what an exciting idea this is? We are accustomed to +thinking of numbers and sentences as "real things," while functions +are less like things and more like activities. As an analogy, think +about cooking. The real foods are the meats, vegetables, ice cream, +and so on. You can't eat a recipe, which is analogous to a +function. A recipe has to be applied to ingredients, and the result +of carrying out the recipe is an edible meal. It would seem weird +if a recipe used other recipes as ingredients: “Preheat the oven +to 350 and insert your <EM>Joy of Cooking.</EM>” But in Scheme we +can do just that.<A NAME="text4" HREF="higher#ft4">[4]</A> + +<P>Cooking your cookbook is unusual, but the general principle isn't. +In some contexts we do treat recipes as things rather than as +algorithms. For example, people write recipes on cards and put them +into a recipe file box. Then they perform operations such as searching +for a particular recipe, sorting the recipes by category (main dish, +dessert, etc.), copying a recipe for a friend, and so on. The same +recipe is both a process (when we're cooking with it) and the object +of a process (when we're filing it). + +<P><H2><CODE><B>Keep</B></CODE></H2> + +<P>Once we have this idea, we can use functions of functions to provide many +different capabilities. +<A NAME="keep"></A> + +<P> +For instance, the <A NAME="g16"></A><CODE>keep</CODE> function takes a predicate and a sentence as +arguments. It returns a sentence containing only the words of the argument +sentence for which the predicate is true. + +<PRE>> (keep even? '(1 2 3 4 5)) +(2 4) + +> (define (<A NAME="g17"></A>ends-e? word) (equal? (last word) 'e)) + +> (keep ends-e? '(please put the salami above the blue elephant)) +(PLEASE THE ABOVE THE BLUE) + +> (keep number? '(1 after 909)) +(1 909) +</PRE> + +<P><CODE>Keep</CODE> will also accept a word as its second argument. In this case, it +applies the predicate to every letter of the word and returns another word: + +<P><PRE>> (keep number? 'zonk23hey9) +239 + +> (define (<A NAME="g18"></A>vowel? letter) (member? letter '(a e i o u))) + +> (keep vowel? 'piggies) +IIE +</PRE> + +<P>When we used <CODE>every</CODE> to select the first letters of words +earlier, we found the first letters even of uninteresting words such +as "the." We're working toward an acronym procedure, and for that +purpose we'd like to be able to discard the boring words. + +<PRE>(define (<A NAME="g19"></A>real-word? wd) + (not (member? wd '(a the an in of and for to with)))) + +> (keep real-word? '(lucy in the sky with diamonds)) +(LUCY SKY DIAMONDS) + +> (every first (keep real-word? '(lucy in the sky with diamonds))) +(L S D) +</PRE> + +<P><H2><CODE><B>Accumulate</B></CODE></H2> +<A NAME="accum"></A> + +<P>In <CODE>every</CODE> and <CODE>keep</CODE>, each element of the second argument +contributes <EM>independently</EM> to the overall result. That is, <CODE>every</CODE> and <CODE>keep</CODE> apply a procedure to a single element at a time. The +overall result is a collection of individual results, with no interaction +between elements of the argument. This doesn't let us say things like "Add +up all the numbers in a sentence," where the desired output is a function +of the entire argument sentence taken as a whole. We can do this with a +procedure named <A NAME="g20"></A><CODE>accumulate</CODE>. <CODE>Accumulate</CODE> takes a procedure and +a sentence as its arguments. It applies that procedure to two of the words +of the sentence. Then it applies the procedure +to the result we got back and another element of the sentence, and so on. +It ends when it's combined all the words of the sentence into a single result. + +<P><PRE>> (accumulate + '(6 3 4 -5 7 8 9)) +32 + +> (accumulate word '(a c l u)) +ACLU + +> (accumulate max '(128 32 134 136)) +136 + +> (define (<A NAME="g21"></A>hyphenate word1 word2) + (word word1 '- word2)) + +> (accumulate hyphenate '(ob la di ob la da)) +OB-LA-DI-OB-LA-DA +</PRE> + +<P>(In all of our examples in this section, the second argument +contains at least two elements. In the "pitfalls" section at the end of +the chapter, we'll discuss what happens with smaller arguments.) + +<P><CODE>Accumulate</CODE> can also take a word as its second argument, using the +letters as elements: + +<P><PRE>> (accumulate + 781) +16 + +> (accumulate sentence 'colin) +(C O L I N) +</PRE> + +<P> +<H2>Combining Higher-Order Functions</H2> + +What if we want to add up all the numbers in a sentence but ignore the words +that aren't numbers? First we <CODE>keep</CODE> the numbers in the sentence, then +we <CODE>accumulate</CODE> the result with <CODE>+</CODE>. It's easier to say in Scheme: + +<PRE>(define (<A NAME="g22"></A>add-numbers sent) + (accumulate + (keep number? sent))) + +> (add-numbers '(4 calling birds 3 french hens 2 turtle doves)) +9 + +> (add-numbers '(1 for the money 2 for the show 3 to get ready + and 4 to go)) +10 +</PRE> + +<P>We also have enough tools to write a version of the <A NAME="g23"></A><CODE>count</CODE> procedure, +which finds the number of words in a sentence or the number of letters in a +word. First, we'll define a procedure <CODE>always-one</CODE> that returns 1 no +matter what its argument is. We'll <CODE>every always-one</CODE> over our argument +sentence,<A NAME="text5" HREF="higher#ft5">[5]</A> which will result in a sentence of as +many ones as there were words in the original sentence. Then we can use +<CODE>accumulate</CODE> with <CODE>+</CODE> to add up the ones. This is a slightly +roundabout approach; later we'll see a more natural way to find the <CODE>count</CODE> of a sentence. + +<PRE>(define (<A NAME="g24"></A>always-one arg) + 1) + +(define (<A NAME="g25"></A>count sent) + (accumulate + (every always-one sent))) + +> (count '(the continuing story of bungalow bill)) +6 +</PRE> + +You can now understand the <CODE>acronym</CODE> procedure from Chapter 1: + +<PRE>(define (<A NAME="g26"></A>acronym phrase) + (accumulate word (every first (keep real-word? phrase)))) + +> (acronym '(reduced instruction set computer)) +RISC + +> (acronym '(structure and interpretation of computer programs)) +SICP +</PRE> + +<A name="whichHOF"> +<P><H2>Choosing the Right Tool</H2> + +<P>So far you've seen three higher-order functions: <A NAME="g27"></A><CODE>every</CODE>, +<A NAME="g28"></A><CODE>keep</CODE>, and <A NAME="g29"></A><CODE>accumulate</CODE>. How do you decide which one to +use for a particular problem? + +<P><CODE>Every</CODE> transforms each element of a word or sentence individually. The +result sentence usually contains as many elements as the +argument.<A NAME="text6" HREF="higher#ft6">[6]</A> + +<P><CENTER><IMG SRC="../ss-pics/every.jpg" ALT="figure: every"></CENTER> + +<P><CODE>Keep</CODE> selects certain elements of a word or sentence and discards the +others. The elements of the result are elements of the argument, without +transformation, but the result may be smaller than the original. + +<P><CENTER><IMG SRC="../ss-pics/keep.jpg" ALT="figure: keep"></CENTER> + +<P><CODE>Accumulate</CODE> transforms the entire word or sentence into a single result +by combining all of the elements in some way. + +<P><CENTER><IMG SRC="../ss-pics/accumulate.jpg" ALT="figure: accumulate"></CENTER> + +<P>These three pictures represent graphically the differences in the meanings +of <CODE>every</CODE>, <CODE>keep</CODE>, and <CODE>accumulate</CODE>. In the pictures, we're +applying these higher-order procedures to sentences, but don't forget that +we could have drawn similar pictures in which the higher-order procedures +process the letters of a word. + +<P>Here's another way to compare these three higher-order functions: + +<P><P> +<TABLE><THEAD><STRONG><TR><TH>function<TH>purpose<TH>first +argument is a …</STRONG> +<TBODY> +<TR><TD><CODE>every</CODE><TD>transform <TD>one-argument +<EM>transforming</EM> function +<TR><TD><CODE>keep</CODE><TD>select<TD>one-argument <EM>predicate</EM> +function +<TR><TD><CODE>accumulate</CODE> <TD>combine<TD>two-argument +<EM>combining</EM> function +</TABLE> + + +<P><P> +To help you understand these differences, we'll look at specific examples +using each of them, with each example followed by an equivalent computation +done without the higher-order procedure. Here is an example for <CODE>every</CODE>: + +<P><PRE>> (every double 'girl) +(GG II RR LL) + +> (se (double 'g) + (double 'i) + (double 'r) + (double 'l)) +(GG II RR LL) +</PRE> + +<P> + +<P>You can, if you like, think of the first of these expressions +as abbreviating the second. + +<P> + +<P>An expression using <CODE>keep</CODE> can also be replaced with an expression that +performs the same computation without using <CODE>keep</CODE>. This time it's a +little messier: + +<P> + +<P><PRE>> (keep even? '(1 2 3 4 5)) +(2 4) + +> (se (if (even? 1) 1 '()) + (if (even? 2) 2 '()) + (if (even? 3) 3 '()) + (if (even? 4) 4 '()) + (if (even? 5) 5 '())) +(2 4) +</PRE> + +<P> +Here's how an <CODE>accumulate</CODE> can be expressed the long way: + +<P><PRE>> (accumulate word '(a c l u)) +ACLU + +> (word 'a (word 'c (word 'l 'u))) +ACLU +</PRE> + +<P>(Of course <CODE>word</CODE> will accept any number of arguments, so we +could have computed the same result with all four letters as arguments to +the same invocation. But the version we've shown here indicates how +<CODE>accumulate</CODE> actually works; it combines the elements one by one.) + +<P><H2>First-Class Functions and First-Class Sentences</H2> + +<P>If Scheme (or any dialect of Lisp) is your first programming language, +having procedures that operate on entire sentences at once may not seem like +a big deal. But if you used to program in some lesser language, you're +probably accustomed to writing something like <CODE>first-letters</CODE> as a <EM>loop</EM> in which you have some variable named <CODE>I</CODE> and you carry out some +sequence of steps for <CODE>I=1</CODE>, <CODE>I=2</CODE>, and so on, until you get to <CODE>N</CODE>, the number of elements. The use of higher-order functions allows us to +express this problem all at once, rather than as a sequence of events. Once +you're accustomed to the Lisp way of thinking, you can tell yourself "just +take <CODE>every first</CODE> of the sentence," and that feels like a single step, +not a complicated task. + +<P>Two aspects of Scheme combine to permit this mode of expression. One, +which we've mentioned earlier, is that sentences are first-class data. +You can use an entire sentence as an argument to a procedure. You can type a +quoted sentence in, or you can compute a sentence by putting words together. + +<P>The second point is that functions are also first-class. This lets us write +a procedure like <CODE>pigl</CODE> that applies to a single word, and then +combine that with <CODE>every</CODE> to translate an entire sentence to Pig Latin. +If Scheme didn't have first-class functions, we couldn't have general-purpose +tools like <CODE>keep</CODE> and <CODE>every</CODE>, because we couldn't say which +function to extend to all of a sentence. You'll see later that without <CODE>every</CODE> it would still be possible to write a specific <CODE>pigl-sent</CODE> +procedure and separately write a <CODE>first-letters</CODE> procedure. But the +ability to use a procedure as argument to another procedure lets us <EM>generalize</EM> the idea of "apply this function to every word of the +sentence." + +<P><H2><CODE><B>Repeated</B></CODE></H2> + +<P>All the higher-order functions you've seen so far take functions as +arguments, but none of them have functions as return values. That is, +we have machines that can take machines in their input hoppers, but now +we'd like to think about machines that drop <EM>other machines</EM> out of +their output chutes—machine factories, so to speak. +<A NAME="repeated"></A> + +<P>In the following example, the procedure <A NAME="g30"></A><CODE>repeated</CODE> returns a procedure: + +<PRE>> ((repeated bf 3) '(she came in through the bathroom window)) +(THROUGH THE BATHROOM WINDOW) + +> ((repeated plural 4) 'computer) +COMPUTERSSSS + +> ((repeated square 2) 3) +81 + +> (define (<A NAME="g31"></A>double sent) + (se sent sent)) + +> ((repeated double 3) '(banana)) +(BANANA BANANA BANANA BANANA BANANA BANANA BANANA BANANA) +</PRE> + +The procedure <CODE>repeated</CODE> takes two arguments, a procedure and a number, +and returns a new procedure. The returned procedure is one that invokes the +original procedure repeatedly. For example, <CODE>(repeated bf 3)</CODE> +returns a function that takes the butfirst of the butfirst of the +butfirst of its argument. + +Notice that all our examples start with two open parentheses. If we just +invoked <CODE>repeated</CODE> at the Scheme prompt, we would get back a procedure, +like this: + +<PRE>> (repeated square 4) +#<PROCEDURE> +</PRE> + +The procedure that we get back isn't very interesting by itself, so +we invoke it, like this: + +<PRE>> ((repeated square 4) 2) +65536 +</PRE> + +To understand this expression, you must think carefully about its +two subexpressions. Two subexpressions? Because there are two open +parentheses next to each other, it would be easy to ignore one of them and +therefore think of the expression as having four atomic subexpressions. But +in fact it has only two. The first subexpression, <CODE>(repeated square 4)</CODE>, has a procedure as its value. The second +subexpression, <CODE>2</CODE>, has a number as its value. The value of the entire +expression comes from applying the procedure to the number. + +All along we've been saying that you evaluate a compound expression in two +steps: First, you evaluate all the subexpressions. Then you apply the +first value, which has to be a procedure, to the rest of the values. But +until now the first subexpression has always been just a single word, the +name of a procedure. Now we see that the first expression might be an +invocation of a higher-order function, just as any of the argument +subexpressions might be function invocations. + +We can use <CODE>repeated</CODE> to define <A NAME="g32"></A><CODE>item</CODE>, which returns a particular +element of a sentence: + +<PRE>(define (<A NAME="g33"></A>item n sent) + (first ((repeated bf (- n 1)) sent))) + +> (item 1 '(a day in the life)) +A + +> (item 4 '(a day in the life)) +THE +</PRE> + +<P><H2>Pitfalls</H2> + +<P>Some people seem to fall in love with <CODE>every</CODE> and try to use it in +all problems, even when <CODE>keep</CODE> or <CODE>accumulate</CODE> would be more +appropriate. + +<P>If you find yourself using a predicate function as the first argument to +<CODE>every</CODE>, you almost certainly mean to use <CODE>keep</CODE> instead. For +example, we want to write a procedure that determines whether any of the +words in its argument sentence are numbers: + +<P><PRE>(define (any-numbers? sent) ;; wrong! + (accumulate or (every number? sent))) +</PRE> + +<P>This is wrong for two reasons. First, since Boolean values aren't words, +they can't be members of sentences: + +<P><PRE>> (sentence #T #F) +ERROR: ARGUMENT TO SENTENCE NOT A WORD OR SENTENCE: #F + +> (every number? '(a b 2 c 6)) +ERROR: ARGUMENT TO SENTENCE NOT A WORD OR SENTENCE: #T +</PRE> + +<P>Second, even if you could have a sentence of Booleans, Scheme doesn't allow +a special form, such as <CODE>or</CODE>, as the argument to a higher-order +function.<A NAME="text7" HREF="higher#ft7">[7]</A> Depending on your version of Scheme, +the incorrect <CODE>any-numbers?</CODE> procedure might give an error message about +either of these two problems. + +<P>Instead of using <CODE>every</CODE>, select the numbers from the argument and count +them: + +<P><PRE>(define (<A NAME="g34"></A>any-numbers? sent) + (not (empty? (keep number? sent)))) +</PRE> + +<P>The <CODE>keep</CODE> function always returns a result of the same type (i.e., +word or sentence) as its second argument. This makes sense because if you're +selecting a subset of the words of a sentence, you want to end up with a +sentence; but if you're selecting a subset of the letters of a word, you +want a word. <CODE>Every</CODE>, on the other hand, always returns a sentence. +You might think that it would make more sense for <CODE>every</CODE> to return a +word when its second argument is a word. Sometimes that <EM>is</EM> what you +want, but sometimes not. For example: + +<P><A NAME="spelldigit"></A> +<PRE>(define (<A NAME="g35"></A>spell-digit digit) + (item (+ 1 digit) + '(zero one two three four five six seven eight nine))) + +> (every spell-digit 1971) +(ONE NINE SEVEN ONE) +</PRE> + +<P>In the cases where you do want a word, you can just <CODE>accumulate word</CODE> the sentence that <CODE>every</CODE> returns. + +<P> +<P>Remember that <CODE>every</CODE> expects its first argument to be a function of +just one argument. If you invoke <CODE>every</CODE> with a function such as <CODE>quotient</CODE>, which expects two arguments, you will get an error message from +<CODE>quotient</CODE>, complaining that it only got one argument and wanted to get +two. + +<P>Some people try to get around this by saying things like + +<P><PRE>(every (quotient 6) '(1 2 3)) ;; wrong! +</PRE> + +<P>This is a sort of wishful thinking. The intent is that Scheme +should interpret the first argument to <CODE>every</CODE> as a fill-in-the-blank +template, so that <CODE>every</CODE> will compute the values of + +<P><PRE>(quotient 6 1) +(quotient 6 2) +(quotient 6 3) +</PRE> + +<P>But of course what Scheme really does is the same thing it always +does: It evaluates the argument expressions, then invokes <CODE>every</CODE>. So +Scheme will try to compute <CODE>(quotient 6)</CODE> and will give an error message. + +<P>We picked <CODE>quotient</CODE> for this example because it requires exactly two +arguments. Many Scheme primitives that ordinarily take two arguments, +however, will accept only one. Attempting the same wishful thinking with +one of these procedures is still wrong, but the error message is different. +For example, suppose you try to add 3 to each of several numbers this way: + +<P><PRE>(every (+ 3) '(1 2 3)) ;; wrong! +</PRE> + +<P>The first argument to <CODE>every</CODE> in this case isn't "the +procedure that adds 3," but the result returned by invoking <CODE>+</CODE> with +the single argument <CODE>3</CODE>. <CODE>(+ 3)</CODE> returns the number <CODE>3</CODE>, which +isn't a procedure. So you will get an error message like "Attempt to apply +non-procedure 3." + +<P>The idea behind this mistake—looking for a way to "specialize" a +two-argument procedure by supplying one of the arguments in advance—is +actually a good one. In the next chapter we'll introduce a new mechanism +that does allow such specialization. + +<P>If the procedure you use as the argument to <CODE>every</CODE> returns an empty +sentence, then you may be surprised by the results: + +<P><PRE>(define (<A NAME="g36"></A>beatle-number n) + (if (or (< n 1) (> n 4)) + '() + (item n '(john paul george ringo)))) + +> (beatle-number 3) +GEORGE + +> (beatle-number 5) +() + +> (every beatle-number '(2 8 4 0 1)) +(PAUL RINGO JOHN) +</PRE> + +<P>What happened to the <CODE>8</CODE> and the <CODE>0</CODE>? Pretend that <CODE>every</CODE> didn't exist, and you had to do it the hard way: + +<P><PRE>(se (beatle-number 2) (beatle-number 8) (beatle-number 4) + (beatle-number 0) (beatle-number 1)) +</PRE> + +<P>Using result replacement, we would get + +<P><PRE>(se 'paul '() 'ringo '() 'john) +</PRE> + +<P>which is just <CODE>(PAUL RINGO JOHN)</CODE>. + +<P>On the other hand, if <CODE>every</CODE>'s argument procedure returns an empty <EM>word,</EM> it will appear in the result. + +<P><PRE>> (every bf '(i need you)) +("" EED OU) +</PRE> + +<P>The sentence returned by <CODE>every</CODE> has three words in it: the +empty word, <CODE>eed</CODE>, and <CODE>ou</CODE>. + +<P>Don't confuse + +<P><PRE>(first '(one two three four)) +</PRE> + +<P>with + +<P><PRE>(every first '(one two three four)) +</PRE> + +<P>In the first case, we're applying the procedure <CODE>first</CODE> to a +sentence; in the second, we're applying <CODE>first</CODE> four separate times, +to each of the four words separately. + +<P>What happens if you use a one-word sentence or one-letter word as argument +to <CODE>accumulate</CODE>? It returns that word or that letter, without even +invoking the given procedure. This makes sense if you're using something +like <CODE>+</CODE> or <CODE>max</CODE> as the accumulator, but it's disconcerting that + +<P><PRE>(accumulate se '(one-word)) +</PRE> + +<P>returns the <EM>word</EM> <CODE>one-word</CODE>. + +<P> +What happens if you give <CODE>accumulate</CODE> an empty sentence or word? +<CODE>Accumulate</CODE> accepts empty arguments for some combiners, but not for +others: + +<P><PRE>> (accumulate + '()) +0 + +> (accumulate max '()) +ERROR: CAN'T ACCUMULATE EMPTY INPUT WITH THAT COMBINER +</PRE> + +<P>The combiners that can be used with an empty sentence or word are +<CODE>+</CODE>, <CODE>*</CODE>, <CODE>word</CODE>, and <CODE>sentence</CODE>. <CODE>Accumulate</CODE> checks +specifically for one of these combiners. + +<P>Why should these four procedures, and no others, be allowed to <CODE>accumulate</CODE> an empty sentence or word? The difference between these and +other combiners is that you can invoke them with no arguments, whereas <CODE>max</CODE>, for example, requires at least one number: + +<P><PRE>> (+) +0 + +> (max) +ERROR: NOT ENOUGH ARGUMENTS TO #<PROCEDURE>. +</PRE> + +<P><CODE>Accumulate</CODE> actually invokes the combiner with no arguments +in order to find out what value to return for an empty sentence or word. +We would have liked to implement <CODE>accumulate</CODE> so that <EM>any</EM> +procedure that can be invoked with no arguments would be accepted as a +combiner to accumulate the empty sentence or word. Unfortunately, Scheme +does not provide a way for a program to ask, "How many arguments will this +procedure accept?" The best we could do was to build a particular set of +zero-argument-okay combiners into the definition of <CODE>accumulate</CODE>. + +<P>Don't think that the returned value for an empty argument is always zero or +empty. + +<P><PRE>> (accumulate * '()) +1 +</PRE> + +<P>The explanation for this behavior is that any function that works +with no arguments returns its <EM>identity element</EM> in that case. +What's an identity element? The function <CODE>+</CODE> has the identity element +<CODE>0</CODE> because <CODE>(+</CODE> <EM>anything</EM> <CODE>0)</CODE> returns the <EM>anything.</EM> Similarly, the empty word is the identity element for <CODE>word</CODE>. In general, a function's identity element has the property that when +you invoke the function with the identity element and something else as +arguments, the return value is the something else. It's a Scheme convention +that a procedure with an identity element returns that element when invoked +with no arguments.<A NAME="text8" HREF="higher#ft8">[8]</A> + +<P>The use of two consecutive open parentheses to invoke the procedure +<A NAME="g37"></A> +returned by a procedure is a strange-looking notation: + +<P><PRE>((repeated bf 3) 987654) +</PRE> + +<P>Don't confuse this with the similar-looking <CODE>cond</CODE> notation, +in which the outer parentheses have a special meaning (delimiting a <CODE>cond</CODE> clause). Here, the parentheses have their usual meaning. The inner +parentheses invoke the procedure <CODE>repeated</CODE> with arguments <CODE>bf</CODE> and +<CODE>3</CODE>. The value of that expression is a procedure. It doesn't have a +name, but for the purposes of this paragraph let's pretend it's called <CODE>bfthree</CODE>. Then the outer parentheses are basically saying <CODE>(bfthree 987654)</CODE>; they apply the unnamed procedure to the argument <CODE>987654</CODE>. + +<P>In other words, there are two sets of parentheses because there are two +functions being invoked: <CODE>repeated</CODE> and the function returned by +<CODE>repeated</CODE>. So don't say + +<P><PRE>(repeated bf 3 987654) ;; wrong +</PRE> + +<P>just because it looks more familiar. <CODE>Repeated</CODE> isn't a +function of three arguments. + +<P><H2>Boring Exercises</H2> + +<P><B>8.1</B> What does Scheme return as the value of each of the following expressions? +Figure it out for yourself before you try it on the computer. + +<P><PRE> +> (every last '(algebra purple spaghetti tomato gnu)) + +> (keep number? '(one two three four)) + +> (accumulate * '(6 7 13 0 9 42 17)) + +> (member? 'h (keep vowel? '(t h r o a t))) + +> (every square (keep even? '(87 4 7 12 0 5))) + +> (accumulate word (keep vowel? (every first '(and i love her)))) + +> ((repeated square 0) 25) + +> (every (repeated bl 2) '(good day sunshine)) +</PRE> + +<P><B>8.2</B> Fill in the blanks in the following Scheme interactions: + +<P><PRE>> (______ vowel? 'birthday) +IA + +> (______ first '(golden slumbers)) +(G S) + +> (______ '(golden slumbers)) +GOLDEN + +> (______ ______ '(little child)) +(E D) + +> (______ ______ (______ ______ '(little child))) +ED + +> (______ + '(2 3 4 5)) +(2 3 4 5) + +> (______ + '(2 3 4 5)) +14 +</PRE> + +<P> +<B>8.3</B> Describe each of the following functions in English. Make sure to include a +description of the domain and range of each function. Be as precise as +possible; for example, "the argument must be a function of one numeric +argument" is better than "the argument must be a function." + +<P><PRE>(define (f a) + (keep even? a)) + +(define (g b) + (every b '(blue jay way))) + +</PRE> + +<P> +<PRE>(define (h c d) + (c (c d))) + +(define (i e) + (/ (accumulate + e) (count e))) + +accumulate + +sqrt + +repeated + +(repeated sqrt 3) + +(repeated even? 2) + +(repeated first 2) + +(repeated (repeated bf 3) 2) +</PRE> + +<P> +<P> +<H2>Real Exercises</H2> +<P> +Note: Writing helper procedures may be useful in solving some of these +problems. <EM>If you read Part IV before this, do not use recursion +in solving these problems; use higher order functions instead.</EM> + +<a name="hofex"> + +<P><B>8.4</B> Write a procedure <CODE><A NAME="g38"></A>choose-beatles</CODE> that takes a predicate +function as its argument and returns a sentence of just those Beatles (John, +Paul, George, and Ringo) that satisfy the predicate. For example: + +<P><PRE>(define (<A NAME="g39"></A>ends-vowel? wd) (vowel? (last wd))) + +(define (<A NAME="g40"></A>even-count? wd) (even? (count wd))) + +> (choose-beatles ends-vowel?) +(GEORGE RINGO) + +> (choose-beatles even-count?) +(JOHN PAUL GEORGE) +</PRE> + +<P> + + +<P><B>8.5</B> Write a procedure <CODE><A NAME="g41"></A>transform-beatles</CODE> that takes a procedure as an +argument, applies it to each of the Beatles, and returns the results in a +sentence: + +<P><PRE>(define (<A NAME="g42"></A>amazify name) + (word 'the-amazing- name)) +</PRE> + +<P> + +<P><PRE>> (transform-beatles amazify) +(THE-AMAZING-JOHN THE-AMAZING-PAUL THE-AMAZING-GEORGE + THE-AMAZING-RINGO) + +> (transform-beatles butfirst) +(OHN AUL EORGE INGO) +</PRE> + +<P> + +<B>8.6</B> When you're talking to someone over a noisy radio connection, you sometimes +have to spell out a word in order to get the other person to understand it. +But names of letters aren't that easy to understand either, so there's a +standard code in which each letter is represented by a particular word that +starts with the letter. For example, instead of "B" you say "bravo." + +<P>Write a procedure <CODE><A NAME="g43"></A>words</CODE> that takes a word as its argument and +returns a sentence of the names of the letters in the word: + +<P><PRE>> (words 'cab) +(CHARLIE ALPHA BRAVO) +</PRE> + +<P>(You may make up your own names for the letters or look up the +standard ones if you want.) + +<P>Hint: Start by writing a helper procedure that figures out the name for a +single letter. + + +<P> +<B>8.7</B> [<A HREF="../ssch14/recur-patterns.html#lettcrec">14.5</A>]<A NAME="text9" HREF="higher#ft9">[9]</A> +Write a procedure <CODE><A NAME="g44"></A>letter-count</CODE> that takes a sentence as its +argument and returns the total number of letters in the sentence: +<A NAME="lettcount"></A> + +<P><PRE>> (letter-count '(fixing a hole)) +11 +</PRE> + +<P> +<B>8.8</B> [<A HREF="../ssch12/leap.html#exaggrec">12.5</A>] +Write an <CODE><A NAME="g45"></A>exaggerate</CODE> procedure which exaggerates sentences: +<A NAME="exagg"></A> + +<P><PRE>> (exaggerate '(i ate 3 potstickers)) +(I ATE 6 POTSTICKERS) + +> (exaggerate '(the chow fun is good here)) +(THE CHOW FUN IS GREAT HERE) +</PRE> + +<P>It should double all the numbers in the sentence, and it should replace +"good" with "great," "bad" with "terrible," and anything else you +can think of. + +<P> +<B>8.9</B> What procedure can you use as the first argument to <CODE>every</CODE> so that for +any sentence used as the second argument, <CODE>every</CODE> returns that sentence? + +<P>What procedure can you use as the first argument to <CODE>keep</CODE> so that for +any sentence used as the second argument, <CODE>keep</CODE> returns that sentence? + +<P>What procedure can you use as the first argument to <CODE>accumulate</CODE> so that +for any sentence used as the second argument, <CODE>accumulate</CODE> returns that +sentence? + + +<P> +<B>8.10</B> Write a predicate <CODE><A NAME="g46"></A>true-for-all?</CODE> that takes two arguments, a +predicate procedure and a sentence. It should return <CODE>#t</CODE> if the +predicate argument returns true for <EM>every</EM> word in the sentence. +<A NAME="trueforall"></A> + +<P><PRE>> (true-for-all? even? '(2 4 6 8)) +#T + +> (true-for-all? even? '(2 6 3 4)) +#F +</PRE> + +<P> +<B>8.11</B> [<A HREF="../ssch12/leap.html#gparec">12.6</A>] +Write a GPA procedure. It should take a sentence of grades as its argument +and return the corresponding grade point average: +<A NAME="gpa"></A> + +<P><PRE>> (<A NAME="g47"></A>gpa '(A A+ B+ B)) +3.67 +</PRE> + +<P>Hint: write a helper procedure <CODE><A NAME="g48"></A>base-grade</CODE> that takes +a grade as argument and returns 0, 1, 2, 3, or 4, and another helper +procedure <CODE>grade-modifier</CODE> that returns −.33, 0, or .33, depending on +whether the grade has a minus, a plus, or neither. + + +<P> +<B>8.12</B> [<A HREF="../ssch11/recursion.html#countumsrec">11.2</A>] +When you teach a class, people will get distracted if you say "um" too many +times. Write a <CODE><A NAME="g49"></A>count-ums</CODE> that counts the number of times "um" +appears in a sentence: +<A NAME="countums"></A> + +<P><PRE>> (count-ums + '(today um we are going to um talk about functional um programming)) +3 +</PRE> + +<P> +<B>8.13</B> [<A HREF="../ssch11/recursion.html#unspellrec">11.3</A>] +Write a procedure <CODE><A NAME="g50"></A>phone-unspell</CODE> that takes a spelled version of +a phone number, such as <CODE>POPCORN</CODE>, and returns the real phone number, in +this case <CODE>7672676</CODE>. You will need to write a helper procedure that +uses an 8-way <CODE>cond</CODE> expression to translate a single letter into a +digit. +<A NAME="unspell"></A> + + +<P> +<B>8.14</B> Write the procedure <CODE><A NAME="g51"></A>subword</CODE> that takes three arguments: a +word, a starting position number, and an ending position number. It should +return the subword containing only the letters between the specified +positions: + +<P><PRE>> (subword 'polythene 5 8) +THEN +</PRE> + +<P> + +<HR> +<A NAME="ft1" HREF="higher#text1">[1]</A> Like all the procedures in this book that deal with words and +sentences, <CODE>every</CODE> and the other procedures in this chapter +are part of our extensions to Scheme. Later, in Chapter 17, we'll +introduce the standard Scheme equivalents.<P> +<A NAME="ft2" HREF="higher#text2">[2]</A> Talking about <CODE>every</CODE> strains our +resolve to distinguish functions from the procedures that implement them. +Is the argument to <CODE>every</CODE> a function or a procedure? If we think of +<CODE>every</CODE> itself as a procedure—that is, if we're focusing on how it +does its job—then of course we must say that it does its job by repeatedly +invoking the <EM>procedure</EM> that we supply as an argument. But it's +equally valid for us to focus attention on the function that the <CODE>every</CODE> +procedure implements, and that function takes <EM>functions</EM> as +arguments.<P> +<A NAME="ft3" HREF="higher#text3">[3]</A> You can get in trouble mathematically by trying to define a +function whose domain includes <EM>all</EM> functions, because applying such +a function to itself can lead to a paradox. In programming, the +corresponding danger is that applying a higher-order procedure to <EM>itself</EM> might result in a program that runs forever.<P> +<A NAME="ft4" HREF="higher#text4">[4]</A> Some recipes may seem to include other +recipes, because they say things like "add pesto (recipe on p. +12)." But this is just composition of functions; the <EM>result</EM> +of the pesto procedure is used as an argument to this recipe. The +pesto recipe itself is not an ingredient.<P> +<A NAME="ft5" HREF="higher#text5">[5]</A> We mean, of course, "We'll invoke <CODE>every</CODE> with the +procedure <CODE>always-one</CODE> and our argument sentence as its two arguments." +After you've been programming computers for a while, this sort of abuse of +English will come naturally to you.<P> +<A NAME="ft6" HREF="higher#text6">[6]</A> What we mean by "usually" is that <CODE>every</CODE> is most +often used with an argument function that returns a single word. If the +function returns a sentence whose length might not be one, then the number +of words in the overall result could be anything!<P> +<A NAME="ft7" HREF="higher#text7">[7]</A> As we said in Chapter 4, special forms aren't +procedures, and aren't first-class.<P> +<A NAME="ft8" HREF="higher#text8">[8]</A> PC Scheme returns zero for an invocation of <CODE>max</CODE> with no arguments, but that's the wrong answer. If anything, the +answer would have to be −∞.<P> +<A NAME="ft9" HREF="higher#text9">[9]</A> Exercise <A HREF="../ssch14/recur-patterns.html#lettcrec">14.5</A> in Part IV asks you to solve this +same problem using recursion. Here we are asking you to use +higher-order functions. Whenever we pose the same problem in both parts, we'll +cross-reference them in brackets as we did here. When you see the problem +for the second time, you might want to consult your first solution for ideas.<P> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="part3.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch9/lambda.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |