On Lisp - Chapter 2

Functions

Functions are the building-blocks of Lisp programs. They are also the building-blocks of Lisp. In most languages the + operator is something quite different from user-defined functions. But Lisp has a single model, function application, to describe all the computation done by a program. The Lisp + operator is a function, just like the ones you can define yourself.

In fact, except for a small number of operators called special forms, the core of Lisp is a collection of Lisp functions. What’s to stop you from adding to this collection? Nothing at all: if you think of something you wish Lisp could do, you can write it yourself, and your new function will be treated just like the built-in ones.

This fact has important consequences for the programmer. It means that any new function could be considered either as an addition to Lisp, or as part of a specific application. Typically, an experienced Lisp programmer will write some of each, adjusting the boundary between language and application until the two fit one another perfectly. This book is about how to achieve a good fit between language and application. Since everything we do toward this end ultimately depends on functions, functions are the natural place to begin.

2.1 Functions as Data

Two things make Lisp functions different. One, mentioned above, is that Lisp itself is a collection of functions. This means that we can add to Lisp new operators of our own. Another important thing to know about functions is that they are Lisp objects.

Lisp offers most of the data types one finds in other languages. We get integers and floating-point numbers, strings, arrays, structures, and so on. But Lisp supports one data type which may at first seem surprising: the function. Nearly all programming languages provide some form of function or procedure. What does it mean to say that Lisp provides them as a data type? It means that in Lisp we can do with functions all the things we expect to do with more familiar data types, like integers: create new ones at runtime, store them in variables and in structures, pass them as arguments to other functions, and return them as results.

The ability to create and return functions at runtime is particularly useful. This might sound at first like a dubious sort of advantage, like the self-modifying machine language programs one can run on some computers. But creating new functions at runtime turns out to be a routinely used Lisp programming technique.

2.2 Defining Functions

Most people first learn how to make functions with defun. The following expression defines a function called double which returns twice its argument.

> (defun double (x) (* x 2)) DOUBLE

Having fed this to Lisp, we can call double in other functions, or from the toplevel:

> (double 1) 2

A file of Lisp code usually consists mainly of such defuns, and so resembles a file of procedure definitions in a language like C or Pascal. But something quite different is going on. Those defuns are not just procedure definitions, they’re Lisp calls. This distinction will become clearer when we see what’s going on underneath defun.

Functions are objects in their own right. What defun really does is build one, and store it under the name given as the first argument. So as well as calling double, we can get hold of the function which implements it. The usual way to do so is by using the #’ (sharp-quote) operator. This operator can be understood as mapping names to actual function objects. By affixing it to the name of double

> #’double #<Interpreted-Function C66ACE>

we get the actual object created by the definition above. Though its printed representation will vary from implementation to implementation, a Common Lisp function is a first-class object, with all the same rights as more familiar objects like numbers and strings. So we can pass this function as an argument, return it, store it in a data structure, and so on:

