I need help completing this backwardChain.java program, its missing some versions of the overloaded method called unify. In particular, it is missing the implementations for UNIFY that take two literals, that take two logical terms, and that take two functions. I have to provide bodies for these three methods by modifying the BackwardChain.java le and none others.I have provided sample files at the end as well:

1. BindingList unify(Literal lit1, Literal lit2, BindingList bl) This method attempts to nd a binding list that allows for the unication of the two provided literals, under the constraints of the given binding list. If the two literals can be unied, a new binding list is returned, augmenting the given binding list with any additional bindings needed to unify the two literals. If unication is not possible, this method should return null.

2.BindingList unify(Term t1, Term t2, BindingList bl) This method attempts to nd a binding list that allows for the unication of the two provided terms (which can be constants, variables, or functions), under the constraints of the given binding list. If the two terms can be unied, a new binding list is returned, augmenting the given binding list with any additional bindings needed to unify the two terms. If unication is not possible, this method should return null. 3.BindingList unify(Function f1, Function f2, BindingList bl) This method attempts to nd a binding list that allows for the unication of the two provided functions, under the constraints of the given binding list. If the two functions can be unied, a new binding list is returned, augmenting the given binding list with any additional bindings needed to unify the two functions. If unication is not possible, this method should return null.

// BackwardChain.java

