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.