CS 321
Programming Languages and Compilers
Prolog
Prolog
• PROgramming LOGic
• Algorithm = Logic + Control
• Logic programming deals with computing
relations rather than functions.
• To understand Prolog one must understand
– logic: the rules of deduction in first order logic
– control: the way Prolog implements this logic, I.e. the search
strategy that Prolog adopts.
2
Prolog
What is Prolog
• Prolog is a ‘typeless’ language with a very simple
syntax.
• Prolog is a logical programming language.
• Prolog uses
– Horn clauses
– implements resolution
» using a “depth first” strategy
» unification
• Atoms, lists and records are the data structures.
3
Prolog
Declarative Languages
• Also known as logic programming
• Examples: Prolog, SQL, Datalog.
• Typical of database systems and artificial
intelligence.
• Declarative specifications: Specify what you
want, not how to compute it.
• E.g. Find X and Y such that
3*X+2*Y=1
X-Y=4
4
Prolog
Classical First-Order Logic
• simplest form of logical statements is an atomic
formula. e.g.
man(tom)
woman(mary)
married(tom,mary)
• More complex formulas can be built up using
logical connectives:  ,  ,  ,  X ,  X .
5
Prolog
Examples of First Order Logic
smart(tom)  dumb(tom)
smart(tom)  tall(tom)
dumb(tom)
X married(tom,X)
X loves(tom,X)
X [married(tom,X)  female(X)  human(X)]
6
Prolog
Logical Implication
rich(tom)   smart(tom)
This implies that if tom is smart, then he must be
rich. So, we often write this as
rich(tom)  smart(tom)
In general, P  Q and Q  P are abbreviations for
PQ
Examples:
 X[(person(X)  smart(X))  rich(X)]
 X mother(john,X)
 X [mother(john,X)   Y[mother(john,Y)  Y=X]
]
7
Prolog
Horn Rules
• Logic programming is based on formulas called
Horn rules. These have the form
 x 1 ,..., x k [A  B 1  B 2  ...  B j ]
• Examples:
 X,Y[A(X)  B(X,Y)  C(Y)]
 X[A(X)  B(X)]
 X[A(X,d)  B(X,e)]
A(c,d) B(d,e)
 X A(X)
 X A(X,d)
A(c,d)
• Note that atomic formulas are also Horn rules,
often called facts.
• A set of Horn rules is called a Logic Program.
8
Prolog
Logical Inference with Horn Rules
• Logic programming is based on a simple idea:
From rules and facts, derive more facts.
• Example 1. Given the facts A, B, C, D, and the
rules:
1. E  A  B
2. F  C  D
3. G  E  F
From 1, derive E; from 2, derive F; from 3, derive G.
9
Prolog
Logical Inference
• Example 2: Given these facts:
man(plato)
man(socrates)
and this rule:
 X [man(X)  mortal(X)]
derive:
mortal(plato), mortal(socrates).
10
Prolog
Recursive Inference
• Example, given
 X[mortal(X)  mortal(son_of(X))]
mortal(plato)
derive:
mortal(son_of(plato))
(using X=plato)
mortal(son_of(son_of(plato)))
(using X=son_of(plato))
mortal(son_of(son_of(son_of(plato))))
(using X=son_of(son_of(plato)))
11
Prolog
Logic Programming
• Horn rules correspond to programs, and a form of
Horn inference corresponds to execution.
• For example, consider the rule:
 X,Y p(X)  q(X,Y)  r(X,Y)  s(X,Y)
• This rule can be interpreted as a program where
–
–
–
–
p is the program name,
q, r, s are subroutine names,
X is a parameter of the program, and
Y is a local variable.
12
Prolog
Non-Horn Formulas
• The following formulas are not Horn:
AB
AB
ABC
X[A(X)  B(X)]
A  (B  C)
X[flag(X)  [red(X)  white(X)]]
 X  Y[wife(X)  married(X,Y)]
13
Prolog
Non-Horn Inference
• Non-Horn inference is more complex that with
Horn formulas alone. Example:
AB
AC
B  C (non-Horn)
We can infer A, but only by doing case analysis
either B or C is true.
if B then A
if C then A
Therefore, A.
• Non-Horn formulas do not correspond to
programs, and non-Horn inference does not
correspond to execution.
14
Prolog
Logical Equivalence
• Many non-Horn formulas can be put into Horn
form by using either:
– logical equivalence
– Skolemization (a subject for a later course).
• Example of logical equivalence:
 A   B   A   ( B)
AB
BA
 B  A (Horn)
15
Prolog
Logical Laws
AA
(A  B)   A   B
A  (B  C)  (A  B)  (A  C)
ABAB
• Example using logical equivalence and laws:
A  (B  C)  A   (B  C)
 A  (B)  ( C)
 (A  B)  (A   C)
 (A  B)  (A  C)
(Horn)
16
Prolog
Non-convertible Formulas
• In general, rules of the following form cannot be
converted into Horn form:
 x[(A
1
 ...  A n )  ( B 1  ...  B m )]
For example,
(A  B)  (C  D)
(A  B)  C
(A  B)
i.e., if it is possible to infer a non-trivial disjunction
from a set of formulas, then the set is inherently
non-Horn.
17
Prolog
Prolog
• Syntax is Horn clauses of terms.
• Proof process involves SLD Resolution
– unification + substitution: pattern matching between terms +
binding unresolved variables as needed.
– automatic backtracking: if one attempt fails, try again until all
search paths are exhausted.
SLD stands for Selecting a literal, using a Linear strategy,
restricted to Definite clauses. The name SLD was coined by
researchers in automatic theorem proving before the birth of
logic programming
18
Prolog
Prolog Notation
• For convenience, we don’t write the universal
quantifiers, so a rule:
 X [p(X)  (q(X)  r(X))]
