AST to AST translation in Python

In an attempt to further simplify PyRete's rule compiler I've split it into three parts.

1) Pre-processing (splits a rule into subrules, if necessary),
2) macro-expansion (translates, for example, Exists(CE*) into Not(Not(CE*))) and
3) Rete Network construction (creates Production-, Alpha- and BetaNodes and joins them together).

The complexity of trying to handle all of that in one class just got out of hand. Also, I think this design will make PyRete a lot more flexible and easier to extend with custom constructs (given that they are not violating Python's syntax that is).

Anyway, the idea is that the Rete Network construction (step 3) should only have to deal with constructs that can be translated directly into a node in the Rete Network and that everything else should be handled in either of the two previous steps. This means, among other things, that in step 3 there'll only be Object-Pattern-CEs, Test-CEs and Not-CEs left.

I'll talk about parts of step 2 (the macro-expansion) since I think it's the most interesting part.

Unfortunately there isn't that much written about AST to AST translation in Python. Not very surprising considering that it's not generally the level of abstraction most people decide to interfer with the compilation-chain. Most attempts either cover the whole thing, from front to back, like python4ply and EasyExtend or perform low-level bytecode manipulation as bytecodehacks and psyco. Even the Python docs for the compiler module and its AST visitor class is quite sparse to say the least.

Luckily I've spent more than a year poking around on the AST level of Python code so I'm used to trial and error and having exceptions thrown in my face every now and then. The translation scheme I've implemented is not as smooth as having Common Lisp or Scheme macros but it does the job.

Here's the code for handling the Exists-CE:

>>> class ExistsCE(object):
...   @classmethod
...   def expand(self, node):
...     nodesToVisit = [node]
...     while len(nodesToVisit) > 0:
...       curr = nodesToVisit.pop(0)
...       for child in curr.getChildNodes():
...         nodesToVisit.append(child)
...       if isinstance(curr, CallFunc) and curr.node.name == "Exists":
...         curr.node.name = "Not"
...         curr.args = [CallFunc(Name("Not"), curr.args)]
...     return node

and here's a sample usage (I've highlighted the interesting parts).

>>> ast = compiler.parse("Exists(Spam(eggs == 1, bacon = 2))")
>>> print ast
Module(None, Stmt([Discard(CallFunc(Name('Exists'), [CallFunc(Name('Spam'), [Com
pare(Name('eggs'), [('==', Const(1))]), Keyword('bacon', Const(2))], None, None)
], None, None))]))

and if we run it through the ExistsCE macro expander we get:

>>> print ExistsCE.expand(ast)
Module(None, Stmt([Discard(CallFunc(Name('Not'), [CallFunc(Name('Not'), [CallFun
c(Name('Spam'), [Compare(Name('eggs'), [('==', Const(1))]), Keyword('bacon', Con
st(2))], None, None)], None, None)], None, None))]))

which is exactly the same AST as if we had written two nested Not calls instead:

>>> print compiler.parse("Not(Not(Spam(eggs == 1, bacon = 2)))")
Module(None, Stmt([Discard(CallFunc(Name('Not'), [CallFunc(Name('Not'), [CallFun
c(Name('Spam'), [Compare(Name('eggs'), [('==', Const(1))]), Keyword('bacon', Con
st(2))], None, None)], None, None)], None, None))]))

I wonder if I can abstract away some of that boiler plate, make it more general and usable. I'll have to tinker some more but it shouldn't be impossible.

1000 LOC removed

There's not many things that make me happier than being able to remove existing code. These past few days have been quite good in that respect.

Previously I compiled a Rete Network from a Python AST by passing the rule function's AST to an ASTVisitor which returned a dictionary holding information about which nodes should be created. The dictionary was then passed to a method (construct_rete) which was in charge of creating the Rete Network and figuring out in what way the nodes should be connected.

That way of doing it turned out to be an ugly beast of complexity which managed to resist all of my attempts to make it simpler. I spent more than half a year trying before I binned it completely and yesterday I updated PyRete's SVN repository with the code I've got so far.

The approach I use now is that I pass the rule function's AST to an ASTVisitor which *directly* calls the Rete implementation. This way I don't have to go through all of the trouble of maintaining a dictionary with intermediate details and the result is that I've managed to get rid of about 1000 lines of code and the compilation process is more or less understandable.

"K-I-S-S. Keep it simple, stupid. Great advice. Hurts my feelings every time." -Dwight Schrute

Yet another post about the RuleCompiler

There's still a lot of code to be written for the RuleCompiler but I came a bit further today. I've added print statements to the parser so I can trace the creation of the Rete Network.

>>> def rule1(self, large = Large, medium = Medium, small = Small):
...   salience = 10
...   if large(value == x and x > 10, another == y) and \
...      medium(value == y and y > x, another == z) and \
...      small(value == z):
...     pass

>>> parse(rule1)
# p = ProductionNode(rule = rule1)
# p.doc = None
# o1 = ObjectTypeNode(type = Small)
# o2 = ObjectTypeNode(type = Medium)
# o3 = ObjectTypeNode(type = Large)
# p.salience = 10
# x = large.value
# a1 = AlphaNode(large.value > 10)
# y = large.another
# j1 = JoinNode(large.another == medium.value)
# a2 = AlphaNode(large.another > large.value)
# z = medium.another
# j2 = JoinNode(medium.another == small.value)

I'm about 90% done. It took about 8h of programming, spread out during a week. I figure the last 10% will take at least as long. They always seem to do. But this is good. In my previous attempts it took me a lot longer to get this far.

A couple of days ago I thought I could lose the fact bindings (the method parameters) but it occured to me today that they are needed if one or more of the Facts are to be referenced in the RHS. So, the bindings stay.

