6 Abstraction

6.1 Similarities Everywhere

Many of our data definitions and function definitions look alike. For example, the definition for a list of strings differs from that of a list of numbers in only two regards: the name of the class of data and the words “string” and “number.” Similarly, a function that looks for a specific string in a list of strings is nearly indistinguishable from one that looks for a specific number in a list of numbers.

Over the years, people have come to realize that these kinds of similarities are problematic. Therefore good programmers try to eliminate them as much as possible. Seen this way a program is just like an essay or a memo. The first version is just a draft, and drafts demand editing. “Eliminate” implies that programmers write down their first drafts of programs, spot similarities, and then rework their drafts. Good programmers go through several such rounds of editing, but they also know when to stop because further rounds of editing eliminate only insignificant similarities.

In DrRacket, choose “Intermediate Student Language” from the “How to Design Programs” submenu in the “Language” menu. This section is about eliminating similarities in function definitions and in data definitions, a process that is called abstraction. Our means of avoiding similarities are specific to “Intermediate Student Language” or ISL for short. Other functional programming languages provide similar means, but in object-oriented languages you may find different mechanisms. Nevertheless, all abstraction step share the basic ideas spelled out in this chapter, and it will thus help you become a good programmer.

6.1.1 Similarities in Functions

The design recipe determines a function’s basic organization because the template is created from the data definition without regard to the purpose of the function. Not surprisingly then, functions that consume the same kind of data look alike.

; Los -> Boolean ; does l contain "dog" (define (contains-dog? l)   (cond     [(empty? l) false]     [else      (or        (string=? (first l) "dog")        (contains-dog?          (rest l)))]))

; Los -> Boolean ; does l contain "cat" (define (contains-cat? l)   (cond     [(empty? l) false]     [else      (or        (string=? (first l) "cat")        (contains-cat?          (rest l)))]))

Figure 47: Two similar functions

Consider the two functions in figure 47, which consume lists of strings and look for specific strings. The function on the left looks for "dog", the one on the right for "cat". The two functions are nearly indistinguishable. Each consumes lists of strings; each function body consists of a cond expressions with two clauses. Each produces false if the input is empty; each uses an or expressions to determine whether the first item is the desired item and, if not, uses recursion to look in the rest of the list. The only difference is the string that is used in the comparison of the nested cond expressions: contains-dog? uses "dog" and contains-cat? uses "cat". To highlight the differences, the two strings are shaded.

; Los -> Boolean ; does l contain "dog" (define (contains-dog? l)   (contains? "dog" l))

; Los -> Boolean ; does l contain "cat" (define (contains-cat? l)   (contains? "cat" l))

Figure 48: Two similar functions, revisited

Computing borrows the term “abstract” from mathematics. A mathematician refers to “6” as an abstract number because it only represents all different ways of naming six things. In contrast, “6 inches” or “6 eggs” are concrete instances of “6” because they express a measurement and a count. What you have just seen for the first time is called functional abstraction. Abstracting different versions of functions is one way to eliminate similarities from programs, and as you can see with this one simple example, doing so simplifies programs.

Exercise 183: Use contains? to define functions that search for "atom", "basic", and "zoo", respectively.

Exercise 184: Create test suites for the following two functions:

; Lon -> Lon ; add 1 to each number on l (define (add1* l)   (cond     [(empty? l) false]     [else      (cons (add1 (first l))            (add1* (rest l)))]))

; Lon -> Lon ; add 5 to each number on l (define (plus5 l)   (cond     [(empty? l) false]     [else      (cons (+ (first l) 5)            (plus5 (rest l)))]))

Then abstract over them. Define above two functions in terms of the abstraction as one-liners and use the existing test suites to confirm that the revised definitions work properly. Finally, design a function that subtracts 2 from each number on a given list.

6.1.2 More Similarities in Functions

Abstraction looks easy in the case of contains-dog? and contains-cat?. It takes only a comparison of two function definitions, a replacement of a literal string with a function parameter, and a quick check that it is easy to define the old functions with the abstract function. This kind of abstraction is so natural that it showed up in the preceding two parts of the book without much ado.

This section illustrates how the very same principle yields a powerful form of abstraction. Take a look at figure 49. Both functions consume a list of numbers and a threshold. The left one produces a list of all those numbers that are below the threshold, while the one on the right produces all those that are above the threshold.

; Lon Number -> Lon ; construct the list of numbers ; on l that are below t (define (small l t)   (cond     [(empty? l) empty]     [else      (cond        [(< (first l) t)         (cons (first l)               (small (rest l) t))]        [else         (small (rest l) t)])]))

