Tiny Rule Engine, part 2

In the previous blog post I wrote about tiny rule engine, my implementation of pattern directed inference system from Building Problem Solvers by Kenneth D. Forbus and Johan de Kleer. This blog post will be about internals of the system.

Building Problem Solvers has really excellent explanation of their implementation of the system and mine is based on that. So if this one looks too confusing, have a look at that one too.

There are three main components that do the heavy lifting: assert!, rule and run, some auxialiary functions like create-tre, show and true? are needed too.

Overview

Tiny rule engine is represented as a dictionary that is created with create-tre function.

(defn create-tre [tre-name &optional [debug False]]
  "create a new tiny rule engine"
  {:title tre-name
   :assertions []
   :rules []
   :assertion-queue []
   :rule-queue []
   :debug debug})

Assertions and rules that has already been processed are stored in :assertions and :rules and ones not yet processed in :assertion-queue and :rule-queue. With this division it’s easier to keep track when the engine has reached stable state and no new changes can occur anymore.

run will process both queues one item at a time. As processing them will usually mean mutating queues by removing and adding items, it was easiest to just have while loop that keeps going until both queues are empty.

(defn run [tre]
  "process tre until all queues are empty"
  (while (or (rule-queue tre)
             (assertion-queue tre))
    (process-assertion-queue tre)
    (process-rule-queue tre)))

Both assert! and rule macros are rather messy, so I’m not going through them. It’s sufficient to say that assertion is an expression like: (earth is round) or (sun is shining). Rule on the other hand is represented as a tupple like: (, ‘(?x is round) {‘?x ‘earth}). First element is pattern with possible variables, second is function that will execute when pattern matches and third one is dictionary consisting on variables and their values. We’ll look at rules more closely later, first step is to figure out how assertions work (since it’s kind of circular process where assertions and rules feed each other, we could start with rules too though).

Rules and Assertions

Assertion queue is processed with process-assertion-queue:

(defn process-assertion-queue [tre]
  "take first assertion in queue and process it"
  (when (assertion-queue tre)
    (setv new-assertion (.pop (assertion-queue tre)))
    (when (not (assertion-defined? tre new-assertion))
      (.append (assertions tre) new-assertion)
      (ap-each (rules tre)
               (run-rule it new-assertion)))))

We have to check that queue actually contain anything before popping an item from it. This is because the run loop will call both process-assertion-queue and process-rule-queue repeatedly as long as there’s items in either one of them. Assertion is then moved into assertions of tiny rule engine and all rules are run against it. We make sure to do these steps only if assertion isn’t already in the engine. This speeds up processing a bit and prevents some of the infinite loops that might otherwise happen.

Rules queue is processed in the same manner. Pop a rule out of queue if there’s any, move it to processed rules and then run it against every assertion in the engine. It would be nice to be able to check if the rule is already in the engine or not, but I couldn’t figure out a way to do it as it would require comparing two functions. And figuring out if a function is equal to another is quite a bit more complicated thing than I was willing to deal with right now (are two functions equal if they produce the same result but look different?).

(defn process-rule-queue [tre]
  "take first rule in queue and process it"
  (when (rule-queue tre)
    (setv processed-rule (.pop (rule-queue tre)))
    (.append (rules tre) processed-rule)
    (ap-each (assertions tre)
             (run-rule processed-rule it))))

That run-rule is where things start to get really interesting:

(defn run-rule [rule assertion]
  "run rule for assertion"
  (setv bindings (unify assertion
                        (first rule)
                        (get rule 2)))
  (when bindings
    ((second rule) bindings)))

Looks tiny, but this is starting to be at the heart of the system. First step is to take assertion and rule with associated bindings and see if they match. For example, if we have assertion (weather is nice) and rule with pattern (weather is ?x), matching depends on the value of ?x in bindings. If there is no value associated with it, we get bindings back: {‘?x ‘nice}. If ?x has value in bindings that is different from ‘nice no value will be returned and function will exit with null value.

