Tiny Rule Engine, part (inc n)

Not too surprisinly, I’m still tinkering with the tiny rule engine. Specifically on how to add some logic into rules.

Up to this point, rules have been pretty simple. When a happens, assert b. While one can build pretty complicated things with this and frames, adding some logic can spice up things considerably.

What I initially thought as a simple task, turned out to be rather tangled problem.

First, I had written the code to assume that every form inside assert! and rule body would accept optional argument for environment. That is, a dictionary containing all variables and their values. Clearly this isn’t case with standard library functions or any other code than what I had written. Initially I thought that I would just wrap all the regular code inside a function so it could handle this extra parameter. While it could work, it would look rather messy, so the idea was discarded.

(rule tre (speed is ?v)
  (rule tre (time is ?t)
    ((fn [env]
        (assoc env '?d (* (get env '?v)
                          (get env '?t)))
        (assert! tre (distance is ?d) env)))))

Second idea, the one I ended up implementing, was to change macro so that it would detect what forms inside of the body would be able to deal with the parameter and what couldn’t. If form started with assert! or rule, I knew that they required the parameter and all other forms didn’t. Resulting filtering was somewhat like the one shown below. ~g!tre-env contains bindings that is inserted at the end of assert! and rule forms inside of body being processed.

(setv new-body (map (fn [elem]
                      (if (in (first elem) (, 'assert! 'rule))
                        `(~@elem ~g!tre-env)

Side effect of this was that now only those two forms had access to environment and could manipulate the data in there. If I were to have any kind of meaningful logic with body of a rule, this wouldn’t work. One idea I tried was to have specific functions that could access the environment: get! and set!. Both would take environment as parameter, which would solve the problem. But this doesn’t work if forms are nested, as they often are. In the example below, set! has access to environment, but those two get!s don’t.

(rule tre (speed is ?v)
  (rule tre (time is ?t)
    (set! '?d (* (get! '?v)
                 (get! '?t)))
    (assert! tre (distance is ?d))))

To work around this limitation, I decided let the macro to rewrite body completely. It would descent recursively and insert environment as a parameter where it was needed. At the same time I could get rid of the get! function and just use symbols directly instead. Macro deals every symbol that starts with a question mark as one that should interact with the environment. Because environment is a dictionary, macro can rewrite those symbols as associating or getting data from dictionary:

(setv ?d (* ?v ?t))

is transformed to roughly this (g!env is further replaced with an symbol that is guaranteed to be unique and bound to current environment):

(assoc g!env '?d (* (get g!env '?v)
                    (get g!env '?t)))

Notice how a symbol starting with question mark is sometimes rewritten to get form and other times not. Macro has to be aware of in which context the symbol is being used. While this currently works, I’m pretty sure that there are edge cases that the macro can’t handle correctly and will instead produce incorrect code. But those can be dealt with when such an event presents itself.

For those interested in the gritty details, core of the rewriting is show below. First case rewrites assert! and rule macros. Second one is a special case of setv that is delegated to a separate function (that might recursively call this function in case of non-trivial code). Third one is handling all symbols that don’t start with question mark (ie. if, fn, for and so on). Fourth one is for cases where symbol starting with question mark is used to retrieve value from environment. Last case is for rewrite expression recursively.

(defn rewrite-elem [elem]
   "rewrite part of rule"
   (cond [(and (not (symbol? elem))
               (in (first elem) (, 'assert! 'rule))) `(~@elem ~g!tre-env)]
         [(and (not (symbol? elem))
               (= (first elem) 'setv)) (rewrite-setv elem)]
         [(and (symbol? elem)
               (not (.startswith elem "?"))) elem]
         [(and (symbol? elem)
               (.startswith elem "?")) `(get ~g!tre-env (quote ~elem))]
         [(not (symbol? elem)) (HyExpression (map rewrite-elem elem))]))

Having these parts in place, I can now write code in style of:

(rule tre (speed is ?v)
  (rule tre (time is ?t)
    (setv ?d (* ?v ?t))
    (assert! tre (distance is ?d))))

This looks rather nice and compact, without being impenetrable.

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