Ripple-Down Rules (RDR) Users' Manual

(Non)Introduction

This document assumes the user is familiar with the concept of Ripple-Down Rules. Those users seeking an introduction or justification are recommended to review material elsewhere, e.g. at Compton's site, or this author's introduction. The purpose of this document is to provide guidelines and an example for building, querying and modifying an RDR system. The implementation of the RDR framework described here is available on this site as rdr_impl.pl, with unit tests for consistency provided as rdr_unit_tests.pl.

Creating an RDR Tree, a tutorial

The default rule environment

The fundamental structure of the RDR system is the rule_env/2 term which contains both the if-then rule-tree stored as a "simple Ariadne zipper" and an env/2 term containing the current scenario stored as attributed values along with the currently most-likely conclusion.

Every RDR system starts with a default rule_env/2 that is initialized by the init_rule_env/1 predicate. Let's get started then. Load rdr_impl.pl into your Prolog environment and call that goal now:

?- init_rule_env(RDR).

In this tutorial, we will be building a rule-tree that contains a (very small) universe for the Animal guessing game, represented with the following model:

IF true THEN none
EXCEPT IF 'four legs' THEN pony
       EXCEPT IF barks THEN dog
              EXCEPT ⊥
              ELSE IF meows THEN cat
                   EXCEPT ⊥
                   ELSE ⊥
       ELSE IF swims THEN fish
            EXCEPT ⊥
            ELSE IF 'spins web' THEN spider
                 EXCEPT ⊥
                 ELSE ⊥
ELSE ⊥

Adding rules

Each RDR system then is tailored to the problems it must solve by adding exception rules and else rules to the knowledge base with the predicate add_rule/4. But first, to add a rule to the tree, the rule, itself, must first be created. An IF-THEN rule/2 term is composed of a cond/1 term (its condition or test) and a concl/1 term (its conclusion). The system provides two ways to go about creating rules: the predicate make_simple_rule/3 or predicates that allow you to construct the cond/1 and concl/1 terms by hand — make_cond/2, present/2 for cond/1 and assume/2 for concl/1.

The rules developed in this tutorial are simple ones, but the cond/1 type description and the file rdr_unit_tests.pl shows more complex examples. Let's add our first rule to the system:

?- init_rule_env(rule_env(Tree, Env)),
   make_simple_rule('four legs', pony, Rule),
   add_rule(left, Rule, Tree, NewTree),
   RDR = rule_env(NewTree, Env).

What we've done here is add an EXCEPT branch, that is to say, the left branch, to the top-level rule — the top-level rule always succeeds with a none conclusion. We've added an exception; we're saying that IF the environment contains the attribute 'four legs', THEN we conclude the animal is a pony: every little girl's dream and first guess.

This is all well and good for adding rules (EXCEPT or ELSE) to the top-level, but how do we navigate through the rule tree to add rules to specific branches in our concern? There are two such ways.

The normal way for going about adding rules is as in the following scenario: the system runs a scenario, and the analyst determines that the conclusion is not what is needed. When the scenario is run, the rule_env/2 term is left in the state where the rule that resulted in the conclusion is left in focus. In this case, it is a very simple matter to call add_rule/4 against that focused element, and then settle/2 the tree for the next scenario.
However, if we are starting with the default knowledge base, and we wish to bootstrap the system to some semblance of functionality (as we are doing in this tutorial), we must navigate the knowledge base manually. The predicates advance/3 and withdraw/2 provide this functionality. To descend into an EXCEPT branch, one would call advance(left, Tree, NewTree); the ELSE branch, advance(right, Tree, NewTree). To reascend up the tree to a parent rule, one simply calls withdraw(Tree, NewTree), and the system automagically ascends the branch, incorporating any modifications to the knowledge base as it goes (ah! the magic of zippers!).

Given that we are bootstrapping our knowledge base, let us complete it using the navigational tools provided by advance/3 and withdraw/2:

