[previous] [up] [next]     [index]
Next: Designing Abstractions from Examples Up: Functions are Values Previous: Syntax and Semantics

Contracts for Abstract and Polymorphic Functions

When we first abstracted below and above into filter1, we did not formulate a contract. Unlike the functions we had defined before, filter1 consumed a type of values that we never before used as data: primitive operations and other functions. Still, we eventually agreed in plain English writing that filter1's first argument, rel-op, would always be a function that consumes two numbers and produces a boolean value.

If, in the past, we had been asked to write a contract for rel-op, we would have written 

;; rel-op : number number -> boolean
Considering that functions and primitive operations are values, this contract says that an arrow symbol, ->, describes a class of values: functions and primitive operations. The names on the left of -> specify what each value in the class of functions must be applied to; the name on the right says what each value is going to produce if it is applied to proper values. In general, we say that 
(A B -> C)
means the class of all functions and primitives that consume an element in A and an element in B and produce an element in C. Or more succinctly, they are functions ``from A and B to C.''

The arrow notation is like the (listof ...) notation from the previous section. Both specify a class of data via a combination of other classes. For listof, we used data definitions to agree on what they mean. Others can follow the example and introduce their own abbreviations based on data definitions. For arrows, we just made an agreement, and it stays with us for good.

Using the arrow notation, we can formulate a first contract and a proper purpose statement for filter1: 

;; filter1 : (number number -> boolean) lon number -> lon 
;; to construct the list of those numbers n on alon for which 
;; (rel-op n t) evaluates to true 
(define (filter1 rel-op alon t) ...)
The unusual part of the contract is that it specifies the class to which the first argument must belong not with a name introduced by a data definition but with a direct data definition, using the arrow notation. More concretely, it specifies that the first argument must be a function or a primitive operation and, as discussed, what kind of arguments it consumes and what kind of value it produces.

Exercises

Exercise 20.2.1

Explain the following classes of functions:

  1. (number -> boolean),
  2. (boolean symbol -> boolean),
  3. (number number number -> number),
  4. (number -> (listof number)), and
  5. ((listof number) -> boolean). Solution

Exercise 20.2.2

Formulate contracts for the following functions:

  1. sort, which consumes a list of numbers and a function that consumes two numbers and produces a boolean; sort produces a list of numbers.
  2. map, which consumes a function from numbers to numbers and a list of numbers; it also produces a list of numbers.
  3. project, which consumes a list of lists of symbols and a function from lists of symbols to symbols; it produces a list of symbols. Solution

The second version of filter1 was the result of abstracting below and below-ir. Its definition did not differ from the first version, but the process of abstracting from below-ir clarified that filter1 could be applied to all kinds of lists, not just lists of numbers.

To describe all kinds of lists, we use (listof X). Here is a first attempt at a contract for filter1: 

;; filter1 : ... (listof X) number -> (listof X)
The key to using filter1 with different classes of lists is to use a comparison function that can compare the items on the list with the second argument, which is a number. That is, the first argument is a function in the class 
(X number -> boolean)
which means it consumes an element of X and a number, and produces a boolean. Put together, we get the following contract for filter1: 
;; filter1 : (X number -> boolean) (listof X) number -> (listof X)

As in our contract for length, X here stands for an arbitrary collection of Scheme data. We can replace it with anything, as long as all three occurrences are replaced by the same thing. Hence, by using X in the description of the first parameter, the second parameter, and the result, we specify that rel-op consumes elements of class X, that the second argument is a list of Xs, and that the result of filter1 is also a list of Xs.

When we wish to apply filter1, we must check that the arguments make sense. Suppose we wish to evaluate 

(filter1 < (list 3 8 10) 2)
Before we do that, we should confirm that filter1 can indeed consume < and (list 3 8 10), given its contract. A quick check shows that < makes sense because it belongs to the class 
(number number -> boolean)
and (list 3 8 10) makes sense because it belongs to 
(listof number)
The two classes are identical to the first two argument parts of filter1's contract if X is replaced by number. More generally, to ensure that arguments make sense, we must find replacements of the variables in contracts so that the functions contract and the classes of the arguments match.

For a second example, consider 

(filter1  tex2html_wrap_inline72246  LOIR 10)
Here, we must replace X with IR, because tex2html_wrap_inline72246 has the contract 
(IR number -> boolean)
and LOIR belongs to (listof IR). Again, the application is legitimate because all the arguments belong to the required collections of data.

Let us look at one more example: the use of filter1 to extract all toys with the same name from a list of inventory records: 

;; find : (listof IR) symbol -> (listof IR)
(define (find aloir t) 
  (filter1 eq-ir? aloir t))


;; eq-ir? : IR symbol -> boolean 
(define (eq-ir? ir p) 
  (symbol=? (ir-name ir) p))
It is straightforward to check with examples that the function works properly. Our task here is to understand how this agrees with filter1's contract. The obvious problem is that the ``threshold'' argument is a symbol, not a number. The use of filter1 is therefore in conflict with its current contract. To overcome this deficiency, we must introduce another variable, say, TH for thresholds, that stands for some collection of data: 
;; filter1 : (X TH -> boolean) (listof X) TH -> (listof X)

Now we can replace X with the name of one data collection and TH with that of a second one or possibly the same. In particular, the application 

(filter1 eq-ir? LOIR 'doll)
works because a replacement of X by IR and TH by symbol in filter1's contract shows that the arguments are legitimate.

Exercises

Exercise 20.2.3

Use filter1 to develop a function that consumes a list of symbols and extracts all those that are not equal to 'car. Give filter1's corresponding contract. Solution

Exercise 20.2.4

Formulate general contracts for the following functions:

  1. sort, which consumes a list and a function that consumes two items from the list and produces a boolean; it produces a list of numbers.
  2. map, which consumes a function from list items to Xs and a list; it produces a list of Xs.
  3. project, which consumes a list of lists and a function from lists to Xs; it produces a list of Xs.
Compare with exercise [cross-reference]. Solution

Contracts and Types: In summary, the contracts for functions are made up of types. A TYPE is either

  1. a basic type, such as number, symbol, boolean, or empty;
  2. a defined type, such as inventory-record, list-of-numbers, or family-tree;
  3. a function type, such as (number -> number) or (boolean -> symbol);
  4. a parametric type, which is either a defined type or a function type with type variables.
When we wish to use a function with a parametric type, we must first find a replacement for all the variables in the function's contract so that we know the arguments belong to proper classes. If this cannot be done, we must either revise the contract or question our decision to reuse this function. 

[previous] [up] [next]     [index]
Next: Designing Abstractions from Examples Up: Functions are Values Previous: Syntax and Semantics

PLT