Handling defrules in MPS, executing the RHS

I've been rewriting the deftemplate code for MPS more or less from scratch... but I'll have to talk about that some other time. It's high time to focus on the defrule macro(s). I'll break this up into several posts and I'll start with the function for executing the RHS.

The MPS syntax (a subset of CLIPS') for defrule looks like this:

  defrule-construct
    ::= (defrule rule-name
          conditional-element*
          =>
          expression*)

  conditional-element
    ::= template-pattern-CE ¦ assigned-pattern-CE ¦
        not-CE ¦ and-CE ¦ or-CE ¦ test-CE ¦
        exists-CE ¦ forall-CE

  assigned-pattern-CE
    ::= single-field-variable <- template-pattern-CE

  not-CE     ::= (not conditional-element)
  and-CE     ::= (and conditional-element+)
  or-CE      ::= (or conditional-element+)
  test-CE    ::= (test function-call)
  exists-CE  ::= (exists conditional-element+)
  forall-CE  ::= (forall conditional-element
                         conditional-element+)

  template-pattern-CE
    ::= (deftemplate-name single-field-LHS-slot*)

  single-field-LHS-slot
    ::= (slot-name constraint)

  constraint ::= ?  connected-constraint


  connected-constraint
    ::= single-constraint ¦
        single-constraint & connected-constraint
        single-constraint ¦ connected-constraint

  single-constraint
    ::= term ¦ ~term

  term       ::= constant ¦ single-field-variable ¦
                 :function-call ¦ =function-call

  single-field-variable
    ::= ?variable-symbol

I'm quite far from having all of the above supported, but I've got enough to show how the function that executes the RHS of a rule works.

The defrule macro works by expanding into a series of macro calls which handle more and more specific cases in the processing. The macro itself is quite simple

(defmacro defrule (name &body body)
  (let ((rhs (cdr (member '=> body)))
        (lhs (ldiff body (member '=> body))))
    `(progn
       (compile-lhs ,name ,@lhs)
       (compile-rhs ,name ,@rhs))))

As you can see, it expands into two other macro-calls: compile-lhs and compile-rhs, where the first parses the conditional-elements and, in the process, creates two symbol-tables (fact-bindings and variable-bindings) with all of the variables it can find.

The second macro handles the RHS and looks like this:

(defmacro compile-rhs (name &body rhs)
  (when (null rhs)
    (setf rhs '(t)))
  `(defun ,(make-sym "RHS/" name) (activation)
     (let* ((token (activation-token activation))
            ,@(mapcar #'make-fact-binding (reverse fact-bindings))
            ,@(mapcar #'make-variable-binding (reverse variable-bindings)))
       ,@rhs)))

So, if we evaluate this:

MPS> (defrule foobar
       ?foo <- (foo (bar ?bar) (baz 1))
        =>
       (format t "~%~A ~A" ?foo ?bar))

it expands into this (among other things):

(DEFUN RHS/FOOBAR (ACTIVATION)
  (LET* ((TOKEN (ACTIVATION-TOKEN ACTIVATION))
         (?FOO (NTH 0 TOKEN))
         (?BAR (DEFTEMPLATE/FOO-BAR ?FOO)))
    (FORMAT T "~%~A ~A" ?FOO ?BAR)))

Most of the work is with figuring out how to assign values to each of the variables. I'm using a simple list as the structure for the tokens. WMEs (fact objects) are added in the order they appear in the list of conditional elements. Once all of the WMEs are bound, all of the variable-bindings are bound by using the automatically constructed accessor methods for those structs.

The actions in the RHS are simply spliced into the let* form at macro-expansion time which completes the function definition. It is then evaluated and stored with the rule's production node. Later, when that production node is left-activated, it creates an activation (with the WMEs and some additional meta-data like timestamps and such) and places it in the conflict-set. If that activation ever triggers a rule, it is passed as an argument to the RHS function.

Since I haven't got enough of "the rest" of MPS in place. We're going to have to mock an activation and call the function directly to see whether or not it works.

MPS> (rhs/foobar (make-activation :token (list (foo (bar 1) (baz 1)))))
#S(DEFTEMPLATE/FOO :BAR 1 :BAZ 1) 1
NIL
MPS>

There's really not much more to say about the RHS so I'll stop here. The LHS is a bit more complicated and I hope that I can show some of that code soon.

Pattern matching function declarations in Python

All those who have tried to write a rules-based program know that there are, at least, two differences between "regular" programming and rules-based programming. The first is that you have no direct control over the flow of execution and the second is that, instead of specifying input parameters, you specify patterns that should be matched for a certain "function" (or rule) to be invoked.

The bit about giving up control is quite difficult for most programmers (at least the ones I know) and it doesn't translate well to other types of programming anyway. But it would be interesting to try and add pattern matching functions to a language such as Python and see whether it could be useful (or at least fun to experiment with).

It's not a new idea. The first language to support pattern matching this way was Snobol (version 4 I think) which was introduced in the late 60s/early 70s. Both Haskell and Erlang has it and there are a bunch of others as well, Qi and Prolog to mention a few.

I'm thinking about something along the lines of:

>>> from patternmatching import *
>>> @patternmatched
... def fac(n = 0):
...   return 1
...
>>> @patternmatched
... def fac(n = int):
...   return n* fac(n = n-1)
...
>>> fac(5)
120
>>>

The idea is that the first function would handle any calls to the fac function where the parameter n is 0 and the second function would handle any calls where the parameter n is an int (but not 0). And, yes. I've got the above working already. The tricky bits are providing more elaborate forms of pattern matching with the available syntax.

I'll be back shortly with some code...

When should I use a rule engine?

This is an interesting question that I think about quite a lot. I consider myself somewhat of a rule engine evangelist and I've always felt a bit annoyed that it's so difficult to explain the benefits of a rules based approach to others.

The textbook answer to the question is that a rule engine should be used when the problem is ill-structured and the solution is difficult or impractical to describe with an algorithm or when the knowledge required to formulate a solution changes frequently. But that's just words.

I've tried to find an ill-structured problem that is small enough to use as an example but I'm not really sure one exists. The best I've got so far is the problem of translating a number to text, where 0 <= number <= 99. It's an ill-structured problem that is easy to grasp but still translates to an ugly implementation with a lot of special-cases-handling in most programming languages. Not that it translates to a very pretty CLIPS application either... but I guess that comes with the territory.

Anyone got a better idea?

MPS inference engine, the rest of the implementation

In the last post I mentioned a few of the design choices I've made for the Rete Network implementation. The rest of the engine is quite straight forward and simple. There's really not much to talk about but I'll show some code anyway ;-).

Another thing though, and a bit more interesting really, is that I have been thinking about whether or not I should try to stay true to CLIPS' behaviour and functionality in the misc engine functions as well.

For example, the agenda function currently returns a list of all activations on the agenda and CLIPS prints them but returns no value. Similarly there's facts which behaves like get-fact-list instead. Used at the REPL there's little difference in what the user sees but the reason I've made them different is because then I can write other functions on top of them.

Ok. As promised, some code. Here is the run function (which uses agenda):

|(defun run (&optional (limit -1))
|  (do* ((curr-agenda (agenda) (agenda))
|        (execution-count 0 (+ execution-count 1))
|        (limit limit (- limit 1)))
|       ((or (eq limit 0)
|            (= (length curr-agenda) 0)) execution-count)
|    (let* ((activation (first curr-agenda))
|           (rhs-func (make-sym "RHS-" (string (activation-rule activation))))
|           (prod-mem (make-sym "PRODUCTION-" (string (activation-rule activation)) "-MEMORY")))
|      (funcall rhs-func activation)
|      (store '- activation prod-mem))))

and here is the assert function (I'm shadowing the built-in assert function, still accessible as cl:assert though):

|(defun assert (&rest facts)
|  (incf timestamp)
|  (dolist (fact facts)
|    (store '+ fact 'working-memory)
|    (mapcar #'(lambda (node) (funcall node '+ fact timestamp))
|            (gethash (type-of fact) (gethash 'root rete-network)))))

I hope that they are at least somewhat readable to others.

I've now finished the functions that make up the inference engine implementation. And it works... as long as you manually divide your program into alpha, beta and production nodes and connect them properly in the Rete Network ;-)

MPS inference engine, the Rete Network implementation

It's difficult to talk about the MPS defrule macro and the code it expands to without first explaining the environment in which it is meant to run. So I'll try to explain and describe my current thoughts and ideas that make up the design of the MPS inference engine in this and following posts.

The engine is made up of some I/O functions (assert and retract), the Rete Network, a Conflict Resolver and an Execution Engine. The Rete Network is the most central part of the whole thing so I'll start there.

It is basically implemented within a hash-table. This is the simplest possible representation of a Rete Network that I can think of. There are, of course, a few helper functions to abstract away some of the book keeping details of this design choice. During rule compilation there are functions for adding a node/memory and connecting nodes/memories with each other and at run time there are functions to propagate facts/tokens, access contents of and store facts/tokens in memory.

A processing node (for example an alpha node) is implemented as a function and is stored in the hash-table as well. A very simple LHS construct like:

|(defrule foo
|  (bar (baz ?baz&:(> ?baz 10)))
|  =>)

would be represented in the Rete Network by the following function:

|(defun bar-baz->-10 (key fact timestamp)
|  (when (> (deftemplate/bar-baz fact) 10)
|    (store key fact 'bar-baz->-10-memory)
|    (propagate key fact timestamp 'bar-baz->-10)))

A join node is represented by two functions (one for left and one for right activation) and is slightly more complex (but not much). If we change the LHS to:

|(defrule foo
|  (bar-1 (baz ?baz))
|  (bar-2 (baz ?baz))
|  =>)

we would have to create a join node for joining facts on the ?baz variable. It would look something like this:

|(let ((left-memory  'bind-bar-1-memory)
|      (right-memory 'bind-bar-2-memory))
|  (defun join-bar-1-baz-and-bar-2-baz-left (key token timestamp)
|    (dolist (fact (contents-of right-memory))
|      (when (eq (bar-1-baz (nth 0 token))
|                (bar-2-baz fact))
|        (store key (append token (list fact)) 'join-bar-1-baz-and-bar-2-baz-memory)
|        (propagate key (append token (list fact)) timestamp 'join-bar-1-baz-and-bar-2-baz))))
|
|  (defun join-bar-1-baz-and-bar-2-baz-right (key fact timestamp)
|    (dolist (token (contents-of left-memory))
|      (when (eq (bar-1-baz (nth 0 token))
|                (bar-2-baz fact))
|        (store key (append token (list fact)) 'join-bar-1-baz-and-bar-2-baz-memory)
|        (propagate key (append token (list fact)) timestamp 'join-bar-1-baz-and-bar-2-baz)))))

As you can see variables are expanded into "positions" everywhere in the functions. Variables are, however, available and bound in the execution context of the production node's RHS function.

There are some more bits and pieces that are good to know. The root node, for example, is a hash-table. Each deftemplate-type is a key and the value contains a list of alpha nodes.

Compilation consists of (apart from expanding the rule's LHS into a number of functions) a series of calls to add-to-root and connect-nodes. Since each node is responsible for propagating as well as storing facts/tokens in memory we can connect the processing nodes to each other directly. The example above would be compiled with:

|(add-to-root 'bar-1 #'bind-bar-1) ; This might not be necessary! We should
|(add-to-root 'bar-2 #'bind-bar-2) ; be able to connect directly to the join.
|(connect-nodes 'bind-bar-1 #'join-bar-1-baz-and-bar-2-baz-left)
|(connect-nodes 'bind-bar-2 #'join-bar-1-baz-and-bar-2-baz-right)
|(connect-nodes 'join-bar-1-baz-and-bar-2-baz #'production-foo)

This is all theory, though. I don't actually have all of the defrule macro in place so the final version might very well expand into something different. But I hope this conveys the general idea of the Rete Network implementation.

Handling deftemplates in MPS

There are three parts to my MPS (Minimal Production System) experiment, the "engine" itself and the deftemplate and defrule macros. So far, I've spent most of my time on the deftemplate macro. It turned out to be a bit trickier than I thought to implement. Mostly because I was stuck thinking about too complex macro expansions (which I never got to work).

Here is the syntax as BNF (well, sort of[1]):

|  deftemplate-construct
|    ::= (deftemplate deftemplate-name
|                     [comment]
|                     single-slot-definition*)
|
|  single-slot-definition
|    ::= (slot slot-name [default-attribute])
|
|  default-attribute
|    ::= (default ?NONE | expression) |
|        (default-dynamic expression)

It is a subset of CLIPS' deftemplate syntax. There are no multislots and no constraint-attributes for slots (types, ranges and such). But, apart from that, it is more or less the same[2]. And here's how it works:

|; SLIME 2007-03-14
|;;;; Compile file / [...] /mps. ...
|CL-USER> (in-package :mps)
|#[Package "MPS"]
|MPS> (deftemplate foo
|       (slot a-slot)
|       (slot a-default-slot (default 1))
|       (slot required-slot (default ?NONE)))
|FOO
|MPS> (foo)
|
|The slot: REQUIRED-SLOT in deftemplate: FOO requires an explicit value.
|   [Condition of type SIMPLE-ERROR]
|
|Restarts:
| 0: [ABORT] Return to SLIME's top level.
| 1: [ABORT-BREAK] Reset this process
| 2: [ABORT] Kill this process
|
|Invoking restart: Return to SLIME's top level.
|; Evaluation aborted
|MPS> (foo (required-slot 1))
|#S(DEFTEMPLATE/FOO :A-SLOT NIL :A-DEFAULT-SLOT 1 :REQUIRED-SLOT 1)
|MPS> (deftemplate bar
|       (slot default-gensym (default (gensym)))
|       (slot dynamic-gensym (default-dynamic (gensym))))
|BAR
|MPS> (bar)
|#S(DEFTEMPLATE/BAR :DEFAULT-GENSYM #:G31 :DYNAMIC-GENSYM #:G40)
|MPS> (bar)
|#S(DEFTEMPLATE/BAR :DEFAULT-GENSYM #:G31 :DYNAMIC-GENSYM #:G41)
|MPS>

The macro expands into a defstruct (deftemplate/foo) and another defmacro (foo) that is used as a constructor for the template. The reason it is a macro and not a regular function is because a function's arguments are evaluated whilst a macro's is not. And since there's no function named a-slot or a-default-slot etc. So we'd be thrown into the debugger if we tried to evaluate something like (foo (a-slot 1)).

Here's the macroexpansion of a simple template:

|MPS> (pprint (macroexpand-1 '(deftemplate foo
|                               (slot a)
|                               (slot b (default 1)))))
|
|(PROGN (DEFSTRUCT DEFTEMPLATE/FOO "" (A NIL) (B 1))
|       (DEFMACRO FOO (&REST SLOTS)
|         ""
|         (CALL-DEFSTRUCT-CONSTRUCTOR 'DEFTEMPLATE/FOO SLOTS)))
|; No value
|MPS>

Most of the code is spent checking that the template follows the syntax described in the BNF. The expansion itself is rather simple, almost trivial (it is the last progn below).

|(defmacro deftemplate (deftemplate-name &body body)
|  "
|  The deftemplate construct is used to create a template which can then
|  be used by non-ordered facts to access fields of the fact by name.
|
|  Examples:
|  (deftemplate object
|    (slot id (default-dynamic (gensym)))
|    (slot name (default ?NONE))           ; Makes name a required field
|    (slot age))
|  "
|
|  (macrolet ((signal-deftemplate-error (msg &rest args)
|               `(error (concatenate 'string "~&The deftemplate ~A contains at least one invalid slot-definition: ~S." ,msg)
|                       ,@args)))
|    (let ((comment "")
|          (defstruct-name (intern (concatenate 'string "DEFTEMPLATE/" (string deftemplate-name))))
|          (defstruct-slots '()))
|
|      ;; Extract the documentation string
|      (when (stringp (car body))
|        (setf comment (car body))
|        (setf body (cdr body)))
|
|      ;; Check syntax and extract slot-specifiers
|      (dolist (slot body)
|        (let* ((slot-name (cadr slot))
|               (curr-defstruct-slot `(,slot-name nil)))
|          (unless (eq (car slot) 'slot)
|            (signal-deftemplate-error "~&Expected SLOT instead of ~A."
|                                      deftemplate-name slot (car slot)))
|
|          (when (> (length slot) 2)
|            (dolist (default-attribute (cddr slot))
|              (unless (consp default-attribute)
|                (signal-deftemplate-error "~&Expected (default ?NONE|expression) or (default-dynamic expression) instead of ~A."
|                                          deftemplate-name slot default-attribute))
|              (unless (or (eq (car default-attribute) 'default)
|                          (eq (car default-attribute) 'default-dynamic))
|                (signal-deftemplate-error "~&Expected DEFAULT or DEFAULT-DYNAMIC instead of: ~A."
|                                          deftemplate-name slot (car default-attribute)))
|              (if (eq (car default-attribute) 'default)
|                  (if (eq (cadr default-attribute) '?NONE)
|                      (setf curr-defstruct-slot `(,slot-name (required ',slot-name ',deftemplate-name)))
|                      (setf curr-defstruct-slot `(,slot-name ',(eval (cadr default-attribute)))))
|                  (setf curr-defstruct-slot `(,slot-name ,(cadr default-attribute))))))
|
|          (setf defstruct-slots (append defstruct-slots (list curr-defstruct-slot)))))
|
|      `(progn
|         (defstruct ,defstruct-name
|           ,comment
|           ,@defstruct-slots)
|
|         (defmacro ,deftemplate-name (&rest slots)
|           ,comment
|           (call-defstruct-constructor ',defstruct-name slots))))))

and here are the functions used as helpers:

|(defun required (slot-name deftemplate-name)
|  (error "~&The slot: ~A in deftemplate: ~A requires an explicit value." slot-name deftemplate-name))
|
|(defun as-keyword (sym)
|  (intern (string-upcase sym) :keyword))
|
|(defun call-defstruct-constructor (defstruct-name &rest slots)
|  (let ((constructor (intern (concatenate 'string "MAKE-" (string defstruct-name)))))
|    (apply constructor (mapcan #'(lambda (slot)
|                                   `(,(as-keyword (car slot)) ,(cadr slot)))
|                               (car slots)))))

I should probably try to write a macro to abstract away all those (intern (concatenate 'string ...)) calls but otherwise, that's about it for deftemplate. Next up is getting all of the defrule construct working (which feels like a much tougher task).

[1] I hate that I still haven't found a good way of sharing code using Blogger. Tips and pointers are very welcome!

[2] The default and default-dynamic attributes in CLIPS take a variable number of expressions (at least according to the BNF found in the CLIPS Basic Programming Guide, Appendix H). I assume it assigns the value of the last as the default but I haven't tried. Anyway, if you want to evaluate several expressions in that place you're going to have to wrap it explicitly in a progn (effectively making it one expression).

A Minimal Production System

I've been experimenting a bit with bits and pieces of a production system in Common Lisp for a few days now. It all started as a fun exercise in Common Lisp macrology (the idea was to convert CLIPS syntax into executable Common Lisp code) but since things have fallen into place so neatly. I thought maybe it would be worth implementing parts of CLIPS syntax and functionality. So now, the only question is: which parts to implement?

I'm not going to do anything about data types and built-in functions. I'll add support for ?variables but that's about it (no multifields and no globals) and as far as constructs go I'll manage with defrule and deftemplate (no implied/ordered facts). If it doesn't turn out to be too difficult I'll try to include connected constraints in defrule but I won't bother with slot constraints in deftemplates (types and such). I'm hoping to include all CEs but it depends on how hairy it gets.

So. What have I missed? Is there something unnecessary on the list?

[Update 2008-08-03]: Hm. I guess I forgot about a bunch of engine commands. So here goes. Assert and retract seem stupid to leave out, as does run. I'll probably be annoyed not to have facts so I guess that's in as well. Load, clear, reset and agenda feel necessary but I think I'll only work with one conflict resolution strategy (depth) though.

The Absolute Minimum Every CLIPS Developer Absolutely, Positively Must Know About the Not-CE and Template-Pattern-Constraints (No Excuses!)

Ok. So I stole the title from Joel's very popular article about Unicode, but it's not just a way to get attention. The point is that there are some things about how CLIPS (and other Rule Engines) handle not that might not be all that obvious to programmers used to languages such as Python or Java.

More specifically, I'm talking about the difference between

|CLIPS> (defrule rule1
|  (spam (eggs ?eggs) (bacon ?bacon))
|  (test (not (and (eq ?eggs 1) (eq ?bacon 2))))
|  =>)

and

|CLIPS> (defrule rule2
|  (not (spam (eggs 1) (bacon 2))
|  =>)

You're not alone if you've ever made the mistake of thinking that wrapping a template-pattern-CE with a not would negate the constraints inside it. That's, however, not what the Not-CE does.

A logical not is the simplest possible operator. It simply returns True if the expression it applies to returns False and vice versa. In CLIPS, it's easy enough to figure out what expression a not applies to, but you might be surprised at how that expression is evaluated?

The Not-CE evaluates to True if there are no facts in Working Memory matching the pattern it applies to. You should think of not as short hand for Not-in-Working-Memory and not as a Not-Equals variant. I know it's not at all that obvious since there are no hints (compare Java's !=) but it should make it's behaviour less of a surprise.

LISA, Multislots and thoughts about Pattern matching

LISA has no multislots. That's just the way it is. You can add a list to a slot, but you have to match it as-is unless you provide a custom test-function.

About a week ago, Pedro Kröger announced on the Lisa Users mailing list that he was converting the Zebra puzzle from CLIPS to LISA. The rule syntax is so similar between the engines that it ought to have been a quite straightforward and simple exercise. But, since the CLIPS solution uses implied deftemplates (which are implemented as multislots) the LISA program wouldn't work.

This, and many other situations like it, has made me wonder about why nested fact structures aren't supported. Matching, on any level in a nested list, is actually described in Forgy's thesis (from 1979) but hasn't, for some reason, been implemented in most rule engines. Probably because it's faster to only allow flat structures.

The Rete implementation described in the thesis constructs an awful lot of nodes but I'm not sure you need all of them. A rule compiler ought to be able to figure out which part of a structure to test without doing too many feature-tests ("is the second subelement a list of 3 subelements" etc).

Expert Systems Book

I live about 50 m from the University of Chalmers and, naturally, I make use of their library.

During my visit last week I accidently found a very interesting 6-volume set of books named Expert Systems: The Technology of Knowledge Management and Decision Making for the 21st Century.

I'm currently reading the first volume and it is very good. It's a bit theoretical, but I can really recommend it to anyone interested in Expert Systems. Here's a short list of selected chapters to whet your appetite:

Volume 1.
Ch. 4 - Reasoning with Imperfect Information.

Volume 2.
Ch. 9 - Model of Reasoning with Conflicting Information Sources in Knowledge Based Systems.

Volume 3.
Ch. 24 - Cellular Automata Architectures for Pattern Recognition.

Volume 4.
Ch. 29 - Automatic Knowledge Discovery in Larger Scale Knowledge-Data Bases.
Ch. 34 - Neural Networks for Economic Forecasting Problems.

Volume 5.
Ch. 37 - Hybrid Expert Systems: An Approach to Combining Neural Computation and Rule-Based Reasoning.
Ch. 40 - Distributed Logic Processors in Process Indentification.

Volume 6.
Ch. 46 - Methodology for Building Case-Based Resaoning Systems in Ill-Structured Optimization Domains.

There are 50 chapters all in all spanning almost 2000 pages so this is probably going to take me a while.

Evolvable Rules

I stumbled on Evolvable Rules and REAT (Rete Evolution of Augmenting Topologies) yesterday whilst searching for interesting stuff to read. I'm not yet sure about what I think of the project but Greg sure got my attention.

The idea behind evolvable rules seem to be using Artificial Neural Network (ANN) techniques to generate a Rete network and some additional stuff like conflict resolution and the code needed for executing the RHS of a rule.

There's not that much info yet but Greg shares a few references that explain the technology he intends to use. Apart from Charles Forgy's Rete papers (the thesis and the article) and the Wikipedia description of the Rete algorithm (which we have another Charles to thank for) he also refers to Evolving Neural Networks through Augmenting Topologies by Kenneth O. Stanley and Risto Miikkulainen.

I haven't read the last paper that thoroughly (skimmed it once) and I'm only just learning about ANN technology but it seems to me that this requires a lot of work. And, if I understand correctly, it might not be very good at producing a Rete network at all and since there are "simple" rules that can be used to construct a Rete network based on, for example, an Abstract Syntax Tree I don't really see the point. Apart from being really cool of course ;-)

Anyway, I'm real interested to see how all this works out. I've had similar lines of thought myself after having read An Optimization Algorithm for Production Systems by Toru Ishida last summer. It would be really neat to find a way to automatically optimize (restructure) a Rete network based on the contents of the working memory without having to pass through all Facts and re-evaulate the goal of the optimization continuously.

The problem is that I have no idea of how, or even if, it can be accomplished. But I bet that if someone does it, it's probably going to have something to do with using ANN GA techniques. I'm not holding my breath though.

MultiField variables in pyRete

I've been thinking about MultiField variables quite a bit these past few weeks. I want to fit them into pyRete. However, they're a bit different from SingleField variables - as this snippet shows:

CLIPS> (deftemplate Person (multislot name))
CLIPS> (assert (Person (name Astrid Ingrid Eowyn Lindberg)))
[fact-1]
CLIPS> (defrule match-names
         (Person (name $?n1 $?n2))
        =>
         (printout t $?n1 " " $?n2 crlf))
CLIPS> (run)
() (Astrid Ingrid Eowyn Lindberg)
(Astrid) (Ingrid Eowyn Lindberg)
(Astrid Ingrid) (Eowyn Lindberg)
(Astrid Ingrid Eowyn) (Lindberg)
(Astrid Ingrid Eowyn Lindberg) ()

As you can see a MultiField variable can, and will, hold all possible combinations of values found in a multislot.

Given the current design of pyRete this means that I'll have to implement functionality to generate all combinations *within* a Node's match method. I'm slightly worried that this might make the processing quite a bit slower (I believe it's slower in Clips as well but I haven't benchmarked it so I can't really say for sure).

The other thing is that in Clips there's no way of nesting multifield structures. You cannot have a multifield of multifields. When it comes to Python, nested tuples/lists/dicts are common and I'd like to end up with an implementation that supports them.

The question is how to best do that?

In pyRete today there's no equivalent to Single or MultiField variables. Variables are bound to fact-instances and not parts of a fact (attributes of an object). You *can* introduce a variable in the RHS that binds to a part of a fact, but that cannot be done using pattern-matching.

>>> def rule(foo = Foo):
...   if foo(something = 100):
...     something_else = foo.something_else
...     # ...

So what we're talking about here is basically the possibility to do this:

>>> def rule(foo = Foo):
...   if foo(something = 100, something_else = something_else):
...     # ...

However, this will of course let you do far more sophisticated things than that. For example, you could "filter" out facts based on attribute values in another fact:

>>> def rule(foo = Foo, bar = Bar):
...   if foo(something = var) and bar(something_else = var):
...     # ...

My thoughts so far are that I'll use __ as Clips use $? and _ as Clips use ?. Named Single and MultiField variables would be _foo and __foo respectively. Variables will default to SingleField so foo and _foo are really the same thing.

Unfortunately those types of variable names already have a meaning in Python. Though I'm not sure I can afford to care about that since there's really no other way to distinguish variable names without breaking syntax rules (which I'm hoping to avoid).

Also, I'd like to introduce a way of specifying a minimum and possibly a maximum number of values a MultiField should take on. That would allow you to, for example, say that all MultiField variables must have at least one value. My Clips example would instead give the following result:

(Astrid) (Ingrid Eowyn Lindberg)
(Astrid Ingrid) (Eowyn Lindberg)
(Astrid Ingrid Eowyn) (Lindberg)

I don't really have a suggestion for syntax for that though, _foo_1toN doesn't really feel right :-)

If you've got any suggestions or thoughts about this I'd love to hear them.

Yet another starting-over post

This is the fifth time I've decided to start over (more or less from scratch) in my attempt to produce a Rete rule engine in Python. It' irritating that it's so hard to get the pyRete code into a shape I'm pleased with and I've been feeling kind of low these past few weeks since my last attempt to beat the RuleCompiler into submission failed miserably.

I know that developing a rule engine is no easy task and that others have devoted large portions of their lives doing it so 2 years isn't that much, really. I'd feel a whole lot better though if I was sure that I won't write this post again in a year or so.

Another Clips and Lisa comparison

I spent this evening with Emacs, CLisp and Lisa. I wanted to get this piece of Clips code working:

|CLIPS> (deftemplate movie
|  (multislot title))
|CLIPS> (deffacts movies
|  (movie (title "A" "B" "C"))
|  (movie (title "B" "C" "D"))
|  (movie (title "C" "D" "E")))
|CLIPS> (defrule chain
|  ?m1 <- (movie (title $? $?link&:(> (length$ $?link) 0)))
|  ?m2 <- (movie (title $?link $?))
|  (test (neq ?m2 ?m1)) ; Avoid infinite chains because of
|                       ; movie titles like "Liar Liar".
| =>
|  (printout t (fact-slot-value ?m1 title) " " (fact-slot-value ?m2 title) crlf))
|CLIPS> (reset)
|==> Activation 0      chain: f-1,f-2
|==> Activation 0      chain: f-2,f-3
|==> Activation 0      chain: f-1,f-3
|CLIPS> (run)
|("A" "B" "C") ("C" "D" "E")
|("B" "C" "D") ("C" "D" "E")
|("A" "B" "C") ("B" "C" "D")

Note how elegantly $?link matches any number of elements in a multislot.

Unfortunately, there are no multislots in Lisa. But, you're allowed to add a list (or even a list of lists) to a slot. Only thing is that you either have to match it as-is or provide your own predicate function to perform whatever test you need done. Here's what I came up with:

|LISA-USER> (deftemplate movie ()
|             (slot title))
|#[STANDARD-CLASS MOVIE]
|LISA-USER> (deffacts movies ()
|             (movie (title '("A" "B" "C")))
|             (movie (title '("B" "C" "D")))
|             (movie (title '("C" "D" "E"))))
|(#[DEFFACTS
|   MOVIES ; (#[MOVIE ; id -1 #x19FF2789] #[MOVIE ; id -1 #x19FF2ADD]
|    #[MOVIE ; id -1 #x19FF2E31])
|   #x19FF2EDD])
|LISA-USER> (defun overlap? (list-1 list-2)
|             (if (not (equal list-1 list-2))
|                   (dotimes (index (min (length list-1)
|                                        (length list-2)))
|                     (if (equal (subseq list-1 (- (length list-1) index 1) (length list-1))
|                                (subseq list-2 0 (+ index 1)))
|                       (return-from overlap? t))))
|             nil)
|OVERLAP?
|LISA-USER> (defrule chain ()
|             (?m1 (movie (title ?title1)))
|             (?m2 (movie (title ?title2)))
|             (test (overlap? ?title1 ?title2))
|             =>
|             (format t "~A ~A~%" ?title1 ?title2))
|#[RULE CHAIN]
|LISA-USER> (reset)
|T
|LISA-USER> (run)
|(A B C) (B C D)
|(B C D) (C D E)
|(A B C) (C D E)
|3

Not quite as elegant... but it works. I never managed to get the not equal test working in the rule so I had to place it in the overlap? function. Other than that, I think they're about as equivalent as they can get.

Going from Clips to Lisa

I'm currently experimenting with (and thinking about moving my current after-work projects to) Lisa. It's close enough to Clips to make it very easy to pick up but there are a few things that will take some time to get used to.

CL-USER> (in-package LISA-USER)
#[PACKAGE LISA-USER]
LISA-USER> (deftemplate foo
    (slot name)
    (slot age))
; Evaluation aborted
LISA-USER> (deftemplate foo ()
    (slot name)
    (slot age))
#[STANDARD-CLASS FOO]
LISA-USER> (assert (foo (name "Johan") (age 34)))
#[FOO ; id 1 #x1A015B01]
LISA-USER> (defrule remove-old-people
      ?foo <- (foo (age ?age&:(> ?age 30)))
      =>
      (retract ?foo))
; Evaluation aborted
LISA-USER> (defrule remove-old-people
      (?foo (foo (age ?age (> ?age 30))))
      =>
      (retract ?foo))
; Evaluation aborted
LISA-USER> (defrule remove-old-people ()
      (?foo (foo (age ?age (> ?age 30))))
      =>
      (retract ?foo))
#[RULE REMOVE-OLD-PEOPLE]
LISA-USER> (agenda)
#[ACTIVATION (INITIAL-CONTEXT.RETRACT-PEOPLE-OVER-30 (F-1) ; salience = 0)
#x19FAED25]
#[ACTIVATION (INITIAL-CONTEXT.RETRACT-PEOPLE-OVER-30 (F-1) ; salience = 0)
#x19FAED25]
For a total of 2 activations.
; No value
LISA-USER> (facts)
#[FOO ; id 1 #x19FAEBDD]
For a total of 1 fact.
; No value
LISA-USER> (run)
1
LISA-USER> (facts)
For a total of 0 facts.
; No value
LISA-USER>

Each of the ; Evaluation aborted lines marks where I was sent into the debugger. I'm not sure how I managed to get two activations but I suspect that part of the rule was already created when I got the error of not having specified any keywords. No warning about redefining the rule though!

Anyway, Lisa allows me to use the full power of Common Lisp side by side with a Rete-engine and I must admit I kind of like that idea. Lately, one of the things I've come to miss in Clips is the ability to define rules dynamically. I've tried using eval:

CLIPS> (eval "(defrule blah (whatever) =>)")
[EXPRNPSR3] Missing function declaration for defrule.
FALSE

but without success.

Whenever such a need has appeared I have used Python to dynamically generate the source code which I then load and run in Clips but I'd prefer to keep it all in one place and since I know better than to have delusions about pyRete performance I *think* this might be the way to go.

[2007-10-17] Update: Less than an hour after I posted this I learned that there is indeed a way to generate rules dynamically. The function is called build and is described in chapter 12.3.6 Evaluating a Construct within a String of the Clips Basic Programming Guide. Thanks Gary and Peter for pointing this out.

Drools puzzle #1

I completely missed the announcement for the Drools puzzles but it looks like lots of fun. Here's my solution to the first puzzle using Clips. You run it by executing the batch file:

CLIPS> (batch "... /ages-of-the-sons.bat")
TRUE
CLIPS> (clear)
CLIPS> (load "ages-of-the-sons.clp")
%%!***
TRUE
CLIPS> (generate-ages)
FALSE
CLIPS> (run)
What are the ages of the three sons of the old man?
2, 2 and 9
10 rules fired
40 mean number of facts (44 maximum).
0 mean number of instances (0 maximum).
4 mean number of activations (8 maximum)

And the FUD just keeps on coming...

I've been following James' posts from the European Business Rules Conference this week. Very interesting, if you're into that kind of stuff.

I was a bit surpised to learn that some Business Rule Engine vendor actually stood up saying that Rete, and Rete-based rule engines, are suitable for only 10% of all problems. I don't know what vendor it is but the logic is very similar to that found in a paper I just read (yes, apparently Rete becomes less and less significant, dropping from 20% to 10% in about a year ;-)

Rete or Not?

This is probably old stuff to most people but I only found InRule yesterday when I was checking to see if my del.icio.us subscriptions had anything interesting for me to read about. Anyway, on InRule's web site they have a paper titled Rete or Not?

The paper is an attempt to convince us that InRule's engine is better than Rete-based engines. AFAICT the reason is because InRule's engine can handle multiple modes for rule execution. But the paper is mostly about why Rete's no good anyway. Among other things, it says, "...users must understand how a Rete engine works before effectively writing rules" and, my favourite statement, "Roughly 20% of business applications have a need for Rete".

There are quite a few things in the paper that conflicts with my view of how the Rete Algorithm works and in general how a Rete-based rule engine works and what can and cannot be done with one. For example, the description of partial "left" and "right" matches doesn't make any sense.

To me, the Rete Algorithm is a solution to the many patterns/many facts matching problem. It's not the only solution and it might not even be the best solution but the claims they make in the paper are just too much.

I find it hard to take it seriously since they don't say which engine they're comparing against, come to think of it, they don't even say how the InRule engine works. Apart from saying that they have an execution mode that is similar to Rete and some other modes which work sequentially there's NO information about what's going on.

If they really want to convince people they have a better engine; why not run some benchmarks?

[2007-06-25] Update: Well, apparently: "InRule will benchmark using your performance needs, with real-life application and capacity scenarios. We recognize that every client environment is unique, and do not believe in making idle claims based on questionable proprietary benchmarks. We will demonstrate and substantiate actual performance metrics."

What about questionable (all benchmarks are) non-proprietary ones? It seems they don't do those either. What the **** does benchmark using your performance needs mean anyway? And, just so you know. I'm not kidding or making this up or anything! That's what they say on their web site. Right here (under Performance).

I'm adding the label humour to these posts. This is too much. It's gotta be a joke.

Rule-Based Programming in C (DDJ article)

Rule-Based Programming in C is an article by Lynwood Wilson that I found on the DDJ website. The article's main idea is that you don't need a Rule Engine for simpler situations. Instead you can use the "native" language of your application (in this case C).

Most of the article (2 out of 4 pages) is spent discussing strategies on how to control the execution of rules (using global variables!) to avoid infinite loops and such. The C code for the various control strategies seems even more complex than just embedding the rules as normal if/then clauses. At least that has the advantage of probably being what the next programmer to look at the code expects to see.

Wouldn't these 4 pages have been better spent discussing how to embed Clips?

Ruby Rools

Yet another Ruby Rule Engine. This one's not based on the Rete algorithm though, which makes it (at least for me), a lot less interesting than for example Ruleby. The author wants feedback on the latest release though so who knows where it will end up.