Tiny rule engine, part 1

I have been slowly working my way through Building Problem Solvers by Kenneth D. Forbus and Johan de Kleer. This blog post is about my implementation of pattern directed inference system in Hy .

In short, pattern directed inference system is a system where one can assert facts (Sun is shining, birds are singing) and declare rules that in turn assert more facts (if sun is shining, it’s warm outside). While it doesn’t sound particularly exciting (simple if statement would take care of the previous example), it starts to get interesting when amount of rules and facts grow. I’m showing a quick example of usage of the system, before diving into internals of the implementation in second blog post.

First of all, lets import few macros and functions that we’ll need:

=> (require [stilpo.tre [assert! rule]])
=> (import [stilpo.tre [create-tre run true?]])

First step is to create our tiny rule engine (hence name tre). It has title “family” that we can use to keep track of different rule engines, if we’re using more than one at any given time.

=> (setv tre (create-tre "family"))

Tiny rule engine operates asserts that are just lists of symbols. I like using something that looks as close to natural language as possible, although pretty much any kind of notation will work. Lets assert couple facts about who is parent of who:

=> (assert! tre (Alice is parent of Bob))
=> (assert! tre (Bob is parent of Charlie))

Initially I was trying to come up with a way of being able to skip the need to specify rule engine (tre), but decided in the end that having to state it explicitly makes things easier to manage when working with multiple engines at the same time. Now we have two facts, next we’ll need some rules to operate on them.

=> (rule tre (?x is parent of ?y)
...  (assert! tre (?y is children of ?x)))

=> (rule tre (?x is parent of ?y)
...  (rule tre (?y is parent of ?z)
...    (assert! tre (?x is grand parent of ?z))))

=> (rule tre (?x is grand-parent of ?y)
...  (assert! tre (?y is grand children of ?x)))

First rule states that if ?x is parent of ?y, then ?y is childred on ?x. Any symbol starting with question mark is trated as a variable. When rules are processed, these variable are bound to symbols they match and are available for assertions.

The second rule is interesting as it has two nested rules. First step checks if ?x is parent of ?y and second step checks if ?y is parent of ?z. Variable ?y has to be bound to same symbol in both rules for rule to execute. This allows us to build more complex rules that require multiple matches before an assertion triggers.

Until now we have been building state for the tiny rule engine, now it’s time to make it evaluate things:

=> (run tre)

Run function will start evaluating rules on assertions and it keeps doing that until no more assertions are being inserted. After the engine has stopped, we can query some facts:

=> (true? tre '(Alice is grand parent of Charlie))

=> (show tre 'Alice)
Alice is parent of Bob
Alice is grand parent of Charlie
Bob is children of Alice

Order of rules and assertions doesn’t matter, the end result should still be the same. It would be even possible to call run after every time a new rule or assertion was added and the result would still be the same. This allows users to experiment with the rules and get a feel of a specific problem they’re working with. Word of warning though, while it’s easy to add rules and assertions, it’s impossible to remove them. Once something has been asserted as true, it will remain true forever. This is because removing a rule or assertion would mean finding all the rules and assertions that were caused by it and removing them too (and the ones caused by it and so on). To make things worse, in very complex rule and assertion sets, same assertion could be result of multiple rules. Therefore it’s easier just not allow removal of assertions or rules.

Here’s another rule with two parts:

=> (rule tre (?x is parent of ?y)
...  (rule tre (?x is parent of ?z)
...    (assert! tre (?y is sibling of ?z))))

=> (assert! tre (Alice is parent of Zed))
=> (run tre)

=> (show 'Zed)
Alice is parent of Zed
Zed is children of Alice
Zed is sibling of Bob
Bob is sibling of Zed

So Bob and Zed are siblings, because they have same parent. This rule shows how the engine ensures that ?y and ?z don’t match the same symbol. Because if that were allowed, Zed would soon find another sibling, but how? First rule (?x is parent of ?y) would match to “Alice is parent of Zed”, binding Alice to ?x and Zed to ?y. Next rule would match two different assertions: “Alice is parent of Bob” and “Alice is parent of Zed”. In both cases ?x would be Alice (it has to, as it was bound in the previous step) and ?z would be Bob or Zed, depending on the assertion. Initial implementation of the engine didn’t force variables to have different values, which lead to funny bugs. Of course I’m not sure at all that ensuring them to be different doesn’t cause strange behaviour in some other case.

Nothing prevents us from using same variable multiple times in rule:

=> (rule tre (?x is nothing like ?x)
...  (assert! tre (There is glitch in the matrix)))

The previous rule would trigger if there were something that is nothing like itself, which sounds quite confusing. But indeed it’s possible, at least within the tiny rule engine.

So far I have been just playing with the engine and trying to get a feel of what kind of things it works with. In the future I would like to use it for some actual project. Knowing me, that something most likely will be a game of sorts. While it sounds attractive to write AI with this, one has to remember that it’s impossible to remove rules or assertions after they have been inserted in the engine. Maybe one could use this as a high level director that could accumulate knowledge and based on that generate goals for the lower level AIs to work towards to?


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s