P A R T O N E CHAPTER 1 GETTING STARTED: A TRUTH TABLE PROGRAM 1.1 HELLO WORLD . . . . . . . . . . . . . . . . . . . . 1 1.2 TRUTH TABLE . . . . . . . . . . . . . . . . . . . . 2 1.3 THE PROGRAM . . . . . . . . . . . . . . . . . . . . 3 CHAPTER 2 PREFIX TO INFIX TRANSLATOR 2.1 INFIX AND PREFIX NOTATION . . . . . . . . . . . . . 7 2.2 USER MANUAL . . . . . . . . . . . . . . . . . . . . 9 2.3 DESIGNING THE IMPLEMENTATION . . . . . . . . . . . 10 2.4 THE PROGRAM . . . . . . . . . . . . . . . . . . . 12 2.5 EXERCISES AND READING . . . . . . . . . . . . . . 13 CHAPTER 3 INFIX EVALUATOR 3.1 USER MANUAL . . . . . . . . . . . . . . . . . . . 16 3.2 DESIGNING THE IMPLEMENTATION . . . . . . . . . . . 17 3.3 THE PROGRAM . . . . . . . . . . . . . . . . . . . 19 3.4 EXERCISES AND READING . . . . . . . . . . . . . . 20 CHAPTER 4 MACRO EXPANDER 4.1 TEXT MACROS . . . . . . . . . . . . . . . . . . . 23 4.2 DESIGNING THE IMPLEMENTATION . . . . . . . . . . . 25 4.3 THE PROGRAM . . . . . . . . . . . . . . . . . . . 27 4.4 EXERCISES AND READING . . . . . . . . . . . . . . 29 CHAPTER 5 TRUTH TABLE GENERATOR 5.1 USER MANUAL . . . . . . . . . . . . . . . . . . . 30 5.2 DESIGNING THE IMPLEMENTATION . . . . . . . . . . . 32 5.2.1 The Translation To Internal Form . . . . . . . . 32 5.2.2 The Truth Table Generator . . . . . . . . . . . 34 5.3 THE PROGRAM . . . . . . . . . . . . . . . . . . . 36 5.4 EXERCISES AND READING . . . . . . . . . . . . . . 40 CHAPTER 6 OPERATOR PRECEDENCE PARSING 6.1 BOTTOM UP PARSING . . . . . . . . . . . . . . . . 44 6.2 PRECEDENCE RELATIONS . . . . . . . . . . . . . . . 46 6.2.1 The Algorithm . . . . . . . . . . . . . . . . . 47 6.2.2 The Program . . . . . . . . . . . . . . . . . . 50 6.3 PRECEDENCE FUNCTIONS . . . . . . . . . . . . . . . 52 6.3.1 The Algorithm . . . . . . . . . . . . . . . . . 52 6.3.2 The Program . . . . . . . . . . . . . . . . . . 54 6.4 EXERCISES AND READING . . . . . . . . . . . . . . 56 P A R T T W O CHAPTER 7 AN IMPERATIVE LANGUAGE 7.1 USER MANUAL . . . . . . . . . . . . . . . . . . . 58 7.2 DESIGNING THE IMPLEMENTATION . . . . . . . . . . . 60 7.2.1 Implementing The Syntax . . . . . . . . . . . . 60 7.2.2 Implementing The Semantics . . . . . . . . . . . 62 7.3 THE PROGRAM . . . . . . . . . . . . . . . . . . . 66 7.4 EXERCISES AND READING . . . . . . . . . . . . . . 74 CHAPTER 8 SECOND ORDER RECURSION 8.1 FIRST ORDER RECURSION . . . . . . . . . . . . . . 77 8.1.1 An Example Of First Order Recursion . . . . . . 77 8.1.2 The Even-Odd Partitioning Problem . . . . . . . 78 8.2 SECOND ORDER RECURSION . . . . . . . . . . . . . . 80 8.2.1 An Example Of Second Order Recursion . . . . . . 80 8.2.2 Three Other Examples . . . . . . . . . . . . . . 82 8.3 A LET-EXPRESSION EVALUATOR . . . . . . . . . . . . 87 8.3.1 The Implementation . . . . . . . . . . . . . . . 88 8.3.2 The Program . . . . . . . . . . . . . . . . . . 89 8.4 BACKTRACKING IMPLEMENTED AS SECOND ORDER RECURSION 92 CHAPTER 9 REGULAR EXPRESSIONS 9.1 SOME FORMAL LANGUAGE THEORY . . . . . . . . . . . 96 9.1.1 Strings And Operations On Strings . . . . . . . 96 9.1.2 Languages And Operations On Languages . . . . . 97 9.1.3 Regular Expressions And Regular Languages . . . 98 9.1.4 Exercises And Reading . . . . . . . . . . . . . 99 9.2 A REGULAR EXPRESSION EXPANDER . . . . . . . . . . 99 9.2.1 User Manual . . . . . . . . . . . . . . . . . . 100 9.2.2 Designing The Implementation . . . . . . . . . . 102 9.2.3 The Program . . . . . . . . . . . . . . . . . . 104 9.2.4 Exercises And Reading . . . . . . . . . . . . . 108 CHAPTER 10 SEMANTIC TABLEAUX 10.1 TRUTH TABLES VERSUS SEMANTIC TABLEAUX . . . . . . 109 10.2 DESIGNING THE IMPLEMENTATION . . . . . . . . . . . 110 10.2.1 A Goal Stack Machine . . . . . . . . . . . . . . 110 10.2.2 Predictive Parsing On A Stack . . . . . . . . . 111 10.2.3 Translating On A Stack . . . . . . . . . . . . . 113 10.2.4 The Model Generator . . . . . . . . . . . . . . 115 10.3 THE PROGRAM . . . . . . . . . . . . . . . . . . . 116 10.4 EXERCISES AND READING . . . . . . . . . . . . . . 120 10.5 THE IDENTITY CALCULUS . . . . . . . . . . . . . . 123 CHAPTER 11 CONTEXT FREE LANGUAGES 11.1 GRAMMARS . . . . . . . . . . . . . . . . . . . . . 125 11.1.1 User Manual . . . . . . . . . . . . . . . . . . 125 11.1.2 An Example Run . . . . . . . . . . . . . . . . . 127 11.2 DESIGNING THE IMPLEMENTATION . . . . . . . . . . . 128 11.2.1 Reading And Storing The Grammar . . . . . . . . 129 11.2.2 Processing Input Strings . . . . . . . . . . . . 132 11.3 THE PROGRAM . . . . . . . . . . . . . . . . . . . 133 11.4 EXERCISES AND READING . . . . . . . . . . . . . . 138 11.5 PROPLOG - PROPOSITIONAL PROLOG . . . . . . . . . . 141 11.5.1 Generalising The Use Of Grammars . . . . . . . . 141 11.5.2 A Dramatic Restriction On Productions . . . . . 142 11.5.3 A Logical Interpretation . . . . . . . . . . . . 143 P A R T T H R E E CHAPTER 12 HIGHER ORDER RECURSION 12.1 THIRD ORDER RECURSION . . . . . . . . . . . . . . 146 12.1.1 An Example Of Third Order Recursion . . . . . . 147 12.1.2 Partitioning Numbers Again . . . . . . . . . . . 149 12.1.3 Infix To Prefix Translation . . . . . . . . . . 149 12.2 A TRUTHTABLE PROGRAM . . . . . . . . . . . . . . . 152 12.3 FOURTH ORDER RECURSION . . . . . . . . . . . . . . 158 12.4 EXERCISES AND READING . . . . . . . . . . . . . . 159 CHAPTER 13 A DETERMINISTIC PARSER 13.1 A VERY SIMPLE PARSING MACHINE . . . . . . . . . . 162 13.2 SAMPLE RUNS . . . . . . . . . . . . . . . . . . . 164 13.3 DESIGNING THE IMPLEMENTATION . . . . . . . . . . . 170 13.3.1 The Parsing Procedures . . . . . . . . . . . . . 171 13.3.2 Code Generation . . . . . . . . . . . . . . . . 172 13.3.3 The Interpreter . . . . . . . . . . . . . . . . 173 13.4 THE PROGRAM . . . . . . . . . . . . . . . . . . . 173 13.5 EXERCISES AND READING . . . . . . . . . . . . . . 179 CHAPTER 14 SYMBOL TABLE AND RECURSION 14.1 THE MACHINE . . . . . . . . . . . . . . . . . . . 182 14.1.1 A Brief Description . . . . . . . . . . . . . . 182 14.1.2 The Simulating Program . . . . . . . . . . . . . 184 14.2 DESIGNING THE HIGH LEVEL LANGUAGE . . . . . . . . 186 14.2.1 Language Level . . . . . . . . . . . . . . . . . 186 14.2.2 Syntax . . . . . . . . . . . . . . . . . . . . . 187 14.3 DESIGNING THE COMPILER . . . . . . . . . . . . . . 189 14.3.1 Syntax . . . . . . . . . . . . . . . . . . . . . 189 14.3.2 Semantics . . . . . . . . . . . . . . . . . . . 191 14.3.3 A Look Inside . . . . . . . . . . . . . . . . . 194 14.4 THE COMPILER . . . . . . . . . . . . . . . . . . . 198 14.5 EXERCISES AND READING . . . . . . . . . . . . . . 207 CHAPTER 15 A THEOREM PROVER FOR MONADIC LOGIC 15.1 MONADIC LOGIC . . . . . . . . . . . . . . . . . . 210 15.2 OUTLINE OF THE SYSTEM . . . . . . . . . . . . . . 212 15.3 AN EXAMPLE RUN . . . . . . . . . . . . . . . . . . 213 15.4 DESIGNING THE IMPLEMENTATION . . . . . . . . . . . 222 15.4.1 The Main Program . . . . . . . . . . . . . . . . 222 15.4.2 Scanner And Compiler . . . . . . . . . . . . . . 223 15.4.3 The Interpreter - Outline . . . . . . . . . . . 225 15.4.4 The Interpreter - Details . . . . . . . . . . . 228 15.5 THE PROGRAM . . . . . . . . . . . . . . . . . . . 231 15.6 EXERCISES AND READING . . . . . . . . . . . . . . 244 15.6.1 A Theorem Prover For Algebra . . . . . . . . . . 247 CHAPTER 16 DATALOG - A PRECURSOR TO PROLOG 16.1 THE DATALOG LANGUAGE . . . . . . . . . . . . . . . 250 16.2 DESIGNING THE IMPLEMENTATION . . . . . . . . . . . 256 16.2.1 A Regular Grammar For DATALOG . . . . . . . . . 256 16.2.2 Parsing . . . . . . . . . . . . . . . . . . . . 258 16.2.3 Code Generation: Opcodes . . . . . . . . . . . . 260 16.2.4 The Interpreter . . . . . . . . . . . . . . . . 263 16.2.5 Code Generation: Addresses . . . . . . . . . . . 266 16.3 THE PROGRAM . . . . . . . . . . . . . . . . . . . 267 16.4 EXERCISES AND READING . . . . . . . . . . . . . . 275 P A R T F O U R CHAPTER 17 SOME UTILITIES 17.1 DESIRABLE UTILITIES . . . . . . . . . . . . . . . 278 17.2 THE IMPLEMENTATION . . . . . . . . . . . . . . . . 279 17.2.1 The Scanner . . . . . . . . . . . . . . . . . . 279 17.2.2 Error Reporting . . . . . . . . . . . . . . . . 283 17.2.3 Other Utilities . . . . . . . . . . . . . . . . 284 17.3 THE PROGRAM . . . . . . . . . . . . . . . . . . . 285 17.4 REMARKS AND A MAJOR PROJECT . . . . . . . . . . . 294 CHAPTER 18 A MINIATURE VERSION OF JOY, A FUNCTIONAL LANGUAGE 18.1 INTRODUCTION . . . . . . . . . . . . . . . . . . . 296 18.1.1 Theoretical Background . . . . . . . . . . . . . 296 18.1.2 Tutorial On JOY . . . . . . . . . . . . . . . . 301 18.2 THE JOY LANGUAGE . . . . . . . . . . . . . . . . . 306 18.2.1 Design Principles . . . . . . . . . . . . . . . 307 18.2.2 The Core Language . . . . . . . . . . . . . . . 308 18.2.3 Standard Library . . . . . . . . . . . . . . . . 309 18.3 THEORY OF JOY . . . . . . . . . . . . . . . . . . 313 18.3.1 JOY Algebra . . . . . . . . . . . . . . . . . . 313 18.3.2 JOY Types . . . . . . . . . . . . . . . . . . . 315 18.3.3 A JOY Interpreter Written In JOY . . . . . . . . 317 18.4 THE IMPLEMENTATION . . . . . . . . . . . . . . . . 320 18.5 THE PROGRAM . . . . . . . . . . . . . . . . . . . 324 18.6 EXERCISES AND READING . . . . . . . . . . . . . . 334 18.7 PROJECTS . . . . . . . . . . . . . . . . . . . . . 339 18.7.1 Improving Efficiency . . . . . . . . . . . . . . 339 18.7.2 An Imperative Version Of JOY . . . . . . . . . . 340 18.7.3 A Non-deterministic Version Of JOY. . . . . . . 342 CHAPTER 19 A LANGUAGE FOR QUERYING DATABASES 19.1 DESIGN OF THE LANGUAGE . . . . . . . . . . . . . . 343 19.1.1 Sorts And Types . . . . . . . . . . . . . . . . 344 19.1.2 Determinates And Determinables: . . . . . . . . 345 19.1.3 Formal Definitions . . . . . . . . . . . . . . . 346 19.2 A SAMPLE RUN . . . . . . . . . . . . . . . . . . . 348 19.3 USER MANUAL . . . . . . . . . . . . . . . . . . . 353 19.4 THE IMPLEMENTATION . . . . . . . . . . . . . . . . 356 19.4.1 General And Context Free Syntax . . . . . . . . 356 19.4.2 Context Sensitive Syntax . . . . . . . . . . . . 357 19.4.3 Semantics - Closed Atomic Formulas . . . . . . . 359 19.4.4 Semantics - Variables . . . . . . . . . . . . . 363 19.4.5 Semantics - Other Aspects . . . . . . . . . . . 366 19.5 THE PROGRAM . . . . . . . . . . . . . . . . . . . 367 19.6 EXERCISES AND READING . . . . . . . . . . . . . . 388 CHAPTER 20 A PETRI NET VERIFIER 20.1 INTRODUCTION . . . . . . . . . . . . . . . . . . . 391 20.2 NETS AND NETVER . . . . . . . . . . . . . . . . . 392 20.2.1 Static Descriptions Of Nets . . . . . . . . . . 392 20.2.2 Dynamic Behaviour . . . . . . . . . . . . . . . 393 20.2.3 Control Of Behaviour . . . . . . . . . . . . . . 394 20.2.4 Productions And Actions . . . . . . . . . . . . 395 20.2.5 Modes Of Behaviour . . . . . . . . . . . . . . . 395 20.3 SYNTAX . . . . . . . . . . . . . . . . . . . . . . 396 20.3.1 Lexical Matters . . . . . . . . . . . . . . . . 396 20.3.2 Context Free Syntax . . . . . . . . . . . . . . 397 20.3.3 Context Sensitive Restrictions . . . . . . . . . 398 20.4 SEMANTICS . . . . . . . . . . . . . . . . . . . . 399 20.4.1 Control Primitives . . . . . . . . . . . . . . . 399 20.4.2 Mode Selection . . . . . . . . . . . . . . . . . 399 20.4.3 Primitives From Regular Algebra . . . . . . . . 400 20.4.4 Primitives From Boolean Algebra . . . . . . . . 401 20.4.5 Discrete Event Primitives . . . . . . . . . . . 402 20.4.6 State Primitives . . . . . . . . . . . . . . . . 403 20.4.7 Place Primitives . . . . . . . . . . . . . . . . 404 20.5 EXAMPLES . . . . . . . . . . . . . . . . . . . . . 405 20.6 IMPLEMENTATION . . . . . . . . . . . . . . . . . . 413 20.7 THE PROGRAM . . . . . . . . . . . . . . . . . . . 414 20.8 DISCUSSION . . . . . . . . . . . . . . . . . . . . 432 20.8.1 Embellishments . . . . . . . . . . . . . . . . . 433 20.8.2 More Advanced Backtracking . . . . . . . . . . . 433 20.8.3 A More Powerful Object Language . . . . . . . . 434 CHAPTER 21 SELF-COMPILING COMPILERS 21.1 INTRODUCTION . . . . . . . . . . . . . . . . . . . 437 21.1.1 General . . . . . . . . . . . . . . . . . . . . 437 21.1.2 The Source Languages And The Target Language . . 438 21.2 A SMALL SELF-COMPILING COMPILER . . . . . . . . . 439 21.2.1 Rationale For HITECO 1 . . . . . . . . . . . . . 440 21.2.2 The HITECO Source Code . . . . . . . . . . . . . 441 21.2.3 The TECO Target Code . . . . . . . . . . . . . . 443 21.3 BOOTSTRAPPING . . . . . . . . . . . . . . . . . . 444 21.3.1 The Bootstrapping Process In General . . . . . . 445 21.3.2 Bootstrap To HITECO2 . . . . . . . . . . . . . . 446 21.3.3 Bootstrap To HITECO3 . . . . . . . . . . . . . . 450 21.4 A USEABLE SELF-COMPILING COMPILER . . . . . . . . 451 21.4.1 A Description Of HITECO4 . . . . . . . . . . . . 451 21.4.2 The HITECO4 Source . . . . . . . . . . . . . . . 453 21.4.3 The TECO Target Code . . . . . . . . . . . . . . 459 21.4.4 In Conclusion . . . . . . . . . . . . . . . . . 463 21.5 EXERCISES AND READING . . . . . . . . . . . . . . 463 A P P E N D I C E S APPENDIX A ANSWERS TO EXERCISES A.1 THE MARRIAGE PUZZLE . . . . . . . . . . . . . . . 465 A.2 PREFIX TO MINIMALLY PARENTHESISED INFIX . . . . . 466 A.3 TWO NON-RECURSIVE TRANSLATORS . . . . . . . . . . 470 A.4 DISPLAYING VALUES OF SUBFORMULAS . . . . . . . . . 474 A.5 A SMALL APL INTERPRETER . . . . . . . . . . . . . 478 A.6 CARTESIAN PRODUCT . . . . . . . . . . . . . . . . 486 A.7 TRUTH TABLES . . . . . . . . . . . . . . . . . . . 489 A.8 OPTIMISED SEMANTIC TABLEAUX WITH MACROS . . . . . 497 A.9 THE IDENTITY CALCULUS . . . . . . . . . . . . . . 510 A.10 A PROPLOG INTERPRETER . . . . . . . . . . . . . . 519 A.11 A TRANSLATION MACHINE . . . . . . . . . . . . . . 525 A.12 GRAMMAR GENERATOR - WITH EXTENSIONS . . . . . . . 527 A.13 A THEOREM PROVER FOR ALGEBRA . . . . . . . . . . . 533 A.14 S5 MODAL LOGIC TABLEAUX . . . . . . . . . . . . . 540 A.15 FOURTH ORDER RECURSION FOR TABLEAUX . . . . . . . 547 A.16 ERROR TREATMENT IN A SMALL PROCEDURAL LANGUAGE . . 554 A.17 SELF-REPRODUCING PROGRAMS IN JOY . . . . . . . . . 573 APPENDIX B BIBLIOGRAPHY AND INDEX B.1 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . 575 B.2 INDEX . . . . . . . . . . . . . . . . . . . . . . 586