Inference engine in Java

[Will Ware]

/**
* Use directed graph to reason, ala RDF.
*
* Inefficient forward chaining: first derive everything
* that can be derived, then query the resulting database
* of facts.
*/

import java.util.ArrayList;
import java.util.Iterator;
import java.util.HashMap;

public class Thing {
String name;
boolean isVariable, isTriple;
protected Thing() {
isVariable = isTriple = false;
}
Thing(String name) {
this();
this.name = name;
}
boolean equals(Thing other) {
if (isTriple) {
if (!other.isTriple) return false;
return ((Triple)this).equals((Triple)other);
}
else if (isVariable) {
if (!other.isVariable) return false;
return ((Variable)this).equals((Variable)other);
}
else if (name == null)
return (other.name == null);
return name.equals(other.name);
}
int intValue() {
return (new Integer(name).intValue());
}
public String toString() {
return name;
}
void thinkAbout(Triple tr, Database db)
throws LogicException {
}
Thing map(HashMap m) {
if (m.containsKey(this))
return (Thing) m.get(this);
return this;
}

public static void main(String[] args) {
/* nouns */
Thing alice = new Thing("alice");
Thing paul = new Thing("paul");
Thing molly = new Thing("molly");
Thing idaho = new Thing("idaho");
Thing human = new Thing("human");
Thing dog = new Thing("dog");
Thing symmetric = new Thing("symmetric");
Thing transitive = new Thing("transitive");
/* predicates */
Thing liveswith = new Thing("liveswith");
Thing pet = new Thing("pet");
Thing species = new Thing("species");
Thing sibling = new Thing("sibling");
Thing hasprop = new Thing("hasprop");
/* predicates that actually do things */
Thing implies = new Implies("implies");
Thing maxcardinality = new MaxCardinality("maxcardinality");
/* variables */
Thing W = new Variable("W");
Thing X = new Variable("X");
Thing Y = new Variable("Y");
Thing Z = new Variable("Z");

Triple[] rules = {
/* definitions of symmetric and transitive */
new Triple(new Triple(X, hasprop, symmetric),
implies,
new Triple(new Triple(Y, X, Z),
implies,
new Triple(Z, X, Y))),
new Triple(new Triple(X, hasprop, symmetric),
implies,
new Triple(new Triple(Y, X, Z, Triple.NOT),
implies,
new Triple(Z, X, Y, Triple.NOT))),
new Triple(new Triple(W, hasprop, transitive),
implies,
new Triple(new Triple(X, W, Y),
implies,
new Triple(new Triple(Y, W, Z),
implies,
new Triple(X, W, Z)))),

new Triple(liveswith, hasprop, symmetric),
new Triple(sibling, hasprop, symmetric),
new Triple(liveswith, hasprop, transitive),
new Triple(sibling, hasprop, transitive),

/* Pets live with their owners. */
new Triple(new Triple(X, pet, Y),
implies,
new Triple(X, liveswith, Y)),

/* If you have a pet, you're human. */
new Triple(new Triple(X, pet, Y),
implies,
new Triple(Y, species, human)),

/* If you have a pet, the pet is not your sibling. */
new Triple(new Triple(X, pet, Y),
implies,
new Triple(X, sibling, Y, Triple.NOT)),

/* Siblings are the same species */
new Triple(new Triple(X, sibling, Y),
implies,
new Triple(new Triple(X, species, Z),
implies,
new Triple(Y, species, Z))),

/* If X liveswith Y, and Z not-liveswith X, */
/* then Z not-liveswith Y */
new Triple(new Triple(X, liveswith, Y, Triple.NOT),
implies,
new Triple(new Triple(Z, liveswith, X),
implies,
new Triple(Z, liveswith, Y,
Triple.NOT))),

/* If X is human and lives with Y, */
/* and Z is the pet of Y, */
/* then Z is also the pet of X. */
new Triple(new Triple(X, species, human),
implies,
new Triple(new Triple(X, liveswith, Y),
implies,
new Triple(new Triple(Z, pet, Y),
implies,
new Triple(Z, pet, X)))),

/* Nobody gets more than one species */
new Triple(species, maxcardinality, new Thing("1")),
};

Triple[] facts = {
new Triple(alice, liveswith, paul),
new Triple(alice, liveswith, molly, Triple.NOT),
new Triple(alice, sibling, paul),
new Triple(alice, sibling, molly),
new Triple(idaho, pet, alice),
new Triple(idaho, species, dog),

/* fallacies */
// new Triple(idaho, pet, paul, Triple.NOT), // paradox
// new Triple(paul, species, dog), // species cardinality
};

Database db = new Database(rules);
db = db.add(new Database(facts));
try { db.think(); }
catch (Exception e) {
e.printStackTrace();
return;
}
db.dump();

/* Test questions
*/
System.out.println("Who lives with alice?");
Iterator iter = db.match(new Triple(null, liveswith, alice));
while (iter.hasNext())
System.out.println((Thing)iter.next());

System.out.println("Who is human?");
iter = db.match(new Triple(null, species, human));
while (iter.hasNext())
System.out.println((Thing)iter.next());

System.out.println("Who has idaho for a pet?");
iter = db.match(new Triple(idaho, pet, null));
while (iter.hasNext())
System.out.println((Thing)iter.next());

System.out.println("What is idaho's species?");
iter = db.match(new Triple(idaho, species, null));
while (iter.hasNext())
System.out.println((Thing)iter.next());

System.out.println("Who doesn't live with Molly, and how do you
know?");
iter = db.match(new Triple(null, liveswith, molly, Triple.NOT));
while (iter.hasNext())
System.out.print(((Triple)iter.next()).explain());
}
}

class Variable extends Thing {
Variable(String name) {
super(name);
isVariable = true;
}
boolean equals(Thing other) {
if (!other.isVariable || other.isTriple)
return false;
return name.equals(other.name);
}
}

class Triple extends Thing {
final static boolean NOT = false;
Thing subj, pred, obj;
boolean affirmative;
Triple[] why;
Triple(Thing subj, Thing pred, Thing obj) {
this(subj, pred, obj, true);
}
Triple(Thing subj, Thing pred, Thing obj,
boolean affirmative) {
isTriple = true;
this.subj = subj;
this.pred = pred;
this.obj = obj;
this.affirmative = affirmative;
why = new Triple[0];
}
boolean equals(Triple other) {
if (other.isVariable || !other.isTriple)
return false;
if (!subj.equals(other.subj))
return false;
if (!pred.equals(other.pred))
return false;
if (!obj.equals(other.obj))
return false;
if (affirmative != other.affirmative)
return false;
return true;
}
public String toString() {
String r;
r = ("(" + subj.toString() +
" ");
if (!affirmative)
r += "not-";
r += (pred.toString() + " " +
obj.toString() + ")");
return r;
}
Triple negate() {
return new Triple(subj, pred, obj,
!affirmative);
}
public Object clone() {
Triple t = new Triple(subj, pred, obj,
affirmative);
t.why = why;
return t;
}
String explain() {
return explain(0);
}
String explain(int indent) {
String r = "";
for (int i = 0; i < indent; i++)
r += " ";
r += toString() + "\n";
for (int i = 0; i < why.length; i++)
r += why[i].explain(indent + 1);
return r;
}
Thing map(HashMap m) {
return new Triple(subj.map(m),
pred.map(m),
obj.map(m),
affirmative);
}
}

class LogicException extends Exception {
LogicException(String message) {
super(message);
}
}

class Database {
ArrayList lst, newlst;
Database(Triple[] tlist) {
ArrayList lst = new ArrayList();
for (int i = 0; i < tlist.length; i++)
lst.add(tlist[i]);
init(lst);
}
Database(ArrayList lst) {
init(lst);
}
private void init(ArrayList lst) {
this.lst = lst;
newlst = new ArrayList();
}
Database add(Database other) {
ArrayList lst2 = (ArrayList) lst.clone();
lst2.addAll(other.lst);
return new Database(lst2);
}
void merge(Database other) {
}
Triple findThis(Triple t) {
int n;
for (n = 0; n < lst.size(); n++) {
Triple x = (Triple) lst.get(n);
if (x.equals(t))
return x;
}
for (n = 0; n < newlst.size(); n++) {
Triple x = (Triple) newlst.get(n);
if (x.equals(t))
return x;
}
return null;
}
void add(Triple t) {
if (!lst.contains(t))
lst.add(t);
}
void dump() {
int i;
String r = "";
Iterator iter = lst.iterator();
i = 0;
while (iter.hasNext()) {
r += " " + (new Integer(i)).toString();
r += " " + ((Thing)iter.next()).toString() + "\n";
i++;
}
System.out.print(r);
}
void enqueue(Triple t) {
if (findThis(t) == null)
newlst.add(t);
}
private int flush() {
int n = newlst.size();
lst.addAll(newlst);
newlst = new ArrayList();
return n;
}
Iterator match(Triple t) {
ArrayList alst = new ArrayList();
Iterator iter = lst.iterator();
while (iter.hasNext()) {
Triple t2 = (Triple) iter.next();
if ((t.subj == null ||
t.subj.equals(t2.subj)) &&
(t.pred == null ||
t.pred.equals(t2.pred)) &&
(t.obj == null ||
t.obj.equals(t2.obj)) &&
t.affirmative == t2.affirmative)
alst.add(t2);
}
return alst.iterator();
}
void think()
throws LogicException {
while (true) {
System.out.println(lst.size());
ArrayList predlist = new ArrayList();
Iterator iter = lst.iterator();
Iterator iter2;
while (iter.hasNext()) {
Triple triple = (Triple) iter.next();
Thing pred = triple.pred;
if (!predlist.contains(pred))
predlist.add(pred);
}
iter = predlist.iterator();
while (iter.hasNext()) {
Thing pred = (Thing) iter.next();
iter2 = match(new Triple(null, pred, null));
while (iter2.hasNext())
pred.thinkAbout((Triple) iter2.next(),
this);
}
if (flush() == 0)
break;
}
System.out.println(lst.size());
}
}

class Implies extends Thing {
Implies(String name) {
super(name);
}
void thinkAbout(Triple tr, Database db)
throws LogicException {
Triple antecedent = (Triple) tr.subj;
Triple template = (Triple) antecedent.clone();
Triple consequent = (Triple) tr.obj;
boolean vars[] = {
antecedent.subj.isVariable,
antecedent.pred.isVariable,
antecedent.obj.isVariable
};
if (vars[0])
template.subj = null;
if (vars[1])
template.pred = null;
if (vars[2])
template.obj = null;
Iterator iter = db.match(template);
while (iter.hasNext()) {
Triple premise = (Triple) iter.next();
HashMap bindings = new HashMap();
if (vars[0])
bindings.put(antecedent.subj,
premise.subj);
if (vars[1])
bindings.put(antecedent.pred,
premise.pred);
if (vars[2])
bindings.put(antecedent.obj,
premise.obj);
Triple newguy =
(Triple) consequent.map(bindings);
if (!tautology(newguy)) {
Triple[] why = { tr, premise };
newguy.why = why;
/* check for paradox: to we already know this
* is false?
*/
Triple contrary = db.findThis(newguy.negate());
if (contrary != null) {
System.out.print(contrary.explain());
System.out.print(newguy.explain());
throw new LogicException("Paradox: " +
newguy.toString());
}
db.enqueue(newguy);
}
}
}
private boolean tautology(Triple x) {
/* Tautologies have the form "X implies X" */
return (x.pred.equals(this) &&
x.subj.equals(x.obj));
}
}

class MaxCardinality extends Thing {
MaxCardinality(String name) {
this.name = name;
}
void thinkAbout(Triple tr, Database db)
throws LogicException {
Thing pred = tr.subj;
int limit = tr.obj.intValue();
Iterator it = db.match(new Triple(null, pred, null));
while (it.hasNext()) {
Triple t = (Triple) it.next();
Iterator S = db.match(new Triple(t.subj, pred, null));
int n;
for (n = 0; S.hasNext(); n++)
S.next();
if (n > limit) {
S = db.match(new Triple(t.subj, pred, null));
while (S.hasNext())
System.out.print(((Triple)S.next()).explain());
throw new LogicException("cardinality: " + pred.name);
}
}
}
}