Logic Programming: PrologCOMS W4115Prof. Stephen A. EdwardsSpring 2003Columbia UniversityDepartment of Computer ScienceLogicAll Caltech graduates are nerds.Stephen is a Caltech graduate.Is Stephen a nerd?PrologAll Caltech graduates are nerds.Stephen is a Caltech graduate.Is Stephen a nerd?nerd(X) :- techer(X).techer(stephen).?- nerd(stephen).yesMore Logic“My Enemy’s Enemy is My Friend.”friend(X,Z) :-enemy(X,Y), enemy(Y,Z).enemy(stephen, ryan).enemy(ryan, jordan).enemy(jordan, jacob).?- friend(stephen,jordan).yes?- friend(stephen,X).X = jordan?- friend(X, Y).X = stephen Y = jordanX = ryan Y = jacobThe Basic Idea of Prolog•AI programs often involve searching for the solution toa problem.•Why not provide this search capability as theunderlying idea of the language?•Result: PrologPrologMostly declarative.Program looks like a declaration of facts plus rules fordeducing things.“Running” the program involves answering questions thatrefer to the factsor can be deduced from them.More formally, you provide the axioms, and Prolog tries toprove theorems.Prolog ExecutionFactsnerd(X) :- techer(X).techer(stephen).↓Query?- nerd(stephen). → Search (Execution)↓ResultyesSimple SearchingStarts with the query:?- nerd(stephen).Can we convince ourselves that nerd(stephen) is truegiven the facts we have?techer(stephen).nerd(X) :- techer(X).First says techer(stephen) is true. Not helpful.Second says that we can conclude nerd(X) is true if wecan conclude techer(X) is true. More promising.Simple Searchingtecher(stephen).nerd(X) :- techer(X).?- nerd(stephen).Unifying nerd(stephen) with the head of the secondrule, nerd(X), we conclude that X = stephen.We’re not done: for the rule to be true, we must find thatall its conditions are true. X = stephen, so we wanttecher(stephen) to hold.This is exactly the first clause in the database; we’resatisfied. The query is simply true.More Clever Searchingtecher(stephen).techer(todd).nerd(X) :- techer(X).?- nerd(X).“Tell me about everybody who’s provably a nerd.”As before, start with query. Rule only interesting thing.Unifying nerd(X) with nerd(X) is vacuously true, so weneed to establish techer(X).More Clever Searchingtecher(stephen).techer(todd).nerd(X) :- techer(X).?- nerd(X).Unifying techer(X) with techer(stephen) succeeds,setting X = stephen, but we’re not done yet.Unifying techer(X) with techer(todd) also succeeds,setting X = todd, but we’re still not done.Unifying techer(X) with nerd(X) :- fails, returning no.More Clever Searching> ˜/tmp/beta-prolog/bpBeta-Prolog Version 1.2 (C) 1990-1994.| ?-[user].|:techer(stephen).|:techer(todd).|:nerd(X) :- techer(X).|:ˆDyes| ?-nerd(X).X = stephen?;X = todd?;no| ?-Order Matters> ˜/tmp/beta-prolog/bpBeta-Prolog Version 1.2 (C) 1990-1994.| ?-[user].|:techer(todd).|:techer(stephen).|:nerd(X) :- techer(X).|:ˆDyes| ?-nerd(X).X = todd?;Todd returned firstX = stephen?;no| ?-Searching and BacktrackingXXOXOXXOXOXOXOXOXOXyesXOXOXOXXOXOXOOXXOXOXOOXXnoXOXOXOXOXOXOXOXXOnoXOXOXOXyesXOXXOXXOXXOXXOXXOXX O XOXOXOXOXOXO. . .XThe Prolog EnvironmentDatabase consists of clauses.Each clause consists ofterms, which may be constants,variables, or structures.Constants: foo my Const + 1.43Variables: X Y Everybody MyvarStructures: rainy(rochester)teaches(edwards, cs4115)Structures and FunctorsA structure consists of a functor followed by an openparenthesis, a list of comma-separated terms, and a closeparenthesis:bin_‘‘Functor’’tree(paren must follow immediatelyfoo, bin_tree(bar, glarch) )What’s a structure? Whatever you like.A predicate nerd(stephen)A relationship teaches(edwards, cs4115)A data structure bin(+, bin(-, 1, 3), 4)UnificationPart of the search procedure that matches patterns.The search attempts to match a goal with a rule in thedatabase byunifying them.Recursive rules:•A constant only unifies with itself•Two structures unify if they have the same functor, thesame number of arguments, and the correspondingarguments unify•A variable unifies with anything but forces anequivalenceUnification ExamplesThe = operator checks whether two structures unify:| ?- a = a.yes % Constant unifies with itself| ?- a = b.no % Mismatched constants| ?- 5.3 = a.no % Mismatched constants| ?- 5.3 = X.X = 5.3?; % Variables unifyno| ?-foo(a,X) = foo(X,b).no % X=a required, but inconsistent| ?- foo(a,X) = foo(X,a).X = a?; % X=a is consistentno| ?-foo(X,b) = foo(a,Y).X = aY = b?; % X=a, then b=Yno| ?-foo(X,a,X) = foo(b,a,c).no % X=b required, but inconsistentThe Searching Algorithmsearch(goal g, variables e)for each clause h :- t1, . . . , tnin the databasee = unify(g, h, e)if successful,for each term t1, . . . , tn,e = search(tk, e)if all successful, return ereturn noOrder matterssearch(goal g, variables e)for each clauseIn the order they appearh :- t1, . . . , tnin the databasee = unify(g, h, e)if successful,for each termIn the order they appeart1, . . . , tn,e = search(tk, e)if all successful, return ereturn noOrder Affects Efficiencyedge(a, b). edge(b, c).edge(c, d). edge(d, e).edge(b, e). edge(d, f).path(X, X).path(X, Y) :-edge(X, Z), path(Z, Y).Consider the query?- path(a, a).path(a,a)path(a,a)=path(X,X)X=ayesGood programming practice: Put the easily-satisfiedclauses first.Order Affect Efficiencyedge(a, b). edge(b, c).edge(c, d). edge(d, e).edge(b, e). edge(d, f).path(X, Y) :-edge(X, Z), path(Z, Y).path(X, X).Consider the query?- path(a, a).path(a,a)path(a,a)=path(X,Y)X=a Y=aedge(a,Z)edge(a,Z)=edge(a,b)Z=bpath(b,a)Will eventually produce the right answer, but will spendmuch more time doing so.Order can cause Infinite Recursionedge(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).Consider the query?- path(a, a).path(a,a)Goalpath(a,a)=path(X,Y)UnifyX=a Y=aimpliespath(a,Z)Subgoalpath(a,Z)=path(X,Y)X=a Y=Zpath(a,Z)path(a,Z)=path(X,Y)X=a Y=Zedge(Z,a)edge(Z,a)Like LL(k) grammars.Prolog as an Imperative LanguageA declarative statement such asP if Q and R and Scan also be interpreted procedurally asTo solve P, solve Q, then R, then S.This is the problem with the last example.path(X, Y) :- path(X, Z), edge(Z, Y).“To solve P, solve P...”Prolog as an Imperative Languagego :- print(hello_), print(world).?- go.hello_worldyesCutsWays to shape the behavior of the search:•Modify clause and term order.Can affect efficiency, termination.•“Cuts”Explicitly forbidding further backtracking.CutsWhen the search reaches a cut (!), it does no
View Full Document
Unlocking...