If we got bindings back, second step is to execute function in the rule and supply bindings to it. The function can then add more assertions or rules to the engine and loop keeps going on.

Unification

Unification is couple lines of code:

(defn unify [assertion pattern bindings]
  "unify assertion and pattern, return new bindings or None"
  (if (= (len assertion) (len pattern))
    (reduce unify-sym (zip assertion pattern)
            (copy-bindings bindings))))

First length of assertion and pattern are checked. If they are different, unification will fail and we don’t need to even try it. If they happen to be same length, we copy supplied bindings (we don’t want to accidentally change bindings that are used somewhere else in the program) and start comparing assertion and pattern one symbol at a time. This is done by unify-sym:

(defn unify-sym [env (, assertion-sym pattern-sym)]
  "unify two symbols while respecting env"
  (cond [(is env None) None]
        [(= assertion-sym pattern-sym) env]
        [(and (var? pattern-sym)
              (in pattern-sym env)
              (= (get env pattern-sym) assertion-sym)) env]
        [(and (var? pattern-sym)
              (not (in pattern-sym env))
              (not (in assertion-sym (.values env)))) (add-binding env 
                                                                   pattern-sym 
                                                                   assertion-sym)]
        [True None]))

Looks complicated. Luckilly it’s 5 different cases, so we don’t have to deal with all of it in one go. One case at a time will suffice. The goal is to compare two symbols in respect with bindings (called env in this function, I really should change that to be consisted) and decide if unification is possible and if a new element should be added to bindings. We shouldn’t ever change a binding, because that would mean that previously done unification wouldn’t hold anymore. So we only add to the bindings.

First case is sort of safety check. If the function is called without bindings, something has gone horribly wrong earlier and we can’t continue. Thus we signal that binding failed and let the caller deal with the situation.

Second case is when assertion symbol and pattern symbol are identical. In this case bindings will not change and we can just return the value that was passed in. So far so good.

This case is when pattern symbol is variable (?x, ?y ?really-long-variable-name and so on), it has been stored into bindings earlier and the value stored into it is identical to the value of assertion symbol. In this case the bindings are just fine and we return them as they are.

Fourth case is the most involved one. Here pattern symbol is again variable, it hasn’t been encountered before (it’s not in the bindings) and the assertion symbol hasn’t been stored in bindings either. In this case, variable and corresponding symbol are added to the bindings before returning them.

Fifth case is the default. If we got this far, unification fails and None is returned.

But why do we check that the value of assertion symbol hasn’t been stored earlier in the fourth step? Original implementation I wrote didn’t have this check and that caused a subtle bug. Consider following set of assertions and rules.

(assert! tre (Alice is child of Bob))
(assert! tre (Charlie is child of Bob))

(rule tre (?x is child of ?y)
  (rule tre (?z is child of ?y)
    (assert tre (?x is sibling of ?z))))

If ?x and ?z are both children of ?y, they are siblings.

First rule matches (Alice is child of Bob) and binds Alice to ?x and Bob to ?y. The next rule is then (?z is child of Bob), that matches both (Alice is child of Bob) and (Charlie is child of Bob). In first case we get assertion (Alice is sibling of Alice) and in the second case we get (Alice is sibling of Charlie). Thus, Alice is sibling of herself, which is plain nonsense. But if we check that value of ?z hasn’t been stored in bindings earlier, only latter case will happen and things work out just nicely. There probably are cases, where it would make to sense to allow same value in multiple bindings, but I haven’t encountered one yet. It’s just one of those choices one has to make when designing such a system.

But, in the end, if unification succeeded, resulting bindings will be used when calling the rule that was being unified and new rules or assertions will be added into two queues. And process will keep on churning until both queues are empty.

That’s it. There are some minor details here and there, but the main idea is shown above. It took some fiddling and experimenting to get it working, but as an excercise this was fun project to do.

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