ancestorrelations, 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'. |=