; Lon Number -> Lon ; construct the list of numbers ; on l that are above t (define (large l t)   (cond     [(empty? l) empty]     [else      (cond        [(> (first l) t)         (cons (first l)               (large (rest l) t))]        [else         (large (rest l) t)])]))

Figure 49: Two more similar functions

The two functions different in only one place: the comparison operator that determines whether a number from the given list should be a part of the result or not. The function on the left uses <, the right one >. Other than that, the two functions look identical, not counting the function name.

Stop! At this point you should ask whether this definition makes any sense. Without further ado, we have created a function that consumes a function—something that you probably have not seen before. If you have taken a calculus course, you encountered the differential operator and the indefinite integral, both of which are functions that consume and produce a function. But we do not assume that you have taken such a course and show you these wonderful tricks anyway. It turns out, however, that your simple little teaching language ISL supports these kinds of functions, and that defining such functions is one of the most powerful tools of good programmers—even in languages in which function-consuming functions do not seem to be available.

Exercise 185: Check step 1 of the last calculation

(extract < (cons 6 (cons 4 empty)) 5)

= (extract < (cons 4 empty) 5)

by hand. Show every step.

Exercise 186: Evaluate the expression

(extract < (cons 8 (cons 6 (cons 4 empty))) 5)

by hand. Show the new steps, rely on prior calculations where possible.

Exercise 187: Evaluate (squared>? 3 10), (squared>? 4 10), and (squared>? 5 10) by hand. Then show that

(extract squared>? (list 3 4 5) 10)

evaluates to (list 4 5).

Exercise 188: The use of squared>? also suggests that the following function works with extract, too:

; Number Number -> Boolean

(define (squared10? x c)

(> (sqr x) 10))

In other words, the relational function that extract uses may ignore its second argument. After all, we already know it and it stays the same throughout the evaluation of (extract squared>? l t).

This, in turn, suggests another simplification of extract:

(define (filter predicate l)

(cond

[(empty? l) empty]

[else (cond

[(predicate (first l))

(cons (first l) (filter predicate (rest l)))]

[else

(filter predicate (rest l))])]))

The function filter consumes only a relational function, called predicate, and a list of numbers. Every item i on the list is checked with predicate. If (predicate i) holds, i is included in the result; otherwise, i disappears.

Show how to use filter to define functions that are equivalent to small and large. Test the definitions.

So far you have seen that abstracted function definitions can be more useful than the functions you start from. For example, contains? is more useful than contains-dog? and contains-cat?, and extract is more useful than small and large. These effects of abstraction are crucial for large, industrial programming projects. For that reason, programming language and software engineering research has focused on how to create single points of control in large projects. Of course, the same idea applies to all kinds of computer designs (word documents, spread sheets) and organizations in general. Another important aspect of abstraction is that you now have a single point of control over all these functions. If it turns out that the abstract function contains a mistake, fixing its definition suffices to fix all other definitions. Similarly, if you figure out how to accelerate the computations of the abstract function or how to reduce its energy consumption, then all functions defined in terms of this function are improved without further ado. The following exercises indicate how these single-point-of-control improvements work.

Exercise 189: Abstract the following two functions into a single function:

; Nelon -> Number ; to determine the smallest ; number on l (define (inf l)   (cond     [(empty? (rest l))      (first l)]     [else      (cond        [(< (first l) (inf (rest l)))         (first l)]        [else         (inf (rest l))])]))

; Nelon -> Number ; to determine the largest ; number on l (define (sup l)   (cond     [(empty? (rest l))      (first l)]     [else      (cond        [(> (first l) (sup (rest l)))         (first l)]        [else         (sup (rest l))])]))

Both consume non-empty lists of numbers (Nelon) and produce a single number. The left one produces the smallest number in the list, the right one the largest.

Define inf-1 and sup-1 in terms of the abstract function. Test each of them with these two lists:

(list 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1)

(list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25)

Why are these functions slow on some of the long lists?

Modify the original functions with the use of max, which picks the larger of two numbers, and min, which picks the smaller one. Then abstract again, define inf-2 and sup-2, and test them with the same inputs again. Why are these versions so much faster?

For a complete answer to the two questions on performance, see Intermezzo: Scope.

Exercise 190: The sort-> function consumes a list of numbers and produces a sorted version:

; Lon -> Lon

; constructs a list from the items in l in descending order

(define (sort-> l0)

(local (; Lon -> Lon

(define (sort l)

(cond

[(empty? l) empty]

[else (insert (first l) (sort (rest l)))]))

; Number Lon -> Lon

(define (insert an l)

(cond

[(empty? l) (list an)]

[else

(cond

[(> an (first l)) (cons an l)]

[else (cons (first l) (insert an (rest l)))])])))

(sort l0)))

