[05a128]: doc / source / overview / rules / forward_chaining.txt  Maximize  Restore  History

Download this file

186 lines (158 with data), 7.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
.. $Id$
..
.. Copyright Š 2007 Bruce Frederiksen
..
.. Permission is hereby granted, free of charge, to any person obtaining a copy
.. of this software and associated documentation files (the "Software"), to deal
.. in the Software without restriction, including without limitation the rights
.. to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
.. copies of the Software, and to permit persons to whom the Software is
.. furnished to do so, subject to the following conditions:
..
.. The above copyright notice and this permission notice shall be included in
.. all copies or substantial portions of the Software.
..
.. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
.. IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
.. FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
.. AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
.. LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
.. OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
.. THE SOFTWARE.
restindex
crumb: Forward Chaining
page-description:
Explanation of forward-chaining rules.
/description
format: rest
encoding: utf8
output-encoding: utf8
include: yes
initialheaderlevel: 3
/restindex
=============================================
Forward Chaining
=============================================
Forward chaining rules_ are processed automatically as each `rule base`_ is
activated_.
When a `rule base`_ is activated_, all of its forward-chaining rules_ (and then,
its inherited_ forward-chaining rules_) are run in the order that they appear
in the `.krb file`_.
Example
==============
Consider this example::
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)
Identifying Forward-Chaining Rules
======================================
Note that the keyword ``foreach`` is used for the **if** part of each rule_
and the keyword ``assert`` is used for the **then** part of each rule_.
The use of these keywords is what identifies these rules_ as
forward-chaining rules_.
How Forward-Chaining Rules are Run
=====================================
Starting off with a set of ``family.son_of`` and ``family.daughter_of`` facts_,
these rules_ will figure out, and assert_, all ``family.child_parent``
relationships.
The rules_ are run in order. First the ``son_of`` rule_ is run. For each
match of facts_ to the pattern_ ``family.son_of($son, $father, $mother)``
it asserts_ two additional ``family.child_parent`` facts_.
Note that ``$son``, ``$father`` and ``$mother`` are `pattern variables`_.
These can match any value, but once matched they have the same value for
the rest of that rule_ invocation. Thus, the value ``$father`` is bound to
on line 3, will be the same value used on line 5 for ``$father`` in the
new fact_ to be asserted_. (But not the same value as the ``$father`` used
on lines 9 or 11, because those are in a different rule_).
After the ``son_of`` rule, the ``daughter_of`` rule is run for all
``family.daughter_of`` facts.
Then the ``grand_parent_and_child`` rule_ is run for all combinations of
``family.child_parent`` facts_ that satisfy the two patterns_ on lines 15 and
17. This rule_ asserts_ the grand-child/grand-parent relationships. You'll
notice that it uses the ``$_`` `pattern variable`_. This is called the
*anonymous* variable. It is different than other `pattern variables`_ in that
each use of ``$_`` can match a different value.
Finally, the ``great_grand_parent_and_child`` rule is run. As this rule
asserts_ new facts_, those facts_ may be used by the same rule_ to produce
even more great, great... ``family.child_parent`` relationships.
Forward-Chaining Defined
============================
Thus, even though pyke runs the rules_ in order, it will go back and rerun
prior rules_ if a new fact_ is asserted_ that matches any of the prior
`rule's`_ premises in its ``foreach`` clause. This forms an implicit linkage
from one `rule's`_ **then** (``assert``) clause
to another `rule's`_ **if** (``foreach``) clause.
This is what the term
*forward-chaining* refers to, since the linkage proceeds in a logically
forward direction. This is also referred to as *data driven*, since the
initial data (facts_) drive the inferencing.
The forward-chaining continues until no more rules_ can be fired.
Running the Example
===========================
These rules could be run as follows:
>>> import pyke
>>> pyke.load('examples')
>>> pyke.assert_('family', 'son_of', ('michael', 'bruce', 'marilyn'))
>>> pyke.assert_('family', 'son_of', ('bruce', 'thomas', 'norma'))
>>> pyke.assert_('family', 'daughter_of', ('norma', 'allen', 'ismay'))
>>> pyke.activate('fc_example') # This is where the rules are run!
>>> pyke.get_kb('family').dump_specific_facts()
child_parent('michael', 'norma', ('grand',), 'son', 'mother')
child_parent('michael', 'marilyn', (), 'son', 'mother')
child_parent('norma', 'allen', (), 'daughter', 'father')
child_parent('michael', 'thomas', ('grand',), 'son', 'father')
child_parent('michael', 'bruce', (), 'son', 'father')
child_parent('bruce', 'ismay', ('grand',), 'son', 'mother')
child_parent('michael', 'ismay', ('great', 'grand'), 'son', 'mother')
child_parent('bruce', 'norma', (), 'son', 'mother')
child_parent('michael', 'allen', ('great', 'grand'), 'son', 'father')
child_parent('bruce', 'allen', ('grand',), 'son', 'father')
child_parent('bruce', 'thomas', (), 'son', 'father')
child_parent('norma', 'ismay', (), 'daughter', 'mother')
daughter_of('norma', 'allen', 'ismay')
son_of('michael', 'bruce', 'marilyn')
son_of('bruce', 'thomas', 'norma')
.. _activated: ../../using_pyke.html#setting-up-each-case
.. _assert: activated_
.. _asserted: assert_
.. _asserts: assert_
.. _fact: ../knowledge_bases/fact_bases.html#facts
.. _facts: fact_
.. _inherited: ../knowledge_bases/rule_bases.html#rule-base-inheritance
.. _.krb file: ../../krb_syntax/index.html
.. _pattern variable: patterns_
.. _pattern variables: `pattern variable`_
.. _pattern: ../../krb_syntax/pattern.html
.. _patterns: pattern_
.. _rule: index.html
.. _rules: rule_
.. _rule's: rule_
.. _rule base: ../knowledge_bases/rule_bases.html

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks