<P> <A NAME="polly"></A> <P><P><CENTER><IMG SRC="../ss-pics/polly.jpg" ALT="figure: polly"></CENTER> <HTML> <HEAD> <TITLE>Simply Scheme: Introducing Computer Science ch 19: Implementing Higher-Order Functions</TITLE> </HEAD> <BODY> <HR> <CITE>Simply Scheme:</CITE> <CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT <H2>Chapter 19</H2> <H1>Implementing 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/ssch19.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="../ssch18/trees.html"><STRONG>BACK</STRONG></A> chapter thread <A HREF="../ssch20/part6.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>This chapter is about writing <EM><A NAME="g1"></A>higher-order procedures—</EM>that is, procedures that implement <A NAME="g2"></A><A NAME="g3"></A>higher-order functions. We are going to study the implementation of <CODE>every</CODE>, <CODE>keep</CODE>, and so on. <P>Really there are no new techniques involved. You know how to write recursive procedures that follow the <CODE>every</CODE> pattern, the <CODE>keep</CODE> pattern, and so on; it's a small additional step to generalize those <A NAME="g4"></A> patterns. The truly important point made in this chapter is that you aren't limited to a fixed set of higher-order functions. If you feel a need for a new one, you can implement it. <P><H2>Generalizing Patterns</H2> <P>In Chapter 14, we showed you the procedures <CODE>square-sent</CODE> and <CODE>pigl-sent</CODE>, which follow the <CODE>every</CODE> pattern of recursion. In order to write the general tool, <CODE>every</CODE> itself, we have to <EM>generalize the pattern</EM> that those two have in common. <P>Before we get to writing higher-order procedures, let's look at a simpler case of generalizing patterns. <P>Suppose we want to find out the areas of several different kinds of shapes, given one linear dimension. A straightforward way would be to do it like this: <P><PRE>(define pi 3.141592654) (define (<A NAME="g5"></A>square-area r) (* r r)) (define (<A NAME="g6"></A>circle-area r) (* pi r r)) (define (<A NAME="g7"></A>sphere-area r) (* 4 pi r r)) (define (<A NAME="g8"></A>hexagon-area r) (* (sqrt 3) 1.5 r r)) > (square-area 6) 36 > (circle-area 5) 78.53981635 </PRE> <P>This works fine, but it's somewhat tedious to define all four of these procedures, given that they're so similar. Each one returns the square of its argument times some constant factor; the only difference is the constant factor. <P>We want to generalize the pattern that these four procedures exhibit. Each of these procedures has a particular constant factor built in to its definition. What we'd like instead is one single procedure that lets you choose a constant factor when you invoke it. This new procedure will take a second argument besides the linear dimension <CODE>r</CODE> (the radius or side): a <CODE>shape</CODE> argument whose value is the desired constant factor. <P><PRE>(define (<A NAME="g9"></A>area shape r) (* shape r r)) (define square 1) (define circle pi) (define sphere (* 4 pi)) (define hexagon (* (sqrt 3) 1.5)) > (area sphere 7) 615.752160184 </PRE> <P>What's the point? We started with several procedures. Then we found that they had certain points of similarity and certain differences. In order to write a single procedure that generalizes the points of similarity, we had to use an additional argument for each point of difference. (In this example, there was only one point of difference.) <P>In fact, <EM>every</EM> procedure with arguments is a generalization in the same way. Even <CODE>square-area</CODE>, which we presented as the special case to be generalized, is more general than these procedures: <P><PRE>(define (area-of-square-of-side-5) (* 5 5)) (define (area-of-square-of-side-6) (* 6 6)) </PRE> <P>These may seem too trivial to be taken seriously. Indeed, nobody would write such procedures. But it's possible to take the area of a particular size square without using a procedure at all, and then later discover that you need to deal with squares of several sizes. <P>This idea of using a procedure to generalize a pattern is part of the larger idea of abstraction that we've been discussing throughout the book. We notice an algorithm that we need to use repeatedly, and so we separate the algorithm from any particular data values and give it a name. <P>The idea of generalization may seem obvious in the example about areas of squares. But when we apply the same idea to generalizing over a function, rather than merely generalizing over a number, we gain the enormous expressive power of higher-order functions. <P><H2>The <CODE><B>Every</B></CODE> Pattern Revisited</H2> <P>Here again is the <CODE>every</CODE> template: <P><PRE>(define (<B>every-something</B> sent) (if (empty? sent) '() (se (______ (first sent)) (<B>every-something</B> (bf sent))))) </PRE> <P>You've been writing <CODE>every</CODE>-like procedures by filling in the blank with a specific function. To generalize the pattern, we'll use the trick of adding an argument, as we discussed in the last section. <P><PRE>(define (<A NAME="g10"></A>every fn sent) (if (empty? sent) '() (se (fn (first sent)) (every fn (bf sent))))) </PRE> <P>This is hardly any work at all for something that seemed as mysterious as <CODE>every</CODE> probably did when you first saw it. <P>Recall that <CODE>every</CODE> will also work if you pass it a word as its second argument. The version shown here does indeed work for words, because <CODE>first</CODE> and <CODE>butfirst</CODE> work for words. So probably "<CODE>stuff</CODE>" would be a better formal parameter than "<CODE>sent</CODE>." (The result from <CODE>every</CODE> is always a sentence, because <CODE>sentence</CODE> is used to construct the result.) <P> <P><H2>The Difference between <CODE><B>Map</B></CODE> and <CODE><B>Every</B></CODE></H2> <P>Here's the definition of the <CODE>map</CODE> procedure: <P><PRE>(define (<A NAME="g11"></A>map fn lst) (if (null? lst) '() (cons (fn (car lst)) (map fn (cdr lst))))) </PRE> <P>The structure here is identical to that of <CODE>every</CODE>; the only difference is that we use <CODE>cons</CODE>, <CODE>car</CODE>, and <CODE>cdr</CODE> instead of <CODE>se</CODE>, <CODE>first</CODE>, and <CODE>butfirst</CODE>. <P>One implication of this is that you can't use <CODE>map</CODE> with a word, since it's an error to take the <CODE>car</CODE> of a word. When is it advantageous to use <CODE>map</CODE> instead of <CODE>every</CODE>? Suppose you're using <CODE>map</CODE> with a structured list, like this: <P><PRE>> (map (lambda (flavor) (se flavor '(is great))) '(ginger (ultra chocolate) pumpkin (rum raisin))) ((GINGER IS GREAT) (ULTRA CHOCOLATE IS GREAT) (PUMPKIN IS GREAT) (RUM RAISIN IS GREAT)) </PRE> <P><PRE>> (every (lambda (flavor) (se flavor '(is great))) '(ginger (ultra chocolate) pumpkin (rum raisin))) (GINGER IS GREAT ULTRA CHOCOLATE IS GREAT PUMPKIN IS GREAT RUM RAISIN IS GREAT) </PRE> <P>Why does <CODE>map</CODE> preserve the structure of the sublists while <CODE>every</CODE> doesn't? <CODE>Map</CODE> uses <CODE>cons</CODE> to combine the elements of the result, whereas <CODE>every</CODE> uses <CODE>sentence</CODE>: <P><PRE>> (cons '(pumpkin is great) (cons '(rum raisin is great) '())) ((PUMPKIN IS GREAT) (RUM RAISIN IS GREAT)) > (se '(pumpkin is great) (se '(rum raisin is great) '())) (PUMPKIN IS GREAT RUM RAISIN IS GREAT) </PRE> <P><H2><CODE><B>Filter</B></CODE></H2> <P>Here's the implementation of <A NAME="g12"></A><CODE>filter</CODE>: <P><PRE>(define (<A NAME="g13"></A>filter pred lst) (cond ((null? lst) '()) ((pred (car lst)) (cons (car lst) (filter pred (cdr lst)))) (else (filter pred (cdr lst))))) </PRE> <P>Like <CODE>map</CODE>, this uses <CODE>cons</CODE> as the constructor so that it will work properly on structured lists. We're leaving the definition of <CODE>keep</CODE>, the version for words and sentences, as an exercise. <P>(Aside from the difference between lists and sentences, this is just like the <CODE>keep</CODE> template on page <A HREF="../ssch14/recur-patterns.html#keeptemplate">there</A>.) <P><H2><CODE><B>Accumulate</B></CODE> and <CODE><B>Reduce</B></CODE></H2> <P>Here are the examples of the <A NAME="g14"></A><CODE>accumulate</CODE> pattern that we showed you before: <P><PRE>(define (addup nums) (if (empty? nums) 0 (+ (first nums) (addup (bf nums))))) (define (scrunch-words sent) (if (empty? sent) "" (word (first sent) (scrunch-words (bf sent))))) </PRE> <P>What are the similarities and differences? There are <EM>two</EM> important differences between these procedures: the combiners (<CODE>+</CODE> versus <CODE>word</CODE>) and the values returned in the base cases (zero versus the empty word). According to what we said about generalizing patterns, you might expect that we'd need two extra arguments. You'd invoke <CODE>three-arg-accumulate</CODE> like this: <P><PRE>> (three-arg-accumulate + 0 '(6 7 8)) 21 > (three-arg-accumulate word "" '(come together)) COMETOGETHER </PRE> <P>But we've actually defined <CODE>accumulate</CODE> and <A NAME="g15"></A><CODE>reduce</CODE> so that only two arguments are required, the procedure and the sentence or list. We thought it would be too much trouble to have to provide the identity element all the time. How did we manage to avoid it? <P>The trick is that in our <CODE>reduce</CODE> and <CODE>accumulate</CODE> the base case is a one-element argument, rather than an empty argument. When we're down to one element in the argument, we just return that element: <P><PRE>(define (accumulate combiner stuff) ;; first version (if (empty? (bf stuff)) (first stuff) (combiner (first stuff) (accumulate combiner (bf stuff))))) </PRE> <P>This version is a simplification of the one we actually provide. What happens if <CODE>stuff</CODE> is empty? This version blows up, since it tries to take the <CODE>butfirst</CODE> of <CODE>stuff</CODE> immediately. Our final version has a specific check for empty arguments: <P><PRE>(define (<A NAME="g16"></A>accumulate combiner stuff) (cond ((not (empty? stuff)) (real-accumulate combiner stuff)) ((member combiner (list + * word se append)) (combiner)) (else (error "Can't accumulate empty input with that combiner")))) (define (<A NAME="g17"></A>real-accumulate combiner stuff) (if (empty? (bf stuff)) (first stuff) (combiner (first stuff) (real-accumulate combiner (bf stuff))))) </PRE> <P>This version works just like the earlier version as long as <CODE>stuff</CODE> isn't empty. (<CODE>Reduce</CODE> is the same, except that it uses <CODE>null?</CODE>, <CODE>car</CODE>, and <CODE>cdr</CODE>.) <P>As we mentioned in Chapter 8, many of Scheme's primitive procedures return their identity element when invoked with no arguments. We can take advantage of this; if <CODE>accumulate</CODE> is invoked with an empty second argument and one of the procedures <CODE>+</CODE>, <CODE>*</CODE>, <CODE>word</CODE>, <CODE>sentence</CODE>, <CODE>append</CODE> or <CODE>list</CODE>, we invoke the combiner with no arguments to produce the return value. <P> <P>On the other hand, if <CODE>accumulate</CODE>'s combiner argument is something like <CODE>(lambda (x y) (word x '- y))</CODE> or <CODE>max</CODE>, then there's nothing <CODE>accumulate</CODE> can return, so we give an error message. (But it's a more descriptive error message than the first version; what message do you get when you call that first version with an empty second argument?) <P>It's somewhat of a kludge that we have to include in our procedure a list of the functions that can be called without arguments. What we'd like to do is invoke the combiner and find out if that causes an error, but Scheme doesn't provide a mechanism for causing errors on purpose and recovering from them. (Some dialects of Lisp do have that capability.) <P><H2>Robustness</H2> <P>Instead of providing a special error message for empty-argument cases that <CODE>accumulate</CODE> can't handle, we could have just let it blow up: <P><PRE>(define (accumulate combiner stuff) ;; non-robust version (if (not (empty? stuff)) (real-accumulate combiner stuff) (combiner))) </PRE> <P>Some questions about programming have clear right and wrong answers—if your program doesn't work, it's wrong! But the decision about whether to include the extra check for a procedure that's usable with an empty argument is a matter of judgment. <P>Here is the reasoning in favor of this simpler version: In either version, the user who tries to evaluate an expression like <P><PRE>(accumulate max '()) </PRE> <P>is going to get an error message. In the longer version we've spent both our own programming effort and a little of the computer's time on every invocation just to give a <EM>different</EM> error message from the one that Scheme would have given anyway. What's the point? <P>Here is the reasoning in favor of the longer version: In practice, the empty-argument situation isn't going to arise because someone uses a quoted empty sentence; instead the second argument to <CODE>accumulate</CODE> will be some expression whose value happens to be empty under certain conditions. The user will then have to debug the program that caused those conditions. Debugging is hard; we should make it easier for the user, if we can, by giving an error message that points clearly to the problem. <P>A program that behaves politely when given incorrect input is called <EM>robust.</EM> It's not always a matter of better or worse error messages. For example, a program that reads input from a human user might offer the chance to try again if some input value is incorrect. A robust program will also be alert for hardware problems, such as running out of space on a disk, or getting garbled information over a telephone connection to another machine because of noise on the line. <P>It's possible to pay either too little or too much attention to program robustness. If you're a professional programmer, your employer will expect your programs to survive errors that are likely to happen. On the other hand, your programs will be hard to read and debug if the error checking swamps the real work! As a student, unless you are specifically asked to "bulletproof" your program, don't answer exam questions by writing procedures like this one: <P><PRE>(define (even? num) ;; silly example (cond ((not (number? num)) (error "Not a number.")) ((not (integer? num)) (error "Not an integer.")) ((< num 0) (error "Argument must be positive.")) (else (= (remainder num 2) 0)))) </PRE> <P>In the case of <CODE>accumulate</CODE>, we decided to be extra robust because we were writing a procedure for use in a beginning programming course. If we were writing this tool just for our own use, we might have chosen the non-robust version. Deciding how robust a program will be is a matter of taste. <P><H2>Higher-Order Functions for Structured Lists</H2> <P>We've given you a fairly standard set of higher-order functions, but there's no law that says these are the only ones. Any time you notice yourself writing what feels like the same procedure over again, but with different details, consider inventing a higher-order function. <P>For example, here's a procedure we defined in Chapter 17. <P><PRE>(define (<A NAME="g18"></A>deep-pigl structure) (cond ((word? structure) (pigl structure)) ((null? structure) '()) (else (cons (deep-pigl (car structure)) (deep-pigl (cdr structure)))))) </PRE> <P>This procedure converts every word in a <A NAME="g19"></A><A NAME="g20"></A>structured list to Pig Latin. Suppose we have a structure full of numbers and we want to compute all of their squares. We could write a specific procedure <CODE>deep-square</CODE>, but instead, we'll write a higher-order procedure: <P><PRE>(define (<A NAME="g21"></A>deep-map f structure) (cond ((word? structure) (f structure)) ((null? structure) '()) (else (cons (deep-map f (car structure)) (deep-map f (cdr structure)))))) </PRE> <P><H2>The Zero-Trip Do Loop</H2> <P>The first programming language that provided a level of abstraction over the instructions understood directly by computer hardware was Fortran, a language that is still widely used today despite the advances in programming language design since then. Fortran remains popular because of the enormous number of useful programs that have already been written in it; if an improvement is needed, it's easier to modify the Fortran program than to start again in some more modern language. <P>Fortran includes a control mechanism called <CODE>do</CODE>, a sort of higher-order procedure that carries out a computation repeatedly, as <CODE>every</CODE> does. But instead of carrying out the computation once for each element of a given collection of data (like the sentence argument to <CODE>every</CODE>), <CODE>do</CODE> performs a computation once for each integer in a range specified by its endpoints. "For every number between 4 and 16, do such-and-such." <P>What if you specify endpoints such that the starting value is greater than the ending value? In the first implementation of Fortran, nobody thought very hard about this question, and they happened to implement <CODE>do</CODE> in such a way that if you specified a backward range, the computation was done once, for the given starting value, before Fortran noticed that it was past the ending value. <P>Twenty years later, a bunch of computer scientists argued that this behavior was wrong—that a <CODE>do</CODE> loop with its starting value greater than its ending value should not carry out its computation at all. This proposal for a "zero-trip <CODE>do</CODE> loop" was strongly opposed by Fortran old-timers, not because of any principle but because of all the thousands of Fortran programs that had been written to rely on the one-trip behavior. <P>The point of this story is that the Fortran users had to debate the issue so heatedly because they are stuck with only the control mechanisms that are built into the language. Fortran doesn't have the idea of function as data, so Fortran programmers can't write their own higher-order procedures. But you, using the techniques of this chapter, can create precisely the control mechanism that you need for whatever problem you happen to be working on. <P><H2>Pitfalls</H2> <P>The most crucial point in inventing a higher-order function is to make sure that the pattern you have in mind really does generalize. For example, if you want to write a higher-order function for structured data, what is the base case? Will you use the tree abstract data type, or will you use <CODE>car</CODE>/<CODE>cdr</CODE> recursion? <P>When you generalize a pattern by adding a new argument (typically a procedure), be sure you add it to the recursive invocation(s) as well as to the formal parameter list! <P><H2>Boring Exercises</H2> <P><B>19.1</B> What happens if you say the following? <P><PRE>(every cdr '((john lennon) (paul mccartney) (george harrison) (ringo starr))) </PRE> <P>How is this different from using <CODE>map</CODE>, and why? How about <CODE>cadr</CODE> instead of <CODE>cdr</CODE>? <P> <H2>Real Exercises</H2> <P><B>19.2</B> Write <CODE>keep</CODE>. Don't forget that <CODE>keep</CODE> has to return a sentence if its second argument is a sentence, and a word if its second argument is a word. <P>(Hint: it might be useful to write a <CODE>combine</CODE> procedure that uses either <CODE>word</CODE> or <CODE>sentence</CODE> depending on the types of its arguments.) <P> <B>19.3</B> Write the three-argument version of <CODE>accumulate</CODE> that we described. <P><PRE>> (three-arg-accumulate + 0 '(4 5 6)) 15 > (three-arg-accumulate + 0 '()) 0 > (three-arg-accumulate cons '() '(a b c d e)) (A B C D E) </PRE> <P> <B>19.4</B> Our <CODE>accumulate</CODE> combines elements from right to left. That is, <P><PRE>(accumulate - '(2 3 4 5)) </PRE> <P>computes 2−(3−(4−5)). Write <CODE>left-accumulate</CODE>, which will compute ((2−3)−4)−5 instead. (The result will be the same for an operation such as <CODE>+</CODE>, for which grouping order doesn't matter, but will be different for <CODE>-</CODE>.) <P> <B>19.5</B> Rewrite the <CODE>true-for-all?</CODE> procedure from Exercise <A HREF="../ssch8/higher.html#trueforall">8.10</A>. Do not use <CODE>every</CODE>, <CODE>keep</CODE>, or <CODE>accumulate</CODE>. <P> <B>19.6</B> Write a procedure <CODE><A NAME="g22"></A>true-for-any-pair?</CODE> that takes a predicate and a sentence as arguments. The predicate must accept two words as its arguments. Your procedure should return <CODE>#t</CODE> if the argument predicate will return true for any two adjacent words in the sentence: <A NAME="exanypair"></A> <P><PRE>> (true-for-any-pair? equal? '(a b c b a)) #F > (true-for-any-pair? equal? '(a b c c d)) #T > (true-for-any-pair? < '(20 16 5 8 6)) ;; 5 is less than 8 #T </PRE> <P> <B>19.7</B> Write a procedure <CODE><A NAME="g23"></A>true-for-all-pairs?</CODE> that takes a predicate and a sentence as arguments. The predicate must accept two words as its arguments. Your procedure should return <CODE>#t</CODE> if the argument predicate will return true for <EM>every</EM> two adjacent words in the sentence: <A NAME="exallpairs"></A> <P><PRE>> (true-for-all-pairs? equal? '(a b c c d)) #F > (true-for-all-pairs? equal? '(a a a a a)) #T > (true-for-all-pairs? < '(20 16 5 8 6)) #F > (true-for-all-pairs? < '(3 7 19 22 43)) #T </PRE> <P> <B>19.8</B> Rewrite <CODE>true-for-all-pairs?</CODE> (Exercise <A HREF="implement-hof.html#exallpairs">19.7</A>) using <CODE>true-for-any-pair?</CODE> (Exercise <A HREF="implement-hof.html#exanypair">19.6</A>) as a helper procedure. Don't use recursion in solving this problem (except for the recursion you've already used to write <CODE>true-for-any-pair?</CODE>). Hint: You'll find the <CODE>not</CODE> procedure helpful. <P> <B>19.9</B> Rewrite either of the sort procedures from Chapter 15 to take two arguments, a list and a predicate. It should sort the elements of that list according to the given predicate: <P><PRE>> (sort '(4 23 7 5 16 3) <) (3 4 5 7 16 23) > (sort '(4 23 7 5 16 3) >) (23 16 7 5 4 3) > (sort '(john paul george ringo) before?) (GEORGE JOHN PAUL RINGO) </PRE> <P> <B>19.10</B> Write <CODE>tree-map</CODE>, analogous to our <CODE>deep-map</CODE>, but for trees, using the <CODE>datum</CODE> and <CODE>children</CODE> selectors. <P> <B>19.11</B> Write <CODE>repeated</CODE>. (This is a hard exercise!) <P> <B>19.12</B> Write <CODE>tree-reduce</CODE>. You may assume that the combiner argument can be invoked with no arguments. <P><PRE>> (tree-reduce + (make-node 3 (list (make-node 4 '()) (make-node 7 '()) (make-node 2 (list (make-node 3 '()) (make-node 8 '())))))) 27 </PRE> <P> <B>19.13</B> Write <CODE>deep-reduce</CODE>, similar to <CODE>tree-reduce</CODE>, but for structured lists: <P><PRE>> (deep-reduce word '(r ((a (m b) (l)) (e (r))))) RAMBLER </PRE> <P> <HR> <P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> <A HREF="../ssch18/trees.html"><STRONG>BACK</STRONG></A> chapter thread <A HREF="../ssch20/part6.html"><STRONG>NEXT</STRONG></A> <P> <ADDRESS> <A HREF="../index.html">Brian Harvey</A>, <CODE>bh@cs.berkeley.edu</CODE> </ADDRESS> </BODY> </HTML>