Updated June 30, 2023
Introduction to Unification
Unification is a concept that is linked to logic programming. Unification, as the name suggests, is a binding logic between two or more variables. The goal is to make two expressions look identical by using substitution. For simple logic, we use first-order unification, and to unify typed lambda terms, we use higher-order unification.
What is Unification?
It is used in logical programming, where the aim is to make expressions look identical to each other and to make them identical, we generally use substitution. Substitution means replacing one variable with another term.
Here are some examples:
Statement: X * Y
Substitution (x as a and y as b)
- a * Y ………. (i)
- X * b ……… (ii)
- a * b …….. (iii)
All these 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)
All these expressions are identical on substituting substitution set.
We will take some numerical simple cases where unifying two expressions is possible and not possible.
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, it is used in logic programming. So it is useful in creating logical expressions that are used in type inference, logic programming, order sorting, e -unification, etc.
1. Uses in Logic Programming
The concept, we can say, is the main idea behind the invention of logic programming. It is a binding mechanism that is a one-time assignment.
In logic programming, the condition is that two variables can only be unified if they are identical.
2. Type Inference
It 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 the substitution of ‘a’ in place of ‘P,’ it 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” or “Char.”
3. Order Sorted Unification
Sorting is very important in ordering things according to one’s choices, but writing 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 relationship between mother: and animal. The name of the mother is ‘Dessie.’ A relation can be then said by Dessie: dog. It fits better, right? But wait, a dog’s mother is also a dog, so another relation can also be built, leading to function overloading.
Here algorithm is given by Walther, which considers the intersection to be declared in the algorithm.
Condition for Unification
For a unification to be carried out successfully, the 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 expressions must be identical.
Why do We Need the Unification?
It is the most fundamental concept regarding logical programming in computer science. The algorithm plays a key role in specializing in the operation, equations, or rules of the data. For a basic understanding, if we need to combine two simple but overlapping equations or rules, we can easily combine them by performing a substitution, which is nothing but unification.
As discussed earlier, unification can be used for type inference, where we can see that substituting 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.
Conclusion
Unification is a kind of binding logic, generally substitution between two or more variables. The goal is to make two expressions look alike. In the above article, we discussed the type, where we unification, and the conditions for unification. In addition, we have explored examples where unification is possible, and unification is not possible.
Recommended Articles
This is a guide to What is Unification? Here we also discuss the introduction and uses and different examples. You may also have a look at the following articles to learn more –
