Book Review

by Peter Norvig

Common Lisp: A Tutorial

Wendy L. Milner.

Englewood Cliffs, NJ: Prentice Hall, 1988. 519 pages paperback.

A textbook or tutorial on Common Lisp has to cover a lot of ground: the voluminous Common Lisp standard, the mixture of functional and other styles that has come to be known as Lisp programming, and the tenets of good programming and design in general, regardless of language. The book "Common Lisp: A Tutorial" chooses to concentrate on the first of these. More than half the book is a tour of the Common Lisp standard, data type by data type, function by function. Each function is accompanied by a variety of examples and exercises (with answers) designed to help the novice who finds Steele's "Common Lisp: the Language" a little terse. Milner's book does not attempt to teach programming; the most complicated example is a program that shuffles a deck of cards.

The problem is that the examples and exercises are riddled with bugs. There are many nice examples that could be just what the novice needs to understand a particular function, but unfortunately there are just too many errors mixed in with these. The book provides fairly complete coverage of the language, but no motivation behind the topics covered. Individual functions are for the most part explained well, but the tone is ``here is how MAPCAR works,'' and never ``Suppose you wanted to solve problem x. You could define functions F and G, and because G involves transforming every element of a list, you could use MAPCAR.'' Because of this, the completeness of the book begins to become a draw-back: the reader can not tell which functions are more likely to be useful.

The sections of the book that deal with general concepts rather than specific functions are either very shallow or contain serious misconceptions. One chapter is devoted to ``Blocking Constructs,'' meaning flow of control special forms. Milner couches everything in the procedural language metaphor, explaining that blocks indicate ``a beginning and end of a segment that can be entered and exited'' (p. 76). Milner never uses the functional language metaphor, where instead of blocks one would speak of expressions that evaluate to some value. Even outside the blocking chapter, she repeatedly writes in the procedural language style, using the two expression sequence (IF P (RETURN-FROM F X)) Y rather than (IF P X Y), and using (IF P T NIL) instead of P. She suggests using (PROG () ... (RETURN-FROM F X)), but never mentions PROGN. Milner echoes the structured programming party line in condemning GO, but fails to warn that THROW is worse than GO, and that RETURN-FROM is almost as bad.

On page 67, in a comparison of Lisp to C, Fortran, Pascal and BASIC, we see: ``Parenthesis are one difference. No line numbers are another difference.'' Of course, neither C nor Pascal has line numbers, but aside from that, I was hoping for a more informed discussion, covering areas such as data abstraction, strong vs. weak typing, early vs. late binding, functions as objects, extensibility, and so on. None was forthcoming. Programmers coming from other languages often are puzzled by the lack of syntax in Lisp, and Milner admirably tries to explain keywords and reserved words. Unfortunately, her discussion (p. 9) makes no reference to special forms, fails to clearly distinguish lambda-list keywords from keyword-package keywords, and does not mention that keywords are self-evaluating symbols that can be used outside of argument lists. To make things worse, she says on page 44: ``In most languages, the names of functions are reserved words. The functions are defined by the implementors of the language, and there is no way to add more.'' I can't think of any current language that fits that description.

The short discussion of Artificial Intelligence and Expert Systems, while intentionally brief and not a focus of the book, is also quite shallow: ``Humans reason symbolically, not numerically. ... Artificial Intelligence is a method of programming a computer so that the computer uses symbols instead of numbers. It isn't as exciting put that way---No R2-D2 and no C-3PO. Just plain straightforward programming.''

There is a chapter on recursion, which tries to distinguish three types of recursion: linear recursive, linear iterative recursion, and tree recursion. Actually, these impressive-sounding terms are a change from the tone of the rest of the book, which is quite down-to-earth and jargon-free (as much as a book on programming can be). However, the distinction between linear recursive and linear iterative is never made quite clear. I thought the later was supposed to refer to tail recursion, but in the solution to an exercise on page 267 we see two tail-recursive implementations of a version of FIND, one labeled iterative and the other recursive.

There are repeated places where the terminology is not quite right. On page 12, Milner writes, ``A form is a single complete unit in a program. It begins and ends with parentheses.'' Steele (page 66) makes it clear that ``form'' as a technical term refers to any evaluable data object: it need not be in a program, and it need not have parentheses. On page 256, in a table of macro characters we see ``The accent acute is an abbreviation for the symbol QUOTE. The commercial ``at'' is used within a backquoted list.'' Actually, the quote mark is an abbreviation for a two-element list consisting of QUOTE and the next form read, and @ is not a macro character at all, although it is used within a backquoted list. Milner states that the characters ?![]{} may not be used in symbols, when in fact they can. PRIN1-TO-STRING is described as ``Outputs the object as PRIN1 does, but first makes it a string'' when in fact it does not do output. It sometimes seems that Milner is discussing an older dialect rather than Common Lisp: page 10 states ``CAR, CDR, and CONS are the basis for all Lisp functions.''

