Declarative Programming
Terms, Lists & Unification
Geraint A. Wiggins
Professor of Computational Creativity
Department of Computer Science
Vrije Universiteit Brussel
Terms
I So far, we have only encountered predicates which talk
about simple values, called atomic constants e.g.,
jane
a
1
simple term
I When we want to represent complicated, structured
knowledge, this is rather limited
I Therefore, we are also allowed to use more general
structures called terms
Terms (2)
I A term is like a literal ie
I it has a functor – a Prolog atom;
I and maybe some arguments, each of which can be a
term, or a variable
I Examples of terms:
simple term
dog(bonzo)
fat(X)
lots(a,2,D,f(X,g))
’a string’( ’EVEN capitals!’ )
I These are not terms:
2(x)
X(2)
Terms (3)
I The difference between literals and terms is
I literals form individual goals to which a truth value can
be assigned;
I terms are values in themselves and do not have a truth
value.
I You can tell the difference by where they are found:
I literals appear as the outermost structure in heads and
bodies of clauses, and in goals, e.g.,
literal( term in literal( term in term ) ).
?- lit1( t in lit1 ), lit2( t in lit2 ).
I terms appear as arguments to literals, e.g.,
?- literal( functor( arg1, arg2 ) ).
X = 2.
Terms (4)
I We sometimes think of terms as tree structures
(Trees in computer science grow downwards!)
I So the term functor( arg1, arg2 ) might be thought
of as
functor
arg1 arg2
J
J
J
J
JJ
I and literal( atom, func( 1, 2 )) as
literal
atom func
J
J
J
J
1 2
�
�
��
A
A
AA
Terms (5)
I Examples of terms:
% person( Name, Age, EyeCol, HairCol )
person( george, 35, brown, fair ).
animal( type = dog,
name = bonzo,
hairyness = very ).
I While terms are helpful in making the language more
flexible, they are still not completely so – the number of
arguments is fixed
I What happens if we want to represent a variable number
of things in one place?
Lists
I There is a special kind of term, called a list.
I It can be represented in 2 ways – the internal
representation or the syntactic sugar
I The internal representation uses 2 symbols:
. (dot – a functor)
[] (empty list – an atom)
I . connects a term (on the left) with a list (on the right)
I NB this is not symmetrical
I The last list to be connected to any list is []
Lists (2)
I Examples:
[]
.(a,[])
.(1,.(2,[]))
.(.(a,[]),.(.(b,.(c,[])),[]))
I However, this is not an easy notation
I Instead of . , we write
[A|B]
where A is the term (head) and B is the list (tail)
I The same examples:
[]
[a|[]]
[1|[2|[]]]
[[a|[]]|[[b|[c|[]]]]]
Lists (3)
I This is still not easy to read
I So we introduce simpler forms:
[A] [A|[]]
[A,B] [A|[B|[]]]
[A,B|C] [A|[B|C]]
I Now our examples read:
[]
[a]
[1,2]
[[a],[b,c]]
which is much better!
Lists (4)
I The different forms of list are all interchangeable, so
?- [a,b,c] = .(a,.(b,.(c,[])))
true
?- [1,2] = [1|[2|[]]]
true
I Lists are important because
I they enable us to deal with collections of items
I they enable us to control recursive programs
Unification
I Now that we have terms, our original idea of unification is
not adequate
I We need to be able to deal with more complex structures,
e.g.,
person(Name,Age) = person(george,65)
functor( X, a ) = functor( Y, Y )
[a,f(X,Y)] = [A|[f(A,B)]]
I We can think of unification as matching trees:
functor
X a
J
J
J
J
JJ
functor
Y Y
J
J
J
J
JJ
First-order Term Unification in Prolog
I To unify two terms
1. Compare their functors; if they do not match, then fail;
otherwise. . .
2. if the terms have different numbers of arguments, then
fail; otherwise. . . ∗
3. if the terms have no arguments then succeed;
otherwise. . .
4. for each pair of respective arguments
4.1 if one is a variable, let it be identical to the other;
otherwise. . .
4.2 unify the two arguments using this procedure
(∗ This is an efficiency measure in some systems)
I A more formal version of this algorithm is given in
“Foundations of Logic Programming”
(John W. Lloyd, 1987, publ. Springer-Verlag)
First-order Term Unification (2)
I It is important to understand that this algorithm is an
approximation
I In one particular situation, it is unsound – ie logically
incorrect
I That situation is when a variable is unified with a term
strictly containing itself e.g.,
X = f(X)
g(X) = g(p(X,Y))
I In principle, we can test for this (the occurs check) but in
practice doing so is too slow
I So we ignore it on the basis that such expressions are
meaningless anyway and should never arise