CSc 520 - Principles of Programming Languages
43 : Logic Programming -- Prolog Unification

Christian Collberg

Department of Computer Science

University of Arizona

1 Unification & Matching

So far, when we've gone through examples, I have said simply that when trying to satisfy a goal, Prolog searches for a matching rule or fact.
What does this mean, to match?
Prolog's matching operator or =. It tries to make its left and right hand sides the same, by assigning values to variables.
Also, there's an implicit = between arguments when we try to match a query

to a rule

The rule:

The goal:

x ^3 + x^2 + 1 matches U + V
- x ^3 + x^2 is bound to U
- 1 is bound to V

Can two terms and be ``made identical,'' by assigning values to their variables?

Two terms and match if

they are identical atoms
one or both are uninstantiated variables
they are terms and , and
1. the arities are the same ()
2. the functors are the same ()
3. the arguments match ( )

Consequences of Prolog Matching:

An uninstantiated variable will match any object.
An integer or atom will match only itself.
When two uninstantiated variables match, they share:
- When one is instantiated, so is the other (with the same value).
Backtracking undoes all variable bindings.

From Prolog for Programmers, Kluzniak & Szpakowicz, page 18.
Assume that during the course of a program we attempt to match the goal p(X, b(X, Y)) with a clause , whose head is p(X, b(X, y)).
First we'll compare the arity and name of the functors. For both the goal and the clause they are 2 and p, respectively.

Matching1A

The second step is to try to unify the first argument of the goal (X) with the first argument of the clause head (A).
They are both variables, so that works OK.
From now on A and X will be treated as identical (they are in the list of variable substitutions ).

Matching1B

Next we try to match the second argument of the goal (b(X, Y)) with the second argument of the clause head (b(c, A)).
The arities and the functors are the same, so we go on to to try to match the arguments.
The first argument in the goal is X, which is matched by the first argument in the clause head (c). I.e., X and c are now treated as identical.

Matching1C

Finally, we match A and Y. Since A=X and X=c, this means that Y=c as well.

Matching1D

A term is either a
- a constant (an atom or integer)
- a variable
- a structure
Two terms match if
- there exists a variable substitution which makes the terms identical.
Once a variable becomes instantiated, it stays instantiated.
Backtracking undoes variable instantiations.
Prolog searches the database sequentially (from top to bottom) until a matching clause is found.

Christian Collberg 2008-04-23