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 lend themselves to recursive formulations.

    Welcome to PowerLoom 3.0.1.beta

Copyright (C) USC Information Sciences Institute, 1997-2003.
PowerLoom is a registered trademark of the University of Southern California.
PowerLoom comes with ABSOLUTELY NO WARRANTY!
Type `(copyright)' for detailed copyright information.
Type `(help)' for a list of available commands.
Type `(demo)' for a list of example applications.
Type `bye', `exit', `halt', `quit', or `stop', to exit.


|= (demo 6)

Now reading from `PL:sources;logic;demos;recursion.ste'.
Type `?' at the pause prompt for a list of available commands.

;;; -*- Mode: Lisp; Package: STELLA; Syntax: COMMON-LISP; Base: 10 -*-

;;; Version: recursion.ste,v 1.9 2001/06/06 19:07:30 tar Exp


;;; Inference along parent and ancestor relations with recursive rules
;;; ==================================================================

;;; This file 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 lend themselves to recursive formulations.  The file
;;; also demonstrates the use of `PowerLoom's `defrelation' command.

;;; The best way to view this file is by calling `(demo)' and
;;; selecting it from the menu of example demos.  This demo assumes
;;; familiarity with some basic PowerLoom concepts which are described
;;; in the introductory demo (#1 on the demo menu) and other demos
;;; preceding this one.


;; Standard demo preamble:

|= (in-package "STELLA")
------ pause ------c


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

|MDL|/PL-KERNEL-KB/PL-USER/RECURSION

|= (in-module "RECURSION")


|= (clear-module "RECURSION")


|= (reset-features)

|l|(:EMIT-THINKING-DOTS :JUST-IN-TIME-INFERENCE)

|= (in-dialect :KIF)

:KIF

;; The already familiar `Person' class:

|= (defconcept PERSON (?p)
  :documentation "The class of human beings.")

|c|PERSON

|= (defrelation happy ((?p PERSON)))

|r|HAPPY

|= (deffunction age ((?p PERSON)) :-> (?a INTEGER))

|f|AGE

;; 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 `:->' 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 ((?p PERSON) (?parent PERSON))
  :documentation "True if `self' has `parent' as a parent.")

|r|HAS-PARENT

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

|r|HAS-ANCESTOR

;; Rule 1: All parents are ancestors:

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

|P|(FORALL (?x ?y)
   (<= (HAS-ANCESTOR ?x ?y)
       (HAS-PARENT ?x ?y)))

;; 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 ?z)
   (<= (HAS-ANCESTOR ?x ?z)
       (EXISTS (?y)
          (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 ABBY) |P|(PERSON BENNY) |P|(PERSON CARLA) |P|(PERSON DEBBIE)
 |P|(PERSON EDWARD) |P|(PERSON FRED))

;; 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=BENNY

;; 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=BENNY
  #2: ?Z=CARLA
  #3: ?Z=DEBBIE

|= (retrieve)

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

|= (retrieve)

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

|= (retrieve)

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

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

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

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

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

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

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

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

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

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

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

No solutions.


|= 

Finished demo `PL:sources;logic;demos;recursion.ste'.

|= 

Information Sciences Institute PowerLoom Home Page
PowerLoom is a registered trademark of the University of Southern California.
Last modified: May 27, 2006