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 Non-values: The recipe requires a substantial modification for non-values.
Here is a pair of similar function definitions:
For our running example, we obtain the following pair of functions:
(define (convertCF f alon) (cond [(empty? alon) empty] [else (cons (f (first alon)) (convertCF f (rest alon)))]))
(define (names f aloIR) (cond [(empty? aloIR) empty] [else (cons (f (first aloIR)) (names f (rest aloIR)))]))
fas a parameter. Now we replace
nameswith 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
and furthermore suppose that one original function is called
f-original and consumes one argument. If
differs from the other concrete function in the use of one value, say,
boxed-value, then we define the following function:
(define (f-from-abstract x) (f-abstract boxed-value x))
For every proper value
(f-from-abstract V) now
produces the same answer as
Let us return to our example. Here are the two new definitions:
mapis a correct abstraction, we now apply these two functions to the examples that we specified for the development of
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
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
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 -> ???
map creates a
list from the results of applying
f to each item. Thus, if
map produces a list of
Ys. 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
a list of
Xs and a function from
Y -- no
matter for what collection of
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.
tabulate, which is the abstraction of the following two
tabulate. Also use
tabulateto define a tabulation function for
tan. What would be a good, general contract? Solution
fold, which is the abstraction of the following two functions:
fold is defined and tested, use it to define
append, which juxtaposes the items of two lists or, equivalently,
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))
Compare the four examples to formulate a contract. Solution
natural-f, which is the abstraction of the following two
natural-f. Also use
n-multiplier, which consumes
xwith additions only. Use the examples to formulate a contract.
Hint: The two function differ more than, say, the functions
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.
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:
->, we have
IR; to the right, it is
Consider the second stage of our abstraction recipe. The most natural contracts are as follows:
symbolwith variables, we get an abstract contract, and it is indeed a contract for
number, we get the first of the intermediate contracts.
Here is a second pair of examples:
below-ir. The contracts differ in two places: the lists consumed and produced. As usual, the functions of the second stage consume an additional argument:
A comparison of the two contracts suggests that
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
Ybecause the second argument is always just the first argument of
filter1's first argument.
Here is the new contract:
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.
to create the lists
(list 0 ... 3) and
(list 1 ... 4);
to create the list
(list .1 .01 .001 .0001);
evens, which consumes a natural number
and creates the list of the first
n even numbers;
tabulate from exercise 21.1.1; and
diagonal, which consumes a natural number
and creates a list of lists of
(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
map to define the following functions:
convert-euro, 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
convertFC, which converts a list of Fahrenheit measurements
to a list of Celsius measurements;
move-all, which consumes a list of
posn structures and
translates each by adding
3 to the x-component.
Here is the version of
filter that DrScheme provides:
filter : (X -> boolean) (listof X) -> (listof X);; to construct a list of
Xfrom all those items on
alon;; for which
predicate?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))])]))
filter to define the following functions:
eliminate-exp, 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
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
selection, which consumes two lists of names and selects all
those from the second one that are also on the
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 data-traversal 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 built-in operations.
Abstract the functions
clear-a-circle into a
process-circle. 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 short-hand for that
Abstract the functions
clear-a-rectangle into a
Abstract the functions
clear-shape into a
process-shape. Compare the function with the template
andmap to define
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.
LUNAR, a list that sketches a lunar lander picture (see
figure 58). The list should consist of rectangles,
circles, and lines.
Develop the program
lunar-lander. 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) (control-up-down LUNAR 10 move-lander draw-losh)
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.
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 (fun-for-l l) (cond [(empty? l) ...] [else ... (first l) ... (fun-for-l (rest l)) ...]))
It contains two gaps, one in each clause. When we define a list-processing
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.
reduce we can define many plain list-processing 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
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 list-processing functions can be defined in a similar manner.
47 A currently popular method of abstraction is INHERITANCE in class-based object-oriented programming languages. Inheritance is quite similar to functional abstraction, though it emphasizes those aspects that change over those that stay the same.