Transcript Document

Logical Programming
 Declarative programming style
 Programs are similar to specifications rather than
implementations in conventional programming languages
 A programmer declares the logical properties that describe the
problem
 The problem description is used by the logical programming
system to infer / find a solution
 Problem description is given in a logical formalism based on
first-order predicate logic, but nondeclarative features added
 Logical programs
well found mathematical model =
symbolic logic
1
Principles of logic programming
Prolog

Logical programming: R. Kowalski and A. Colmerauer, eraly 70s.
S1  S2  ... Sn  S
in FOPL  logical / declarative interpretation:
S1  S2  ... Sn logically implies S (if S1 and S2 ... and Sn are each True then S is also True)
 Associated procedural interpretation
S if S1 and S2 ... and Sn
and can be executed in a recursive PL where S is the procedure head and S1, S2, ... Sn is the
body.
 S1  S2  ... Sn  S is called a (Horn) clause in FOPL (disjunction of literals, with at
most 1 positive literal)
 Every Si and S is a predicate (true or false relation) of arity n
pred: Dn  {True, False}
 literal = a predicate or a negated predicated
 A logical program = a sequence of clauses
2








In Prolog, a clause
S1  S2  ... Sn  S
is to be written as
S :- S1 , S2 , ..., Sn .
S – head of the clause
S1 , S2 , ..., Sn – body of the clause
S :- S1 , S2 , ..., Sn . is also called a Prolog rule
If the body is empty (S is unconditionally true) then we write
S.
S. it is also called a Prolog fact.
Literal, term, functor, ground term, ground clause
Clauses are implicitly quantified universally
Variables = identifiers starting with uppercase letters
Symbolic constants = identifiers starting with lowercase letters
Numbers = string of digits
Example
has(john, a_cat).
% fact
has(john, credit).
% fact
has(john, good_history).
% fact
has (john, book(prolog, clocksin, 1981)).
% fact
has(X, a_car):- has(X, credit), has(X, good_history).
% rule
3



A logical circuit: AND-Gate
The gate is built by connecting a NAND-Gate and an Inverter_Gate.
The entire circuit is defined by the relation:
and_gate(In1, In2, Out)
based on the relations
nand_gate(In1, In2, Out)
inverter(In, Out)
rezistor(source, n1).
rezistor(source, n2).
tranzistor(n2, null, n1).
tranzistor(n3, n4, n2).
n1
tranzistor(n5, null, n4).
inverter(In, Out) :n2
tranzistor(In, null, Out),
rezistor(source, Out).
nand_gate(In1, In2, Out) :tranzistor(In1, X, Out),
tranzistor(In2, null, X),
rezistor(source, Out).
and_gate(In1, In2, Out) :nand_gate(In1, In2, X),
inverter(X, Out).
n3
n4
n5

For the query (goal)
?- and_gate(In1, In2, Out).
In1 = n3, In2= n5, Out = n1
4
Types in Prolog

Atoms = symbolic constants
atom(john)

Numbers = strings of digits
integer(34)
integer(112)
atom(book)
atomic(X) :- atom(X).
atomic(X) :- integer(X).

Variables

var(X) – succeeds if X is an uninstantiated variable
Prolog is a dynamically typed language: no type declaration is provided for variables.
The value that is bound dynamically to a variable determines the nature of the object and
thus the legality of the operations applied to it.



