0 � -· en -a 0 )> .. n< 0 :s 3 n 3 Q. 0 :s - -- - _, H i titlepage ii copyrightpage Tomy family,and toJackie. iv λ Preface ThisbookisintendedforanyonewhowantstobecomeabetterLispprogrammer. ItassumessomefamiliaritywithLisp,butnotnecessarilyextensiveprogramming experience. Thefirst few chapterscontain a fair amountof review. I hopethat thesesectionswillbeinterestingtomoreexperiencedLispprogrammersaswell, becausetheypresentfamiliarsubjectsinanewlight. It’sdifficulttoconveytheessenceofaprogramminglanguageinonesentence, butJohnFoderarohascomeclose: Lispisaprogrammableprogramminglanguage. There is more to Lisp than this, but the ability to bend Lisp to one’s will is a largepartofwhatdistinguishesaLispexpertfromanovice. Aswellaswriting theirprogramsdowntowardthelanguage,experiencedLisp programmersbuild thelanguageuptowardtheirprograms. Thisbookteacheshowtoprograminthe bottom-upstyleforwhichLispisinherentlywell-suited. Bottom-up Design Bottom-updesignisbecomingmoreimportantassoftwaregrowsincomplexity. Programstoday may have to meet specificationswhich are extremely complex, orevenopen-ended. Undersuchcircumstances,thetraditionaltop-downmethod sometimes breaksdown. In its place there has evolveda style of programming v vi PREFACE quite differentfrom what is currently taughtin most computerscience courses: a bottom-up style in which a program is written as a series of layers, each one actingasasortofprogramminglanguagefortheoneabove. XWindowsandTEX areexamplesofprogramswritteninthisstyle. Thethemeofthisbookistwofold: thatLispisanaturallanguageforprograms written in the bottom-upstyle, and that the bottom-up style is a natural way to write Lisp programs. On Lisp will thusbe of interestto two classes of readers. For people interested in writing extensible programs, this book will show what youcandoifyouhavetherightlanguage. ForLispprogrammers,thisbookoffers apracticalexplanationofhowtouseLisptoitsbestadvantage. The title is intended to stress the importance of bottom-up programmingin Lisp. Instead of just writing your program in Lisp, you can write your own languageonLisp,andwriteyourprograminthat. It is possible to write programs bottom-up in any language, but Lisp is the mostnaturalvehicleforthisstyleofprogramming. InLisp,bottom-updesignis not a special technique reserved for unusually large or difficult programs. Any substantialprogramwillbewrittenpartlyinthisstyle. Lispwasmeantfromthe start to be an extensiblelanguage. The languageitself is mostly a collectionof Lispfunctions,nodifferentfromtheonesyoudefineyourself. What’smore,Lisp functionscan be expressedas lists, which are Lisp data structures. This means youcanwriteLispfunctionswhichgenerateLispcode. AgoodLispprogrammermustknowhowtotakeadvantageofthispossibility. Theusualwaytodosoisbydefiningakindofoperatorcalleda macro. Mastering macros is one of the most importantsteps in movingfrom writing correctLisp programsto writing beautiful ones. IntroductoryLisp books have room for no morethanaquickoverviewofmacros:anexplanationofwhatmacrosare,together witha fewexampleswhichhintatthe strangeandwonderfulthingsyoucando withthem. Thosestrangeandwonderfulthingswillreceivespecialattentionhere. Oneoftheaimsofthisbookistocollectinoneplaceallthatpeoplehavetillnow hadtolearnfromexperienceaboutmacros. Understandably, introductory Lisp books do not emphasize the differences between Lisp and other languages. They have to get their message across to studentswhohave,forthemostpart,beenschooledtothinkofprogramsinPascal terms. It would only confuse matters to explain that, while defun looks like a proceduredefinition,itisactuallyaprogram-writingprogramthatgeneratescode whichbuildsafunctionalobjectandindexesitunderthesymbolgivenasthefirst argument. OneofthepurposesofthisbookistoexplainwhatmakesLispdifferentfrom otherlanguages. WhenIbegan,Iknewthat,allotherthingsbeingequal,Iwould muchratherwriteprogramsinLispthaninCorPascalorFortran. Iknewalsothat thiswasnotmerelyaquestionoftaste. ButIrealizedthatifIwasactuallygoing PREFACE vii toclaimthatLispwasinsomewaysabetterlanguage,Ihadbetterbepreparedto explainwhy. WhensomeoneaskedLouisArmstrongwhatjazzwas,hereplied“Ifyouhave toaskwhatjazzis,you’llneverknow.” Buthedidanswerthequestioninaway: heshowedpeoplewhatjazzwas. That’sonewaytoexplainthepowerofLisp—to demonstratetechniquesthatwouldbedifficultorimpossibleinotherlanguages. Mostbooksonprogramming—evenbooksonLispprogramming—dealwiththe kindsof programsyoucouldwrite in any language. On Lisp dealsmostlywith the kinds of programs you could only write in Lisp. Extensibility, bottom-up programming, interactive development, source code transformation, embedded languages—thisiswhereLispshowstoadvantage. Inprinciple,ofcourse,anyTuring-equivalentprogramminglanguagecando the same things as any other. But that kind of power is not what programming languages are about. In principle, anything you can do with a programming languageyoucandowithaTuringmachine;inpractice,programmingaTuring machineisnotworththetrouble. So when I say that this book is about how to do things that are impossible inotherlanguages,I don’tmean“impossible”in themathematicalsense, butin the sense that matters for programminglanguages. That is, if you had to write someoftheprogramsinthisbookinC,youmightaswelldoitbywritingaLisp compilerinCfirst. EmbeddingProloginC, forexample—canyouimaginethe amountofworkthatwouldtake? Chapter24showshowtodoitin180linesof Lisp. IhopedtodomorethansimplydemonstratethepowerofLisp,though. Ialso wantedtoexplainwhyLispisdifferent. Thisturnsouttobeasubtlequestion—too subtle to be answered with phrases like “symbolic computation.” What I have learnedsofar,IhavetriedtoexplainasclearlyasIcan. PlanoftheBook Since functionsare the foundationof Lisp programs, the bookbeginswith sev- eral chapters on functions. Chapter 2 explains what Lisp functions are and the possibilities they offer. Chapter 3 then discusses the advantages of functional programming,thedominantstyleinLispprograms. Chapter4showshowtouse functionstoextendLisp. ThenChapter5suggeststhenewkindsofabstractions wecandefinewithfunctionsthatreturnotherfunctions. Finally,Chapter6shows howtousefunctionsinplaceoftraditionaldatastructures. The remainderof the book dealsmore with macrosthan functions. Macros receivemoreattentionpartlybecausethereismoretosayaboutthem,andpartly becausetheyhavenottillnowbeenadequatelydescribedinprint. Chapters7–10 viii PREFACE formacompletetutorialonmacrotechnique. Bytheendofityouwillknowmost ofwhatanexperiencedLispprogrammerknowsaboutmacros: howtheywork; howtodefine,test,anddebugthem;whentousemacrosandwhennot;themajor typesofmacros;howtowriteprogramswhichgeneratemacroexpansions;how macrostylediffersfromLispstyleingeneral;andhowtodetectandcureeachof theuniqueproblemsthatafflictmacros. Followingthis tutorial, Chapters11–18show some of the powerfulabstrac- tions you can build with macros. Chapter 11 shows how to write the classic macros—thosewhichcreatecontext,orimplementloopsorconditionals. Chap- ter12explainstheroleofmacrosinoperationsongeneralizedvariables. Chap- ter13showshowmacroscanmakeprogramsrunfasterbyshiftingcomputation to compile-time. Chapter 14 introduces anaphoric macros, which allow you to use pronounsin yourprograms. Chapter15showshowmacrosprovidea more convenient interface to the function-buildersdefined in Chapter 5. Chapter 16 showshowtousemacro-definingmacrostomakeLispwriteyourprogramsfor you. Chapter17discussesread-macros,andChapter18,macrosfordestructuring. With Chapter 19 begins the fourth part of the book, devoted to embedded languages. Chapter 19 introduces the subject by showing the same program, a program to answer queries on a database, implemented first by an interpreter and then as a true embedded language. Chapter 20 shows how to introduce intoCommonLispprogramsthenotionofacontinuation,anobjectrepresenting the remainder of a computation. Continuations are a very powerful tool, and can be used to implementboth multipleprocessesand nondeterministicchoice. Embeddingthese controlstructures in Lisp is discussed in Chapters 21 and 22, respectively. Nondeterminism, which allows you to write programs as if they hadforesight,soundslike an abstractionof unusualpower. Chapters23and24 presenttwoembeddedlanguageswhichshowthatnondeterminismlivesuptoits promise: acompleteATNparserandanembeddedPrologwhichcombinedtotal about200linesofcode. ◦ Thefactthattheseprogramsareshortmeansnothinginitself.Ifyouresortedto writingincomprehensiblecode,there’snotellingwhatyoucoulddoin200lines. Thepointis,theseprogramsarenotshortbecausetheydependonprogramming tricks,butbecausethey’rewrittenusingLispthewayit’smeanttobeused. The pointof Chapters23and 24 is nothow to implementATNs in one pageof code orPrologintwo,buttoshowthattheseprograms,whengiventheirmostnatural Lispimplementation,simplyarethatshort. Theembeddedlanguagesinthelatter chaptersprovideaproofbyexampleofthetwinpointswithwhichIbegan: that Lisp is a naturallanguageforbottom-updesign, and thatbottom-updesignis a naturalwaytouseLisp. The bookconcludeswith a discussion of object-orientedprogramming,and particularly CLOS, the Common Lisp Object System. By saving this topic till