One operation does the work
In most languages there are many separate mechanisms for handling data: function parameters, assignment, constructors, field access, switch or match statements, equality tests. Prolog has one mechanism that does all of these jobs, called unification. When you call a predicate, the call is unified with the head of each clause; that is parameter passing. When a clause head says date(Y, M, _), unification takes a date apart; that is field access and pattern matching. When a variable is unified with place(accra, ghana), a structure is built; that is construction. When two ground terms are unified, they are compared; that is equality.
Unification is also why Prolog predicates work in several directions. In lesson 1, capital(peru, X) and capital(X, lima) used the same facts. Nothing in the facts said which argument was the input. Unification simply made the two sides equal, filling in whichever variables needed values.
This lesson looks closely at the data Prolog works with, and at the precise rules of unification. It is short on new predicates and long on understanding, and everything else in the course rests on it.
Terms are trees
Lesson 1 listed the kinds of term: atoms, numbers, variables and compound terms. A compound term has a name, called its functor, and a fixed number of arguments, its arity; Prolog writes the pair as name/arity. The arguments can be any terms, including other compound terms, so every term is a tree:
Two kinds of term look special but are ordinary compound terms underneath:
- Operators.
1 + 2is the term+(1, 2): a tree with functor+/2. Prolog does not compute 3 when it sees it. Arithmetic happens only when you ask for it, withis/2(lesson 5). The same goes fora - b,x * y,key-valuepairs and even(A :- B): they are all trees. - Lists.
[red, green, blue]is a chain of two-argument cells ending in the empty list[]. The notation[H|T]means "a list whose first element isHand whose remaining elements form the listT". Lesson 4 is all about lists.
You can inspect any term. functor(T, Name, Arity) gives its functor, and T =.. List (pronounced "univ") converts between a term and a list of its functor and arguments, in both directions.
Definition— Unification
Two terms unify if there is a way to give values to their variables that makes them identical. Unification finds such values, the unifier, and binds the variables to them. Prolog always finds the most general unifier: the one that binds no more than it must.
The rules are few:
- An unbound variable unifies with any term, and becomes bound to it. Two unbound variables unify by becoming the same variable.
- Two atoms or two numbers unify only if they are identical.
- Two compound terms unify if they have the same functor and arity, and their arguments unify pairwise, from left to right, with all bindings made so far kept.
- Nothing else unifies: an atom never unifies with a compound term,
f/2never unifies withf/3.
Rule 3 makes unification work on whole trees at once, and its last clause, with all bindings kept, is what makes it powerful: a variable bound while unifying one argument carries its value into the next. point(A, B) = point(B, 3) first unifies A with B (they become the same variable), then B with 3, so both end up as 3.
Example— Unifying by hand
Unify pair(f(X, g(Y)), Z) with pair(f(a, W), W).
- Both are
pair/2, so unify the arguments in turn. - First arguments:
f(X, g(Y))withf(a, W). Both aref/2. ThenXwitha: bindX = a. Theng(Y)withW:Wis unbound, so bindW = g(Y). - Second arguments:
ZwithW.Wis alreadyg(Y), so bindZ = g(Y).
The most general unifier is X = a, W = g(Y), Z = g(Y), and Y stays unbound: nothing forced it to have a value, so Prolog does not invent one. Typed at the toplevel, the query gives exactly this, in SWI-Prolog's compact form:
?- pair(f(X, g(Y)), Z) = pair(f(a, W), W).
X = a,
Z = W, W = g(Y).Z = W, W = g(Y) says that Z and W are now the same variable, whose value is g(Y).
Unification at work
Unification by example
The goal X = Y asks Prolog to unify X and Y. This program tries eight unifications. Where a unification can fail, it uses ( Condition -> Then ; Else ), Prolog's if-then-else, which lesson 5 explains properly:
:- initialization(main, main).
main :-
city(X1, peru) = city(lima, Y1),
format("1. X = ~w, Y = ~w~n", [X1, Y1]),
date(2026, M2, 19) = date(Y2, 11, D2),
format("2. year ~w, month ~w, day ~w~n", [Y2, M2, D2]),
point(A3, B3) = point(B3, 3),
format("3. A = ~w, B = ~w~n", [A3, B3]),
[H4|T4] = [red, green, blue],
format("4. H = ~w, T = ~w~n", [H4, T4]),
X5 = 1 + 2,
X5 = Left + Right,
format("5. X = ~w, whose arguments are ~w and ~w~n", [X5, Left, Right]),
( f(X6, X6) = f(a, b)
-> format("6. succeeded with X = ~w~n", [X6])
; format("6. f(X, X) and f(a, b) do not unify~n")
),
( 1 + 2 = 3
-> format("7. 1 + 2 = 3 succeeded~n")
; format("7. 1 + 2 and 3 do not unify~n")
),
T8 = flight(nairobi, accra, 2026),
functor(T8, Name, Arity),
T8 =.. Parts,
format("8. functor ~w, arity ~w, parts ~w~n", [Name, Arity, Parts]).1. X = lima, Y = peru
2. year 2026, month 11, day 19
3. A = 3, B = 3
4. H = red, T = [green,blue]
5. X = 1+2, whose arguments are 1 and 2
6. f(X, X) and f(a, b) do not unify
7. 1 + 2 and 3 do not unify
8. functor flight, arity 3, parts [flight,nairobi,accra,2026]Work through each line by the rules:
- Same functor
city/2. First arguments:Xgetslima. Second arguments:Ygetsperu. Information flowed both ways in one unification. - Variables on both sides again: the left supplies the year and day, the right supplies the month.
- The chain of rule 3:
AandBbecome one variable, which then becomes 3. - A list pattern:
Hgets the first element,Tthe rest. Xis bound to the tree1+2, which can then be taken apart by unifying it withLeft + Right.- The first arguments bind
Xtoa; the second arguments then askato unify withb, which fails. The whole unification fails, and its bindings are undone. +(1, 2)is a compound term and3is a number. They are different trees.functor/3and=../2look inside a term.
Pattern matching in clause heads
Unification is most useful in the heads of rules and in queries. Here a small database of events uses nested terms, and each rule pulls out exactly the parts it needs:
:- initialization(main, main).
% event(Name, date(Year, Month, Day), place(City, Country))
event(jazz_night, date(2026, 12, 5), place(accra, ghana)).
event(book_fair, date(2026, 11, 28), place(guadalajara, mexico)).
event(film_festival, date(2027, 1, 22), place(rotterdam, netherlands)).
event(tech_summit, date(2026, 12, 14), place(lisbon, portugal)).
event(lantern_parade, date(2027, 2, 12), place(taipei, taiwan)).
% in_month(Name, Year, Month): the event Name takes place in that month.
in_month(Name, Year, Month) :-
event(Name, date(Year, Month, _), _).
% same_month(A, B): events A and B take place in the same month.
same_month(A, B) :-
event(A, date(Y, M, _), _),
event(B, date(Y, M, _), _),
A @< B.
% city_of(Name, City): ignore the country, keep the city.
city_of(Name, City) :-
event(Name, _, place(City, _)).
main :-
format("In December 2026:~n"),
forall(in_month(E, 2026, 12), format(" ~w~n", [E])),
format("Pairs in the same month:~n"),
forall(same_month(A, B), format(" ~w and ~w~n", [A, B])),
city_of(book_fair, City),
format("The book fair is in ~w.~n", [City]),
format("Events in 2027:~n"),
forall(event(E2, date(2027, _, _), place(C2, _)),
format(" ~w in ~w~n", [E2, C2])).In December 2026:
jazz_night
tech_summit
Pairs in the same month:
jazz_night and tech_summit
The book fair is in guadalajara.
Events in 2027:
film_festival in rotterdam
lantern_parade in taipeiin_monthpassesYearandMonthstraight into a pattern. Called with2026and12, unification acts as a filter; called with variables, the same rule would list every event's month.same_monthuses the same variablesYandMin two goals, so the second event must match the first one's year and month. That is a join, written without any comparison operator.A @< Bcompares terms in Prolog's standard order (for atoms, alphabetical). Without it, the rule would report each pair twice, once in each order, and pair every event with itself._, the anonymous variable, says "anything, and I don't need it". Each_is a different variable, sodate(_, _, _)matches any date.- The last query in
mainputs patterns straight into the goal: all events in 2027, with their city.
Four kinds of equality
Prolog has several predicates that look like equality and mean different things. This program reports which goals succeed:
:- initialization(main, main).
% check(Label, Goal): run Goal once and report whether it succeeded.
check(Label, Goal) :-
( call(Goal)
-> format("~w~t~34|true~n", [Label])
; format("~w~t~34|false~n", [Label])
).
main :-
check("X = a", _X1 = a),
check("X == a (X unbound)", _X2 == a),
check("X = Y, X == Y", (X3 = Y3, X3 == Y3)),
check("X == Y (both unbound)", _X4 == _Y4),
check("X \\= a (X unbound)", _X5 \= a),
check("b \\= a", b \= a),
check("dif(X, a), X = b", (dif(X6, a), X6 = b)),
check("dif(X, a), X = a", (dif(X7, a), X7 = a)),
check("X = f(X)", X8 = f(X8)),
check("unify_with_occurs_check(X, f(X))", unify_with_occurs_check(X9, f(X9))).X = a true
X == a (X unbound) false
X = Y, X == Y true
X == Y (both unbound) false
X \= a (X unbound) false
b \= a true
dif(X, a), X = b true
dif(X, a), X = a false
X = f(X) true
unify_with_occurs_check(X, f(X)) false| Predicate | Meaning |
|---|---|
A = B | Unify: make them equal, binding variables if needed |
A == B | Already identical, without binding anything. Two different unbound variables are not identical |
A \= B | Cannot be unified right now. With an unbound variable this is almost always false |
A \== B | Not identical right now |
dif(A, B) | A constraint: A and B must end up different. It waits until there is enough information to decide |
X \= a with X unbound is false because X could be a. Newcomers use \= to mean "is not equal to" and get mysterious failures; dif/2 says what they meant, and keeps meaning it however the variables are bound later. The check/2 helper itself shows two small techniques: call(Goal) runs a goal passed as data (goals are terms too), and the ~t~34| in the format string pads with spaces up to column 34.
The last two lines concern the occurs check. Should X unify with f(X)? No finite term is equal to a term containing itself, so logically the answer is no, and unify_with_occurs_check/2 says so. But checking whether a variable occurs inside the other term costs time on every unification, so Prolog systems traditionally skip it. SWI-Prolog then creates a cyclic term, f(f(f(...))) forever. In everyday programs the situation rarely arises; where soundness matters, as in theorem provers and type checkers, use unify_with_occurs_check/2, or set the flag occurs_check to true or error.
Unification beyond Prolog
Unification was not invented for Prolog. John Alan Robinson described it in 1965 as the core step of resolution, a method for automated theorem proving; Prolog's execution is a restricted, efficient form of resolution. The same algorithm appears in places you may not expect:
- Type inference. When a compiler for Haskell, OCaml, Rust or TypeScript infers that
xmust be a list of integers, it is unifying type expressions with type variables: the Hindley–Milner algorithm is unification over types. If you have ever seen an error like "cannot unifyIntwithString", that is this algorithm reporting a failure. - Pattern matching in functional languages is one-way unification: the pattern has variables, the value does not.
- Logic and query languages such as Datalog, and rule engines in configuration and security tools, match patterns against facts in exactly this way.
So the time you spend getting fluent with unification here pays off well outside Prolog.
Common misconceptions
Misconception
"= assigns a value." = unifies. It can bind a variable on either side, both sides, or neither, and it can fail. Once bound, a variable cannot be rebound in the same clause: X = 1, X = 2 simply fails.
Misconception
"X = 1 + 2 makes X equal to 3." It makes X the term 1+2. To compute, write X is 1 + 2 (lesson 5).
Misconception
"\= means not equal." It means "cannot be unified now". For a not-yet-bound variable it is false, which is rarely what you want. Use dif/2 for "must be different", or compare after the variables are bound.
Misconception
"Predicates have inputs and outputs." Many work in several modes, because unification does not care which side a value comes from. Documentation marks the intended modes with + (bound on call), - (unbound) and ? (either), as in length(?List, ?Length).
Exercises
Try each question before opening the hints. Every answer about program output was checked by running the program with SWI-Prolog 10.1.
1. Terms and unification
Warm-upComputationalAfter f(X, g(Y)) = f(a, g(X)), what is the value of Y?
2. Terms and unification
Warm-upComputationalAfter [A, B | C] = [1, 2, 3, 4], what does format("~w", [C]) print?
3. Terms and unification
CoreComputationalDoes p(X, b) = p(a, X) succeed?
4. Terms and unification
CoreComputationalWhat does this print?
P = 2 * 3, Q = P, format("~w~n", [Q])
5. Terms and unification
CoreComputationalWhat term does T =.. [point, 1, 2] bind T to? Write it as ~w would print it.
6. Terms and unification
Warm-upHumanWhat is the arity of the term event(jazz_night, date(2026, 12, 5), place(accra, ghana))?
7. Terms and unification
StretchHumanA rule is meant to find two different speakers of a language: pair(A, B) :- A \= B, speaks(A, L), speaks(B, L). It never succeeds. Why, and what is the fix?
Further reading and resources
- SWI-Prolog manual, comparison and unification of termsThe reference for =, ==, =, @< and the standard order of terms.
- SWI-Prolog manual, analysing and constructing termsfunctor/3, arg/3, =../2 and friends.
- Unification (Wikipedia)The general idea, Robinson's 1965 algorithm and its uses beyond Prolog, such as type inference.