**Implementation study**

In the last entry, we introduced what RDR (ripple-down rules) are and reviewed the types that comprise an example system. This entry will show how those types are used to implement such a system.

`> ``module ``RDRFinding` where

This module scans the RDR tree in context to give BOTH the best-fitting conclusion AND the final Branch that led to the ultimate conclusion (in the form of a zipper so that the branch may be replace in place using standard operations on the zipper).You have already encountered the above imported modules, but the next two modules need an introduction. The first>importRDRTypes

>importData.Transitive

>importData.Zipper

>importData.BinaryTree

>importData.Map(Map)

>importqualifiedData.MapasMap

>importControl.Monad.State

>importData.Maybe

`> ``import` `Control`.`Monad`.`Utils`

contains my weird and wonderful syntax when I'm using monads for parsing or logic tasks. The parsing syntax you've seen before (see the critique), but I do add one new syntactic construct:`(>>|) :: m a → (a → b) → m b`

because I'm always doing "`m >>= ``return` . f

", and `liftM`

seems to feel oddly backwards when I'm visualizing data flow. The next`> ``import` `Data`.`Mutable`

provides a generic operation for changing a data structure:So, what's the game? We have anclassMutablet dir val | t → dir, t → valwhere

mutate :: dir → val → t →Maybet

`Environment`(a set of attributed values) combined with a

`RuleTree`into the

`State Monad`. What we do is guide the values in the environment through the rule tree (where a successful

`Condition`chooses the

`EXCEPT`

branch and displaces the currently saved `Conclusion`with the one associated with this

`Rule`, and conversely if the

`Condition`fails, the

`ELSE`

branch is selected, without displacing the currently saved `Conclusion`). When we reach a

`Leaf`, we return our current position in the tree (the current state of the

`Zipper`) along with the last valid

`Conclusion`. All this is done by

`runRule`

:> runRule ::RuleFindinga b c k v

> runRule = get >>= λ (RuleEnvroot env) . runRule' root env

> runRule' ::RuleTreea b c k v →Environmentk v b c

> →RuleFindinga b c k v

> runRule' tree env@(Envks curr)

> = branch tree >>: λ (cond, conc) .

>let(dir, concl) = liftZdir (testCond cond env conc)

>inadvance dir tree >>: λ path .

> put (RuleEnvpath (Envks concl)) >> runRule

> where x >>: f = tryS curr x f

*Whew!*This is a mouthful in the number of functions it introduces, but conceptually,

`runRule`

is rather straightforward. Let's break it down.The function

`runRule`

, itself, merely destructures the `RuleTreeEnv`term, passing that information to

`runRule'`

, so let's move right on to that worker function. First, let's examine the funny syntactic construct, `(>>:)`

— what is this monadic operator doing? We see from its definition that it calls `tryS`

:So,> tryS :: a →Maybeb → (b →Statec a) →Statec a

> tryS x may f =maybe(returnx) f may

`tryS`

lifts the `State Monad`into semideterminism (using the

`Maybe Monad`). As an aside, perhaps, then,

`runRule'`

could be rewritten as a `StateT`over the

`Maybe Monad`... perhaps an intrepid reader will gain a ⊥-trophy for an implementation and explanation?

Using that monadic operator,

`(>>:)`

, we get the current `branch`

in focus (bailing if the focus is on a `Leaf`) ...

... then we test the condition at that> branch ::RuleTreea b c k v

> →Maybe(Conditiona (Knowledgek v),

>Conclusionb c (Knowledgek v))

> branch (Zip_ (Branch(Rulecond conc) _ _)) =Just(cond, conc)

> branch (Zip_Leaf) =Nothing

`Branch`...

I do this little> testCond ::Conditiona (Knowledgek v)

> →Environmentk v ca cb

> →Conclusionca cb (Knowledgek v)

> →Either(Environmentk v ca cb)

> (Environmentk v ca cb)

> testCond (Cond_ test) env@(Envkb _) conc1

> | test kb =Left$Envkb conc1

> |otherwise=Rightenv

> liftZdir ::Either(Environmentk v ca cb)

> (Environmentk v ca cb)

> → (BinDir,Conclusionca cb (Knowledgek v))

> liftZdir test =either(λ (Env_ c) . (L, c))

> (λ (Env_ c) . (R, c))

> test

*pas de deux*between

`testCond`

and `liftZdir`

because somehow it just feels right to use the `Either`type here. Perhaps, sometime later Arrows will come into play. At any rate,

`liftZdir . testCond`

can be considered one function that returns the appropriate leg of the branch to continue finding the best viable `Conclusion`, as well as the best current

`Conclusion`reached from applying the

`Environment`to the

`Condition`.

Given that information, we now

`advance`

down that `path`

, updating the state, and continue to test recursively, until we reach a `Leaf`, at which point we have our answer (the ultimate viable

`Conclusion`).

If we're happy with that answer, we call

`runRule`

with a new transaction (in other words, a fresh `Environment`), and the

`Zipper`pointing back at the top of the

`RuleTree`. If we're not happy, then we're given the ability to add a new

`Rule`to the

`RuleTree`. We do this with

`addRule`

:The above functions are the meat of the implementation for this simple RDR system. There are a few conveniences that the following functions provide. The first one is> addRule ::BinDir→Rulea b c (Knowledgek v)

> →RuleTreea b c k v →RuleTreea b c k v

> addRule dir rule (Ziphist branch)

> =letruleB =BranchruleLeafLeaf

>inZiphist (mutate dir ruleB branch)

`answer`

that scans the rule tree, making the best conclusion, and then backs up one step to provide the user access to the branch in case the precipitating rule finding wasn't exactly giving the desired result.The next three functions help to automate the creation of the rule parts,> answer ::RuleTreeEnva b c k v →RuleTreeEnva b c k v

> answer rule =letRuleEnvz ans = execState runRule rule

>inRuleEnv(fromJust $ withdraw z) ans

`Condition`s and

`Conclusion`s. The function

`mkCond`

creates a test function with the assumption that the knowledge store contains a `(k,v)`

pair. It does the lookup in the knowledge store and passes the extracted values to the test function (which, as with any good predicate, returns either `True`or

`False`). If we can't find the key, I guess, for now, we'll assume the returned value is

`False`:

This completes the implementation of this RDR system. The next entry will create a small RDR system, based on the game Animal, to demonstrate how the system works.> mkCond ::Ordk ⇒ k → (v →Bool) →Conditionk (Knowledgek v)

> mkCond key fn =Condkey $ λ ks .maybeFalsefn (Map.lookup key ks)

> present ::Ordk ⇒ k →Conditionk (Knowledgek v)

> present =flipmkCond (constTrue)

> assume :: k →Conclusionk k env

> assume key =Conclkey (constkey)

## No comments:

Post a Comment