Logic Programming: The Prolog LanguageStephen A. EdwardsColumbia UniversityFall 2008LogicAll 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 E nemy 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 p rograms often involve searching for the solution to aproblem.ÏWhy not provide this search capability as the underlying ideaof the lan gua ge?ÏResult: PrologPrologMostly declarative.Program looks like a declaration of facts plus rules for deducingthings.“Running” the program involves answering questions that refer tothe facts or can be deduced from them.More formally, you provide the axioms, and Prolog tries to provetheorems.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 true given thefacts we have?techer(stephen).nerd(X) :- techer(X).First says techer(stephen) is true. Not helpful.Second says th at we can conclude nerd(X) is true if we canconclude techer(X) is true. More promising.Simple Searchingtecher(stephen).nerd(X) :- techer(X).?- nerd(stephen).Unifying nerd(stephen) with the head of the second rule,nerd(X), we conclude that X = stephen.We’re not done: for the rule to be true, we mu st find that all itsconditions are true. X = stephen, so we want techer(stephen)to hold.This is exactly the fir st clause in the database; we’re satisfied. Thequery 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 we need toestablish 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 BacktrackingXX OX O XX O XO X OX O XO X OXyesX O XO X OXX O XO X OO XX O XO X OO X XnoX O XO X OX OX O XO X OX X OnoX O XO X OXyesX OXX OXX OXX OXX OXX OXX O XOXOXOXOXOXO...XThe Prolog EnvironmentDatabase consists of Horn clauses.Each clause consists ofterms, which may be constants, variables, orstructures.Constants: foo my_Const + 1.43Variables: X Y Everybody My_varStructures: rainy(rochester)teaches(edwards, cs4115)Struct ures and FunctorsA structure consists of a functor followed by an open parenthesis, alist of comma-separated terms, and a close parenthesis: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 the database byunifying t hem.Recursive rules:ÏA constant only unifies with itselfÏTwo structures unify if they have the same functor, the samenumber of arguments, and the corresponding arguments unifyÏA variable unifies with anything but forces an equivalenceUnification ExamplesThe = operator checks whether two structures unify:| ?- a = a.yes % Constant unifies wit h 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 clausein the order they appearh :- t1,..., tnin the databasee = unify(g , h, e)if successful,for each termin the order th ey a ppeart1,..., tn,e = search(tk, e)if all successful, return ereturn noNote: This pseudo-code ignores one very important par t of thesearching process!Order 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 th e query?- path(a, a).path(a,a)path(a,a)=path(X,X)X=ayesGood programming practice: Put the easily-satisfied clauses 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 th e 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 spend much moretime 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 th e 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)Bill and Ted in Prologsuper_band(X) :- on_guitar(X, eddie_van_halen).on_guitar(X, eddie_van_halen) :- triumphant_video(X).triumphant_video(X) :- decent_instruments(X).decent_instruments(X) :- know_how_to_play(X).know_how_to_play(X) :- on_guitar(X, eddie_van_halen).super_band(wyld_stallyns).What will Bill and Ted do?Prolog a s 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 path example.path(X, Y) :- path(X, Z), edge(Z, Y).“To solve P, solve P. . .”Prolog a s an Imperative Languagego :- print(hello_), print(world).?- go.hello_worldyesCutsWays to shape the behavior of the
View Full Document
Unlocking...