Prolog programming

2 Prolog ProgrammingProlog Programming  DATA STRUCTURES IN PROLOG  PROGRAMMING TECHNIQUES  CONTROL IN PROLOG  CUTS

3 DATA STRUCTURES IN PROLOG  Lists in Prolog List notation is a way of writing terms  Terms as Data Term correspond with list

4 Lists in Prolog  The simplest way of writing a list is to enumerate its elements. The list consisting of the 3 atoms a, b and c can be written as [a, b, c] The list that doesn’t have elements called empty list denoted as [ ]

5 Lists in Prolog  We can also specify an initial sequence of elements and a trailing list, separated by | The list [a, b, c] can also be written as [a, b, c | [ ] ] [a, b | [c] ] [a | [b, c] ]

6 Lists : Head & Tail  A special case of this notation is a list with head H and tail T, written as [H|T]  The head is the first element of a list, and  The tail is the list consisting of the remaining elements. The list [a, b, c] can also be separated as • Head:The first element is a • Tail:The list of remaining elements = [b, c]

7 Lists : Unification  Unification can be used to extract the components of a list, so explicit operators for extracting the head and tail are not needed. The solution of the query  Bind variable H to the head and variable T to the tail of list [a, b, c]. ?- [H | T] = [a, b, c]. H = a T = [b, c]

8 Lists : Specified terms  The query (partially specified terms)  The term [ a | T ] is a partial specification of a list with head a and unknown tail denoted by variable T.  Similarly, [ H, b, c] is a partial specification of a list with unknown head H and tail [b, c].  These two specification to unify H = a, T =[b,c] ?- [a | T] = [H, b, c]. T = [b, c] H = a

9 Lists in Prolog  Example 2 The append relation on lists is defined by the following rules: Append([ ], Y, Y). Append([H | X], Y, [H | Z]) :- append(X,Y,Z). In words, The result of appending the empty list [ ] and a list Y is Y. If the result of appending X and Y is Z, then the result of appending [H | X] and Y is [H | Z]

10 Lists : Compute Arguments  The rules for append can be used to compute any one of the arguments from the other two:  Inconsistent arguments are rejected ?- append([a, b], [c, d], Z). Z = [a, b, c, d] ?- append([a, b], Y, [a, b, c, d]). Y = [c, d] ?- append(X, [c, d], [a, b, c, d]). X = [a, b] ?- append(X, [d, c], [a, b, c, d]). no

11 Terms as Data  The Dot operator or functor ‘.’ corresponds to make list with H and T.  [H | T ] is syntactic sugar for the term .(H,T)  Lists are terms. The term for the list [a, b, c] is .(H,T) .(a, .(b, .(c, [])))

12 Terms as Data  following terms can be drawn a tree  There is a one-to-one correspondence between trees and terms .(a, .(b, .(c, []))) ∙ ∙ ∙ a b c []

13 Terms : Binary Tree  Binary trees can be written as terms  An atom leaf for a leaf  A functor nonleaf with 2 arguments leaf nonleaf(leaf,leaf) nonleaf(nonleaf(leaf,leaf), nonleaf(leaf,leaf)) nonleaf(nonleaf(leaf,leaf),leaf) nonleaf(leaf,nonleaf(leaf,leaf))

14 List : tree  Example 3 A binary search tree is either empty, or it consists of a node with two binary search trees as subtrees.  Each node holds an integer.  Smaller elements appear in the left subtree of a node and larger elements appear in the right subtree.  Let a term node(K,S,T) represent a tree K S T

15 Binary search trees 15 2 16 10 129 0 3 19 10 2 12 9 153 0 16 3

16 Binary search trees  The rules define a relation member to test whether an integer appear at some node in a tree. The two arguments of member are an integer and a tree. member(K,_,_). member(K, node(N,S,_)) :- K < N, member(K, S). member(K, node(N,_,T)) :- K > N, member(K, T).

17 PROGRAMMING TECHNIQUES  The strengths of Prolog namely, backtracking and unification.  Backtracking allows a solution to be found if one exists  Unification allows variables to be used as placeholders for data to be filled in later.  Careful use of the techniques in this section can lead to efficient programs. The programs rely on left-to-right evaluation of subgoals.

18 Guess and Verify  A guess-and-verify query has the form Where guess(S) and verify(S) are subgoals.  Prolog respond to a query by generating solutions to guess(S) until a solution satisfying verify(S) is found. Such queries are also called generate-and-test queries. Is there an S such that guess(S) and verify(S)?

19 Guess and Verify  Similarly, a guess-and-verify rule has the following form:  Example Conslusion(…) if guess(…,S,…) and verify(…,S,…) overlap(X, Y) :- member(M, X), member(M, Y). Two lists X and Y overlap if there is some M that is a member of both X and Y. The first goal member(M, X) guesses an M from list X, and the second goal member(M, Y) verifies that M also appears in list Y.

