12.4 Unification

Building Parsers with Java
By Steven  John  Metsker

Table of Contents
Chapter  12.   Engines


Suppose that you would like to be able to match a structure such as:

 city(Name, Altitude) 

with a structure such as:

 city(denver, 5280) 

so that you can extract a structure's data into variables . Logic engines provide just this kind of matching in a behavior called unification. Unification lets a variable bind to a value. It also allows entire structures to bind, with all the terms in a structure binding to their counterparts in another structure. For example, if you ask the two structures here to unify, the variables Name and Altitude will unify with denver and 5280 , as the following program shows:

 package sjm.examples.engine;  import sjm.engine.*; /**  * Show two structures unifying.  */ public class ShowStructureUnification { public static void main(String args[]) {     // city(denver, 5280)     Structure denver = new Structure("denver");     Structure altitude = new Structure(new Integer(5280));     Structure city = new Structure(         "city", new Structure[]{denver, altitude});     // city(Name, Altitude)     Variable name = new Variable("Name");     Variable alt = new Variable("Altitude");     Structure vCity = new Structure(         "city",         new Term[]{name, alt});     // show the cities     System.out.println(city);     System.out.println(vCity);     // unify, and show the variables     vCity.unify(city);     System.out.println("\n    After unifying: \n");     System.out.println("Name = " + name);     System.out.println("Alt  = " + alt); } } 

Running this program prints the following:

 city(denver, 5280)  city(Name, Altitude)     After unifying: Name = denver Alt  = 5280 

The code creates the two structures city and vCity and then unifies them. The unification succeeds because the structures have the same functor and the same number of terms, and their terms are able to unify. After unification, the variables in vCity take on the values of the corresponding terms in city .

The rule for unifying structures is as follows :

  • A structure can unify with another structure if the structures have equal functors and an equal number of terms, and if these terms can unify.

When the vCity structure unifies with the city structure, it verifies that both structures have the same functor ( "city" ) and the same number of terms (two). Then it asks these terms to unify. For example, the variable Name unifies with the structure denver . The rule for unifying uninstantiated variables is as follows:

  • An uninstantiated variable unifies with a structure by taking the structure as its value.

By taking a structure as its value, a variable in a logic program acts somewhat like a variable in an assignment statement in a Java program. However, in a Java program each new assignment overwrites the previous value of a variable. Consider these Java statements:

 String x = null, y = null;  x = "denver"; x = y; 

These lines leave x with the value null . Unification differs from assignment in that, after unifying with a term, a variable uses that term in future unifications. For example, a variable X can unify with a structure denver and can then unify with another variable Y . In this second unification, X is instantiated and Y is not, so Y takes on the value of X . The following code shows this:

 package sjm.examples.engine;  import sjm.engine.*; /**  * Show a variable unifying with a structure and then  * another variable.  */ public class ShowVariableUnification2 { public static void main(String args[]) {     Variable x = new Variable("X");     Variable y = new Variable("Y");     Structure denver = new Structure("denver");     x.unify(denver);     x.unify(y);     System.out.println("X = " + x);     System.out.println("Y = " + y); } } 

This program unifies X with denver and then unifies X with Y . Running the class prints:

 X = denver  Y = denver 

When a variable has unified with a term (either a structure or another variable) and then attempts to unify with another term, the variable passes the unification request to the term to which it has instantiated.

  • An instantiated variable unifies by asking its instantiated value to unify.

In the preceding example, when X unifies with Y , X has already instantiated with denver . To attempt to unify with Y , X passes the unification request to denver so that denver unifies with Y . This has the same effect of Y unifying with denver , and so the previously uninstantiated Y takes on denver as its value.

In short, when a variable attempts to unify with a structure, if the variable is uninstantiated it takes the structure as its instantiated value. If the variable is already instantiated, it delegates the unification request to the value that it is holding.


Building Parsers with Java
Building Parsers With Javaв„ў
ISBN: 0201719622
EAN: 2147483647
Year: 2000
Pages: 169

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net