09 logic programming

Logic Programming Some "declarative" slides on logic programming and Prolog. James Brucker

Introduction to Logic Programming  Declarative programming describes what is desired from the program, not how it should be done  Declarative language: statements of facts and propositions that must be satisfied by a solution to the program real(x). proposition: x is a real number. x > 0. proposition: x is greater than 0.

Declarative Languages  what is a "declarative language"?  give another example (not Prolog) of a declarative language. SELECT * FROM COUNTRY WHERE CONTINENT = 'Asia';

Facts, Rules, ...  What is a proposition?  What are facts?  What are rules?  What is a predicate?  What is a compound term?

Facts: fish(salmon). likes(cat, tuna). Predicates: fish, likes Compound terms: likes(cat, X), fish(X) Atoms: cat, salmon, tuna Rule: eats(cat,X)  likes(cat,X), fish(X).

A Really Simple Directed Graph a b c d (1) edge(a, b). (2) edge(a, c). (3) edge(c, d). (4) path(X, X). (5) path(X, Y)  edge(X, N), path(N, Y). Question: What are the...  atoms  facts  rules

Clausal Form  Problem: There are too many ways to express propositions.  difficult for a machine to parse or understand  Clausal form: standard form for expressing propositions n m A A A B B B          2 1 2 1 Example: path(X, Y)  edge(X, N)  path(N, Y). Antecedent Consequent

Clausal Form Example Meaning: if there is an edge from X to N and there a path from N to Y, then there is a path from X to Y. The above is also called a "headed Horn clause". In Prolog this is written as a proposition or rule: path(X, Y)  edge(X, N)  path(N, Y). path(X, Y) :- edge(X, N) , path(N, Y).

Query  A query or goal is an input proposition that we want Prolog to "prove" or disprove.  A query may or may not require that Prolog give us a value that satisfies the query (instantiation). 1 ?- edge(a,b). Yes 2 ?- path(c,b). No 3 ?- path(c,X). X = c ; X = d ; No

Logical Operations on Propositions  What are the two operations that a logic programming language performs on propositions to establish a query? That is, how does it satisfy a query, such as:

Unification Unification is a process of finding values of variables (instantiation) to match terms. Uses facts. (1-3) edge(a,b). edge(a,c). edge(c,d). (Facts) (4) path(X,X). (Rule) (5) path(X,Y) := edge(X,N), path(N,Y). (Rule) ?- path(a,d). This is the query (goal). Instantiate { X=a, Y=d }, and unify path(a,d) with Rule 5. After doing this, Prolog must satisfy: edge(a,N). This is a subgoal. path(N,d). This is a subgoal.

Unification in plain English Compare two atoms and see if there is a substitution which will make them the same. How can we unify 6 with 5? Let X := a Let Y := Z 1. edge(a, b). (Fact) 5. path(X, Y) :- edge(X, N) , path(N, Y). 6. path(a, Z). (Query)

