Implementing backward chaining in PyCLIPS.

I have been having an interesting e-mail conversation with Francesco about PyCLIPS this last week. PyCLIPS is mostly geared towards adding CLIPS to Python programs but it can also be used to add Python functionality to CLIPS. I've been urging him to add his Shell utility to the main package. The reason is because I think it would make a brilliant starting point for extensions. Regular expressions, backward chaining, database access and GUI capabilities are all good examples of what could be done.

I've done a little proof-of-concept implementation of backward chaining to show the idea and to provide a basis for discussion of these kinds of things. There are still a lot of things to do if this experiment is ever going to be useful and it might not even be possible to reach decent functionality (but it might be worth exploring further?). However, there are ways around most things when you control the dialog window ;-)

The general idea of the experiment is to implement something similar to how Jess handles backward chaining. Since there's no way to extend the syntax of CLIPS I can't add an explicit-CE and instead we'll have to make do with an explicit function.

> (deffunction MAIN::explicit ($?rules)
>   (progn$ (?rule $?rules)
>      (python-call explicit ?rule)))

I'll explain how it works after we've looked at do-backward-chaining and talked about some of the Python code.

> (deffunction MAIN::do-backward-chaining ($?templates)
>   (progn$ (?template $?templates)
>      (python-call do-backward-chaining ?template)))

I'm using Francesco's shell.py script as a basis for this experiment. I've modified it slightly though. When loaded it defines the above methods and attaches them to their Python counterpart using:

_cm.RegisterPythonFunction(do_backward_chaining, "do-backward-chaining")
_cm.RegisterPythonFunction(explicit, "explicit")

I've also made it such that whenever a user enters "(clear)" in the console the above functions are re-defined. I haven't found a good way of hooking into the clear command yet so if it's executed from a batch, this little hack won't do any good.

OK, let's see how it "works". Here's the factorial example from Jess In Action:

CLIPS[1/1]> (defrule print-factorial-10
CLIPS[1/2]:   (factorial 10 ?r1)
CLIPS[1/3]:   =>
CLIPS[1/4]:   (printout t "The factorial of 10 is " ?r1 crlf))
CLIPS[2/1]> (defrule do-factorial
CLIPS[2/2]:   (need-factorial ?x ?)
CLIPS[2/3]:   =>
CLIPS[2/4]:   (bind ?r 1)
CLIPS[2/5]:   (bind ?n ?x)
CLIPS[2/6]:   (while (> ?n 1)
CLIPS[2/7]:     (bind ?r (* ?r ?n))
CLIPS[2/8]:     (bind ?n (- ?n 1)))
CLIPS[2/9]:   (assert (factorial ?x ?r)))
CLIPS[3/1]> (do-backward-chaining factorial)
; + rule MAIN::print-factorial-10/0
nil
CLIPS[4/1]> (reset)
CLIPS[5/1]> (run)
The factorial of 10 is 3628800
CLIPS[6/1]>

The rules themselves are really not that interesting. What's interesting is that none of them ought to have been activated. And the reason they are is because of the function call to do-backward-chaining. We get a hint at what it has done on the line that says

; + rule MAIN::print-factorial-10/0

What happens is that the do-backward-chaining function in CLIPS calls the do_backward_chaining function in Python which searches through all rules (in all modules) for CEs that match

r"^\s*?\(%s\b(.*?)\)$" % (template)

(Yes. It's a Regular Expression. I know it's a bit hackish to do introspection work based on ppdefrule calls but it's not like there's any other option. At least not any that I can think of. If you know of a better way please let me know!)

If it finds a CE that matches, in our case (factorial 10 ?r1) in print-factorial-10, it generates a new rule based on the one containing the match. It adds a "/0" to the name (making it print-factorial-10/0), copies the LHS but removes the matching CE and constructs an RHS by taking the matching CE with a few modifications and placing it in an assert statement. The modifications it does is adding "need-" to the template name and replacing all variables with nil. We can see the result with

CLIPS[6/1]> (ppdefrule print-factorial-10/0)
(defrule MAIN::print-factorial-10/0
=>
(assert (need-factorial 10 nil)))
CLIPS[7/1]>

So, now it's easy to see why we got a result after (reset) and (run). Here's the dialog again, with facts and rules watched.

CLIPS[7/1]> (watch facts)
CLIPS[8/1]> (watch rules)
CLIPS[9/1]> (reset)
<== f-0     (initial-fact)
<== f-1     (need-factorial 10 nil)
<== f-2     (factorial 10 3628800)
==> f-0     (initial-fact)
CLIPS[10/1]> (run)
FIRE    1 print-factorial-10/0: f-0
==> f-1     (need-factorial 10 nil)
FIRE    2 do-factorial: f-1
==> f-2     (factorial 10 3628800)
FIRE    3 print-factorial-10: f-2
The factorial of 10 is 3628800
CLIPS[11/1]>

This little hack does unfortunately not work with deftemplates unless you also define a need-deftemplate as an exact copy. And, that just doesn't feel right. Also, if you've got a connected constraint in your CE, it will be ignored. I haven't been able to figure out a good way to communicate that type of constraint to the rule matching the need-fact so if you've got one please let me know.

When it comes to explicit, I've tried to keep it as simple as possible. I keep a list of all generated rules and when you execute

CLIPS[11/1]> (explicit print-factorial-10)
; - rule MAIN::print-factorial-10/0

any generated rule for print-factorial-10 is taken away (undefruled).

CLIPS[12/1]> (reset)
<== f-0     (initial-fact)
<== f-1     (need-factorial 10 nil)
<== f-2     (factorial 10 3628800)
==> f-0     (initial-fact)
CLIPS[13/1]> (run)
CLIPS[14/1]>

and that's it really.

That's all it does (for now at least). It's simple and it's not very elegant, but it works. I won't publish the code (yet) because I'm still trying to clean it up. Trying to make it "easier" to build on. I'll share with anyone interested though (send me an e-mail). But I would like to hear if this is a stupid idea in general or if I've done something wrong somewhere. Is there something I havent thought of that might pop up later and turn out to be near impossible to fix?