Introduction to Prolog
Jean G. Vaucher Incognito Universit de Montral January 1987
PROLOG
A programming language based on the formalism and the concepts of formal logic.
PROgrammation LOGique Robinson Kowalski (resolution) (Logic Programming) ( PROLOG ) (Quintus)
Colmerauer & Roussel Warren I.C.O.T. 5th Generation DEC-10
PSI Engine
Jean G Vaucher
2/18/03
Declarative programming +Concise Notation +Programming by specification +Constraints +DB Programming Facts and Rules
Jean G Vaucher
2/18/03
LOGIC PROGRAMMING BASICS
Terms
relationship between objects loves (peter,jane)
Variables & functional expressions
loves (X, mother(jane))
STATEMENTS
<head> :- <body> .
RULES bird(B) :- flies(B), lays_eggs(B). FACTS (no body )
flies (sparrow). QUERY (no head )
:- loves(X,peter) , girl(X). 1) Prove that there is someone who loves Peter and is a girl 2) Find values of X so that the terms in the query match facts in the database
Jean G Vaucher
2/18/03
Facts
parent (john, robert) . relationship (predicate) : parent objects: John, Robert
John is a parent of Robert
interpretation
A parent of John is Robert. ? ? ?
Arity 2 1 3 0 parent (john, robert) . man ( john ) . loves ( graham , simula , madly ) . hot .
Relational programming
Jean G Vaucher
2/18/03
Program
Set of Facts Database
likes likes likes likes likes
( fred , susan) . ( mary , fred) . ( fred , beer ) . ( susan , fred ) . ( jack , mary) .
man (jack) . man (fred) . woman (susan). woman (mary). drink (beer) .
Jean G Vaucher
2/18/03
Queries
Is fred a man ?
:- man (fred) . => ok
==> Is man(fred) TRUE ? ==> Is the fact man(fred) in the database ?
Goal to be proved
Does Fred like Mary ?
:- likes (fred , mary ) . => no
Conjunction of goals
:- likes ( fred , beer ) , man ( fred ) . => ok
Jean G Vaucher
2/18/03
Variables
An unspecified individual Denoted by initial Capital letter
Who likes Mary ? ==> Is there an X such likes( X ,mary) can be found in the DB ?
:- likes ( X , mary ) . => X = jack Multiple answers
What does Fred like ?
:- likes ( fred , T ) . => T = susan ; T = beer
What girls does Fred like ?
:- likes ( fred , G ) , woman (G) . => G = susan
Jean G Vaucher
2/18/03
PERT Example
2 1 1 2 3 3
4 5 5 7
4 8 7 9 6 6 10
Prolog description arc ( Id, start-node, end-node, duration, resource) arc (1,n1,n2,1,r1). arc (2,n1,n3,4,r2). arc (3,n2,n3,2,r3). arc (4,n2,n4,3,r1). arc (5,n2,n5,1,r2). arc (6,n3,n6,4,r3). arc (7,n5,n4,2,r1). arc (8,n4,n7,3,r2). arc (9,n5,n6,1,r3). arc(10,n6,n7,4,r1).
Jean G Vaucher
2/18/03
10
DATABASE PROGRAMMING
arc (1,n1,n2,1,r1). arc (2,n1,n3,4,r2). arc (3,n2,n3,2,r3). arc (4,n2,n4,3,r1). arc (5,n2,n5,1,r2). arc (6,n3,n6,4,r3). arc (7,n5,n4,2,r1). arc (8,n4,n7,3,r2). arc (9,n5,n6,1,r3). arc(10,n6,n7,4,r1). arc ( Id, start-node, end-node, duration, resource)
:- arc(4,n2,n4,_,_). => OK :- arc(6,_,_,D,R). => D=4, R=r3 %
% Does arc4 link nodes 2 and 4 ? % What is the duration of activity 6 and what resource does it use ?
Does activity 7 follows directly activity 5. :- arc(5,_,N,_,_), arc(7,N,_,_,_). => N=5 % Yes, they meet at node 5. :- arc(A,n5,_,_,_). => A=7 A=9 % What activities start at node 5 ?
Jean G Vaucher
2/18/03
11
PROLOG's Algorithm
:- term1, term2, . . . , termn .
equivalent to
for_all DB matches for term1 do for_all DB matches for term2 do . . . . for_all DB matches for termn do PRINT VALUES OF VARIABLES ( and optionally stop );
BACKTRACKING
When a term fails, Prolog uses another match for the previous term and tries again.
Jean G Vaucher
2/18/03
12
Example
likes likes likes likes likes ( ( ( ( ( mary , fred) . fred , susan) . fred , beer ) . susan , fred ) . jack , mary) .
woman (susan). woman (mary).
:- likes ( fred,G) , woman (G) .
likes ( mary , fred) likes ( fred , susan) => w o m a n ( s u s a n ) woman (susan) woman (mary).
likes ( fred , beer ) => woman(beer)
==>
G=susan
likes ( susan , fred ) . likes ( jack , mary) .
woman (susan). woman (mary).
Jean G Vaucher
2/18/03
13
Rules
Example: bird (B) :- flies (B) , lays_eggs (B) . <head> :- <tail> 1) Head is true IF tail is true 2) To prove Head , try to prove tail Examples: friends (A,B) :- likes (A,B) , likes (B,A). person (P) :- woman (P) . person (P) :- man (P) . likes (M, mary) :- man (M) .
Jean G Vaucher
2/18/03
14
likes likes likes likes likes
( ( ( ( (
mary , fred) . fred , susan) . fred , beer ) . susan , fred ) . jack , mary) . (susan). (mary).
woman woman
:- friends (susan , F) . => F = fred :- likes (F , mary) . => F = jack ; F = fred ; F = jack
:- person (X) . => X = susan ; X = mary ; X = jack; X = fred
Jean G Vaucher
2/18/03
15
Unification
Find constraints on variables so t become identical
hat 2 terms
likes ( fred , X )
likes ( Y , eva )
Y = fred X = eva likes ( fred , eva )
1 pred (X, fonct (X,Y)) <==> pred (fred, fonct (Z,Z))
pred
pred
fonct
fred Z
fonct
Z X = fred X=Z Z=Y
pred ( fred , fonct ( fred , fred)
Jean G Vaucher
2/18/03
16
Operators
Infix Notation 1+2 '+'(1,2) Unary & Binary operators op( 500 , yfx , + ) .
- Priority , arity, associativity
Useful Operators
arithmetic:
+ - * / is := > < =:=
evaluable predicates
comparison:
Arithmetic :- X is 4 + 5 , Y is ( X - 1 ) * 2 , 2 is 3-1. X=9 Y = 16
Jean G Vaucher
2/18/03
17
"=" Equality ?
Unification operator op ( 700 , xfx , = ) . = ( X , X) . :- f(1) = f(X) , =(Var,123) . X=1 Var = 123 :- X = 1 + 3 , Y is 1 + 3 . X=1+3 Y=4 A=1 :- 4 = 1 + 3 . no. :- f (X , g( X , Y)) = f (123 , g( Z , Z )) . X = 123 Y = 123 Z = 123 :- A + 1 = red + 1 . A = red
Jean G Vaucher
2/18/03
18
== = is
:- X = 1 + 2 . X=1+2 :- X == 1 + 2 . no :- X is 1 + 2 . X=3 :- X = 1 , f ( 1 ) == f ( X ) . X=1 :- X is f ( 1 , 2 ) . no or error
Jean G Vaucher
2/18/03
19
Inequality
Not_unifiable Not Equal Not Identical :- joe \= fred. ok :- X \= 123 . no :- 1 + 2 =:= 3 . no :- 1 + 2 \== 3 . ok :- 1 + 2 \= 3 . ok :- 1 + 2 \= X . no
\= =:= \==
Jean G Vaucher
2/18/03
20
Complex Unification
(Zaniolo,,C. 1984 Object-oriented programming in Prolog)
area( rect( H , W ) ,A) :- A is H * W . area( square (Side) , A) :- area( rect(Side,Side), A) . area( triang (Side) , A) :- A is (H * W) / 2 . :- X = square(10) , area(X,Z) , write(area=Z) . area=100 ok
selection of rule parameter passing - values in / out Note use of = to combine terms
Jean G Vaucher
2/18/03
21
Input / Output
Prolog Terms read (X) write nl Characters get (C) get0 (C) put (C) Primitive but can be extended M-Prolog, Prolog II primitives read_record(Str) read_token(Token) in-sentence(Sent,_) (X)
Prolog syntax delimited by period
Jean G Vaucher
2/18/03
22
:-
write('Input: ') , read(I), I2 is I+1, write(I2), nl .
Input: 123 . 124 ok
Jean G Vaucher
2/18/03
23
Consulting and querying
DataBase male(fred). male(toto). boolean(0). boolean(1). ..... Rules & facts
Consulting file
Consult(f) male(fred) Answers Ed Window
Queries :- male(X). :X=fred; X=toto
male(fred). male(toto). boolean(0).
Jean G Vaucher
2/18/03
24
Assert & Retract
To update the database during execution :- male(X). X = fred ; X = toto :- assert( male(john) ). :- male(X). X = fred ; X = toto ; X = john :- retract( male(toto) ). :- male(X). X = fred ; X = john
Asserta & assertz
Jean G Vaucher
2/18/03
25
Assignment
Pascal Var x; x := 5; writeln (x); x := x+1; Prolog assert( value_of( x,5 ) ), value_of( x,X ), writeln( X ), retract( value_of( x,OldX )) , NewX is OldX+1, assert( value_of( x,NewX ) ).
Jean G Vaucher
2/18/03
26
List Processing
Jean G Vaucher
2/18/03
27
List Processing
Lists: Dynamic data structures Trees Graphs (1234) nil ( 1 ((2) 3) 4 )
LISP:
1) special symbol for empty list: nil or [] 2) binary nodes: "|" or "." Left = first Right = rest of list PROLOG:
[1,2,3,4]
1 2 3 4 [] 2/18/03
Jean G Vaucher
28
List Processing
Accessing elements Building lists [ 1,2,3,4 ] = [ X|Y ]
[1,2,3,4]
[X|Y]
1 2 3 4 []
=> X =1 , Y = [ 2,3,4 ] :- [1,2,3 ] = [_,A| B] . A = 2 , B =[3]
Jean G Vaucher
2/18/03
29
Procedures for Lists
first (E,L)
E is the first element of the list L
first ( X , [X|_] ) . :- first ( C , [red,white,blue] ) . C = red last (E,L)
E is the last element of the list L
last( X , [X] ) . last( X , [_| Rest] ) :- last( X , Rest ) . :- last ( C , [red,white,blue] ) . C = blue member( E,L )
E is a member of the list L
member ( X , [X|_] ) . member ( X , [_| Rest] ) :- member( X , Rest ) . :- member( red , [red,white,blue] ). ok
Jean G Vaucher
2/18/03
30
Using the Rules
member( E,L ) member ( X , [X|_] ) . member ( X , [_| Rest] ) :- member( X , Rest ) . Generator :- member( X , [red,white,blue] ). X = red ; member( X , [white,blue]) X = white ; member( X , [blue]) X = blue Constraints :- L = [_,_,_] , member( fred,L ), member (3,L), last(zzz,L) . L = [fred,3,zzz] ; L = [3,fred,zzz]
Jean G Vaucher
2/18/03
31
Logic Black Holes
infinite loops after a few good answers generators of elements of infinite set -i.e. lists Example :- member( 1 ,L ) , L = [X,X] . L = [1,1] ; L = [1,1] ; ..... infinite loop ...
The first term generates all lists of which "1" is a member:
[1], [1,..], [,1], [,1,..], [,,1], [,,,1]... etc ...
Only two are acceptable, but the generator keeps providing candidates for the second term to reject.
Jean G Vaucher
2/18/03
32
APPEND Prototypical Example of DECLARATIVE PROGRAMMING
Procedure with multiple uses
Jean G Vaucher
2/18/03
33
APPEND
append (L1, L2, L3)
L3 is the result of concatenating L1 and L2
append( [], L, L). append( [X|Xs], L2, [X|L3] ):- append( Xs,L2,L3) . Checking append( [1,2] , [3] , [1,2,3] ). | append( [2] , [3] , [2,3] ). | append( [] , [3] , [3] ). |
Proved by rule 1 by rule 2 by rule 2
Jean G Vaucher
2/18/03
34
APPEND
append( [], L, L). append( [X|Xs], L2, [X|L3] ):- append( Xs,L2,L3) .
Concatenating lists :- append( [a,b] , [c,d] , L) . L = [a,b,c,d]
Spliting lists :- append(L1,L2 , [a,b,c] ). L1 = [] , L2 = [a,b,c] ; L1 = [a] , L2 = [b,c] ; L1 = [a,b] , L2 = [c] ; L1 = [a,b,c] , L2 = []
Jean G Vaucher
2/18/03
35
APPEND
prefix( P,L ):
L.
P is a list of elements which prefix list
prefix( P,L ) :- append( P, _ , L). Sublist( S,L):
S is a sublist of L
sublist( S,L ) :- prefix( P, L), append(_, S , P) . Nave Reverse reverse( [],[] ). reverse( [X|Xs], Zs ) :reverse( Xs,Ys), append( Ys, [X], Zs) .
Jean G Vaucher
2/18/03
36
Permutations
insert( E, L, L2 ):
The list L2 is obtained by inserting E into the list L.
insert( E , [] , [E] ). insert( E , [F|R] , [F|Rx] ) :- insert( E,R,Rx ). permute (L, Lp):
The list Lp is a permutation of L
permute( [],[] ). permute( [E|R], Lp) :permute( R,Rp) , insert( E,Rp ). :- permute( [ i, die, broke] , P ), writeln(P),fail. [i, die, broke] [die, i, broke] [die, broke, i] [i, broke, die] [broke, i, die] [broke, die, i]
Jean G Vaucher
2/18/03
37
CUT
Stops the combinatorial backtracking
:- term1, term2,
. . . termn.
etc...
for all term1 do for all term2 do .... Examples:
max( A,B, M) :- A > B , M=A. max( A,B, M) :- B>=A , M=B. ... , max(10,1,M), print(M), fail ... M=10 M=1
or
digit(0). digit(1). ...
digit(9).
..., read(X), digit(X), ... fail ....
Jean G Vaucher
2/18/03
38
CUT
(2)
or
within a clause prevents backtrack to goals to its left prevents use alternative clauses
CUT
f(...) :- .... ... . f(...) :- .... , ... , ! , ... . f(...) :- .... ... . f(...) :- .... ... .
max(M, B, M) :- M<B, ! . max(_, M, M) . % else one_of( P ) :- P , ! . :- ... read(D) , one_of(digit(D)) , ...
Jean G Vaucher
2/18/03
39
Prolog and Logic Programming
Prolog is not Logic (programming) Limited use of rules Problems with negative facts disjunctive conclusions
Modus ponens
( A -> B ) & A =>
Modus tolens
( A -> B ) & B
=>
Example: 1) Professors are poor 2) Paul is a professor 3) Peter is rich (not poor) ==>> Paul is poor Peter is not a professor 4) Professors are devoted or crazy
(!!) (!!) (!!)
Jean G Vaucher
2/18/03
40
Implementations
Edinburgh Prologs
DEC-10, C-Prolog Quintus (speed champ ?) BIM Arity / AI Systems / Chalcedony M-Prolog Industrial strength
(MAC / PC)
Others
Prolog II (Apple II, VAX, MAC) - different syntax - dif - freeze Micro Prolog (LPA) early robust & fast Z80 -> IBM -> MAC Borland's Turbo-Prolog (Type declarations)
Parallelism & Object-Orientation
- Concurrent Prolog - IC-Prolog, ParLog - T-Prolog - LOGLISP - Smalltalk V - POOPS, SIMPOOPS parallelism
Multiple languages Objects
Jean G Vaucher
2/18/03
41
SIM P
ulation rolog
bject
O P
riented rogramming
ystem
Natural integration Process Oriented Structure of SIMULA Knowledge manipulation of PROLOG Parallelism and Time
Implementation
450 lines of Prolog built-in compiler
Jean G Vaucher
2/18/03
42
Single Server Queue
class client (id); methods seize(R) :- wait(R,1). release(R) :- send(R,1). begin uniform(0,10,Ta), hold(Ta), id(N), Nx is N+1, new_process (client, [id(Nx)] ), write(N), writeln(" Waiting"), seize (res), write(N), writeln(" Entering resource"), uniform(0,8,Ts), hold(Ts), release (res), write(N), writeln (" Leaving system"). end begin send(res,1), new_process( client, [id(1)] ), hold (20), writeln("Closing down system"), terminate. end.
Jean G Vaucher
2/18/03
43
Compiler Output
CLASSES class(client) class(main) CLASS PREDICATES class_predicate(client,seize) class_predicate(client,release) OBJECT PREDICATES obj_pred(client,[id]) obj_pred(main,[]) CLAUSES 1: clauses(client,seize(_89),[wait(_89,1)],_90) 2: clauses(client,release(_81),[send(_81,1)],_82) 3: clauses(client, begin, [uniform(0,10,_70), hold(_70), id(_71), _72 is _71+1, new_process(client, [id(_72)]), write(_71), writeln( Waiting), seize(res), write(_71), writeln( Entering resource), uniform(0, 8,_73), hold(_73), release(res), write(_71), writeln( Leaving system)], _74) 4: clauses(main, begin, [send(res,1), new_process(client, [id(1)]), hold(20), writeln(Closing down system), terminate], _45)
Jean G Vaucher
2/18/03
44
Simple Queue Output
1 Waiting 1 Entering resource 2 Waiting 3 Waiting 1 Leaving system 2 Entering resource 4 Waiting 2 Leaving system 3 Entering resource 3 Leaving system 4 Entering resource Closing down system *** THE END *** CPU : 0.95 sec EVALS: 3779 FAILS: 453
Jean G Vaucher
2/18/03
45
Conclusions
, Prolog - 5th Generation Language , Declarative programming , Power of Unification - pattern matching - rule selection , No longer a research curiosity . Industrial language , (SIM) POOPS : structured Prolog , Knowledge and Processes
Modelling for the future
Jean G Vaucher
2/18/03
46
References
Clocksin, W.F. and Mellish, C.S., Programming in Prolog, 2nd Edition, Springer Verlag, New York, 1984. Kowalski, R. "Logic for problem solving", North-Holland, 1979. Sterling, L. and Shapiro, E. "The Art of Prolog", The MIT Press, 1986. Giannesini F., Kanoui H., Pasero R., Van Caneghem M., "Prolog", Interditions, Paris, 1985. Bratko, Ivan, "PROLOG, Programming for artificial intelligence", Addison-Wesley, 1986.
Jean G Vaucher
2/18/03