?- init_rule_env(rule_env(Tree, Env)),
   make_simple_rule('four legs', pony, FourLegs),
   add_rule(left, FourLegs, Tree, T1),
   advance(left, T1, T2),
   make_simple_rule(barks, dog, Dog),
   add_rule(left, Dog, T2, T3),
   make_simple_rule(swims, fish, Fish),
   add_rule(right, Fish, T3, T4),
   advance(left, T4, T5),
   make_simple_rule(meows, cat, Cat),
   add_rule(right, Cat, T5, T6),
   withdraw(T6, T7),
   advance(right, T7, T8),
   make_simple_rule('spins web', spider, Spider),
   add_rule(right, Spider, T8, T9),
   settle(T9, NewTree),
   RDR = rule_env(NewTree, Env).

Of course, the above can be greatly simplified using a definite clause grammar, and the predicate add_animals/2 in the file rdr_unit_tests.pl demonstrates this simplification, but the above straightforward query, albeit complex, does produce the example knowledge base for this tutorial.

Running the system

Great! We have a working knowledge base, all that needs be done is to initialize the env/2 to the scenario at hand and then call run_rule/2. Let's do that in two scenarios: one for a spider, and one for a cat.

Now, the guessing game Animal provides a nice framework for describing the structure of RDR, but RDR is not Animal, in that Animal is an interactive environment, but, in RDR, all the facts are present at the get-go, so we initialize our RDR environment pretending to engage in an interactive dialogue with the system. To add these attributed values to the environment, we call the predicate update_env/3:

?- init_rule_env(rule_env(T0, Env0)),
   add_animals(T0, Tree),
   update_env('spins web' - _, Env0, Env1),
   run_rule(rule_env(Tree, Env1), RuleEnv1),
   RuleEnv1 = rule_env(_, NewEnv1),
   run_concl(NewEnv1, Concl1),
   update_env('four legs' - _, Env0, E1),
   update_env(meows - _, E1, Env2),
   run_rule(rule_env(Tree, Env2), RuleEnv2),
   RuleEnv2 = rule_env(_, NewEnv2),
   run_concl(NewEnv2, Concl2).

As we can see from executing that query, RuleEnv1 has the complete rule tree, focused on the rule that rendered Concl1 (the spider finding). Similarly, RuleEnv2 yields the tree with Concl2 (the cat finding).

Modifying the system

The above findings seems satisfactory, but let's explore an area of the RDR system that may be improved. Not everything that swims is a fish; so, let's run the system, reach that unsatisfactory conclusion, and then modify and rerun the system to reach a satisfactory conclusion with the modified knowledge base. No new predicates need be introduced to affect this change.

?- init_rule_env(rule_env(T0, Env0)),
   add_animals(T0, Tree),
   update_env(swims - _, Env0, E1),
   update_env(flies - _, E1, Env1),
   run_rule(rule_env(Tree, Env1), rule_env(T1, Wrong)),
   run_concl(Wrong, NotDuck),
   make_simple_rule(flies, duck, DuckRule),
   add_rule(left, DuckRule, T1, T2),
   settle(T2, NewTree),
   run_rule(rule_env(NewTree, Env1), rule_env(_, Correct)),
   run_concl(Correct, Ducky).

