LProlog

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Prolog in 90 minutes :

Prolog in 90 minutes Ulf Nilsson Dept of Computer and Information Science yu kwong yiu wilson

Logic programs:

Logic programs A logic program describes individuals and relations between individuals (or properties of individuals). The program is used to answer queries about the world described in the program.

Relations:

Relations Adam is a parent of Bill Paris is the capital of France 5 is greater than 2 plus 2 X times 1 is equal to X X is a subset of Y 5 is the maximum of 2 and 5 There is an edge from a to b

Properties:

Properties Adam is a parent Adam is male X plus 1 is non-zero Paris is a capital Grass is green The music was loud

Queries:

Queries Who is the father of Bill? Is there an edge from a to b? Which town is a capital ? Who is male ?

Language primitives:

Language primitives Constants adam, paris, 5, 3.14, [], ´Adam’, ... Variables X, Y, List, _12, _, ... Function symbols plus/2, +/2, f/1, ... Predicate symbols capital/2, greater/2, non_zero/1, >/2, ...

Terms:

Terms Terms represent individuals Constants Variables Compound terms E.g. paris, X, plus(2,3), plus(2,plus(3,4)) Infix notation: 2+3

Atomic formulas:

Atomic formulas Atomic formulas describe relations: If p is a predicate letter of arity n and t 1 ,...,t n are terms then p(t 1 ,...,t n ) is an atomic formula . E.g. capital(paris,france) greater(X,2) Infix notation: X > 2

Logic Programs:

Logic Programs A logic program is a set of clauses: facts rules The program is used to answer queries.

Facts:

Facts A fact is an expression of the form: A. where A is an atomic formula. Examples: edge(a, X). parent(adam, bill).

Interpretation Facts:

Interpretation Facts Consider a fact A. Declarative (logical) reading: For all values of the variables (in A), A is true. Procedural (operational) reading: A is solved.

Rules:

Rules A rule is an expression of the form: A 0 :- A 1 , ... , A n . where each A i is an atomic formula. Examples: path(X,Y) :- edge(X,Y). father(X,Y) :- parent(X,Y), male(X).

Interpretation Rules:

Interpretation Rules Consider a rule A 0 :- A 1 , ... , A n . Declarative (logical) reading: For all values of the variables in the rule, A 0 if A 1 and...and A n . Procedural (operational) reading: To solve A 0 , first solve A 1 , then A 2 etc.

Example:

Example gp(X,Y) :- p(X,Z), p(Z,Y). p(X,Y) :- f(X,Y). p(X,Y) :- m(X,Y). f(adam,bill). f(bill,carl). m(anne,bill).

Queries:

Queries A query is an expression of the form: ?- A 1 , ..., A n . where n=0,1,2,... and A 1 , ..., A n are atomic formulas. Examples: ?- father(X, bill). ?- parent(X, bill), male(X).

Interpretation Queries:

Interpretation Queries Consider a query ?- A 1 , ... , A n . Declarative (logical) reading: Are there values of the variables such that A 1 and...and A n ? Procedural (operational) reading: First solve A 1 , then A 2 etc

Ground SLD-Resolution:

Ground SLD-Resolution ?- A 1 ,A 2 ,...,A n . ?- B 1 ,...,B m ,A 2 ,...,A n . A 1 :- B 1 ,...,B m . where A 1 :- B 1 ,...,B m is an instantiated program clause.

A Derivation:

parent(X,Y) :- father(X,Y). parent(X,Y) :- mother(X,Y). father(adam,bill). mother(anne,bill). A Derivation ?- parent(adam,bill) ?- father(adam,bill) ?- true parent(X,Y) :- father(X,Y). parent(X,Y) :- mother(X,Y). father(adam,bill). mother(anne,bill). parent(X,Y) :- father(X,Y). parent(X,Y) :- mother(X,Y). father(adam,bill). mother(anne,bill).

Another Derivation:

parent(X,Y) :- father(X,Y). parent(X,Y) :- mother(X,Y). father(adam,bill). mother(anne,bill). Another Derivation ?- parent(anne,bill) ?- mother(anne,bill) ?- true parent(X,Y) :- father(X,Y). parent(X,Y) :- mother(X,Y). father(adam,bill). mother(anne,bill). parent(X,Y) :- father(X,Y). parent(X,Y) :- mother(X,Y). father(adam,bill). mother(anne,bill).

Full SLD-Resolution:

Full SLD-Resolution ?- A 1 ,A 2 ,...,A n . ?- A 1 = B 0 , B 1 ,...,B m ,A 2 ,...,A n . B 0 :- B 1 ,...,B m . where: B 0 :- B 1 ,...,B m is a renamed program clause. ?- (B 1 ,...,B m ,A 2 ,...,A n ) q . q is a solution to the equation A 1 = B 0 .

Yet Another Derivation:

?- X=X1, bill=Y1 , father(X1,Y1). ?- father(X,bill). Yet Another Derivation ?- parent(X,bill). parent(X1,Y1) :- father(X1,Y1). father(adam,bill). ?- X=adam, bill=bill . ?- true. Answer: X=adam

And Another One...:

And Another One... ?- gp(X,Y). gp(X1,Y1) :- p(X1,Z1),p(Z1,Y1). ?- X=X1, Y=Y1 , p(X1,Z1), p(Z1,Y1). ?- p(X,Z1), p(Z1,Y). p(X2,Y2) :- f(X2,Y2). ?- X=X2, Z1=Y2 , f(X2,Y2), p(Z1,Y). ?- f(X,Z1), p(Z1,Y). f(adam,bill). ?- X=adam,Z1=bill , p(Z1,Y). ?- p(bill,Y). X=adam p(X3,Y3) :- f(X3,Y3). ?- bill=X3, Y=Y3 , f(X3,Y3). ?- f(bill,Y). f(bill,carl). ?- bill=bill, Y=carl . ?- true. Y=carl

