nils m holm zen style ppprrrooogggrrraaammmmmmiiinnnggg zen style programming Copyright (C)2008NilsM Holm All rightsreserved Print and distribution:Lulu Press,Inc Order: http://www.lulu.com/nmh/ preface A program is a description of an abstract, general solution to a specific problem. It is typically written in a formal language called a programminglanguage.The primarypurpose of a program is to be understood by fellow human beings, thereby spreading knowledge. In order to achieve maximalreadability,aprogramminglanguageshouldhavecertainproperties: 1. Itshouldbesmallanduniform; 2. Itshouldbefreefromambiguity; 3. Itshouldprovideahighdegreeof abstraction; 4. Itshouldbeindependentfromconcretecomputerarchitectures. Thefirstpointsareno-brainers.If alanguageistoocomplexorhasnouniformsyntaxandseman- tics,programmerswillhavetolookupthingsinthemanualperpetuallyinsteadof concentratingon theactualproblem.Ifthelanguageintroducesambiguity,peoplewilleventuallychooseonepossible outcomeinternallyandstartwritingprogramsthatdependontheirimaginationinsteadof facts. A high degree of abstraction means that the language should provide means of dealing with recurringtasksgracefullyandwithouthavingtoreinventthewheeloverandoveragain.Thismay seemlikeacontradictionto1.,butthistextwillshowthatthisdoesnothavetobethecase. A programming language that is used to describe algorithms in a readable way must be fully architecture-neutral. As soon as the language depends on features of a particular machine, the first principle is violated,because the knowledge that is necessary to understand a program then includestheknowledgeof theunderlyingarchitecture. Thefirstpartof thisbookintroducestheconceptof functionalprogramming,describesalanguage thatfulfillsallof theaboverequirements,andshowshowtosolvesimpleproblemsinit. Oncea languagehasbeen chosen,it can be used toformulatesolutionstoallkindsof logicprob- lems.Programmingis limited to solutionsof logic problems,because it cannot anwser questions like‘‘howcanwelearntolivein peace?’’and ‘‘whyislifeworthliving?’’.Thesearethelimitsof science as we know it.The class of problemsthat can be solved by programsis much smaller.It typicallyinvolvesveryclearlydefinedtaskslike --findpermutationsof aset; --findfactorsof aninteger; --representaninfinitesequence; --translateformallanguageAtolanguageB; --findapatterninasequenceof characters; --solveasystemof assertions. Of course these tasks have to be defined in much greater detail in order to be able to solve them programmatically.Thisiswhat thesecond part of the book isabout:creatinggeneralsolutionsto logicproblems. Thelanguagethatwillbeusedinthisbook isaminimalisticvariantof Schemecalledzenlisp.Its onlydata typesaresymbolsand ordered pairs.Nothingelseisrequiredtodescribealgorithmsfor solvingallof thelogicproblemslistedabove.Thelanguagemayappearuselesstoyou,becauseit doesnot provideanyaccessto‘‘real-world’’applicationprogram interfacesand it cannot be used to write interactive programs, but I have chosen this language on purpose: it demonstrates that programmingdoesnotdependonthesefeatures. Thesecondpartof thebook showshowtoapplythetechniquesof thefirstparttosomeproblems of varying complexity.The topics discussed in this part range from simple functions for sorting or permuting lists to regular expression matching, formal language translation, and declarative programming. It contains the full source code to a source-to-source compiler, a meta-circular interpreterandalogicprogrammingsystem. The third part,finally,showshow toimplement the abstractionlayer that isnecessaryfor solving problems in an abstract way on a concrete computer. It reproduces the complete and heavily annotatedsourcecodeforaninterpreterof zenlisp. The first chapter of this part strives to deliver an example of readable code in a language that is not suitable for abstraction.It attempts to develop a programming style that does not depend on annotations to make the intention of the programmer clear.Comments are interspersed between functions,though,becauseproseisstilleasiertoreadthanimperativecode. At this point the tour ends.It starts with an abstract and purely symbolic view on programming, advancesto the application of symbolicprogrammingto more complex problems,and concludes withtheimplementationof asymbolicprogrammingsystemonactualcomputersystems. Ihopethatyouwillenjoythetour! NilsMHolm,September2008 contents part one:symbolic programming . . . . . . . . . . . . . . . . . 9 1. basicaspects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1 symbolsandvariables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1 callingfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 functioncomposition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 conditions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 recursion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 formsandexpressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.5.1 lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.5.2 forms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5.3 expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.6 recursionoverlists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2. moreinterestingaspects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1 variadicfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2 equalityandidentity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.1 comparingmorecomplexstructures. . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 morecontrol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4 structuralrecursion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.5 functionsrevisited. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.5.1 boundandfreevariables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.6 localcontexts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.6.1 closures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.6.2 recursivefunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.6.3 recursiveclosures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.6.4 recursivebindings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.7 higher-orderfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.7.1 mapping. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.7.2 folding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3. ratheresotericaspects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.1 numericfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.1.1 numericpredicates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.1.2 integerfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.1.3 rationalfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.1.4 typecheckingandconversion. . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2 sideeffects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2.1 subtlesideeffects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2.2 evaluation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3 metaprogramming. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3.1 programshackingprograms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3.2 betareductionbysubstitution. . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.4 packages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 part two:algorithms . . . . . . . . . . . . . . . . . . . . . . . 63 4. listfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.1 headsandtails. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2 findthen’thtailof alist. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.3 counttheatomsof aform. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4 flattenatree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.5 partitionalist. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.6 foldingovermultiplelists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.7 substitutevariables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5. sorting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.1 insertionsort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.2 quicksort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.3 mergesort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.4 unsortinglists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 6. logicandcombinatoricfunctions. . . . . . . . . . . . . . . . . . . . . . . . . 78 6.1 turninglistsintosets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.2 unionof sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.3 findmemberswithagivenproperty. . . . . . . . . . . . . . . . . . . . . . . . . 79 6.4 verifyproperties. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.5 combinationsof sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.6 permutationsof sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 7. mathfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 7.1 sequencesof numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 7.2 fastfactorialfunction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 7.3 integerfactorization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 7.4 partitioningintegers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 7.5 exploringthelimitsof computability. . . . . . . . . . . . . . . . . . . . . . . . 91 7.6 transposingmatrixes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 8. datastructures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 8.1 generators. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 8.2 streams. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 8.3 ml-stylerecords. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 9. compilers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 9.1 translatinginfixtoprefix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 9.1.1 formalgrammars. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 9.1.2 leftversusrightrecursion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 9.1.3 implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 9.2 translatingprefixtoinfix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 9.3 regularexpressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 9.3.1 regularexpressioncompilation. . . . . . . . . . . . . . . . . . . . . . . . . . 123 9.3.2 regularexpressionmatching. . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 9.4 meta-circularinterpretation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 10. mexprc--anm-expressioncompiler. . . . . . . . . . . . . . . . . . . . . . . 139 10.1 specification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 10.1.1 annotatedgrammar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 10.2 implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 10.2.1 lexicalanalysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 10.2.2 syntaxanalysisandcodesynthesis. . . . . . . . . . . . . . . . . . . . . . . . . 147 10.3 exampleprograms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 10.3.1 appendlists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 10.3.2 thetowersof hanoi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 10.3.4 nqueens. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 11. anothermicrokanren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 11.1 introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 11.1.1 functionsversusgoals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 11.1.2 unification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 11.1.3 logicoperators. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 11.1.4 parameterizedgoals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 11.1.5 reification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 11.1.6 recursion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 11.1.7 convertingpredicatestogoals. . . . . . . . . . . . . . . . . . . . . . . . . . 173 11.1.8 convertingfunctionstogoals. . . . . . . . . . . . . . . . . . . . . . . . . . . 174 11.1.9 condversusany. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 11.1.10 firstclassvariables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 11.1.11 firstclassgoals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 11.1.12 negation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 11.1.13 cutting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 11.2 alogicpuzzle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 11.3 implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 11.2.1 basics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 11.2.2 goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.2.3 interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 part three:zenlisp implementation . . . . . . . . . . . . . . 195 12. cpart. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 12.1 preludeanddatadeclarations. . . . . . . . . . . . . . . . . . . . . . . . . . . 195 12.2 miscellaneousfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 12.3 errorreporting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 12.4 countingfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 12.5 memorymanagement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 12.6 symboltables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 12.7 reader. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 12.8 primitiveoperationhandlers. . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 12.9 specialformhandlers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 12.10 evaluator. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 12.11 printer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 12.12 initialization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 12.13 interpreterinterface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 12.14 interpretershell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 13. lisppart. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 13.1 baselibrary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 13.2 iteratorpackage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 13.3 naturalmathfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 13.4 integermathfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 13.5 rationalmathfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 A.1 tailcallrules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 A.2 zenlisp functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 A.2.1 definitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 A.2.2 control. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 A.2.3 lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 A.2.4 miscellanea. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 A.2.5 packages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 A.2.6 metafunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 A.3 mathfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 A.4 workingwithzenlisp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 A.4.1 thedevelopmentcycle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 A.5 zenlisp fortheexperiencedschemer. . . . . . . . . . . . . . . . . . . . . . . 314 A.6 answerstosomequestions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 A.7 listof figures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 A.8 listof exampleprograms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 A.9 codelicense. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 part one symbolic programming This part discusses the foundations of symbolic programming by means of a purely symbolic, lexicallyscoped,functionalvariantof LISPcalledzenlisp. Zenlisp issimilartoScheme,butsimpler. Being purely symbolic, the language has only two fundamental data types: the symbol and the orderedpair. Zenlisp implementsthe paradigm of functional programming.Functional programming focuses on the evaluation of expressions. Programs are sets of functions that map values to values. Tail-recursiveexpressionsevaluateinconstantspace,makingiterationaspecialcaseof recursion. Zenlisp programsaretypicallyfreeof sideeffects. Although the techniques described in this text are presented in a LISPy language, the purely symbolic approach makes it easy to adapt those techniques to other functional languages and maybeeventolanguagesof otherparadigms. 1. basic aspects 1.1 symbols and variables Thisisaquoted symbol: ’marmelade Itiscalledaquoted symbolbecauseof thequotecharacterinfrontof it. Anythingthatisquotedreducestoitself: ’marmelade => ’marmelade The=>operatorreads‘‘reducesto’’or‘‘evaluatesto’’. Thelefthandsideof => isa programand itsrighthandiscalledthenormal form(or the‘‘result’’) of thatprogram. Asymbolthatisnot quotediscalledavariable. Hereisavariable: food Thenormalformof avariableisthevalueassociatedwiththatvariable: 9 zenstyleprogramming (define food ’marmelade) food => ’marmelade Theabovedefinebindsthevalue’marmeladetothevariablefood. Afterbindingavariabletoa value,eachreferencetothevariableresultsinthevalueboundtothat variable;thevariablereducestoitsvalue: food => ’marmelade Symbolsandvariablesareindependentfromeachother: (define marmelade ’fine-cut-orange) marmelade => ’fine-cut-orange While marmelade now refers to ’fine-cut-orange, the quoted symbol ’marmelade still reducestoitself andfood stillreducesto’marmelade: ’marmelade => ’marmelade food => ’marmelade Oncedefined,thevalueof avariablenormallydoesnotchange. Asymbolthathasnovalueassociatedwithitisnotavalidvariable: undefined-symbol => bottom Bottomdenotesanundefined value. Anythingthatreducestobottomshouldbeconsideredanerror. Aquotedsymbolisitsownvalue,soaquotedsymbolwithoutanassociationisfine: ’undefined-symbol => ’undefined-symbol 1.2 functions Thefollowingexpressionappliestheappendfunctiontotwoarguments: (append ’(pizza with) ’(extra cheese)) => ’(pizza with extra cheese) Thedata’(pizza with)and’(extra cheese)arelists.Appendappendsthem. Listsareintheirnormalformsbecausetheyarequoted: ’(pizza with cheese) => ’(pizza with cheese) Thenormalformof afunctionapplicationisthevaluereturnedbytheappliedfunction: (reverse ’(pizza with pepperonies)) => ’(pepperonies with pizza) 10