1、PrefaceThis book is intended for anyone who wants to become a better Lisp programmer.It assumes some familiarity with Lisp, but not necessarily extensive programmingexperience. The first few chapters contain a fair amount of review. I hope thatthese sections will be interesting to more experienced L
2、isp programmers as well,because they present familiar subjects in a new light.Its difficult to convey the essence of a programming language in one sentence,but John Foderaro has come close:Lisp is a programmable programming language.There is more to Lisp than this, but the ability to bend Lisp to on
3、es will is alarge part of what distinguishes a Lisp expert from a novice. As well as writingtheir programs down toward the language, experienced Lisp programmers buildthe language up toward their programs. This book teaches how to program in thebottom-up style for which Lisp is inherently well-suite
4、d.Bottom-up DesignBottom-up design is becoming more important as software grows in complexity.Programs today may have to meet specifications which are extremely complex,or even open-ended. Under such circumstances, the traditional top-down methodsometimes breaks down. In its place there has evolved
5、a style of programmingvvi PREFACEquite different from what is currently taught in most computer science courses:a bottom-up style in which a program is written as a series of layers, each oneacting as a sort of programming language for the one above. X Windows and TEXare examples of programs written
6、 in this style.The theme of this book is twofold: that Lisp is a natural language for programswritten in the bottom-up style, and that the bottom-up style is a natural way towrite Lisp programs. On Lisp will thus be of interest to two classes of readers.For people interested in writing extensible pr
7、ograms, this book will show whatyou can do if you have the right language. For Lisp programmers, this book offersa practical explanation of how to use Lisp to its best advantage.The title is intended to stress the importance of bottom-up programming inLisp. Instead of just writing your program in Li
8、sp, you can write your ownlanguage on Lisp, and write your program in that.It is possible to write programs bottom-up in any language, but Lisp is themost natural vehicle for this style of programming. In Lisp, bottom-up design isnot a special technique reserved for unusually large or difficult prog
9、rams. Anysubstantial program will be written partly in this style. Lisp was meant from thestart to be an extensible language. The language itself is mostly a collection ofLisp functions, no different from the ones you define yourself. Whats more, Lispfunctions can be expressed as lists, which are Li
10、sp data structures. This meansyou can write Lisp functions which generate Lisp code.A good Lisp programmer must know how to take advantage of this possibility.The usual way to do so is by defining a kind of operator called a macro. Masteringmacros is one of the most important steps in moving from wr
11、iting correct Lispprograms to writing beautiful ones. Introductory Lisp books have room for nomore than a quick overview of macros: an explanation of what macros are,togetherwith a few examples which hint at the strange and wonderful things you can dowith them. Those strange and wonderful things wil
12、l receive special attention here.One of the aims of this book is to collect in one place all that people have till nowhad to learn from experience about macros.Understandably, introductory Lisp books do not emphasize the differencesbetween Lisp and other languages. They have to get their message acr
13、oss tostudents who have, for the most part, been schooled to think of programs in Pascalterms. It would only confuse matters to explain that, while defun looks like aprocedure definition, it is actually a program-writing program that generates codewhich builds a functional object and indexes it unde
14、r the symbol given as the firstargument.One of the purposes of this book is to explain what makes Lisp different fromother languages. When I began, I knew that, all other things being equal, I wouldmuch rather write programs in Lisp than in C or Pascal or Fortran. I knew also thatthis was not merely
15、 a question of taste. But I realized that if I was actually goingPREFACE viito claim that Lisp was in some ways a better language, I had better be prepared toexplain why.When someone asked Louis Armstrong what jazz was, he replied “If you haveto ask what jazz is, youll never know.” But he did answer
16、 the question in a way:he showed people what jazz was. Thats one way to explain the power of Lisptodemonstrate techniques that would be difficult or impossible in other languages.Most books on programmingeven books on Lisp programmingdeal with thekinds of programs you could write in any language. On
17、 Lisp deals mostly withthe kinds of programs you could only write in Lisp. Extensibility, bottom-upprogramming, interactive development, source code transformation, embeddedlanguagesthis is where Lisp shows to advantage.In principle, of course, any Turing-equivalent programming language can dothe sa
18、me things as any other. But that kind of power is not what programminglanguages are about. In principle, anything you can do with a programminglanguage you can do with a Turing machine; in practice, programming a Turingmachine is not worth the trouble.So when I say that this book is about how to do
19、things that are impossiblein other languages, I dont mean “impossible” in the mathematical sense, but inthe sense that matters for programming languages. That is, if you had to writesome of the programs in this book in C, you might as well do it by writing a Lispcompiler in C first. Embedding Prolog
20、 in C, for examplecan you imagine theamount of work that would take? Chapter 24 shows how to do it in 180 lines ofLisp.I hoped to do more than simply demonstrate the power of Lisp, though. I alsowanted to explain why Lisp is different. This turns out to be a subtle questiontoosubtle to be answered w
21、ith phrases like “symbolic computation.” What I havelearned so far, I have tried to explain as clearly as I can.Plan of the BookSince functions are the foundation of Lisp programs, the book begins with sev-eral chapters on functions. Chapter 2 explains what Lisp functions are and thepossibilities th
22、ey offer. Chapter 3 then discusses the advantages of functionalprogramming, the dominant style in Lisp programs. Chapter 4 shows how to usefunctions to extend Lisp. Then Chapter 5 suggests the new kinds of abstractionswe can define with functions that return other functions. Finally, Chapter 6 shows
23、how to use functions in place of traditional data structures.The remainder of the book deals more with macros than functions. Macrosreceive more attention partly because there is more to say about them, and partlybecause they have not till now been adequately described in print. Chapters 710viii PRE
24、FACEform a complete tutorial on macro technique. By the end of it you will know mostof what an experienced Lisp programmer knows about macros: how they work;how to define, test, and debug them; when to use macros and when not; the majortypes of macros; how to write programs which generate macro expa
25、nsions; howmacro style differs from Lisp style in general; and how to detect and cure each ofthe unique problems that afflict macros.Following this tutorial, Chapters 1118 show some of the powerful abstrac-tions you can build with macros. Chapter 11 shows how to write the classicmacrosthose which cr
26、eate context, or implement loops or conditionals. Chap-ter 12 explains the role of macros in operations on generalized variables. Chap-ter 13 shows how macros can make programs run faster by shifting computationto compile-time. Chapter 14 introduces anaphoric macros, which allow you touse pronouns i
27、n your programs. Chapter 15 shows how macros provide a moreconvenient interface to the function-builders defined in Chapter 5. Chapter 16shows how to use macro-defining macros to make Lisp write your programs foryou. Chapter 17 discusses read-macros, and Chapter 18, macros for destructuring.With Cha
28、pter 19 begins the fourth part of the book, devoted to embeddedlanguages. Chapter 19 introduces the subject by showing the same program, aprogram to answer queries on a database, implemented first by an interpreterand then as a true embedded language. Chapter 20 shows how to introduceinto Common Lis
29、p programs the notion of a continuation, an object representingthe remainder of a computation. Continuations are a very powerful tool, andcan be used to implement both multiple processes and nondeterministic choice.Embedding these control structures in Lisp is discussed in Chapters 21 and 22,respect
30、ively. Nondeterminism, which allows you to write programs as if theyhad foresight, sounds like an abstraction of unusual power. Chapters 23 and 24present two embedded languages which show that nondeterminism lives up to itspromise: a complete ATN parser and an embedded Prolog which combined totalabo
31、ut 200 lines of code.The fact that these programs are short means nothing in itself. If you resorted towriting incomprehensible code, theres no telling what you could do in 200 lines.The point is, these programs are not short because they depend on programmingtricks, but because theyre written using
32、 Lisp the way its meant to be used. Thepoint of Chapters 23 and 24 is not how to implement ATNs in one page of codeor Prolog in two, but to show that these programs, when given their most naturalLisp implementation, simply are that short. The embedded languages in the latterchapters provide a proof
33、by example of the twin points with which I began: thatLisp is a natural language for bottom-up design, and that bottom-up design is anatural way to use Lisp.The book concludes with a discussion of object-oriented programming, andparticularly CLOS, the Common Lisp Object System. By saving this topic
34、tillPREFACE ixlast, we see more clearly the way in which object-oriented programming is anextension of ideas already present in Lisp. It is one of the many abstractions thatcan be built on Lisp.A chapters worth of notes begins on page 387. The notes contain references,additional or alternative code,
35、 or descriptions of aspects of Lisp not directly relatedto the point at hand. Notes are indicated by a small circle in the outside margin,like this. There is also an Appendix (page 381) on packages. Just as a tour of New York could be a tour of most of the worlds cultures, astudy of Lisp as the prog
36、rammable programming language draws in most of Lisptechnique. Most of the techniques described here are generally known in the Lispcommunity, but many have not till now been written down anywhere. And someissues, such as the proper role of macros or the nature of variable capture, are onlyvaguely un
37、derstood even by many experienced Lisp programmers.ExamplesLisp is a family of languages. Since Common Lisp promises to remain a widelyused dialect, most of the examples in this book are in Common Lisp. The languagewas originally defined in 1984 by the publication of Guy Steeles Common Lisp:the Lang
38、uage (CLTL1). This definition was superseded in 1990 by the publicationof the second edition (CLTL2), which will in turn yield place to the forthcoming ANSI standard.This book contains hundreds of examples, ranging from single expressions toa working Prolog implementation. The code in this book has,
39、 wherever possible,been written to work in any version of Common Lisp. Those few examples whichneed features not found in CLTL1 implementations are explicitly identified in thetext. Later chapters contain some examples in Scheme. These too are clearlyidentified.The code is available by anonymous FTP
40、 from endor.harvard.edu, whereits in the directory pub/onlisp. Questions and comments can be sent toonlispdas.harvard.edu.AcknowledgementsWhile writing this book I have been particularly thankful for the help of RobertMorris. I went to him constantly for advice and was always glad I did. Severalof t
41、he examples in this book are derived from code he originally wrote, includingthe version of for on page 127, the version of aand on page 191, match onpage 239, the breadth-first true-choose on page 304, and the Prolog interpreterx PREFACEin Section 24.2. In fact, the whole book reflects (sometimes,
42、indeed, transcribes)conversations Ive had with Robert during the past seven years. (Thanks, rtm!)I would also like to give special thanks to David Moon, who read large partsof the manuscript with great care, and gave me very useful comments. Chapter 12was completely rewritten at his suggestion, and
43、the example of variable captureon page 119 is one that he provided.I was fortunate to have David Touretzky and Skona Brittain as the technicalreviewers for the book. Several sections were added or rewritten at their sugges-tion. The alternative true nondeterministic choice operator on page 397 is ba
44、sedon a suggestion by David Toureztky.Several other people consented to read all or part of the manuscript, includingTom Cheatham, Richard Draves (who also rewrote alambda and propmacroback in 1985), John Foderaro, David Hendler, George Luger, Robert Muller,Mark Nitzberg, and Guy Steele.Im grateful
45、to Professor Cheatham, and Harvard generally, for providing thefacilities used to write this book. Thanks also to the staff at Aiken Lab, includingTony Hartman, Janusz Juda, Harry Bochner, and Joanne Klys.The people at Prentice Hall did a great job. I feel fortunate to have workedwith Alan Apt, a go
46、od editor and a good guy. Thanks also to Mona Pompili,Shirley Michaels, and Shirley McGuire for their organization and good humor.The incomparable Gino Lee of the Bow and Arrow Press, Cambridge, did thecover. The tree on the cover alludes specifically to the point made on page 27.This book was types
47、et using LATEX, a language written by Leslie Lamport atopDonald Knuths TEX, with additional macros by L. A. Carr, Van Jacobson, andGuy Steele. The diagrams were done with Idraw, by John Vlissides and ScottStanton. The whole was previewed with Ghostview, by Tim Theisen, which isbuilt on Ghostscript,
48、by L. Peter Deutsch. Gary Bisbee of Chiron Inc. producedthe camera-ready copy.I owe thanks to many others, including Paul Becker, Phil Chapnick, AliceHartley, Glenn Holloway, Meichun Hsu, Krzysztof Lenk, Arman Maghbouleh,Howard Mullings, Nancy Parmet, Robert Penny, Gary Sabot, Patrick Slaney, SteveS
49、trassman, Dave Watkins, the Weickers, and Bill Woods.Most of all, Id like to thank my parents, for their example and encouragement;and Jackie, who taught me what I might have learned if I had listened to them.I hope reading this book will be fun. Of all the languages I know, I like Lispthe best, simply because its the most beautiful. This book is about Lisp at itslispiest. I had fun writing it, and I hope that comes through in the text.Paul GrahamContents1. The Extensible Language 11.1. Design by Evolution 11.2. Programming Bottom-Up 31.3. Extensible Software 51.