is written as
p(X)  q(X), r(X).
• We also use the Prolog conventions:
– variables begin with upper case (A, B, X, Y, Big, Small, ACE)
– constants begin with lower case (a, b, x, y, plato, aristotle)
19
Prolog
Prolog Syntax
< fact >
 < term > .
< rule >
 < term >
< query >
 < terms > .
< term >
 < number
:- < terms > .
> | < atom >
| <variable> | < atom > ( < terms > )
< terms >
 < term
> | < term > , < terms >
20
Prolog
Syntax
• Integers: base 10
• atoms: user defined, supplied
– name starts with lower case: john, student2
• Variables
– begin with upper case: Who, X
– ‘_’ can be used in place of variable name
• Structures
– student(ali, freshman, 194).
• Lists
– [x, y, Z ]
– [ Head | Tail ]
» syntactic sugar for
. ( Head, Tail )
– []
21
Prolog
Prolog Introduction
/* list of facts in prolog, stored in an ascii file, ‘family.pl’*/
mother(mary, ann).
mother(mary, joe).
mother(sue, marY ).
father(mike, ann).
father(mike, joe).
grandparent(sue, ann).
/* reading the facts from a file */
1?- consult ( ‘family.pl’ ).
family.pl compiled, 0.00 sec, 828 bytes
22
Prolog
• Comments are either bound by “/*”,”*/” or any characters
following the “%”.
• Structures are just relationships. There are no inputs or
outputs for the variables of the structures.
• The swipl documentation of the built-in predicates does
indicate how the variables should be used.
pred(+var1, -var2, +var3).
+ indicates input variable
- indicates output variable
• You can also consult a file with a “pl” extension by
?- [family].
23
Prolog
/* Prolog the order of the facts and rules is the order it is searched in */
/* Variation from pure logic model */
2 ?- father( X, Y ).
X = mike /* italics represents computer output */
Y = ann ; /* I type ‘;’ to continue searching the data base */
X = mike
Y = joe ;
no
3 ?- father( X, joe).
X = mike ;
no
24
Prolog
/* Rules */
parent( X , Y ) :– mother( X , Y ). /* If mother( X ,Y ) then parent(
X ,Y ) */
parent( X , Y ) :– father( X , Y ).
/* If the facts are later then grandparent(sue, ann). redundant
*/
/* if parent( X ,Y ) and parent(Y,Z ) then grandparent( X ,Z ). */
grandparent( X , Z ) :– parent( X , Y ),parent(Y, Z ).
25
Prolog
‘or’
parent( X , Y ) :– mother( X , Y ); father( X , Y ).
has same effect as:
parent( X , Y ) :– mother( X , Y ).
parent( X , Y ) :– father( X , Y ).
26
Prolog
mother(mary, ann).
mother(mary, joe).
mother(sue, marY ).
father(mike, ann).
father(mike, joe).
parent( X , Y ) :– mother( X , Y ).
parent( X , Y ) :– father( X , Y ).
?- parent( X , joe).
X = mary
yes
parent ( X, joe).
binding
Y = joe
X = mary
mother( X , joe).
mother( mary, ann). /* fails */
mother (mary, joe).
X = mary
27
Prolog
?- parent( X , ann), parent( X , joe).
X = mary;
X = mike
yes
?- grandparent(sue, Y ).
Y = ann;
Y = joe
yes
28
Prolog
/* specification of factorial n! */
factorial(0,1).
factorial(N, M):– N1 is N – 1, factorial (N1, M1), M is N*M1.
29
Prolog
r1:
r2:
addToSet( X,L,L ) :- member( X, L ).
addToSet( X,L,[X|L] ).
?-addToSet(a, [b,c], O).
r1
Pattern
r2
addToSet( X, L, [X|L] )
addToSet( X, L, L )
unification
addToSet(a,[b,c],[b,c]
addToSet(a, [b,c],[a|[b,c]]
succeeds
subgoals
member(a, [b,c]).
FAILS
backtrack
30
Prolog
Recursion in Prolog
• trivial, or boundary cases
• ‘general’ cases where the solution is constructed
from solutions of (simpler) version of the original
problem itself.
• What is the length of a list ?
• THINK:
The length of a list, [ e | Tail ], is 1 + the length of
Tail
• What is the boundary condition?
– The list [ ] is the boundary. The length of [ ] is 0.
• Where do we store the value of the length?-accumulator -length( [ ], 0 ).
length([H | T], N) :- length(T,Nx), N is Nx + 1
31
Prolog
Recursion
mylength( [ ], 0).
mylength( [X | Y], N):–mylength(Y, Nx), N is Nx+1.
? – mylength( [1, 7, 9], X ).
X=3
? - mylength(jim, X ).
no
? - mylength(Jim, X ).
Jim = [ ]
X=0
32
Prolog
Recursion
mymember( X , [X | _ ] ).
mymember( X , [ _ | Z ] ) :– mymember( X , Z ).
% equivalently: However swipl will give a warning
%
Singleton variables : Y W
mymember( X , [X | Y] ).
mymember( X , [W | Z ] ) :– mymember( X , Z ).
1?–mymember(a, [b, c, 6] ).
no
2? – mymember(a, [b, a, 6] ).
yes
3? – mymember( X , [b, c, 6] ).
X = b;
X = c;
X = 6;
no
33
Prolog
Descargar

Abstract data types