And a Failed One...:

And a Failed One... ?- gp(X,Y). gp(X1,Y1) :- p(X1,Z1),p(Z1,Y1). ?- X=X1, Y=Y1 , p(X1,Z1), p(Z1,Y1). ?- p(X,Z1), p(Z1,Y). p(X2,Y2) :- f(X2,Y2). ?- X=X2, Z1=Y2 , f(X2,Y2), p(Z1,Y). ?- f(X,Z1), p(Z1,Y). f(bill,carl). ?- X=bill,Z1=carl , p(Z1,Y). ?- p(carl,Y). X=bill p(X3,Y3) :- f(X3,Y3). ?- carl=X3, Y=Y3 , f(X3,Y3). ?- f(carl,Y). ?- fail . FAILURE!!!

SLD-Tree:

?- true. Y=carl ?- p(bill,Y). X=adam SLD-Tree ?- gp(X,Y). ?- f(bill,Y). ?- m(bill,Y). ?- fail. ?- p(X,Z), p(Z,Y). ?- f(X,Z), p(Z,Y). ?- p(carl,Y). ?- f(carl,Y). ?- m(carl,Y). ?- fail. ?- fail. ?- m(X,Z), p(Z,Y). ?- f(bill,Y). ?- m(bill,Y). ?- true. Y=carl ?- fail. ?- p(bill,Y). X=anne

Example:

Example /* or(In1, In2, Out) */ or(0, 0, 0). or(0, 1, 1). or(1, 0, 1). or(1, 1, 1). /* nand(In1, In2, Out) */ nand(X, Y, Z) :- and(X, Y, Tmp), inv(Tmp, Z). /* inv(In, Out) */ inv(0, 1). inv(1, 0). /* and(In1, In2, Out) */ and(0, 0, 0). and(0, 1, 0). and(1, 0, 0). and(1, 1, 1).

Database:

Database lecturer(Lecturer,Course) :- course(Course,_,Lecturer,_). duration(Course,Length) :- course(Course,time(_,S,F),_,_), plus(S,Length,F). teaches(Lect,Day) :- course(_, time(Day,_,_), Lect, _). occupied(Room,Day,Time) :- course(_,time(Day,S,F),_,Room), S =< Time, Time =< F. % Database course(logic, time(monday, 8, 10), dave, a12). ...

Recursion:

Recursion path(Node,Node). path(Node1,Node3) :- edge(Node1,Node2), path(Node2,Node3). edge(a,b). edge(a,c). edge(b,d). edge(c,d). edge(d,e). edge(f,g). a b c d e f g

List Notation:

a b c . [] . . c b a List Notation .(a, .(b, .(c, [])))

More On List Notation:

More On List Notation The empty list: [] A non-empty list: .(X,Y) or [X|Y] Syntactic Sugar : [b] instead of [b|[]] and .(b, []) [a,b] instead of [a|[b]] and [a|[b|[]]] [a,b|X] instead of [a|[b|X]]

List manipulation:

List manipulation list([ ]). list([X|Xs]) :- list(Xs). member(X,[X|Xs]). member(X,[Y|Ys]) :- member(X,Ys). append([ ],Ys,Ys). append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

List Manipulation:

List Manipulation % reverse(A, B) % B is A in reverse order reverse([ ],[ ]). reverse([X|Xs],Zs) :- reverse(Xs,Ys), append(Ys,[X],Zs). % Alternative version reverse(Xs,Ys) :- reverse(Xs,[ ],Ys). reverse([ ],Ys,Ys). reverse([X|Xs],Acc,Ys) :- reverse(Xs,[X|Acc],Ys).

Insertion Sort:

Insertion Sort % sort(A,B) % B is a sorted version of A sort([X|Xs],Ys) :- sort(Xs,Zs), insert(X,Zs,Ys). sort([ ],[ ]). % insert(A,B,C) % if B is a sorted list, then C is sorted % and contains all elements in B plus A insert(X,[ ],[X]). insert(X,[Y|Ys],[Y|Zs]) :- X > Y, insert(X,Ys,Zs). insert(X,[Y|Ys],[X,Y|Ys]) :- X =< Y.

Binary Trees:

Binary Trees % binary_tree(A) % A is a binary tree binary_tree(void). binary_tree(tree(Element,Left,Right)) :- binary_tree(Left), binary_tree(Right). % tree_member(A,B) % A is a node in the tree B tree_member(X,tree(X,_,_)). tree_member(X,tree(_,Left,_)) :- tree_member(X,Left). tree_member(X,tree(_,_,Right)) :- tree_member(X,Right).

Built In Predicates:

Built In Predicates setof(X, p(X), S) ~ S is the set of all X such that p(X) bagof(X, p(X), B) ~ B is the sequence of all X such that p(X) findall(X, p(X), B) B is the sequence of all X such that p(X)

Negation:

Negation Prolog contains a weak form of negation called “negation as failure”. Written: \+ p(a) A query ?- \+ p(a) succeeds if the query ?- p(a) fails finitely. Robust only when the goal contains no variables. (Use only as a test!)

Example Negation:

Example Negation on_top(X) :- \+ blocked(X). blocked(X) :- on(Y, X). on(a, b). %---------------------------- ?- on_top(a). yes b a

authorStream Live Help