The Logic Programming Paradigm and Prolog

1、arXiv:cs/0107013v2[cs.PL]12Jul2001TheLogicProgrammingParadigmandPrologKrzysztofR.AptAbstractThisisatutorialonlogicprogrammingandPrologappropriateforacourseonprogramminglanguagesforstudentsfamiliarwithimperativeprogramming.Contents1HistoryofLogicProgramming32BriefOverviewoftheLogicProgrammingParadigm43EquationsSolvedbyUnificationasAtomicActions63.1Terms.................................63.2Substitutions.............................73.3MostGeneralUnifiers........................83.4AUnificationAlgori。

2、thm.......................94ClausesasPartsofProcedureDeclarations114.1SimpleClauses............................114.2ComputationProcess.........................124.3Clauses................................135Prolog’sApproachtoProgramming155.1MultipleUsesofaSingleProgram.................155.2LogicalVariables...........................166ArithmeticsinProlog206.1ArithmeticOperators........................206.2ArithmeticComparisonRelations..................216.3EvaluationofArithmeticExpressions.......。

3、.........237Control,AmbivalentSyntaxandMeta-Variables257.1Cut..................................257.2AmbivalentSyntaxandMeta-variables...............267.3ControlFacilities...........................287.4NegationasFailure..........................307.5Higher-OrderProgrammingandMeta-ProgramminginProlog..3118AssessmentofProlog339BibliographicRemarks3610Summary3621HistoryofLogicProgrammingThelogicprogrammingparadigmhasitsrootsinautomatedtheoremprovingfromwhichittookthenotionofadeduction.Whatisnewisth。

4、atintheprocessofdeductionsomevaluesarecomputed.Thecreationofthisprogrammingparadigmistheoutcomeofalonghistorythatformostofitscourseranwithinlogicandonlylaterinsidecomputerscience.Logicprogrammingisbasedonthesyntaxoffirst-orderlogic,thatwasoriginallyproposedinthesecondhalfof19thcenturybyGottlobFregeandlatermodifiedtothecurrentlyusedformbyGiuseppePeanoandBertrandRussell.Inthe1930sKurtG¨odelandJacquesHerbrandstudiedthenotionofcom-putabilitybasedonderivations.Theseworkscanbeviewedastheoriginofthe“comp。

5、utationasdeduction”paradigm.Additionally,HerbranddiscussedinhisPhDthesisasetofrulesformanipulatingalgebraicequationsontermsthatcanbeviewednowasasketchofaunificationalgorithm.Somethirtyyearslaterin1965AlanRobinsonpublishedhisfundamentalpaper[9]thatliesatthefoundationsofthefieldofautomateddeduction.Inthispaperheintroducedtheresolutionprinciple,thenotionofunificationandaunificationalgorithm.Usingtheresolutionmethodonecanprovetheoremsoffirst-orderlogic,butanotherstepwasneededtoseehowonecouldcomputewithin。

6、thisframework.Thiswaseventuallyachievedin1974byRobertKowalskiinhispaper[6]inwhichlogicprogramswitharestrictedformofresolutionwereintroduced.ThedifferencebetweenthisformofresolutionandtheoneproposedbyRobinsonisthatthesyntaxismorerestricted,butprovingnowhasasideeffectintheformofasatisfyingsubstitution.Thissubstitutioncanbeviewedasaresultofacomputationandconsequentlycertainlogicalformulascanbeinterpretedasprograms.Inparallel,AlainColmerauerwithhiscolleaguesworkedonaprogramminglanguagefornaturallangua。

7、geprocessingbasedonautomatedtheoremproving.ThisultimatelyledtocreationofPrologin1973.KowalskiandColmerauerwithhisteamofteninteractedintheperiod1971–1973.Thisinfluencedtheirviewsandhelpedthemtocrystallizetheideas.Prologcanbeseenasapracticalrealizationoftheideaoflogicprograms.Itstartedasaprogramminglanguageforapplicationsinnaturallanguagepro-cessing,butsoonafteritwasfoundthatitcanbeusedasageneralpurposeprogramminglanguage,aswell.Anumberofotherattemptstorealizethecom-putationasdeductionparadigmwerep。

8、roposedaroundthesametime,notablybyCordellGreenandCarlHewitt,butthelogicprogrammingproposal,prob-ablybecauseitwasthesimplestandmostversatile,becamemostsuccessful.Originally,PrologwasimplementedbyPhilippeRoussel,acolleagueofColmerauer,intheformofaninterpreterwritteninAlgol-W.AnimportantstepforwardwasachievedbyDavidH.Warrenwhoproposedin1983anab-stractmachine,nowcalledWAM(WarrenAbstractMachine),thatconsistsofamachinearchitecturewithaninstructionsetwhichservesasatargetformachineindependentPrologcompi。

9、lers.WAMbecameastandardbasisforimplementingPrologandotherlogicprogramminglanguages.Thelogicprogrammingparadigminfluencedanumberofdevelopmentsin3computerscience.Alreadyintheseventiesitledtothecreationofdeductivedatabasesthatextendtherelationaldatabasesbyprovidingdeductioncapabil-ities.AfurtherimpetustothesubjectcameunexpectedlyfromtheJapaneseFifthGenerationProjectforintelligentcomputingsystems(1982–1991)inwhichlogicprogrammingwaschosenasitsbasis.Morerecently,thisparadigmledtoconstraintlogicprogram。

10、mingthatrealizesageneralapproachtocomputinginwhichtheprogrammingprocessislimitedtoagenerationofconstraints(re-quirements)andasolutionofthem,andtoinductivelogicprogramming,alogicbasedapproachtomachinelearning.TheaboveaccountofhistoryoflogicprogrammingandPrologshowsitsrootsinlogicandautomateddeduction.Infact,ColmerauerandRousselwritein[3]:“ThereisnoquestionthatPrologisessentiallyatheoremprover‘`alaRobinson.’Ourcontributionwastotransformthattheoremproverintoaprogramminglanguage.”Thisoriginofthelogic。