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

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