Declarative Programming
Fundamentals of Prolog
Geraint A. Wiggins
Professor of Computational Creativity
Department of Computer Science
Vrije Universiteit Brussel
What makes a good Prolog program?
I In order of decreasing importance:
I correctness & careful design
I clarity & comments
I speed
(at least for our purposes here)
Because we understand the logical meaning of logic
programs we can rely on the computer to transform
elegant but inefficient programs into ugly (but
invisible) efficient ones
What makes a bad Prolog program?
I In no particular order:
I hacking undesigned code at the terminal
I using obscure or meaningless variable and predicate
names
I not commenting code
I abusing the procedural aspects of Prolog to produce
logically meaningless code
More about Prolog clause syntax (1)
I Recall that a Prolog program is made up of predicates
. . . and a predicate is made up of clauses.
I A clause has a head and maybe a body.
I The head of a clause always takes one of two forms:
predname
predname( argument1, argument2, …)
I If the predicate is always true, there is no body, and we
finish with a full-stop (period).
More about Prolog clause syntax (2)
I If the predicate is conditional, we connect it to a body of
subgoals with the if operator, :-
I (In logic, this is ←, NOT `.)
I Each subgoal is a Prolog literal
. . . which is either
I like a head, as before; or
I a negated head, written
\+ predname
\+ predname( argument1, …)
I Note the space after the \+ operator
I We will return to \+ later
More about Prolog clause syntax (3)
I We can combine literals in Prolog clauses with the
operators
I , (comma) meaning “and” – conjunction
I ; (semicolon) meaning “or” – disjunction
You should never need to use ; in a program
because you can express disjunction via multiple
clauses. It makes Prolog compilation less effective
and your program less clear
More about Prolog clause syntax (4)
I There is also -> (minus, greater than) supposedly
meaning “implies”
You should never need to use ->, and it is best
avoided because it does not mean the same as
“logical implies”
I We can make complex expressions using brackets
( l1( a1, a2 ); l2( a3 )), l3( a1 )
l1( a1, a2 ); ( l2( a3 ), l3( a1 ))
l1( a1, a2 ); l2( a3 ), l3( a1 )
More about Prolog goal syntax
I We run a Prolog program by asking a question, or more
precisely, stating a goal
I Prolog goal syntax is the same as the syntax of the clause
body
I Literals are combined with “and”, “or”, “not” and
“implies”
Proof strategy
I Prolog solves questions by attempting to prove them
I Suppose we have consulted the following program
parent( alan, clive ).
parent( clive, dave ).
ancestor( A, B ) :- parent( A, B ).
ancestor( A, B ) :- parent( A, C ),
ancestor( C, B ).
and we ask the question
ancestor( alan, dave ).
Proof strategy
I To prove this, prolog starts at the top of the database,
and tried to find a predicate called ancestor;
I Then it looks at each clause in turn, and tries to unify its
head with the goal.
I Once unification is complete, attempt to prove the literals
in the body, in order of appearance
This is the prolog built-in proof strategy. However,
it is possible to override it – we will cover this later.
Unification
I Unification works by comparing the structure of literals:
I First compare the predicate name;
I Then, for each argument;
I If the goal argument is a variable, then make it the same
as the program argument, and unification succeeds;
I Otherwise, if the program argument is a variable, then
make it the same as the goal argument, and unification
succeeds;
I Otherwise, if both arguments are the same, unification
succeeds;
I Otherwise, unification fails
We will cover unification in more detail later
Proof Strategy (3)
Prove: ancestor( alan, dave )
Find: ancestor clause 1
Unify: A = alan, B = dave
Prove: parent( alan, dave ) FAIL
Try again:
Find: ancestor clause 2
Unify: A = alan, B = dave
Prove: parent( alan, C )
Find: parent clause 1
Unify: C = clive SUCCEED
Next goal:
Prove: ancestor( clive, dave )
Find: ancestor clause 1
Unify: A = clive, B = dave
Prove: parent( clive, dave ) SUCCEED
Answer: yes.
Summary
I In this lecture, we have covered:
I Prolog style
I More Prolog syntax
I Prolog standard proof (search) strategy