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
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<title>Backward Chaining</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<link rel="stylesheet" href="../../stylesheets/pyke.css" type="text/css" />
</head>
<body>
<table id="page-table">
<thead class="head">
<tr id="header1"><th id="header" colspan="3">
</th></tr>
<tr id="header2">
<th id="crumb-left"></th>
<th id="crumb-line">
<div id="nav">
<ul>
<li><a href="../../index.html">Home</a></li>
<li>></li>
<li><a href="../index.html">Logic Programming</a></li>
<li>></li>
<li><a href="index.html">Rules</a></li>
<li>></li>
<li>Backward Chaining</li>
</ul>
</div>
</th>
<th id="crumb-right"></th>
</tr>
</thead>
<tbody id="body">
<tr id="body-tr">
<td id="left-nav">
<div id="left-nav-div">
<div class="title-nav"><a href="../../index.html">Home</a></div><div class="nav-branch">
<div class="normal-nav"><a href="../../about_pyke/index.html">About Pyke</a></div>
<div class="title-nav"><a href="../index.html">Logic Programming</a></div><div class="nav-branch">
<div class="normal-nav"><a href="../statements.html">Statements</a></div>
<div class="normal-nav"><a href="../pattern_matching/index.html">Pattern Matching</a></div>
<div class="title-nav"><a href="index.html">Rules</a></div><div class="nav-branch">
<div class="normal-nav"><a href="forward_chaining.html">Forward Chaining</a></div>
<div class="normal-nav"><a href="backward_chaining.html">Backward Chaining</a></div>
</div>
<div class="normal-nav"><a href="../plans.html">Plans</a></div>
</div>
<div class="normal-nav"><a href="../../knowledge_bases/index.html">Knowledge Bases</a></div>
<div class="normal-nav"><a href="../../pyke_syntax/index.html">Pyke Syntax</a></div>
<div class="normal-nav"><a href="../../using_pyke/index.html">Using Pyke</a></div>
<div class="normal-nav"><a href="../../examples.html">Examples</a></div>
<div class="normal-nav"><a href="../../PyCon2008-paper.html">PyCon 2008 Paper</a></div>
</div>
</div>
<div id="icons">
<div id="project-page">
<a href="http://sourceforge.net/projects/pyke/">Pyke Project Page</a>
</div>
Please Make a Donation:<br />
<a href="http://sourceforge.net/donate/index.php?group_id=207724">
<img src="http://images.sourceforge.net/images/project-support.jpg"
width="88" height="32" border="0"
alt="Support This Project" /> </a> <br /><br />
Hosted by: <br />
<a href="http://sourceforge.net/projects/pyke">
<img src="http://sflogo.sourceforge.net/sflogo.php?group_id=207724&type=14"
width="150" height="40"
alt="Get Python Knowledge Engine (PyKE) at SourceForge.net. Fast, secure and Free Open Source software downloads" /></a>
</div>
</td>
<td id="main-td">
<div id="main">
<a name="startcontent" id="startcontent"></a>
<div class="document" id="backward-chaining">
<h1 class="title">Backward Chaining</h1>
<p>Backward chaining <a class="reference external" href="index.html">rules</a> are processed when your program asks Pyke a <a class="reference external" href="../../knowledge_bases/question_bases.html">question</a>
(i.e., asks Pyke to <a class="reference external" href="../../using_pyke/proving_goals.html">prove</a> a specific <em>goal</em>). Pyke will only use <a class="reference external" href="../../using_pyke/index.html#getting-started">activated</a>
<a class="reference external" href="../../knowledge_bases/rule_bases.html">rule bases</a> to do the proof.</p>
<div class="section" id="overview-of-backward-chaining">
<h2>Overview of "Backward-Chaining"</h2>
<p>To do backward-chaining, Pyke finds rules whose <em>then</em> part matches the <em>goal</em>
(i.e., the question). Once it finds such a rule, it tries to (recursively)
prove all of the subgoals in the <em>if</em> part of that rule. Some of these
subgoals are matched against facts, and others are subgoals for other
backward-chaining rules. If all of the subgoals can be proven, the rule
succeeds and the original goal is proven. Otherwise, the rule fails, and Pyke
tries to find another rule whose <em>then</em> part matches the goal, and so on.</p>
<p>So Pyke ends up linking (or <em>chaining</em>) the <em>if</em> part of the first rule to the
<em>then</em> part of the next rule.</p>
<p>Reviewing:</p>
<ol class="arabic simple">
<li>Pyke starts by finding a rule whose <em>then</em> part matches the goal.</li>
<li>Pyke then proceeds to process the <em>if</em> part of that rule.</li>
<li>Which may link (or chain) to the <em>then</em> part of another rule.</li>
</ol>
<p>Since Pyke processes these rules from <em>then</em> to <em>if</em> to <em>then</em> to <em>if</em> in the
reverse manner that we normally think of using rules, it's called <em>backward</em>
chaining.</p>
<p>To make this more clear, Pyke has you write your backward-chaining rules
upside down by writing the <em>then</em> part first (since that's how it is
processed).</p>
</div>
<div class="section" id="use-when-rather-than-then-if">
<h2>"Use", "When" Rather than "Then", "If"</h2>
<p>But <em>then-if</em> rules sound confusing, so Pyke uses the words <strong>use</strong> and
<strong>when</strong> rather than <strong>then</strong> and <strong>if</strong>. You can then read the rule as "use"
this statement "when" these other statements can be proven.</p>
<div class="note">
<p class="first admonition-title">Note</p>
<p class="last">Unlike the <em>assert</em> clause in <a class="reference external" href="forward_chaining.html">forward-chaining</a> rules, Pyke only allows
one statement in the <em>use</em> clause.</p>
</div>
</div>
<div class="section" id="example">
<h2>Example</h2>
<p>Consider this example:</p>
<pre class="literal-block">
1 direct_father_son
2 use father_son($father, $son, ())
3 when
4 family2.son_of($son, $father)
5 grand_father_son
6 use father_son($grand_father, $grand_son, (grand))
7 when
8 father_son($father, $grand_son, ())
9 father_son($grand_father, $father, ())
10 great_grand_father_son
11 use father_son($gg_father, $gg_son, (great, $prefix1, *$rest_prefixes))
12 when
13 father_son($father, $gg_son, ())
14 father_son($gg_father, $father, ($prefix1, *$rest_prefixes))
15 brothers
16 use brothers($brother1, $brother2)
17 when
18 father_son($father, $brother1, ())
19 father_son($father, $brother2, ())
20 check $brother1 != $brother2
21 uncle_nephew
22 use uncle_nephew($uncle, $nephew, $prefix)
23 when
24 brothers($uncle, $father)
25 father_son($father, $nephew, $prefix1)
26 $prefix = ('great',) * len($prefix1)
27 cousins
28 use cousins($cousin1, $cousin2, $distance, $removed)
29 when
30 uncle_nephew($uncle, $cousin1, $prefix1)
31 father_son($uncle, $cousin2, $prefix2)
32 $distance = min(len($prefixes1), len($prefixes2)) + 1
33 $removed = abs(len($prefixes1) - len($prefixes2))
</pre>
<div class="note">
<p class="first admonition-title">Note</p>
<p class="last">These <a class="reference external" href="index.html">rules</a> draw the same conclusions as the <a class="reference external" href="forward_chaining.html">forward-chaining</a> <a class="reference external" href="forward_chaining.html#example">example</a>,
with the addition of the <em>brothers</em>, <em>uncle_nephew</em> and <em>cousins</em> rules.</p>
</div>
<p>We can draw something similar to a function call graph with these rules:</p>
<div class="figure align-center">
<img alt="../../images/bc_rules.png" src="../../images/bc_rules.png" style="width: 509.0px; height: 583.0px;" />
<p class="caption">Example Rules</p>
</div>
<p>These <a class="reference external" href="index.html">rules</a> are not used until you ask Pyke to <a class="reference external" href="../../using_pyke/proving_goals.html">prove</a> a goal.</p>
<p>The easiest way to do this is with <em>some_engine.prove_1_goal</em> or
<em>some_engine.prove_goal</em>. <a class="reference external" href="../../using_pyke/proving_goals.html">Prove_1_goal</a> only returns the first proof found
and then stops (or raises <tt class="docutils literal">pyke.knowledge_engine.CanNotProve</tt>). <a class="reference external" href="../../using_pyke/proving_goals.html">Prove_goal</a>
returns a context manager for a generator that generates all possible proofs
(which, in some cases, might be infinite).</p>
<p>Both functions return the <a class="reference external" href="../pattern_matching/pattern_variables.html">pattern variable</a> variable bindings, along with
the <a class="reference external" href="../plans.html">plan</a>.</p>
</div>
<div class="section" id="backtracking-with-backward-chaining-rules">
<h2>Backtracking with Backward-Chaining Rules</h2>
<p>For this example, these are the starting set of <tt class="docutils literal">family2</tt> facts:</p>
<pre class="literal-block">
1 son_of(tim, thomas)
2 son_of(fred, thomas)
3 son_of(bruce, thomas)
4 son_of(david, bruce)
</pre>
<p>And we want to know who fred's nephews are. So we'd ask <tt class="docutils literal">uncle_nephew(fred,
$nephew, $prefix)</tt>.</p>
<p>Here are the steps (in parenthesis) in the inferencing up until the first
failure is encountered (with the line number from the example preceding each
line):</p>
<pre class="literal-block">
(1) 22 use uncle_nephew(fred, $nephew, $prefix)
24 brothers(fred, $father)
(2) 16 use brothers(fred, $brother2)
18 father_son($father, fred, ())
(3) 2 use father_son($father, fred, ())
4 family2.son_of(fred, $father)
matches fact 2: son_of(fred, thomas)
19 father_son(thomas, $brother2, ())
(4) 2 use father_son(thomas, $son, ())
4 family2.son_of($son, thomas)
matches fact 1: son_of(tim, thomas)
20 check fred != tim
25 father_son(tim, $nephew, $prefix1)
(5.1) 2 use father_son(tim, $son, ())
4 family2.son_of($son, tim) => FAILS
(5.2) 6 use father_son(tim, $grand_son, (grand))
8 father_son(tim, $grand_son, ())
2 use father_son(tim, $son, ())
4 family2.son_of($son, tim) => FAILS
(5.3) 11 use father_son(tim, $gg_son, (great, $prefix1, *$rest_prefixes))
13 father_son(tim, $gg_son, ())
2 use father_son(tim, $son, ())
4 family2.son_of($son, tim) => FAILS
</pre>
<p>Each rule invocation is numbered (in parenthesis) as a step number. Step 5
has tried 3 different rules and they have all failed (5.1, 5.2 and 5.3).</p>
<p>If you think of the rules as functions, the situation now looks like this
(the step numbers that succeeded circled in black, and steps that failed
circled in red):</p>
<div class="figure align-center">
<img alt="../../images/bc_backtracking.png" src="../../images/bc_backtracking.png" style="width: 590.0px; height: 465.0px;" />
<p class="caption">We Need to Backtrack!</p>
</div>
<p>At this point, Pyke has hit a dead end and must backtrack. The way that
backtracking proceeds is to go back up the list of steps executed, combining
the steps from all rules into one list. Thus, when step 5 fails, Pyke backs
up to step 4 and tries to find another solution to that step.</p>
<p>If another solution is found, Pyke proceeds forward again from that point. If
no other solutions are found, Pyke backs up another step.</p>
<p>When Pyke goes back to step 4, the next solution binds <tt class="docutils literal">$son</tt> to <tt class="docutils literal">fred</tt>.
This fails the subsequent check in the <tt class="docutils literal">brothers</tt> rule:</p>
<pre class="literal-block">
20 check $brother1 != $brother2
</pre>
<p>And so Pyke goes back to step 4 once again. The next solution binds <tt class="docutils literal">$son</tt>
to <tt class="docutils literal">bruce</tt>. This succeeds for <tt class="docutils literal">brother</tt> and is passed down to
<tt class="docutils literal">father_son</tt> which returns <tt class="docutils literal">david</tt> as <tt class="docutils literal">fred's</tt> nephew.</p>
<p>Further backtracking reveals no other solutions.</p>
<div class="section" id="backtracking-summary">
<h3>Backtracking Summary</h3>
<p>Thus we see:</p>
<ol class="arabic simple">
<li>The <a class="reference external" href="index.html#backtracking">backtracking</a> algorithm: "<strong>fail</strong> goes <em>up</em> (or <em>back</em>) while
<strong>success</strong> goes <em>down</em> (or <em>forward</em>)" is not limited to the steps within a
<em>single</em> rule's <tt class="docutils literal">when</tt> clause; but includes the <em>entire</em> chain of
inferencing from the very start of trying to prove the top level goal.</li>
<li>This execution model is not available within traditional programming
languages like Python.</li>
<li>The ability to go back to <em>any</em> point in the computation to try an
alternate solution is where backward-chaining systems get their power!</li>
</ol>
<!-- This code is hidden. It will add '' to sys.path, change to the doc.examples
directory and store the directory path in __file__ for the code section
following:
>>> import sys
>>> if '' not in sys.path: sys.path.insert(0, '')
>>> import os
>>> os.chdir("../../../examples")
>>> __file__ = os.getcwd() -->
</div>
</div>
<div class="section" id="running-the-example">
<h2>Running the Example</h2>
<blockquote>
<pre class="doctest-block">
>>> from pyke import knowledge_engine
>>> engine = knowledge_engine.engine(__file__)
>>> engine.activate('bc_related')
</pre>
</blockquote>
<p>Nothing happens this time when we activate the rule base, because there are no
forward-chaining rules here.</p>
<p>We want to ask the question: "Who are Fred's nephews?". This translates
into the Pyke statement: <tt class="docutils literal">bc_related.uncle_nephew(fred, $v1, $v2)</tt>.</p>
<div class="note">
<p class="first admonition-title">Note</p>
<p class="last">Note that we're using the name of the rule base, <tt class="docutils literal">bc_related</tt> rather than
the fact base, <tt class="docutils literal">family2</tt> here; because we expect this answer to come from
the <tt class="docutils literal">bc_related</tt> rule base.</p>
</div>
<p>This is 'bc_related', 'uncle_nephew', with ('fred',) followed by 2 pattern
variables as arguments:</p>
<blockquote>
<pre class="doctest-block">
>>> from __future__ import with_statement
>>> with engine.prove_goal('bc_related.uncle_nephew(fred, $nephew, $distance)') as gen:
... for vars, no_plan in gen:
... print vars['nephew'], vars['distance']
david ()
</pre>
</blockquote>
<!-- ADD_LINKS MARKER -->
</div>
</div>
<!-- <div id="return-to-top">
<a href="#">Return to Top</a>
</div>
-->
</div>
</td>
<td id="right-nav">
<div id="right-nav-div">
<h3>More:</h3>
<div class="right-item"><a href="forward_chaining.html">Forward Chaining</a><p>Explanation of <em>forward-chaining rules</em> and how <em>forward-chaining</em>
works.</p>
</div>
<div class="right-item"><a href="backward_chaining.html">Backward Chaining</a><p>Explanation of <em>backward-chaining</em> rules, including how
<em>backward-chaining</em> and <em>backtracking</em> works.</p>
</div>
</div>
</td>
</tr>
</tbody>
<tfoot id="foot">
<tr id="foot2">
<td id="copyright" colspan="3">
Copyright © 2007-2009 Bruce Frederiksen
</td>
</tr>
</tfoot>
</table>
<div id="last-modified">
Page last modified
Mon, Mar 08 2010.
</div>
<script type="text/javascript">
var gaJsHost = (("https:" == document.location.protocol) ?
"https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost +
"google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript">
try {
var pageTracker = _gat._getTracker("UA-6310805-1");
pageTracker._trackPageview();
} catch(err) {}
</script>
</body>
</html>
|
