Skip to content
LumenaryAcademy
Foundations 50 min

Terms and unification

Every Prolog value is a tree, and one operation, unification, matches trees with variables in both directions.

Code tested · 3AI-draftedAwaiting review by a computer scientist
MotivationH

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.

DefinitionsH

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:

event/3jazz_nightdate/3place/22026125accraghana
The term event(jazz_night, date(2026, 12, 5), place(accra, ghana)) as a tree. Inner nodes are functors with their arity; leaves are atoms and numbers.

Two kinds of term look special but are ordinary compound terms underneath:

  • Operators. 1 + 2 is 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, with is/2 (lesson 5). The same goes for a - b, x * y, key-value pairs 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 is H and whose remaining elements form the list T". 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:

  1. An unbound variable unifies with any term, and becomes bound to it. Two unbound variables unify by becoming the same variable.
  2. Two atoms or two numbers unify only if they are identical.
  3. 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.
  4. Nothing else unifies: an atom never unifies with a compound term, f/2 never unifies with f/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).

  1. Both are pair/2, so unify the arguments in turn.
  2. First arguments: f(X, g(Y)) with f(a, W). Both are f/2. Then X with a: bind X = a. Then g(Y) with W: W is unbound, so bind W = g(Y).
  3. Second arguments: Z with W. W is already g(Y), so bind Z = 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:

text
?- 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).

Worked examplesH

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:

prolog
:- 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]).
text
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:

  1. Same functor city/2. First arguments: X gets lima. Second arguments: Y gets peru. Information flowed both ways in one unification.
  2. Variables on both sides again: the left supplies the year and day, the right supplies the month.
  3. The chain of rule 3: A and B become one variable, which then becomes 3.
  4. A list pattern: H gets the first element, T the rest.
  5. X is bound to the tree 1+2, which can then be taken apart by unifying it with Left + Right.
  6. The first arguments bind X to a; the second arguments then ask a to unify with b, which fails. The whole unification fails, and its bindings are undone.
  7. +(1, 2) is a compound term and 3 is a number. They are different trees.
  8. functor/3 and =../2 look 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:

prolog
:- 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])).
text
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 taipei
  • in_month passes Year and Month straight into a pattern. Called with 2026 and 12, unification acts as a filter; called with variables, the same rule would list every event's month.
  • same_month uses the same variables Y and M in 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 @< B compares 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, so date(_, _, _) matches any date.
  • The last query in main puts 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:

prolog
:- 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))).
text
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
PredicateMeaning
A = BUnify: make them equal, binding variables if needed
A == BAlready identical, without binding anything. Two different unbound variables are not identical
A \= BCannot be unified right now. With an unbound variable this is almost always false
A \== BNot 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.

IntuitionH

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 x must 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 unify Int with String", 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 misconceptionsH

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

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-upComputational

After f(X, g(Y)) = f(a, g(X)), what is the value of Y?

2. Terms and unification

Warm-upComputational

After [A, B | C] = [1, 2, 3, 4], what does format("~w", [C]) print?

3. Terms and unification

CoreComputational

Does p(X, b) = p(a, X) succeed?

Choose one

4. Terms and unification

CoreComputational

What does this print?

P = 2 * 3, Q = P, format("~w~n", [Q])

5. Terms and unification

CoreComputational

What term does T =.. [point, 1, 2] bind T to? Write it as ~w would print it.

6. Terms and unification

Warm-upHuman

What is the arity of the term event(jazz_night, date(2026, 12, 5), place(accra, ghana))?

7. Terms and unification

StretchHuman

A 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?

Choose one

Further reading and resources