prolog-unification

Unification in Prolog finds a substitution set of variable bindings that makes two terms syntactically identical. It structurally decomposes constants, variables, and compound terms, binding variables bidirectionally until the terms match or fail.

Bidirectional variable binding allows both terms to carry unbound variables that resolve during solving. The unification process creates write-once aliases and transitively resolves substitutions until both terms become identical.

The occurs check prevents infinite terms by verifying a variable does not appear within the term it binds to. Enable it during constraint solving when logically sound substitutions are required, accepting the performance tradeoff.

Unifying f(X, g(Y, a)) with f(h(Z), g(b, Z)) matches compound structures recursively. The resulting substitution binds X to h(Z) and Y to b, resolving Z transitively to produce a consistent binding environment.

The Martelli-Montanari algorithm provides backtracking-ready solutions through write-once substitution environments with rollback semantics. If unification fails, the environment rolls back previous bindings to explore alternative matching paths.