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

Diff of /doc/source/logic_programming/rules/backward_chaining.txt [5cabfd] .. [4dca5a] Maximize Restore

  Switch to unified view

a/doc/source/logic_programming/rules/backward_chaining.txt b/doc/source/logic_programming/rules/backward_chaining.txt
...
...
91
Consider this example::
91
Consider this example::
92
92
93
     1  direct_father_son
93
     1  direct_father_son
94
     2      use father_son($father, $son, ())
94
     2      use father_son($father, $son, ())
95
     3      when
95
     3      when
96
     4          family.son_of($son, $father)
96
     4          family2.son_of($son, $father)
97
        
97
        
98
     5  grand_father_son
98
     5  grand_father_son
99
     6      use father_son($grand_father, $grand_son, (grand))
99
     6      use father_son($grand_father, $grand_son, (grand))
100
     7      when
100
     7      when
101
     8          father_son($father, $grand_son, ())
101
     8          father_son($father, $grand_son, ())
...
...
143
143
144
   Example Rules
144
   Example Rules
145
145
146
These rules_ are not used until you ask Pyke to prove_ a goal.
146
These rules_ are not used until you ask Pyke to prove_ a goal.
147
147
148
The easiest way to do this is with *some_engine.prove_1* or
148
The easiest way to do this is with *some_engine.prove_1_goal* or
149
*some_engine.prove_n*.  Prove_1_ only returns the first proof found and
149
*some_engine.prove_goal*.  Prove_1_goal_ only returns the first proof found
150
then stops (or raises ``pyke.knowledge_engine.CanNotProve``).  Prove_n_
150
and then stops (or raises ``pyke.knowledge_engine.CanNotProve``).  Prove_goal_
151
returns a context manager for a generator that generates all possible proofs
151
returns a context manager for a generator that generates all possible proofs
152
(which, in some cases, might be infinite).  In both cases, you pass a tuple
152
(which, in some cases, might be infinite).
153
of data arguments and the number of variable arguments as the last two
154
parameters.  The total number of arguments for the goal is the sum of the
155
length of the data arguments that you pass plus the number of variable
156
arguments that you specify.
157
153
158
Both functions return the variable bindings for the number of variable
154
Both functions return the `pattern variable`_ variable bindings, along with
159
arguments you specified as a tuple, along with the plan_.
155
the plan_.
160
156
161
Backtracking with Backward-Chaining Rules
157
Backtracking with Backward-Chaining Rules
162
=========================================
158
=========================================
163
159
164
For this example, these are the starting set of ``family`` facts::
160
For this example, these are the starting set of ``family2`` facts::
165
161
166
     1  son_of(tim, thomas)
162
     1  son_of(tim, thomas)
167
     2  son_of(fred, thomas)
163
     2  son_of(fred, thomas)
168
     3  son_of(bruce, thomas)
164
     3  son_of(bruce, thomas)
169
     4  son_of(michael, bruce)
165
     4  son_of(david, bruce)
170
166
171
And we want to know who fred's nephews are.  So we'd ask ``uncle_nephew(fred,
167
And we want to know who fred's nephews are.  So we'd ask ``uncle_nephew(fred,
172
$nephew, $prefix)``.
168
$nephew, $prefix)``.
173
169
174
Here are the steps (in parenthesis) in the inferencing up until the first
170
Here are the steps (in parenthesis) in the inferencing up until the first
175
failure is encountered (with the line number from the example preceding each
171
failure is encountered (with the line number from the example preceding each
176
line)::
172
line)::
177
173
178
    (1)   22  use uncle_nephew(fred, $nephew, $prefix)
174
    (1)   22  use uncle_nephew(fred, $nephew, $prefix)
179
              25  brothers(fred, $father)
175
              24  brothers(fred, $father)
180
    (2)           25  use brothers(fred, $brother2)
176
    (2)           16  use brothers(fred, $brother2)
181
                      18  father_son($father, fred, ())
177
                      18  father_son($father, fred, ())
182
    (3)                   2  use father_son($father, fred, ())
178
    (3)                   2  use father_son($father, fred, ())
183
                              4  family.son_of(fred, $father)
179
                              4  family2.son_of(fred, $father)
180
                                   matches fact 2: son_of(fred, thomas)
184
                      19  father_son(thomas, $brother2, ())
181
                      19  father_son(thomas, $brother2, ())
185
    (4)                   2  use father_son(thomas, $son, ())
182
    (4)                   2  use father_son(thomas, $son, ())
186
                              4  family.son_of($son, thomas)
183
                              4  family2.son_of($son, thomas)
184
                                   matches fact 1: son_of(tim, thomas)
187
                      20  check fred != tim
185
                      20  check fred != tim
188
              24  father_son(tim, $nephew, $prefix1)
186
              25  father_son(tim, $nephew, $prefix1)
189
    (5.1)         2  use father_son(tim, $son, ())
187
    (5.1)         2  use father_son(tim, $son, ())
190
                      4  family.son_of($son, tim)                                => FAILS
188
                      4  family2.son_of($son, tim)                               => FAILS
191
    (5.2)         6  use father_son(tim, $grand_son, (grand))
189
    (5.2)         6  use father_son(tim, $grand_son, (grand))
192
                      8  father_son(tim, $grand_son, ())
190
                      8  father_son(tim, $grand_son, ())
193
                          2  use father_son(tim, $son, ())
