CS计算机代考程序代写 prolog flex algorithm Declarative Programming

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