Create a test suite for sort->.

Design the function sort-<, which sorts lists of numbers in ascending order.

Create sort-a, which abstracts sort-> and sort-<. It consumes the comparison operation in addition to the list of numbers. Define versions sort-> and sort-< in terms of sort-a.

Use sort-a to define a function that sorts a list of strings by their lengths, both in descending and ascending order.

Later we will introduce several different ways to sort lists of numbers, all of them faster than sort-a. If you then change sort-a, all uses of sort-a will benefit.

6.1.3 Similarities in Data Definitions

To instantiate a data definition with two parameters, you need two names of data collections. Using Number and Image for the parameters of CP, you get [CP Number Image], which describes the collections of points that combine a number with an image. In contrast [CP Boolean String] combines Boolean values with strings in a point structure.

Exercise 191: Here are two strange but similar data definitions:

; A Nested-string is one of: ; – String ; – (make-layer Nested-string)

; A Nested-number is one of: ; – Number ; – (make-layer Nested-number)

Both data definitions exploit this structure definition:

(define-struct layer (stuff))

Both define nested forms of data’ one is about numbers and the other about strings. Make examples for both. Abstract over the two. Then instantiate the abstract definition to get back the originals.

Exercise 192: Take a look at this data definition:

; A [Bucket ITEM] is

;   (make-bucket N [List-of ITEM])

; interp. the n in (make-bucket n l) is the length of l

;   i.e., (= (length l) n) is always true

When you instantiate Bucket with String, IR, and Posn, you get three different data collections. Describe each of them with a sentence and with two distinct examples.

Now consider this instantiations:

; [Bucket [List-of [List-of String]]]

Construct three distinct pieces of data that belong to this collection.

6.1.4 Functions are Values

The functions of this section stretch our understanding of program evaluation. It is easy to understand how functions consume more than numbers, say strings, images, and Boolean values. Structures and lists are a bit of a stretch, but they are finite “things” in the end. Function-consuming functions, however, are strange. Indeed, these kind of functions violate the BSL grammar of the first intermezzo in two ways. First, the names of primitive operations and functions are used as arguments in applications. Second, parameters are used as if they were functions, that is, the first position of applications.

Spelling out the problem tells you how the ISL grammar differs from BSL’s. First, our expression language should include the names of functions and primitive operations in the definition. Second, the first position in an application should allow things other than function names and primitive operations; at a minimum, it must allow variables and function parameters. In anticipation of other uses of functions, we agree on allowing arbitrary expressions in that position.

The changes to the grammar seem to demand changes to the evaluation rules, but they don’t change at all. All that changes is the set of values. To accommodate functions as arguments of functions, the simplest change is to say that functions are values. Thus, we start using the names of functions and primitive operations as values; later we introduce another way to deal with functions as values.

Exercise 193: Assume the definitions area in DrRacket contains (define (f x) x). Identify the values among the following expressions:

1. (cons f empty)

2. (f f)

3. (cons f (cons 10 (cons (f 10) empty)))

Explain why they are values and why the remaining expressions are not values.

Exercise 194: Argue why the following sentences are now legal definitions:

1. (define (f x) (x 10))

2. (define (f x) (x f))

3. (define (f x y) (x 'a y 'b))

Explain your reasoning.

Exercise 195: Develop a-function=. The function determines whether two functions from numbers to numbers produce the same results for 1.2, 3, and -5.775.

Can we hope to define function=?, which determines whether two functions from numbers to numbers are equal?

6.2 Designing Abstractions

In essence, to abstract is to turn something concrete into a parameter. We have this several times in the preceding section. To abstract similar function definitions, you add parameters that replace concrete values in the definition. To abstract similar data definitions, you create parametric data definitions. When you will encounter other programming languages, you will see that their abstraction mechanisms also require the introduction of parameters, though they may not be function parameters.

6.2.1 Abstractions from Examples

When you first learned to add, you worked with concrete examples. Your parents probably taught you to use your fingers to add two small numbers. Later on, you studied how to add two arbitrary numbers; you were introduced to your first kind of abstraction. Much later still, you learned to formulate expressions that convert temperatures from Celsius to Fahrenheit or calculate the distance that a car travels at a certain speed in a given amount of time. In short, you went from very concrete examples to abstract relations.

This section introduces a design recipe for creating abstractions from examples. As the preceding section shows, creating abstractions is easy. We leave the difficult part to the next section where we show you how to find and use existing abstractions.