// // This class implements a backward chaining inference procedure. The // implementation is very skeletal, and the resulting reasoning process is // not particularly efficient. Knowledge is restricted to the form of // definite clauses, grouped into a list of positive literals (facts) and // a list of Horn clause implications (rules). The inference procedure // maintains a list of goals. On each step, a proof is sought for the // first goal in this list, starting by an attempt to unify the goal with // any known fact in the knowledge base. If this fails, the rules are // examined in the order in which they appear in the knowledge base, searching // for a consequent that unifies with the goal. Upon successful unification, // a proof is sought for the conjunction of the rule antecedents. If this // fails, further rules are considered. Note that this is a strictly // depth-first approach, so it is incomplete. Note, also, that there is // no backtracking with regard to matches to facts -- the first match is // always taken and other potential matches are ignored. This can make // the algorithm incomplete in another way. In short, the order in which // facts and rules appear in the knowledge base can have a large influence // on the behavior of this inference procedure. // // In order to use this inference engine, the knowledge base must be // initialized by a call to "initKB". Queries are then submitted using the // "ask" method. The "ask" function returns a binding list which includes // bindings for intermediate // import java.util.*; public class BackwardChain { public KnowledgeBase kb; // Default constructor ... public BackwardChain() { this.kb = new KnowledgeBase(); } // initKB -- Initialize the knowledge base by interactively requesting // file names and reading those files. Return false on error. public boolean initKB() { return (kb.readKB()); } // unify -- Return the most general unifier for the two provided literals, // or null if no unification is possible. The returned binding list // should be freshly allocated. public BindingList unify(Literal lit1, Literal lit2, BindingList bl) { // PROVIDE YOUR CODE HERE! return (null); } // unify -- Return the most general unifier for the two provided terms, // or null if no unification is possible. The returned binding list // should be freshly allocated. public BindingList unify(Term t1, Term t2, BindingList bl) { // PROVIDE YOUR CODE HERE! return (null); } // unify -- Return the most general unifier for the two provided lists of // terms, or null if no unification is possible. The returned binding list // should be freshly allocated. public BindingList unify(Function f1, Function f2, BindingList bl) { // PROVIDE YOUR CODE HERE! return (null); } // unify -- Return the most general unifier for the two provided lists of // terms, or null if no unification is possible. The returned binding // list should be freshly allocated. public BindingList unify(List ts1, List ts2, BindingList bl) { if (bl == null) return (null); if ((ts1.size() == 0) && (ts2.size() == 0)) // Empty lists match other empty lists ... return (new BindingList(bl)); if ((ts1.size() == 0) || (ts2.size() == 0)) // Ran out of arguments in one list before reaching the // end of the other list, which means the two argument lists // can't match ... return (null); List terms1 = new LinkedList(); List terms2 = new LinkedList(); terms1.addAll(ts1); terms2.addAll(ts2); Term t1 = terms1.get(0); Term t2 = terms2.get(0); terms1.remove(0); terms2.remove(0); return (unify(terms1, terms2, unify(t1, t2, bl))); } // askFacts -- Examine all of the facts in the knowledge base to // determine if any of them unify with the given literal, under the // given binding list. If a unification is found, return the // corresponding most general unifier. If none is found, return null // to indicate failure. BindingList askFacts(Literal lit, BindingList bl) { BindingList mgu = null; // Most General Unifier for (Literal fact : kb.facts) { mgu = unify(lit, fact, bl); if (mgu != null) return (mgu); } return (null); } // askFacts -- Examine all of the facts in the knowledge base to // determine if any of them unify with the given literal. If a // unification is found, return the corresponding most general unifier. // If none is found, return null to indicate failure. BindingList askFacts(Literal lit) { return (askFacts(lit, new BindingList())); } // ask -- Try to prove the given goal literal, under the constraints of // the given binding list, using both the list of known facts and the // collection of known rules. Terminate as soon as a proof is found, // returning the resulting binding list for that proof. Return null if // no proof can be found. The returned binding list should be freshly // allocated. BindingList ask(Literal goal, BindingList bl) { BindingList result = askFacts(goal, bl); if (result != null) { // The literal can be unified with a known fact ... return (result); } // Need to look at rules ... for (Rule candidateRule : kb.rules) { if (candidateRule.consequent.pred.equals(goal.pred)) { // The rule head uses the same predicate as the goal ... // Standardize apart ... Rule r = candidateRule.standardizeApart(); // Check to see if the consequent unifies with the goal ... result = unify(goal, r.consequent, bl); if (result != null) { // This rule might be part of a proof, if we can prove // the rule's antecedents ... result = ask(r.antecedents, result); if (result != null) { // The antecedents have been proven, so the goal // is proven ... return (result); } } } } // No rule that matches has antecedents that can be proven. Thus, // the search fails ... return (null); } // ask -- Try to prove the given goal literal using both the list of // known facts and the collection of known rules. Terminate as soon as // a proof is found, returning the resulting binding list for that proof. // Return null if no proof can be found. The returned binding list // should be freshly allocated. BindingList ask(Literal goal) { return (ask(goal, new BindingList())); } // ask -- Try to prove the given list of goal literals, under the // constraints of the given binding list, using both the list of known // facts and the collection of known rules. Terminate as soon as a proof // is found, returning the resulting binding list for that proof. Return // null if no proof can be found. The returned binding list should be // freshly allocated. BindingList ask(List goals, BindingList bl) { if (goals.size() == 0) { // All goals have been satisfied ... return (bl); } else { List newGoals = new LinkedList(); newGoals.addAll(goals); Literal goal = newGoals.get(0); newGoals.remove(0); BindingList firstBL = ask(goal, bl); if (firstBL == null) { // Failure to prove one of the goals ... return (null); } else { // Try to prove the remaining goals ... return (ask(newGoals, firstBL)); } } } } // // Binding // // This class implements an element of a logical binding list. It is a // simple pair, consisting of a variable and its (term) value. These are // grouped to form binding lists (substitution lists). // // David Noelle -- Tue Apr 10 17:08:45 PDT 2007 // public class Binding { public Variable var; public Term val; // Default constructor ... public Binding() { this.var = null; this.val = null; } // Constructor with field values ... public Binding(Variable var, Term val) { this.var = var; this.val = val; } }

// // BindingList // // This class implements a logical binding list (or substitution list). It // consists of a simple list of variable/value bindings. A method is // provided for adding bindings, one at a time, and for composing binding // lists together. Most importantly, a method is provided for searching // a binding list for the bound value of a given variable, if any. This // search is currently done inefficiently, using a linear search of the list. // The search is recursive, returning a value for which there is no // subsequent binding, if such exists. Lastly, a filtering function that // extracts only bindings of interest (e.g., those involving variables // in a query) is provided.

import java.io.*; import java.util.*;

public class BindingList {

public List pairs;

// Default constructor ... public BindingList() { this.pairs = new ArrayList(); }

// Copy constructor ... public BindingList(BindingList bl) { this(); this.pairs.addAll(bl.pairs); }

// compose -- Add all of the bindings in the given binding list to the // end of this binding list. public void compose(BindingList bl) { pairs.addAll(bl.pairs); }

// boundValue -- Search this binding list for a value corresponding to // the given variable. Return null if no such binding is found. public Term boundValue(Variable v) { for (Binding b : pairs) { if (b.var.equals(v)) { Term value = b.val; if (b.val.v != null) { // The value term is another variable ... value = boundValue(b.val.v); if (value == null) // This is the best we can do ... value = b.val; } if (b.val.f != null) { // The value term is a function, which could contain // bound variables ... value = new Term(b.val.f.subst(this)); } return (value); } } return (null); }

// addBinding -- Add the given binding to the binding list. public void addBinding(Variable var, Term val) { Binding b = new Binding(var, val); pairs.add(b); }

// filterBindings -- Return a copy of this binding list that only // contains bindings for variables in the given set. public BindingList filterBindings(Set vars) { BindingList newBL = new BindingList(); for (Binding b : pairs) { if (vars.contains(b.var)) newBL.addBinding(b.var, boundValue(b.var)); } return (newBL); }

// write -- Write this binding list to the given stream. public void write(OutputStream str) { PrintWriter out = new PrintWriter(str, true); out.printf("{ "); for (Binding b : pairs) { b.var.write(str); out.printf(" = "); b.val.write(str); out.printf(" "); } out.printf("} "); }

}

// // Constant // // This class implements a logical constant. This is simply a symbol. // public class Constant extends Symbol { // For making arbitrary novel constants ... static String gensymPrefix = "CONST-"; static int gensymCounter = 1; }

// // Function // // This class implements a logical function. Each function has a symbolic // name and a list of arguments, with each argument being a term. Methods // are provided for identifying all of the variables in a function (including // those appearing deep within arguments) and for substituting variables with // their corresponding values, according to a given binding list. //

import java.io.*; import java.util.*;

public class Function {

public FunctionName func; public List args;

// Default constructor ... public Function() { this.func = new FunctionName(); this.args = new ArrayList(); }

// equals -- Return true if and only if this function instance is the // same as the given argument. public boolean equals(Function f) { if (!(func.equals(f.func))) return (false); if (args.size() != f.args.size()) return (false); for (int i = 0; i < args.size(); i++) if (!(args.get(i).equals(f.args.get(i)))) return (false); return (true); }

// allVariables -- Return a set of all the variables in this function. public Set allVariables() { Set allVs = new HashSet(); for (Term arg : args) { allVs.addAll(arg.allVariables()); } return (allVs); }

// subst -- Return a new Function object that is the result of applying // the given binding list to this function invocation. Return null on // error. public Function subst(BindingList bl) { Function result = new Function(); result.func = func; for (Term arg : args) { result.args.add(arg.subst(bl)); } return (result); }

// read -- Read a function invocation from the given scanner, filling // in this Function object with the results. Return false on error. public boolean read(Scanner inScanner) { inScanner.useDelimiter("[\\s]+"); // Find and discard opening parenthesis ... try { inScanner.skip("[\\s]*\\("); } catch (NoSuchElementException e) { return (false); } // Read function name ... if (!(func.read(inScanner))) // Failed to read function name ... return (false); // Read each argument term, checking for the end of the function // expression ... inScanner.useDelimiter("[\\s]*"); while (!(inScanner.hasNext("[\\s]*\\)"))) { Term thisArg = new Term(); inScanner.useDelimiter("[\\s]+"); if (!(thisArg.read(inScanner))) // Failed to read argument term ... return (false); inScanner.useDelimiter("[\\s]*"); args.add(thisArg); } // Read closing parenthesis ... try { inScanner.skip("[\\s]*\\)"); } catch (NoSuchElementException e) { return (false); } // Reading was successful ... return (true); }

// write -- Write this function invocation to the given stream. public void write(OutputStream str) { try { str.write('('); func.write(str); for (Term arg : args) { str.write(' '); arg.write(str); } str.write(')'); } catch (IOException e) { // Something went wrong ... } }

}

