Go to the first, previous, next, last section, table of contents.

Using and Writing Higher-Order Procedures

A higher-order procedure is one that can take procedures as arguments and/or return them as values. We can use that to write general procedures that do a basic kind of thing, and take arguments that specialize their behavior. The arguments are themselves procedures, which will do specialized things withing the general pattern that the general procedure implements.

Here's a simple example.

Scheme provides a procedure display, which can write textual representation of a data object on the screen, much like the way the read-eval-print loop displays results of expressions you type in. (This is a very handy procedure for debugging, as well as for programs that interact with users.)

Suppose, though, that you want to display a list of objects, not just one. You want a routine list-display to iterate over a list, and display each item in it. The obvious way to write it is to just call display from inside your list-display routine.

(Actually, display can display a list of items, but it puts parentheses around the items in the list. Let's suppose we don't want those parentheses around the displayed items. Writing our own list-display will give us the freedom to make it do whatever we want it to, rather than what display does automatically for lists.)

Here's a version like that:

Scheme>(define (list-display lis)
          (if (null? lis)
              (begin (display (car lis))
                     (list-display (cdr lis)))))

I've written this procedure recursively, because it's easy to use recursion over lists--usually it's easier than using an iteration construct. This procedure checks to see if the list it got was empty, and if so, it returns #f. (That's a reasonable value to return from a procedure that's used for effect, rather than for value.) Otherwise, it displays the first item, and then calls itself recursively to display the rest of the list. I used a begin to sequence the displaying and the recursive call.

It would be cleaner to use cond, so here's an equivalent version using cond:

Scheme>(define (list-display lis)
          (cond ((null? lis)
                 (display (car lis))
                 (list-display (cdr lis)))))

Notice that this is a two-branch conditional, but we use cond instead of if because a cond branch can be a sequence. (We need a sequence because we want to use display to create a side-effect, i.e., writing to the user's screen, as well as calling list-display recursively to do the rest of the work.)

Now try it out:

Scheme>(list-display '(1 2 3))

What happened here is that it displayed each item in the list as it was evaluated, and then Scheme printed out the return value, #f.

This works, but the procedure is not very general. Iterating over lists is very common, so it would be nice to have a more general procedure that iterates over lists, and applies whatever procedure you want.

We can modify our procedure to do this. Instead of taking just a list argument, it can take an argument that's a procedure, and apply that procedure to each element of the list.

We'll call our procedure list-each, because it iterates over a list and does whatever you want to each element.

Scheme>(define (list-each proc lis)
          (cond ((null? lis)
                 (proc (car lis))
                 (list-each proc (cdr lis)))))

The only change we made was to add an argument proc, to accept (a pointer to) a procedure, and to change the call to display into a call to proc.

Remember that procedure names are really just names of variables that hold pointers to procedures, so this works---(proc (car lis)) is just a combination whose first expression is proc, which looks up the value of the local variable proc.

Now we can call this general procedure with the argument display, to tell it to display each thing in the list.

Scheme>(list-each display '(1 2 3))

But maybe this isn't what we want. We might want to print each item, and then a newline (go to the next line), to spread things out vertically. We could write a procedure display-with-newline to do that, but it's easier just to use a lambda expression to create the procedure we need.

Try this:

Scheme>(list-each (lambda (x)
                     (display x)
                  '(1 2 3))

The lambda expression creates a one-argument procedure that will display its argument and then call newline. We pass the procedure that results from this lambda directly to list-each, without ever giving it a name, or saving a pointer to it anywhere. (After list-each is through with it, the procedure will become garbage and its space can be reclaimed by the garbage collector.)

(Scheme has a standard procedure similar to our list-each, but more general, called for-each.)

This is the end of Hunk L

At this point, you should go back to the previous chapter and
read Hunk M before returning here and continuing this tutorial.

(Go BACK to read Hunk M, which starts at section lambda and Lexical Scope (Hunk M).)

Go to the first, previous, next, last section, table of contents.