/* The definitions of the basic formula interfaces, Form and IfForm, appear below. Interfaces are used rather * than abstract classes so that the Constant and Variable classes can be subtypes in BOTH hierarchies. */ /** Form ::= Constant | Variable | Not(Form) | And(Form, Form) | Or(Form, Form) | Implies(Form, Form) | * If(Form, Form, Form) */ interface Form { /** @return the IfForm equivalent to this. */ IfForm convertToIf(); /** @return String representation of this. */ String print(); } /** IfForm ::= Constant | Variable | IfIf(IfForm, IfForm, IfForm) */ interface IfForm { /** @return the normalized form equivalent to this. A normalized IfForm only contains atoms (Constant | Variable) in * test position. */ IfForm normalize(); /** @return the normalized form equivaent to new If(this, conseq, alt), assuming the formulas this, conseq, and alt * are already normalized. */ IfForm headNormalize(IfForm conseq, IfForm alt); /** @return the "simplest" normalized form for this, assuming this is already normalized. Tautologies are reduced to * Constant.TRUE; contradictions are reduced to Constant.FALSE. Other formulas are reduced according to an ordered * set of reduction rules. */ IfForm eval(Environment env); /** @return a Form f containing the fewest possible If constructions such that f.convertToIf() = this. */ Form convertToBool(); /** @return String representation of this. */ String print(); } /* An Environment is a list of bindings of variables to constants (instances of Constant). */ abstract class Environment { Environment bind(Variable s, IfForm v) { return new AddBinding(s,v,this); } /** Returns the matching Constant bound to v. If no such Constant is found, returns v. */ abstract public IfForm lookup(Variable v); } /** The Empty Environment class, akin to Scheme empty */ class EmptyEnvironment extends Environment { /** Single empty environment. */ static Environment ONLY = new EmptyEnvironment(); private EmptyEnvironment() { } IfForm lookup(Variable v) { return v; } } /** The non-empty Environment class, akin to Scheme cons. */ class AddBinding extends Environment { Variable sym; IfForm value; Environment rest; IfForm lookup(Variable s) { if (s.equals(sym)) return value; else return rest.lookup(s); } } /* The concrete classes in the Form and IfForm composite hierarchies follow. */ class Variable implements Form, IfForm { String name; public IfForm convertToIf() { return null; /* ... */ } public IfForm normalize() { return null; /* ... */ } public IfForm headNormalize(IfForm conseq, IfForm alt) { return null; /* ... */ } public IfForm eval(Environment env) { return env.lookup(this); } // lookup(this) returns this on failure public Form convertToBool() { return null; /* ... */ } public String print() { return name; } } class Constant implements Form, IfForm { boolean value; /** Singleton definitions of true and false. */ static Constant TRUE = new Constant(true); static Constant FALSE = new Constant(false); private Constant(boolean v) { value = v; } public IfForm convertToIf() { return null; /* ... */ } public IfForm normalize() { return null; /* ... */ } public IfForm headNormalize(IfForm conseq, IfForm alt) { return null; /* ... */ } public IfForm eval(Environment env) { return null; /* ... */ } public Form convertToBool() { return null; /* ... */ } public String print() { if (this == TRUE) return "T"; else return "F"; } } class IfIf implements IfForm { IfForm test,conseq,alt; public IfForm normalize() { return null; /* ... */ } public IfForm headNormalize(IfForm conseq, IfForm alt) { return null; /* ... */ } public IfForm eval(Environment env) { return null; /* ... */ } public Form convertToBool() { return null; /* ... */ } public String print() { return "(? " + test.print() + " " + conseq.print() + " " + alt.print() + ")"; } } class If implements Form { Form test,conseq,alt; public IfForm convertToIf() { return null; /* ... */ } public String print() { return "(? " + test.print() + " " + conseq.print() + " " + alt.print() + ")"; } } class Not implements Form { Form arg; public IfForm convertToIf() { return null; /* ... */ } public String print() { return "(! " + arg.print() + ")"; } } class And implements Form { Form left,right; public IfForm convertToIf() { return null; /* ... */ } public String print() { return "(& " + left.print() + " " + right.print() + ")"; } } class Or implements Form { Form left,right; public IfForm convertToIf() { return null; /* ... */ } public String print() { return "(| " + left.print() + " " + right.print() + ")"; } } class Implies implements Form { Form left,right; public IfForm convertToIf() { return null; /* ... */ } public String print() { return "(> " + left.print() + " " + right.print() + ")"; } }