// // FunctionName // // This class implements a symbolic function name. This is simply a symbol.

public class FunctionName extends Symbol {

// For making arbitrary novel constants ... static String gensymPrefix = "FUNC-"; static int gensymCounter = 1;

}

// // Knowledge Base // // This class implements a knowledge base of definite clauses. A list of // positive literals with only ground terms is maintained as a database of // "facts". Horn clause "rules" are also kept in an ordered list. Typically, // these facts and rules are read from plain text files, and the names of // these files are maintained by the KnowledgeBase object. Indeed, this // class includes methods for prompting the user for these file names, storing // them in the object, and reading collections of facts and rules from // the corresponding files. The top-level function for reading a knowledge // base from user-specified files is called "readKB". //

import java.io.*; import java.util.*;

public class KnowledgeBase {

String factsFilename = "facts.dat"; String rulesFilename = "rules.dat"; public List facts; public List rules;

// Default constructor ... public KnowledgeBase() { this.facts = new ArrayList(); this.rules = new ArrayList(); }

// Constructor with filenames specified ... public KnowledgeBase(String factsFilename, String rulesFilename) { this(); this.factsFilename = factsFilename; this. rulesFilename = rulesFilename; }

// setFactsFilename -- Record the given pathname of the facts file for // later use during knowledge base reading. public void setFactsFilename(String filename) { factsFilename = filename; }

// setRulesFilename -- Record the given pathname of the rules file for // later use during knowledge base reading. public void setRulesFilename(String filename) { rulesFilename = filename; }

// promptForFilenames -- Using the standard output stream and the standard // input stream, prompt the user to input the pathnames for a facts file // and for a rules file. Record the input pathnames in this object for // later use during knowledge base reading. Return false on error. public boolean promptForFilenames() { try { InputStreamReader converter = new InputStreamReader(System.in); BufferedReader in = new BufferedReader(converter); String buffer; System.out.println("Enter the name of the facts file:"); buffer = in.readLine(); setFactsFilename(buffer); System.out.println("Enter the name of the rules file:"); buffer = in.readLine(); setRulesFilename(buffer); } catch (IOException e) { // Something went wrong ... return (false); } return (true); }

// readFacts -- Attempt to open the facts file specified by the // appropriate pathname stored in this KnowledgeBase object. If this // file can be opened for reading, read a collection of facts from this // file into the knowledge base. Return false on error. public boolean readFacts() { try { File factFile = new File(factsFilename); if (factFile.exists() && factFile.canRead()) { FileInputStream factFileIn = new FileInputStream(factFile); InputStreamReader factISReader = new InputStreamReader(factFileIn); BufferedReader factBufferedReader

= new BufferedReader(factISReader); Scanner factScanner = new Scanner(factBufferedReader); // Allocate storage for the first fact to be read ... Literal fact = new Literal(); while (fact.read(factScanner)) { // Record the fact in the knowledge base ... facts.add(fact); // Allocate storage for the next fact ... fact = new Literal(); } return (true); } else { // The file cannot be read ... return (false); } } catch (IOException e) { // Something went wrong ... return (false); } }

// readRules -- Attempt to open the rules file specified by the // appropriate pathname stored in this KnowledgeBase object. If this // file can be opened for reading, read a collection of rules from this // file into the knowledge base. Return false on error. public boolean readRules() { try { File ruleFile = new File(rulesFilename); if (ruleFile.exists() && ruleFile.canRead()) { FileInputStream ruleFileIn = new FileInputStream(ruleFile); InputStreamReader ruleISReader = new InputStreamReader(ruleFileIn); BufferedReader ruleBufferedReader

= new BufferedReader(ruleISReader); Scanner ruleScanner = new Scanner(ruleBufferedReader); // Allocate storage for the first rule to be read ... Rule r = new Rule(); while (r.read(ruleScanner)) { // Record the rule in the knowledge base ... rules.add(r); // Allocate storage for the next rule ... r = new Rule(); } return (true); } else { // The file cannot be read ... return (false); } } catch (IOException e) { // Something went wrong ... return (false); } }

// readKB -- Prompt the user for the pathnames of a facts file and a // rules file, and then read those files into this KnowledgeBase object. // Return false on error. public boolean readKB() { return (promptForFilenames() && readFacts() && readRules()); }

}

