The Logic Programming Paradigm and Prolog

arXiv:cs/0107013v2[cs.PL]12Jul2001TheLogicProgrammingParadigmandPrologKrzysztofR.AptAbstractThisisatutorialonlogicprogrammingandPrologappropriateforacourseonprogramminglanguagesforstudentsfamiliarwithimperativeprogramming.Contents1HistoryofLogicProgramming32BriefOverviewoftheLogicProgrammingParadigm43EquationsSolvedbyUnificationasAtomicActions63.1Terms.................................63.2Substitutions.............................73.3MostGeneralUnifiers........................83.4AUnificationAlgorithm.......................94ClausesasPartsofProcedureDeclarations114.1SimpleClauses............................114.2ComputationProcess.........................124.3Clauses................................135Prolog’sApproachtoProgramming155.1MultipleUsesofaSingleProgram.................155.2LogicalVariables...........................166ArithmeticsinProlog206.1ArithmeticOperators........................206.2ArithmeticComparisonRelations..................216.3EvaluationofArithmeticExpressions................237Control,AmbivalentSyntaxandMeta-Variables257.1Cut..................................257.2AmbivalentSyntaxandMeta-variables...............267.3ControlFacilities...........................287.4NegationasFailure..........................307.5Higher-OrderProgrammingandMeta-ProgramminginProlog..3118AssessmentofProlog339BibliographicRemarks3610Summary3621HistoryofLogicProgrammingThelogicprogrammingparadigmhasitsrootsinautomatedtheoremprovingfromwhichittookthenotionofadeduction.Whatisnewisthatintheprocessofdeductionsomevaluesarecomputed.Thecreationofthisprogrammingparadigmistheoutcomeofalonghistorythatformostofitscourseranwithinlogicandonlylaterinsidecomputerscience.Logicprogrammingisbasedonthesyntaxoffirst-orderlogic,thatwasoriginallyproposedinthesecondhalfof19thcenturybyGottlobFregeandlatermodifiedtothecurrentlyusedformbyGiuseppePeanoandBertrandRussell.Inthe1930sKurtG¨odelandJacquesHerbrandstudiedthenotionofcom-putabilitybasedonderivations.Theseworkscanbeviewedastheoriginofthe“computationasdeduction”paradigm.Additionally,HerbranddiscussedinhisPhDthesisasetofrulesformanipulatingalgebraicequationsontermsthatcanbeviewednowasasketchofaunificationalgorithm.Somethirtyyearslaterin1965AlanRobinsonpublishedhisfundamentalpaper[9]thatliesatthefoundationsofthefieldofautomateddeduction.Inthispaperheintroducedtheresolutionprinciple,thenotionofunificationandaunificationalgorithm.Usingtheresolutionmethodonecanprovetheoremsoffirst-orderlogic,butanotherstepwasneededtoseehowonecouldcomputewithinthisframework.Thiswaseventuallyachievedin1974byRobertKowalskiinhispaper[6]inwhichlogicprogramswitharestrictedformofresolutionwereintroduced.ThedifferencebetweenthisformofresolutionandtheoneproposedbyRobinsonisthatthesyntaxismorerestricted,butprovingnowhasasideeffectintheformofasatisfyingsubstitution.Thissubstitutioncanbeviewedasaresultofacomputationandconsequentlycertainlogicalformulascanbeinterpretedasprograms.Inparallel,AlainColmerauerwithhiscolleaguesworkedonaprogramminglanguagefornaturallanguageprocessingbasedonautomatedtheoremproving.ThisultimatelyledtocreationofPrologin1973.KowalskiandColmerauerwithhisteamofteninteractedintheperiod1971–1973.Thisinfluencedtheirviewsandhelpedthemtocrystallizetheideas.Prologcanbeseenasapracticalrealizationoftheideaoflogicprograms.Itstartedasaprogramminglanguageforapplicationsinnaturallanguagepro-cessing,butsoonafteritwasfoundthatitcanbeusedasageneralpurposeprogramminglanguage,aswell.Anumberofotherattemptstorealizethecom-putationasdeductionparadigmwereproposedaroundthesametime,notablybyCordellGreenandCarlHewitt,butthelogicprogrammingproposal,prob-ablybecauseitwasthesimplestandmostversatile,becamemostsuccessful.Originally,PrologwasimplementedbyPhilippeRoussel,acolleagueofColmerauer,intheformofaninterpreterwritteninAlgol-W.AnimportantstepforwardwasachievedbyDavidH.Warrenwhoproposedin1983anab-stractmachine,nowcalledWAM(WarrenAbstractMachine),thatconsistsofamachinearchitecturewithaninstructionsetwhichservesasatargetformachineindependentPrologcompilers.WAMbecameastandardbasisforimplementingPrologandotherlogicprogramminglanguages.Thelogicprogrammingparadigminfluencedanumberofdevelopmentsin3computerscience.Alreadyintheseventiesitledtothecreationofdeductivedatabasesthatextendtherelationaldatabasesbyprovidingdeductioncapabil-ities.AfurtherimpetustothesubjectcameunexpectedlyfromtheJapaneseFifthGenerationProjectforintelligentcomputingsystems(1982–1991)inwhichlogicprogrammingwaschosenasitsbasis.Morerecently,thisparadigmledtoconstraintlogicprogrammingthatrealizesageneralapproachtocomputinginwhichtheprogrammingprocessislimitedtoagenerationofconstraints(re-quirements)andasolutionofthem,andtoinductivelogicprogramming,alogicbasedapproachtomachinelearning.TheaboveaccountofhistoryoflogicprogrammingandPrologshowsitsrootsinlogicandautomateddeduction.Infact,ColmerauerandRousselwritein[3]:“ThereisnoquestionthatPrologisessentiallyatheoremprover‘`alaRobinson.’Ourcontributionwastotransformthattheoremproverintoaprogramminglanguage.”Thisoriginofthelogic