20  The rules for member are member(M, [M |_]). Member(M, [_ |T]) :- member(M, T). The first rule says that M is a member of a list with head M. The second rule says that M is a member of a list if M is a member of its tail T.

21 Consider query  These query  The first goal in this query generates solutions and the second goal tests to see whether they are acceptable. ?- overlap([a,b,c,d],[1,2,c,d]). yes ?- member(M,[a,b,c,d]),member(M,[1,2,c,d]).

22 Consider query  The solutions generated by the first goal are  Test the second goal ?- member(M,[a,b,c,d]). M = a; M = b; M = c; M = d; no ?- member(a,[1,2,c,d]). no ?- member(b,[1,2,c,d]). no ?- member(c,[1,2,c,d]). yes

23 Hint  Since computation in Prolog proceeds from left to right, the order of the subgoals in a guess-and-verify query can affect efficiency.  Choose the subgoal with fewer solutions as the guess goal.  Example of the effect of goal order ?- X = [1,2,3], member(a,X). no ?- member(a,X), X = [1,2,3]). [infinite computation]

24 Variables as Placeholders in Terms  Variables have been used in rules and queries but not in terms representing objects.  Terms containing varibales can be used to simulate modifiable data structures;  The variables serve as placeholders for subterms to be filled in later.

25 Represent Binary Trees in Terms  The terms leaf and nonleaf(leaf,leaf) are completely specified. leaf nonleaf(leaf,leaf)

26 Partially specified list  The example list [a, b | X] has  Its first element : a  Its second element : b  Do not yet know what X represents  “Open list” if its ending in a variable, referred “end marker variable”  “Close list” if it is not open.

27 How prolog know variable  Prolog used machine-generated variables, written with a leading underscore (“_”) followed by an integer. ?- L = [a, b | X]. L = [a, |_G172] X = _G172 Yes

28  Prolog generates fresh variables each time it responds to a query or applies a rule.  An open list can be modified by unifying its end marker ?- L = [a, b | X], X = [c,Y]. L = [a,b,c |_G236] X = [c,_G236] Y = _G236 Yes

29  Extending an open list by unifying its end marker. a b L X _172 a b L X _236 c (a) Before X is bound. (b) After X = [c | Y].

30  Unification of an end-marker variable is akin to an assignment to that variable.  List L changes from [a, b | _172]  [a, b, c | _236] when _172 unifies with [c | _236]  Advantage of working with open lists is that the end of a list can be accessed quickly.

31 Open list implement queues when a queue is created, where L is an open list with end marker E When element a enters queue Q, we get queue R. When element a leaves queue Q, we get queue R. q(L,E) enter(a,Q,R) leave(a,Q,R)

32 Open list implement queue ?- setup(Q). ?- setup(Q), enter(a,Q,R). ?- setup(Q), enter(a,Q,R), leave(S,R,T). ?- setup(Q), enter(a,Q,R), enter(b,R,S), leave(X,S,T),leave(Y,T,U), wrapup(q([],[])). setup(q(X,X)). enter(A, q(X,Y), q(X,Z)) :- Y = [A | Z]. leave(A, q(X,Z), q(Y,Z)) :- Y = [A | Y]. wrapup(q([],[])).

33 Test queue ?-setup(Q),enter(a,Q,R),enter(b,R,S),leave(X,S,T), leave(Y,T,U),wrapup(U). Q = q([a, b], [a, b]) R = q([a, b], [b]) S = q([a, b], []) X = a T = q([b], []) Y = b U = q([], []) Yes ?-

34 Operations on a queue Q _1 R _2 a a T _3 b Q Q R setup(Q) enter(a,Q,R) enter(b,R,S)

35 Operations on a queue a T _3 b X leave(X,S,T) a T _3 b Y leave(Y,T,U)

36 Internal Prolog  A queue q(L,E) consists of open list L with end marker E.  The arrows from Q therefore go to the empty open list _1 with end marker _1. setup(q(X,X)). ?-setup(Q). Q = q(_1,_1) yes

38  When an element leaves a queue q(L,E), the resulting queue has the tail of L in place of L. Note in the diagram to the right of leave(X,S,T) that the open list for queue T is the tail of the open list for S.  The final goal wrapup(U) checks that the enter and leave operations leave U in an initial state q(L,E), where L is an empty openlist with end marker E.

39 Difference Lists  Difference List are a technique for coping with such changes.  Difference List consists of a list and its suffix.  We write this difference list as dl(L,E).

40 Contents of Difference List  The contents of the difference list consist of the elements that are in L but not in E.  Examples of difference lists with contents [a,b] are dl([a,b],[]). Dl([a,b,c],[c]). Dl([a,b|E],E). Dl([a,b,c|F],[c|F]).

41 CONTROL IN PROLOG  In the informal equation  “Logic” refers to the rules and queries in a logic program and  “control” refers to how a language computes a response to a query. algorithm = logic + control

