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.
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:
(cons f empty)
(f f)
(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:
(define (f x) (x 10))
(define (f x) f)
(define (f x y) (x 'a y 'b))
Exercise 20.1.3.
Develop afunction=?
. 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
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, relop
, 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 relop
,
we would have written
;; relop : 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 numbersn
onalon
for which ;;(relop n t)
evaluates totrue
(define (filter1 relop 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:
(number > boolean)
,
(boolean symbol > boolean)
,
(number number number > number)
,
(number > (listof number))
, and
((listof number) > boolean)
.
Solution
Exercise 20.2.2. Formulate contracts for the following functions:
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.
map
, which consumes a function from numbers to numbers and a
list of numbers; it also produces a list of numbers.
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 belowir
. Its definition did not differ from
the first version, but the process of abstracting from belowir
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 relop
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 eqir? aloir t)) ;;eqir? : IR symbol > boolean
(define (eqir? ir p) (symbol=? (irname 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 eqir? 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:
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.
map
, which consumes a function from list items to X
s and a
list; it produces a list of X
s.
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
a basic type, such as number, symbol, boolean, or empty
;
a defined type, such as inventoryrecord
,
listofnumbers
, or familytree
;
a function type, such as (number > number)
or
(boolean > symbol)
;
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.