<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>