Perhaps the worst confusion is that symbols and variables are never clearly distinguished. On page 59 we see ``When a symbol is used within a function, a value is looked for first in the function, then in the package, and then in the system environment.'' This single sentence contains four major misconceptions: it equates symbols with variables, it assumes that a function is the only way to set up a local binding (even though LET is covered three pages later), it confuses packages and global bindings, and it assumes that the system package is used by all other packages.

On the positive side, the coverage of Common Lisp functions is quite thorough, and the range of examples inventive and usually good (except for the too-numerous bugs). There is a very good discussion of number syntax. There are well-chosen examples for MAPCAR, and for the tricky FORMAT function (although there is a bug in the use of ~T on page 333). There are a lot of answers to exercises (65 pages worth), and a nice appendix listing all the functions, variables, and constants in the language. However, there are a few omissions. For example, while we are told that ROUND returns two numbers, multiple values are never mentioned in the book. There are also occasional places where Milner shows the behavior of her version of Common Lisp without remarking that other implementations may vary. On page 169 she chose to illustrate the UNION function using #'< as the :TEST predicate. While using a non-equivalence relation as the predicate is a strange and confusing decision, I was able to determine from a careful reading of Steele that her explanation (and HP Lisp's results) were incorrect. Several other Common Lisps display the same bug; any Lisp implementors reading this are encouraged to check their implementation.

Here are a few examples of buggy code that I was able to find in a quick pass through the book (I've omitted a half dozen other bugs):

On page 181, the exercise is ``write a function that substitutes the symbol 'ZERO for each element that is equal to zero.'' The answer is:

    (defun nil-for-zero (a-list)
      (subst-if '(zero) '(lambda (x) (when (numberp x) (zerop x)))
		:key '(lambda (x) (if (atom x) x (car x)))))

This function is misnamed, has a misnamed argument, fails to use #' to properly create a function, is hopelessly convoluted, and is just plain incorrect:

    (nil-for-zero '(0 1))  =>  (zero)

I realize that Milner was trying to illustrate SUBST-IF, but a far better answer to the stated problem would be:

    (defun zero-for-0 (tree)
      (subst 'zero 0 tree))

In fact, even the question is buggy; it should have said the symbol ZERO; 'ZERO is an expression that evaluates to a symbol, but is not a symbol itself. There are other places where confusion between printed representation and internal form crops up. On page 222 we see ``If you consider the array a list, which it is internally, ...''. On page 143 Milner states that if you evaluate '(1 2 3), you create a list. Actually, it is when you READ '(1 2 3) that the list is created; evaluating the expression merely returns the list built by READ.

The two implementations of recursive FIND both contain bugs. The exercise is to find an atom even if it is nested in a subsequence of the top-level sequence. However, neither solution follows both branches of any branching subsequence. Furthermore, the solution allowing keywords does not work because, in true procedural fashion, Milner uses multiple SETQ's:

    (defun i-find (item seq &key (test #'eql) (test-not nil)
		   (start 0 s-flag) (end nil)
		   (key #'identity) (from-end nil))
      (if s-flag (setq seq (subseq seq start)))
      (if end (setq seq (subseq seq 0 end)))

and SEQ will be set improperly if :END is specified and :START is not 0. No mention is made of the fact that the solution is very inefficient if SEQ is not a list, and that there are alternative ways of processing vectors efficiently.

On page 356, an exercise asks the reader to write a function that reads each line of a file and prints the results. The solution reads expressions, not lines of text, and uses the symbol END as an end of file marker, and thus will terminate early for any file that contains the symbol END at top level.

On page 106, an exercise asks for a function with the following behavior:

   (build-it '(1 2 3))
     => ((x) (x x) (x x x))

The solution is:

    (defun round3 (x)
      (let ((result '()))
	(dotimes (n (length x) result)
	  (setq result (cons (car (nthcdr n x)) result)))))

    (defun build-it (arg-list)
      (let ((result '()))
	(dolist (a (round3 arg-list) result)
	  (setq result (cons (build1 a) result)))))

where BUILD1 was previously defined. The solution is technically correct, but I think it would be only fair to the novice programmer to mention that ROUND3 is just a convoluted implementation of REVERSE that would be better done with DOLIST, that PUSH would be appropriate here, that (CAR (NTHCDR N X)) is the same as (ELT X N), and that the whole thing could be better written as:

    (defun build-it (numbers)
      (mapcar #'build1 numbers))

In conclusion, "Common Lisp: A Tutorial" is grossly ill-informed, both at the level of technical detail and in the portrayal of general concepts. Although there are some nice examples of how to use individual functions, there is no guidance at a higher level, and there are too many errors for me to recommended this book to anyone.

				Peter Norvig
				Computer Science Department
				University of California, Berkeley
				Berkeley, California