Computation type demo grammar

[guyemerson]

I've updated the demo grammar for my talk on the Turing completeness of unification. It now has:

• Boolean logic and Peano arithmetic, following my suggested best practices for implementing computation types and wrapper types.
• A simple example of a pathological type system where unification can get stuck in an infinite loop (thanks to @anncopestake for asking about this)
• A slight improvement to the Turing machine code, along with a second example
• Alternative append types, including prepend-list, which is more efficient than append-list, but appends the lists in the reverse order

There are five LKB scripts:

• script-pathological loads the pathological type system where unification can fail to terminate (see pathological.tdl)
• script-turing loads the easier-to-understand implementation of Turing machines, with two example machines (see turing.tdl)
• script-twofeat-turing loads the two-feature implementation of Turing machines, along with the same two example machines (see twofeat.tdl)
• script-lambda loads the implementation of untyped lambda calculus (see lambda.tdl)
• script-pseudoenglish loads a Matrix-derived grammar which includes types for list operations (defined in matrix.tdl), Boolean logic and Peano arithmetic (defined in computation.tdl), as well as non-deterministic list operations (defined in pop.tdl). It's a pseudo-English grammar, because the head-comp rule allows the elements to be taken off in any order, so that "I give the cat the dog" has two analyses, differing in the ARG2 and ARG3 of "give". The following operations are implemented:
  • List operations: append (three variants), reverse, non-deterministic pop
  • Boolean operations: and, or, negation
  • Arithmetic operations: addition, subtraction, multiplication, comparison