When we first learn to add, we use concrete examples. Later on, we study how to add two arbitrary numbers; that is, we form an abstraction of the addition operation. Much later still, we learn to formulate abstractions directly as expressions: expressions that compute the wage of some employee, expressions that convert temperatures, or expressions that determine the area of a geometric shape. In short, we initially go from concrete examples to abstraction, but eventually we learn to form abstractions directly without thinking (much) about concrete instances.
In this section, we discuss a design recipe for creating abstractions from concrete examples. Later, in sections 21.5 and 22 we study additional approaches to function abstraction.
Forming abstractions from examples is easy. As we have seen in section 19, we start from two concrete function definitions, compare them, mark the differences, and abstract. Let us formulate these steps as a recipe:
Warning: Abstracting over Nonvalues: The recipe requires a substantial modification for nonvalues.
Here is a pair of similar function definitions:
For our running example, we obtain the following pair of functions:
f
and added f
as a
parameter. Now we replace convertCF
and names
with a new
name and thus obtain the abstract function:
(define (map f lon) (cond [(empty? lon) empty] [else (cons (f (first lon)) (map f (rest lon)))]))
We use the name map
for the result in our running example, because
it is the traditional name in programming languages
for this specific function.
In most cases, defining the original function based on the abstract one is
straightforward. Suppose the abstract function is called fabstract
,
and furthermore suppose that one original function is called
foriginal
and consumes one argument. If foriginal
differs from the other concrete function in the use of one value, say,
boxedvalue
, then we define the following function:
(define (ffromabstract x) (fabstract boxedvalue x))
For every proper value V
, (ffromabstract V)
now
produces the same answer as (foriginal V)
.
Let us return to our example. Here are the two new definitions:
;;  ;; 
map
is a correct abstraction, we now apply these
two functions to the examples that we specified for the development of
convertCF
and names
.
A case in point is the contract for map
. On one hand, if we view
map
as an abstraction of convertCF
, the contract could be
construed as
;; map : (number > number) (listof number) > (listof number)
On the other hand, if we view map
as an abstraction of
names
, the contract could be construed as
;; map : (IR > symbol) (listof IR) > (listof symbol)
But the first contract would be useless in the second case, and vice
versa. To accommodate both cases, we must understand what map
does and then fix a contract.
By looking at the definition, we can see that map applies its first
argument, a function, to every item on the second argument, a list. This
implies that the function must consume the class of data that the list
contains. That is, we know f
has the contract
;; f : X > ???
if lon
contains X
s. Furthermore, map
creates a
list from the results of applying f
to each item. Thus, if
f
produces Y
s, then map
produces a list of
Y
s. Translated into our language of contracts we get this:
;; map : (X > Y) (listof X) > (listof Y)
This contract says that map
can produce a list of Y
s from
a list of X
s and a function from X
to Y
 no
matter for what collection of X
and Y
stand.
Once we have abstracted two (or more) functions, we should check whether
there are other uses for the abstract function. In many cases, an abstract
function is useful in a much broader array of contexts than we first
anticipate and makes functions easier to read, understand, and maintain.
For example, we can now use map
every time we need a function to
produce a new list by processing all items on an existing list. If that
function is a primitive operation or a function we have defined, we don't
even write a function. Instead, we simply write an expression that performs
the task. Unfortunately, there is no recipe that guides this discovery
process. We must practice it and develop an eye for matching abstract
functions to situations.
Exercise 21.1.1.
Define tabulate
, which is the abstraction of the following two
functions:
tabulate
.
Also use tabulate
to define a tabulation function for
sqr
and tan
. What would be a good, general contract?
Solution
Exercise 21.1.2.
Define fold
, which is the abstraction of the following two functions:
fold
.
After fold
is defined and tested, use it to define
append
, which juxtaposes the items of two lists or, equivalently,
replaces empty
at the end of the first list with the second list:
(equal? (append (list 1 2 3) (list 4 5 6 7 8)) (list 1 2 3 4 5 6 7 8))
Finally, define map
using fold
.
Compare the four examples to formulate a contract. Solution
Exercise 21.1.3.
Define naturalf
, which is the abstraction of the following two
functions:
naturalf
. Also use naturalf
to
define nmultiplier
, which consumes n
and x
and
produces n
times x
with additions only. Use the examples
to formulate a contract.
Hint: The two function differ more than, say, the functions sum
and product
in exercise 21.1.2. In particular, the
base case in one instance is a argument of the function, where in the other
it is just a constant value.
Solution
Formulating General Contracts: To increase the usefulness of an abstract function, we must formulate a contract that describes its applicability in the most general terms possible. In principle, abstracting contracts follows the same recipe that we use for abstracting functions. We compare and contrast the old contracts; then we replace the differences with variables. But the process is complicated and requires a lot of practice.
Let us start with our running example: convertCF
and names
:

