Abstracting from Examples

Forming abstractions from examples is easy. As we have seen in section , 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 (   (first alon)) 
        (convertCF (rest alon)))])) 

;; names : loIR -> los
(define (names aloIR) 
  (cond 
    [(empty? aloIR) empty] 
    [else 
      (cons (   (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 (   (first alon)) 
        (convertCF f (rest alon)))])) 

(define (names f aloIR)
  (cond 
    [(empty? aloIR) empty] 
    [else 
      (cons (   (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.

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

Be sure to define the two functions in terms of tabulate. Also use tabulate to define a tabulation function for square 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:

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

Don't forget to test 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)) 

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

Don't forget to test natural-f. Also use natural-f to define n-multiplier, 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 . 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:

Comparing the two contracts shows that they differ in two places. To the left of ->, 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:

(number -> number)	(listof number)	->	(listof number)
(IR -> symbol)	(listof IR)	->	(listof symbol)

These new contracts suggest a pattern. Specifically, they suggest that the first argument, a function, consumes the items on the second argument, a list, and furthermore, that the results produced by these applications make up the output. The second contract is particularly telling. If we replace 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)

It is straightforward to check that by replacing X with number and Y with number, we get the first of the intermediate contracts.

Here is a second pair of examples:

number	(listof number)	->	(listof number)
number	(listof IR)	->	(listof IR)

They are the contracts for below and 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:

(number number -> boolean)	number	(listof number)	->	(listof number)
(number IR -> boolean)	number	(listof IR)	->	(listof IR)

The new argument is a function, which in the first case consumes a number, and in the second case an 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:

(number X -> boolean)	number	(listof X)	->	(listof X)
(number X -> boolean)	number	(listof X)	->	(listof X)

A closer inspection of 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)

The result of the first argument must be 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.