Constructing a Rete Network.
I've got my ObjectTypeNodes, my AlphaNodes, my BetaNodes, my AlphaMemories, my BetaMemories and my ProductionNodes. Everything is set, I'm all ready to start constructing the Rete Network.
Most of my test-rules provide little or no problem at all. I hook up a chain of AlphaNodes after an ObjectTypeNode and end it all with an AlphaMemory. If it's the "first" AlphaMemory for this Rule I also make a LeftInputAdapterNode. Then I hook up the "first" BetaNode's leftInput to the LeftInputAdapter and the rightInput to the AlphaMemory that holds the second variable's type and so on and so on until there's no more BetaNodes left and I add on the ProductionNode.
In cases like that there's no problem. This is also the "classic" portrait of what a Rete Network looks like. Almost every example I've seen has had this "look", but what if there's no condition in the rule that requires joining? Say that we'd write a rule like this:
>>> import pyRetesure, it's stupid. But never mind that.
>>> @pyRete.Rule
... def foo(a = Type1, b = Type2):
... if a.n == 1 and b.n == 2:
... print "Score!"
At the moment, pyRete makes two ObjectTypeNodes, two AlphaNodes and a ProductionNode. But there's no way to trigger the Action because the Rete Network "stops" at the AlphaMemories. So now I have to decide, do I perform a dummy join in the ProductionNode or do I set up a dummy BetaNode that feeds the ProductionNode? Also, are there more situations like this? Looks like I'm spending this week going through some source code to check out how Drools and Sumatra handles this situation.
BTW. Charles Young updated Wikipedia this week with more details on the Rete Algorithm. I likes.
Labels:
pyRete,
Rete Algorithm
5 kommentarer:
There's no need to make a dummy join to make it work. The simplest and best way is to add the terminal node as a successor to the last alpha node in the chain.
Although charles has improved the explanation there are factual errors in his update to the wikipedia. Forgy clearly defines the first check after the root node is the object type node. It isn't optional. What is optional is node sharing, additional beta node indexing and other optimizations.
In terms of getting the simple rule to fire. The way drools, clips, sumatra and jess work is each node propogates to the subsequent node in the network. Basically, if the fact matches the condition of the alphaNode, like (a.n == 1), it propogates the fact to the successor nodes. Basically, it pushes the fact down the network.
In the case of CLIPS, drive.c is responsible for pushing facts through the network. hope that helps.
Thanks for the comments Peter. It sure does help.
I may have misunderstood you but the problem is that a and b are of *different* Types.
In my example Rule, there would be two ObjectTypeNodes and two AlphaNodes. I need a way of joining them because I just can't chain them together since they are, or at least should be, different.
I can see now that my example is not very clear. I should have used different attributes instead. In a duck type situation (or if a and b where of the same Type) this would have been as easy as you say. Just hook up the ProductionNode after the AlphaMemory and we're good to go.
Unfortunately in this situation I'm not sure what to do unless I join them in some way and since there's no real join to be done it should be easy. Probably something similar to just accepting all incoming objects and construct a Token with all tokens or objects in the "other" input.
About the wikipedia, I actually just saw it when I wrote my blog post. I haven't had time to go through it yet. I was happy to see the schematic picture of a Rete Network though because it's more or less exactly the same as what I've done (apart from the dummy top and join nodes).
I'll be going through Drools and Sumatra source code later this afternoon and hopefully will at least have a few ideas of how this particular situation is handled.
I totally missed the fact there were 2 object types. Must have been brain dead :) That happens to me frequently.
I thought i might help to show how i implemented BetaNode and ZJNode. If you go down to line 151 for BetaNode http://ruleml-dev.cvs.sourceforge.net/ruleml-dev/sumatra/src/main/woolfel/engine/rete/BetaNode.java?view=markup you'll see it calls this.evaluate(left,rfcts). The evaluate method in turn declares boolean eval = true and then iterates over the bindings and evaluates the facts. In the case where a join doesn't compare the facts, evaluate simply returns true.
for comparison, assertFacts method in ZJBetaNode never calls evaluate (http://ruleml-dev.cvs.sourceforge.net/ruleml-dev/sumatra/src/main/woolfel/engine/rete/ZJBetaNode.java?view=markup). I did this as an optimization. When the rule is compiled, I look at how many bindings the join has. If it has zero, I use ZJBetaNode instead of BetaNode.
hope that makes it more clear.
I've responded to Peter's comments about the Wikipedia article over on his blog site. I'm sure there will be some further discussion. Any other suggestions for improvements, or possible corrections, are very welcome, or feel free to change, edit or delete. In the meantime, I'll review the article over the next few days and see if I can improve the clarity, tidy up a few areas, etc. I may also edit soem fo the original content, jwhich currently I have left in place.
Charles, I'm quite grateful that you updated the Wikipedia. It's good work (even though, the moment I read it, I knew that Peter was going to have something to say about those *optional* type checks) and I enjoyed reading it. It's definitely better than before.
I should also say that I'm willing to help any way I can. I've actually been thinking about writing a summary myself. At the very least to serve as documentation for my toy implementation.
At the moment I'm trying to implement Rete in Python. It has proven to be quite a challenge. Partly because there's too many descriptions and implementations to look at (they vary quite a bit as well).
I started out quite closely to Doorenbos' pseudo code description but decided to leave that since I'm interested in a closer fit to Python OO than (name attr value) tuples can give me.
The past few months have changed my understanding of Rete several times. I keep running into little details that are not described anywhere (apart from in code of course).
I can't say that I've "got it" at the moment (probably not) but there may be parts of my description that could be used for Wikipedia.
Skicka en kommentar