Resolution Resolution is an inference rule that allows propositions to be combined.  Idea: match the consequent (LHS) of one proposition with the antecedent (RHS term) of another. ). ( ) ( then ) ( ) ( If ) ( ) ( ) ( ) ( 2 1 1 2 2 1 2 1 y Q y P y Q y P X Q X Q X P X P      Examples are in the textbook and tutorials.

Resolution Example How can we unify 6 with 5? Let X := a Let Y := Z Resolution: 1. edge(a, b). (Fact) 5. path(X, Y) :- edge(X, N) , path(N, Y). 6. path(a, Z). (Query)

How to handle failures  Prolog can work backwards towards the facts using resolution, instantiation, and unification.  As it works, Prolog must try each of several choices.  These choices can be stored as a tree. ?- path(a,d). The goal. Unify: unify path(a,d)with Rule 5 by instantiate { X=a,Y=d } Subgoal: edge(a,N). Instantiate: N=b which is true by Fact 1. Subgoal: path(b,d). Unify: path(b,d)with Rule 5: path(b,d) :- edge(b,N),path(N,d) Failure: can't instantiate edge(b,N) using any propositions.

How to handle failures (2)  When a solution process fails, Prolog must undo some of the decisions it has made.  This is called backtracking.  same as backtracking you use in recursion.  Marks a branch of the tree as failed.

How it Works (1) There are 2 search/execution strategies that can be used by declarative languages based on a database of facts. 1. Forward Chaining 2. Backward Chaining  what are the meanings of these terms?

How it Works (2) 1. Forward Chaining 2. Backward Chaining  Which strategy does Prolog use?  Under what circumstances is one strategy more effective than the other? Consider two cases:  large number of rules, small number of facts  small number of rules, large number of facts

PROLOG: PROgramming in LOGic The only "logic" programming language in common use.

3 Parts of a Prolog Program 1. A database contains two kinds of information.  What information is in a database? 2. A command to read or load the database.  in Scheme you can use load("filename")  in Prolog use consult('filename') 3. A query or goal to solve.

Ancestors ancestor(X,Y) :- parent(X,Y). ancestor(X,Y) :- ancestor(X,Z), ancestor(Z,Y). parent(X,Y) :- mother(X,Y). parent(X,Y) :- father(X,Y). father(bill, jill). mother(jill, sam). mother(jill, sally). File: ancestors.pl

Query the Ancestors ?- consult('/pathname/ancestors.pl'). ancestor(bill,sam). Yes ?- ancestor(bill,X). X = jill ; X = sam ; ERROR: Out of local stack ?- ancestor(X,bob). ERROR: Out of local stack

Understanding the Problem  You need to understand how Prolog finds a solution. ancestor(X,Y) :- parent(X,Y). ancestor(X,Y) :- ancestor(X,Z), ancestor(Z,Y). parent(X,Y) :- mother(X,Y). parent(X,Y) :- father(X,Y). father(bill,jill). mother(jill,sam). father(bob,sam). Depth-first search causes immediate recursion

Factorial factorial(0,1). factorial(N,N*M) :- factorial(N-1,M).  The factorial of 0 is 1.  The factorial of N is N*M if the the factorial of N-1 is M File: factorial1.pl ?- consult('/path/factorial1.pl'). ?- factorial(0,X). X = 1 Yes ?- factorial(1,Y). ERROR: Out of global stack

Query Factorial ?- consult('/path/factorial1.pl'). ?- factorial(2,2). No ?- factorial(1,X). ERROR: Out of global stack ?- 2*3 = 6. No ?- 2*3 = 2*3. Yes Problem: Arithmetic is not performed automatically. ?- 6 is 2*3. Yes ?- 2*3 is 6. No is(6,2*3). l-value = r-value ?

Arithmetic via Instantiation: is  "=" simply means comparison for identity. factorial(N, 1) :- N=0.  "is" performs instantiation if the left side doesn't have a value yet. product(X,Y,Z) :- Z is X*Y.  this rule can answer the query: product(3,4,N). Answer: N = 12.  but it can't answer: product(3,Y,12).

is does not mean assignment!  This always fails: N is N - 1. % sumto(N, Total): compute Total = 1 + 2 + ... + N. sumto(N, 0) :- N =< 0. sumto(N, Total) := Total is Subtotal + N, N is N-1, always fails sumto(N, Subtotal). ?- sumto(0, Sum). Sum = 0. Yes ?- sumto(1, Sum). No

is : how to fix?  How would you fix this problem? % sumto(N, Total): compute Total = 1 + 2 + ... + N. sumto(N, 0) :- N =< 0. sumto(N, Total) := N1 is N-1, always fails sumto(N1, Subtotal), Total is Subtotal + N. ?= sumto(5, X).

Factorial revised factorial(0,1). factorial(N,P) :- N1 is N-1, factorial(N1,M), P is M*N. Meaning:  The factorial of 0 is 1.  factorial of N is P if N1 = N-1 and factorial of N1 is M and P is M*N. File: factorial2.pl

Query Revised Factorial ?- consult('/path/factorial2.pl'). ?- factorial(2,2). Yes ?- factorial(5,X). X = 120 Yes ?- factorial(5,X). X = 120 ; ERROR: Out of local stack ?- factorial(X,120). but still has some problems... request another solution

Factorial revised again factorial(0,1). factorial(N,P) :- not(N=0), N1 is N-1, factorial(N1,M), P is M*N. File: factorial3.pl ?- factorial(5,X). X = 120 ; No ?- Makes the rules mutually exclusive.

Readability: one clause per line factorial(0,1). factorial(N,P) :- not(N=0), N1 is N-1, factorial(N1,M), P is M*N. factorial(0,1). factorial(N,P) :- not(N=0), N1 is N-1, factorial(N1,M), P is M*N. Better

Finding a Path through a Graph edge(a, b). edge(b, c). edge(b, d). edge(d, e). edge(d, f). path(X, X). path(X, Y) :- edge(X, Z), path(Z, Y). a b c d e f ?- edge(a, b). Yes ?- path(a, a). Yes ?- path(a, e). Yes ?- path(e, a). No

How To Define an Undirected Graph? edge(a, b). edge(b, c). edge(b, d). edge(d, e). edge(d, f). edge(X, Y) := not(X=Y), edge(Y, X). path(X, X). path(X, Y) :- edge(X, Z), path(Z, Y). a b c d e f ?- edge(b, a). Yes ?- path(a, b). Yes ?- path(b, e). No

Queries and Answers  When you issue a query in Prolog, what are the possible responses from Prolog? % Suppose "likes" is already in the database :- likes(jomzaap, 219212). % Programming Languages. Yes. :- likes(papon, 403111). % Chemistry. No. :- likes(Who, 204219). % Theory of Computing? Who = pattarin  Does this mean Papon doesn't like Chemistry?

Closed World Assumption  What is the Closed World Assumption?  How does this affect the interpretation of results from Prolog?

List Processing  [Head | Tail] works like "car" and "cdr" in Scheme.  Example: ?- [H | T ] = [a,b,c,d,e]. returns: H = a T = [b,c,d,e]  This can be used to build lists and decompose lists.  Can use [H|T] on the left side to de/construct a list: path(X, Y, [X|P]) :- edge(X, Node), path(Node, Y, P).

member Predicate  Test whether something is a member of a list ?- member(a, [b,c,d]). No.  can be used to have Prolog try all values of a list as values of a variable. ?- member(X, [a1,b2,c3,d4] ). X = a1 X = b2 X = c3

member Predicate example  Use member to try all values of a list.  Useful for problems like  Queen safety  enumerating possible rows and columns in a game. % dumb function to find square root of 9 squareroot9(N) :- member(N,[1,2,3,4,5,5,6,7,8,9]), 9 is N*N.

appending Lists ?- append([a,b],[c,d,e],L). L = [a,b,c,d,e]  append can resolve other parameters, too: ?- append(X, [b,c,d], [a,b,c,d] ). X = a ?- append([],[a,b,c],L). L = [a,b,c]

Defining your own 'append' append([], List, List). append([Head|Tail], X, [Head|NewTail]) :- append(Tail, X, NewTail).

Type Determination  Prolog is a weakly typed language.  It provides propositions for testing the type of a variable PREDICATE SATISFIED (TRUE) IF var(X) X is a variable nonvar(X) X is not a variable atom(A) A is an atom integer(K) K is an integer real(R) R is a floating point number number(N) N is an integer or real atomic(A) A is an atom or a number or a string functor(T,F,A) T is a term with functor F, arity A T =..L T is a term, L is a list. clause(H,T) H :- T is a rule in the program

Tracing the Solution ?- trace. [trace] ?- path(a,d). Call: (8) path(a, d) ? creep Call: (9) edge(a, _L169) ? creep Exit: (9) edge(a, b) ? creep Call: (9) path(b, d) ? creep Call: (10) edge(b, _L204) ? creep Exit: (10) edge(b, c) ? creep Call: (10) path(c, d) ? creep Call: (11) edge(c, _L239) ? creep ^ Call: (12) not(c=_G471) ? creep ^ Fail: (12) not(c=_G471) ? creep Fail: (11) edge(c, _L239) ? creep Fail: (10) path(c, d) ? creep Redo: (10) edge(b, _L204) ? creep

Solution Process Stack Substitution (Instantiation) [path(a,c), path(X,X)] [path(a,c), path(a,a)] X = a Undo. [path(a,c), path(X,X)] [path(a,c), path(c,c)] X = c Undo. (1) path(X,X). (2) path(X,Y) := edge(X,Z), path(Z,Y). ?- path(a,c).

Solution Process (2) Stack Substitution (Instantiation) [path(a,c), path(X,Y)] (Rule 2) [path(a,c), path(a,Y)] X = a X = a, Y = c edge(a,Z), path(Z,c) new subgoals edge(a,b), path(b,c) X = a, Y = c, Z = b path(b,c) edge(a,b) is a fact - pop it. (1) path(X,X). (2) path(X,Y) := edge(X,Z), path(Z,Y). ?- path(a,c).

What does this do? % what does this do? sub([], List). sub([H|T], List) :- member(H, List), sub(T, List).

What does this do? % what does this do? foo([], _, []). foo([H|T], List, [H|P]) :- member(H, List), foo(T, List, P). foo([H|T], List, P) :- not( member(H, List) ), foo(T, List, P). Underscore (_) means "don't care". It accepts any value.

Max Function  Write a Prolog program to find the max of a list of numbers:  max( List, X).  max( [3, 5, 8, -4, 6], X). X = 8.  Strategy:  use recursion  divide the list into a Head and Tail.  compare X to Head and Tail. Two cases:  Head = max( Tail ). in this case answer is X is Head.  X = max( Tail ) and Head < X.  what is the base case?

Max Function % max(List, X) : X is max of List members max([X], X). base case max([H|Tail], H) :- 1st element is max max(Tail, X), H >= X. max([H|Tail], X) :- 1st element not max complete this case.

Towers of Hanoi % Move one disk move(1,From,To,_) :- write('Move top disk from '), write(From), write(' to '), write(To), nl. % Move more than one disk. move(N,From,To,Other) :- N>1, M is N-1, move(M,From,Other,To), move(1,From,To,_), move(M,Other,To,From). See tutorials at: www.csupomona.edu and www.cse.ucsc.edu

Learning Prolog  The Textbook - good explanation of concepts  Tutorials:  http://www.thefreecountry.com/documentation/onlineprolog.sht ml has annotated links to tutorials.  http://www.cse.ucsc.edu/classes/cmps112/Spring03/languages /prolog/PrologIntro.pdf last section explains how Prolog resolves queries using a stack and list of substitutions.  http://cs.wwc.edu/~cs_dept/KU/PR/Prolog.html explains Prolog syntax and semantics.  http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/conte nts.html has many examples

09 logic programming

More Related Content

What's hot

Similar to 09 logic programming

Recently uploaded

09 logic programming