Exercise 196: Design tabulate, which is the abstraction of the following two functions:

; Number -> [List-of Number] ; tabulate sin between n ; and 0 (inclusive) in a list (define (tab-sin n)   (cond     [(= n 0) (list (sin 0))]     [else      (cons (sin n)            (tab-sin (sub1 n)))]))

; Number -> [List-of Number] ; tabulate sqrt between n ; and 0 (inclusive) in a list (define (tab-sqrt n)   (cond     [(= n 0) (list (sqrt 0))]     [else      (cons (sqrt n)            (tab-sqrt (sub1 n)))]))

When tabulate is properly designed, use it to define a tabulation function for sqr and tan.

Exercise 197: Design fold1, which is the abstraction of the following two functions:

; [List-of Number] -> Number ; compute the sum of ; the numbers on l (define (sum l)   (cond     [(empty? l) 0]     [else      (+ (first l)         (sum (rest l)))]))

; [List-of Number] -> Number ; compute the product of ; the numbers on l (define (product l)   (cond     [(empty? l) 1]     [else      (* (first l)         (product (rest l)))]))

Exercise 198: Design fold2, which is the abstraction of the following two functions:

; [List-of Number] -> Number (define (product l)   (cond     [(empty? l) 1]     [else      (* (first l)         (product (rest l)))]))

; [List-of Posn] -> Image (define (image* l)   (cond     [(empty? l) emt]     [else      (place-dot (first l)                 (image* (rest l)))]))   ; Posn Image -> Image (define (place-dot p img)   (place-image dot                (posn-x p) (posn-y p)                img))   ; graphical constants:     (define emt (empty-scene 100 100)) (define dot (circle 3 "solid" "red"))

Compare this exercise with exercise 197. Even though both involve the product function, this exercise poses an additional challenge because the second function, image*, consumes a list of Posns and produces an Image. Still, the solution is within reach of the material in this section, and it is especially worth comparing the solution with the one to the preceding exercise. The comparison yields interesting insights into abstract signatures.

Last but not least, when you are dealing with data definitions, the abstraction process proceed in an analogous manner. The extra parameters to data definitions stands for collections of values, and to testing means to spell out a data definition for some concrete examples. All in all, abstracting over data definitions tends to be easier than abstracting over functions, and so we leave it to you to adapt the design recipe appropriately.

6.2.2 Similarities in Signatures

As it turns out, a function’s signature is key to its reuse. Thus, to increase the usefulness of an abstract function, you must learn to formulate signatures that describes abstracts in their most general terms possible. To understand how this works, we start with a second look at signatures and from the simple—though possibly startling—insight that signatures are basically data definitions.

In general, the arrow notation of signatures is like the List-of notation from Similarities in Data Definitions. The latter consumes (the name of) one class of data, say X, and describes all lists of X items—without assigning it a name. The arrow notation consumes an arbitrary number of classes of data and describes collections of functions.

What this means is that the abstraction design recipe applies to signatures, too. You compare similar signatures; you highlight the differences; and then you replace those with parameters. But the process of abstracting signatures feels more complicated than the one for functions, partly because signature are already abstract pieces of the design recipe and partly because the arrow-based notation is much more complex than anything else we have encountered.

To make more progress on a signature for the abstraction of the two functions in exercise 198, we need to take the first two steps of the design recipe:

Exercise 199: Each of the following signatures describes a collection of functions:

; (Number -> Boolean)

; (Boolean String -> Boolean)

; (Number Number Number -> Number)

; (Number -> [List-of Number])

; ([List-of Number] -> Boolean)

Describe these collections with at least one example from ISL.

Exercise 200: Formulate signatures for the following functions:

• sort-n, which consumes a list of numbers and a function that consumes two numbers (from the list) and produces a Boolean; sort-n produces a sorted list of numbers.

• sort-s, which consumes a list of srings and a function that consumes two strings (from the list) and produces a Boolean; sort-s produces a sorted list of strings.

Then abstract over the two signatures, following the above steps. Also show that the generalized signature can be instantiated to describe the signature of a sort function for lists of IRs.

Exercise 201: Formulate signatures for the following functions:

• map-n, which consumes a list of numbers and a function from numbers to numbers to produce a list of numbers.

• map-s, which consumes a list of srings and a function from strings to strings and produces a list of strings.

Then abstract over the two signatures, following the above steps. Also show that the generalized signature can be instantiated to describe the signature of the map-IR function above.

6.2.3 Single Point of Control