42 CONTROL IN PROLOG  Control in Prolog is characterized by two decisions  Goal order : Choose the leftmost subgoal.  Rule order : Select the first applicable rule.  The response to a query is affected both by goal order within the query and by rule order with in the database of facts and rules.

43 CONTROL IN PROLOG start with a query as the current goal; while the current goal is nonempty do choose the leftmost subgoal; if a rule applies to the subgoal then select the first applicable rule; form a new current goal else backtrack end if end while; succeed

44 Example  A sublist S of Z can be specified in the following seemingly equivalent ways:  preffix X of Z and suffix S of X.  suffix S of X and prefix X of Z. appen1([],Y,Y). appen1([H|X],Y,[H|Z]):- appen1(X,Y,Z). Prefix(X,Z) :- appen1(X,Y,Z). Suffix(Y,Z) :- appen1(X,Y,Z). appen2([H|X],Y,[H|Z]):- appen2(X,Y,Z). appen2([],Y,Y).

45 Queries  The corresponding queries usually produce the same responses.  Rule order can also make a difference. ?-prefix(X,[a,b,c]),suffix([e],X). no ?-suffix([e],X),prefix(X,[a,b,c]). [infinite computation]

46 Queries ?- appen1(X,[c],Z). X = [] Z = [c] ; X = [_G230] Z = [_G230, c] ; X = [_G230, _G236] Z = [_G230, _G236, c] ; ?- appen2(X,[c],Z).  New Solutions are produced on demand for

47 Unification an Substitutions  Unification is central to control in Prolog  Substitution is a function from variables to terms

48 Applying a Rule to a Goal  A rule applies to a subgoal G if its head A unifies with G  Variables in the rule are renamed before unification to keep them distinct from variables in the subgoal. A :- B1, B2, …, Bn

49 A computation that succeeds without backtracking GOAL Suffix([a],L),prefix(L,[a,b,c]). suffix([a],L) if append(_1,[a],L). Append(_1,[a],L),prefix(L,[a,b,c]). {_1[],L[a]} append([],[a],[a]). Prefix([a],[a,b,c]). prefix([a],[a,b,c]) if append([a],_2,[a,b,c]) append([a],_2,[a,b,c]). prefix([a],[a,b,c]) if append([],_2,[b,c]) Append([],_2,[b,c]). {_2[b,c]} append([],[b,c],[b,c]) yes

51 Goal Order Changes Solutions

52 Cuts  A cut prunes or “cuts out” and unexplored part of a Prolog search tree.  Cuts can therefore be used to make a computation more efficient by eliminating futile searching and backtracking.  Cuts can also be used to implement a form of negation

53 Cuts  A cut, written as !, appears as a condition within a rule. When rule is applied, the cut tells control to backtrack past Cj-1,…,C1,B, without considering any remaining rules for them. B :- C1,…, Cj-1, !,Cj+1,…,Ck

54 A cut as the First Condition  Consider rules of the form  If the goal C fails, then control backtracks past B without considering any remaining rules for B. Thus the cut has the effect of making B fail if C fails. B :- !, C.

55 Example b :- c. b :- d. b :- e. b,G c,G e,G X d,G!,d,G d,G b :- c. b :- !,d. b :- e.

56 Example  ?-a(X). a(1) :- b; a(2) :- e; b :- c. b :- d. a(1) :- b; a(2) :- e; b :- !,c. b :- d. a(X) b e c d Yes X=2Yes X=1 backtrack a(X) b e !c d Yes X=2 backtrack c

57 The Effect of Cut  As mentioned earlier, when a rule is applied during a computation  The cut tells control to backtrack past Cj- 1,..C1,B without considering any remaining rules for them.  The effect of inserting a cut in the middle of a guess-and-verify rule. B :- C1,…, Cj-1, !,Cj+1,…,Ck

58 The Effect of Cut  The right side of a guess-and-verify rule has the form guess(S), verify(S), where guess(S) generates potential solutions until one satisfying verify(S) is found.  The effect of insering a cut between them, as is to eliminate all but the first guess. Conclusion(S) :- guess(S), !, verify(S)

59 a(X) :- b(X). a(X) :- f(X). b(X) :- g(X),v(X). b(X) :- X = 4, v(X). g(1). g(2). g(3). v(X). f(5) a(X) :- b(X). a(X) :- f(X). b(X) :- g(X),!,v(X). b(X) :- X = 4, v(X). g(1). g(2). g(3). v(X). f(5) (a) (b)

60 a(Z) b(Z) f(5) g(Z),v(Z) v(4) v(1) v(2) v(3) a(Z) b(Z) f(5) g(Z),!,v(Z) v(4) !v(X) v(1) v(2) v(3) (a) (b)

61 Negation as Failure  The not operator in Prolog is implemented by the rules not(X) :- X, !, fail. not(_).

Prolog programming

More Related Content

What's hot

Viewers also liked

Similar to Prolog programming

More from Harry Potter

Recently uploaded

Prolog programming