NotesThis section is also intended as a bibliography. All the books and papers listed here shouldbe considered recommended reading.v Foderaro, John K. IntroductiontotheSpecialLispSection. CACM34,9 (September1991), p. 27.viii The final Prolog implementation is 94 lines of code. It uses 90 lines of utilities fromprevious chapters. TheATN compiler adds 33 lines, for a total of 217. Since Lisphas no formal notion of a line, there is a large margin for error when measuring thelength of a Lisp program in lines.ix Steele, Guy L., Jr. Common Lisp:theLanguage, 2nd Edition. DigitalPress, Bedford(MA), 1990.5 Brooks, Frederick P. The Mythical Man-Month. Addison-Wesley, Reading (MA),1975, p. 16.18 Abelson, Harold, and Gerald Jay Sussman, with Julie Sussman. Structure andInterpretation of Computer Programs. MIT Press, Cambridge, 1985.21 Moreprecisely, wecannot definearecursivefunctionwitha singlelambda-expression.We can, however, generate a recursive function by writing a function to take itselfas an additional argument,(setq fact#’(lambda (f n)(if (= n 0)1(* n (funcall f f (- n 1))))))and then passing it to a function that will return a closure in which original functionis called on itself:387388 NOTES(defun recurser (fn)#’(lambda (&rest args)(apply fn fn args)))Passing fact to this function yields a regular factorial function,> (funcall (recurser fact) 8)40320which could have been expressed directly as:((lambda (f) #’(lambda (n) (funcall f f n)))#’(lambda (f n)(if (= n 0)1(* n (funcall f f (- n 1))))))Many Common Lisp users will find labels or alambda more convenient.23 Gabriel, Richard P. Performance and Standardization. Proceedings of the FirstInternational Workshop on Lisp Evolution and Standardization, 1988, p. 60.Testing triangle in one implementation, Gabriel found that “even when the Ccompiler is provided with hand-generated register allocation information, the Lispcode is 17% faster than an iterative C version of this function.” His paper mentionsseveral other programs which ran faster in Lisp than in C, including one that was42% faster.24 If you wanted to compile all the named functions currently loaded, you could do itby calling compall:(defun compall ()(do-symbols (s)(when (fboundp s)(unless (compiled-function-p (symbol-function s))(print s)(compile s)))))This function also prints the name of each function as it is compiled.26 You may be able to see whether inline declarations are being obeyed by calling(disassemble ’foo), which displays some representation of the object code offunction foo. This is also one way to check whether tail-recursion optimization isbeing done.31 One could imagine nreverse defined as:(defun our-nreverse (lst)(if (null (cdr lst))lst(prog1 (nr2 lst)(setf (cdr lst) nil))))NOTES 389(defun nr2 (lst)(let ((c (cdr lst)))(prog1 (if (null (cdr c))c(nr2 c))(setf (cdr c) lst))))43 Good design always puts a premium on economy, but there is an additional reasonthat programs should be dense. When a program is dense, you can see more of it atonce.People know intuitively that design is easier when one has a broad view of one’swork. This is why easel painters use long-handled brushes, and often step backfrom their work. This is why generals position themselves on high ground, even ifthey are thereby exposed to enemy fire. And it is why programmers spend a lot ofmoney to look at their programs on large displays instead of small ones.Dense programs make the most of one’s field of vision. A general cannot shrink abattle to fit on a table-top, but Lisp allows you to perform corresponding feats ofabstraction in programs. And the more you can see of your program at once, themore likely it is to turn out as a unified whole.This is not to say that one should make one’s programs shorter at any cost. If youtake all the newlines out of a function, you can fit it on one line, but this does notmake it easier to read. Dense code means code which has been made smaller byabstraction, not text-editing.Imagine how hard it would be to program if you had to look at your code on adisplay half the size of the one you’re used to. Making your code twice as densewill make programming that much easier.44 Steele, Guy L., Jr. Debunking the “Expensive Procedure Call” Myth or, Procedu-ral Call Implementations Considered Harmful or, LAMBDA: The Ultimate GOTO.Proceedings of the National Conference of the ACM, 1977, p. 157.48 For reference, here are simpler definitions of some of the functions in Figures 4.2and 4.3. All are substantially (at least 10%) slower:(defun filter (fn lst)(delete nil (mapcar fn lst)))(defun filter (fn lst)(mapcan #’(lambda (x)(let ((val (funcall fn x)))(if val (list val))))lst))(defun group (source n)(if (endp source)nil(let ((rest (nthcdr n source)))(cons (if (consp rest) (subseq source 0 n) source)(group rest n)))))390 NOTES(defun flatten (x)(mapcan #’(lambda (x)(if (atom x) (mklist x) (flatten x)))x))(defun prune (test tree)(if (atom tree)tree(mapcar #’(lambda (x)(prune test x))(remove-if #’(lambda (y)(and (atom y)(funcall test y)))tree))))49 Written as it is, find2 will generate an error if it runs off the end of a dotted list:> (find2 #’oddp ’(2 . 3))>>Error: 3 is not a list.CLTL2 (p. 31) says that it is an error to give a dotted list to a function expecting alist. Implementations are not required to detect this error; some do, some don’t.The situation gets murky with functions that take sequences generally. A dottedlist is a cons, and conses are sequences, so a strict reading ofCLTL would seem torequire that(find-if #’oddp ’(2 . 3))return nil instead of generating an error, because find-if is supposed to take asequence as an argument.Implementations vary here. Some generate an error anyway, and others return nil.However, even implementations which follow the strict reading in the case abovetend to deviate in e.g. the case of (concatenate ’cons ’(a . b) ’(c . d)),which is likely to return (ac.d)instead of (a c).In this book, the utilities which expect lists expect proper lists. Those which operateon sequences will accept dotted lists. However, in general it would be asking fortrouble to pass dotted lists to any function that wasn’t specifically intended for useon them.66 If we could tell how many parameters each function had, we could write a version ofcompose so that, in f◦g, multiplevaluesreturned by gwould becomethe correspond-ing arguments to f. InCLTL2, the new function function-lambda-expressionreturns a