Sketchy LISP

An Introduction to Functional Programming in Scheme

2.3 Higher Order Functions

A higher order function is a procedure that either takes a procedure as an argument or returns a procedure (or both). For instance, the complement and compose procedures introduced earlier in this book were higher order functions (HOFs). A classic among the HOFs is the mapcar procedure, which used to be part of early versions of LISP. Mapcar maps a procedure over a list. It is defined as follows:

(define (mapcar a f)
  (cond ((null? a) '())
    (else (cons (f (car a))
                (mapcar (cdr a) f)))))

Using this procedure you can do quite a few useful things like computing the sum of squares of a set of numbers:

(define (sum-of-squares . x)
  (apply + (mapcar x (lambda (x) (* x x)))))

or find the member with the least absolute value in a list of numbers:

(define (least-abs x)
  (apply min (mapcar x abs)))

In both of these procedures, mapcar creates an argument list for a variadic procedure such as + or min. This combination can be seen frequently in Scheme programs. The following sample reduction of sum-of-squares illustrates how apply and mapcar interact:

(sum-of-squares 2 3 5 7)
-> (apply + (mapcar (2 3 5 7) (lambda (x) (* x x))))
-> (apply + (4 9 25 49))
-> (+ 4 9 25 49)
=> 87

The Scheme standard does not define mapcar but a much more powerful procedure called map. You may have observed that mapcar can only apply procedures of one argument to the members of a single list. Map eliminates this limitation. It can be applied to any number of lists. To allow for this, the procedure argument had to move to the first position. Map can do anything mapcar can do and more, like computing the inner product (the dot product) of two vectors:

(define (v* a b) (apply + (map * a b)))

or the sum of two vectors:

(define (v+ a b) (map + a b))

or even the sum of any number of vectors:

(define (v+ . a) (apply map + a))

In the above defintion, apply takes three arguments rather than two. In fact apply itself is variadic. When more than two arguments are passed to it, the second through second-to-last arguments are consed to the last argument:

            (apply map + a) -> (map + a)
(apply list 2 3 4 '(5 6 7)) -> (list 2 3 4 5 6 7)

Map is a variadic procedure which accepts a number of lists, so the structure it ultimately processes is a list of lists. Like mapcar it passes the car parts of these lists to its procedure argument. It then advances to the cdr parts of its list arguments.

The version of map that will be constructed here will stop as soon as it reaches the end of one of the lists passed to it. Subsequently it processes lists only up to the length of its shortest argument:

(map + '(1 2 3) '(4 5)) => (5 7)

Note that this behavior, although found in some environments, does not comply with the Scheme standard, which states that all lists passed to map must have the same length.

A procedure for testing whether one member of a list is equal to () can easily be created by first introducing another useful predicate: any? tests whether a given list a contains any member satisfying a predicate p:

(define (any? p a)
  (cond ((null? a) #f)
    ((p (car a)) #t)
    (else (any? p (cdr a)))))

Using this predicate, the any-null? procedure is trivial:

(define (any-null? x) (any? null? x))

Procedures for taking the car parts and the cdr parts of the sublists of a list can be defined by means of mapcar:

(define (car-of a) (mapcar a car))
(define (cdr-of a) (mapcar a cdr))

Given these procedures, the definition of map is quite straight-forward. The procedure basically looks like mapcar, but uses car-of instead of car, cdr-of instead of cdr and any-null? instead of null?. And because a real map has to run in constant space, the following version is tail-recursive, too:

(define (map f . a)
  (letrec
    ((map2
       (lambda (a b)
         (cond ((any-null? a) (reverse b))
           (else (map2 (cdr-of a)
                       (cons (apply f (car-of a)) b)))))))
    (map2 a '())))

Note that this procedure would accept zero lists, which the real map procedure does not. However, as mentioned earlier, standard Scheme provides no procedure for indicating failure, so this condition is left unchecked. (You may use bottom or an implementation dependent error reporting facility to improve this version of map.)

One question that comes into mind is this: If map can do anything mapcar can do, can the occurrences of mapcar in car-of and cdr-of be replaced with map? Can mapcar be optimized away completely by doing this? The startling answer is: no. (Before you go ahead: can you figure out on your own why this optimization is not possible?)

The answer is given in a semi-formal way by assuming that car-of is written in this way:

(define (cdr-of a) (map cdr a))

Given this definition, a sample application of map is reduced:

(map - '(1 2 3))
-> (map2 ((1 2 3)) ())
-> (cond ((any-null? ((1 2 3))) (reverse b)) ...)
-> (cond (else (map2 (cdr-of ((1 2 3))) ...)))

The ellipses in the above reduction denote that this part of the expression is currently of no interest. What is interesting at this point is that

(map cdr ((1 2 3)))

has to be evaluated in order to get the value of first argument of map2. It is evaluated like this:

(map cdr ((1 2 3)))
-> (map2 ((1 2 3)) ())
-> (cond ((any-null? ((1 2 3))) (reverse b)) ...)
-> (cond (else (map2 (cdr-of ((1 2 3))) ...)))

At this point (map cdr ((1 2 3))) has to be evaluated again in order to continue the reduction. In other words: To compute the first argument of map2, the first argument of map2 has to be computed. This is a recursive statement without a trivial case, so its reduction can never terminate.

No reduction containing the same intermediate step twice (like above example) can ever reduce to a normal form, because such a repetition indicates a cycle in that reduction. If you can show that the evaluation of an expression contains a cycle, you have proven that the expression in question has no normal form. In terms of programming: you have proven that the program will crash when it is run. Do you think that this can be done in imperative languages?

2.3.1 Some Fun with Higher Order Functions

In an earlier section, two versions of the depth procedure were shown. The section ended with the question whether depth can be written in any simpler way. Using higher order procedures, indeed, it can:

(define (depth a)
  (if (pair? a)
      (+ 1 (apply max (map depth a)))
      0))

Higher order functions are a quite powerful tool. They actually do add expressiveness to a language, because they allow it to do things that could not be done without them. Another previous section explained why if cannot be implemented as an ordinary procedure. The reasoning was as follows. Given a procedure xif which implements if, the expression

(letrec
  ((down
     (lambda (n)
       (xif (zero? n)
            0
            (down (- n 1))))))
  (down 1))

would reduce to bottom, because both the trivial and the recursive branch of

(xif (zero? n) 0 (down (- n 1)))

would be evaluated before xif was applied and therefore the procedure could never terminate. Higher order functions help here, too, because they can be used to wrap up expressions for later evaluation. Consider the expression

(lambda () (down (- n 1)))

This expression reduces to a procedure whose body is the branch that causes trouble in the above application of xif. Because the troublesome expression is wrapped up in a procedure, it is not evaluated before the procedure is applied (to zero arguments) by writing:

((lambda () (down (- n 1))))

(Note the additional parentheses!) The following equation holds for any expression x:

x = ((lambda () x))

The following implementation of xif is based on this equality:

(define (xif pred true false)
  (if (pred) (true) (false)))

It accepts three zero-argument procedures which wrap up the predicate, the true branch and the false branch of the conditional expression, so

(if a b c)

has the same meaning as

(xif (lambda () a) (lambda () b) (lambda () c))

Therefore above expression involving the application of down can be re-written using xif:

(letrec
  ((down
     (lambda (n)
       (xif (lambda () (zero? n))
            (lambda () 0)
            (lambda () (down (- n 1)))))))
  (down 1))

Except for its awkward syntax xif is perfectly equal to if. The above expression even reduces in constant space, so any value can be passed to down safely.

In fact, higher order functions are so powerful that lambda alone is sufficient to create an entire programming language. Doing so is beyond the scope of this book, but here is a little teaser: In the section explaining primitive procedures, these were described as procedures that cannot be implemented in Scheme itself easily. Here is how the basic list processing primitives can be re-written in Scheme using only lambda and variables:

(define (kons a b) (lambda (p) (p a b)))
(define (kar x) (x (lambda (a b) a)))
(define (kdr x) (x (lambda (a b) b)))

Let us see if this works:

(kons 'head 'tail) => #<procedure (p)>

Does not look too promising, does it? But wait. A cons cell is an object that glues together two other objects, where the first one can be extracted using car and the second one can be extracted using cdr, and this is exactly what kar and kdr do with objects created using kons:

(kar (kons 'head 'tail)) => head
(kdr (kons 'head 'tail)) => tail

Here is an explanation how it works. Note that the external representations of procedures include bodies here and the variables of procedures are substituted by their values to make the code easier to read.

(kons 'head 'tail)
=> #<procedure (p) (p head tail)>
(kdr (kons 'head 'tail))
-> (kdr #<procedure (p) (p head tail)>)
-> (#<procedure (x) (x (lambda (a b) b))>
    #<procedure (p) (p head tail)>)
-> (#<procedure (p) (p head tail)> (lambda (a b) b))
-> ((lambda (a b) b) head tail)
=> tail

Even recursion can be implemented using lambda exclusively by using self-application:

(define (S f x) (f f x))

Using S, the recursive fact procedure from the first section can be re-written in this way:

(S (lambda (f x)
     (cond ((zero? x) 1)
       (else (* x (f f (- x 1))))))
   5)
=> 120

This expression uses an anonymous recursive procedure to compute the factorial of 5, but how can a procedure apply itself when it has no name?

A procedure that is passed to S has to provide an additional argument which will be bound to a copy of itself. This is what the f argument of the above lambda function is used for. (There is a more general device known as the Y combinator that does not have this limitation. It will be introduced later.)

S applies the procedure f to two arguments: f itself and 5. Here is another depiction of the anonymous factorial procedure. This time, S is expanded to a lambda function and the first argument of the operator is rendered in boldface characters:

((lambda (f x) (f f x))
 (lambda (f x)
   (cond ((zero? x) 1)
     (else (* x (f f (- x 1))))))
 5)

You might want to try to evaluate this expression on a piece of paper in order to understand what it does. You may need a lot of paper, though, which is why there is no sample reduction in this book.