Transcript document

Introduction to Prolog
Brian Paden
28-4-2008
P-Phunck - Prolog
1
History

Creators: Alain Colmerauer & Phillipe Roussel


Robert Kowalski


University of Edinburgh
Named by: Philippe Roussel


University of Aix-Marseille 1972
programmation en logique
First compiler: David H. D. Warren
28-4-2008
P-Phunck - Prolog
2
More History

1984 – Began working on standard

1987 – ISO Standard Group Formed

1995 – ISO Standard published


Most current
New version expected “by early 2000”
28-4-2008
P-Phunck - Prolog
3
Predicate Logic

First order predicate calculus

Propositions


Resolution


Atomic propositions & compound terms
Inference rule
Horn clauses

Single atomic proposition on left side

Empty left side
28-4-2008
P-Phunck - Prolog
4
Data Types

Atom



Letters or numbers
'“Var”'
'x', 'longConstant17',
Variable

Start with uppercase 'X', 'NotanAtom'

Anonymous variable - '_'
Fact

28-4-2008
'doesntKnow( “Prolog”, brian ).'
P-Phunck - Prolog
5
Variables

Two states

Instantiated


Uninstantiated


Variable has a set value
Has not been assigned a value
Closed-world assumption

Only true if it can be proven
28-4-2008
P-Phunck - Prolog
6
Data Structures



Compound term

Functor and arguments

'weird( prolog, yes ).'
Queries

'?- good( presentation, brian )'

Only returns 'yes' or 'no'
Conjunction

28-4-2008
Multiply queries and facts
P-Phunck - Prolog
7
Special Compound Terms

List

Head


Tail




First element in list
List containing everything else in list except the head
Last element is empty list - '[]'
'[]', '.' - '[a,[b,[c]]]' == 'a.b.c.[]'
String

Special list – all elements are atoms

28-4-2008
'[“This”,is,a,string,in,”Prolog”]'
P-Phunck - Prolog
8
More Lists


Special list operators

'[]' - Empty list

'[X|Y]' – X is head, Y is tail

'””' - convert list to list containing ascii values
Recursive search for element of list
member(X,[X|_]).
member(X,[_|Y]) :- member(X,Y).
?- member(c,[a,b,c,d,e,f]).
yes
28-4-2008
P-Phunck - Prolog
9
Built in Operators

Compound construction



',' - conjunction, ';' - disjunction
Comparison

'X = Y' – equality, 'X \= 2' – inequality

'X == Y' – strict equality, 'X \== 2' – strict inequality

'X < Y', 'X =< Y', - less than, less than equal to

'X > Y', 'X >= Y' – greater than, greater than equal to
Arithmetic

28-4-2008
'X + Y', 'X - Y', 'X * Y', 'X / Y', 'X mod Y'
P-Phunck - Prolog
10
Arithmetic


Operators that stand out

'\' - not, '\=' - not equal

'=<' - less equal, '>=' - greater equal
Perform arithmetic

'is'



28-4-2008
' Y = Y/X' – tests equality
'Y is Y/X' – assigns numeric value to Y
Right hand side of 'is' must be algebraic
P-Phunck - Prolog
11
Looping

No iteration, only recursion
factorial(0,1).
factorial(N,F) :N>0,
N1 is N-1,
factorial(N1,F1),
F is N * F1.
?- factorial(3,X).
X=6
28-4-2008
P-Phunck - Prolog
12
I/O

Special file



Output

'tell(X).' - creates/opens file

'telling(X).' - gets open file name

'told' – closes file
Input


'user'
see, seeing, seen
Misc

28-4-2008
'tab(X)', 'nl'
P-Phunck - Prolog
13
Backtracking

User query

Searches database for fact declaring it true

Matching fact (head rule) found


No matching fact found


Mark place in database, move on to next goal
Attempt to re-satisfy goal
 Undo last change and try again
Cut

Shortcuts backtracking

