Introduction to Unification
Unification is a concept that is linked to logic programming. Unification as the name suggests is a kind of binding logic between two or more variables. The goal of unification is to make two expression look like identical by using substitution. Unification can be used for type inference, order sorting, narrowing, e-unification, etc. for simple logics we use first-order unification and to unify typed lambda terms we use higher-order unification.
What is Unification?
Unification is used in logical programming where the aim is to make expressions look identical to each other, and in order to make them identical, we generally use substitution. Substitution means replacing one variable with another term. When the unification is performed for variables representing functions, it is called as higher order unification and if unification is performed for simple variables it is called first order unification.
Here are some examples for unification:
Statement: X * Y
Substitution (x as a and y as b)
- a * Y ………. (i)
- X * b ……… (ii)
- a * b …….. (iii)
These all expressions are identical as we substitute X and Y as a and b.
Statement
F(x, g(y)) ……………….. (i)
F(a, g(h(z))) ………….. (ii)
Here substitution set will be given by:
{a/x, h(z)/y}
- F(a, g(y)) ………….. (i)
- F(a, g(h(z)) ………. (ii)
- F(x, g(h(z))) ……… (iii)
These all expression are identical on substituting substitution set.
We will take some numerical simple cases where it is possible and not possible to unify two expressions.
Example #1
f(5) ……. (i)
f(x) ……. (ii)
Substitute: {x/5}, Unification is possible.
Example #2
divide(25/x) ……….. (i)
divide(y/5) …………. (ii)
Substitute {y/25 , x/5}, Unification is possible.
Example #3
divide (25/x) ……….. (i)
divide(x/5) ………….(ii)
Substitute {x/25 , x/ 5}, Unification is not possible
Uses of Unification
As we understand unification is used in logical programming. So it is useful is creating logical expressions that are used in type inference, logic programming, order sorting, e -unification, etc.
1. Uses in Logic Programming
The concept of unification we can say is the main idea behind the invent of logic programming. Unification is a binding mechanism which is one time assignment. In logic programming, unification operation is denoted by “ = ” sign or equality sign.
4.6 (3,144 ratings)
View Course
In logic programming, the condition is that two variables can only be unified if they are identical.
2. Type Inference
Unification can be used for type inference. For example, one expression is given as True : [ ‘P’, ‘Q’, ‘R’] which is of type “Bool”. Now if we use unification substitution of ‘a’ in place of ‘P’, It also must be of the same type. That means if there is another expression that represents the same variables [ ‘P’, ‘Q’, ‘R’] but is of type “Char”. And if tried to substitute ‘a’ in place of ‘P’ type inference will not allow because ‘a’ cannot be substituted to “Bool” as well as “Char”.
3. Order Sorted Unification
Sorting is very important in ordering the things according to one’s choices, but to write logic could be difficult here. For example, we are sorting living creatures. As a sort, we can say a dog is sub sort of sort animal. Now let us say we are defining a relation mother : animal. The name of the mother is ‘Dessie’. A relation can be then said Dessie : dog. It fits better right !. But wait, mother of a dog is also a dog so another relation can also be build which leads to function overloading.
Here unification algorithm is given by Walther which considers intersection to be declared in the algorithm.
Condition for Unification
For a unification to be carried out successfully these following conditions must be satisfied:
- Arguments in the problem expression should be the same in numbers.
Ψ1 = {f (p, q), and Ψ2 = f (a, g(b))
S0 = {f (p, q), f (a, g(b))}
SUBSTITUTE = {a/p}
S1 => {f (a, q), f (a, f(b))}
SUBSTITUTE = {f(b) / q}
S2 => {f (a, f(b)), f (a, f(b))}, Unified Successfully
- In an expression there shouldn’t be two similar variables, otherwise, unification will fail.
Ψ1 = {f (a, a), and Ψ2 = f (b, g(b))
S0 = {f (a, a), f (b, f(b))}
SUBSET θ= {a/b}
S1 => {f (b, b), f (Z, f(Z))}
SUBST θ= {f(b) / b}, Unification Failed.
- The initial predicate symbol in both the expression must be identical.
Why We Need the Unification?
Unification is the most fundamental concept when it comes to logical programming in computer science. In many real time problems, we find rules or operations or equations or some patterns, which are needed to be applied to some sort of data. The unification algorithm plays key role to specialize in the operation or equations or rules to the data. For basic understanding, if there is a need to combine two simple but overlapping equations or rules, by performing substitution we can easily combine them which is nothing but unification.
For any new theorem to be used, it must be proved and checked before implementation. Higher order unification is used in proof assistance and proving Theorems. As discussed earlier, unification can be used for type inference where we can see that substitution of only the same variable type is possible not on the different type hence it removes redundancy in algorithms. Data types are significantly important in computer science for defining different variables. Unification is an inherent part of algorithms used in Artificial intelligence, Natural language programming, pattern detection, parsing algorithms, etc.
Conclusion
Unification is a basic concept which is linked to logical programming in computer science. Unification is a kind of binding logic generally substitution between two or more variables. The goal of unification is to make two expression look alike. In the above article, we discussed the type of unification, where we unification and conditions for unification. In addition to it we also have explored examples where unification is possible and where unification is not possible. And at last, we also have discussed the need of unification.
Recommended Articles
This is a guide to What is Unification?. Here we also discuss the introduction and uses of unification along with different examples. You may also have a look at the following articles to learn more –
