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 PQ 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: AB AB ABC 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: AB AC 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) AB BA B A (Horn) 15 Prolog Logical Laws AA (A B) A B A (B C) (A B) (A C) ABAB • 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