Executing PrologExecuting Prologldots Executing Prologldots Executing PrologNorthern Exposure ExampleMaggie (Janine Turner)Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Northern Exposure Exampleldots Readings and ReferencesProlog So Farldots520 —Spring 2008 — 44CSc 520Principles of ProgrammingLanguages44 : Logic Programming — Executing PrologChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 44Executing PrologNow that we know about matching, we can take acloser look at how Prolog tries to satisfy goals.In general, to solve a goalG = G1, G2, · · · , Gm,Prolog will first try to solve the sub-goal G1.It solves a sub-goal G1it will look for a ruleHi:- B1, · · · , Bnin the database, such that G1and Hiwill match.Any variable substitutions resulting from the match willbe stored in a variable θ.[2]520 —Spring 2008 — 44Executing Prolog...A new goal will be constructed by replacing G1withB1, · · · , Bn, yieldingG′= B1, · · · , Bn, G2, · · · , Gm.If n = 0 the new goal will be shorter and we’ll be onestep closer to a solution to G!Any new variable bindings from θ are applied to the newgoal, yielding G′′.We recursively try to find a solution to G′′.[3]520 —Spring 2008 — 44Executing Prolog...FUNC Execute (G = G1, G2, · · · , Gm; Result);IF IsEmpty(G) THEN Result := YesELSEResult := No;i := 1;WHILE Result=No & i ≤ NoOfClauses DOClause := Hi:- B1, · · · , Bn;IF Unify(G1, Clause, θ) THENG′:= B1, · · · , Bn, G2, · · · , Gm;G′′:= substitute(G′, θ);Execute(G′′, Result);ENDIF;i := i + 1;ENDDOENDIF[4]520 —Spring 2008 — 44Executing PrologMatch?Unify(Hi, G1)Scan databaseEmpty?G1, G2, ..., GmGoal(2) H2 :− B1, ..., Bn(3) H3 :− C1, ..., Cn(1) H1 :− A1, ..., AnDatabase......NoYesNoYesSucceedHi :− X1, ..., XnNo more HifailReplace G1 by X1,...,XnX1,...,Xn,G2,...,GmX1’,...,Xn’,G2’,...,Gm’Substitute vars from θθ = {· · · }[5]520 —Spring 2008 — 44Northern Exposure Example% From the Northern Exposure FAQ% friend(of, kind(name, regular)).friend(maggie, person(eve, yes)).friend(maggie, moose(morty, yes)).friend(maggie, person(harry, no)).friend(maggie, person(bruce, no)).friend(maggie, person(glenn, no)).friend(maggie, person(dave, no)).friend(maggie, person(rick, no)).friend(maggie, person(mike, yes)).friend(maggie, person(joel, yes)).[6]520 —Spring 2008 — 44Maggie (Janine Turner)[7]520 —Spring 2008 — 44Northern Exposure Example...cause of death(morty, copper deficiency).causeof death(harry, potato salad).causeof death(bruce, fishing accident).causeof death(glenn, missile).causeof death(dave, hypothermia).causeof death(rick, hit by satellite).causeof death(mike, none yet).causeof death(joel, none yet).male(morty). male(harry). male(bruce).male(glenn). male(dave). male(rick).male(mike). male(joel). female(eve).[8]520 —Spring 2008 — 44Northern Exposure Example...alive(X) :- cause of death(X, none yet).pastime(eve, hypochondria).pastime(mike, hypochondria).pastime(X, golf) :- job(X,doctor).job(mike, lawyer). job(adam, chef).job(maggie, pilot). job(joel, doctor).?- friend(maggie, person(B, yes)),male(B),alive(B),pastime(B, golf).[9]520 —Spring 2008 — 44Northern Exposure Example...Match?Unify(Hi, G1)Scan databaseHi :− X1, ..., Xnmale(B), alive(B),pastime(B, golf).friend(maggie, p(B, yes)), Empty?male(eve), alive(eve),pastime(eve, golf).friend(m,p(eve,yes)).friend(m,m(morty,yes)).friend(m,p(harry,no)).friend(m,p(mike,yes)).friend(m,p(joel,yes)).cause_od(mike,none).cause_od(joel,none).male(mike).male(joel).female(eve).pastime(X,golf):−job(X,doctor).job(adam,chef).job(joel,doctor).alive(X):−cause_od(X, none).pastime(eve, hypocondriac).pastime(mike, hypocondriac).HiNoYesNoYesSucceedfailNo more HiG1Replace G1 by <empty>θ = {B=eve}Substitute vars from θ[10]520 —Spring 2008 — 44Northern Exposure Example...Match?Unify(Hi, G1)Scan databaseEmpty?male(eve), alive(eve),pastime(eve, golf).failfriend(m,p(eve,yes)).friend(m,m(morty,yes)).friend(m,p(harry,no)).friend(m,p(mike,yes)).friend(m,p(joel,yes)).cause_od(mike,none).cause_od(joel,none).male(mike).male(joel).female(eve).pastime(X,golf):−job(X,doctor).job(adam,chef).job(joel,doctor).alive(X):−cause_od(X, none).pastime(mike, hypocondriac).pastime(eve, hypocondriac).(1)?NoYesNoYesSucceedNo more HiG1[11]520 —Spring 2008 — 44Northern Exposure Example...Match?Unify(Hi, G1)Scan databasemale(B), alive(B),pastime(B, golf).friend(maggie, p(B, yes)), Empty?Hi :− X1, ..., XnNoYesNoYesSucceedfailNo more HiG1friend(m,p(eve,yes)).friend(m,m(morty,yes)).friend(m,p(harry,no)).friend(m,p(mike,yes)).friend(m,p(joel,yes)).cause_od(mike,none).cause_od(joel,none).male(mike).male(joel).female(eve).pastime(X,golf):−job(X,doctor).job(adam,chef).job(joel,doctor).alive(X):−cause_od(X, none).pastime(eve, hypocondriac).pastime(mike, hypocondriac).HiReplace G1 by <empty>pastime(mike, golf).male(mike),alive(mike),θ = {B=mike}Substitute vars from θ[12]520 —Spring 2008 — 44Northern Exposure Example...Match?Unify(Hi, G1)Scan databaseEmpty?friend(m,p(eve,yes)).friend(m,m(morty,yes)).friend(m,p(harry,no)).friend(m,p(mike,yes)).friend(m,p(joel,yes)).cause_od(mike,none).cause_od(joel,none).male(mike).male(joel).female(eve).pastime(X,golf):−job(X,doctor).job(adam,chef).job(joel,doctor).alive(X):−cause_od(X, none).pastime(eve, hypocondriac).pastime(mike, hypocondriac).Hi(1)pastime(mike, golf).alive(mike),NoYesNoYesSucceedmale(mike), alive(mike),pastime(mike, golf).failNo more HiG1Hi :− X1, ..., XnReplace G1 by <empty>θ = {}Substitute vars from θ[13]520 —Spring 2008 — 44Northern Exposure Example...Match?Unify(Hi, G1)Scan databaseEmpty?(2)friend(m,p(eve,yes)).friend(m,m(morty,yes)).friend(m,p(harry,no)).friend(m,p(mike,yes)).friend(m,p(joel,yes)).cause_od(mike,none).cause_od(joel,none).male(mike).male(joel).female(eve).pastime(X,golf):−job(X,doctor).job(adam,chef).job(joel,doctor).alive(X):−cause_od(X, none).pastime(eve, hypocondriac).pastime(mike, hypocondriac).Hi(1)pastime(mike, golf).cause_od(mike,
View Full Document
Unlocking...