III Abstraction
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 places: the names of the classes 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.
Experience shows that these kinds of similarities are problematic. The
similarities come about because programmers—
Good programmers try to eliminate similarities as much as the programming language allows.A program is like an essay. The first version is a draft, and drafts demand editing. “Eliminate” implies that programmers write down their first drafts of programs, spot similarities (and other problems), and get rid of them. For the last step, they either abstract or use existing (abstract) functions. It often takes several iterations of this process to get the program into satisfactory shape.
The first half of this part shows how to abstract over similarities in functions and data definitions. Programmers also refer to the result of this process as an abstraction, conflating the name of the process and its result. The second half is about the use of existing abstractions and new language elements to facilitate this process. While the examples in this part are taken from the realm of lists, the ideas are universally applicable.
16 Similarities Everywhere
If you have solved only a fraction of the exercises in Arbitrarily Large Data, you know that many solutions look alike. As a matter of fact, the similarities may tempt you to copy the solution of one problem to create the solution for another one. But thou shall not steal code, not even your own. Instead, you must abstract over similar pieces of code and this chapter teaches you how to abstract.
Our means of avoiding similarities are specific to “Intermediate Student” or ISL for short. In DrRacket, choose “Intermediate Student” from the “How to Design Programs” submenu in the “Language” menu. Almost all other programming languages provide similar means; in objectoriented languages you may find additional abstraction mechanisms. Regardless, these mechanisms share the basic characteristics spelled out in this chapter, and thus the design ideas explained here apply in other contexts, too.
16.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 (containsdog? l) (cond [(empty? l) #false] [else (or (string=? (first l) "dog") (containsdog? (rest l)))]))
; Los > Boolean ; does l contain "cat" (define (containscat? l) (cond [(empty? l) #false] [else (or (string=? (first l) "cat") (containscat? (rest l)))]))
; String Los > Boolean ; determines whether l contains the string s (define (contains? s l) (cond [(empty? l) #false] [else (or (string=? (first l) s) (contains? s (rest l)))]))
; Los > Boolean ; does l contain "dog" (define (containsdog? l) (contains? "dog" l))
; Los > Boolean ; does l contain "cat" (define (containscat? l) (contains? "cat" l))
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 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 235. Use contains? to define functions that search for "atom", "basic", and "zoo", respectively.



Then abstract over them. Define the above two functions in terms of the abstraction as oneliners 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.
16.2 Different Similarities
Abstraction looks easy in the case of containsdog? and containscat?. 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 79. 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 ; select those numbers on l ; that are below t (define (small l t) (cond [(empty? l) '()] [else (cond [(< (first l) t) (cons (first l) (small (rest l) t))] [else (small (rest l) t)])]))
; Lon Number > Lon ; select those numbers on l ; that are above t (define (large l t) (cond [(empty? l) '()] [else (cond [(> (first l) t) (cons (first l) (large (rest l) t))] [else (large (rest l) t)])]))
The two functions differ 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.
(define (extract R l t) (cond [(empty? l) '()] [else (cond [(R (first l) t) (cons (first l) (extract R (rest l) t))] [else (extract R (rest l) t)])]))
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—
(checkexpect (extract < '() 5) (small '() 5)) (checkexpect (extract < '(3) 5) (small '(3) 5)) (checkexpect (extract < '(1 6 4) 5) (small '(1 6 4) 5))
; Lon Number > Lon (define (small1 l t) (extract < l t))
; Lon Number > Lon (define (large1 l t) (extract > l t))
; Number Number > Boolean ; is the area of a square with side x larger than c (define (squared>? x c) (> (* x x) c))
(extract squared>? (list 3 4 5) 10)
Exercise 237. Evaluate (squared>? 3 10), (squared>? 4 10), and (squared>? 5 10) in DrRacket.
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 containsdog? and containscat?, 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 singlepointofcontrol improvements work.
; Nelon > Number ; determines 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 ; determines 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))])]))
Exercise 238. Abstract the two functions in figure 80 into a single function: Both consume nonempty lists of numbers (Nelon) and produce a single number. The left one produces the smallest number in the list, the right one the largest.
(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)
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 inf2 and sup2, 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 Local Function Definitions.
16.3 Similarities in Data Definitions
; A Lon (Listofnumbers) is one of: ; – '() ; – (cons Number Lon)
; A Los (ListofString) is one of: ; – '() ; – (cons String Los)
[Listof Number] says that ITEM represents all numbers so the notation is just another name for Listofnumbers;
[Listof String] defines the same class of data as ListofString; and
 if we had identified a class of inventory records, like this:
(definestruct ir [name price]) ; An IR is a structure: ; (makeir String Number)
(definestruct point [hori veri])
; A Pairbooleanstring is a structure: ; (makepoint Boolean String)
; A Pairnumberimage is a structure: ; (makepoint Number Image)
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.
; A Nestedstring is one of: ; – String ; – (makelayer Nestedstring)
; A Nestednumber is one of: ; – Number ; – (makelayer Nestednumber)
(definestruct layer [stuff])
Exercise 241. Compare and contrast the data definitions for NEListoftemperatures and NEListofBooleans. Then formulate an abstract data definition NEListof.
; A [Bucket ITEM] is a structure: ; (makebucket N [Listof ITEM]) ; interpretation (makebucket n l) combines the length ; n of some list l with the list itself ; that is, (= (length l) n) is always true
; String [Listof String] > [Maybe [Listof String]] ; returns the remainder of the list los if it contains s ; #false otherwise (checkexpect (occurs "a" (list "b" "a" "d")) (list "d")) (checkexpect (occurs "a" (list "b" "c" "d")) #f) (define (occurs s los) los)
16.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. Functionconsuming 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 246. Develop function=at1.23and5.775?. The function determines whether two functions from numbers to numbers produce the same results for 1.2, 3, and 5.775.
Mathematicians say that two functions are equal if they compute the same
result when given the same input—
Can we hope to define function=?, which determines whether two functions from numbers to numbers are equal? If so, define the function. If not, explain why and consider the implication that you have encountered the first easily definable idea for which you cannot define a function.
16.5 Computing with Functions
The switch from BSL+ to ISL allows the use of functions as values, that is, as arguments to functions, as results, as items in lists, and so on. In function applications, the first position is now just an expression and DrRacket evaluates this expression like all others. Naturally, it expects a function as a result. Surprisingly, a liberal interpretation of the laws of algebra suffices to evaluate programs in ISL.
(extract < '() 5) == '()
== (cond [(empty? '()) '()] [else (cond [(< (first '()) t) (cons (first '()) (extract < (rest '()) 5))] [else (extract < (rest '()) 5)])]) == (cond [#true '()] [else (cond [(< (first '()) t) (cons (first '()) (extract < (rest '()) 5))] [else (extract < (rest '()) 5)])]) == '()
(extract < (cons 4 '()) 5) == (cond [(empty? (cons 4 '())) '()] [else (cond [(< (first (cons 4 '())) 5) (cons (first (cons 4 '())) (extract < (rest (cons 4 '())) 5))] [else (extract < (rest (cons 4 '())) 5)])])
(cond [(empty? (cons 4 '())) '()] [else (cond [(< (first (cons 4 '())) 5) (cons (first (cons 4 '())) (extract < (rest (cons 4 '())) 5))] [else (extract < (rest (cons 4 '())) 5)])]) == (cond [#false '()] [else (cond [(< (first (cons 4 '())) 5) (cons (first (cons 4 '())) (extract < (rest (cons 4 '())) 5))] [else (extract < (rest (cons 4 '())) 5)])]) == (cond [(< (first (cons 4 '())) 5) (cons (first (cons 4 '())) (extract < (rest (cons 4 '())) 5))] [else (extract < (rest (cons 4 '())) 5)]) == (cond [(< 4 5) (cons (first (cons 4 '())) (extract < (rest (cons 4 '())) 5))] [else (extract < (rest (cons 4 '())) 5)])
== (cond [#true (cons (first (cons 4 '())) (extract < (rest (cons 4 '())) 5))] [else (extract < (rest (cons 4 '())) 5)]) == (cons 4 (extract < (rest (cons 4 '())) 5)) == (cons 4 (extract < '() 5)) == (cons 4 '())
(extract < (cons 6 (cons 4 '())) 5) == (extract < (cons 4 '()) 5) == (cons 4 (extract < '() 5)) == (cons 4 '())
(extract squared>? (list 3 4 5) 10) ==
(1)
== (cond [(empty? (list 3 4 5)) '()] [else (cond [(squared>? (first (list 3 4 5)) 10) (cons (first (list 3 4 5)) (extract squared>? (rest (list 3 4 5)) 10))] [else (extract squared>? (rest (list 3 4 5)) 10)])])
(2)
... == (cond [(squared>? 3 10) (cons (first (list 3 4 5)) (extract squared>? (rest (list 3 4 5)) 10))] [else (extract squared>? (rest (list 3 4 5)) 10)])
(3)
== (cond [(> (* 3 3) 10) (cons (first (list 3 4 5)) (extract squared>? (rest (list 3 4 5)) 10))] [else (extract squared>? (rest (list 3 4 5)) 10)])
(4)
== (cond [(> 9 10) (cons (first (list 3 4 5)) (extract squared>? (rest (list 3 4 5)) 10))] [else (extract squared>? (rest (list 3 4 5)) 10)])
(5)
== (cond [#false (cons (first (list 3 4 5)) (extract squared>? (rest (list 3 4 5)) 10))] [else (extract squared>? (rest (list 3 4 5)) 10)])
(6)
... == (extract squared>? (rest (list 3 4 5)) 10)
(7)
Exercise 247. Use DrRacket’s stepper to fill in the gaps between the steps in this last calculation. Pay attention to how the stepper deals with functions as arguments and how it retains 4.
> (extract squared>? (list 3 4 5) 10) (list 4 5)
17 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.
17.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.
; Listofnumbers > Listofnumbers ; converts a list of Celsius ; temperatures to Fahrenheit (define (cf* l) (cond [(empty? l) '()] [else (cons (C2F (first l)) (cf* (rest l)))]))
; Inventory > Listofstrings ; extracts the names of toys ; from an inventory (define (names i) (cond [(empty? i) '()] [else (cons (IRname (first i)) (names (rest i)))]))
; Number > Number ; converts one Celsius ; temperature to Fahrenheit (define (C2F c) (+ (* 9/5 c) 32))
(definestruct IR [name price]) ; An IR is a structure: ; (makeIR String Number) ; An Inventory is one of: ; – '() ; – (cons IR Inventory)
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.
Step 1 is to compare two items for similarities.
When you find two function definitions that are almost the same except for their namesThe recipe requires a substantial modification for abstracting over nonvalues. and some values at a few analogous places, compare them, mark the differences. If the two definitions differ in more than one place, connect the corresponding differences with a line or a comment.
Figure 82 shows a pair of similar function definitions:. The two functions apply a function to each item in a list. They differ only as to which function they apply to each item. The two highlights emphasize this essential difference. They also differ in two inessential ways: the names of the function and the names of the parameters.
Next we abstract. To abstract means to replace the contents of corresponding code highlights with new names and add these names to the parameter list. For our running example, we obtain the following pair of functions after replacing the differences with g:
(define (cf* l g) (cond [(empty? l) '()] [else (cons (g (first l)) (cf* (rest l) g))])) (define (names i g) (cond [(empty? i) '()] [else (cons (g (first i)) (names (rest i) g))])) This first change eliminates the essential difference. Now each function traverses a list and applies some given function to each item.The inessential differences—
the names of the functions and occasionally the names of some parameters— are easy to eliminate. Indeed, if you have explored DrRacket, you know that check syntax allows you to do this systematically and easily: (define (map1 k g) (cond [(empty? k) '()] [else (cons (g (first k)) (map1 (rest k) g))])) (define (map1 k g) (cond [(empty? k) '()] [else (cons (g (first k)) (map1 (rest k) g))])) We choose to use map1 for the name of the function and k for the name of the list parameter. No matter which names you choose, the result is two identical function definitions.Our example is simple. In many cases, you will find that there is more than just one pair of differences. The key is to find pairs of differences. When you mark up the differences on paper and pencil, connect related boxes with a line. Then introduce one additional parameter per line. And don’t forget to change all recursive uses of the function so that the additional parameters go along for the ride.
Now we must validate that the new function is a correct abstraction of the original pair of functions. To validate means to test, which here means to define the two original functions in terms of the abstraction.
Thus suppose that one original function is called foriginal and consumes one argument and that the abstract function is called abstract. If foriginal differs from the other concrete function in the use of one value, say, val, the following function definition(define (ffromabstract x) (abstract x val)) introduces the function ffromabstract, which should be equivalent to foriginal. That is, for every proper value V, (ffromabstract V) should produce the same answer as (foriginal V). This is particularly true for all values that your tests for foriginal use. So reformulate and rerun those tests for ffromabstract and make sure they succeed.Let us return to our running example:; Listofnumbers > Listofnumbers (define (cf*frommap1 l) (map1 l C2F)) ; Inventory > Listofstrings (define (namesfrommap1 i) (map1 i IRname)) A complete example would include some tests, and thus we can assume that both cf* and names come with some tests:(checkexpect (cf* (list 100 0 40)) (list 212 32 40)) (checkexpect (names (list (makeIR "doll" 21.0) (makeIR "bear" 13.0))) (list "doll" "bear")) To ensure that the functions defined in terms of map1 work properly, you can copy the tests and change the function names appropriately:(checkexpect (cf*frommap1 (list 100 0 40)) (list 212 32 40)) (checkexpect (namesfrommap1 (list (makeIR "doll" 21.0) (makeIR "bear" 13.0))) (list "doll" "bear")) To make a new abstraction useful, it needs a signature. As Using Abstractions explains, reuse of abstract functions start with their signatures. Finding useful signatures is, however, a serious problem. For now we just use the running example to illustrate the problem. Similarities in Signatures below resolves the issue.
So consider the problem of finding a signature for map1. On the one hand, if you view map1 as an abstraction of cf*, you might think the signature is; Listofnumbers [Number > Number] > Listofnumbers
That is, the original signature extended with one signature for functions:Since the additional parameter for map1 is a function, the use of a function signature shouldn’t surprise you. This function signature is also quite simple; it is a “name” for all the functions from numbers to numbers. Here C2F is such a function, and so are add1, sin, and imagpart.On the other hand, if you view map1 as an abstraction of names, the signature is quite different:; Inventory [IR > String] > Listofstrings
This time the additional parameter is IRname, which is a selector function that consumes IRs and produces Strings. But clearly this second signature would be useless in the first case, and vice versa. To accommodate both cases, the signature for map1 must express that Number, IR, and String are coincidental.Also concerning signatures, you are probably eager to use Listof by now. It is clearly easier to write [Listof IR] than spelling out a data definition for Inventory. So yes, as of now, we use Listof when it is all about lists and you should too.
; Listofnumbers > Listofnumbers (define (add1toeach l) (map1 l add1))
; Number > [Listof Number] ; tabulates sin between n ; and 0 (inclusive) in a list (define (tabsin n) (cond [(= n 0) (list (sin 0))] [else (cons (sin n) (tabsin (sub1 n)))]))
; Number > [Listof Number] ; tabulates sqrt between n ; and 0 (inclusive) in a list (define (tabsqrt n) (cond [(= n 0) (list (sqrt 0))] [else (cons (sqrt n) (tabsqrt (sub1 n)))]))
; [Listof Number] > Number ; computes the sum of ; the numbers on l (define (sum l) (cond [(empty? l) 0] [else (+ (first l) (sum (rest l)))]))
; [Listof Number] > Number ; computes the product of ; the numbers on l (define (product l) (cond [(empty? l) 1] [else (* (first l) (product (rest l)))]))
; [Listof Number] > Number (define (product l) (cond [(empty? l) 1] [else (* (first l) (product (rest l)))]))
; [Listof Posn] > Image (define (image* l) (cond [(empty? l) emt] [else (placedot (first l) (image* (rest l)))])) ; Posn Image > Image (define (placedot p img) (placeimage dot (posnx p) (posny p) img)) ; graphical constants: (define emt (emptyscene 100 100)) (define dot (circle 3 "solid" "red"))
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 testing means spelling 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.
17.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—
In general, the arrow notation of signatures is like the
Listof 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—
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 arrowbased notation is much more complex than anything else we have encountered.
Since listing the parameters of a signature is extra work for our purposes, we simply say that from now on all variables in signatures are parameters. Other programming languages, however, insist on explicitly listing the parameters of signatures, but in return you can articulate additional constraints in such signatures and the signatures are checked before you run the program.
both signatures describe oneargument functions;
both argument descriptions employ the Listof construction;
To make more progress on a signature for the abstraction of the two functions in exercise 254, we need to take the first two steps of the design recipe:
(define (pr* l bs jn) (cond [(empty? l) bs] [else (jn (first l) (pr* (rest l) bs jn))]))
(define (im* l bs jn) (cond [(empty? l) bs] [else (jn (first l) (im* (rest l) bs jn))]))
; [Listof X] Y [X Y > Y] > Y
Given two similar function definitions, f and g, compare their signatures for similarities and differences. The goal is to discover the organization of the signature and to mark the places where one signature differs from the other. Connect the differences as pairs just like you do when you analyze function bodies.
Abstract f and g into fabs and gabs. That is, add parameters that eliminate the differences between f and g. Create signatures for fabs and gabs. Keep in mind what the new parameters originally stood for; this helps you figure out the new pieces of the signatures.
Check whether the analysis of step 1 extends to the signatures of fabs and gabs. If so, replace the differences with variables that range over classes of data. Once the two signatures are the same you have a signature for the abstracted function.
 Test the abstract signature in two ways. First, ensure that suitable substitutions of the variables in the abstract signature yield the signatures of fabs and gabs. Second, check that the generalized signature is in sync with the code. For example, if p is a new parameter and its signature is
; ... [A B > C] ....
then p should always be applied to two arguments, the first one from A and the second one from B. And the result of an application of p is going to be a C and should be used where elements of C are expected.
; [Number > Boolean] ; [Boolean String > Boolean] ; [Number Number Number > Number] ; [Number > [Listof Number]] ; [[Listof Number] > Boolean]
sortn, which consumes a list of numbers and a function that consumes two numbers (from the list) and produces a Boolean; sortn produces a sorted list of numbers.
sorts, which consumes a list of strings and a function that consumes two strings (from the list) and produces a Boolean; sorts produces a sorted list of strings.
mapn, which consumes a list of numbers and a function from numbers to numbers to produce a list of numbers.
maps, which consumes a list of strings and a function from strings to strings and produces a list of strings.
17.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.
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 classbased objectoriented languages.
17.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 organization of the (major) input data definition. It is therefore not surprising that many function definitions look similar to each other.
; [Listof X] Y [X Y > Y] > Y (define (reduce l base combine) (cond [(empty? l) base] [else (combine (first l) (reduce (rest l) base combine))]))
; [Listof Number] > Number (define (sum lon) (reduce lon 0 +))
; [Listof Number] > Number (define (product lon) (reduce lon 1 *))
18 Using Abstractions
Once you have abstractions, you should use them when possible. They create single points of control, and they are a worksaving device. More precisely, the use of an abstraction helps readers of your code to understand your intentions. If the abstraction is wellknown and built into the language or comes with its standard libraries, it signals more clearly what your function does than customdesigned code.
This chapter 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 reusing such abstractions. One key ingredient is a new syntactic construct, local, for defining functions and variables (and even structure types) 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 reusing abstract functions.
; N [N > X] > [Listof X] ; constructs a list by applying f to 0, 1, ..., (sub1 n) ; (buildlist n f) == (list (f 0) ... (f ( n 1))) (define (buildlist n f) ...) ; [X > Boolean] [Listof X] > [Listof X] ; produces a list from all those items on alox for which p holds (define (filter p alox) ...) ; [Listof X] [X X > Boolean] > [Listof X] ; produces a version of alox that is sorted according to cmp (define (sort alox cmp) ...) ; [X > Y] [Listof X] > [Listof Y] ; constructs a list by applying f to each item on alox ; (map f (list x1 ... xn)) == (list (f x1) ... (f xn)) (define (map f alox) ...) ; [X > Boolean] [Listof X] > Boolean ; determines whether p holds for every item on alox ; (andmap p (list x1 ... xn)) == (and (p x1) ... (p xn)) (define (andmap p alox) ...) ; [X > Boolean] [Listof X] > Boolean ; determines whether p holds for at least one item on alox ; (ormap p (list x1 ... xn)) == (or (p x1) ... (p xn)) (define (ormap p alox) ...) ; [X Y > Y] Y [Listof X] > Y ; applies f from right to left to each item in alox and base ; (foldr f base (list x1 ... xn)) == (f x1 ... (f xn base)) (define (foldr f base alox) ...) ; [X Y > Y] Y [Listof X] > Y ; applies f from left to right to each item in alox and base ; (foldl f base (list x1 ... xn)) == (f xn ... (f x1 base)) (define (foldl f base alox) ...)
18.1 Existing Abstractions
> (buildlist 3 add1) (list 1 2 3)
> (filter odd? (list 1 2 3 4 5)) (list 1 3 5)
> (sort (list 3 2 1 4 5) >) (list 5 4 3 2 1)
> (map add1 (list 1 2 2 3 3 3)) (list 2 3 3 4 4 4)
(foldr + 0 '(1 2 3 4 5)) == (+ 1 (+ 2 (+ 3 (+ 4 (+ 5 0))))) == (+ 1 (+ 2 (+ 3 (+ 4 5)))) == (+ 1 (+ 2 (+ 3 9))) == (+ 1 (+ 2 12)) == (+ 1 14) == 15
(foldl + 0 '(1 2 3 4 5)) == (+ 5 (+ 4 (+ 3 (+ 2 (+ 1 0))))) == (+ 5 (+ 4 (+ 3 (+ 2 1)))) == (+ 5 (+ 4 (+ 3 3))) == (+ 5 (+ 4 6)) == (+ 5 10) == 15
; [X > Number] [Listof X] > X ; finds the (first) item in alox that maximizes f, that is: ; if (argmax f (list x1 ... xn)) == xi, ; then (>= (f xi) (f x1)), (>= (f xi) (f x2)), and so on (define (argmax f alox) ...) ; [X > Number] [Listof X] > X ; finds the (first) item in alox that minimizes f, that is: ; if (argmin f (list x1 ... xn)) == xi, ; then (<= (f xi) (f x1)), (<= (f xi) (f x2)), and so on (define (argmin f alox) ...)
(definestruct address [firstname lastname street]) ; An Addr is a structure: ; (makeaddress String String String) ; interpretation associates a street address with a person's name ; [Listof Addr] > String ; creates a string of first names, sorted in alphabetical order, ; separated and surrounded by blank spaces (define (listing l) (foldr stringappendwithspace " " (sort (map addressfirstname l) string<?))) ; String String > String ; concatenates two strings and prefixes with space (define (stringappendwithspace s t) (stringappend " " s t)) (define ex0 (list (makeaddress "Matthias" "Fellson" "Sunburst") (makeaddress "Robert" "Findler" "South") (makeaddress "Matthew" "Flatt" "Canyon") (makeaddress "Shriram" "Krishna" "Yellow"))) (checkexpect (listing ex0) " Matthew Matthias Robert Shriram ")
Figure 84 illustrates the power of composing the functions from figure 83. Its main function is listing. The purpose is to create a string from a list of addresses. More precisely, the expected result is a string that represents a sorted list of first names, separated and surrounded by blank spaces.
design a function that extracts the first names from the given list of Addr;
design a function that sorts these names in alphabetical order;
design a function that concatenates the strings from step 2.
(map addressfirstname l)
; [X Y > Y] Y [Listof X] > Y ; myfoldl works just like foldl (checkexpect (myfoldl cons '() '(a b c)) (foldl cons '() '(a b c))) (checkexpect (myfoldl / 1 '(6 3 2)) (foldl / 1 '(6 3 2))) (define (myfoldl f e l) (foldr f e (reverse l)))
Design mybuildlist, which works just like buildlist. Hint Recall the addatend function from exercise 193. Note on Design Accumulators covers the concepts that you need to design these functions properly.
18.2 Local Function Definitions
Take a second look at figure 84. The stringappendwithspace function clearly plays a subordinate role and has no use outside of this narrow context. Almost all programming languages support some way for stating this relationship as a part of the program. The idea is called a local definition, sometimes also a private definition. In ISL, local expressions introduce locally defined functions, variables, and structure types, and this section introduces the mechanics of local.
; [Listof Addr] > String ; creates a string of first names, sorted in alphabetical order, ; separated and surrounded by blank spaces (define (listing.v2 l) (local (; String String > String ; concatenates two strings and prefixes with space (define (stringappendwithspace s t) (stringappend " " s t))) ; — IN — (foldr stringappendwithspace " " (sort (map addressfirstname l) string<?))))
In this example, the sequence of definitions consists of a single function definition, the one for stringappendwithspace. The body of local is the body of the original listing function. Its reference to stringappendwithspace is now resolved locally, that is, there is no need to look in the global sequence of definitions. Conversely, outside of the local expression, it is impossible to refer to stringappendwithspace. Since there is no such reference in the original program, it remains intact and you can confirm this with the test suite.
; [Listof Number] [Number Number > Boolean] > [Listof Number] (define (sortcmp alon0 cmp) (local (; [Listof Number] > [Listof Number] ; produces a variant of alon sorted by cmp (define (isort alon) (cond [(empty? alon) '()] [else (insert (first alon) (isort (rest alon)))])) ; Number [Listof Number] > [Listof Number] ; inserts n into the sorted list of numbers alon (define (insert n alon) (cond [(empty? alon) (cons n '())] [else (if (cmp n (first alon)) (cons n alon) (cons (first alon) (insert n (rest alon))))]))) (isort alon0)))
(define (listing.v3 l) (local (; String String > String ; concatenates two strings and prefixes with space (define (stringappendwithspace s t) (stringappend " " s t)) (define firstnames (map addressfirstname l)) (define sortednames (sort firstnames string<?))) ; — IN — (foldr stringappendwithspace " " sortednames)))
For a second example, consider figure 85. The organization of this definition tells the reader that sortcmp needs two auxiliary functions: isort and insert. Note the reference to cmp in the latter, which tells the reader that the comparison function remains the same for the entire sorting process.
By making insert local, it also becomes impossible to abuse
insert. Reread its purpose statement. The adjective “sorted”
means that a program should use insert only if the second
argument is already sorted. As long as insert is defined at the
toplevel, nothing guarantees that insert is always used
properly. Once its definition is local to the sortcmp function,
the proper use is guaranteed—
Exercise 260. Use a local expression to organize the functions for drawing a polygon in figure 68. If a globally defined functions is widely useful, do not make it local.
Exercise 261. Use a local expression to organize the functions for rearranging words from Word Games, the Heart of the Problem.
; Nelon > Number ; determines the smallest number on l (define (inf l) (cond [(empty? (rest l)) (first l)] [else (local ((define smallestinrest (inf (rest l)))) (cond [(< (first l) smallestinrest) (first l)] [else smallestinrest]))])) Figure 86: Using local to improve performance
For a final example, let us take a look at the inf function from figure 80. Using local to improve this function’s performance yields the definition in figure 86. Here the local expression shows up in the middle of a cond expression. It also doesn’t define a function but a variable whose initial value is the result of a natural recursion. Now recall that the evaluation of a local expression evaluates the definitions once and for all before the body is evaluated. What this means here is that (inf (rest l)) is evaluated once, but the body of the local expression refers to the result twice. Put differently, the use of local saves the reevaluation of (inf (rest l)) at each stage in the computation. To confirm this insight, reevaluate the above version of inf on the inputs suggested in exercise 238.
; Inventory > Inventory ; creates an Inventory from aninv for all ; those items that cost less than $1 (define (extract1 aninv) (cond [(empty? aninv) '()] [else (cond [(<= (irprice (first aninv)) 1.0) (cons (first aninv) (extract1 (rest aninv)))] [else (extract1 (rest aninv))])]))
; 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) '()] [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)))
Design the function sort<, which sorts lists of numbers in ascending order.
Create sorta, 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 sorta.
Use sorta to define functions that sort lists of strings by their lengths: one for ascending order and another one in descending order.
Later we will introduce several different ways to sort lists of numbers, all of them faster than sorta. If you then change sorta, all uses of sorta will benefit.
18.3 ... Add Expressive Power
The third and last example illustrates how local adds expressive power to BSL and BSL+. Finite State Machines presents the design of a world program that simulates how a finite state machine recognizes sequences of key strokes. While the data analysis leads in a natural manner to the data definitions in figure 76, an attempt to design the main function of the world program fails. Specifically, even though the given finite state machine remains the same over the course of the simulation, the state of the world must include it so that the program can transition from one state to the next when the player presses a key.
; FSM FSMState > FSMState ; match the keys pressed by a player with the given FSM (define (simulate fsm s0) (local (; State of the World: FSMState ; FSMState KeyEvent > FSMState ; finds the next state in the transition table of fsm0 (define (findnextstate s keyevent) (find fsm s))) ; NOW LAUNCH THE WORLD (bigbang s0 [todraw stateascoloredsquare] [onkey findnextstate]))) ; FSMState > Image ; renders current state as colored square (define (stateascoloredsquare s) (square 100 "solid" s)) ; FSM FSMState > FSMState ; finds the state matching current in the given transition table (fsm) (define (find transitions current) (cond [(empty? transitions) (error "not found")] [else (local ((define s (first transitions))) (if (state=? (transitioncurrent s) current) (transitionnext s) (find (rest transitions) current)))]))
Figure 87 shows an ISL solution to the problem. It
uses local function definitions and can thus equate the state of
the world with the current state of the finite state
machine. Specifically, simulate locally defines the key event
handler, which consumes only the current state of the world and the
KeyEvent that represents the player’s key stroke. Because this
locally defined function can refer to the given finite state machine
fsm, it is possible to find the next state in the transition
table—
As the figure also shows, all other functions are defined in parallel to the main function. This includes the function find, which performs the actual search in the transition table. The key improvement over BSL is that a locally defined function can reference both parameters to the function and globally defined auxiliary functions.
In short, this program organization signals to a future reader exactly the insights that the data analysis stage of the design recipe for world programs finds. First, the given representation of the finite state machine remains unchanged. Second, what changes over the course of the simulation is the current state of the finite machine.
The lesson is that the chosen programming language affects a programmer’s ability to express solutions, and a future reader’s ability to recognize the design insight of the original creator.
18.4 Computing with local
(define (simulate fsm s0) (local ((define (findnextstate s keyevent) (find fsm s))) (bigbang s0 [todraw stateascoloredsquare] [onkey findnextstate])))
(simulate ANFSM ASTATE)
== (local ((define (findnextstate s keyevent) (find ANFSM ASTATE))) (bigbang ASTATE [todraw stateascoloredsquare] [onkey findnextstate]))
== (local ((define (findnextstate1 s keyevent) (find anfsm astate))) (bigbang s0 [todraw stateascoloredsquare] [onkey findnextstate1]))
We use to indicate the step produces two pieces.
== (define (findnextstate1 s keyevent) (find anfsm astate)) (bigbang s0 [todraw stateascoloredsquare] [onkey findnextstate1])
(inf (list 2 1 3)) == 1
(inf (list 2 1 3)) == (cond [(empty? (rest (list 2 1 3))) (first (list 2 1 3))] [else (local ((define smallestinrest (inf (rest (list 2 1 3))))) (cond [(< (first (list 2 1 3)) smallestinrest) (first (list 2 1 3))] [else smallestinrest]))])
... == (local ((define smallestinrest (inf (rest (list 2 1 3))))) (cond [(< (first (list 2 1 3)) smallestinrest) (first (list 2 1 3))] [else smallestinrest]))
== (define smallestinrest1 (inf (rest (list 2 1 3)))) (cond [(< (first (list 2 1 3)) smallestinrest1 3) (first (list 2 1 3))] [else smallestinrest1])
== (define smallestinrest1 (cond [(empty? (rest (list 1 3))) (first (list 1 3))] [else (local ((define smallestinrest (inf (rest (list 1 3))))) (cond [(< (first (list 1 3)) smallestinrest) (first (list 1 3))] [else smallestinrest]))])) (cond [(< (first (list 2 1 3)) smallestinrest1) (first (list 2 1 3))] [else smallestinrest1])
(define smallestinrest1 (local ((define smallestinrest (inf (rest (list 1 3))))) (cond [(< (first (list 1 3)) smallestinrest) (first (list 1 3))] [else smallestinrest]))) (cond [(< (first (list 2 1 3)) smallestinrest3) (first (list 2 1 3))] [else smallestinrest3])
== (define smallestinrest2 (inf (rest (list 1 3)))) (define smallestinrest2 (cond [(< (first (list 1 3)) smallestinrest2) (first (list 1 3))] [else smallestinrest2])) (cond [(< (first (list 2 1 3)) smallestinrest2) (first (list 2 1 3))] [else smallestinrest2])
For the rest of the calculation, see figure 88; it omits the very last step, which would require replacing the name of a constant with its value. The exercises request that you explore this example some more.
(inf (list 2 1 3))
(1)
... == (define smallestinrest2 (cond [(empty? (rest (list 3))) (first (list 3))] [else (local ((define smallestinrest (inf (rest (list 3))))) (cond [(< (first (list 3)) smallestinrest) (first (list 3))] [else smallestinrest]))])) (define smallestinrest1 (cond [(< (first (list 1 3)) smallestinrest2) (first (list 1 3))] [else smallestinrest2])) (cond [(< (first (list 2 1 3)) smallestinrest1) (first (list 2 1 3))] [else smallestinrest1])
(2)
== (define smallestinrest2 3) (define smallestinrest1 (cond [(< (first (list 1 3)) smallestinrest2) (first (list 1 3))] [else smallestinrest2])) (cond [(< (first (list 2 1 3)) smallestinrest1) (first (list 2 1 3))] [else smallestinrest1])
(3)
== (define smallestinrest2 3) (define smallestinrest1 1) (cond [(< (first (list 2 1 3)) smallestinrest1) (first (list 2 1 3))] [else smallestinrest1])
(4)
== (define smallestinrest2 3) (define smallestinrest1 1) smallestinrest1
(5)
Figure 88: Computing with local
Exercise 265. Use DrRacket’s stepper to fill in the gaps in the calculation for inf, say, between step 2 and 3 in figure 88.
(sup (list 2 1 3))
((local ((define (f x) (+ (* 4 (sqr x)) 3))) f) 1) == ((local ((define (f1 x) (+ (* 4 (sqr x)) 3))) f1) 1) == (define (f1 x) (+ (* 4 (sqr x)) 3)) (f1 1)
Exercise 267. Use DrRacket’s stepper to fill in any gaps in the above calculation.
18.5 Using Abstractions, by Example
Sample Problem Design the function add3toall. The function consumes a list of Posns and adds 3 to the xcoordinates of each of them.
; [Listof Posn] > [Listof Posn] ; adds 3 to each xcoordinate on the given list (checkexpect (add3toall (list (makeposn 30 10) (makeposn 0 0))) (list (makeposn 33 10) (makeposn 3 0))) (define (add3toall lop) '())
At this point, we stop and ask what kind of function we are dealing with. Clearly, add3toall is clearly a listprocessing function. The question is whether it is like any of the functions in figure 83. The signature tells us that add3toall is a listprocessing function that consumes and produces a list. In figure 83, we have several functions with similar signatures: map, filter, and sort.
The purpose statement and example also tell you that add3toall
deals with each Posn separately and assembles the results into a
single list. Some reflection says that also confirms that the resulting
list contains as many items as the given list. All this thinking points
to one function—
; [Listof Posn] > [Listof Posn] ; adds 3 to each xcoordinate on the given list (checkexpect (add3toall (list (makeposn 30 10) (makeposn 0 0))) (list (makeposn 33 10) (makeposn 3 0))) (define (add3toall lop) (local (; Posn > Posn ; ... (define (afunfromposntoposn p) ... p ...)) (map afunfromposntoposn lop)))
(add3toall (list (makeposn 30 10) (makeposn 0 0))) == (map afun (list (makeposn 30 10) (makeposn 0 0))) == (list (afun (makeposn 30 10)) (afun (makeposn 0 0)))
; [Listof Posn] > [Listof Posn] ; adds 3 to each xcoordinate on the given list (checkexpect (add3toall (list (makeposn 30 10) (makeposn 0 0))) (list (makeposn 33 10) (makeposn 3 0))) (define (add3toall lop) (local (; Posn > Posn ; adds 3 to the xcoordinate of the given Posn (define (add3toone p) (makeposn (+ (posnx p) 3) (posny p)))) (map add3toone lop)))
Sample Problem Design a function that eliminates all Posns from a list that have a ycoordinate of larger than 100.
; [Listof Posn] > [Listof Posn] ; eliminates Posns whose ycoordinate is larger than 100 (checkexpect (keepgood (list (makeposn 0 110) (makeposn 0 60))) (list (makeposn 0 60))) (define (keepgood lop) '())
; [Listof Posn] > [Listof Posn] ; eliminates Posns whose ycoordinate is larger than 100 (checkexpect (keepgood (list (makeposn 0 110) (makeposn 0 60))) (list (makeposn 0 60))) (define (keepgood lop) (local (; Posn > Boolean ; should this Posn stay on the list (define (good? p) #true)) (filter good? lop)))
Before you read on, analyze the signature of filter and keepgood and determine why the helper function consumes individual Posns and produces Booleans.
; [Listof Posn] > [Listof Posn] ; eliminates Posns whose ycoordinate is larger than 100 (checkexpect (keepgood (list (makeposn 0 110) (makeposn 0 60))) (list (makeposn 0 60))) (define (keepgood lop) (local (; Posn > Posn ; should this Posn stay on the list (define (good? p) (not (> (posny p) 100)))) (filter good? lop)))
Sample Problem Design a function that determines whether any of a list of Posns is close to some given position pt where “close” means a distance of at most 5 pixels.
; Posn Posn Number > Boolean ; is the distance between p and q less than d (define (closeto p q d) ...)
; [Listof Posn] Posn > Boolean ; is any Posn on lop close to pt (checkexpect (close? (list (makeposn 47 54) (makeposn 0 60)) (makeposn 50 50)) #true) (define (close? lop pt) #false)
The Boolean range also gives away a clue with respect to
figure 83. Only two functions in this list produce
Boolean values—
; [Listof Posn] Posn > Boolean (define (close? lop pt) (local (; Posn > Boolean ; ... (define (isoneclose? p) ...)) (ormap closeto? lop)))
; [Listof Posn] > Boolean (define (close? lop pt) (local (; Posn > Boolean ; is one shot close to pt (define (isoneclose? p) (closeto p pt CLOSENESS))) (ormap isoneclose? lop))) (define CLOSENESS 5) ; in terms of pixels
18.6 Designing with Abstractions
Step 1 is to follow the design recipe for functions for three steps. Specifically, you should distill the problem statement into a signature, a purpose statement, an example, and a stub definition.
Consider the problem of defining a function that places small red circles on a 200 by 200 canvas for a given list of Posns. The first three steps design recipe yield this much:; [Listof Posn] > Image ; adds the Posns on lop to the empty scene (checkexpect (dots (list (makeposn 12 31))) (placeimage DOT 12 32 BACKGROUND)) (define (dots lop) BACKGROUND) ; graphical constants (define BACKGROUND (emptyscene 200 200)) (define DOT (circle 5 "solid" "red")) Next we exploit the signature and purpose statement to find a matching abstraction. To match means to pick an abstraction whose purpose is more general than the one for the function to be designed; it also means that the signatures are related. It is often best to start with the desired output and to find an abstraction that has the same or a more general output.
For our running example, the desired output is an Image. While none of the available abstractions produces an image, two of them have a variable to the right ofWrite down a template. For the reuse of abstractions a template uses local for two different purposes. The first one is to note which abstraction to use and how in the body of the local expression. The second one is to write down a stub for the helper function: its signature, its purpose (optionally), and its header. Keep in mind that the signature comparison in the preceding step suggests most of the signature for the auxiliary function.
Here is what this template looks like for our running example if we choose foldr:Finally, it is time to define the helper function inside local. In most cases, this auxiliary function consumes relatively simple kinds of data, like those encountered in FixedSize Data. You know how to design those in principle. The only difference is that now you may not only use the function’s arguments and global constants but also the arguments of the surrounding function.
In our running example, the purpose of the helper function is to add one dot to the given scene, which you can (1) guess or (2) derive from the example:The last step is to test the definition in the usual manner.
For abstract functions, it is occasionally possible to use the abstract example of their purpose statement to confirm their workings at a more general level. You may wish to use the abstract example for foldr to confirm that dots does add one dot after another to the background scene.
18.7 Finger Exercises: Abstraction
Each of the following set of exercises suggests small practice problems for specific abstractions in ISL.
Exercise 269. Use map to define the function converteuro, which converts a list of US$ amounts into a list of € amounts based on an exchange rate of €1.22 per US$.
Also use map to define convertFC, which converts a list of Fahrenheit measurements to a list of Celsius measurements.
Finally, try your hands at translate, a function that translates a list of Posns into a list of list of pairs of numbers, i.e., [Listof [list Number Number]].
Exercise 270. An inventory record specifies the name of an item, a description, the acquisition price, and the recommended sales price.
Define a function that sorts a list of inventory records by the difference between the two prices.
Exercise 271. Define eliminateexp, which consumes a number, ua and a list of inventory records, and it produces a list of all those structures whose sales price is below ua.
Then use filter to define recall, which consumes the name of an inventory item, called ty, and a list of inventory records and which produces a list of inventory records that do not use the name ty.
In addition, define selection, which consumes two lists of names and selects all those from the second one that are also on the first.
Exercise 273. Use ormap to define findname. The function consumes a name and a list of names. It determines whether any of the names on the latter are equal to or an extension of the former.
With andmap you can define a function that checks all names on a list of names start with the letter "a".
Should you use ormap or andmap to define a function that ensures that no name on some list exceeds some given width?
Now use one of the fold functions to define functions that compute the sum and the product, respectively, of a list of numbers.
With one of the fold functions, you can define a function that horizontally composes a list of Images. Hints (1) Look up beside and emptyimage. Can you use the other fold function? Also define a function that stacks a list of images vertically. (2) Check for above in the libraries.
Exercise 275. The fold functions are so powerful that you can define almost any listprocessing functions with them. Use fold to define map.
Exercise 276. Use existing abstractions to define the prefixes and suffixes functions from exercise 190. Ensure that they pass the same tests as the original function.
18.8 Projects: Abstraction
Now that you have some experience with the existing listprocessing abstractions in ISL, it is time to tackle some of the small projects for which you already have programs. The challenge is to look for two kinds of improvements. First, inspect the programs for functions that traverse lists. For these functions, you already have signatures, purpose statements, tests, and working definitions that pass the tests. Change the definitions to use abstractions from figure 83. Second, also determine whether there are opportunities to create new abstractions. Indeed, you might be able to abstract across these classes of programs and provide generalized functions that help you write additional programs.
You may wish to tackle these exercises again after studying Nameless Functions.
Design mostfrequent. The function consumes a Dictionary and produces the LetterCount for the letter that is most frequently used as the first one in the words of the given Dictionary.
Design wordsbyfirstletter. The function consumes a Dictionary and produces a list of Dictionarys, one per Letter. Do not include '() if there are no words for some letter; ignore the empty grouping instead.
Design selectalbumdate. The function consumes the title of an album, a date, and an LTracks. It extracts from the latter the list of tracks that belong to the given album and have been played after the given date.
Design selectalbums. The function consumes an LTracks. It produce a list of LTracks, one per album. Each album is uniquely identified by its title and shows up in the result only once.
Exercise 279. Full Space War spells out a game of space war. In the basic version, a UFO descends and a player defends with a tank. One additional suggestion is to equip the UFO with charges that it can drop at the tank; the tank is destroyed if a charge comes close enough.
Inspect the code of your project for places where it can benefit from existing abstraction, that is, processing lists of shots or charges.
Once you have simplified the code with the use of existing abstractions look for opportunities to create abstractions. Consider moving lists of objects as one example where abstraction may pay off.
Exercise 280. Feeding Worms explains how another one of the oldest computer games work. The game features a worm that moves at a constant speed in a playercontrolled direction. When it encounters food, it eats the food and grows. When it runs into the wall or into itself, the game is over.
This project can also benefit from the abstract listprocessing in ISL. Look for places to use them and replace existing code one piece at a time, relying on the tests to ensure the program works.
19 Nameless Functions
; [Listof IR] String > Boolean (define (find aloir threshold) (local (; IR > Boolean (define (acceptable? ir) (<= (irprice ir) threshold))) (filter acceptable? aloir)))
; [Listof IR] String > Boolean (define (find aloir threshold) (filter (lambda (ir) (<= (irprice ir) threshold)) aloir))
19.1 Functions from lambda
(lambda (x) (* 10 x)), which assumes that the argument is a number and computes the exponent of 10 to the number;
(lambda (name) (stringappend "hello, " name ", how are you?")), which consumes a string and creates a greeting with stringappend; and
(lambda (ir) (<= (irprice ir) threshold)), which is a function on an IR struct that extracts the price and compares it with some threshold value.
This way of thinking about lambda shows one more time why the rule for computing with local is complicated.
A nameless function is a value like any other value. The only interesting
parts are the function parameters—
> ((lambda (x) (* 10 x)) 2) 20
> ((lambda (name rst) (stringappend name ", " rst)) "Robby" "etc.") "Robby, etc."
> ((lambda (ir) (<= (irprice ir) threshold)) (makeir "bear" 10)) #true
(define threshold 20)
> (map (lambda (x) (* 10 x)) '(1 2 3)) (list 10 20 30)
> (foldl (lambda (name rst) (stringappend name ", " rst)) "etc." '("Matthew" "Robby")) "Robby, Matthew, etc."
> (filter (lambda (ir) (<= (irprice ir) threshold)) (list (makeir "bear" 10) (makeir "doll" 33))) (list (ir ...))
consumes a number and decides whether it is less than 10;
consumes two numbers, multiplies them, and turns the result into a string;
consumes two inventory records and compares them by price;
consumes a natural number and produces 0 if it is even and 1 if it is odd; and
consumes an Posn p together with a rectangular Image and adds a red 3pixel dot to the image at p.
19.2 Computing with lambda
The insight that lambda abbreviates a certain kind of local also connects constant definitions and function definitions. Instead of viewing function definitions as given, we can take lambdas as another fundamental concept and say that a function definition abbreviates a plain constant definition with a lambda expression on the righthand side.
Alonzo Church, who invented lambda in the late 1920s, aimed to create a unifying theory of functions in mathematics. From his work we know that from a purely theoretical perspective, a language does not need local once it has lambda. But the margin of this page is too small to explain this idea properly. If you are curious, read up on the Y combinator.
Exercise 284. Experiment with the above definitions in DrRacket.
(compare (random 100000))
expr  =  ...  
  (expr expr ...)  
value  =  ...  
  (lambda (variable variable ...) expr) 
((lambda (x1 ... xn) fbody) v1 ... vn) == fbody ; with all occurrences of x1 ... xn ; replaced with v1 ... vn, respectively
((lambda (x) (* 10 x)) 2) == (* 10 2) == 20 ((lambda (name rst) (stringappend name ", " rst)) "Robby" "etc.") == (stringappend "Robby" ", " "etc.") == "Robby, etc." ((lambda (ir) (<= (irprice ir) threshold)) (makeir "bear" 10)) == (<= (irprice (makeir "bear" 10)) threshold) == (<= 10 threshold) == #true assuming that threshold is larger than or equal to 10.
Exercise 285. Confirm that DrRacket’s stepper can deal with lambda expressions.
(map (lambda (x) (* 10 x)) '(1 2 3)) (foldl (lambda (name rst) (stringappend name ", " rst)) "etc." '("Matthew" "Robby")) (filter (lambda (ir) (<= (irprice ir) threshold)) (list (makeir "bear" 10) (makeir "doll" 33)))
19.3 Abstracting with lambda
(define (dots lop) (local (; Posn Image > Image (define (addonedot p scene) ...)) (foldr addonedot BACKGROUND lop)))
(define (dots lop) (foldr (lambda (oneposn scene) (placeimage DOT (posnx oneposn) (posny oneposn) scene)) BACKGROUND lop))
The following exercises request that you solve the problems from Finger Exercises: Abstraction with lambda in ISL+ .
Exercise 288. Use map to define the function converteuro, which converts a list of US$ amounts into a list of € amounts based on an exchange rate of €1.22 per US$.
Also use map to define convertFC, which converts a list of Fahrenheit measurements to a list of Celsius measurements.
Finally, try your hands at translate, a function that translates a list of Posns into a list of list of pairs of numbers, i.e., [Listof [list Number Number]].
Exercise 289. An inventory record specifies the name of an inventory item, a description, the acquisition price, and the recommended sales price.
Define a function that sorts a list of inventory records by the difference between the two prices.
Exercise 290. Use filter to define eliminateexp. The function consumes a number, ua and a list of inventory records (containing name and price), and it produces a list of all those structures whose acquisition price is below ua.
Then use filter to define recall, which consumes the name of an inventory item, called ty, and a list of inventory records and which produces a list of inventory records that do not use the name ty.
In addition, define selection, which consumes two lists of names and selects all those from the second one that are also on the first.
Exercise 292. Use ormap to define findname. The function consumes a name and a list of names. It determines whether any of the names on the latter are equal to or an extension of the former.
With andmap you can define a function that checks all names on a list of names start with the letter "a".
Should you use ormap or andmap to define a function that ensures that no name on some list exceeds some given width?
Now use one of the fold functions to define functions that compute the sum and the product, respectively, of a list of numbers.
With one of the fold functions, you can define a function that horizontally composes a list of Images. Hints (1) Look up beside and emptyimage. Can you use the other fold function? Also define a function that stacks a list of images vertically. (2) Check for above in the libraries.
Exercise 294. The fold functions are so powerful that you can define almost any listprocessing functions with them. Use fold to define mapviafold, which simulates map.
19.4 Specifying with lambda
Figure 85 shows a generalized sorting function that consumes a list of values and a comparison function for such values. The details of the definitions don’t matter for this section, and to help the discussion figure 89 displays the essence of the sorting function. The body of sortcmp introduces two local auxiliary functions: isort and insert. In addition, the figure also comes with two test cases that illustrate the workings of sortcmp. One demonstrates how the function works on strings and the other one for numbers.
; [Listof Number] [Number Number > Boolean] > [Listof Number] ; sort alon0 according to cmp (checkexpect (sortcmp '("a" "c" "b") string<?) '("a" "b" "c")) (checkexpect (sortcmp '(2 1 3 4 6 5) <) '(1 2 3 4 5 6)) (define (sortcmp alon0 cmp) (local (; [Listof Number] > [Listof Number] ; produces a variant of alon sorted by cmp (define (isort alon) ...) ; Number [Listof Number] > [Listof Number] ; inserts n into the sorted list of numbers alon (define (insert n alon) ...)) (isort alon0)))
(checksatisfied (sort> '()) sorted>?) (checksatisfied (sort> '(12 20 5)) sorted>?) (checksatisfied (sort> '(3 2 1)) sorted>?) (checksatisfied (sort> '(1 2 3)) sorted>?)
(checksatisfied (sortcmp '("a" "c" "b") string<?) (sorted string<?)) (checksatisfied (sortcmp '(2 1 3 4 6 5) <) (sorted <))
; [X X > Boolean] > [ [Listof X] > Boolean] ; produces a function that determines whether ; some list is sorted according to cmp (define (sorted cmp) ...)
(checkexpect (sorted string<?) ...) (checkexpect (sorted <) ...)
(checkexpect [(sorted string<?) '("a" "b" "c")] #true) (checkexpect [(sorted <) '(1 2 3 4 5 6)] #true)
; [X X > Boolean] [NEListof X] > Boolean ; determine whether l is sorted according to cmp (checkexpect (sorted? < '(1 2 3)) #true) (checkexpect (sorted? < '(2 1 3)) #false) (