Live-structure analysis for logic programming lang

Live-structureAnalysisforLogicProgrammingLanguageswithDeclarationsMauriceBruynoogheGerdaJanssensAndreasKagedalReportCW231,May1996DepartmentofComputingScience,K.U.LeuvenAbstractLive-structureanalysisaddressestheproblemofmemoryreuseforlogicprogramsthroughprogramanalysisratherthanbyrun-timegarbagecollection.Thepresentpaperfocusesonpurelogicprogramswithdeclarationsofmodes,types,anddeterminism.TheanalysisisbasedonpreviousworkforpurePrologbutintroducesimportantinnovations.First,thelivenessanalysisisextendedtoconsidernotonlyforwardlivenessbutalsobackwardliveness(i.e.,duringbacktrackingbytheprogram).Thisallowsustoidentifythecallswithexclusiveaccesstosomepartsofthedata-structures.Second,theeciencyoftheanalysisisreachednotonlybyexploitingtheinformationprovidedbythedeclarations,butalsobysplittingtheanalysisinagoal-independentandagoal-dependentphase(asproposedbyCodishetal.).Keywords:Programanalysis,AbstractInterpretation,LogicProgramswithDeclarations,Liveness.Live-structureAnalysisforLogicProgrammingLanguageswithDeclarationsMauriceBruynoogheyGerdaJanssenszAndreasKagedalxMay6,1996AbstractLive-structureanalysisaddressestheproblemofmemoryreuseforlogicprogramsthroughprogramanalysisratherthanbyrun-timegarbagecollection.Thepresentpaperfocusesonpurelogicprogramswithdeclarationsofmodes,types,andde-terminism.TheanalysisisbasedonpreviousworkforpurePrologbutintroducesimportantinnovations.First,thelivenessanalysisisextendedtoconsidernotonlyforwardlivenessbutalsobackwardliveness(i.e.,duringbacktrackingbythepro-gram).Thisallowsustoidentifythecallswithexclusiveaccesstosomepartsofthedata-structures.Second,theeciencyoftheanalysisisreachednotonlybyexploit-ingtheinformationprovidedbythedeclarations,butalsobysplittingtheanalysisinagoal-independentandagoal-dependentphase(asproposedbyCodishetal.).Keywords:Programanalysis,AbstractInterpretation,LogicProgramswithDecla-rations,Liveness.1IntroductionInimperativelanguagessuchasCorPascal,theprogrammerexplicitlyrecyclesobsoletememorythroughdestructiveassignments.Declarative(functionalandlogic)languagesintheirpureformdonothavedestructiveassignment.Standardimplementationsusecomponentsofexistingdatastructurestocreatenewones,andkeeptheoldstructurealwaysintact,althoughtheremaybenosubsequentreferencestotheoldstructure.Creatinganewdatastructureinsteadofreusingtheobsoleteoneisnotonlymoreexpensiveinmemoryusagebutalsooftenintime(alleldsneedtobeinitialised,whileonlyafewneedanupdate).Run-timegarbagecollection,activatedtorecoverthedeaddatastructures,furtherincreasesthetimeoverhead.Thepurposeoflive-structureanal-ysisistoderiveateachprogrampointwhichstructurescanhaveasubsequentreferenceafterperformingthenextinstruction.Ifastructurehasnosuchreferences,thenthenextinstructioncanfreelyusethememoryoccupiedbythestructureandcanrecognisethatsomeofitspartsbecomedead.Contactperson:GerdaJanssens,KatholiekeUniversiteitLeuven,Dept.ComputerScience,Celestij-nenlaan200A,B-3001Heverlee,Belgium.Phone[phone],Fax[phone].ySupportedbytheNationalFundforScienticResearch.e-mail:[e-mail]undforScienticResearch.e-mail:[e-mail],projectHCMABILE(CHRX-CT94-0624).e-mail:[e-mail].1In[15],suchananalysishasbeendevelopedforpureProlog.Theanalysisisratherexpensive.Inarstphase,integratedtypes,typeinformationintegratedwithmodeinformation[11],havetobederived.Alsotheactuallivenessanalysisisrathercomplex,partlybecausetheintegratedtypesdierfromprogrampointtoprogrampoint,andconsequently,theinformationaboutpossiblesharingofmemorycellshastobeadaptedfromprogrampointtoprogrampoint.Recently,thepointofviewthatlogicprogramminglanguagesshouldoermorere-dundancy[2]tobeacceptablefromasoftwareengineeringpointofviewhasbeenmorewidelyaccepted.Godel[10]isatypedlanguage,modesanddirectionaltypes[1,16]havealsoreceivedmoreattention.Mercury[5,17]isalanguagewheredeclarations|oftypes,modes,determinism|playaprominentrole.Thesedeclarationsallowthelan-guagetobemoredeclarativethanfullProlog,thecompilertocatchmoreerrors,andtheimplementationtohaveabetterperformance.Mercurypositionsitselfasanalternativetoimperativelanguages,whilestillallowingtoprogramatahigherlevel.Tocompetewithlanguageshavingdestructiveassignment,Mercuryneedstobeabletorecogniseandreusedeadstructures.AlsohereMercuryreliesondeclarations:uniquenesspropertiescanbedeclared.Typescertainlyprovidedeclarativeproperties;thepropertiesdescribedbymodesanddeterminismdeclarationsareratherprocedural,butstillatahighlevelofabstraction.Themodesspecifyforwhichcallsthedenitionisprocedurallywellbehav-ing,andthedeterminismisspecifyingsomethingabouttheclauseselectionandaboutthepossibilityoffailure.Thisismuchlesstruefortheuniquenesspropertieswhicharerelatedtotheuseofmemory,alevelofdetailwhichistypicallyhiddenfromtheprogrammerinlogicandfunctionallanguages.Inthecurrentpaperwedevelopananalysiswhichderiveslivenesspropertiesofpurelogicprogramsaugmentedwithtypes,modesanddeterminismdeclarations.Theanalysiscanbeusedtogenerateorcheck(inthelattercas