.. $Id: forward_chaining.txt 72 2008-03-06 03:03:50Z mtnyogi $
.. 
.. 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:

    >>> from pyke import knowledge_engine
    >>> engine = knowledge_engine.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('fc_example')     # This is where the rules are run!
    >>> 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')

.. _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: ../../krb_syntax/pattern.html#pattern-variable
.. _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
