How can I implement the unification algorithm in a language like Java or C#?

Question

I'm working through my AI textbook I got and I've come to the last homework problem for my section:

"Implement the Unification Algorithm outlined on page 69 in any language of your choice."

On page 69, you have the following pseudo-code for the unification algorithm:

function unify(E1, E2);
    begin
        case
            both E1 and E2 are constants or the empty list:
                if E1 = E2 then return {}
                else return FAIL;
            E1 is a variable:
                if E1 occurs in E2 then return FAIL
                 else return {E2/E1}
            E2 is a variable
                if E2 occurs in E1 then FAIL
                    else return {E1/E2}
            either E1 or E2 are empty then return FAIL
            otherwise:
                begin
                    HE1 := first element of E1;
                    HE2 := first element of E2;
                    SUBS1 := unify(HE1, HE2);
                    if SUBS1 := FAIL then return FAIL;
                    TE1 := apply(SUBS1, rest of E1);
                    TE2 := apply(SUBS1, rest of E2);
                    SUBS2 := unify(TE1, TE2);
                    if SUBS2 = FAIL then return FAIL;
                         else return composition(SUBS1, SUBS2)
                end
            end
        end

Now, I understand the general concept of unification but I have absolutely no idea how I would even begin to implement this in a language like Java or C#.

I'm not even sure what the method signature would look like. What type of variables would it take? I'm fairly certain I need to return lists to represent predicate calculus constructs but that is a guess.

For example, when it says "E1 is a variable", well, if I'm passing it into the Unify method, how could it be anything but? I could check for null but would that be different than "empty list"?

Can anyone help me or point me in the right direction for implementing the Unificaiton algorithm in C# or Java?

Answer 1

The best way to represent type variants is with inheritance. For example, a sequence of expressions is still just an expression. An empty list would be represented by a zero length container in the sequence object. Returning null is therefore acceptable for failure, which I indicate with '?'. I'm not sure if C# actually has a '?', but should get the drift.

abstract class Expression { ... }
class Atom : Expression { ... }
class Variable : Expression { ... }
class Sequence : Expression { List <Expression> ... }

Expression? unify (Expression e1, Expression e2) { ... }

EDIT: The list is covariant. See here. My Vala dialect of C# supports this (for now), but I don't believe .net does.

Answer 2

The variables you will use when implementing the algorithm are perhaps what you could call metavariables. They are variables in your program that describe a variable (or constant, or list, etc) in some other program. As such you need to use a variable that tells you the type of the object (eg. variable, constant) and the value of the object. You can do this via inheritance as Samuel Danielson has suggested, or via some sort of Variant object if your language provides one, or a hand-rolled variant class that can describe any type of variable (eg. via an enum describing the type and a variety of typed fields, of which only one is valid, dependent on the type).

Answer 3

The "... is a variable" means to check the type of the variable. If the type of E1 is a variable value (i.e. not of the type list and not a constant value), then do something.