// // Literal // // This class implements a non-negated literal. Each literal consists of // a symbolic predicate and a list of arguments, each of which is a term. // Methods are provided for identifying all of the variables in a given // literal (including those appearing deep within function arguments) and // for substituting variables with their corresponding values, according to // a given binding list. //

import java.io.*; import java.util.*;

public class Literal {

public Predicate pred; public List args;

// Default constructor ... public Literal() { this.pred = new Predicate(); this.args = new ArrayList(); }

// equals -- Return true if and only if this literal is the same as the // given literal argument. public boolean equals(Literal lit) { if (!(pred.equals(lit.pred))) return (false); if (args.size() != lit.args.size()) return (false); for (int i = 0; i < args.size(); i++) if (!(args.get(i).equals(lit.args.get(i)))) return (false); return (true); }

// allVariables -- Return a set of all the variables in this function. public Set allVariables() { Set allVs = new HashSet(); for (Term arg : args) { allVs.addAll(arg.allVariables()); } return (allVs); }

// subst -- Return a new Literal object that is the result of applying // the given binding list to this literal. Return null on error. public Literal subst(BindingList bl) { Literal result = new Literal(); result.pred = pred; for (Term arg : args) { result.args.add(arg.subst(bl)); } return (result); }

// read -- Read a literal from the given scanner, filling in this object // with the results. Return false on error. public boolean read(Scanner inScanner) { inScanner.useDelimiter("[\\s]+"); // Find and discard opening parenthesis ... try { inScanner.skip("[\\s]*\\("); } catch (NoSuchElementException e) { return (false); } // Read predicate name ... if (!(pred.read(inScanner))) // Failed to read predicate name ... return (false); // Read each argument term, checking for the end of the literal // expression ... inScanner.useDelimiter("[\\s]*"); while (!(inScanner.hasNext("[\\s]*\\)"))) { Term thisArg = new Term(); inScanner.useDelimiter("[\\s]+"); if (!(thisArg.read(inScanner))) // Failed to read argument term ... return (false); inScanner.useDelimiter("[\\s]*"); args.add(thisArg); } // Read closing parenthesis ... try { inScanner.skip("[\\s]*\\)"); } catch (NoSuchElementException e) { return (false); } // Reading was successful ... return (true); }

// write -- Write this literal to the given stream. public void write(OutputStream str) { try { str.write('('); pred.write(str); for (Term arg : args) { str.write(' '); arg.write(str); } str.write(')'); } catch (IOException e) { // Something went wrong ... } }

}

// // Predicate // // This class implements a symbolic predicate name. This is simply a symbol. //

public class Predicate extends Symbol {

// For making arbitrary novel constants ... static String gensymPrefix = "PRED-"; static int gensymCounter = 1;

}

// // Ptwo // // This class provides a "main" method that acts as a driver program for // a very simple backward chaining inference engine. The user is prompted // for the names of two files -- a file containing a collection of positive // literal ground term "facts" and a file containing a collection of Horn // clause "rules" -- and these files are read into an internal knowledge // base. The user is then prompted for a positive literal query, and a // backward chaining inference procedure is used to search for a proof for // that query. The result of that inference process is then reported, // along with an indication of the variable bindings necessary for the // discovered proof to hold.

import java.io.*; import java.util.*;

