Tuesday, 23 June 2009

Revisiting Eliza

I previously blogged about Eliza here but decided it was worth revisiting. Looking back I was being daft and trying to use strings to represent sentences the user enters. Lisp's symbol handling is much simpler to deal with.

Eliza is one of the most famous "AI" programs. It was written to give the impression of a Rogerian pyschoanalyst by answering questions with further questions in an effort to make the patient understand the problem.

The original Eliza paper is a good read. The introduction to the paper is awesome and explains the human learning process really well.

It is said that to explain is to explain away. This maxim is nowhere so well fulfilled as in the area of computer programming, especially in what is called heuristic programming and artificial intelligence. For in those realms machines are made to behave in wondrous ways, often sufficient to dazzle even the most experienced observer. But once a particular program is unmasked, once its inner workings are explained in language sufficiently plain to induce understanding, its magic crumbles away; it stands revealed as a mere collection of procedures, each quite comprehensible. The observer says to himself "I could have written that". With that thought he moves the program in question from the shelf marked "intelligent" to that reserved for curios, fit to be discussed only with people less enlightened that he.

This explains my learning process for functional programming in general. First everything seems weird and wonderful, then understandable and then I might even have a chance of solving it myself!

Once the curtain is lifted we see that Eliza is nothing more than a pattern matching system. Lists of symbols are parsed and matched against a series of rules. The pattern matching functions associate variables with parts of the match and then substitutions can be made.

The tests below demonstrate the use of the pattern matching functions based on the examples in PAIP. fail and no-bindings are sentinel values that can be used to distinguish between no match and failure. An alternative would have been to use exceptions to represent failure, but exceptions always feel yucky to me in FP.

In Norvig's example, he uses the Lisp reader to provide a REPL for Eliza. Since Clojure has access to the GUI libraries of Java then it makes sense to use this and get a basic UI together:

Basic UI of Eliza

The code to create the UI is shown below. The interesting bit is reading the users input as a series of symbols (and the avoidance of laziness!) and the use of interleave to space things out.

Translating this from PAIP was mostly straight-forward, but there were several gotcha's. Nil-punning caught me out a few times, and some Lisp functions didn't have Clojure equivalents with the same name (so digging through the API taught me a few things e.g. sublis and replace). I'm sure there's still much I could do to improve this code. I'm particularly not impressed with position, I must be missing a trick there? Perhaps I should be using vectors more?

The full code can be found on my Clojure Projects Git repository.