>
, we have number
and IR
; to the right,
it is number
versus symbol
.Consider the second stage of our abstraction recipe. The most natural contracts are as follows:

IR
and symbol
with variables, we get an abstract
contract, and it is indeed a contract for map
:
map : (X > Y) (listof X) > (listof Y)

X
with
number
and Y
with number
, we get the first
of the intermediate contracts. Here is a second pair of examples:

below
and belowir
. The
contracts differ in two places: the lists consumed and produced. As usual,
the functions of the second stage consume an additional argument:

IR
.
A comparison of the two contracts suggests that number
and
IR
occupy related positions and that we should replace them with a
variable. Doing so makes the two contracts equal:

filter1
's definition shows that we can also
replace number
with Y
because the second argument is
always just the first argument of filter1
's first argument. Here is the new contract:
filter1 : (Y X > boolean) Y (listof X) > (listof X)

boolean
, because it is
used as a condition. Hence we have found the most general contract
possible.The two examples illustrate how to find general contracts. We compare the contracts of the examples from which we create abstractions. By replacing specific, distinct classes in corresponding positions, one at a time, we make the contract gradually more general. To ensure that our generalized contract works, we check that the contract describes the specific instances of the abstracted function properly.
Scheme provides a number of abstract functions for processing lists. Figure 57 collects the specification of the most important ones. Using these functions greatly simplifies many programming tasks and helps readers understand programs quickly. The following exercises provide an opportunity to get acquainted with these functions.
Exercise 21.2.1.
Use buildlist
to create the lists (list 0 ... 3)
and (list 1 ... 4)
;
to create the list (list .1 .01 .001 .0001)
;
to define evens
, which consumes a natural number n
and creates the list of the first n
even numbers;
to define tabulate
from exercise 21.1.1; and
to define diagonal
, which consumes a natural number n
and creates a list of lists of 0
and 1
.
Example:
(equal? (diagonal 3) (list (list 1 0 0) (list 0 1 0) (list 0 0 1)))
Use local if function definitions require auxiliary functions. Solution
Exercise 21.2.2.
Use map
to define the following functions:
converteuro
, which converts a list of U.S. dollar amounts
into a list of euro amounts based on an exchange rate of 1.22 euro for each
dollar;
convertFC
, which converts a list of Fahrenheit measurements
to a list of Celsius measurements;
moveall
, which consumes a list of posn
structures and
translates each by adding 3
to the xcomponent.
Solution
Exercise 21.2.3.
Here is the version of filter
that DrScheme provides:
;;filter : (X > boolean) (listof X) > (listof X)
;; to construct a list ofX
from all those items onalon
;; for whichpredicate?
holds (define (filter predicate? alon) (cond [(empty? alon) empty] [else (cond [(predicate? (first alon)) (cons (first alon) (filter predicate? (rest alon)))] [else (filter predicate? (rest alon))])]))
Use filter
to define the following functions:
eliminateexp
, which consumes a number, ua
, and a
list of toy structures (containing name and price) and produces a list of
all those descriptions whose price is below ua
;
recall
, which consumes the name of a toy, called
ty
, and a list of names, called lon
, and produces a list
of names that contains all components of lon
with the exception of
ty
;
selection
, which consumes two lists of names and selects all
those from the second one that are also on the
first.
Solution
Just like editing papers, abstracting programs has many advantages. Creating an abstraction often simplifies other definitions. The process of abstracting may uncover problems with existing functions. But, the single most important advantage of abstraction is that it creates a SINGLE POINT OF CONTROL for the functionality in a program. In other words, it (as much as possible) puts in one place the definitions related to some specific task.
Putting the definitions for a specific task in one place makes it easier to maintain a program. Roughly put, program maintenance means fixing the program so that it functions properly in previously untested cases; extending the program so that it can deal with new or unforeseen situations; or changing the representation of some information as data (for example, calendar dates). With everything in one place, fixing an error means fixing it in one function, not four or five similar versions. Extending a function's capabilities means fixing one function, not its related copies. And changing a data representation means changing a general datatraversal function, not all those that came from the same template. Translated into a guideline, this becomes:
Guideline on Creating Abstractions 
Form an abstraction instead of copying and modifying a piece of a program. 
Experience teaches us that maintaining software is expensive. Programmers can reduce the maintenance cost by organizing programs correctly. The first principle of function organization is to match the function's structure to the structure of its input data. If every programmer follows this rule, it is easy to modify and extend functions when the set of possible input data changes. The second principle is to introduce proper abstractions. Every abstracted function creates a single point of control for at least two different functions, often for several more. After we have abstracted, we often find more uses of the new function.
Our design recipe for abstracting functions is the most basic tool to create abstractions. To use it requires practice. As we practice, we expand our capabilities for building and using abstractions. The best programmers are those who actively edit their programs to build new abstractions so that they collect things related to a task at a single point. Here we use functional abstraction to study this practice. While not all languages provide the freedom to abstract functions as easily as Scheme, modern languages often support similar concepts and practicing in powerful languages such as Scheme is the best possible preparation.^{47}
In sections 6.6, 7.4, and 10.3, we studied the problem of moving pictures across a canvas. The problem had two parts: moving individual shapes and moving a picture, which is a list of shapes. For the first part, we need functions to draw, clear, and translate a shape. For the second part, we need functions that draw all shapes on a list, that clear all shapes on a list, and that translate all shapes on a list. Even the most cursory look at the functions shows many repetitions. The following exercises aim to eliminate these repetitions via manual abstraction and Scheme's builtin operations.
Exercise 21.4.1.
Abstract the functions drawacircle
and clearacircle
into a
single function processcircle
.
Define translatecircle
using processcircle
. Hint: If a
primitive function doesn't quite fit an abstraction, we have to define
auxiliary functions. For now, use define
to do so. Intermezzo 4
introduces a handy and important shorthand for that
purpose.
Solution
Exercise 21.4.2.
Abstract the functions drawarectangle
and cleararectangle
into a
single function processrectangle
.
Define translaterectangle
using
processrectangle
.
Solution
Exercise 21.4.3.
Abstract the functions drawshape
and clearshape
into a
single function processshape
. Compare the function with the template
funforshape
.
Define translateshape
using processshape
.
Solution
Exercise 21.4.4.
Use Scheme's map
and andmap
to define drawlosh
,
clearlosh
, and translatelosh
.
Solution