28-4-2008
'!' symbol
P-Phunck - Prolog
14
Backtracking in Action
Database
Result
father(mary,george).
father(john,george).
father(sue,harry).
father(george,edward).
father(X) :father(_,X).
Y=george;
Y=george;
Y=harry;
Y=edward;
no
Query
?- father(Y).
28-4-2008
P-Phunck - Prolog
15
Lists and Backtracking
reverse([],[]).
reverse([Head|Tail],List) :reverse(Tail,Result),
append(Result,[Head],List).
trace.
?- reverse([a,b,c],Q).
28-4-2008
P-Phunck - Prolog
16
Reverse Example
(1) 1 Call: reverse([a,b,c],_6)?
(2) 2 Call: reverse([b,c],_65636)?
(3) 3 Call: reverse([c],_65646)?
(4) 4 Call: reverse([],_65656)?
(4) 4 Call: Exit: reverse([],[])
(5) 4 Call: append([],[c],_65646)?
(5) 4 Exit: append([],[c],[c])
(3) 3 Exit: reverse([c],[c])
(6) 3 Call: append([c],[b],_65636)?
(7) 4 Call: append([],[b],_25)?
(7) 4 Exit: append([],[b],[b])
(6) 3 Exit: append([c],[b],[c,b])
(2) 2 Exit: reverse([b,c],[c,b)
(8) 2 Call: append([c,b],[a],_6)?
(9) 3 Call: append([b],[a],_32)?
(10) 4 Call: append([],[a],_39)?
(10) 4 Exit: append([],[a],[a])
(9) 3 Exit: append([b],[a],[b,a])
(8) 2 Exit: append([c,b],[a],[c,b,a])
(1) Exit: reverse([a,b,c],[c,b,a])
28-4-2008
P-Phunck - Prolog
17
How to Cut
Database
Result
sum_to(1,1) :- !.
sum_to(N,Res) :N1 is N – 1,
sum_to(N1,Res),
Res is Res + N.
X = 15;
no
Query
?- sum_to(5,X).
28-4-2008
P-Phunck - Prolog
18
Useful Built in Predicates

Conditional

'true', 'fail' – Always their namesakes

'atom(X)', 'integer(X)' – true if X is an atom or int

'atomic(X)' – X is not a variable

'asserta(X)' – adds clause X to start of database

'assertz(X)' – adds clause to end of database

'X =.. L' - Univ


28-4-2008
X is variable
L is list where head is functor and tail is arguments
P-Phunck - Prolog
19
Example: Binary Tree
Implementation
Usage
lookup(H,w(H,G,_,__,G) :- !.
lookup(H,w(H1,_,Before,_),G)
:aless(H,H1),
lookup(H,Before,G).
lookup(H,w(H1,_,_,After),G) :not(aless(H,H1)),
lookup(H,After,G).
?- lookup(key,X,582),
lookup(val,X,356).
28-4-2008
P-Phunck - Prolog
20
Example: Quicksort
partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :(
X @< Pivot ->
Smalls = [X|Rest],
partition(Xs, Pivot, Rest, Bigs)
;
Bigs = [X|Rest],
partition(Xs, Pivot, Smalls, Rest)
).
quicksort([])
--> [].
quicksort([X|Xs]) -->
{ partition(Xs, X, Smaller, Bigger) },
quicksort(Smaller), [X], quicksort(Bigger).
28-4-2008
P-Phunck - Prolog
21
Example: Turing Machine
turing(Tape0, Tape) :perform(q0, [], Ls, Tape0, Rs),
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :symbol(Rs0, Sym, RsRest),
once(rule(Q0, Sym, Q1, NewSym, Action)),
action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
perform(Q1, Ls1, Ls, Rs1, Rs).
symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).
28-4-2008
P-Phunck - Prolog
22
Compilers

ISO Compliant

GNU Prolog


SWI-Prolig


http://www.swi-prolog.org/
YAP


http://www.gprolog.org/
http://www.ncc.up.pt/yap/
Visual Prolog (Turbo Prolog)

28-4-2008
http://www.visual-prolog.com/
P-Phunck - Prolog
23
Sources



Clocksin, W.F and Mellish, C.S. Programming
in Prolog. Berlin. Springer-Verlag: 1984
Sebesta, Robert W. Concepts of Programming
Languages: Eighth Edition. 2007
http://en.wikipedia.org/wiki/Prolog
28-4-2008
P-Phunck - Prolog
24