As you can see from this sample query, adding a new rule happens right in place, as the rule tree already has the focus on the rule that rendered the decision. Another important point, after the modification of the rule tree is complete, settle/2 must be called to correct and refocus the rule tree to the top-level rule (in fact, the rule tree must be settled for each new scenario, but settle/2 is only necessary after modifications to the knowledge base occur.

Tutorial conclusion

This concludes the tutorial section of this RDR user manual, the rest of this manual provides the descriptions of the types and predicates used to build, to run, and to modify RDR systems.

Types

Below are the types of the terms used in the predicates of this RDR system.

Type:	`assoc/2`
Structure:	`Key - Value`
Description:	The association relation between `Key` and `Value` used by `attrib_vals/N` and elsewhere.

Type:	`attrib_vals/N`
Disjoint values:	`[]` or `[assoc/2 \| KeyVals]`
Description:	Contains the attributed values that describe the current scenario.

Type:	`concl/1`
Composed of:	`concl(Pred/2)`
Description:	This term is the conclusion, the `THEN` clause of an `IF-THEN` rule/2 term. Its argument is a predicate of the general form ... `pred(+attrib_vals/N, -Ans)` ... that accepts the attributed values of the current scenario and returns the result as `Ans`.

Type:	`cond/1`
Composed of:	`cond(Pred/1)`
Description:	This term is the condition, the `IF` clause of an `IF-THEN` rule/2 term. Its argument is a predicate of the general form ... `pred(+attrib_vals/N)` ... that accepts the attributed values of the current scenario and yields the true of the statement of the condition based on the values of the attributes.
Example:	One way to model the condition `IF foo > 5` is as follows: foo5(`KeyVals`) :- member(foo - `Val`, `KeyVals`), `Val` > 5. The `cond/1` term would then be `cond(foo5)`.

Type:	`dir/0`
Disjoint values:	`left` or `right`
Description:	The direction of the path taken through the rule tree. The convention for this system is the `EXCEPT` branch is the `left` path and the `ELSE` branch is the `right` one.

Type:	`env/2`
Composed of:	`env(attrib_vals/N, concl/1)`
Description:	This term is the environment in which the knowledge base renders judgments. The knowledge base runs rules against its `attrib_vals/N`, iteratively improving its `concl/1` term until no more `rule/2` terms remain, leaving the best judgment.

Type:	`rule/2`
Composed of:	`rule(cond/1, concl/1)`
Description:	Represents an `IF-THEN` rule in the knowledge base.

Type:	`rule_env/2`
Composed of:	`rule_env(zip/2, env/2)`
Description:	The primary structure of the RDR system. The `rule_env/2` contains the `IF-THEN` rule tree as a "simple Ariadne zipper" as well as the environment which contains the attributed values of the current scenario as well as the currently most-likely conclusion.

Predicates

The below predicates construct, modify, and query the RDR system.

add_rule(+dir/0, +rule/2, +zip/2, -zip/2)
Adds a rule/2 branch to the current position (so indicated by the dir/0) into the knowledge base.
advance(+dir/0, +zip/2, -zip/2)
Descends into the rule tree along the branch specified by the dir/0 argument.
assume(+Ans, -concl/1)
Creates a concl/2 term that accepts, but ignores, any input attrib_vals/N and simply returns Ans as the result of calling run_concl/2.
init_rule_env(-rule_env/2)
Provides the default rule_env/2 that every rule system starts with:
```
IF true THEN none
EXCEPT ⊥
ELSE ⊥
```
make_equiv_cond(+assoc/2, -cond/1)
Creates a cond/1 term that asserts Key is associated with the value Value.
make_simple_rule(+Key, Ans, -rule/2)
Creates a rule/2 term where the IF clause, the cond/1 term, simply checks for the presence of Key and the THEN clause, the concl/1 term, simply returns the Ans value.
present(+Key, -cond/1)
Creates a cond/1 term that asserts Key is present in the attrib_vals/N term.
run_concl(+env/2, -Ans)
Calls the current concl in the env/2, feeding it the attrib_vals/N. The result of that call is Ans.
run_rule(+rule_env/2, -rule_env/2)
Runs the system. Applies the rules against the attributed values stored in the environment and returns the focus on the rule that resulted in the most plausible conclusion.
settle(+zip/2, -zip/2)
Called after modifying the knowledge base to refocus the system on the top-level rule, correcting the knowledge base from the point of modification up to the top-level rule.

Alternate description: the fix point of withdraw/2.
update_env(+assoc/2, +env/2, -env/2)
Add some new information to our environment.
withdraw(+zip/2, -zip/2)
Reascends the rule tree incorporating any modifications made in the branch at the focus.