See the book page for further details.
part one: symbolic programming . . . . . . . . . . . 9
1. basic aspects . . . . . . . . . . . . . . 9
1.1 symbols and variables . . . . . . . . . . . 9
1.2 functions . . . . . . . . . . . . . . . 10
1.2.1 calling functions . . . . . . . . . . . . 11
1.2.2 function composition . . . . . . . . . . . 12
1.3 conditions . . . . . . . . . . . . . . 13
1.4 recursion . . . . . . . . . . . . . . . 15
1.5 forms and expressions . . . . . . . . . . . 16
1.5.1 lists . . . . . . . . . . . . . . . . 17
1.5.2 forms . . . . . . . . . . . . . . . . 19
1.5.3 expressions . . . . . . . . . . . . . . 20
1.6 recursion over lists . . . . . . . . . . . 20
2. more interesting aspects . . . . . . . . . . 24
2.1 variadic functions . . . . . . . . . . . . 24
2.2 equality and identity . . . . . . . . . . . 26
2.2.1 comparing more complex structures . . . . . . . 27
2.3 more control . . . . . . . . . . . . . . 29
2.4 structural recursion . . . . . . . . . . . 30
2.5 functions revisited . . . . . . . . . . . 33
2.5.1 bound and free variables . . . . . . . . . . 34
2.6 local contexts . . . . . . . . . . . . . 35
2.6.1 closures . . . . . . . . . . . . . . . 36
2.6.2 recursive functions . . . . . . . . . . . 38
2.6.3 recursive closures . . . . . . . . . . . . 39
2.6.4 recursive bindings . . . . . . . . . . . . 40
2.7 higher-order functions . . . . . . . . . . 42
2.7.1 mapping . . . . . . . . . . . . . . . 43
2.7.2 folding . . . . . . . . . . . . . . . 45
3. rather esoteric aspects . . . . . . . . . . 47
3.1 numeric functions . . . . . . . . . . . . 47
3.1.1 numeric predicates . . . . . . . . . . . . 48
3.1.2 integer functions . . . . . . . . . . . . 50
3.1.3 rational functions . . . . . . . . . . . . 51
3.1.4 type checking and conversion . . . . . . . . 52
3.2 side effects . . . . . . . . . . . . . . 54
3.2.1 subtle side effects . . . . . . . . . . . 55
3.2.2 evaluation . . . . . . . . . . . . . . 56
3.3 metaprogramming . . . . . . . . . . . . . 56
3.3.1 programs hacking programs . . . . . . . . . 57
3.3.2 beta reduction by substitution . . . . . . . . 59
3.4 packages . . . . . . . . . . . . . . . 62
3.4.1 caveats . . . . . . . . . . . . . . . 63
part two: algorithms . . . . . . . . . . . . . . 65
4. list functions . . . . . . . . . . . . . 65
4.1 heads and tails . . . . . . . . . . . . . 65
4.2 find the n'th tail of a list . . . . . . . . 66
4.3 count the atoms of a form . . . . . . . . . 66
4.4 flatten a tree . . . . . . . . . . . . . 67
4.5 partition a list . . . . . . . . . . . . 68
4.6 folding over multiple lists . . . . . . . . . 69
4.7 substitute variables . . . . . . . . . . . 70
5. sorting . . . . . . . . . . . . . . . 70
5.1 insertion sort . . . . . . . . . . . . . 71
5.2 quicksort . . . . . . . . . . . . . . . 72
5.3 mergesort . . . . . . . . . . . . . . . 74
5.4 unsorting lists . . . . . . . . . . . . . 75
6. logic and combinatoric functions . . . . . . . 79
6.1 turning lists into sets . . . . . . . . . . 79
6.2 union of sets . . . . . . . . . . . . . 80
6.3 find members with a given property . . . . . . 80
6.4 verify properties . . . . . . . . . . . . 81
6.5 combinations of sets . . . . . . . . . . . 82
6.6 permutations of sets . . . . . . . . . . . 85
7. math functions . . . . . . . . . . . . . 87
7.1 sequences of numbers . . . . . . . . . . . 87
7.2 fast factorial function . . . . . . . . . . 88
7.3 integer factorization . . . . . . . . . . . 89
7.4 partitioning integers . . . . . . . . . . . 90
7.5 exploring the limits of computability . . . . . 92
7.6 transposing matrixes . . . . . . . . . . . 95
8. data structures . . . . . . . . . . . . . 95
8.1 generators . . . . . . . . . . . . . . 95
8.2 streams . . . . . . . . . . . . . . . 96
8.3 ml-style records . . . . . . . . . . . . 100
9. compilers . . . . . . . . . . . . . . 106
9.1 translating infix to prefix . . . . . . . . 106
9.1.1 formal grammars . . . . . . . . . . . . 107
9.1.2 left vs right recursion . . . . . . . . . . 112
9.1.3 implementation . . . . . . . . . . . . . 113
9.2 translating prefix to infix . . . . . . . . 117
9.3 regular expressions . . . . . . . . . . . 121
9.3.1 regular expression compilation . . . . . . . 123
9.3.2 regular expression matching . . . . . . . . 126
9.4 meta-circular interpretation . . . . . . . . 129
10. an m-expression compiler . . . . . . . . . 137
10.1 mexprc example programs . . . . . . . . . . 150
10.1.1 factorial function . . . . . . . . . . . 151
10.1.2 append lists . . . . . . . . . . . . . 151
10.1.3 the towers of hanoi . . . . . . . . . . . 151
10.1.4 n-queens . . . . . . . . . . . . . . . 151
11. another micro kanren . . . . . . . . . . . 152
11.1 a logic puzzle . . . . . . . . . . . . . 156
part three: zenlisp implementation . . . . . . . . . 158
12. c part . . . . . . . . . . . . . . . 158
12.1 prelude and data declarations . . . . . . . . 158
12.2 miscellaneous functions . . . . . . . . . . 167
12.3 error reporting . . . . . . . . . . . . 168
12.4 counter functions . . . . . . . . . . . . 170
12.5 memory management . . . . . . . . . . . . 171
12.6 symbol tables . . . . . . . . . . . . . 176
12.7 reader . . . . . . . . . . . . . . . 181
12.8 primitive operation handlers . . . . . . . . 187
12.9 special form handlers . . . . . . . . . . 194
12.10 evaluator . . . . . . . . . . . . . . 213
12.11 printer . . . . . . . . . . . . . . . 220
12.12 initialization . . . . . . . . . . . . . 223
12.13 interpreter interface . . . . . . . . . . 226
12.14 interpreter shell . . . . . . . . . . . . 230
13. lisp part . . . . . . . . . . . . . . 235
13.1 base library . . . . . . . . . . . . . 235
13.2 iterator package . . . . . . . . . . . . 239
13.3 natural math functions . . . . . . . . . . 240
13.4 integer math functions . . . . . . . . . . 251
13.5 rational math functions . . . . . . . . . . 258
appendix . . . . . . . . . . . . . . . . . 267
A.1 tail call rules . . . . . . . . . . . . 267
A.2 zenlisp functions . . . . . . . . . . . . 267
A.2.1 definitions . . . . . . . . . . . . . . 268
A.2.2 control . . . . . . . . . . . . . . . 268
A.2.3 lists . . . . . . . . . . . . . . . . 269
A.2.4 miscellanea . . . . . . . . . . . . . . 270
A.2.5 packages . . . . . . . . . . . . . . . 271
A.2.6 meta functions . . . . . . . . . . . . . 271
A.3 math functions . . . . . . . . . . . . . 272
A.4 working with zenlisp . . . . . . . . . . . 273
A.4.1 the development cycle . . . . . . . . . . 275
index . . . . . . . . . . . . . . . . . . 278
Copyright (C) 2008 Nils M Holm
< nmh @ t3x . org >