Download Prolog Programming A First Course

Chapter 4
Unification, Recursion and
Lists
chapter-recursion
We describe the matching process known as Unification that
has already been met.
We review the basic idea of recursion as a programming technique.
We apply these ideas to list processing.
4.1
Unification
Unification is the name given to the way Prolog does its matching. We will
not do more than sketch the basic ideas here. Basically, an attempt can be
made to unify any pair of valid Prolog entities or terms.
Unification is more than simple matching. A naive view of the matching
process might be represented by the question “can the target object be
made to fit one of the source objects”. The implicit assumption is that the
source is not affected —only the target is coerced to make it look like some
source object.
Unification implies mutual coercion. There is an attempt to alter both the
target and the current source object to make them look the same.
Consider how we might match the term book(waverley,X) against some
clause for which book(Y, scott) is the head. The naive approach might be
that X/scott is the correct substitution —or even that the matching cannot
be done. Unification provides the substitutions X/scott and Y/waverley.
With these substitutions both terms look like book(waverley,scott).
Unification is a two way matching process
The substitution X/scott and Y/waverley is known as a unifier —to
be precise, the most general unifier. If we unify X with Y then one
unifier might be the substitution X/1 and Y/1 but this is not the most
general unifier.
Consider the infix predicate =/2.
26