# Section 20Functions 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.

 = (define ( ...) ) | (define ) | (define-struct ( ...)) = | | | | empty | ( ...) | (cond ( ) ...( )) | (cond ( ) ...(`else` )) | (local ( ...) ) = `x` | `area-of-disk` | `circumference` | ... = `true` | `false` = `'a` | `'doll` | `'sum` | ... = `1` | `-1` | `3/5` | `1.22` | ... = `+` | `-` | `cons` | `first` | `rest` | ...

Figure 56:  Intermediate Student Scheme: The grammar

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:

 = | | ( ...)
Figure 56 displays the entire Scheme grammar, with all the extensions we have encountered so far. It shows that the accommodation of abstract functions does not lengthen the grammar, but makes it simpler.

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:

 = | | | empty | | (names of `define`d functions) | = empty | (cons )

Put differently, if we now wish to decide whether we can apply the substitution rule for functions, we must still ensure that all arguments are values, but we must recognize that function names and primitive operations count as values, too.

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 `X`s, and that the result of `filter1` is also a list of `X`s.

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 `X`s and a list; it produces a list of `X`s.

3. `project`, which consumes a list of lists and a function from lists to `X`s; it produces a list of `X`s.

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.