In general, programs are like drafts of papers. Editing drafts is important to correct typos, to fix grammatical mistakes, to make the document consistent, and to eliminate repetitions. Nobody wants to read papers that repeat themselves a lot, and nobody wants to read such programs either.

The elimination of similarities in favor of abstractions has many advantages. Creating an abstraction simplifies definitions. It may also uncover problems with existing functions, especially when similarities aren’t quite right. But, the single most important advantage is the creation of single points of control for some common functionality.

Putting the definition for some functionality in one place makes it easy to maintain a program. When you discover a mistake, you have to go to just one place to fix it. When you discover that the code should deal with another form of data, you can add the code to just one place. When you figure out an improvement, one change improves all uses of the functionality. If you had made copies of the functions or code in general, you would have to find all copies and fix them; otherwise the mistake might live on or the only one of the functions would run faster.

We therefore formulate this guideline:

Creating Abstractions: Form an abstraction instead of copying and modifying any piece of a program.

Our design recipe for abstracting functions is the most basic tool to create abstractions. To use it requires practice. As you practice, you expand your capabilities to read, organize, and maintain programs. 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; in other courses on programming, you will encounter other forms of abstraction, most importantly inheritance in class-based object-oriented languages.

6.2.4 Abstractions from Templates

Over the course of the first two chapters, we have designed many functions using the same template. After all, the design recipe says to organize functions around the structure of the (major) input data definition. It is therefore not surprising that many function definitions look similar to each other.

6.3 Using Abstractions, Part I

Many programming languages provide a number of looping constructs, or loop for short. A loop processes a compound piece of data, one piece at a time. In our terminology a loop abstracts over the traversal of data and applies some given function to each of its pieces. You have encountered several such loops in the first two sections of this chapter: extract, fold1, map1, etc. These functions consume a function and apply it to each item on some list.

Once you have such loop abstractions, you should use them when possible. They create single points of control data, and they are a work-saving device. To make this precise, the use of an abstraction helps the reader of your code to understand your intentions, in particular if the abstraction is well-known and built into the language or comes with its standard libraries.

This section is all about the reuse of existing ISL abstractions. It starts with a section on existing ISL abstractions, some of which you have seen under false names. The remaining sections are about re-using such abstractions. One key ingredient is a new syntactic construct, local, for defining functions and variables (even structures) locally within a function. An auxiliary ingredient, introduced in the last section, is the lambda construct for creating nameless functions; lambda is a convenience but inessential to the idea of re-using abstract functions.

; [X] N (N -> X) -> [List-of X]

; construct a list by applying f to 0, 1, ..., (sub1 n)

;    (build-list f n) = (list (f 0) ... (f (- n 1)))

(define (build-list n f) ...)

; [X] (X -> Boolean) [List-of X] -> [List-of X]

; produce a list from all those items on alox for which p holds

(define (filter p alox) ...)

; [X] [List-of X] (X X -> Boolean) -> [List-of X]

; produce a variant of alox that is sorted according to cmp

(define (sort alox cmp) ...)

; [X Y] (X -> Y) [List-of X] -> [List-of Y]

; construct a list by applying f to each item on alox

;    (map f (list x-1 ... x-n)) = (list (f x-1) ... (f x-n))

(define (map f alox) ...)

; [X] (X -> Boolean) [List-of X] -> Boolean

; determine whether p holds for every item on alox

;    (andmap p (list x-1 ... x-n)) = (and (p x-1) ... (p x-n))

(define (andmap p alox) ...)

; [X] (X -> Boolean) [List-of X] -> Boolean

; determine whether p holds for at least one item on alox

;    (ormap p (list x-1 ... x-n)) = (or (p x-1) ... (p x-n))

(define (ormap p alox) ...)

; [X Y] (X Y -> Y) Y [List-of X] -> Y

; compute the result of applying f from right to left to all of

; alox and base, that is, apply f to

;    the last item in alox and base,

;    the penultimate item and the result of the first step,

;    and so on up to the first item

;    (foldr f base (list x-1 ... x-n)) = (f x-1 ... (f x-n base))

(define (foldr f base alox) ...)

; [X Y] (X Y -> Y) Y [List-of X] -> Y

; compute the result of applying f from left to right to all of

; alox and base, that is, apply f to

;    the first item in alox and base,

;    the second item and the result of the first step,

;    and so on up to the last item:

;    (foldl f base (list x-1 ... x-n)) = (f x-n ... (f x-1 base))

(define (foldl f base alox) ...)

WARNING: you cannot design build-list, build-string, or foldl with the design principles you know at this point; Accumulators covers the necessary ideas.

Figure 50: ISL's built-in abstract functions for list-processing