Section 20

Functions are Values

The functions of section 19 stretch our understanding of evaluation. It is easy to understand how functions consume numbers and symbols; cosuming structures and lists is a bit more complicated, but still within our grasp; but functions consuming functions is a strange idea. As a matter of fact, the functions of section 19 violate the Scheme grammar of section 8.

In this section, we discuss how to adjust Scheme's grammar and evaluation rules so that we can understand the role of functions as data or values. Without a good understanding of these ideas, we cannot hope to abstract functions. Once we understand these ideas, we can turn to the problem of writing contracts for such functions. Finally, the last part of the section introduces functions that produce functions, another powerful abstraction technique.

20.1  Syntax and Semantics

The abstract functions of section 19 violate Scheme's basic grammar in two ways. First, the names of functions and primitive operations are used as arguments in applications. An argument, though, is an expression, and the class of expressions does not contain primitive operations and function names. It does contain variables, but we agreed that they are only those variables mentioned in variable definitions and as function parameters. Second, parameters are used as if they were functions, that is, the first position of applications. But the grammar of section 8 allows only the names of functions and primitive operations in this place.

Spelling out the problem suggests the necessary changes. First, we should include the names of functions and primitive operations in the definition of <exp>. Second, the first position in an application should allow things other than function names and primitive operations; at a minimum, it must allow variables that play the role of function parameters. In anticipation of other uses of functions, we agree on allowing expressions in that position.

Here is a summary of the three changes:

The same is true of the evaluation rules. Indeed, they don't change at all. What changes is the set of values. To accommodate functions as arguments of functions, the simplest change is to say that the set of values includes the names of functions and primitive operations:

Exercise 20.1.1.   Assume the Definitions window in DrScheme 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.    Solution

Exercise 20.1.2.   Argue why the following sentences are legal definitions:

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

2. (define (f x) f)

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

   Solution

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

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

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

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 (from the list) 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 <ir LOIR 10)

Here, we must replace X with IR, because <ir 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.

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 of items and a function that consumes two items (from the list) and produces a boolean; it produces a list of items.

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