搜索
FunctionalComputationsinLogicPrograms†SaumyaK.DebrayDepartmentofComputerScienceTheUniversityofArizonaTucson,AZ85721DavidS.WarrenDepartmentofComputerScienceStateUniversityofNewYorkatStonyBrookStonyBrook,NY11794Abstract:Whiletheabilitytosimulatenondeterminismandcomputemultiplesolutionsforasinglequeryisapowerfulandattractivefeatureoflogicprogramminglanguages,itisexpensiveinbothtimeandspace.Sinceprogramsinsuchlanguagesareveryoftenfunctional,i.e.donotproducemorethanonedistinctsolutionforasingleinput,thisoverheadisespeciallyundesirable.Thispaperdescribeshowpro-gramsmaybeanalyzedstaticallytodeterminewhichliteralsandpredicatesarefunctional,andhowtheprogrammaythenbeoptimizedusingthisinformation.Ournotionof‘‘functionality’’subsumesthenotionof‘‘determinacy’’thathasbeenconsideredbyvariousresearchers.Ouralgorithmislessreliantonlanguagefeaturessuchasthecut,andthusextendsmoreeasilytoparallelexecutionstrategies,thanothersthathavebeenproposed.CategoriesandSubjectDescriptors:D.3[Software]:ProgrammingLanguages;D.3.2[ProgrammingLanguages]:LanguageClassifications−nonprocedurallanguages;D.3.4[ProgrammingLanguages]:Processors−compilers,optimization;I.2[ComputingMethodologies]:ArtificialIntelligence;I.2.3[ArtificialIntelligence]:DeductionandTheoremProving−logicprogramming.hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh†ApreliminaryversionofthispaperwaspresentedattheThirdInternationalConferenceonLogicProgramming,London,July1986.ThisworkwassupportedinpartbytheNationalScienceFoundationundergrantnumberDCR-8407688.1.IntroductionInrecentyears,therehasbeenagreatdealofinterestinlogicprogramminglanguages,thebestknownofthesebeingProlog.Theabilitytosimulatenondeterminismisapowerfulfeatureofsuchlanguages.Itpermitsthesuccinctandreadilyunderstandableexpressionoflogicalalternativesthatrequirecomplexconstructsinmanyprogramminglanguages.However,theadditionalruntimesupportneededforthis,e.g.theabilitytorememberpreviousstatesandbacktracktothemonfailure,canincurasignificantover-head.Thisisespeciallyundesirablesincepredicatesinlogicprogramsareveryoftenfunctional,anddonotneedthisgeneralizedbacktrackingability.Knowledgeaboutthefunctionalityofpredicatescanbeusedtomakesignificantimprovementsinthespaceandtimerequirementsofaprogram.Knowingthatapredicateisfunctionalmaymakeitpossible,forexample,toavoidhavingtorecordasystemstatetobacktrackto,effectearlyreclamationofspaceontheruntimestack,andavoidunnecessarysearch.Traditionally,themeansofcontrollingProlog’ssearchhasbeenthroughcutsinsertedbythepro-grammer.This,however,makesprogramshardertounderstandandreasonaboutdeclaratively[20,22].Analternativeistotreatthecutasalow-levelprimitivethatshouldbeusedinfrequentlybytheprogram-mer,ifatall,butwhichmaybeintroducedbycompilersinthecourseofgeneratingoptimizedcodeforexecutioninasequentialenvironment.Inthisview,thecutisseen,notasalanguagefeatureintrinsictologicprogramming,butasanimplementationfeatureofsequentialProlog.(Itisnotobviouswhethercutsareveryusefulinparallelexecutionschemes.)Toemphasizethedistinctionbetweenuser-suppliedcutsandthosegeneratedbythecompiler,wewillrefertothelatteras‘‘savecp/cuttopairs’’(thereasonforthesenamesisdiscussedinSection5.1).Itthenbecomestheresponsibilityofthecompilertodeter-minewhichpartsoftheprograminvolveredundantsearchthatcanbeeliminatedbyinsertingsavecp/cuttopairs.Thispaperexploreswaysofdoingthisbyinferringfunctionalityofpredicatesandliterals.Aspecialcaseoffunctionality,thatofdeterminacy,hasbeeninvestigatedbyMellish[16],Naish[19]andSawamuraandTakeshima[23].DeransartandMaluszynski,takingadifferentapproach,havecharacterizedsuchbehavioroflogicprogramsintermsofattributegrammars,butintherestrictedsettingofdefiniteclauseprograms[DeransartMaluszynski1985].Theseauthorshavenotconsideredtherela-tionshipbetweenfunctionalcomputationsandnegationbyfailure,orinvestigatedconnectionswithdependencytheoryindatabases.AnotionsimilartothatoffunctionalityhasbeenconsideredbyMendel-zonintherestrictedsettingofdatabases,i.e.assumingthatfunctionsymbolsareabsent,andthatsomepredicatesaredefinedentirelybygroundfacts[17].Ourapproachisbothmoregeneralandlessopera-tional.Itdoesnotrelyexclusivelyonuser-suppliedcutstoinferfunctionality,therebypromotingwhatwebelieveisabetterprogrammingstyle.Italsoenablesustooptimizecertaincaseswhereaparticularcallofapredicatemaybefunctionaleventhoughthepredicateitselfisnot.Thereaderisassumedtobeacquaintedwiththebasicconceptsoflogicprogramming,anintroduc-tiontowhichmaybefoundin[14].Theremainderofthispaperisorganizedasfollows:Section2intro-ducesvariousconceptsthatareusedlaterinthepaper.Section3definesanddiscussesthenotionsoffunctionalityandmutualexclusion.Section4describesanalgorithmforthestaticinferenceof2functionality.Section5discussessomecompile-timeoptimizationsthatarepossiblewithknowledgeoffunctionality.Section6concludeswithasummary.2.Preliminaries2.1.TheLanguageThelanguageconsideredhereisessentiallythatoffirstorderpredicatelogic.Ithascountablesetsofvariables,functionsymbolsandpredicatesymbols,thesesetsbeingmutuallydisjoint.Eachfunctionandpredicatesymbolisassociatedw