Preface ThisbookisintendedforanyonewhowantstobecomeabetterLispprogrammer. ItassumessomefamiliaritywithLisp,butnotnecessarilyextensiveprogramming experience. Thefirst few chapterscontaina 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,experiencedLispprogrammersbuild thelanguageuptowardtheirprograms. Thisbookteacheshowtoprograminthe bottom-upstyleforwhichLispisinherentlywell-suited. Bottom-up Design Bottom-updesignisbecomingmoreimportantassoftwaregrowsincomplexity. Programstodaymay haveto meet specificationswhich are extremelycomplex, orevenopen-ended. Undersuchcircumstances,thetraditionaltop-downmethod sometimes breaksdown. In its place therehas evolveda style of programming v vi PREFACE quite differentfromwhat is currentlytaughtin most computerscience courses: a bottom-upstyle in which a programis written as a series of layers, each one actingasasortofprogramminglanguagefortheoneabove. XWindowsandTEX areexamplesofprogramswritteninthisstyle. Thethemeofthisbookistwofold: thatLispisanaturallanguageforprograms written in the bottom-upstyle, and that the bottom-upstyle is a natural way to writeLisp programs. OnLisp will thusbeofinterestto twoclasses ofreaders. For people interested in writing extensibleprograms, this bookwill show what youcandoifyouhavetherightlanguage. ForLispprogrammers,thisbookoffers apracticalexplanationofhowtouseLisptoitsbestadvantage. The title is intended to stress the importanceof bottom-upprogrammingin Lisp. Instead of just writing your program in Lisp, you can write your own languageonLisp,andwriteyourprograminthat. It is possible to write programs bottom-upin any language, but Lisp is the mostnaturalvehicleforthisstyleofprogramming. InLisp,bottom-updesignis not a special techniquereservedfor unusuallylargeor difficult programs. Any substantialprogramwillbewrittenpartlyinthisstyle. Lispwasmeantfromthe start tobean extensiblelanguage. Thelanguageitself is mostlya collectionof Lispfunctions,nodifferentfromtheonesyoudefineyourself. What’smore,Lisp functionscan be expressedas lists, which are Lisp datastructures. 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 withafewexampleswhichhintatthestrangeandwonderfulthingsyoucando 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 confusematters 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 kindsofprogramsyoucouldwriteinanylanguage. OnLisp 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 anyother. But that kindof poweris 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,Idon’tmean“impossible”inthemathematicalsense,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 Sincefunctionsarethe foundationofLispprograms,thebookbeginswith 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. Theremainderofthebookdealsmorewith macrosthanfunctions. 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–18showsomeofthe 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 anaphoricmacros, which allow you to usepronounsinyourprograms. Chapter15showshowmacrosprovideamore 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 canbe usedto implementbothmultipleprocessesandnondeterministicchoice. Embeddingthese controlstructures in Lisp is discussed in Chapters 21 and22, respectively. Nondeterminism, which allows you to write programs as if they hadforesight,soundslikeanabstractionofunusualpower. Chapters23and24 presenttwoembeddedlanguageswhichshowthatnondeterminismlivesuptoits promise: acompleteATNparserandanembeddedPrologwhichcombinedtotal ◦ about200linesofcode. Thefactthattheseprogramsareshortmeansnothinginitself.Ifyouresortedto writingincomprehensiblecode,there’snotellingwhatyoucoulddoin200lines. Thepointis,theseprogramsarenotshortbecausetheydependonprogramming tricks,butbecausethey’rewrittenusingLispthewayit’smeanttobeused. The pointofChapters23and24is nothowtoimplementATNs inonepageofcode orPrologintwo,buttoshowthattheseprograms,whengiventheirmostnatural Lispimplementation,simplyarethatshort. Theembeddedlanguagesinthelatter chaptersprovideaproofbyexampleofthetwinpointswithwhichIbegan: that Lispis a naturallanguageforbottom-updesign,andthatbottom-updesignis a naturalwaytouseLisp. Thebookconcludeswith a discussionof object-orientedprogramming,and particularly CLOS, the Common Lisp Object System. By saving this topic till PREFACE ix last, we see more clearly the way in which object-oriented programmingis an extensionofideasalreadypresentinLisp. Itisoneofthemanyabstractionsthat canbebuiltonLisp. Achapter’sworthofnotesbeginsonpage387. Thenotescontainreferences, additionaloralternativecode,ordescriptionsofaspectsofLispnotdirectlyrelated tothepointathand. Notesareindicatedbyasmallcircleintheoutsidemargin, likethis. ThereisalsoanAppendix(page381)onpackages. ◦ JustasatourofNewYorkcouldbeatourofmostoftheworld’scultures,a studyofLispastheprogrammableprogramminglanguagedrawsinmostofLisp technique. MostofthetechniquesdescribedherearegenerallyknownintheLisp community,butmanyhavenottillnowbeenwrittendownanywhere. Andsome issues,suchastheproperroleofmacrosorthenatureofvariablecapture,areonly vaguelyunderstoodevenbymanyexperiencedLispprogrammers. Examples Lispisafamilyoflanguages. SinceCommonLisppromisestoremainawidely useddialect,mostoftheexamplesinthisbookareinCommonLisp. Thelanguage wasoriginallydefinedin1984bythepublicationofGuySteele’sCommonLisp: theLanguage(CLTL1). Thisdefinitionwassupersededin1990bythepublication ofthesecondedition(CLTL2),whichwillinturnyieldplacetotheforthcoming ◦ ANSIstandard. Thisbookcontainshundredsofexamples,rangingfromsingleexpressionsto aworkingPrologimplementation. Thecodeinthisbookhas,whereverpossible, beenwrittentoworkinanyversionofCommonLisp. Thosefewexampleswhich needfeaturesnotfoundinCLTL1implementationsareexplicitlyidentifiedinthe text. Later chapters contain some examples in Scheme. These too are clearly identified. ThecodeisavailablebyanonymousFTPfromendor.harvard.edu,where it’s in the directory pub/onlisp. Questions and comments can be sent to [email protected]. Acknowledgements WhilewritingthisbookIhavebeenparticularlythankfulforthehelpofRobert Morris. IwenttohimconstantlyforadviceandwasalwaysgladIdid. Several oftheexamplesinthisbookarederivedfromcodeheoriginallywrote,including the version of for on page 127, the version of aand on page 191, match on page239,thebreadth-firsttrue-chooseonpage304,andtheProloginterpreter x PREFACE inSection24.2. Infact,thewholebookreflects(sometimes,indeed,transcribes) conversationsI’vehadwithRobertduringthepastsevenyears. (Thanks,rtm!) IwouldalsoliketogivespecialthankstoDavidMoon,whoreadlargeparts ofthemanuscriptwithgreatcare,andgavemeveryusefulcomments. Chapter12 wascompletelyrewrittenathissuggestion,andtheexampleofvariablecapture onpage119isonethatheprovided. Iwas fortunatetohaveDavidTouretzkyandSkonaBrittainas thetechnical reviewersforthebook. Severalsectionswereaddedorrewrittenattheirsugges- tion. Thealternativetruenondeterministicchoiceoperatoronpage397isbased onasuggestionbyDavidToureztky. Severalotherpeopleconsentedtoreadallorpartofthemanuscript,including Tom Cheatham, Richard Draves (who also rewrote alambda and propmacro back in 1985), John Foderaro, David Hendler, George Luger, Robert Muller, MarkNitzberg,andGuySteele. I’mgratefultoProfessorCheatham,andHarvardgenerally,forprovidingthe facilitiesusedtowritethisbook. ThanksalsotothestaffatAikenLab,including TonyHartman,JanuszJuda,HarryBochner,andJoanneKlys. Thepeopleat PrenticeHall did agreat job. I feelfortunateto haveworked with Alan Apt, a good editor and a good guy. Thanks also to Mona Pompili, ShirleyMichaels,andShirleyMcGuirefortheirorganizationandgoodhumor. TheincomparableGinoLeeoftheBowandArrowPress,Cambridge,didthe cover. Thetreeonthecoveralludesspecificallytothepointmadeonpage27. ThisbookwastypesetusingLATEX,alanguagewrittenbyLeslieLamportatop DonaldKnuth’s TEX, with additionalmacrosby L. A. Carr, Van Jacobson, and Guy Steele. The diagrams were done with Idraw, by John Vlissides and Scott Stanton. The whole was previewedwith Ghostview, by Tim Theisen, which is builtonGhostscript,byL.PeterDeutsch. GaryBisbeeofChironInc.produced thecamera-readycopy. I owe thanks to many others, including Paul Becker, Phil Chapnick, Alice Hartley, Glenn Holloway, Meichun Hsu, Krzysztof Lenk, Arman Maghbouleh, HowardMullings,NancyParmet,RobertPenny,GarySabot,PatrickSlaney,Steve Strassman,DaveWatkins,theWeickers,andBillWoods. Mostofall,I’dliketothankmyparents,fortheirexampleandencouragement; andJackie,whotaughtmewhatImighthavelearnedifIhadlistenedtothem. Ihopereadingthisbookwillbefun. OfallthelanguagesIknow,IlikeLisp the best, simply because it’s the most beautiful. This book is about Lisp at its lispiest. Ihadfunwritingit,andIhopethatcomesthroughinthetext. PaulGraham Contents 1. TheExtensibleLanguage 1 4.4. Search 48 4.5. Mapping 53 1.1. DesignbyEvolution 1 4.6. I/O 56 1.2. ProgrammingBottom-Up 3 4.7. SymbolsandStrings 57 1.3. ExtensibleSoftware 5 4.8. Density 59 1.4. ExtendingLisp 6 1.5. WhyLisp(orWhen) 8 5. ReturningFunctions 61 2. Functions 9 5.1. CommonLispEvolves 61 2.1. FunctionsasData 9 5.2. Orthogonality 63 2.2. DefiningFunctions 10 5.3. Memoizing 65 2.3. FunctionalArguments 13 5.4. ComposingFunctions 66 2.4. FunctionsasProperties 15 5.5. RecursiononCdrs 68 2.5. Scope 16 5.6. RecursiononSubtrees 70 2.6. Closures 17 5.7. WhentoBuildFunctions 75 2.7. LocalFunctions 21 2.8. Tail-Recursion 22 6. FunctionsasRepresentation 76 2.9. Compilation 24 6.1. Networks 76 2.10. FunctionsfromLists 27 6.2. CompilingNetworks 79 6.3. LookingForward 81 3. FunctionalProgramming 28 3.1. FunctionalDesign 28 7. Macros 82 3.2. ImperativeOutside-In 33 7.1. HowMacrosWork 82 3.3. FunctionalInterfaces 35 7.2. Backquote 84 3.4. InteractiveProgramming 37 7.3. DefiningSimpleMacros 88 7.4. TestingMacroexpansion 91 4. UtilityFunctions 40 7.5. DestructuringinParameter 4.1. BirthofaUtility 40 Lists 93 4.2. InvestinAbstraction 43 7.6. AModelofMacros 95 4.3. OperationsonLists 44 7.7. MacrosasPrograms 96 xi xii CONTENTS 7.8. MacroStyle 99 12.2. TheMultipleEvaluation 7.9. DependenceonMacros 101 Problem 167 7.10. MacrosfromFunctions 102 12.3. NewUtilities 169 7.11. SymbolMacros 105 12.4. MoreComplexUtilities 171 12.5. DefiningInversions 178 8. WhentoUseMacros 106 8.1. WhenNothingElseWill 13. Computationat Do 106 Compile-Time 181 8.2. MacroorFunction? 109 13.1. NewUtilities 181 8.3. ApplicationsforMacros 111 13.2. Example: BezierCurves 185 13.3. Applications 186 9. VariableCapture 118 9.1. MacroArgumentCapture 118 14. AnaphoricMacros 189 9.2. FreeSymbolCapture 119 9.3. WhenCaptureOccurs 121 14.1. AnaphoricVariants 189 9.4. AvoidingCapturewithBetter 14.2. Failure 195 Names 125 14.3. ReferentialTransparency 198 9.5. AvoidingCapturebyPrior Evaluation 125 15. MacrosReturning 9.6. AvoidingCapturewith Functions 201 Gensyms 128 9.7. AvoidingCapturewith 15.1. BuildingFunctions 201 Packages 130 15.2. RecursiononCdrs 204 9.8. CaptureinOther 15.3. RecursiononSubtrees 208 Name-Spaces 130 15.4. LazyEvaluation 211 9.9. WhyBother? 132 16. Macro-DefiningMacros 213 10. OtherMacroPitfalls 133 16.1. Abbreviations 213 10.1. NumberofEvaluations 133 16.2. Properties 216 10.2. OrderofEvaluation 135 16.3. AnaphoricMacros 218 10.3. Non-functionalExpanders 136 10.4. Recursion 139 17. Read-Macros 224 11. ClassicMacros 143 17.1. MacroCharacters 224 17.2. DispatchingMacro 11.1. CreatingContext 143 Characters 226 11.2. Thewith-Macro 147 17.3. Delimiters 227 11.3. ConditionalEvaluation 150 17.4. WhenWhatHappens 229 11.4. Iteration 154 11.5. IterationwithMultiple Values 158 18. Destructuring 230 11.6. NeedforMacros 161 18.1. DestructuringonLists 230 18.2. OtherStructures 231 12. GeneralizedVariables 165 18.3. Reference 236 12.1. TheConcept 165 18.4. Matching 238 CONTENTS xiii 19. AQueryCompiler 246 24.7. Examples 344 24.8. TheSensesofCompile 346 19.1. TheDatabase 247 19.2. Pattern-MatchingQueries 248 25. Object-OrientedLisp 348 19.3. AQueryInterpreter 250 19.4. RestrictionsonBinding 252 25.1. Plusc¸aChange 348 19.5. AQueryCompiler 254 25.2. ObjectsinPlainLisp 349 25.3. ClassesandInstances 364 20. Continuations 258 25.4. Methods 368 25.5. AuxiliaryMethodsand 20.1. SchemeContinuations 258 Combination 374 20.2. Continuation-Passing 25.6. CLOSandLisp 377 Macros 266 25.7. WhentoObject 379 20.3. Code-WalkersandCPS Conversion 272 21. MultipleProcesses 275 21.1. TheProcessAbstraction 275 21.2. Implementation 277 21.3. TheLess-than-Rapid Prototype 284 22. Nondeterminism 286 22.1. TheConcept 286 22.2. Search 290 22.3. SchemeImplementation 292 22.4. CommonLisp Implementation 294 22.5. Cuts 298 22.6. TrueNondeterminism 302 23. ParsingwithATNs 305 23.1. Background 305 23.2. TheFormalism 306 23.3. Nondeterminism 308 23.4. AnATNCompiler 309 23.5. ASampleATN 314 24. Prolog 321 24.1. Concepts 321 24.2. AnInterpreter 323 24.3. Rules 329 24.4. TheNeedfor Nondeterminism 333 24.5. NewImplementation 334 24.6. AddingPrologFeatures 337