Lists
Functor .
.(15, .(toot, .(duck, .(donald, [ ])))
[15, toot, duck, donald]
Operator for lists |
L = [X | Y]
Equivalent to Lisp/Scheme X=car(L)
Structures
functor(arg1, .., argn)
List is a structure
book(prolog, clocksin, 1981).
see also ML
Y = cdr(L)
5
Logical programming paradigm
 Recursively specified programs
1

(see also Chapter 1 EPL)
n=0
en =
Mathematics
x * en-1(x), n > 0
 Scheme
(define e
(lambda (n x)
(if (zero? n) 1
(* x (e (- n 1) x )))))
PROLOG
e(0, _ , Res) :- Res = 1. % e(0, _ , 1).
e(N, X, Res) :- N1 is N-1,
e(N1, X, Res1),
Res is X * Res1.
 C
int e(int e, int x)
{int t = 1, i;
if (n = = 0) return 1;
else { for (i = n; i > 0; i - -) t = t * x; return t; }
6
PROLOG
LISP
member(Item, List) :- List = [Item| _ ].
member(Item, List) :List = [_ | Rest], member(Item, Rest).
(defun lisp-member (item list)
(and (consp list)
(or (eql item (first list))
(lisp-member item (rest list)))))
member(Item, [Item]).
member(Item, [_| Rest]) :member(Item, Rest).
Anonymous variables
 Recursively specified data types
(see also Section 2.2 EPL)
PROLOG
Scheme
bintree(Btree) :- leaf_node(Btree).
bintree(Btree) :- interior_node(Btree).
leaf_node(Datum) :- integer(Datum).
interior_node([Key, Left, Right]) :atom(Key),
bintree(Left),
bintree(Right).
(define-datatype bintree bintree?
(leaf-node
(datum number?))
(interior-node
(key symbol?)
(left bintree?)
(right bintree?))))
?- bintree([a, [b, 3, 5], 7]).
YES
?- bintree([a, b, c]). (bintree? (interior-node a
NO
(leaf 2) (leaf 3)))
7
 Deriving programs from BNF specifications
(see also Section 3.1 EPL)
<expression> ::= <number> |
lit-exp (datum)
<identifier> |
var-exp (id)
(<primitive> <expression>*)
primapp-exp (prim rands)
<primitive> ::= + | - | * | add1 | sub1
PROLOG
Scheme
expression(E) :- lit_exp(E).
expression(E) :- var_exp(E).
expression(E) :- primapp_exp (E).
lit_exp(Datum) :- integer(Datum).
var_exp(Id) :- atom(Id).
primapp_exp([Prim | Rands]) :primitive(Prim),
exp_list(Rands).
exp_list([]).
exp_list([First_exp | Rest_exp]) :expression(First_exp),
exp_list(Rest).
primitive(‘+’).
primitive(‘-’).
primitive(‘*’).
primitive(add1).
primitive(sub1).
(define-datatype expression expression?
(lit-exp (datum number?))
(var-exp (id symbol?))
(primapp-exp
(prim primitive?)
(rands (list-of expression?))))
(define-datatype primitive primitive?
(add-prim)
(substract-prim)
(mul-prim)
(incr-prim)
(decr-prim))
8
Deductions in logical programs
Declarative interpretation
 The declarative interpretation of a Prolog program refers to
the logical interpretation of the clauses in the program, the
result of the program being represented by all the logical
consequences of these clauses.
 The declarative interpretation of a Prolog program
determines if a goal (query) is true (may be satisfied) and, if
yes, for which variable instances.
9
 A goal G is true in a Prolog program, i.e. is a logical consequence of the
program, if and only if:
 there is a clause C in the program and
 there is a ground instance of C, I such that
 I’s head is equal to C and
 either all goals in I’s body are true or I’s body is empty (I is a fact)

In order to check these conditions, an abstract Prolog processor has to take a query as a
goal to be proven true and try to unify it with a head of a clause in the program.
 What is unification?


Substitution = a set of pairs
 = {<Xi, ti> | Xi is a variable and ti is a term, Xi  Xj
for all i, j with i  j, and Xi does not occur in tj for all i, j}
The result of applying a substitution to an expression E is denoted by (E)
(E) and is obtained by replacing every occurrence of Xi in E by ti

Two expression E1 and E2 unify if there is a substitution  such that
(E1) = (E2)
 is called the unifier of the two expressions.

Unification combines pattern matching and binding of variables.
10
 The most general unifier (MGU)  of two expressions E1 and E2 is the unifier
with the following property:
- for any other unifier  of E1 and E2 ( (E1) = (E2) ) there is a
substitution  such that (E1) = ((E1)) and (E2) = ((E2))
 Check to see why this definition is equivalent to the one in Section 8.2.1, PLC
 Example
E1 = P(a, X, Y)
E2 = P(Z, U, T)
Unifier
 = {<Z, a>, <X, b>, <Y, c>, <U, b>, <T, c>}
(E1) = (E2) = P(a, b, c)
Most general unifier
 = {<Z, a>, <X, U>, <Y, T>}
(E1) = (E2) = P(a, U, T)
 When trying to prove a goal, the Prolog processor will compute the MGU to
unify the query with the head of a clause.
11
Unification algorithm
Unify(t1, t2)  MGU or Fail



















MGU = { }
WS = {<t1, t2>}
repeat
remove a pair <x1, x2> from WS
case
x1 and x2 are two identical constants or variables: do nothing
x1 is a variable that does not occur in x2:
substitute x2 for x1 in any pair in WS and in MGU;
insert <x1, x2> in MGU;
x2 is a variable that does not occur in x1:
substitute x1 for x2 in any pair in WS and in MGU;
insert <x2, x1> in MGU;
x1 is f(y1, y2, …, yn), x2 is f(z1, z2, …, zn), f is a functor, and n  1:
insert <y1, z1>, <y2, z2>, …, <yn, zn> into WS;
else return fail;
end case
until WS = { }
return MGU
end
12
Procedural interpretation of Prolog programs
A nondeterministic interpretation algorithm
Interpret(P,G)  YES and variable bindings (in G) or NO













SG = {G};
a copy of G is used to initialize SG
repeat
remove an element E from SG
select a (renamed) clause X :- X1, X2, …, Xn from P (n = 0 for a fact)
such that <E, X> unifies with MGU 
if such a clause does not exist
then return NO
insert X1, X2, …, Xn into SG;
apply  to all elements of SG and to G
until SG = { }
if SG = { }
then return YES and / or the variable bindings in G
end
13
 The interpretation algorithm  a search algorithm
 Search tree
 To provide a deterministic implementation of the nondeterministic interpretation
algorithm we must indicate the strategy of selecting the clauses that unify
 Breadth-first, Depth-first
 Strategy
complete proof procedure
sound proof procedure
 A Prolog interpreter uses depth-first / backtracking and the order of clauses in
the database
sound but not complete, efficient
 For a given query, Prolog may find one answer (solution) or all answers
(solutions)
member(Item, [Item| _ ]).
member(Item, [ _ | Rest]) :member(Item, Rest).
?- member(b, [a, b, c]).
YES
?- member(X, [a, b, c]).
X = a;
X = b;
X = c;
NO
14
% parent(PersonX, PersonY)
% ancestor(PersonX, PersonZ)
parent(john, tom).
parent(ada, tom).
parent(ada, mary).
parent(tom, ellen).
parent(tom, mike).
parent(mike, roco).
ancestor1(X, Z) :- parent(X, Z).
ancestor1(X, Z) :- parent(X, Y), ancestor1(Y, Z).
% Change rule order:
ancestor2(X, Z) :- parent(X, Y), ancestor2(Y, Z).
ancestor2(X, Z) :- parent(X, Z).
% Change goal order in first version
ancestor3(X, Z) :- parent(X, Z).
ancestor3(X, Z) :- ancestor3(X, Y), parent(Y, Z).
% Change both rule order and goal order:
ancestor4(X, Z) :- ancestor4(X, Y), parent(Y, Z).
ancestor4(X, Z) :- parent(X,Z).
john
ada
tom
mary
ellen
mike
roco
?- ancestor1(ada, mike).
YES
?- ancestor2(ada, mike).
YES
?- ancestor3(ada, mike).
YES
?- ancestor4(ada, mike).
Infinite loop, stack overflow
?- ancestor1(mary, roco).
NO
?- ancestor2(mary, roco).
NO
?- ancestor3(mary, roco).
Infinite loop, stack overflow
15
The Lion and the Unicorn (Alice in Wonderland, Carroll Lewis)
Hypotheses:
1) The Lion lies on Monday, Tuesday and Wednesday, and tell the truth on all other days
2) The Unicorn lies on Thursday, Friday and Saturday and tell the truth on all other days
3) Today the Lion says: „Yesterday was one of the days in which I lied”
4) Today also, the Unicorn says: „Yesterday was one of the days in which I lied”
Conclusion:
What day is today?
follows(monday, tuesday).
follows(tuesday, wednesday).
follows(wednesday, thursday).
follows(thursday, friday).
follows(friday, saturday).
follows(saturday,sunday).
follows(sunday, monday).
% lie(Animal, Day) – The Animal lies on Day.
lies(lion, monday).
lies(lion, tuesday).
lies(lion, wednesday).
lies(unicorn, thursday).
lies(unicorn, friday).
lies(unicorn, saturday).
% says(Animal, Day) – The Animal says the truth on Day.
says(Animal, Today) :follows(Yesterday, Today), lies(Animal, Yesterday).
possible(Animal, Today) :says(Animal, Today), not(lies(Animal, Today)).
possible(Animal, Today) :lies(Animal, Today), not(says(Animal, Today)).
% Prepare conclusion
negation as failure
today(Today) :possible(lion, Today), possible(unicorn, Today).
% Conclusion
?- today(Today).