## [d43b93]: doc / html / overview / rules / backward_chaining.html Maximize Restore History

### backward_chaining.html    254 lines (237 with data), 12.9 kB

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253``` ``` Backward Chaining

Please Make a Donation:

Hosted by:

Backward Chaining

Backward chaining rules are processed when your program asks pyke to prove a specific goal. Pyke will only use activated rule bases to do the proof.

Example

Consider this example:

1  son_father:  2      use child_parent(\$son, \$father, (), son, father)  3      when  4          family.son_of(\$son, \$father, \$_)   5  son_mother:  6      use child_parent(\$son, \$mother, (), son, mother)  7      when  8          family.son_of(\$son, \$_, \$mother)   9  daughter_father: 10      use child_parent(\$daughter, \$father, (), daughter, father) 11      when 12          family.daughter_of(\$daughter, \$father, \$_)  13  daughter_mother: 14      use child_parent(\$daughter, \$mother, (), daughter, mother) 15      when 16          family.daughter_of(\$daughter, \$_, \$mother)  17  grand_parent_and_child: 18      use child_parent(\$grand_child, \$grand_parent, (grand), 19                       \$grand_child_type, \$grand_parent_type) 20      when 21          child_parent(\$grand_child, \$parent, (), \$grand_child_type, \$_) 22          child_parent(\$parent, \$grand_parent, (), \$_, \$grand_parent_type)  23  great_grand_parent_and_child: 24      use child_parent(\$gg_child, \$gg_parent, (great, \$prefix1, *\$rest_prefixes), 25                       \$gg_child_type, \$gg_parent_type) 26      when 27          child_parent(\$gg_child, \$parent, (), \$gg_child_type, \$_) 28          child_parent(\$parent, \$gg_parent, (\$prefix1, *\$rest_prefixes), 29                       \$_, \$gg_parent_type)

Identifying Backward-Chaining Rules

These rules draw the same conclusions as the forward-chaining example; but you'll notice three differences:

1. The rule's if and then parts are reversed.
2. The rules use different keywords: use for the then clause and when for the if clause.
3. The facts established by backward-chaining do not have a knowledge base name prefix. In this case, the knowledge base name defaults to the rule base category of this rule base (it's root rule base name).

How Backward-Chaining Rules are Run

These rules are not used until you ask pyke to prove a goal.

The easiest way to do this is with some_engine.prove_1_ or some_engine.prove_n_. Prove_1 only returns the first proof found and then stops (or raises pyke.CanNotProve). Prove_n is a generator that generates all possible proofs (which, in some cases, might be infinite). In both cases, you pass a tuple of arguments and the number of variable arguments as the last two parameters. The total number of arguments for the goal is the sum of the length of the actual arguments that you pass plus the number of variable arguments that you specify.

Both functions return the variable bindings for the number of variable arguments you specified as a tuple, along with the plan.

Running the Example

>>> import pyke >>> engine = pyke.engine('examples') >>> engine.assert_('family', 'son_of', ('michael', 'bruce', 'marilyn')) >>> engine.assert_('family', 'son_of', ('bruce', 'thomas', 'norma')) >>> engine.assert_('family', 'daughter_of', ('norma', 'allen', 'ismay')) >>> engine.activate('bc_example') >>> for vars, no_plan in engine.prove_n('bc_example', 'child_parent', ...                                     ('michael',), 4): ...     print vars ('bruce', (), 'son', 'father') ('marilyn', (), 'son', 'mother') ('thomas', ('grand',), 'son', 'father') ('norma', ('grand',), 'son', 'mother') ('allen', ('great', 'grand'), 'son', 'father') ('ismay', ('great', 'grand'), 'son', 'mother')

Pyke performs the proof by:

1. Checking to see if the goal is simply a known fact. If so, it has a proof!
2. Look for the first backward-chaining rule that concludes the goal in its use clause.
• If not found, the goal fails.
• If found, try to recursively prove all of the subgoals in the rule's when clause.
• If this succeeds, the goal is proven.
• If this fails, go back to step 2 and look for the next rule that concludes the goal in its use clause.

Backward-Chaining Defined

Note how the rules are combined in the opposite direction from forward-chaining rules. Here the first rule's if (when) clause is linked backwards to the next rule's then (use) clause.

This is why these rules are called backward-chaining rules. This is also referred to as goal directed, since the inferencing is driven by the final goal.

Backtracking

Also note that while processing each subgoal within a rule's when clause:

• If pyke succeeds at proving the subgoal:
• Pyke will proceed to the next subgoal within the when clause.
• If pyke reaches the end of the when clause, the rule succeeds.
• If pyke fails at proving the subgoal:
• Pyke will back up to the prior subgoal within the when clause and try to find another proof for it. The process starts over from this prior subgoal, going forward or backing up depending on whether another proof can be found.
• If pyke reaches the beginning of the when clause, the rule fails.

Thus, execution within each rule's when clause proceeds both forwards and backwards up and down the list of subgoals, depending on whether each subgoal succeeds or fails. The process of backing up in the when clause to try alternate subproofs is called backtracking.

More:

Forward Chaining

Explanation of forward-chaining rules.

Backward Chaining

Explanation of backward-chaining rules.

Page last modified Mon, Feb 11 2008.
```