Introduction to Prolog

IntroductiontoPrologWhatisProlog?{Prolog(ProgramminginLogic)isaprogramminglanguageforAIandnon-numericalprogrammingingeneral.Whatisnew?{Conventional(wellestablished,standard)languagesareprocedurallyoriented,whilePrologintroducesthedeclarativeview.1.SyntaxofProlog(a)clausesAPrologprogramconsistsofclauses.APrologclauseisaHornclause.Eachclauseterminateswithafullstop.Prologclausesareofthreetypes:rules,facts,andquestions.Example1:rule{ospring(X,Y):-parent(Y,X).Example2:fact{parent(tom,ann).Example3:questions{parent(X,ann).(b)proceduresAgroupofclauseswhichtheheadofeachclausearethesameiscalledaprocedure.Example:connects(san_francisco,oakland,bart_tran).connects(san_francisco,fremont,bart_tran).connects(concord,daly_city,bart_tran).(c)rulesAruleisaclausewithoneormoreconditions.Foraruletobetrue,allofitsconditionsmustalsobetrue.Theright-handsideoftheruleisaconditionandtheleft-handsideoftheruleistheconclusion.The‘:-’signmeans‘if’.TheclauseinExample1canbestatedasXisanospringofYifYisaparentofX.Theleft-handsideiscalledtheheadoftheruleandtheright-handsideiscalledthebodyoftherule.Thebodyofaruleisalistofgoalsseparatedbycommas.Commasareunderstoodasconjunctions.Example:p:-q,r,s,t.meanspistrueifqandrandsandtaretrue.(d)factsFactsarealwaysunconditionallytrue.Itonlyhasaheadpart(theconclusion)withanemptybody.1Example:has(student,books).(e)questionsQuestionsarequeriesforretrievingfactsthroughrules.Itonlyhasthebody(thegoals).Example:y(penguin).(f)argumentsArgumentscanbeanatom,anumber,avariable,orastructure.(g)atomsAtomsareconcreteobjects(butnumbersareNOTatoms).Therstletterofanatomisalwaysasmallletter.Stringsofletters:tom,nil,x25,x25AB,x,xy,toppartStringsofspecialcharacters:|,===,...,.:.(withcaution)Quotedstrings:’Tom’,’SouthAmerica’(h)numbersThesyntaxofintegersissimpleexceptonemustrememberthattherangeofintegersislimitedtoaninterval,inSICSTUSProlog,between-16383to16383.Examples:3.1416,-0.001,22.223,100(i)variablesVariablesaregeneralobjects.TherstletterofavariableisalwaysaCapitalletter.Example:XandYinExample1.Variablescanbesubstitutedbyanotherobject(becomesinstantiated).variablesareassumedtobeuniversallyquantied(forall).Example:ForallXandY,ifXisaospringofYthenYisaparentofX(Example1).Whenavariableappearsinaclauseonlyonce,itiscalledanonymousvariablewhichisrepresentedbyaaloneorstartwithit.Examples:,23,X,varAvariableisinstantiatedifitisboundtoanon-variableterm.Thatis,toanatom,anumber,orastructure.(j)structures(functions)Structuresarefunctorsthathavezeroormorearguments.Example:startdate(6,may,1996).Example:triangle(point(4,2),point(6,4),point(7,1)).Thestartdateandpointarecalledfunctor,andtriangleiscalledtheprinciplefunctor.Afunctorisdenedbytwothings:nameandarity(numberofarguments).Thegeneralformofafunctorisfunctor/arity.Examples:startdate/3,triangle/3,point/22(k)predicates{afunctorthatspeciessomerelationshipexistingintheproblemdomain.Thedierencebetweenapredicateandafunctionisthatthefunctionwillreturnavaluetothecallingprocedure,whileapredicatedoesnotreturnsvaluebutatrueorfalsestatement.Examples:endofle/0andinteger/1arebuilt-inpredicatesBuilt-inpredicatescomewiththesystemwhichdonotneedtobecompiledorconsultedbeforeitisused.(l)recursiveArunningprocedurecallsitselfwithdierentargumentsandforthepurposeofsolvingsomesubsetoftheoriginalproblem.RecursiveisoneofthefundamentalprinciplesofprogramminginProlog.Example:predecessor(X,Z):-parent(X,Z).predecessor(X,Z):-parent(X,Y),predecessor(Y,Z).(m)commentsExample:/*thisisacomment*/Example:%Thisisalsoacomment2.matchingGiventwoterms,wesaythattheymatchif:{theyareidenticalor{theybecomeidenticalaftertheyareinstantiatedIftwotermsarematchthentheprocesssucceeds.Otherwise,theprocessfails.Examples(arithmeticexpressions):6=:=6;6=n=7Examples(others):six==six,sixn==seven3.OrderofClausesandGoalsdangerofindeniteloopingExample1:p:-p.Example2:ThemonkeyandthebananaprograminAssignment#1orderofclausesisimportantExample3:likes(Person,Something):-animal(Something).3likes(mary,snake):-!,fail.Themostgeneralclauseshouldbetriedlastwhilethemostspecicclauseshouldbetriedrst.Example4:example(1,2,3,4,5):-do_p1.example(1,2,3,4,_):-do_p2.example(1,2,3,_,_):-do_p3.example(1,2,_,_,_):-do_p4.example(1,_,_,_,_):-do_p5.example(_,_,_,_,_):-do_p6.DeclarativeandProceduralMeaningofPrologPrograms1.thedeclarativemeaningconcernedonlywiththerelationsdenedbytheprogramanddetermineswhatwillbetheoutputoftheprogramdetermineswhetheragivengoalistrueandifso,forwhatvaluesofvariablesitistrue.GivenagoalG,thedeclarativemeaningsays:Gistrueifandonlyif{thereisaclauseCintheprogramandthereisaninstanceIofCsuchthat(1)theheadofIisidenticaltoGand(2)allthegoalsinthebodyofIaretrueExample:givenG=hasachild(peter).TheprogramhasaclauseC=hasachild(X):-parent(X,Y).andafactparent(peter,tom).Thenhasachild(peter):-parent(peter,Z).andparent(peter,tom).isaninstanceofG2.theproceduralmeaningspecieshowProloganswersquestions.meanstotrytosatisfyalistofgoals4outputasuccessorfailureindicatorandaninstantiat