On Lisp - Chapter 3

Functional Programming

The previous chapter explained how Lisp and Lisp programs are both built out of a single raw material: the function. Like any building material, its qualities influence both the kinds of things we build, and the way we build them.

This chapter describes the kind of construction methods which prevail in the Lisp world. The sophistication of these methods allows us to attempt more ambitious kinds of programs. The next chapter will describe one particularly important class of programs which become possible in Lisp: programs which evolve instead of being developed by the old plan-and-implement method.

3.1 Functional Design

The character of an object is influenced by the elements from which it is made. A wooden building looks different from a stone one, for example. Even when you are too far away to see wood or stone, you can tell from the overall shape of the building what it’s made of. The character of Lisp functions has a similar influence on the structure of Lisp programs.

Functional programming means writing programs which work by returning values instead of by performing side-effects. Side-effects include destructive changes to objects (e.g. by rplaca) and assignments to variables (e.g. by setq). If side-effects are few and localized, programs become easier to read, test, and debug. Lisp programs have not always been written in this style, but over time Lisp and functional programming have gradually become inseparable.

An example will show how functional programming differs from what you might do in another language. Suppose for some reason we want the elements of

(defun bad-reverse (lst)

(let* ((len (length lst))

(ilimit (truncate (/ len 2))))

(do ((i 0 (1+ i))

(j (1- len) (1- j)))

((>= i ilimit))

(rotatef (nth i lst) (nth j lst)))))

Figure 3.1: A function to reverse lists.

a list in the reverse order. Instead of writing a function to reverse lists, we write a function which takes a list, and returns a list with the same elements in the reverse order.

Figure 3.1 contains a function to reverse lists. It treats the list as an array, reversing it in place; its return value is irrelevant:

> (setq lst ’(a b c))

(A B C)

> (bad-reverse lst)

NIL

> lst

(C B A)

As its name suggests, bad-reverse is far from good Lisp style. Moreover, its ugliness is contagious: because it works by side-effects, it will also drawits callers away from the functional ideal.

Though cast in the role of the villain, bad-reverse does have one merit: it shows the Common Lisp idiom for swapping two values. The rotatef macro rotates the values of any number of generalized variables—that is, expressions you could give as the first argument to setf. When applied to just two arguments, the effect is to swap them.

In contrast, Figure 3.2 shows a function which returns reversed lists. With good-reverse,we get the reversed list as the return value; the original list is not touched.

> (setq lst ’(a b c))

(A B C)

> (good-reverse lst)

(C B A)

> lst

(A B C)

(defun good-reverse (lst)

(labels ((rev (lst acc)

(if (null lst)

acc

(rev (cdr lst) (cons (car lst) acc)))))

(rev lst nil)))

Figure 3.2: A function to return reversed lists.

It used to be thought that you could judge someone’s character by looking at the shape of his head. Whether or not this is true of people, it is generally true of Lisp programs. Functional programs have a different shape from imperative ones. The structure in a functional program comes entirely from the composition of arguments within expressions, and since arguments are indented, functional code will show more variation in indentation. Functional code looks fluid 1) on the page; imperative code looks solid and blockish, like Basic.

1)For a characteristic example, see page 242.

Even from a distance, the shapes of bad- and good-reverse suggest which is the better program. And despite being shorter, good-reverse is also more efficient: O(n) instead of O(n2).

We are spared the trouble of writing reverse because Common Lisp has it built-in. It is worth looking briefly at this function, because it is one that often brings to the surface misconceptions about functional programming. Like good-reverse, the built-in reverseworks by returning a value—it doesn’t touch its arguments. But people learning Lisp may assume that, like bad-reverse, it

works by side-effects. If in some part of a program they want a list lst to be reversed, they may write

(reverse lst)

and wonder why the call seems to have no effect. In fact, if we want effects from such a function, we have to see to it ourselves in the calling code. That is, we need to write

(setq lst (reverse lst))