And, regarding python4ply I've decided to do without it at the moment. The only thing I've found I really miss is the ability to use ? to distinguish a variable name from an attribute name. Without it there's no way a variable can have the same name as an attribute.

python4ply vs a custom rule compiler

Andrew Dalke released python4ply 1.0 today. It might be useful as part of the RuleCompiler since I wouldn't have to constrain the rule syntax to Python's.

One of the main reasons for doing the rule compiler the way I am, is so I wouldn't have to re-implement a parser for Python's syntax but now that Andrew's gone and done just that... I don't know. This is from his announcement:

You might use python4ply to experiment with variations in the Python language. The PLY-based lexer and parser are much easier to change than the C implementation Python itself uses or even the ones written in Python which are part of the standard library.

It would be cool to have support for other syntaxes as well... I'll have to think about it.

Progress with the RuleCompiler

Finally! It's starting to feel like I'm getting somewhere with PyRete's RuleCompiler. Earlier this week I decided to change quite a lot about the allowed syntax in a rule.

I've always kind of thought I'd have to have support for expressing rules in many different ways. For instance, I've tried to support at least three different approaches to expressing:

|CLIPS>(defrule rule
|  (foo (attribute ?attr&:(> ?attr 10)))
|  (bar (attribute ?attr))
|  =>)

This way, which used to be the preferred way, you would write the rule as if you were writing procedural code:

>>> @prodsys.rule
... def rule(engine, foo = Foo, bar = Bar):
...   if foo.attribute == bar.attribute and \
...      foo.attribute > 10:
...     pass

Another way, which always felt a bit weird and unnatural to me, was to use a (logical) variable:

>>> @prodsys.rule
... def rule(engine, foo = Foo, bar = Bar):
...   if foo.attribute == attr and \
...      bar.attribute == attr and \
...      attr > 10:
...     pass

The problem with it, and the reason I don't like it, is that it's not all that clear what is going to happen. There's no way of telling that attr is a logical variable and that makes it look like it's three ordinary comparisons, but it's not. In any other context the code would raise an Exception because the local variable attr is unbound and that's probably how most Python programmers will read it.

I thought that the above would cause a lot of confusion which is why I implemented another way of expressing the same thing which looks a lot more like the pattern-matching syntax of CLIPS:

>>> @prodsys.rule
... def rule(engine, foo = Foo, bar = Bar):
...   if foo(attribute == attr and attr > 10) and \
...      bar(attribute == attr):
...     pass

This is, of course, also slightly problematic but at least there's no interpretation of the code that completely shadows how it's being used in PyRete.

It wasn't until I decided, quite recently, that I'll only support the last type of syntax (pattern matching-style) that I started to get somewhere with the RuleCompiler. It also meant that I could get rid of the object bindings in the parameter list.

The above rule should be written as:

>>> @prodsys.rule
... def rule(engine):
...   if Foo(attribute == attr and attr > 10) and \
...      Bar(attribute == attr):
...     pass

It's only too bad that it takes me so long to figure these things out.

The RuleCompiler and Network Topology

Working on the RuleCompiler has raised a lot of questions. Trying to implement the Rete Algorithm has taught me a lot of things and it is very interesting indeed. Reading Doorenbos' or Forgy's thesis gives a rather broad and general overview of the algorithm but there are several things that are not discussed, at least not extensively. One of those things are network topology.

Consider the following (as always, rather silly rule):

>>> @pyRete.Rule
... def foo(a=int, b=int, c=int, d=int):
...   if a==b and c==d:
...     pass

In the above mentioned papers all BetaNodes (tests involving 2 variables) are chained together. If the BetaNodes' variables overlap, there's no problem (these are the only types of examples given). They'll more or less automatically be connected because one of the input's for the second BetaNode will have to be taken from the first node's BetaMemory.

But, in the rule above, tokens taken from the first node's BetaMemory won't contain either of the variables c or d. I can think of (at least) two ways to compile the Rete Network for the above Rule. I can't say if one is "better" than the other, they contain roughly the same amount of nodes and will probably perform similarly (I haven't tested), but I've chosen topology #2 for pyRete.

This screen dump shows Topology #1:



There are 4 ObjectTypeNodes (red) and 4 AlphaMemories (yellow/greenish) because there's no sharing at all, remember? However, there are 2 LeftInputAdapters (gray) that each feed into a BetaNode (blue). The BetaMemories (darkblue) are joined in a "dummy join" (blue) that feeds into the last BetaMemory that feeds the ProductionNode (white).

The dummy join's job is to extend the incoming left token with the variables and bindings from the incoming right token. There's no test being performed, it basically just performs "token" addition:

{ 'a': n, 'b': n, } + { 'c': n, 'd': n, } = { 'a': n, 'b': n, 'c': n, 'd': n, }

and passes it on to the next Node.

Here's Topology #2



Here, as well, are 4 ObjectTypeNodes and 4 AlphaMemories. There's only 1 LeftInputAdapter though. It feeds into a BetaNode, which, via a BetaMemory, feeds a "dummy join" that feeds into the last BetaNode. The last BetaNode's Memory feeds the ProductionNode.

The dummy join's task here is the same as in #1. It's just a way to make sure that the last BetaNode is fed tokens containing the left input's variables and bindings.

The reason I chose Topology #2 is based on gut-feeling and "looks" and not because I can point you to a page and paragraph in Forgy's thesis saying "that's why!", so if you know it's wrong (or right) please leave a comment.

[Update 2007-01-23]
It turns out that the run-time properties of the two Topologies were not the same, as I previously thought. My implementation of the JoinNode has turned out to be wrong. What happens is that the JoinNode propagates Tokens even though the left input is empty which means that Tokens with only 2 variables/bindings end up in the ProductionNode. Very irritating, but fixed now.