public class Ptwo {

public static void main(String[] args) { try { BackwardChain engine = new BackwardChain(); InputStreamReader converter = new InputStreamReader(System.in); BufferedReader in = new BufferedReader(converter); String queryLine; Literal query = new Literal(); BindingList resultBL;

System.out.println("BACKWARD CHAINING INFERENCE PROCEDURE"); // Read knowledge base ... if (!(engine.initKB())) { System.err.println("Error: Unable to read knowledge base."); return; } // Echo knowledge base for debugging purposes ... System.out.println("FACTS:"); for (Literal fact : engine.kb.facts) { fact.write(System.out); System.out.println(""); } System.out.println("RULES:"); for (Rule r : engine.kb.rules) { r.write(System.out); System.out.println(""); } // Get query ... System.out.println("Enter a (positive literal) query:"); queryLine = in.readLine(); Scanner queryScanner = new Scanner(queryLine); if (!(query.read(queryScanner))) { System.err.println("Error: Unable to read query."); return; } // Run inference procedure ... System.out.println("Running inference procedure ..."); resultBL = engine.ask(query); // Report results ... if (resultBL == null) { System.out.println("NO PROOF FOUND."); } else { // Filter the resulting binding list to only contain // variables that we care about ... resultBL = resultBL.filterBindings(query.allVariables()); // Report the results ... if (resultBL.pairs.size() == 0) { System.out.println("QUERY IS TRUE."); } else { System.out.println("QUERY IS TRUE UNDER THE BINDINGS:"); resultBL.write(System.out); } } // Done ... System.out.println("INFERENCE PROCEDURE COMPLETE"); } catch (IOException e) { // Something went wrong ... } } }

// // Rule // // This class implements a Horn clause rule. Each rule has a textual name, // a positive literal consequent ("head"), and a list of positive literal // antecedents ("tail"). All of the antecedents must be established as // true, under some binding list, in order to use the rule to justify the // truth of the consequent, under the same bindings. Methods are provided // for identifying all of the variables in a given rule (including those // appearing deep within its components) and for substituting variables // with their corresponding values, according to a given binding list. This // substitution procedure is also used by a method that replaces all variables // with novel variables, effectively standardizing the rule apart. //

import java.io.*; import java.util.*;

public class Rule {

public String name; public Literal consequent; // the "head" of the rule public List antecedents; // the "tail" of the rule

// Default constructor ... public Rule() { this.name = "NULL"; this.consequent = null; this.antecedents = new ArrayList(); }

// equals -- Return true if and only if this rule is the same as the // given rule argument. public boolean equals(Rule r) { if (!(name.equals(r.name))) return (false); if (!(consequent.equals(r.consequent))) return (false); if (antecedents.size() != r.antecedents.size()) return (false); for (int i = 0; i < antecedents.size(); i++) if (!(antecedents.get(i).equals(r.antecedents.get(i)))) return (false); return (true); }

// allVariables -- Return a set of all the variables in this function. public Set allVariables() { Set allVs = new HashSet(); allVs.addAll(consequent.allVariables()); for (Literal ante : antecedents) { allVs.addAll(ante.allVariables()); } return (allVs); }

// subst -- Return a new Rule object that is the result of applying // the given binding list to all of the literals in this rule. Return // null on error. public Rule subst(BindingList bl) { Rule result = new Rule(); result.name = name; result.consequent = consequent.subst(bl); for (Literal ante : antecedents) { result.antecedents.add(ante.subst(bl)); } return (result); }

// standardizeApart -- Return a new Rule object that is a copy of this // rule with all of the variable names changed. Return null on error. public Rule standardizeApart() { Set initialVars = allVariables(); BindingList bl = new BindingList(); for (Variable v : initialVars) { // Add a binding from this initial variable to a new, novel, // variable (converted into a term) ... bl.addBinding(v, new Term(new Variable(""))); } return (subst(bl)); }

// read -- Read a rule from the given scanner, filling in this object with // the results. Return false on error. public boolean read(Scanner inScanner) { inScanner.useDelimiter("[\\s]+"); // Find and discard opening parenthesis ... try { inScanner.skip("[\\s]*\\("); } catch (NoSuchElementException e) { return (false); } // Read the "DEFRULE" keyword ... if (inScanner.hasNext()) { String keyword = inScanner.next(); if (!(keyword.toUpperCase().equals("DEFRULE"))) return (false); } else { // There is nothing to read ... return (false); } // Read the rule name ... if (inScanner.hasNext()) { name = inScanner.next(); } else { // There is nothering to read ... return (false); } // Read antecedents ... inScanner.useDelimiter("[\\s]+"); while (inScanner.hasNext() && !(inScanner.hasNext("=>.*"))) { Literal ante = new Literal(); if (!(ante.read(inScanner))) return (false); inScanner.useDelimiter("[\\s]+"); antecedents.add(ante); } // Skip arrow ... try { inScanner.skip("[\\s]*=>"); } catch (NoSuchElementException e) { return (false); } // Read consequent ... if (consequent == null) consequent = new Literal(); if (!(consequent.read(inScanner))) return (false); // Hunt for closing parenthesis and read it ... try { inScanner.skip("[\\s]*\\)"); } catch (NoSuchElementException e) { return (false); } // Done! return (true); }

// write -- Write this rule to the given stream. public void write(OutputStream str) { PrintWriter out = new PrintWriter(str, true); out.printf("(DEFRULE %s ", name); for (Literal antecedent : antecedents) { out.printf(" "); antecedent.write(str); out.printf(" "); } out.printf("=> "); out.printf(" "); consequent.write(str); out.printf(" "); out.printf(") "); }

}

// // Symbol // // This class implements an atomic symbol. Symbol names can be provided // at creation time. If the empty string is provided as a symbol name, // a novel name is provided for the symbol, instead. //

import java.io.*; import java.util.*;

public class Symbol {

// For making arbitrary novel symbols ... static String gensymPrefix = "SYM-"; static int gensymCounter = 1;

public String name = "";

// Default constructor ... public Symbol() { this.name = "NULL"; }

// Constructor with symbol name specified ... public Symbol(String name) { if (name.length() == 0) { // This is a request to generate a symbol ... this.name = String.format("%s%04d", gensymPrefix, gensymCounter); gensymCounter++; } else { this.name = name; } }

// equals -- Return true if and only if this symbol has the same name // as the argument symbol. public boolean equals(Symbol s) { return (s.name.equals(this.name)); }

// read -- Read a symbol from the given scanner, changing the name of // this symbol to match that which was read. Return false on error. public boolean read(Scanner inScanner) { inScanner.useDelimiter("[\\(\\)\\s]+"); if (inScanner.hasNext()) { // There is a symbol ... name = inScanner.next(); return (true); } else { // There is nothing to read ... return (false); } } // write -- Write the name of this symbol to the given stream. public void write(OutputStream str) { PrintWriter out = new PrintWriter(str, true); out.printf("%s", name); }

}

// // Term // // This class implements a logical term: a constant, variable, or function. // This implementation is a little wasteful, providing separate variables // for each of the three types of terms. Methods are provided for identifying // all of the variables in a given term (including those appearing deep // within function arguments) and for substituting variables in a term with // their corresponding values, according to a given binding list. //

import java.io.*; import java.util.*;

public class Term {

public Constant c; public Variable v; public Function f;

// Default constructor ... public Term() { this.c = null; this.v = null; this.f = null; }

// Copy constructor ... public Term(Term trm) { this.c = trm.c; this.v = trm.v; this.f = trm.f; }

// Constructor for constants ... public Term(Constant c) { this.c = c; this.v = null; this.f = null; }

// Constructor for variables ... public Term(Variable v) { this.c = null; this.v = v; this.f = null; }

// Constructor for function invocations ... public Term(Function f) { this.c = null; this.v = null; this.f = f; }

// equals -- Return true if and only if this term is the same as the // given term. public boolean equals(Term trm) { if (((c == null) && (trm.c != null)) || ((c != null) && (trm.c == null)) || ((v == null) && (trm.v != null)) || ((v != null) && (trm.v == null)) || ((f == null) && (trm.f != null)) || ((f != null) && (trm.f == null))) { // Terms are of different types ... return (false); } else { // Terms are of the same type ... return (((c != null) && c.equals(trm.c)) || ((v != null) && v.equals(trm.v)) || ((f != null) && f.equals(trm.f))); } }

// allVariables -- Return a set of all the variables in this term. public Set allVariables() { Set allVs = new HashSet(); if (v != null) { allVs.add(v); } else { if (f != null) { return (f.allVariables()); } } return (allVs); }

// subst -- Return a new Term object that is the result of applying the // given binding list to this term. Return null on error. public Term subst(BindingList bl) { Term result; if (c != null) { result = new Term(c); } else { if (v != null) { result = bl.boundValue(v); if (result == null) result = new Term(v); else // Make a copy, and make sure that the resulting // term also has the binding list applied to it ... result = result.subst(bl); } else { if (f != null) { result = new Term(f.subst(bl)); } else { return (null); } } } return (result); }

// read -- Read a logical term from the given scanner, filling // in this object with the results. Return false on error. public boolean read(Scanner inScanner) { inScanner.useDelimiter("[\\s]+"); if (inScanner.hasNext("\\(.*")) { // The next item is a function invocation ... c = null; v = null; f = new Function(); return (f.read(inScanner)); } if (inScanner.hasNext("\\?.*")) { // The next item is a variable ... c = null; v = new Variable(); f = null; return (v.read(inScanner)); } // Assume that the next item is a constant ... c = new Constant(); v = null; f = null; return (c.read(inScanner)); }

// write -- Write this term to the given stream. public void write(OutputStream str) { if (c != null) { c.write(str); } else { if (v != null) { v.write(str); } else { if (f != null) { f.write(str); } else { try { // Internal error ... str.write('#'); str.write('#'); str.write('#'); } catch (IOException e) { // Something went wrong ... } } } } }

}

// // Variable // // This class implements a logical variable. This is simply a symbol. By // convention, all variable names must start with a question mark. //

public class Variable extends Symbol {

// For making arbitrary novel symbols ... static String gensymPrefix = "?VAR-"; static int gensymCounter = 1;

// Default constructor ... public Variable() { this.name = "?NULL"; }

// Constructor with symbol name specified ... public Variable(String name) { if (name.length() == 0) { // This is a request for a novel variable ... this.name = String.format("%s%04d", gensymPrefix, gensymCounter); gensymCounter++; } else { if (name.charAt(0) != '?') { this.name = "?" + name; } else { this.name = name; } } }

}

//facts.dat

(Missile M1) (Owns Nono M1) (American West) (Enemy Nono America)

//rules.dat

(DEFRULE Criminality (American ?x) (Weapon ?y) (Sells ?x ?y ?z) (Hostile ?z) => (Criminal ?x)) (DEFRULE MissilesFromWest (Missile ?x) (Owns Nono ?x) => (Sells West ?x Nono)) (DEFRULE MissilesAreWeapons (Missile ?x) => (Weapon ?x)) (DEFRULE EnemiesAreHostile (Enemy ?x America) => (Hostile ?x))

//log-noelle.txt

BACKWARD CHAINING INFERENCE PROCEDURE Enter the name of the facts file: /home/noelle/CSE175/Programs/PA2/TestCases/Linux/Criminal/facts.dat Enter the name of the rules file: /home/noelle/CSE175/Programs/PA2/TestCases/Linux/Criminal/rules.dat FACTS: (Missile M1) (Owns Nono M1) (American West) (Enemy Nono America) RULES: (DEFRULE Criminality (American ?x) (Weapon ?y) (Sells ?x ?y ?z) (Hostile ?z) => (Criminal ?x) )

(DEFRULE MissilesFromWest (Missile ?x) (Owns Nono ?x) => (Sells West ?x Nono) )

(DEFRULE MissilesAreWeapons (Missile ?x) => (Weapon ?x) )

(DEFRULE EnemiesAreHostile (Enemy ?x America) => (Hostile ?x) )

Enter a (positive literal) query: (Criminal Noelle) Running inference procedure ... NO PROOF FOUND. INFERENCE PROCEDURE COMPLETE

//readMe.txt

This example doesn't contain recursive rules, so most queries should allow the inference engine to terminate. Incomplete cases, involving endless searches, should be rare.

Try queries like "(Criminal West)" and "(Criminal ?person)".