Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

[4670da]: doc / source / logic_programming / rules / forward_chaining.txt Maximize Restore History

Download this file

forward_chaining.txt    429 lines (312 with data), 15.8 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
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
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
.. $Id$
..
.. Copyright Š 2007-2008 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* and how *forward-chaining*
works.
/description
format: rest
encoding: utf8
output-encoding: utf8
include: yes
initialheaderlevel: 2
/restindex
uservalues
filedate: $Id$
/uservalues
==================
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_ are run
in the order that they appear in the `.krb file`_ for that rule base.
Overview of Forward-Chaining
=============================
To do forward-chaining, Pyke finds rules whose *if* clause matches Pyke's list
of already known facts (the *if* clause may match, or *succeed*, multiple time;
see backtracking_). Each time a rule succeeds, it *fires* this rule, which
adds the facts in the *then* clause of that rule to the list of already known
facts.
These new facts may fire other forward-chaining rules by matching their
*if* clause. This can go on to any depth. So Pyke ends up linking (or
*chaining*) the *then* clause of the first rule to the *if* clause of the next
rule.
.. note::
Forward-chaining continues until no more rules_ can be fired.
Reviewing
----------
#. Pyke starts with the *if* clause of the first rule and checks to see if it
matches the known facts.
#. If so, it proceeds to the *then* clause of that rule (*firing* the rule).
#. Which may link (or *chain*) to the *if* clause of another rule.
Since Pyke processes these rules from *if* to *then* to *if* to *then* in the
manner that we normally think of using rules, it's called *forward* chaining.
"Foreach", "Assert" Rather than "If", "Then"
============================================
Finally, since the statements within the *if* clause of the rule contain
patterns_; they may each match several facts. In this case, the rule will
succeed and be fired multiple times.
The statements in the *then* clause of the rule also contain patterns.
Each time the rule is fired, the pattern variables within the *then*
statements are bound to different values so that different facts are asserted.
To avoid confusion, Pyke uses the words **foreach** and **assert** rather
than **if** and **then** for forward-chaining rules. This is to suggest that
"for each" combination of facts matching the first list of statements,
the rule is fired to "assert" the facts in the second list of statements.
.. note::
The use of **foreach** and **assert** identifies the rule as a
forward-chaining rule.
Example
=======
This example will figure out the paternal ancestry of individuals given a list
of starting statements about who the sons of each father are. (Daughters and
mothers are omitted to keep the example brief). These facts are stored in a
`fact base`_ called ``family`` as ``son_of(son, father)``::
1 son_of(michael, bruce)
2 son_of(bruce, thomas)
3 son_of(thomas, frederik)
4 son_of(frederik, hiram)
We want to derive ``father_son`` relationships of the following form::
father_son($father, $son, $prefix)
where
:$son:
is the name of the son (e.g., michael)
:$father:
is the name of the father (e.g., bruce)
:$prefix:
is a tuple of prefixes before the 'father' and 'son' titles to
indicate the number of generations (e.g., ``()`` for direct
father_son relationships, ``(grand)``, ``(great, grand)``, etc).
This is done using three forward-chaining rules. Each rule is presented as a
separate step:
- `Step 1: Direct_father_son`_
- Step 1 demonstrates the use of `pattern matching`_ to transfer values
from one statement within the rule to another statement.
- `Step 2: Grand_father_son`_
- Step 2 demonstrates backtracking_ within the premises_ of a
forward-chaining rule. Understanding this will help you to understand
`backward-chaining rules`_.
- `Step 3: Great_grand_father_son`_
- Step 3 demonstrates a recursive forward-chaining rule.
Finally, you will be shown how to `Run the Example`_ yourself.
Step 1: Direct_father_son
=========================
First we need to establish the direct father_son relationships (those whose
``$prefix`` is ``()``)::
1 direct_father_son
2 foreach
3 family.son_of($son, $father)
4 assert
5 family.father_son($father, $son, ())
The Use of Pattern Variables
----------------------------
This demonstrates how `pattern variables`_ are used to transfer values from
one statement within a rule into another statement within the rule.
This rule has a single statement in its ``foreach`` clause (on line 3). This
statement matches all four ``son_of`` facts, so the rule succeeds four times;
but with different bindings for the ``$son`` and ``$father`` pattern variables.
This causes different facts to be asserted when the same ``assert`` clause (on
line 5) is run four times; because each time line 5 is run, the values for
``$son`` and ``$father`` are transferred from the statement on line 3 to the
statement on line 5.
When the rule fires matching line 3 to::
1 son_of(michael, bruce)
It runs line 5 to assert::
5 father_son(bruce, michael, ())
And when the rule fires a second time matching line 3 to::
2 son_of(bruce, thomas)
It runs line 5 a second time to assert::
6 father_son(thomas, bruce, ())
The rule fires twice more for the remaining ``son_of`` facts, asserting
two more ``father_son`` relationships. So this rule adds a total of four
new facts::
5 father_son(bruce, michael, ())
6 father_son(thomas, bruce, ())
7 father_son(frederik, thomas, ())
8 father_son(hiram, frederik, ())
Step 2: Grand_father_son
========================
Now we want to add grand son-father relationships. We have a new rule for
this::
6 grand_father_son
7 foreach
8 family.father_son($father, $grand_son, ())
9 family.father_son($grand_father, $father, ())
10 assert
11 family.father_son($grand_father, $grand_son, (grand))
The Use of Backtracking
-----------------------
The ``grand_father_son`` rule_ is run for all combinations of ``father_son``
facts_ that satisfy the two ``foreach`` statements_ (on lines 8 and 9) and
asserts_ a ``(grand)`` ``father_son`` statement (on line 11) for each
combination.
This rule is a good example for backtracking_ and will help later in your
understanding of backtracking with backward-chaining_. So let's follow the
backtracking in the execution of this rule.
The ``foreach`` clause has two statements (on lines 8 and 9) in it that are
both looking for ``father_son`` facts with a prefix of ``()``::
8 family.father_son($father, $grand_son, ())
9 family.father_son($grand_father, $father, ())
These will be matched to the following ``family`` facts (facts 5 through 8)::
5 father_son(bruce, michael, ())
6 father_son(thomas, bruce, ())
7 father_son(frederik, thomas, ())
8 father_son(hiram, frederik, ())
Pyke starts at the top of the list of premises and looks for a match for the
first premise (on line 8). This matches fact 5, so the first premise
succeeds, binding ``$father`` to ``bruce``::
8 family.father_son($father, $grand_son, ()) => fact 5, SUCCESS
9 family.father_son($grand_father, $father, ())
*Success* means go *down*, so Pyke goes to the next premise on line 9. This
succeeds with fact 6 (because ``$father`` is bound to ``bruce``)::
8 family.father_son($father, $grand_son, ()) => fact 5
9 family.father_son($grand_father, $father, ()) => fact 6, SUCCESS
*Success* means go *down*, but Pyke is at the end of the list of premises,
so the *rule* succeeds and Pyke fires the rule to assert::
9 father_son(thomas, michael, (grand))
Since this is a forward-chaining rule, Pyke wants to get *all* of the answers
from it that it can, so it continues as if it had a failure (i.e., as if it's
not happy with this answer).
.. note::
You'll see later that Pyke doesn't do this automatically with
backward-chaining_ rules.
So Pyke *fails* back *up* to the second premise and looks for another
``father_son`` after fact 6 with ``bruce`` as the first argument. This
fails::
8 family.father_son($father, $grand_son, ()) => fact 5
9 family.father_son($grand_father, $father, ()) => FAILS
*Fail* means go *up*, so Pyke goes up to the first premise and looks for
another ``father_son`` after fact 5, which succeeds for fact 6, binding
``$father`` to ``thomas``::
8 family.father_son($father, $grand_son, ()) => fact 6, SUCCESS
9 family.father_son($grand_father, $father, ())
*Success* means go *down*, so Pyke goes down to the second premise which
succeeds for fact 7::
8 family.father_son($father, $grand_son, ()) => fact 6
9 family.father_son($grand_father, $father, ()) => fact 7, SUCCESS
*Success* means go *down*, but Pyke is at the end of the list of premises,
so the *rule* succeeds and Pyke fires the rule to assert::
10 father_son(frederik, bruce, (grand))
Then Pyke *fails* back *up* to the second premise, and continues looking for
another match after fact 7. This fails::
8 family.father_son($father, $grand_son, ()) => fact 6
9 family.father_son($grand_father, $father, ()) => FAILS
*Fail* means go *up*, so Pyke goes back to the first premise and continues
looking for another match after fact 6. (Since fact 7 is just like the last
case, we'll skip matching fact 7 and go straight to the last fact, fact 8).
The match to fact 8 succeeds, binding ``$father`` to ``hiram``::
8 family.father_son($father, $grand_son, ()) => fact 8, SUCCESS
9 family.father_son($grand_father, $father, ())
*Success* means go *down*, so Pyke goes to the second premise and looks for a
``father_son`` for ``hiram``. This fails::
8 family.father_son($father, $grand_son, ()) => fact 8
9 family.father_son($grand_father, $father, ()) => FAILS
*Fail* means go *up*, so Pyke goes back up to the first premise and looks for
another match after fact 8. There are no more facts, so this fails::
8 family.father_son($father, $grand_son, ()) => FAILS
9 family.father_son($grand_father, $father, ())
*Fail* means go *up*, but Pyke is at the top of the list of premises,
so the *rule* fails and Pyke is done processing it.
.. important::
Note that the *last* statement in the ``foreach`` clause may *succeed*
multiple times (which fires the ``assert`` clause multiple times).
But the *first* statement in the ``foreach`` clause may only *fail* once.
When that happens, the whole rule fails and the show's over for this rule!
So running the ``grand_father_son`` rule results in addition of these three
facts::
9 father_son(thomas, michael, (grand))
10 father_son(frederik, bruce, (grand))
11 father_son(hiram, thomas, (grand)) (this is the one we skipped)
Step 3: Great_grand_father_son
==============================
Finally, we want to add great(...) grand son-father relationships. We have
a final rule for this::
12 great_grand_father_son
13 foreach
14 family.father_son($father, $gg_son, ())
15 family.father_son($gg_father, $father, ($prefix1, *$rest_prefixes))
16 assert
17 family.father_son($gg_father, $gg_son,
(great, $prefix1, *$rest_prefixes))
.. note::
Note how the $prefixes for the statement on line 15 are specified as
``($prefix1, *$rest_prefixes)``, rather than just ``$prefix``.
This is done so that it does *not* match ``()``. (But it will still match
``(grand)`` by binding ``$rest_prefixes`` to ``()``).
This is the only rule that can be recursive. As this rule asserts_ new facts_,
those facts may be used by the same rule (by matching the statement on line
15) to produce even more great, great, ... ``father_son`` relationships.
Recursive Rules
---------------
Running this rule normally will assert the following two facts::
12 father_son(frederik, michael, (great, grand))
13 father_son(hiram, bruce, (great, grand))
But, since these facts may also be used by the same rule (on line 15), Pyke
checks each one by trying to run the rule again just for that new fact.
Trying this for the first new fact: ``father_son(frederik, michael,
(great, grand))`` fails to find anything because ``michael`` is not a father.
Trying this for the second new fact: ``father_son(hiram, bruce, (great,
grand))`` results in one more new fact::
14 father_son(hiram, michael, (great, great, grand))
Now this last new fact is tried again with this rule, which fails again
because ``michael`` is not a father.
So at this point Pyke is finished with this rule. The rule ended up firing
three times, asserting::
12 father_son(frederik, michael, (great, grand))
13 father_son(hiram, bruce, (great, grand))
14 father_son(hiram, michael, (great, great, grand))
Running the Example
===========================
.. 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()
These rules could be run as follows:
>>> from pyke import knowledge_engine
>>> engine = knowledge_engine.engine(__file__)
>>> engine.assert_('family', 'son_of', ('michael', 'bruce'))
>>> engine.assert_('family', 'son_of', ('bruce', 'thomas'))
>>> engine.assert_('family', 'son_of', ('thomas', 'frederik'))
>>> engine.assert_('family', 'son_of', ('frederik', 'hiram'))
>>> engine.activate('fc_example') # This is where the rules are run!
>>> engine.get_kb('family').dump_specific_facts()
father_son('bruce', 'michael', ())
father_son('thomas', 'bruce', ())
father_son('frederik', 'thomas', ())
father_son('hiram', 'frederik', ())
father_son('thomas', 'michael', ('grand',))
father_son('frederik', 'bruce', ('grand',))
father_son('hiram', 'thomas', ('grand',))
father_son('frederik', 'michael', ('great', 'grand'))
father_son('hiram', 'bruce', ('great', 'grand'))
father_son('hiram', 'michael', ('great', 'great', 'grand'))
son_of('michael', 'bruce')
son_of('bruce', 'thomas')
son_of('thomas', 'frederik')
son_of('frederik', 'hiram')
.. _Run the Example: `Running the Example`_