Articles and Lectures

Logic Programming Articles

There are several areas of research in the declarative programming community, including inductive logic programming (ILP), where system build rules from making inferences from a provided data set, and Definite Clause Grammars (DCG), an effective system for building scanning/parsing systems and related systems. Definite Clause Grammars: Not Just for Parsing Anymorepresents some practical applications of DCGs that help programs become more computational powerful and orders of magnitude faster. The same problem is addressed using a similar technique, Monads in Haskell, that article is available on the site.

Combinatory Logic Miscellanea

Combinatory logic treats all arguments ("variables") as implicit and does a very good job of handling implied arguments one at a time (via 'currying'). There also exist several standard combinatorial expressions to represent propositional logic relations (and, or, implies, not, etc.) Many logic relations are binary: handling more than one implicit argument at a time tends to cause combinatory expressions to grow exponentially in size. In the following paper I introduce a new combinator (the P-combinator) that is designed to curry two arguments across multiple using combinators at linear (not exponential) cost in size.

I've provided a series of puzzles, thematically linked, on combinatory logic. Try your skill at solving these Bird Puzzles.

Implementing the 'v' functor of Unlambda (also known in the literature as a hopelessly egocentric bird) using only s, k, and i poses an interesting challenge. I have written a paper entitled Meditations on the Void that shows various attempts at this task as well as a successful implementation.

Programming Language Esotera

State machines are a popular way of describing programming tasks, and Whirl examines statefulness vindictively: writing a Whirl program requires awareness of at least two layers of state simply to execute a command. In order for me to write a correct Whirl interpreter, I wrote a formal language definition.

Update (2005-12-14): the document describing the module that implements aspects in Prolog provides an extended example of debugging and optimizing (by 150-fold) the Whirl interpreter.