4.2.1 Procedures as inputs and outputs

All the procedure inputs and outputs we have seen so far have been numbers. The subexpressions of an application can be any expression including a procedure. A higher-order procedure is a procedure that takes other procedures as inputs or that produces a procedure as its output. Higher-order procedures give us the ability to write procedures that behave differently based on the procedures that are passed in as inputs.

We can create a generic composition procedure by making f and g parameters:

(define fog (lambda (f g x) (g (f x))))

The fog procedure takes three parameters. The first two are both procedures that take one input. The third parameter is a value that can be the input to the first procedure.

For example, (fog square cube 2) evaluates to 64, and (fog (lambda (x) (+ x 1)) square 2) evaluates to 9. In the second example, the first parameter is the procedure produced by the lambda expression (lambda (x) (+ x 1)). This procedure takes a number as input and produces as output that number plus one. We use a definition to name this procedure inc (short for increment):

(define inc (lambda (x) (+ x 1)))

A more useful composition procedure would separate the input value, x, from the composition. The fcompose procedure takes two procedures as inputs and produces as output a procedure that is their composition:1

(define fcompose (lambda (f g) (lambda (x) (g (f x)))))

The body of the fcompose procedure is a lambda expression that makes a procedure. Hence, the result of applying fcompose to two procedures is not a simple value, but a procedure. The resulting procedure can then be applied to a value.

Here are some examples using fcompose:

Scheme output
> (fcompose inc inc)
# < procedure >
> ((fcompose inc inc) 1)
3
> ((fcompose inc square) 2)
9
> ((fcompose square inc) 2)
5

Exercise 4.1.  For each expression, give the value to which the expression evaluates. Assume fcompose and inc are defined as above.

1. ((fcompose square square) 3)

2. (fcompose (lambda (x) (* x 2)) (lambda (x) (/ x 2)))

3. ((fcompose (lambda (x) (* x 2)) (lambda (x) (/ x 2))) 1120)

4. ((fcompose (fcompose inc inc) inc) 2)

Exercise 4.2.  Suppose we define self-compose as a procedure that composes a procedure with itself: (define (self-compose f) (fcompose f f)) Explain how (((fcompose self-compose self-compose) inc) 1) is evaluated.

Exercise 4.3.  Define a procedure fcompose3 that takes three procedures as input, and produces as output a procedure that is the composition of the three input procedures. For example, ((fcompose3 abs inc square) -5) should evaluate to 36. Define fcompose3 two different ways: once without using fcompose, and once using fcompose.

Exercise 4.4.  The fcompose procedure only works when both input procedures take one input. Define a f2compose procedure that composes two procedures where the first procedure takes two inputs, and the second procedure takes one input. For example, ((f2compose + abs) 3 -5) should evaluate to 2.

1. We name our composition procedure fcompose to avoid collision with the built-in compose procedure that behaves similarly.