All Packages  This Package  Class Hierarchy  Class Search  Index

Class aima.logic.Unify

java.lang.Object
   |
   +----aima.logic.Unify

The Unify class provides methods for the unification of expressions and the substitution of values for variables in expressions. This code is adapted from LISP code which contained the following comment:

   Unification and Substitutions (aka Binding Lists)

   This code is borrowed from "Paradigms of AI Programming: Case Studies
   in Common Lisp", by Peter Norvig, published by Morgan Kaufmann, 1992.
   The complete code from that book is available for ftp at mkp.com in
   the directory "pub/Norvig".  Note that it uses the term "bindings"
   rather than "substitution" or "theta".  The meaning is the same.
 

See Also: Variable, Bindings, Expression

public class  Unify
     extends java.lang.Object
{
          // Methods 9
     public static void main(String[]) throws Exception;
     public static boolean occursIn(Variable, Object, Bindings);
     public static Object parse(String) throws Exception;
     public static Object parseVariables(Object);
     public static Object renameVariables(Object);
     public static Object substBindings(Object, Bindings);
     public static Object unifier(Object, Object);
     public static Bindings unify(Object, Object);
     public static Bindings unify(Object, Object, Bindings);
}

• parse

   public static Object parse(String exprStr)  throws Exception

Parses the input String into an expression which may be processed by the various unify methods. In particular, tokens in the input that are prefixed appropriately are converted into Variable objects.

Parameter	Description
exprStr	An expression to parse.

Returns:

An expression suitable as input to the various Unify methods

Throws: Exception

May be thrown if the expression String does not parse properly.

See Also: unify, unifier, getPrefix

• parseVariables

   public static Object parseVariables(Object obj) 

Processes a (compound or atomic) expression to create a new expression in which all atoms, whose print names have an appropriate prefix character, are replaced with Variable objects.

Parameter	Description
obj	An expression to process.

Returns:

An expression suitable as input to the various Unify methods

See Also: unify, unifier, Expression, getPrefix

• unifier

   public static Object unifier(Object x, 
                                Object y) 

Returns something that unifies with both x and y (or fail).

Parameter	Description
x	An expression (atomic or compound) to unify.
y	An expression (atomic or compound) to unify.

Returns:

An expression that unifies with both x and y, or the Bindings object that represents failure.

See Also: getFailure, Expression, unify

• unify

   public static Bindings unify(Object x, 
                                Object y) 

Determines if the given expressions match and returns a Bindings object that would make them equal.

By default, the Bindings object returned is in terms of a ListBindings implementation. If you want to explicitly specify the Bindings implementation to use, use the alternative version of unify where you should pass in an empty Bindings object of the desired implementation type. For instance:

     Unify.unify(x,y,HashBindings.getEmpty());
 

would return the results of the unification in a HashBindings Bindings implementation.

Parameter	Description
x	An expression (atomic or compound) to unify.
y	An expression (atomic or compound) to unify.

Returns:

A Bindings object that would make the input parameters match, or the Bindings object that represents failure if they do not match.

See Also: Bindings, ListBindings, HashBindings, Variable, Expression

• unify

   public static Bindings unify(Object x, 
                                Object y, 
                                Bindings theBindings) 

Determines if the given expressions match subject to the variable bindings given in the initial Bindings object and returns a Bindings object that would make them equal.

Parameter	Description
x	An expression (atomic or compound) to unify.
y	An expression (atomic or compound) to unify.
theBindings	An initial set of bindings to begin with.

Returns:

A Bindings object that would make the input parameters match, or the Bindings object that represents failure if they do not match.

See Also: Bindings, Variable, Expression

• occursIn

   public static boolean occursIn(Variable var, 
                                  Object x, 
                                  Bindings theBindings) 

Determines if the given Variable occurs anywhere inside the given expression, subject to the bindings contained in the given Bindings object.

Parameter	Description
var	Variable for which to search.
x	An expression (atomic or compound) to search.
theBindings	An set of bindings on the variables in x

Returns:

true iff var is contained is x subject to theBindings

See Also: Bindings, Variable, Expression

• renameVariables

   public static Object renameVariables(Object x) 

Creates an isomorphic expression to the given expression in which all the variables have been replaced with new ones. If a variable appears more than once in the expression, then it is given the same replacement at each position in which it occurs.

Parameter	Description
x	An expression (atomic or compound) to process.

Returns:

An isomorphic expression with new Variables.

See Also: Variable, Expression

• substBindings

   public static Object substBindings(Object x, 
                                      Bindings theBindings) 

Creates a new expression in which the values of the variables indicated in the given Bindings object are substituted into the given (compound or atomic) expression.

Note: The order of the parameters might be different than what you may be used to seeing if you are familiar with the LISP version of this function (but they are more in line with all the other methods in the Unify class).

Parameter	Description
x	An expression (atomic or compound) to process.
theBindings	The variable bindings.

Returns:

An expression where the Variable values have been substituted in place of the Variables themselves.

See Also: Bindings, Variable, Expression

• main

   public static void main(String[] args)  throws Exception

Tests out the functionality of this class.

Parameter	Description
args	Ignored.

Throws: Exception

Thrown in case of an internal parsing error.

All Packages  This Package  Class Hierarchy  Class Search  Index