The meta rule protocol (MRP) reifies the internal actions of the forward chainer in terms of backward chaining goals. This allows the user to debug, modify, or even replace the default behavior of the forward chainer. The basic hooks into the Forward Chaining Cycle provided by the MRP include conflict resolution and rule firing. Each context may have a meta-rule defined for it which behaves as a meta-interpreter for that context. For example, if no meta-rule is defined for a context it behaves as if it were using the following meta-rule:
(defrule ordinary-context :backward
((ordinary-context)
<--
(start-cycle)
(instantiation ?instantiation)
(fire-rule ?instantiation)
(cut)
(ordinary-context)))
This rule describes the actions of the forward chaining cycle for this context. Firstly start-cycle performs some internal initializations and updates the conflict set. It is essential that this is called at the start of every cycle. Next the preferred instantiation is selected from the conflict set by the call to instantiation and is stored in the variable ?instantiation. The rule corresponding to this is fired (by fire-rule) and the recursive call to ordinary-context means that the cycle is repeated. The cut is also essential as it prevents back-tracking upon failure. Failure occurs when there are no more instantiations to fire (the instantiation predicate fails) and this causes control to be passed on as normal.
A meta-rule may be assigned to a context with the :meta keyword of the defcontext form. The argument of the :meta keyword is the list of actions to be performed by the context. For example, a context using the above ordinary meta-interpreter can be defined by
(defcontext my-context :meta ((ordinary-context)))
This implicitly defines the rule
(defrule my-context :backward
((my-context)
<--
(ordinary-context)))
and whenever this context is invoked, the rule of the same name is called. The context could equally well have been defined as
(defcontext my-context :meta
((start-cycle)
(instantiation ?instantiation)
(fire-rule ?instantiation)
(cut)
(my-context)))
Sometimes it is useful to manipulate the entire conflict set. For this purpose the action (conflict-set ?conflict-set) will return the entire conflict set in the given variable, in the order specified by the context's conflict resolution strategy. The actions
(conflict-set ?conflict-set)
(member ?instantiation ?conflict-set)
(instantiation ?instantiation)
although the latter is more efficient.
Now that the user has access to the instantiations of rules, functions are provided to examine them.
The following functions may be called on instantiations:
inst-rulename (instantiation)
which returns the name of the rule of which this is an instantiation.
inst-token (instantiation)
which returns the list of objects (the token ) which match the rule. These appear in reverse order to the conditions they match.
inst-bindings (instantiation)
which returns an a-list of the variables matched in the rule and their values.
This meta-rule displays the conflict set in a menu to the user and asks for one to be selected by hand on each cycle. Note that we have to check both that there were some instantiations available, and that the user selected one (rather than clicking on the Abort button).
(defrule manual-context :backward
((manual-context)
<--
(start-cycle)
(conflict-set ?conflict-set)
(test ?conflict-set)
; are there any instantiations?
((select-instantiation ?conflict-set)
?instantiation)
(test ?instantiation)
; did the user pick one?
(fire-rule ?instantiation)
(cut)
(manual-context)))
where the function select-instantiation could be defined as
(defun select-instantiation (conflict-set)
(tk:scrollable-menu conflict-set
:title "Select an Instantiation:"
:name-function #'(lambda (inst)
(format nil "~S: ~S"
(inst-rulename inst)
(inst-bindings inst))))
Now a context could be defined by
(defcontext a-context :strategy ()
:meta ((manual-context)))
Meta-rules can also be used to provide an explanation facility. A full implementation of the explanation facility described here is included among the examples distributed with KnowledgeWorks, and is given also in Explanation Facility
Suppose we have a rule about truck scheduling of the form
(defrule allocate-truck-to-load :forward
(load ?l size ?s truck nil destination
?d location ?loc)
(test (not (eq ?d ?loc)))
(truck ?t capacity ?c load nil location ?loc)
(test (> ?c ?s))
-->
(assert (truck ?t load ?l))
(assert (load ?l truck ?t)))
and we wish to add an explanation by entering a form like
(defexplain allocate-truck-to-load
:why ("~S has not reached its destination
~S and ~ does not have a truck
allocated, ~ ~S does not have a load
allocated, and ~ with capacity ~S is
able to carry the load, ~ and both
are at the same place ~S"
?l ?d ?t ?c ?loc)
:what ("~S is scheduled to carry ~S to ~S"
?t ?l ?d)
:because ("A customer requires ~S to be
moved to ~S" ?l ?d))
where the :why form explains why the rule is allowed to fire, the :what form explains what the rule does and the :because gives the ultimate reason for firing the rule.
The stages in the implementation are as follows:
defexplain to store the explanation information in, say, a hash-table keyed against the rule nameadd-explanation takes an instantiation, fetches the explanation information from the hash-table and the variable bindings in the instantiation, and adds the generated explanations to another global data structure, something like:(defun add-instantiation (inst)
(let ((explain-info
(gethash (inst-rulename inst)
*explain-table*)))
(when explain-info
(do-the-rest explain-info
(inst-bindings inst))))))
(defrule explain-context :backward
((explain-context)
<--
(start-cycle)
(instantiation ?inst)
((add-explanation ?inst))
(fire-rule ?inst)
(cut)
(explain-context)))
Another application of meta-rules is in the manipulation of uncertainty. A full implementation of the uncertain reasoning facility described below is included among the examples distributed with KnowledgeWorks, and also in Uncertain Reasoning Facility.
In this example, we wish to associate a certainty factor with objects in a manner similar to the MYCIN system (see Rule-Based Expert Systems , B. G. Buchanan and E. H. Shortliffe, Addison-Wesley 1984). When we assert an "uncertain" object we wish it to acquire the certainty factor of the instantiation which is firing. We define the certainty factor of an instantiation to be the certainty factor of all the objects making up the instantiation multiplied together. Additionally, we wish rules to have an implication strength associated with them which is a multiplicative modifier to the certainty factor obtained by newly asserted uncertain objects. The general approach is as follows:
*c-factor* to hold the certainty factor of the current instantiation and *implic-strength* to hold the implication strength of the rule, and a class of "uncertain" KnowledgeWorks objects:(def-kb-class uncertain-kb-object ()
((c-factor :initform (* *c-factor* *implic-strength*)
:accessor object-c-factor)))
The uncertain objects should contain this class as a mixin.
(defun inst-c-factor (inst)
(reduce '* (inst-token inst) :key 'object-c-factor))
(defrule uncertain-context :backward
((uncertain-context)
<--
(start-cycle)
(instantiation ?inst)
((setq *c-factor* (inst-c-factor ?inst)))
(fire-rule ?inst)
(cut)
(uncertain-context)))
*implic-strength* so that rules may set their implication strength by calling the action:
((implication-strength <number>))
A rule could be defined similarly to:
(defrule my-rule :forward
(my-class ?obj1)
(my-class ?obj2)
-->
((implication-strength 0.6))
(assert (my-class ?obj3)))
where the certainty factor of the new object ?obj3 will automatically become:
(* (object-c-factor ?obj1) (object-c-factor ?obj2) 0.6)
While this is an extremely simplistic version of uncertain reasoning, it suggests how a more elaborate treatment might be approached.
A conflict resolution strategy is a list of conflict resolution tactics. A conflict resolution tactic is a function which takes as arguments two rule instantiations, and returns t if and only if the first is preferred to the second, otherwise NIL. A conflict resolution tactic may be defined by
(deftactic <tactic-name> {<type>} <lambda-list> [<doc-string] <body>)
where <tactic-name> is the name of the tactic and of the function being defined which implements it, and <lambda-list> is a two argument lambda-list. <type> may be either :static or :dynamic, defaulting to :dynamic. A dynamic tactic is one which looks into the objects which match the rule to make up the instantiation; a static one does not. For example, a tactic which prefers instantiations which match, say, truck objects to instantiations which do not could be defined as static. However, if it looks into the slot values of the truck object it should be defined as dynamic. Static tactics are treated more efficiently but wrongly declaring a tactic as static will lead to incorrect conflict resolution. If doc-string is given, then it should be a string. The value can be retrieved by calling the function documentation with doc-type function.
It is an absolute requirement that there exist no instantiations for which
(<tactic-name> <instantiation1> <instantiation2>)
(<tactic-name> <instantiation2> <instantiation1>)
both return t. Consequently, for any single given instantiation
(<tactic-name> <instantiation> <instantiation>)
The function which defines a conflict resolution tactic should be computationally cheap as it is used repeatedly and frequently to compare many different pairs of instantiations.
The following tactic prefers instantiations with truck objects to ones without
(deftactic prefer-trucks :static (inst1 inst2)
(flet ((truck-p (obj) (typep obj 'truck)))
(and (some #'truck-p (inst-token inst1))
(notany #'truck-p (inst-token inst2)))))
Note that this tactic would be incorrect if we did not check that the second instantiation does not refer to any trucks (otherwise it would always return t if both instantiations contain trucks). It can safely be declared as static as it does not look into the slots of the objects which make up the instantiation.
This tactic implements alphabetical ordering on rule names:
(deftactic alphabetical-rulename :static (inst1 inst2)
(string< (symbol-name (inst-rulename inst1))
(symbol-name (inst-rulename inst2))))
This tactic prefers instantiations which bind the variable ?x to zero:
(deftactic prefer-?x=0 :dynamic (inst1 inst2)
(flet ((fetch-?x (inst)
(cdr (assoc '?x (inst-bindings inst)))))
(and (eql 0 (fetch-?x inst1))
(not (eql 0 (fetch-?x inst2))))))
Note that again we must not forget to check that ?x is not zero in the second instantiation. This tactic must be declared dynamic as ?x must have been instantiated from the slots of one of the matched objects.
The final tactic is for the example of uncertain reasoning and implements a method of preferring "more certain" instantiations:
(deftactic certainty :dynamic (inst1 inst2)
(> (inst-c-factor inst1) (inst-c-factor inst2)))
This tactic must be dynamic if the certainty factors of objects can be modified after creation. If this is forbidden the tactic could be defined as static. Then the context defined by
(defcontext my-context :strategy (priority certainty))
will prefer instantiations of rules with higher priority or, if this does not discriminate sufficiently, instantiations which are "more certain".
KnowledgeWorks and Prolog User Guide (Macintosh version) - 26 Feb 2015