Previous Table of Contents Next


3.4.1. First-Class Data

In most programming languages, a procedure is created with a name and can be invoked only with that name. Here’s an example:

   int square(int x) {
     return x * x;
   }

You can do the same thing in Scheme:

   (define (square x)
     (* x x))

This is similar in spirit to the named function notation used in high school algebra:

   f(x) = x2

Both in mathematics and in programming, it is possible, but much less common, to use a function without a name. The mathematical notation is

   x → x2

You can’t just use x2 to represent this function because x2 is an expression whose value is a number, although you don’t know which number until you specify the value of x. Also, note that the following are two different functions:

   x,y → 3x + y
   y,x → 3x + y

In most programming languages, there is no corresponding notation for an anonymous procedure, but in Lisp, you can say

   (lambda (x) (* x x))
   (lambda (x y) (+ (* 3 x) y))
   (lambda (y x) (+ (* 3 x) y))

Even in most Lisp dialects, however, a procedure can’t be used as the value of an ordinary variable; some extra syntax is needed, for example, to write a procedure that takes another procedure as an argument. In Scheme, a procedure is a perfectly ordinary datum. It can be the value of a variable; it can be a member of an array or a list; it can be an argument to or the return value from a procedure. This is what it means for a data type to be first class in a programming language.

In fact, the definition of the procedure square earlier is just an abbreviation for

   (define square (lambda (x) (* x x)))

which is no different in spirit from assigning any other value to a variable, such as this assignment:

   (define pi 3.141592654)

Here is the standard example of a higher-order procedure, one that takes a procedure as one of its arguments. The map procedure computes some function of each element of a list, collecting the results in a new list2:


2 car is a function that extracts the first member of a list; cdr extracts the sublist with all but the first member. cons prepends one additional member to a list. The names have amusing but irrelevant historical roots. The apostrophe () is used as a quotation mark, indicating that the list following it should be taken as literal data, rather than as an expression asking to invoke 4 as a procedure with arguments 7 and 3.
   (define (map procedure values)
     (if (null? values)
         ‘()
         (cons (procedure (car values))
               (map procedure (cdr values)))))
   > (map square ‘(4 7 3))
   (16 49 9)

The combination of first-class procedures (more specifically, the capability for a procedure to return a procedure as its value) with lexical scope makes it easy to write a “procedure factory” procedure in Scheme:

   (define (make-adder num)
     (lambda (x) (+ x num)))

   (define plus-three (make-adder 3))

   (define plus-five (make-adder 5))

Now the expression (plus-three 6) has the value 9, whereas (plus-five 6) has the value 11. Each of these adder procedures “remembers” its own value of num, namely, its value in the lexical environment in which the lambda expression was evaluated.

It is only when combined with lambda that lexical scope really meets its potential. In traditional lexically scoped languages, such as Pascal, lexical scope serves only to restrict the variables available to a procedure when compared with dynamic scope. That restriction can be useful both to improve the efficiency of compiled code and to avoid name capture bugs, but there is nothing in a language without lambda that’s comparable to the way in which lexical scope gives plus-three access to a variable, num, that is not also part of its dynamic environment.

This same ability to export a procedure from a lexical environment also provides, as an automatic consequence, the ability to create local state variables, which, along with local procedures, are the main tools needed in object-oriented programming. I’ll return to that topic later.


Previous Table of Contents Next