instead. Operators like reverse are intended to be called for return values, not side-effects. It is worth writing your own programs in this style too—not only for its inherent benefits, but because, if you don’t, you will be working against the language.

One of the points we ignored in the comparison of bad- and good-reverse is that bad-reverse doesn’t cons. Instead of building new list structure, it operates on the original list. This can be dangerous—the list could be needed elsewhere in the program—but for efficiency it is sometimes necessary. For such cases, Common Lisp provides an O(n) destructive reversing function called nreverse.

A destructive function is one that can alter the arguments passed to it. However, even destructive functions usually work by returning values: you have to assume that nreverse will recycle lists you give to it as arguments, but you still can’t assume that it will reverse them. As before, the reversed list has to be found in the return value. You still can’t write

(nreverse lst)

in the middle of a function and assume that afterwards lst will be reversed. This is what happens in most implementations:

> (setq lst ’(a b c))

(A B C)

> (nreverse lst)

(C B A)

> lst

(A)

To reverse lst, you have would have to set lst to the return value, as with plain reverse.

If a function is advertised as destructive, that doesn’t mean that it’s meant to be called for side-effects. The danger is, some destructive functions give the impression that they are. For example,

(nconc x y)

almost always has the same effect as

(setq x (nconc x y))

If you wrote code which relied on the former idiom, it might seem to work for some time. However, it wouldn’t do what you expected when x was nil.

Only a few Lisp operators are intended to be called for side-effects. In general, the built-in operators are meant to be called for their return values. Don’t be misled by names like sort, remove, or substitute. If you want side-effects, use setq on the return value.

This very rule suggests that some side-effects are inevitable. Having functional programming as an ideal doesn’t imply that programs should never have sideeffects. It just means that they should have no more than necessary.

It may take time to develop this habit. One way to start is to treat the following operators as if there were a tax on their use:

set setq setf psetf psetq incf decf push pop pushnew

rplaca rplacd rotatef shiftf remf remprop remhash

and also let*, in which imperative programs often lie concealed. Treating these operators as taxable is only proposed as a help toward, not a criterion for, good Lisp style. However, this alone can get you surprisingly far.

In other languages, one of the most common causes of side-effects is the need for a function to return multiple values. If functions can only return one value, they have to “return” the rest by altering their parameters. Fortunately, this isn’t necessary in Common Lisp, because any function can return multiple values.

The built-in function truncate returns two values, for example—the truncated integer, and what was cut off in order to create it. A typical implementation will print both when truncate is called at the toplevel:

> (truncate 26.21875)

26

0.21875

When the calling code only wants one value, the first one is used:

> (= (truncate 26.21875) 26)

T

The calling code can catch both return values by using a multiple-value-bind. This operator takes a list of variables, a call, and a body of code. The body is evaluated with the variables bound to the respective return values from the call:

> (multiple-value-bind (int frac) (truncate 26.21875)

(list int frac))

(26 0.21875)

Finally, to return multiple values, we use the values operator:

> (defun powers (x)

(values x (sqrt x) (expt x 2)))

POWERS

> (multiple-value-bind (base root square) (powers 4)

(list base root square))

(4 2.0 16)

Functional programmingis a good idea in general. It is a particularly good idea in Lisp, because Lisp has evolved to support it. Built-in operators like reverse and nreverse are meant to be used in this way. Other operators, like values and multiple-value-bind, have been provided specifically to make functional programming easier.

3.2 Imperative Outside-In

The aims of functional programming may show more clearly when contrasted with those of the more common approach, imperative programming. A functional program tells you what it wants; an imperative program tells you what to do. A functional program says “Return a list of a and the square of the first element of x:”

(defun fun (x)

(list ’a (expt (car x) 2)))

An imperative programs says “Get the first element of x, then square it, then return a list of a and the square:”

(defun imp (x)

(let (y sqr)

(setq y (car x))

(setq sqr (expt y 2))

(list ’a sqr)))