Finding a consistent substitution
A substitution replaces a variable consistently throughout the relevant terms. For example, f(X, a) and f(b, Y) become equal with X = b and Y = a; different occurrences cannot choose incompatible replacements.
For finite first-order terms, a most general unifier preserves unconstrained freedom, allowing other solutions through further instantiation rather than arbitrarily choosing one concrete value.
References: [1]
Decomposition and propagation
Type inference can decompose equality between function types into equalities for argument and result types. A discovered substitution must propagate through remaining constraints until they are solved or conflict.
Incompatible basic types or mismatched constructors cannot be unified by similarity. Solving these equations is a specific task, not a universal inference procedure for every richer type system.
References: [1]
Finite terms and cyclic terms
X = f(X) has no finite first-order term solution. An occurs check rejects binding a variable to a term already containing it, rather than silently introducing an infinite structure.
SWI-Prolog distinguishes checked unification from default behavior that can construct rational trees. Its checked operation prevents creating such cycles, with documented limits concerning pre-existing cycles; implementations must not be assumed semantically identical.
References: [2]