> (eq #’double (car (list #’double))) T

We don’t even need defun to make functions. Like most Lisp objects, we can refer to them literally. When we want to refer to an integer, we just use the integer itself. To represent a string, we use a series of characters surrounded by double-quotes. To represent a function, we use what’s called a lambda-expression. A lambda-expression is a list with three parts: the symbol lambda, a parameter list, and a body of zero or more expressions. This lambda-expression refers to a function equivalent to double:

(lambda (x) (* x 2))

It describes a function which takes one argument x, and returns 2x.

A lambda-expression can also be considered as the name of a function. If double is a proper name, like “Michelangelo,” then (lambda (x) (* x 2)) is a definite description, like “the man who painted the ceiling of the Sistine Chapel.” By putting a sharp-quote before a lambda-expression, we get the corresponding function:

> #’(lambda (x) (* x 2)) #<Interpreted-Function C674CE>

This function behaves exactly like double, but the two are distinct objects.

In a function call, the name of the function appears first, followed by the arguments:

> (double 3) 6

Since lambda-expressions are also names of functions, they can also appear first in function calls:

> ((lambda (x) (* x 2)) 3) 6

In Common Lisp, we can have a function named double and a variable named double at the same time.

> (setq double 2) 2 > (double double) 4

When a name occurs first in a function call, or is preceded by a sharp-quote, it is taken to refer to a function. Otherwise it is treated as a variable name.

It is therefore said that Common Lisp has distinct name-spaces for variables and functions. We can have a variable called foo and a function called foo, and they need not be identical. This situation can be confusing, and leads to a certain amount of ugliness in code, but it is something that Common Lisp programmers have to live with.

If necessary, Common Lisp provides two functions which map symbols to the values, or functions, that they represent. The function symbol-value takes a symbol and returns the value of the corresponding special variable:

> (symbol-value ’double) 2

while symbol-function does the same for a globally defined function:

> (symbol-function ’double) #<Interpreted-Function C66ACE>

Note that, since functions are ordinary data objects, a variable could have a function as its value:

> (setq x #’append) #<Compiled-Function 46B4BE> > (eq (symbol-value ’x) (symbol-function ’append)) T

Beneath the surface, defun is setting the symbol-function of its first argument to a function constructed from the remaining arguments. The following two expressions do approximately the same thing:

(defun double (x) (* x 2))

(setf (symbol-function ’double) #’(lambda (x) (* x 2)))

So defun has the same effect as procedure definition in other languages—to associate a name with a piece of code. But the underlying mechanism is not the same. We don’t need defun to make functions, and functions don’t have to be stored away as the value of some symbol. Underlying defun, which resembles procedure definition in any other language, is a more general mechanism: building a function and associating it with a certain name are two separate operations. When we don’t need the full generality of Lisp’s notion of a function, defun makes function definition as simple as in more restrictive languages.

2.3 Functional Arguments

Having functions as data objects means, among other things, that we can pass them as arguments to other functions. This possibility is partly responsible for the importance of bottom-up programming in Lisp.

A language which allows functions as data objects must also provide some way of calling them. In Lisp, this function is apply. Generally, we call apply with two arguments: a function, and a list of arguments for it. The following four expressions all have the same effect:

(+12)

(apply #’+ ’(1 2))

(apply (symbol-function ’+) ’(1 2))

(apply #’(lambda (x y) (+ x y)) ’(1 2))

In Common Lisp, apply can take any number of arguments, and the function given first will be applied to the list made by consing the rest of the arguments onto the list given last. So the expression

(apply #’+ 1 ’(2))

is equivalent to the preceding four. If it is inconvenient to give the arguments as a list, we can use funcall, which differs from apply only in this respect. This expression

(funcall #’+ 1 2)

has the same effect as those above.

Many built-in Common Lisp functions take functional arguments. Among the most frequently used are the mapping functions. For example, mapcar takes two or more arguments, a function and one or more lists (one for each parameter of the function), and applies the function successively to elements of each list:

> (mapcar #’(lambda (x) (+ x 10))

’(1 2 3)) (11 12 13) > (mapcar #’+

’(1 2 3)

’(10 100 1000)) (11 102 1003)

Lisp programs frequently want to do something to each element of a list and get back a list of results. The first example above illustrates the conventional way to do this: make a function which does what you want done, and mapcar it over the list.

Already we see how convenient it is to be able to treat functions as data. In many languages, even if we could pass a function as an argument to something like mapcar, it would still have to be a function defined in some source file beforehand. If just one piece of code wanted to add 10 to each element of a list, we would have to define a function, called plus ten or some such, just for this one use. With lambda-expressions, we can refer to functions directly.

One of the big differences between Common Lisp and the dialects which preceded it are the large number of built-in functions that take functional arguments. Two of the most commonly used, after the ubiquitous mapcar, are sort and remove-if. The former is a general-purpose sorting function. It takes a list and a predicate, and returns a list sorted by passing each pair of elements to the predicate.

> (sort ’(1 4 2 5 6 7 3) #’<) (123456 7)

To remember how sort works, it helps to remember that if you sort a list with no duplicates by <, and then apply < to the resulting list, it will return true.

If remove-if weren’t included in Common Lisp, it might be the first utility you would write. It takes a function and a list, and returns all the elements of the list for which the function returns false.

> (remove-if #’evenp ’(123456 7)) (1357)

As an example of a function which takes functional arguments, here is a definition of a limited version of remove-if:

(defun our-remove-if (fn lst)

(if (null lst)

nil

(if (funcall fn (car lst))

(our-remove-if fn (cdr lst))

(cons (car lst) (our-remove-if fn (cdr lst))))))

Note that within this definition fn is not sharp-quoted. Since functions are data objects, a variable can have a function as its regular value. That’s what’s happening here. Sharp-quote is only for referring to the function named by a symbol—usually one globally defined as such with defun.

As Chapter 4 will show, writing new utilities which take functional arguments is an important element of bottom-up programming. Common Lisp has so many utilities built-in that the one you need may exist already. But whether you use built-ins like sort, or write your own utilities, the principle is the same. Instead of wiring in functionality, pass a functional argument.

2.4 Functions as Properties

The fact that functions are Lisp objects also allows us to write programs which can be extended to deal with new cases on the fly. Suppose we want to write a function which takes a type of animal and behaves appropriately. In most languages, the way to do this would be with a case statement, and we can do it this way in Lisp as well:

(defun behave (animal) (case animal (dog (wag-tail) (bark)) (rat (scurry) (squeak)) (cat (rub-legs) (scratch-carpet))))

What if we want to add a new type of animal? If we were planning to add new animals, it would have been better to define behave as follows:

(defun behave (animal) (funcall (get animal ’behavior)))

and to define the behavior of an individual animal as a function stored, for example, on the property list of its name:

(setf (get ’dog ’behavior)

#’(lambda ()

(wag-tail)

(bark)))

This way, all we need do in order to add a new animal is define a new property. No functions have to be rewritten.

The second approach, though more flexible, looks slower. It is. If speed were critical, we would use structures instead of property lists and, especially, compiled instead of interpreted functions. (Section 2.9 explains how to make these.) With structures and compiled functions, the more flexible type of code can approach or exceed the speed of versions using case statements.

This use of functions corresponds to the concept of a method in object-oriented programming. Generally speaking, a method is a function which is a property of an object, and that’s just what we have. If we add inheritance to this model, we’ll have all the elements of object-oriented programming. Chapter 25 will show that this can be done with surprisingly little code.

One of the big selling points of object-oriented programming is that it makes programs extensible. This prospect excites less wonder in the Lisp world, where extensibility has always been taken for granted. If the kind of extensibility we need does not depend too much on inheritance, then plain Lisp may already be sufficient.

2.5 Scope

Common Lisp is a lexically scoped Lisp. Scheme is the oldest dialect with lexical scope; before Scheme, dynamic scope was considered one of the defining features of Lisp.

The difference between lexical and dynamic scope comes down to how an implementation deals with free variables. A symbol is bound in an expression if it has been established as a variable, either by appearing as a parameter, or by variable-binding operators like let and do. Symbols which are not bound are said to be free. In this example, scope comes into play:

(let ((y 7)) (defun scope-test (x) (list x y)))

Within the defun expression,x is bound and y is free. Free variables are interesting because it’s not obvious what their values should be. There’s no uncertainty about the value of a bound variable—when scope-test is called, the value of x should be whatever is passed as the argument. But what should be the value of y? This is the question answered by the dialect’s scope rules.

In a dynamically scoped Lisp, to find the value of a free variable when executing scope-test, we look back through the chain of functions that called it. When we find an environment where y was bound, that binding of y will be the one used in scope-test. If we find none, we take the global value of y. Thus, in a dynamically scoped Lisp, y would have the value it had in the calling expression:

> (let ((y 5)) (scope-test 3))

(3 5)

With dynamic scope, it means nothing that y was bound to 7 when scope-test was defined. All that matters is that y had a value of 5 when scope-test was called.

In a lexically scoped Lisp, instead of looking back through the chain of calling functions, we look back through the containing environments at the time the function was defined. In a lexically scoped Lisp, our example would catch the binding of y where scope-test was defined. So this is what would happen in Common Lisp:

> (let ((y 5)) (scope-test 3))