Reasoning with Recursive Rules

    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'.

|=