Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

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

Download this file

forward_chaining.html    232 lines (217 with data), 14.7 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
<!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>Forward 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">
&nbsp;
</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>&gt;</li>
<li><a href="../index.html">Overview</a></li>
<li>&gt;</li>
<li><a href="index.html">Rules</a></li>
<li>&gt;</li>
<li>Forward 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="title-nav"><a href="../index.html">Overview</a></div><div class="nav-branch">
<div class="normal-nav"><a href="../knowledge_bases/index.html">Knowledge Bases</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="../../installing_pyke.html">Installing Pyke</a></div>
<div class="normal-nav"><a href="../../using_pyke.html">Using Pyke</a></div>
<div class="normal-nav"><a href="../../krb_syntax/index.html">KRB Syntax</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"><img src="http://sflogo.sourceforge.net/sflogo.php?group_id=207724&amp;type=3" width="125" height="37" border="0" alt="SourceForge.net Logo" /></a> -->
<a href="http://sourceforge.net"><img src="http://sflogo.sourceforge.net/sflogo.php?group_id=207724&amp;type=4" width="125" height="37" border="0" alt="SourceForge.net Logo" /></a>
</div>
</td>
<td id="main-td">
<div id="main">
<a name="startcontent" id="startcontent"></a>
<div class="document" id="forward-chaining">
<h1 class="title">Forward Chaining</h1>
<p>Forward chaining <a class="reference" href="index.html">rules</a> are processed automatically as each <a class="reference" href="../knowledge_bases/rule_bases.html">rule base</a> is
<a class="reference" href="../../using_pyke.html#setting-up-each-case">activated</a>.</p>
<p>When a <a class="reference" href="../knowledge_bases/rule_bases.html">rule base</a> is <a class="reference" href="../../using_pyke.html#setting-up-each-case">activated</a>, all of its forward-chaining <a class="reference" href="index.html">rules</a> (and then,
its <a class="reference" href="../knowledge_bases/rule_bases.html#rule-base-inheritance">inherited</a> forward-chaining <a class="reference" href="index.html">rules</a>) are run in the order that they appear
in the <a class="reference" href="../../krb_syntax/index.html">.krb file</a>.</p>
<div class="section">
<h3><a id="example" name="example">Example</a></h3>
<p>Consider this example:</p>
<pre class="literal-block">
1 son_of:
2 foreach
3 family.son_of($son, $father, $mother)
4 assert
5 family.child_parent($son, $father, (), son, father)
6 family.child_parent($son, $mother, (), son, mother)
7 daughter_of:
8 foreach
9 family.daughter_of($daughter, $father, $mother)
10 assert
11 family.child_parent($daughter, $father, (), daughter, father)
12 family.child_parent($daughter, $mother, (), daughter, mother)
13 grand_parent_and_child:
14 foreach
15 family.child_parent($grand_child, $parent, (),
16 $grand_child_type, $_)
17 family.child_parent($parent, $grand_parent, (),
18 $_, $grand_parent_type)
19 assert
20 family.child_parent($grand_child, $grand_parent, (grand),
21 $grand_child_type, $grand_parent_type)
22 great_grand_parent_and_child:
23 foreach
24 family.child_parent($gg_child, $parent, (), $gg_child_type, $_)
25 family.child_parent($parent, $gg_parent,
26 ($prefix1, *$rest_prefixes),
27 $_, $gg_parent_type)
28 assert
29 family.child_parent($gg_child, $gg_parent,
30 (great, $prefix1, *$rest_prefixes),
31 $gg_child_type, $gg_parent_type)
</pre>
</div>
<div class="section">
<h3><a id="identifying-forward-chaining-rules" name="identifying-forward-chaining-rules">Identifying Forward-Chaining Rules</a></h3>
<p>Note that the keyword <tt class="docutils literal"><span class="pre">foreach</span></tt> is used for the <strong>if</strong> part of each <a class="reference" href="index.html">rule</a>
and the keyword <tt class="docutils literal"><span class="pre">assert</span></tt> is used for the <strong>then</strong> part of each <a class="reference" href="index.html">rule</a>.
The use of these keywords is what identifies these <a class="reference" href="index.html">rules</a> as
forward-chaining <a class="reference" href="index.html">rules</a>.</p>
</div>
<div class="section">
<h3><a id="how-forward-chaining-rules-are-run" name="how-forward-chaining-rules-are-run">How Forward-Chaining Rules are Run</a></h3>
<p>Starting off with a set of <tt class="docutils literal"><span class="pre">family.son_of</span></tt> and <tt class="docutils literal"><span class="pre">family.daughter_of</span></tt> <a class="reference" href="../knowledge_bases/fact_bases.html#facts">facts</a>,
these <a class="reference" href="index.html">rules</a> will figure out, and <a class="reference" href="../../using_pyke.html#setting-up-each-case">assert</a>, all <tt class="docutils literal"><span class="pre">family.child_parent</span></tt>
relationships.</p>
<p>The <a class="reference" href="index.html">rules</a> are run in order. First the <tt class="docutils literal"><span class="pre">son_of</span></tt> <a class="reference" href="index.html">rule</a> is run. For each
match of <a class="reference" href="../knowledge_bases/fact_bases.html#facts">facts</a> to the <a class="reference" href="../../krb_syntax/pattern.html">pattern</a> <tt class="docutils literal"><span class="pre">family.son_of($son,</span> <span class="pre">$father,</span> <span class="pre">$mother)</span></tt>
it <a class="reference" href="../../using_pyke.html#setting-up-each-case">asserts</a> two additional <tt class="docutils literal"><span class="pre">family.child_parent</span></tt> <a class="reference" href="../knowledge_bases/fact_bases.html#facts">facts</a>.</p>
<p>Note that <tt class="docutils literal"><span class="pre">$son</span></tt>, <tt class="docutils literal"><span class="pre">$father</span></tt> and <tt class="docutils literal"><span class="pre">$mother</span></tt> are <a class="reference" href="../../krb_syntax/pattern.html#pattern-variable">pattern variables</a>.
These can match any value, but once matched they have the same value for
the rest of that <a class="reference" href="index.html">rule</a> invocation. Thus, the value <tt class="docutils literal"><span class="pre">$father</span></tt> is bound to
on line 3, will be the same value used on line 5 for <tt class="docutils literal"><span class="pre">$father</span></tt> in the
new <a class="reference" href="../knowledge_bases/fact_bases.html#facts">fact</a> to be <a class="reference" href="../../using_pyke.html#setting-up-each-case">asserted</a>. (But not the same value as the <tt class="docutils literal"><span class="pre">$father</span></tt> used
on lines 9 or 11, because those are in a different <a class="reference" href="index.html">rule</a>).</p>
<p>After the <tt class="docutils literal"><span class="pre">son_of</span></tt> rule, the <tt class="docutils literal"><span class="pre">daughter_of</span></tt> rule is run for all
<tt class="docutils literal"><span class="pre">family.daughter_of</span></tt> facts.</p>
<p>Then the <tt class="docutils literal"><span class="pre">grand_parent_and_child</span></tt> <a class="reference" href="index.html">rule</a> is run for all combinations of
<tt class="docutils literal"><span class="pre">family.child_parent</span></tt> <a class="reference" href="../knowledge_bases/fact_bases.html#facts">facts</a> that satisfy the two <a class="reference" href="../../krb_syntax/pattern.html">patterns</a> on lines 15 and
17. This <a class="reference" href="index.html">rule</a> <a class="reference" href="../../using_pyke.html#setting-up-each-case">asserts</a> the grand-child/grand-parent relationships. You'll
notice that it uses the <tt class="docutils literal"><span class="pre">$_</span></tt> <a class="reference" href="../../krb_syntax/pattern.html#pattern-variable">pattern variable</a>. This is called the
<em>anonymous</em> variable. It is different than other <a class="reference" href="../../krb_syntax/pattern.html#pattern-variable">pattern variables</a> in that
each use of <tt class="docutils literal"><span class="pre">$_</span></tt> can match a different value.</p>
<p>Finally, the <tt class="docutils literal"><span class="pre">great_grand_parent_and_child</span></tt> rule is run. As this rule
<a class="reference" href="../../using_pyke.html#setting-up-each-case">asserts</a> new <a class="reference" href="../knowledge_bases/fact_bases.html#facts">facts</a>, those <a class="reference" href="../knowledge_bases/fact_bases.html#facts">facts</a> may be used by the same <a class="reference" href="index.html">rule</a> to produce
even more great, great... <tt class="docutils literal"><span class="pre">family.child_parent</span></tt> relationships.</p>
</div>
<div class="section">
<h3><a id="forward-chaining-defined" name="forward-chaining-defined">Forward-Chaining Defined</a></h3>
<p>Thus, even though pyke runs the <a class="reference" href="index.html">rules</a> in order, it will go back and rerun
prior <a class="reference" href="index.html">rules</a> if a new <a class="reference" href="../knowledge_bases/fact_bases.html#facts">fact</a> is <a class="reference" href="../../using_pyke.html#setting-up-each-case">asserted</a> that matches any of the prior
<a class="reference" href="index.html">rule's</a> premises in its <tt class="docutils literal"><span class="pre">foreach</span></tt> clause. This forms an implicit linkage
from one <a class="reference" href="index.html">rule's</a> <strong>then</strong> (<tt class="docutils literal"><span class="pre">assert</span></tt>) clause
to another <a class="reference" href="index.html">rule's</a> <strong>if</strong> (<tt class="docutils literal"><span class="pre">foreach</span></tt>) clause.</p>
<p>This is what the term
<em>forward-chaining</em> refers to, since the linkage proceeds in a logically
forward direction. This is also referred to as <em>data driven</em>, since the
initial data (<a class="reference" href="../knowledge_bases/fact_bases.html#facts">facts</a>) drive the inferencing.</p>
<p>The forward-chaining continues until no more <a class="reference" href="index.html">rules</a> can be fired.</p>
</div>
<div class="section">
<h3><a id="running-the-example" name="running-the-example">Running the Example</a></h3>
<p>These rules could be run as follows:</p>
<blockquote>
<pre class="doctest-block">
&gt;&gt;&gt; import pyke
&gt;&gt;&gt; engine = pyke.engine('examples')
&gt;&gt;&gt; engine.assert_('family', 'son_of', ('michael', 'bruce', 'marilyn'))
&gt;&gt;&gt; engine.assert_('family', 'son_of', ('bruce', 'thomas', 'norma'))
&gt;&gt;&gt; engine.assert_('family', 'daughter_of', ('norma', 'allen', 'ismay'))
&gt;&gt;&gt; engine.activate('fc_example') # This is where the rules are run!
&gt;&gt;&gt; engine.get_kb('family').dump_specific_facts()
child_parent('michael', 'bruce', (), 'son', 'father')
child_parent('michael', 'marilyn', (), 'son', 'mother')
child_parent('bruce', 'thomas', (), 'son', 'father')
child_parent('bruce', 'norma', (), 'son', 'mother')
child_parent('norma', 'allen', (), 'daughter', 'father')
child_parent('norma', 'ismay', (), 'daughter', 'mother')
child_parent('michael', 'thomas', ('grand',), 'son', 'father')
child_parent('michael', 'norma', ('grand',), 'son', 'mother')
child_parent('bruce', 'allen', ('grand',), 'son', 'father')
child_parent('bruce', 'ismay', ('grand',), 'son', 'mother')
child_parent('michael', 'allen', ('great', 'grand'), 'son', 'father')
child_parent('michael', 'ismay', ('great', 'grand'), 'son', 'mother')
daughter_of('norma', 'allen', 'ismay')
son_of('michael', 'bruce', 'marilyn')
son_of('bruce', 'thomas', 'norma')
</pre>
</blockquote>
</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 forward-chaining rules.</p>
</div>
<div class="right-item"><a href="backward_chaining.html">Backward Chaining</a><p>Explanation of backward-chaining rules.</p>
</div>
</div>
</td>
</tr>
</tbody>
<tfoot id="foot">
<tr id="foot2">
<td id="copyright" colspan="3">
Copyright &copy; 2007 Bruce Frederiksen
</td>
</tr>
</tfoot>
</table>
<div id="last-modified">
Page last modified Tue, Feb 12 2008.
</div>
</body>
</html>