Prolog Programming Lecture Module 13 Objective ● ● ● ● ● ● ● ● ● ● ● What is Prolog? Prolog program Syntax of Prolog Prolog Control Strategy Execution of Prolog Query Programming Techniques Termination Rule Order Goal Order Rule Redundancy Iterative Programming What is Prolog? ● Prolog is acronym of PROgramming in LOGic. ● Prolog program is sequence of rules and facts. ● Prolog Rule for grandfather is defined as: gfather(X, Y) :- father(X, Z), parent(Z, Y). father(james, robert). Glimpse of Prolog Program /* Rules: “X is grand father of Y if X is father of Z who is parent of Y */ gfather(X, Y) :father(X, Z), parent(Z, Y). parent(X, Y) :father(X, Y). parent(X, Y) :mother(X, Y). /*Facts “James is father of robert” */ father(james, robert). father(mike, william). father(william, james). father(robert, hency). father(robert, cris). /* Goals ‘ Is abraham a grand father of mike?’*/ ?- gfather(abraham, mike). ?- gfather(X, Y). ?- father(X, Y), father(Y, mike). (1) (2) (3) (4) (5) (6) (7) (8) Back General Syntax of Prolog ● The rules and facts in Prolog are terminated by full stop (.). ● Goal can be included in the program or given at the prompt. ● Goal can be single or conjunction of sub-goal(s) terminated by full ● ● ● ● stop. Constants are numerals and symbols such as, 4, mary, etc. String is a sequence of characters and is enclosed within single quotes e.g., 'This is a string'. Predicate names must start with alphabet and are formed by using lower case letters, numerals and underscore ( _ ). Variable names are formed similar to predicate names but it must start with upper case letter. Normally, we use X, Y, Z, ... for variables. Prolog Control Strategy ● Prolog contains three basic control strategies. − Forward movement − Matching (Unification) − Backward movement (Backtracking) ● Prolog uses depth first search strategy. Forward Movement ● Choose a rule by − searching sequentially in the program from top to bottom whose head matches with the goal with possible unifier. − Remember the position of the matched rule. − Join the rule body in front of the sequence of sub goals to be solved. ● Repeat until either goal is satisfied or is failed. Forward Movement – Cont… ● Consider the following query consisting of n sub-goals. ?- G1, ... , Gi-1, Gi, ... , Gn ● Starts executing or satisfying G1 − If G1 is satisfied using some rule, put a place marker so that next rule for G1 will be searched after the marker. − Continue in forward direction to satisfy G2 and if it is satisfied then continue with common bindings of the variables in sub-goals so far satisfied. − Such a movement is called forward Unification ● Unification is a process of matching or finding the most general unifier. − Constant matches with the same constant. − A variable can match with any constant or any another variable. ● Examples − love(X, sita) unifies with love(ram, sita) with mgu as {X / ram}. − love(X, Y) unify with love(ram, sita) with mgu as {X / ram, Y / sita} respectively. Backtracking ● Backtracking refers to backtrack in search process for a solution. ● In Prolog, backtracking takes place in two situations. − First when a sub goal fails and − Other when the last sub goal succeeds, it backtracks to find alternative solutions. Types of backtracking ● Prolog has two kinds of backtracking. − Shallow and − Deep backtracking ● Both backtrackings take place in conjunction with each other. ● Shallow backtracking occurs − when alternative definition of the goal is tried. − Suppose G1,.., Gi-1 have been satisfied with some common bindings of the variables in subgoals. − While satisfying Gi., if it fails for some rule then try another rule of Gi − This is called shallow backtracking to rules of the same sub-goal Backtracking Cont… ● Deep backtracking occurs − When sub-goal Gi fails for all rules of Gi then backtrack to Gi-1. − This backtracking is called deep backtracking. − Remove the bindings created earlier to satisfy Gi-1. − Try to satisfy Gi-1 again by using an alternative rule, if it exists, from last place marker of Gi-1. and continue the process. − If sub goal Gi-1 is satisfied then move forward to Gi, else backtrack to Gi-2. − The process of backtracking continues till we reach G1. − If G1 fails for all possible definitions, then entire query fails. Backtracking Cont… ● If entire conjunction of sub-goals succeed, then the solution is displayed. ● For alternative solution, the sub goal Gn is tried to be satisfied with alternative rule, if it exist, after last place marker (Shallow backtracking) of Gn . ● Otherwise it backtracks to previous sub goal Gn-1 (Deep backtracking). ● Process is repeated till all possible solutions are generated. Prolog Query ● Two types of query − Ground query No variable in the argument Example: ? gfather(ram, shyam) – Is ram a grand father of shyam? Answer to ground queries are Yes or No Proof tree is generated while solving the query. − Non ground query Atleast one argument is a variable Example: ? gfather(X, shyam) – Who is a grand father of shyam? Answer to such queries are the values bound to the variables in the query. Search tree is generated using DFS to find all possible solutions. Execution of ground query Ground query: Prolog Program ?- gfather(james, hency). Proof tree: ?- gfather(james, hency). (1) ?- father(james, Z), parent(Z, hency). (4) { Z = robert } ?- parent(robert, hency). (2) ?- father(robert, hency). (7) succeeds Answer: Yes Execution of Non ground query Non-Ground query: ?- gfather(william, X). Search tree: Prolog Program ?- gfather(william, X). (1) ?- father(william, Z), parent(Z, X). (6) {Z = james} ?- parent(james, X). (2) (3) ?- father(james, X). ?- mother(james, X). (4) {X = robert} succeeds fails Answer: X = robert Programming Techniques ● Recursion is one of the most important execution control techniques in Prolog. ● Iteration is another important technique. ● Prolog does not support iteration. ● It can be achieved by programming − making recursive call to be the last sub goal in the rule − using the concept of accumulators which are special types of arguments used for holding intermediate results. ● The issues of termination, rule order, goal order and redundancy are also important. Recursion in Prolog ● Consider a classical example of computing factorial using recursion. ● Recurrence relation or mathematical definition for computing factorial of positive integer is: 1, if n = 0 FACTORIAL (n) = n * FACTORIAL (n-1), otherwise ● In Prolog, program for computing factorial of a positive number is written using above definition. ● Factorial predicate contains two arguments; one as input and another as output. Recursion - Cont.. /*fact(N, R) – succeeds if R is unified with the factorial of N */ factorial(0, 1). (1) factorial(N, R) :- N1 is N–1, factorial(N1, R1), R is N * R1. (2) ● Rule (1) states that factorial of 0 is 1 which is a terminating clause. ● Rule (2) is a recursive rule which states that factorial of N is calculated by multiplying N with factorial of (N-1). Goal: ?- factorial(3, R). Execution of factorial query Search tree: ?- factorial(3, R). (2) {N = 3} ?- N1 is N-1, factorial(N1, R1), R is N * R1 (2) {N1 = 2} ?-N2 is N1-1,factorial(N2,R2),R1 is N1*R2,R is N*R1. (2) {N2 = 1} ?-N3 is N2-1, factorial(N3, R3), R2 is N2 * R3…. (1) {N3 = 0, R3 = 1} ?- R2 is 1 * R3 , R1 is N1 * R2, R is N * R1. Succeeds {R2 = 1, R1 = 2, R = 6} List Manipulation in Prolog List is a common and very useful recursive data structure in non numeric programming. In Prolog, a list is represented by − − − elements separated by comma and enclosed in square brackets. Examples: A = [2, 4, 6, 8], B = [[a, b], [c], [p]]. Empty list with no elements is represented by [ ] and is useful for terminating recursive programs for list. Membership function ● An element is a member of a list if it matches with the head or if it is contained in the tail of the list. − The fact that it matches with the head of a list is written as: mem_list(X, [X | _ ]). − The rule that if an element does not match with the head, then it may be in the tail is written as: mem_list(X, [ _ | Y]) :mem_list(X, Y). mem_list(X, [X | _ ]). mem_list(X, [_ | Y]) :- mem_list(X, Y). − Underscore is used for non care entry. (1) (2) Ground Query Goal: ?- mem_list(d, [a, b, c, d, e, f]). Proof tree: ?- mem_list(d, [a, b, c, d, e, f]). (2) {X = d, Y = [b, c, d, e, f]} ?- mem_list(d, [b, c, d, e, f]). (2) {X = d, Y1 = [c, d, e, f]} ?- mem_list(d, [c, d, e, f]). (2) {X = d, Y2 = [d, e, f]} ?- mem_list(d, [d, e, f]). (1) succeeds Ans: Yes Non ground Query Goal: ?- mem_list(X, [a, b, c]). Search tree: ?- mem_list(X, [a, b, c]). (1) (2) {X = a} {Y = [b, c]} succeeds ?- mem_list(X, [b, c]). (1) (2) {X = b} {Y = [c]} succeeds ?- mem_list(X, [c]). (1) (2) {X = c} {Y = []} succeeds ?- mem_list(X, []). Answer:X = a; X = b; X = c fails Termination Depth first traversal of Prolog has a serious problem. If the search tree of a goal with respect to a program contains an infinite branch, the computation will not terminate. Prolog may fail to find a solution of a goal, even if the goal has a finite computation. Non termination arises because of the following reasons: − Left recursive rules: The rule having a recursive goal as the first sub goal in the body. Example ● Consider acyclic directed graph p q r s t ● Graph G is represented by set of connected edges. G = { edge(p, q), edge(q, r), edge(q, s), edge(s, t)} ● Write Prolog Program to check whether there is a route from one node to another node. Program ● Route from node A to B is defined as follows: − route from A to B if there is a root from A some node C and an edge from C to B. − route from A to B if there is a direct edge from A to B. ● Prolog Program route(A, B) :- route(A, C), edge(C, B). route(A, B) :- edge(A, B). edge(p, q). edge(q, r). edge(q, s). edge(s, t). (1) (2) back Query: Check whether there exist a route between nodes p and t . Proof tree Goal: ?- route(p, t). Proof tree: ?- route(p, t). (1) ?- route(p, X), edge(X, t) (1) ?- route(p, Y), edge(Y, X), edge(X, t). Non terminating ● Non terminating program because of left recursion. ● Better way of writing a rule is to write recursive call as the last call. route(A, B) :- edge(A, C), route(C, B). Circular Definition ● Non termination occurs because of Circular definition of the rules. ● For example, ground and nonground queries will not terminate with respect to the following program. teacher(X, Y) :- student(Y, X). student(X, Y) :- teacher(Y, X). student(robert, mike). student(john, robert). Example: ?- teacher(mike, robert) (1) ?- student(robert, mike) (2) ?- teacher(mike, robert) Non termination (1) (2) Rule Order ● A rule order is very important issue in Prolog. ● Change of the order of rules in a program, the branches in any search tree for a goal to be solved with that program get permuted. ● It may affect the efficiency of executing goal. ● Since the search tree is traversed using depth first approach, the order of solutions will be different. − Check the order of solutions obtained if rules are interchanged in a Prolog program (go). Goal Order ● Goal order in Prolog is more significant than rule order. ● It may affect the termination because − subsequent sub goals have different bindings and hence different search trees. ● Consider the following recursive rules. ancester(X, Y) :- parent(X, Z), ancester(Z, Y). route(X, Y) :- edge(X, Z), route(Z, Y). ● If the sub goals in the body of above rules are swapped, then the rules becomes left recursive and all the computations will become non terminating. ● It also affects the amount of search the program does in solving a query . Redundancy ● Redundancy of the solution to the queries is another ● ● ● ● important issue in Prolog programs. In Prolog, each possible deduction means an extra branch in the search tree. The bigger the search tree, higher the computation time. It is desirable in general to keep the size of the search tree as small as possible. Redundant program at times may cause exponential increase in runtime in the event of backtracking. Redundancy – Cont.. ● There are various reasons redundancy gets introduced. by which − The same case is covered by several rules − Redundancy in computation appears in the program by not handling special separately. − See examples given in the book. cases Iteration in Prolog Prolog does not have storage variables that can − hold intermediate results of the computation − be modified as the computation progress. To implement iterative algorithm one requires the storage of intermediate results, Prolog predicates are augmented with additional arguments called accumulators. These are similar to local variables in procedural languages. The programs written using accumulators are iterative in nature. In iterative form of a program, make the recursive call as the last call if possible. Iteration – cont… ● Prolog program for factorial using accumulators. ● Accumulators I and T are used for storing the counter value and intermediate computations fact (N, R) :fact1(N, R, I, T) :- fact1(N, R, 0, 1). I < N, J is I + 1, T1 is J * T, fact1(N, R, J, T1). fact1(N, R, N, R). (1) (2) (3) ● In prolog, predicates can be overloaded. So we can also use ‘fact’ instead of fact1. Search tree Goal: ?- fact (3, R). Search tree: ?- fact(3, R). (1) ?- fact1(3, R, 0, 1). (2) ?- 0 < 3, J is 1, T1 is 1 * 1, fact1(3, R, 1, 1). (2) ?- 1 < 3, J is 2, T1 is 2 * 1, fact1(3, R, 2, 2). (2) ?- 2 < 3, J is 3, T1 is 3 * 2, fact1(3, R, 3, 6). (2) fails Answer: R = 6 (3) {R = 6} succeeds

Descargar
# Artificial Intelligence