Reasoning with Recursive Rules

This example demonstrates that PowerLoom automatically handles reasoning with recursive rules despite its use of a Prolog-style backward chainer (in Prolog, recursive rules rules have to be handled by carefully ordering them to avoid infinite recursion). The example uses parent and ancestor relations, since those naturally lead themselves to recursive formulations. The file also demonstrates the use of PowerLoom's defrelation command. 

;; Standard demo preamble:

|= (in-package "STELLA")


|= (defmodule "/PL-USER/RECURSION")

|MDL|/PL-USER/RECURSION

|= (in-module "/PL-USER/RECURSION")


|= (clear-module "/PL-USER/RECURSION")


|= (reset-features)

|i|()

|= (in-dialect :KIF)

:KIF

;; The already familiar `Person' class:

|= (defclass PERSON (STANDARD-OBJECT)
  :documentation "The class of human beings."
  :slots
  ((happy :type BOOLEAN)
   (age :type INTEGER)))

|C|PERSON

;; Now we define two relations `has-parent' and `has-ancestor' with
;; PowerLoom's `defrelation' command.  `defrelation' is very similar
;; to `deffunction' (see the `append' demo), with the main difference
;; that it does not take a `:type' specification, since relations are
;; boolean-valued.  Similar to functions, relations are polymorphic
;; (indexed on the type of their first argument) unless they were
;; defined with `:polymorphic?' set to FALSE.  Note again, that
;; functions and relations must be defined before they can be used in
;; any assertion or query.

|= (defrelation has-parent ((self PERSON) (parent PERSON))
  :documentation "True if `self' has `parent' as a parent.")

|T|HAS-PARENT

|= (defrelation has-ancestor ((self PERSON) (ancestor PERSON))
  :documentation "True if `self' has `ancestor' as an ancestor.")

|T|HAS-ANCESTOR

;; Rule 1: All parents are ancestors:

|= (assert (forall ((?x PERSON) (?y PERSON))
          (=> (has-parent ?x ?y)
              (has-ancestor ?x ?y))))

|P|(forall ((?x1 PERSON) (?x2 PERSON))
   (<= (HAS-ANCESTOR ?x1 ?x2)
       (HAS-PARENT ?x1 ?x2)))

;; Rule 2: Transitivity of ancestor relations: If `?y' is an ancestor of
;; `?x' and `?z' is an ancestor of `?y' then `?z' is also an ancestor of
;; `?x'.  This rule is recursive, since its consequent (or head) defines a
;; `has-ancestor' relationship by recursively referencing `has-ancestor'
;; in its antecedent (or tail).  A naive backward chaining architecture
;; would backchain into the consequent and simply post the two new
;; `has-ancestor' subgoals from the rule's antecedent.  However, these
;; subgoals might be duplicates of the original goal which could lead to
;; infinite subgoaling.  This is actually the strategy used by Prolog, and
;; there rule recursion has to be handled by hand using knowledge of the
;; order in which rules and clauses are processed and carefully ordering
;; them to avoid infinite recursion.  In PowerLoom the order of assertions
;; is completely irrelevant, and duplicate subgoals are detected
;; automatically.  This is an important feature, since recursion is a very
;; natural and powerful way to formulate axioms or rules, and people often
;; write recursive rules without even realizing that they do:

|= (assert (forall ((?x PERSON) (?z PERSON))
          (=> (exists (?y PERSON)
                (and (has-ancestor ?x ?y)
                     (has-ancestor ?y ?z))) 
              (has-ancestor ?x ?z))))

|P|(forall ((?x PERSON) (?z PERSON))
   (<= (HAS-ANCESTOR ?x ?z)
       (exists ((?y PERSON))
          (and (HAS-ANCESTOR ?x ?y)
               (HAS-ANCESTOR ?y ?z)))))

;; Let us create some people (note, that the top-level `and' gets optimized
;; away to leave only assertions of the individual conjuncts):

|= (assert (and (Person Abby) (Person Benny) (Person Carla)
             (Person Debbie) (Person Edward) (Person Fred)))

{|P|(PERSON FRED)
 |P|(PERSON EDWARD)
 |P|(PERSON DEBBIE)
 |P|(PERSON CARLA)
 |P|(PERSON BENNY)
 |P|(PERSON ABBY)}

;; Some parent and ancestor relationships we know about:

|= (assert (has-parent Abby Benny))

|P|(HAS-PARENT ABBY BENNY)

|= (assert (has-ancestor Benny Carla))

|P|(HAS-ANCESTOR BENNY CARLA)

|= (assert (has-parent Carla Debbie))

|P|(HAS-PARENT CARLA DEBBIE)

|= (assert (has-ancestor Debbie Edward))

|P|(HAS-ANCESTOR DEBBIE EDWARD)

|= (assert (has-parent Edward Fred))

|P|(HAS-PARENT EDWARD FRED)

;; First, let us derive Abby's ancestors using PowerLoom's incremental
;; query machinery.  Remember, that a `retrieve' without a specification
;; of a desired number of solutions generates at most one solution:

|= (retrieve (?z PERSON) (has-ancestor Abby ?z))

There is 1 solution so far:
  #1: ?Z=|i|FRED

;; More solutions of the most recent query can be generated by calling
;; `retrieve' without the query arguments (a desired number of new
;; solutions can still be specified):

|= (retrieve 2)

There are 3 solutions so far:
  #1: ?Z=|i|FRED
  #2: ?Z=|i|EDWARD
  #3: ?Z=|i|DEBBIE

|= (retrieve)

There are 4 solutions so far:
  #1: ?Z=|i|FRED
  #2: ?Z=|i|EDWARD
  #3: ?Z=|i|DEBBIE
  #4: ?Z=|i|CARLA

|= (retrieve)

There are 5 solutions so far:
  #1: ?Z=|i|FRED
  #2: ?Z=|i|EDWARD
  #3: ?Z=|i|DEBBIE
  #4: ?Z=|i|CARLA
  #5: ?Z=|i|BENNY

|= (retrieve)

There are 5 solutions:
  #1: ?Z=|i|FRED
  #2: ?Z=|i|EDWARD
  #3: ?Z=|i|DEBBIE
  #4: ?Z=|i|CARLA
  #5: ?Z=|i|BENNY

;; Now let us retrieve all ancestors of all other people:

|= (retrieve all (?z PERSON) (has-ancestor Benny ?z))

There are 4 solutions:
  #1: ?Z=|i|FRED
  #2: ?Z=|i|EDWARD
  #3: ?Z=|i|DEBBIE
  #4: ?Z=|i|CARLA

|= (retrieve all (?z PERSON) (has-ancestor Carla ?z))

There are 3 solutions:
  #1: ?Z=|i|FRED
  #2: ?Z=|i|EDWARD
  #3: ?Z=|i|DEBBIE

|= (retrieve all (?z PERSON) (has-ancestor Debbie ?z))

There are 2 solutions:
  #1: ?Z=|i|FRED
  #2: ?Z=|i|EDWARD

|= (retrieve all (?z PERSON) (has-ancestor Edward ?z))

There is 1 solution:
  #1: ?Z=|i|FRED

|= (retrieve all (?z PERSON) (has-ancestor Fred ?z))

No solutions.

|=
Information Sciences Institute ISI Intelligent Systems Division PowerLoom Home Page
Last modified: Nov 17, 1997