Backward chaining example Logic programming Sound bite:computation as inference on logical KBs tity p in KB 567 ode nroblem Should bee Backward chaining example Prolog systems with Horn cl bells whistle Program=set of clauses=head:-literal,..literal Properties of backward chaining Prolog examples Depth-first recursive e图cmo.3.ts No need to kop over: Appending two lists to produce a third A-1,21B-0 Backward chaining example Missile(M1) Owns(Nono,M1) Criminal(West) Missile(y) American(West) Weapon(y) Sells(West,M1,z) { y/M1} { } { z/Nono } Hostile(z) {x/West, y/M1, z/Nono} Chapter 9 37 Backward chaining example Hostile(Nono) Missile(M1) Owns(Nono,M1) Enemy(Nono,America) Criminal(West) Missile(y) American(West) Weapon(y) Sells(West,M1,z) { y/M1} { } { } { } { } { z/Nono } {x/West, y/M1, z/Nono} Chapter 9 38 Properties of backward chaining Depth-first recursive proof search: space is linear in size of proof Incomplete due to infinite loops ⇒ fix by checking current goal against every goal on stack Inefficient due to repeated subgoals (both success and failure) ⇒ fix using caching of previous results (extra space!) Widely used (without improvements!) for logic programming Chapter 9 39 Logic programming Sound bite: computation as inference on logical KBs Logic programming Ordinary programming 1. Identify problem Identify problem 2. Assemble information Assemble information 3. Tea break Figure out solution 4. Encode information in KB Program solution 5. Encode problem instance as facts Encode problem instance as data 6. Ask queries Apply program to data 7. Find false facts Debug procedural errors Should be easier to debug Capital(NewY ork,US) than x := x + 2 ! Chapter 9 40 Prolog systems Basis: backward chaining with Horn clauses + bells & whistles Widely used in Europe, Japan (basis of 5th Generation project) Compilation techniques ⇒ approaching a billion LIPS Program = set of clauses = head :- literal1, . . . literaln. criminal(X) :- american(X), weapon(Y), sells(X,Y,Z), hostile(Z). Efficient unification by open coding Efficient retrieval of matching clauses by direct linking Depth-first, left-to-right backward chaining Built-in predicates for arithmetic etc., e.g., X is Y*Z+3 Closed-world assumption (“negation as failure”) e.g., given alive(X) :- not dead(X). alive(joe) succeeds if dead(joe) fails Chapter 9 41 Prolog examples Depth-first search from a start state X: dfs(X) :- goal(X). dfs(X) :- successor(X,S),dfs(S). No need to loop over S: successor succeeds for each Appending two lists to produce a third: append([],Y,Y). append([X|L],Y,[X|Z]) :- append(L,Y,Z). query: append(A,B,[1,2]) ? answers: A=[] B=[1,2] A=[1] B=[2] A=[1,2] B=[] Chapter 9 42