Procedures are First Class

In Scheme, procedures are data objects--you can have a pointer to a procedure and do the same things you can do with any other Scheme value. Technically, we say that procedures are first class objects in the language--you can pass a procedure value as an argument to a procedure, return it as the value of a procedure call, store it in a variable or a field of another object. A procedure pointer is just a value that you can pass around like any other value, like a pair or a boolean.

Procedures are special, of course, because they're the only kind of object that supports the procedure call operation.

In Scheme terminology, a procedure call expression is called a combination. Evaluation of a combination includes evaluation of the argument expressions and application of the procedure to the arguments, i.e., actually calling it with ("applying it to") those values.

An unusual feature of Scheme is that it uses a unified namespace, which means that there's only one kind of name for both normal variables and procedures--in fact, procedure names are really just variable names, and there's only one kind of variable. A named procedure is really just a first-class procedure object that happens to be referenced from a variable.

Recall the definition of min:

(define (min a b)
   (if (< a b)
       a
       b))

When you define a procedure like this, you're really doing three things: creating a procedure, creating a normal variable (named min), and initializing the variable with a pointer to the procedure.

(This means that you can't have both a procedure variable and a "normal" data variable by the same name in the same scope--there's really only one kind of variable, so you can only have one binding in a given scope.)

When you define a procedure as we did above for the min example, Don't let the special syntax for procedure definitions fool you--a procedure name is really just the name of a variable that happens to hold a procedure value. You can use any variable that way, by storing a procedure value in it. You can also assign a new procedure value to a variable, and then use it to name the new procedure.

For example, if you've defined min as above, you can change the value in the binding of min by saying (set! min +). That assignment expression will look up the value of the variable +, which is the addition procedure, and assign that into the variable min.

Then when you call min as before, it will do addition instead, because it will call the same procedure as +. For example (min 5 10) will return 15, not 5.

You could also change the meaning of +, just by assigning a new value to the (the binding of) the variable +. This is probably a bad idea unless you really have a good reason, because if the new procedure doesn't do addition, any code that calls + will return different answers!

It is important to understand how procedure calls actually work in Scheme, which is actually very simple. Consider the combination (procedure call expression) (+ a b). What this really means is

1. look up the value of (the current binding of) the variable +, which we assume is a procedure,
2. look up the values of (the current bindings of) the variables a and b, and
3. apply the procedure to those values, i.e., call it with those values as arguments.

The first subexpression of the combination is evaluated in just the same way as the others, although the result is used differently. The first subexpression is just a subexpression that should return a procedure value, and the others give the arguments to pass to it.

This won't work if the first subexpression doesn't evaluate to a procedure value. For example, you can change the meaning of + with an assignment expression (set! + 3). Then if you attempt to call + with the combination (+ 2 3) you'll get an error. Scheme will say something like "ERROR: Attempt to apply non-procedure."

The fact that the first (operator) subexpression is evaluated just like any other expression can be very useful. Rather than giving the name of a particular procedure to call, we can use any expression whose result is a procedure. For example, we might have a table of procedures to use in different kinds of situations, and search that table for the procedure to call at a particular time:

((look-up-appropriate-procedure key) foo bar)

Here we call the procedure look-up-appropriate-procedure with the argument key to get a procedure, and then apply it to the values of foo and bar.

One warning about combinations: the Scheme language doesn't specify the order in which the subexpressions of a combination are evaluated. Don't write code that depends on whether the operator expression is evaluated first, or on the order of evaluation of the argument expressions.

You might wonder what's so special about first-class procedures, since some other languages (like C) let you pass around pointers to procedures, and call them via those pointers. Scheme's procedures work like Pascal's if you use them for the kinds of things Pascal allows, but also lets you use them in more general ways that I'll explain later.