On Lisp: beyond state machines
State machines part seven.
On Lisp has a section on non-determinism which illustrates an augmented transition network compiler. There's definitely some state machine flavors in there, but there's so much more going on.
The picture (figure 23.6 on page 315) is a directed graph of conditions which map out a simple subset of English grammar. Sentences which fit the grammar can be represented as paths through that graph of conditions. Directed graphs, workflows, and state machines are all in the same family.
Last year I would not have understood that last paragraph. I would have understood the grammar and the language and some of the context, but I would not have grokked it. I wouldn't have been able to write it myself. In fact there were similar sentences in some older documents about Werkflow and I only partly understood what they were talking about.
The ATN compiler described in On Lisp generates code to search for a path through the graph which will match a given sentence and return the parse tree of the sentence. The code will do a depth-first search of the paths through that graph until it finds a match or has exhausted the options that might match. The code itself is fascinating -- continuations built up from closures building towards a Prolog interpreter.
Among other things, it's giving me a sense of what's happening inside a rules engine. The Jess rules engine was the first I encountered. It was being used in some code that we were supposed to integrate with Envoy at PlanetCAD. Drools was the other rules engine.
Prolog is all about searching through collections of rules. As Paul Graham takes me on a tour through his implementation, I am also learning context to help ground RDF and OWL. I still think that RDF and OWL and the Semantic Web smells like a bunch of cool technology looking for a problem to solve. But, the empassioned arguments about how cool the Semantic Web will be make more sense as I understand more about the mechanics of the things that would wander through webs of RDF assertions.
Reading On Lisp has been an enormously mind-expanding exercise in many directions. None of what I've read so far has had anything to do with objects nor object orientation. Functional and declarative are the buzzwords, not objects nor encapsulation. I feel like I've been admitted into an elite club where the real programming secrets are shared, or perhaps more accurately, where the other programming secrets are shared.
The world I knew before was mostly about objects and figuring out how best to encapsulate parts of a problem. Now I see that objects are but an island in a much larger sea. On another chain of islands are functions and closures. I traveled among those islands once long ago. I had forgotten about their charms. Now that I've returned I see larger patterns emerge in that chain of functional islands: continuations and rules engines. There's nothing quite like traveling in another land to expand your view of the larger world and its possibilities.