Exercise 21.4.5. Modify the functions of exercises 21.4.3 and 21.4.4 so that pictures move up and down on a canvas.
Modify all definitions so that a shape can also be a line; a line has a start position, an end position, and a color.
Define LUNAR
, a list that sketches a lunar lander picture (see
figure 58). The list should consist of rectangles,
circles, and lines.
Develop the program lunarlander
. It places LUNAR at the top of a
canvas and then uses the modified functions to move the lander up or down.
Use the teachpack arrow.ss to give users control over how fast and when the lunar lander should move:
(start 500 100) (draw LUNAR) (controlupdown LUNAR 10 movelander drawlosh)
If time permits, modify the function so that a player can move the lander up,
down, left or right. Use controller
from arrow.ss to control the
movements in all directions.
Solution
At the very beginning of this part of the book, we discussed how we design sets of functions from the same template. More specifically, when we design a set of functions that all consume the same kind of data, we reuse the same template over and over again. It is therefore not surprising that the function definitions look similar and that we will abstract them later.
Indeed, we could abstract from the templates directly. While this topic is highly advanced and still a subject of research in the area of programming languages, we can discuss it with a short example. Consider the template for lists:
(define (funforl l) (cond [(empty? l) ...] [else ... (first l) ... (funforl (rest l)) ...]))
It contains two gaps, one in each clause. When we define a listprocessing
function, we fill these gaps. In the first clause, we typically place a
plain value. For the second one, we combine (first l)
and
(f (rest l))
where f
is the recursive function.
We can abstract over this programming task with the following function:
;; reduce : X (X Y > Y) (listof Y) > Y
(define (reduce base combine l)
(cond
[(empty? l) base]
[else (combine (first l)
(reduce base combine (rest l)))]))
It consumes two extra arguments: base
, which is the value for the
base case, and combine
, which is a function that performs the
value combination for the second clause.
Using reduce
we can define many plain listprocessing functions as
well as almost all the functions of figure 57. Here
are two of them:
;;  ;; 
sum
, the base case always produces 0
; adding the
first item and the result of the natural recursion combines the values of
the second clause. Analogous reasoning explains product
.
To define sort
, we need to define an auxiliary function first:
;; sort : (listof number) > (listof number)
(define (sort l)
(local ((define (insert an alon)
(cond
[(empty? alon) (list an)]
[else (cond
[(> an (first alon)) (cons an alon)]
[else (cons (first alon) (insert an (rest alon)))])])))
(reduce empty insert l)))
Other listprocessing functions can be defined in a similar manner.
^{47} A currently popular method of abstraction is INHERITANCE in classbased objectoriented programming languages. Inheritance is quite similar to functional abstraction, though it emphasizes those aspects that change over those that stay the same.