Unification Algorithm - Artificial intelligence:
To merge two statements, we should get a substitution which forms the two sentences similar. Remember that we write V/T to signify that we have substituted term T for variable V (read the "/" sign as "is substituted by"). The purpose of this algorithm will be to construct a substitution (a set of pairs V/T) for a provided pair of statements. So, for example, the output for the pair of statements:
Knows (john)
Knows (john, marry)
Will be: {X/mary}. However, for the two sentences on the top involving jack, the method must fail, as there was no method to unify the sentences.
To explain the algorithm, we have to specify some methods it calls internally.
- The function is a variable(x) checks whether x is a variable.
- The function is a compound(x) checks if x is a compound expression: else a predicate, a method or a connective which includes subparts. The subparts of a procedure or predicate are the arguments. The subparts of a
Connectives are the things it joins. We write rags(x) for the subparts of complex expression x. Note that args(x) outputs a list: the list of subparts. Also, we write op(x) to signify the symbol of the complex operator (predicate name, method name or connective symbol).
- The function is a list(x) checks whether x is a list. We write head(L) for the very first term in a list L and tail(L) for the sub list comprising all the another terms besides the top. Hence the top of [2,3,5,7,11] is 2 and the tail is [3,5,7,11]. This terminology is ordinary in Prolog.
It's very easy to clarify the unification algorithm as a recursive way which is capable to call itself. As this is occurring, a set, mu, is passed around the many parts of the algorithm, gathering substitutions as it goes. The method has two basic parts:
Unify internal(x, y, mu)
which returns a substitution which forms sentence x look exactly as sentence y, given an already presented set of substitutions mu (although mu may be empty). This function checks many properties of x and y and calls either itself again or the
unify variable routine, as given below. Note that the order of the if- statements is important, and if a breakdown is reported at any stage, the complete function fails. If none of the cases is right for the input, then the algorithm fails to search a unifying set of substitutions.
Unify variable (var, x, mu)
which gets back a substitution provided a variable var, a sentence x and an already present set of substitutions mu. This function also includes a set of cases which results other routines to run if the case is right of the input. Again, the order of the cases is essential. Here, if none of the cases is right of the input, a substitution is got back.
The algorithm is as follows:
unify(x,y) = unify_internal(x,y,{}) unify_internal(x,y,mu) ---------------------- Cases
1. if (mu=failure) then return failure
2. if (x=y) then return mu.
3. if (isa_variable(x)) then return unify_variable(x,y,mu)
4. if (isa_variable(y)) then return unify_variable(y,x,mu)
5. if (isa_compound(x) and isa_compound(y)) then return unify_internal(args(x),args(y),unify_internal(op(x),op(y),mu))
6. if (isa_list(x) and isa_list(y)) then return unify_internal(tail(x),tail(y),unify_internal(head(x),head(y),mu))
7. return failure
unify_variable(var,x,mu) ------------------------ Cases
1. if (a substitution var/val is in mu) then return unify_internal(val,x,mu)
2. if (a substitution x/val is in mu) then return unify_internal(var,val,mu)
3. if (var occurs anywhere in x) then return failure
4. add var/x to mu and return