Lecture 23 Administrative: - hw4 is returned - hw5 is due - today's office hour is moved to next tuesday 3:00-4:30pm. Logic Programming 2. Prolog (Programming Logic) ^^^ ^^^ i) first encouter - A Prolog interpreter runs in the context of a database of clauses. - clauses can be either facts or rules. e.g., rainy(rochester). e.g., snowy(X) :- rainy(X), cold(X). note: variables must begin with a uppercase letter. - query is a clause with empty left-hand side. e.g., ?- rainy(C). Suppose the database contains rainy(seattle). rainy(rochester). then the Prolog interpreter would respond to the above query with C = seattle By typing a semicolon, we can get other answers, in this case, C = rochester We can keep prompting the interpreter till we get no further answer. C = seattle; C = rochester; no - lists [a, b, c] .(a, .(b, .(c, []))) [a | [b,c]] member(X, [X|T]). member(X, [H|T]) :- member(X, T). - arithmetic ?- (2+3) = 5. no ?- is(X, 1+2). X = 3 - control flow The cut is a zero-argument predicate (denoted as !) that forces the evaluation of a series of subgoals on the right hand side of a rule not to be retried if the right hand side succeeds once. The fail predicate is a built-in, which always files. 1) if...then...else: statement :- condition, !, then_part. statement :- else_part. e.g., what happen with the following query where a appears in list L n times? ?- member(a, L). To avoid extra successes of the goal, the cut is used as follows. member(X, [X|T]) :- !. member(X, [H|T]) :- member(X, T). 2) iteration my_loop(NP :- natural(I), i =< N, write(I), nl, I = N, !, fail. ii) Implementation and Progmatics - Execution order > Prolog uses backward chaining Mostly because backward chaining is more efficient than forward chaining. > Resolution is commutative and associative. e.g., 1 A :- B, C. 2 F :- D, E. 3 G :- A, F. (1&3)&2 => G :- B,C,D,E. 1&(3&2) => G :- B,C,D,E. where we use & to denote resolution. Therefore, to prove G we can prove A and F one by one in arbitrary order. Prolog chooses a specific order, namely, from left to right. > Depth-first Backward chaining to search for subgoals amounts to searching a tree of subgoals, and Prolog adopts depth-first. e.g., rainy(seattle). rainy(rochester). cold(rochester). snowy(X) :- rainy(X), cold(X). ?- snowy(C). snowy(C) | snowy(X) | / \ / \ / \ rainy(X) cold(X) /\ \ / \ \ / \ cold(seattle) fails; backtrack; cold(rochester) succeeds. rainy(seattle) rainy(rochester) > Backtracking: if at any point a subgoal fails (cannot be satified), the interpreter returns to the previous subgoal and attempts to satify it in a different way. backtracking is managed using a single stack implementation. > Sequential use of clauses. A Prolog program comprises a sequence of clauses, and the interpreter uses them from first to last. While there exist many alternative routes for searching, prolog picks just one (top-down, left-right). Therefore, it is up to the programmer to write wisely to ensure that programs will terminate. e.g., edge(a,b). edge(b,c). edge(c,d). edge(d,e). edge(b,e). edge(d,f). path(X,X). path(X,Y) :- edge(Z,Y), path(X,Z). what about writing the last rule as follows? edge(a,b). edge(b,c). edge(c,d). edge(d,e). edge(b,e). edge(d,f). path(X,X). path(X,Y) :- path(X,Z), edge(Z,Y). what about reversing the order of the last two clauses? edge(a,b). edge(b,c). edge(c,d). edge(d,e). edge(b,e). edge(d,f). path(X,Y) :- path(X,Z), edge(Z,Y). path(X,X). The interpreter will get into an infinite loop. path(a,a) /\ / \ / \ path(X,Y) path(X,X) /\ / \ / \ path(X,Z) edge(Z,Y) /\ / \ / \ path(X,Y) path(X,X) /\ .... / Why not implement breadth-first search? because it is costly. - limitations (Horn clause only) e.g., to express "every living thing is an animal or a plant" in prolog. animal(X) v plant(X) <- living(X) Horn clauses restrict the goals as single term, but here we have two terms in disjuction. In Prolog, we may say animal(X) :- living(X), not plant(X). plant(X) :- living(X), not animal(X). but the predicate "not" is not what it is supposed to be. (see next) - "Closed world" assumption It assumes the knowledge base constain everything that is true. Since a practical KB contains only limited truth, the goal "not T" can succeed simply because our current KB is insufficient to prove T.