Section 21

Designing Abstractions from Examples

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.

21.1  Abstracting from Examples

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:

The comparison:

When we find two function definitions that are almost the same except at a few places and for their names, we compare them and mark the differences with boxes. If the boxes contain only values, we can abstract.

Warning: Abstracting over Non-values: The recipe requires a substantial modification for non-values. 

Here is a pair of similar function definitions:

;; convertCF : lon  ->  lon (define (convertCF alon) (cond [(empty? alon) empty] [else (cons (C->F (first alon)) (convertCF (rest alon)))]))

;; names : loIR  ->  los (define (names aloIR) (cond [(empty? aloIR) empty] [else (cons (IR-name (first aloIR)) (names (rest aloIR)))]))

The two functions apply a function to each item in a list. They differ in only one aspect: what they apply to each item on the list. The two boxes emphasize the difference. Each contains a functional value, so we can abstract.

The abstraction:

Next we replace the contents of corresponding pairs of boxes with new names and add these names to the parameter list. For example, if there are three pairs of boxes, we need three new names. The two definitions must now be the same, except for the function name. To obtain the abstraction, we systematically replace the function names with one new name.

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

We have replaced the boxed names with 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.

The test:

Now we must validate that the new function is a correct abstraction of the original concrete functions. The very definition of abstraction suggests that we define the original functions in terms of the abstract one and test the new versions with the original examples.

In most cases, defining the original function based on the abstract one is straightforward. Suppose the abstract function is called f-abstract, and furthermore suppose that one original function is called f-original and consumes one argument. If f-original 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 V, (f-from-abstract V) now produces the same answer as (f-original V).

Let us return to our example. Here are the two new definitions:

;; convertCF-from-map : lon  ->  lon (define (convertCF-from-map alon) (map C->F alon))

;; names-from-map : loIR  ->  los (define (names-from-map aloIR) (map IR-name aloIR))

To ensure that these two definitions are equivalent to the old one and, indirectly, that map is a correct abstraction, we now apply these two functions to the examples that we specified for the development of convertCF and names.

The contract:

To make the abstraction truly useful, we must also formulate a contract. If the boxed values in stage 2 of our recipe are functions, a contract requires the use of arrow types. Furthermore, to obtain a widely usable contract, we may have to develop or use parametric data definitions and formulate a parametric type.

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 Xs. Furthermore, map creates a list from the results of applying f to each item. Thus, if f produces Ys, then 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 Ys from a list of Xs 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-sin : number  ->  lon
;; to tabulate sin between n 
;; and 0 (inclusive) in a list
(define (tabulate-sin n)
  (cond
    [(= n 0) (list (sin 0))]
    [else
      (cons (sin n)
	(tabulate-sin (sub1 n)))]))

;; tabulate-sqrt : number  ->  lon
;; to tabulate sqrt between n 
;; and 0 (inclusive) in a list
(define (tabulate-sqrt n)
  (cond
    [(= n 0) (list (sqrt 0))]
    [else
      (cons (sqrt n)
	(tabulate-sqrt (sub1 n)))]))

Exercise 21.1.2.   Define fold, which is the abstraction of the following two functions:

;; sum : (listof number)  ->  number
;; to compute the sum of 
;; the numbers on alon
(define (sum alon)
  (cond
    [(empty? alon) 0]
    [else (+ (first alon)
	     (sum (rest alon)))]))

;; product : (listof number)  ->  number
;; to compute the product of 
;; the numbers on alon
(define (product alon)
  (cond
    [(empty? alon) 1]
    [else (* (first alon)
	     (product (rest alon)))]))

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 natural-f, which is the abstraction of the following two functions:

;; copy : N X  ->  (listof X)
;; to create a list that contains
;; obj n times
(define (copy n obj)
  (cond
    [(zero? n) empty]
    [else (cons obj 
                (copy (sub1 n) obj))]))

;; n-adder : N number  ->  number
;; to add n to x using
;; (+ 1 ...) only
(define (n-adder n x)
  (cond
    [(zero? n) x]
    [else (+ 1
             (n-adder (sub1 n) x))]))

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:

Consider the second stage of our abstraction recipe. The most natural contracts are as follows:

Here is a second pair of examples:

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:

Here is the new contract:

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. 

21.2  Finger Exercises with Abstract List Functions

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.

;; build-list : N (N  ->  X)  ->  (listof X)
;; to construct (list (f 0) ... (f (- n 1)))
(define (build-list n f) ...)

;; filter : (X  ->  boolean) (listof X)  ->  (listof X)
;; to construct a list from all those items on alox for which p holds 
(define (filter p alox) ...)

;; quicksort : (listof X) (X X  ->  boolean)  ->  (listof X)
;; to construct a list from all items on alox in an order according to cmp
(define (quicksort alox cmp) ...)

;; map : (X  ->  Y) (listof X)  ->  (listof Y)
;; to construct a list by applying f to each item on alox
;; that is, (map f (list x-1 ... x-n)) = (list (f x-1) ... (f x-n))
(define (map f alox) ...)

;; andmap : (X  ->  boolean) (listof X)  ->  boolean
;; to determine whether p holds for every item on alox
;; that is, (andmap p (list x-1 ... x-n)) = (and (p x-1) (and ... (p x-n)))
(define (andmap p alox) ...)

;; ormap : (X  ->  boolean) (listof X)  ->  boolean
;; to determine whether p holds for at least one item on alox
;; that is, (ormap p (list x-1 ... x-n)) = (or (p x-1) (or ... (p x-n)))
(define (ormap p alox) ...)

;; foldr : (X Y  ->  Y) Y (listof X)  ->  Y
;; (foldr f base (list x-1 ... x-n)) = (f x-1 ... (f x-n base)) 
(define (foldr f base alox) ...)

;; foldl : (X Y  ->  Y) Y (listof X)  ->  Y
;; (foldl f base (list x-1 ... x-n)) = (f x-n ... (f x-1 base)) 
(define (foldl f base alox) ...)

;; assf : (X  ->  boolean) (listof (list X Y))  ->  (list X Y) or false
;; to find the first item on alop for whose first item p? holds
(define (assf p? alop) ...)

Exercise 21.2.1.   Use build-list

1. to create the lists (list 0 ... 3) and (list 1 ... 4);

2. to create the list (list .1 .01 .001 .0001);

3. to define evens, which consumes a natural number n and creates the list of the first n even numbers;

4. to define tabulate from exercise 21.1.1; and

5. 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:

1. 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 dollar;

2. convertFC, which converts a list of Fahrenheit measurements to a list of Celsius measurements;

3. move-all, which consumes a list of posn structures and translates each by adding 3 to the x-component.    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 of X from 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))])]))

Use filter to define the following functions:

1. 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 ua;

2. 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;

3. selection, which consumes two lists of names and selects all those from the second one that are also on the first.    Solution

21.3  Abstraction and a Single Point of Control

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:

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.⁴⁷

21.4  Extended Exercise: Moving Pictures, Again

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.

Exercise 21.4.1.   Abstract the functions draw-a-circle and clear-a-circle into a single function process-circle.

Define translate-circle using 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 purpose.    Solution

Exercise 21.4.2.   Abstract the functions draw-a-rectangle and clear-a-rectangle into a single function process-rectangle.

Define translate-rectangle using process-rectangle.    Solution

Exercise 21.4.3.   Abstract the functions draw-shape and clear-shape into a single function process-shape. Compare the function with the template fun-for-shape.

Define translate-shape using process-shape.    Solution

Exercise 21.4.4.   Use Scheme's map and andmap to define draw-losh, clear-losh, and translate-losh.    Solution

Figure 58:  The Apollo 11 lunar lander  NASA: National Space Science Data Center

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

21.5  Note: Designing Abstractions from Templates

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.

Using 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 : (listof number)  ->  number
(define (sum l) (reduce 0 + l))

;; product : (listof number)  ->  number
(define (product l) (reduce 1 * l))

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 list-processing functions can be defined in a similar manner.