Tuesday, 14 July 2009

Pattern Matching Tools

In order to implement the STUDENT program, we first need a more advanced series of pattern matching tools. Chapter 6 of PAIP generalizes the pattern matching tools we saw in Eliza (see here).

The idea is that matching is extended to be customizable. The algorithm is presented in a "data-driven programming" manner. Each pattern (such as is, or, and, not, if) is associated with a corresponding function that does the work. It's a very extensible system because if we want to add an extra pattern, we just add an entry to the table and the job is done. This is a common theme throughout the book so far, and it's slowly beginning to sink in!

The Common Lisp version uses symbol properties to associate data with symbols. To my knowledge, Clojure doesn't support this (please correct me if I'm wrong!), so I modelled this as a simple associative structure with lookups based on the symbol name.

Most of the other functions were pretty trivial to port across to Clojure, but progv presented some problems. progv is a special operator which creates special bindings. This effectively allows you to inject additional environment into a lump of code you want to evaluate. For the match-if function, the Common Lisp code looks like this:

This effectively makes bindings available to the item that you want to fiddle with. From some of the comments on Critiquing Clojure it looks like there may be a better way of doing this, than the hacky way I've done it. I simply replaced all occurrences of the variables (?var) with the appropriate bindings. On the way, I discovered the oddly named postwalk-replace which traverses deeply into a structure and replaces using a provided map. (note that this is in no way the same as progv because it's just search and replace and doesn't handle the fact that someone could declare a variable overwriting the bindings).

You can find the complete source for the pattern matching chapter of PAIP on my Clojure Projects github page.