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)
> ((fcompose inc square) 2)  
> ((fcompose square inc) 2)  

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.