Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 40 ยท Unification and Backtracking

Prolog Unification: How Terms Match

Understand unification, the pattern matching at the heart of Prolog: the rules for atoms, variables and compound terms, worked examples, lists, failure and the = operator.

Every time Prolog calls a predicate, matches a fact, or evaluates =, it performs unification. It is the single most important mechanism in the language. It combines the work of assignment, pattern matching, argument passing and construction of data. Once you understand unification you understand how Prolog finds answers.

Prolog is read-only on this site. The Python stand-in contains a real unification algorithm (the function unify), so you can run the examples below and see the substitutions it computes.

The idea

Two terms unify if there is a way to give values to their variables that makes the two terms identical. The values chosen form a substitution. The operator = asks Prolog to unify its two sides:

PROLOG
?- f(X, b) = f(a, Y).
X = a,
Y = b.

Prolog made the two terms equal by choosing X = a and Y = b: after substitution both are f(a, b). It works in both directions at once: information from the left side flows to the right side and back. No operation in a conventional language does the same.

The rules

Two terms A and B unify according to the first rule that applies:

  1. If A is an unbound variable, bind it to B (and likewise if B is a variable). Two unbound variables become aliases: they are now the same variable.
  2. If both are atoms or numbers, they unify only if they are identical. a = a succeeds. a = b fails. 1 = 1 succeeds. 1 = 1.0 fails, because an integer and a float are different terms.
  3. If both are compound terms, they unify if they have the same functor and arity and their arguments unify, pairwise, from left to right.
  4. Otherwise, unification fails.

Examples:

PROLOG
?- a = a.                      % true
?- a = b.                      % false
?- X = tom.                    % X = tom
?- f(a, b) = f(a, b).          % true
?- f(a, b) = f(a, c).          % false: b and c differ
?- f(a) = f(a, b).             % false: different arity
?- f(X, X) = f(a, b).          % false: X cannot be both a and b
?- f(X, Y) = f(Y, a).          % X = Y = a (the two variables are linked)
?- point(X, 2) = point(1, Y).  % X = 1, Y = 2

The f(X, X) example matters most: a variable that occurs twice must receive one value. Once X is bound to a by the first argument, the second argument asks whether a = b, which fails.

Unification is not assignment

In other languages X = 5 stores 5 in a memory location, and X = 6 later overwrites it. In Prolog:

  • A variable starts unbound. Unification can bind it once.
  • Once bound, it behaves exactly like its value for the rest of that proof branch.
  • You cannot "change" a bound variable; trying to do so is another unification, which succeeds if the values match and fails otherwise.
PROLOG
?- X = 5, X = 6.
false.

?- X = 5, X = 5.
X = 5.

?- X = 5, Y = X.
X = 5,
Y = 5.

When Prolog backtracks it undoes the bindings made since the choice point; that is how a variable can take a different value in another branch of the search.

This is why code such as X = X + 1 does not increment. It asks for X to be unified with a compound term X+1 that contains X itself. In standard Prolog (and in SWI-Prolog by default) the system creates a cyclic term and does not report an error, so the "answer" is a weird infinite structure. Use is for arithmetic: Y is X + 1.

Unification with lists

Lists are compound terms, so they unify the same way. The notation [Head | Tail] makes the first element and the rest of the list into variables:

PROLOG
?- [H | T] = [1, 2, 3].
H = 1,
T = [2, 3].

?- [A, B | Rest] = [x, y, z, w].
A = x,
B = y,
Rest = [z, w].

?- [H | T] = [].
false.

?- [X, Y] = [1, 2, 3].
false.

The last two fail because an empty list has no head and a two-element pattern cannot match a three-element list. You will use this heavily in lists.

Unification in clause heads

Calling a predicate is unification between the goal and the head of a clause. Take:

PROLOG
parent(tom, bob).

and the goal parent(tom, X). Prolog unifies the goal with the head: the first arguments match (tom = tom), and X = bob. If you define:

PROLOG
first([H | _], H).

then ?- first([a, b, c], X). unifies [a, b, c] with [H | _] (so H = a) and then X with H: X = a. A clause head is a pattern, and the matching also takes the structure apart. The same predicate used in reverse, first(L, a), builds a list with a at the front: L = [a|_].

Unification builds data

Unifying with an unbound variable constructs structure. In the query

PROLOG
?- Person = person(name(ann), age(30)), Person = person(name(N), _).
Person = person(name(ann), age(30)),
N = ann.

the first = builds a term and the second takes it apart. Prolog programs often pass half-filled structures around and let later goals fill the holes.

Try it

The mini-Prolog stand-in includes the same algorithm. The helper u below parses two terms in one variable scope, unifies them and prints the substitution or false.

Python Unifying pairs of terms (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You can see how a failing example fails: f(X, X) against f(a, b) binds X to a and then fails on a against b. The next block shows that the order of unification steps does not change the result, and shows backtracking undoing a binding: member-style choice with a database of three facts.

Python Bindings are undone on backtracking (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each iteration gives X a different value, because each solution comes from a separate substitution; none of them modifies the others.

Special unification operators

Goal Meaning
A = B unify A and B
A \= B succeeds if A and B do not unify
A == B succeeds if the terms are identical (no binding)
unify_with_occurs_check(A, B) unify but refuse cyclic results

The difference between = and == is the subject of the next lesson.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does f(X, Y) = f(1, 2) do?

    Compound terms with the same functor and arity unify argument by argument.
  2. 2. Why does f(X, X) = f(a, b) fail?

    Once X is bound to a, the second argument asks whether a unifies with b, which fails.
  3. 3. What is H after [H | T] = [5, 6, 7]?

    H is the head (first element) and T = [6, 7] is the tail.
  4. 4. Does 1 unify with 1.0?

    Unification is structural identity after substitution. Use =:= to compare numbers by value.
  5. 5. What happens to bindings when Prolog backtracks?

    Backtracking restores the state at the last choice point, so variables are free to take new values.

Summary

  • Unification makes two terms identical by choosing values for variables.
  • Variables bind to anything; atoms and numbers must be identical; compounds need the same functor, arity and unifying arguments.
  • It is bidirectional, builds and takes apart structures, and replaces assignment and argument passing.
  • A bound variable cannot be changed; backtracking undoes bindings.
  • Use is for arithmetic, = only for matching.

Next: Term Comparison and Equality