191
                          2  use father_son(tim, $son, ())
194
                              4  family.son_of($son, tim)                        => FAILS
192
                              4  family2.son_of($son, tim)                       => FAILS
195
    (5.3)         11 use father_son(tim, $gg_son, (great, $prefix1, *$rest_prefixes))
193
    (5.3)         11 use father_son(tim, $gg_son, (great, $prefix1, *$rest_prefixes))
196
                      13 father_son(tim, $gg_son, ())
194
                      13 father_son(tim, $gg_son, ())
197
                          2  use father_son(tim, $son, ())
195
                          2  use father_son(tim, $son, ())
198
                              4  family.son_of($son, tim)                        => FAILS
196
                              4  family2.son_of($son, tim)                       => FAILS
199
197
200
Each rule invocation is numbered (in parenthesis) as a step number.  Step 5
198
Each rule invocation is numbered (in parenthesis) as a step number.  Step 5
201
has tried 3 different rules and they have all failed (5.1, 5.2 and 5.3).
199
has tried 3 different rules and they have all failed (5.1, 5.2 and 5.3).
202
200
203
If you think of the rules as functions, the situation now looks like this
201
If you think of the rules as functions, the situation now looks like this
...
...
225
223
226
    20          check $brother1 != $brother2
224
    20          check $brother1 != $brother2
227
225
228
And so Pyke goes back to step 4 once again.  The next solution binds ``$son``
226
And so Pyke goes back to step 4 once again.  The next solution binds ``$son``
229
to ``bruce``.  This succeeds for ``brother`` and is passed down to
227
to ``bruce``.  This succeeds for ``brother`` and is passed down to
230
``father_son`` which returns ``michael`` as ``fred's`` nephew.
228
``father_son`` which returns ``david`` as ``fred's`` nephew.
231
229
232
Further backtracking reveals no other solutions.
230
Further backtracking reveals no other solutions.
233
231
234
Backtracking Summary
232
Backtracking Summary
235
--------------------
233
--------------------
...
...
243
#. This execution model is not available within traditional programming
241
#. This execution model is not available within traditional programming
244
   languages like Python.
242
   languages like Python.
245
#. The ability to go back to *any* point in the computation to try an
243
#. The ability to go back to *any* point in the computation to try an
246
   alternate solution is where backward-chaining systems get their power!
244
   alternate solution is where backward-chaining systems get their power!
247
245
246
.. This code is hidden.  It will add '' to sys.path, change to the doc.examples
247
   directory and store the directory path in __file__ for the code section
248
   following:
249
   >>> import sys
250
   >>> if '' not in sys.path: sys.path.insert(0, '')
251
   >>> import os
252
   >>> os.chdir("../../../examples")
253
   >>> __file__ = os.getcwd()
254
248
Running the Example
255
Running the Example
249
========================
256
========================
250
257
251
    >>> from pyke import knowledge_engine
258
    >>> from pyke import knowledge_engine
252
    >>> engine = knowledge_engine.engine('doc.examples')
259
    >>> engine = knowledge_engine.engine(__file__)
253
    >>> engine.assert_('family', 'son_of', ('tim', 'thomas'))
254
    >>> engine.assert_('family', 'son_of', ('fred', 'thomas'))
255
    >>> engine.assert_('family', 'son_of', ('bruce', 'thomas'))
256
    >>> engine.assert_('family', 'son_of', ('michael', 'bruce'))
257
    >>> engine.activate('bc_example')
260
    >>> engine.activate('bc_related')
258
261
259
Nothing happens this time when we activate the rule base, because there are no
262
Nothing happens this time when we activate the rule base, because there are no
260
forward-chaining rules here.
263
forward-chaining rules here.
261
264
262
We want to ask the question: "Who are Fred's nephews?".  This translates
265
We want to ask the question: "Who are Fred's nephews?".  This translates
263
into the Pyke statement: ``bc_example.uncle_nephew(fred, $v1, $v2)``.
266
into the Pyke statement: ``bc_related.uncle_nephew(fred, $v1, $v2)``.
264
267
265
.. note::
268
.. note::
266
   Note that we're using the name of the rule base, ``bc_example`` rather than
269
   Note that we're using the name of the rule base, ``bc_related`` rather than
267
   the fact base, ``family`` here; because we expect this answer to come from
270
   the fact base, ``family2`` here; because we expect this answer to come from
268
   the ``bc_example`` rule base.
271
   the ``bc_related`` rule base.
269
272
270
This is 'bc_example', 'uncle_nephew', with ('fred',) followed by 2 pattern
273
This is 'bc_related', 'uncle_nephew', with ('fred',) followed by 2 pattern
271
variables as arguments:
274
variables as arguments:
272
275
273
    >>> from __future__ import with_statement
276
    >>> from __future__ import with_statement
274
    >>> with engine.prove_n('bc_example', 'uncle_nephew', ('fred',), 2) as gen:
277
    >>> with engine.prove_goal('bc_related.uncle_nephew(fred, $nephew, $distance)') as gen:
275
    ...     for vars, no_plan in gen:
278
    ...     for vars, no_plan in gen:
276
    ...         print(vars)
279
    ...         print(vars['nephew'], vars['distance'])
277
    ('michael', ())
280
    david ()
278
281
279
282
280
.. _example: forward_chaining.html#example
283
.. _example: forward_chaining.html#example
281
284
282
285