Abstract Specialization and its Applications

DepartmentGerm´ofanComputerPuebla

Science

TechnicalUniversityofMadrid(UPM),Spain

german@fi.upm.es

ABSTRACT

Theaimofprogramspecializationistooptimizeprogramsbyexploitingcertainknowledgeaboutthecontextinwhichtheprogramwillexecute.Thereexistmanyprogramma-nipulationtechniqueswhichallowspecializingtheprogramindifferentways.Amongthem,oneofthebestknowntech-niquesispartialevaluation,oftenreferredtosimplyaspro-gramspecialization,whichoptimizesprogramsbyspecial-izingthemfor(partially)knowninputdata.Inthisworkwedescribeabstractspecialization,atechniquewhosemainfeaturesare:(1)specializationisperformedwithrespectto“abstract”valuesratherthan“concrete”ones,and(2)abstractinterpretationratherthanstandardinterpretationoftheprogramisusedinordertopropagateinformationaboutexecutionstates.Theconceptofabstractspecializa-tionisattheheartofthespecializationsysteminCiaoPP,theCiaosystempreprocessor.InthispaperwepresentaunifyingviewofthedifferentspecializationtechniquesusedinCiaoPPanddiscusstheirpotentialapplicationsbymeansofexamples.Theapplicationsdiscussedincludeprogramparallelization,optimizationofdynamicscheduling(concur-rency),andintegrationofpartialevaluationtechniques.

CategoriesandSubjectDescriptors

D.1.2[ProgrammingTechniques]:AutomaticProgram-ming—Automaticanalysisofalgorithms,Programtrans-formation;D.3.2[ProgrammingLanguages]:Lan-guageclassification—Constraintandlogiclanguages;D.3.4[ProgrammingLanguages]:Processors—Optimization,Compilers

GeneralTerms

Languages,Performance,Theory

Keywords

AbstractInterpretation,ProgramSpecialization,PartialEvaluation,ProgramOptimization,ProgramParalleliza-tion,LogicProgramming,StaticAnalysis

Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.

PEPM’03June7,2003,SanDiego,California,USACopyright2003ACM1-58113-667-6/03/0006...$5.00.

DepartmentManuelofHermenegildo

ComputerScience

TechnicalUniversityofMadrid(UPM),Spain,and

Dept.ofC.S.andE.andC.Engineering

UniversityofNewMexico,USA

herme@fi.upm.es

1.INTRODUCTION

Theaimofprogramoptimizationis,givenaprogramPtoobtainanotherprogramP′whichissemanticallyequiv-alenttoPbutbehavesbetterforsomecriteriaofinterest.Onetypicalwayofoptimizingprogramsisbyspecializingthemforsomeparticularcontext.Thisallowsautomaticallyovercominglossesinperformancewhichareduetogeneralpurposealgorithms.Thissituationisbecomingmoreandmorefrequentduetotheuseoftechniquessuchasreuseofgeneral-purposeprogramsandlibraries,andsoftwarecom-ponents,whichfacilitatedevelopmentbutcanresultinlargeprogramsandevenwasteofcomputingresources.Morepre-cisely,theaimofprogramspecializationis,givenaprogramPandcertainknowledgeφaboutthecontextinwhichPwillbeexecuted,toobtainaprogramPφwhichisequiva-lenttoPforallcontextswhichsatisfyφandwhichbehavesbetterfromsomegivenpointofview.

Inthecaseofpartialevaluation[4,24],theknowledgeφwhichisexploitedistheso-calledstaticdata,whichcor-respondsto(partial)knowledgeatspecialization(compile)timeabouttheinputdata.Datawhichisnotknownatspecializationtimeiscalleddynamic.Theprogramisop-timizedbyperformingatspecializationtimethosepartsoftheprogramexecutionwhichonlydependonstaticdata.Anotherverygeneralsettingforspecializationspeciallyrelevantinthecontextoflogicprograms,whichhasbeenproposedin[39],istodefinetheknowledgeaboutthecon-textasaso-calledstaticpropertyφ(X1,...,Xn),whereX1,...,Xnaretheformalargumentsofthetop-levelproce-durePandφisdefinedasalogicprogram.However,thisapproachsuffersfromanimportantdifficultyinusingthecontextinformationinanautomatedandeffectiveway.Theapproachwefollowinabstractspecializationisthattheinformationφavailableonthecontextiscapturedbyanabstractsubstitution.Oneadvantageofthisapproachisthattherearewellknowntechniqueswhichallowhandlinginformationrepresentedasabstractsubstitutionsbyusingabstractinterpretationtechniques[6].

1.1AnOverviewofSpecializationTechniques

Forthepurposeofcomparingdifferentexistingtech-niques,letusclassifytheexistingspecializationtechniquesaccordingtohowthefinal,optimized,programisobtained.Ofcourse,thisclassificationisrathercrudeandmanyoftheexistingtechniquescanbeseenasacombinationofthethreeapproacheswhichwewilldiscuss.Thefirstapproachwhichwedescribe,andwhichwewillcallprogramwithan-notations,consistsoftwophases.Duringthefirstphase,

somestaticprogramanalysistechniqueisusedinordertoannotatetheprogramwithanalysisinformation.Inthesec-ondphase,theprogramisoptimizedusingtheinformationobtained.Thisapproachisconceptuallysimple,thoughei-therorbothofthephasesmentionedcanindeedberathercomplex.Awellknownexampleofthiskindoftechniquesisthe“off-line”approachtopartialevaluation,inwhichabinding-timeanalysisphaseisfollowedbyanotheroneinwhichtheresidualprogramisgenerated.

Thesecondclassoftechniquesweconsider,whichwewillcallthetransformationalapproach,isbasedonprogramtransformationtechniques,suchasfold/unfoldtransforma-tions(suchastheonesdevelopedin[3,48]).Inthisscheme,aseriesofnsemantic-preservingprogram-transformationstepsareperformedsuchthatinitiallyP=P0.Then,eachPi+1isobtainedfromPibyapplyingsometransformationTi,i.e.,Pi+1=Ti(Pi),′whichpreservesthesemanticsoftheprogram.FinallyP=Pn.Transformationaltechniquesareverypowerful,themaindifficultybeinginautomaticallydecidingapropersequenceofprogramstransformationstoperforminordertoobtain(anoptimal)programP′.

Thethirdandlastpossibilitywhichweconsider,andwhichwewilldenotethesemanticapproach,isbasedontheexistenceofanalgorithmSwhich,givenaprogramPandsomeknowledgeφ,buildsasemanticrepresentationoftheprogramS(P,φ)whichcapturesthebehaviourofPinsomeprecisewayforallcontextswhichsatisfyφ.Then,thereisacodegenerationalgorithmwhichbuildsthepro-gramPφfromS(P,φ)inastraightforwardway.Oftenthissemanticrepresentationcanbeseenasagraph.Thekindofgraphobtaineddependsontheparticularsemanticsusedbythealgorithm.The“on-line”approachtopartialevaluationis,inourterminology,asemanticapproachsincethebe-haviouroftheprogramispreciselycapturedbythepartialevaluationalgorithm.

Aparticularalgorithmfortheon-linepartialevaluationoflogicprogramsispartialdeduction[35,26].Thoughon-linepartialevaluationcanbeconsideredaninstanceoffold/unfoldtransformations,thecomparativelysignificantsuccessofpartialdeductiontechniquesisprobablyduetothefactthattheyareoftenformalizedasasemanticap-proach.I.e.,analgorithmexistswhichcanbeusedtobuildthesemanticrepresentationoftheprogram.Theexistingalgorithmsforpartialdeduction[35,10,28]areparameter-izedbydifferentcontrolstrategies.Usually,controlisdi-videdintocomponents:“localcontrol,”whichcontrolstheunfoldingforagivenatom,and“globalcontrol,”whichen-suresthatthesetofatomsforwhichapartialevaluationistobecomputedremainsfinite.Severalstrategiesforglobalandlocalcontrolhavebeenproposedwhichproducegood-qualitypartialevaluationsofprograms[36,31].Regardingthecorrectnessofpartialdeduction,twoconditions,definedonthesetofatomstobepartiallyevaluated,havebeenidentifiedwhichensurecorrectnessofthetransformation:“closedness”and“independence”[35].

1.2AbstractvatingExample

SpecializationthroughAMoti-Oneofthedistinguishingfeaturesoflogicprogramming(LP)isthatargumentstoprocedurescanbeuninstanti-atedvariables.This,togetherwiththesearchexecutionmechanismavailable(generallybacktracking)makesitpos-sibletohavemulti-directionalprocedures.I.e.,ratherthan

havingfixedinputandoutputarguments,executioncanbe“reversed”.Thus,wemaycomputethe“input”argumentsfromknown“output”arguments.

Example1.1.Considerthelogicprogrambelow.AsusualinLP,predicates(procedures)arereferredtointhetextasname/arity,wherearityisthenumberofargumentsofthepredicate.Thepredicateground/1isabooleantestwhichsucceedsifandonlyifitsargumentisboundatrun-timetoatermwithoutvariables,andthepredicateis/2(usedasaninfixbinaryoperator)computesthearithmeticvalueofitssecond(right)argumentandunifiesitwithitsfirst(left)argument.

plus(X,Y,Z):-ground(X),ground(Y),!,ZisX+Y.plus(X,Y,Z):-ground(Y),ground(Z),!,XisZ-Y.plus(X,Y,Z):-ground(X),ground(Z),!,YisZ-X.

Theprocedureplus/3definestherelationsuchthatthethirdargumentistheadditionofthefirstandsecondarguments.Theprocedureplus/3ismulti-directional.Forexample,thecallplus(1,2,Sum)canbeusedtocomputetheadditionof1and2.Also,thecallplus(Num,2,3)canbeusedtodeterminewhichisthenumberNumsuchthatwhenaddedto2returns3.

Thus,thedefinitionofplus/2behavesdeclarativelyaslongasatleasttwooftheinputargumentsareground.However,thisgoodbehaviorofplus/3whencomparedtoamono-directionaloperationsuchasis/2isattheexpenseofsomeoverheadwhichisincurredatrun-timeinordertose-lecttheappropriateclausetoexecuteoutofthethreeexist-ingones.Imaginenowthatatcompile-timeitisknownthatthecalltoplus/3willbeoftheformplus(1,2,Sum).Insuchcaseitisclearthatthefirstclausewillbeselectedandtheexecutionwillreturnthevalue3fortheargumentSum.Thisisatypicalexampleofanexecutionwhichcanbenefitfrom(traditional,“concrete”)partialevaluationwhereφistheknowledgethattheinitialcallisplus(X,Y,Z)withX=1andY=2.

Inspiteoftherelativematurityofpartialevaluationoflogicprograms,itiswellknownthatthetechniquehascer-tainshortcomings.Imagineweareinterestedinoptimizingthecode:

p(X,Y,Res):-plus(X,Y,Tmp),plus(1,Tmp,Res).

whereplus/3isdefinedasabove.Byobservingthepro-gramwecanconcludethataftertheexecutionofthecallplus(X,Y,Tmp)allthreeargumentsareground.Asaresult,thecallplus(1,Tmp,Res)canbeoptimizedtoResis1+Tmp.

Unfortunately,intraditionalpartialevaluationnoinfor-mationonthevalueoftheargumentTmpispropagatedtothecallplus(1,Tmp,Res).Theintrinsicproblemunderlyingthisshortcomingofpartialevaluationisthattheonlyinfor-mationwhichcanbecapturedaboutvaluesofargumentsareconcretevalues.Inthecaseoflogicprogramming,valuesarecapturedbysubstitutions.Thisshortcomingofpartialevaluationhasbeenidentifiedandseveralproposalsexistwhichtrytoovercomeit.Ourproposal,abstractspecial-ization,addressesthisproblemdirectly.Abstractspecial-izationallowsspecializingcallswithrespecttoabstractsub-stitutionsinsteadofconcretesubstitutionsasintraditionalpartialevaluation.AswillbediscussedinSection2,ab-stractsubstitutionsareinthiscontextfiniterepresentationsofpossiblyinfinitesetsofdata.Eachsuchrepresentationmethodiscalledanabstractdomain.Thekindofinforma-

tionwhichcanbecapturedbyabstractsubstitutionsvariesfromoneabstractdomaintoanother.Forexample,wecanhaveanabstractdomainwhichallowscapturingtypeinfor-mation.1Suchdomaincanbeusedtodeterminethatinthecallplus(1,Tmp,Res)theargumentTmpisboundtoanumber.Wecanusethisinformationinordertoabstractlyexecutethetwogroundtermsinthefirstclauseofplus/3tothevaluetrue.Wecanevenexecutethe!/0procedurecallandeliminatetherestofclausesforplus/32.Wecanthusoptimizetheoriginalprogramto:

p(X,Y,Res):-plus(X,Y,Tmp),Resis1+Tmp.

Also,thecallplus(X,Y,Tmp)canbeoptimized.SinceTmpisavariablewhichislocaltotheclause,itcanbedeterminedtobeafreevariable(andthusdefinitelynotground).Thus,theprogramcanbeoptimizedto:

p(X,Y,Res):-plus1(X,Y,Tmp),Resis1+Tmp.

plus1(X,Y,Z):-ground(X),ground(Y),!,ZisX+Y.whereplus1/3isaspecializedversionofplus/3.Generaliz-ingfromtheexamplesabovewecandevelopaspecializationsystemwhichisabletoperformtheoptimizationsshownabove.Thespecializationsystemwillbeableto:(1)capturemoregeneralinformationthantraditionalsubstitutions,i.e.,itwillcaptureabstractsubstitutions,(2)propagatesuchin-formationinacorrectwayusingasuitablesemantics,and(3)carryouttheoptimizationsenabledbytheinformationavailable.

Intherestofthepaperwepresentsuchasystem.Thestructureofthepaperisasfollows.AfterrecallingsomebasicconceptsofabstractinterpretationinSection2,wepresenttheconceptofabstractexecutabilityinSection3.Thenweintroduceourgenericabstractmultiplespecializa-tionframeworkinSection4.Wecontinuewithseveralappli-cationsofabstractmultiplespecialization:inthecontextofautomaticprogramparallelizationinSection5,optimizationofdynamicschedulinginSection6,andpartialevaluationinSection7.Finally,Section8discussesrelatedworkandSection9presentssomeconclusions.

2.ABSTRACTINTERPRETATION

StaticProgramanalysisaimsatderivingatcompile-timecertainpropertiesoftherun-timebehaviorofaprogram.Weprovidesomebackgroundandnotationonabstractin-terpretation[6],whichisarguablyoneofthemostsuccessfultechniquesforstaticprogramanalysis.

Inabstractinterpretation,theexecutionoftheprogramis“simulated”onanabstractdomain(Dα)whichissimplerthantheactual,concretedomain(D).Anabstractvalueisafiniterepresentationofa,possiblyinfinite,setofactualvaluesintheconcretedomain(D).ThesetofallpossibleabstractsemanticvaluesrepresentsanabstractdomainDαwhichisusuallyacompletelatticeorcpowhichisascendingchainfinite.However,forthisstudy,abstractinterpretationisrestrictedtocompletelatticesoversetsbothforthecon-crete󰀕2D,⊆󰀖andabstract󰀕Dα,⊑󰀖domains.

Abstractvaluesandsetsofconcretevaluesarerelatedviaapairofmonotonicmappings󰀕α,γ󰀖:abstractionα:2D→

X={X1,...,Xn}assigns

toeachvariableXiavaluevintheset{ground,var,any}whereeachvrepresentsaninfinitesetofterms.ThefactthatavariableXiisassignedanabstractvaluevindicatesthatXiwillbeboundatrun-timetosometermbelongingtov.groundisthesetofalltermswithoutvariables;varisthesetofunboundvariables(possiblyaliasedtootherunboundvariables);andanyisthesetofallterms.Theabstractdo-mainiscomplementedbytheabstractsubstitutions⊥and⊤.Asusualinabstractinterpretation,⊥denotestheabstractsubstitutionsuchthatγ(⊥)=∅.Thesubstitution⊤issuchthatγ(⊤)=D.Inourdomain,⊤correspondstoassigninganytoeachvariablein

ttodenote

atupleofterms.AclauseisoftheformH:-B1,...,BnwhereH,thehead,isanatomandB1,...,Bn,thebody,isapossiblyemptyfiniteconjunctionofatoms.Atomsinthebodyofaclauseareoftencalledliterals.Aprogramisafinitesequenceofclauses.

2.1Goal-Dependentanalysis

Goal-dependentanalysesarecharacterizedbygeneratinginformationwhichisvalidonlyforarestrictedsetofcallstoapredicate,asopposedtogoal-independentanalyseswhoseresultsarevalidforanycalltothepredicate.Goal-dependentanalysesallowobtainingresultswhicharespecial-ized(restricted)toagivencontext.Asaresult,theyprovideingeneralbetter(stronger)resultsthangoal-independentanalyses.Inaddition,goal-dependentanalysesprovidein-formationonboththecallandsuccessstatesforeachpred-icate,whereasgoal-independentanalysesinprincipleonlyprovideinformationonsuccessstatesofpredicates.Forthesereasons,andsinceprogramspecializationgreatlyre-liesoninformationaboutcallstatestopredicates,wewillrestrictthediscussiontogoal-dependentanalyses.

Inordertoimprovetheaccuracyofgoal-dependentanal-yses,somekindofdescriptionoftheinitialcallstothepro-gramshouldbegiven.3Withthisaim,wewilluseentrydeclarationsinthespiritof[2].Theirroleistorestrictthestartingpointsofanalysistoonlythosecallswhichsatisfyadeclarationoftheform‘:-entryPred:Call.’whereCallisanabstractcallsubstitutionforPred.Forexample,thefollowingdeclarationinformstheanalyzerthatatrun-timeallinitialcallstothepredicateqsort/2willhaveatermwithoutvariablesinthefirstargumentposition::-entryqsort(A,B):ground(A).

Definition

RT(L,P)⊆TS(L,P)

executabletotrueinP

RT(L,P)⊆FF(L,P)

B,Dα):λL⊑λ′

B,Dα):executabletofalseinP

4

tionActually,plicity,notbutonlythealsoatanalyzersusedinpracticegenerateinforma-atthethepredicateclauseliterallevel,level.

asstatedhereforsim-λL⊑λ′

Forsimplicity,wewilllimithereinthediscussiontoreduc-ingaprocedurecallorprogramfragmentL(forexample,a“literal”inthecaseoflogicprogramming)toeithertrueorfalse.Eachrun-timeinvocationoftheprocedurecallLwillhavealocalenvironmentwhichstorestheparticularvaluesofeachvariableinLforthatinvocation.Wewilluseθtodenotethisenvironment(composedofassignmentsofvaluestovariables,i.e.,substitutions)andtherestriction(projec-tion)oftheenvironmentθtothevariablesofaprocedurecallLisdenotedθ|L.

Wenowintroducesomedefinitions.GivenaprocedurecallLtoapredicatewhichperformsnoside-effectsinaprogramPwedefinethetrivialsuccesssetofLinPasTS(L,P)={θ|L:LθsucceedsexactlyonceinPwithemptyanswersubstitution(ǫ)}.Similarly,givenaprocedurecallLfromaprogramPwedefinethefinitefailuresetofLinPasFF(L,P)={θ|L:LθfailsfinitelyinP}.

Finally,givenaprocedurecallLfromaprogramPwedefinetherun-timesubstitutionsetofLinP,denotedRT(L,P),asthesetofallpossiblesubstitutions(run-timeenvironments)intheexecutionstatejustpriortoexecutingLinanypossibleexecutionofprogramP.

Table1showstheconditionsunderwhichaprocedurecallLisabstractlyexecutabletoeithertrueorfalse.Inspiteofthesimplicityoftheconcepts,thesedefinitionsareingeneralnotdirectlyapplicableinpracticesinceRT(L,P),TS(L,P),andFF(L,P)aregenerallynotknownatcompiletime.However,acollectingsemanticsisgenerallyusedasconcretesemanticsforabstractinterpretationsothatanal-ysiscomputesforeachprocedurecallLintheprogramanabstractsubstitutionλLwhichisasafeapproximationofRT(L,P),i.e.∀L∈P.RT(L,P)⊆γ(λL).

Also,undercertainconditionswecancomputeeitherau-tomaticallyorbyhandsetsofabstractvaluesATS(

L,Dα)whereLtriviallysucceeds(resp.

finitelyfails).Soundnessrequiresthat∀λ∈ATS(

L,P)and∀λ∈AFF(L,P).

Eventhoughthesimpleoptimizationsillustratedabovemayseemofnarrowapplicability,infactformanybuiltinproceduressuchasthosethatcheckbasictypesorwhichinspectthestructureofdata,eventhesesimpleoptimiza-tionsareindeedveryrelevant.Twonon-trivialexamplesaretheirapplicationtosimplifyingindependencetestsinprogramparallelization[45],discussedinSection5,andtheoptimizationofdelayconditionsinlogicprogramswithdy-namicprocedurecallschedulingorder[41],discussedinSec-tion6.

Also,theclassofoptimizationswhichcanbeperformedcanbemadetocovertraditionallower-leveloptimizationsaswell,providedthelower-levelcodetobeoptimizedis

“reflected”(i.e.,ismadeexplicit)atthesourceleveloriftheabstractinterpretationisperformeddirectlyattheobjectlevel.

4.

ABSTRACTMULTIPLESPECIALIZA-TION

Thetraditionalapproachusedinanalysis-basedoptimiz-ingcompilersistofirstanalyzetheprogramandthenusetheinformationinAnalysis(P,p,λ,Dα)toannotatethepro-gramwithinformationwhichisthenusedforoptimiza-tion.Often,theunderlyinganalysisalgorithmismulti-variant.However,analysisinformationforthedifferentversionsofaprocedurecallis“flattened”,i.e.,“lubbed”togetherbeforebeingusedforoptimization.Thoughthisapproachallowsimportantoptimizations,itproducesopti-mizationswhichmaybesuboptimalwhencomparedwiththeoptimizationswhichcouldbeachievedifseparatespe-cializationswereimplementedforthedifferentversionscon-sideredbymulti-variantanalysis.Moreprecisely,pose{󰀕pj,λc1,λs1󰀖,...,󰀕pj,λcn,λs

sup-n󰀖}n>1arethetuplesinAnalysis(P,p,λ,Dα)forpredicatepj.Generally,onlyoneversionforpjisimplemented,whichisizingpjw.r.t.λc1⊔λc2,...⊔λc

equivalenttospecial-n.

Themainideathatwewillexploitistogenerateadif-ferentversionofpjforeachtuple󰀕pj,λci,λs

i󰀖.Then,eachversioncanbespecializedthecallsubstitutionsλc

w.r.t.λciregardlessoftherestof

j∀j=i.Hopefully,thiswillleadtofurtheropportunitiesforoptimizationineachparticu-larversion.NotethatifanalysisterminatesthenumberoftuplesinAnalysis(P,p,λ,Dα)foreachpredicatemustbefinite,andthustheresultingprogramwillbefinite.Wewillrefertothiskindofspecializationasabstractmultiplespe-cialization[43,45].Animportantobservationhereisthatabstractmultiplespecializationisnotaprogramwithan-notationsapproachbutratherasemanticapproachintheterminologyofSection1.1.

4.1AnalysisAnd–OrGraphs

Traditional,goaldependentabstractinterpretersforLPbasedonBruynooghe’sanalysisframework[1],inordertocomputeAnalysis(P,p,λ,Dα),constructanand–orgraphwhichcorrespondsto(orapproximates)theabstractseman-ticsoftheprogram.WewilldenotebyAO(P,p,λ,Dα)theand–orgraphcomputedbytheanalyzerforaprogramPwithcallingpattern󰀕p,λ󰀖usingthedomainDα.Suchand–orgraphcanbeviewedasafiniterepresentationofthe(pos-siblyinfinite)setofand–ortreesexploredbythe(possiblyinfinite)concreteexecution.Concreteand–ortreeswhichareinfinitecanberepresentedfinitelythroughawideningintoarationaltree.Also,theuseofabstractvaluesinsteadofconcreteonesallowsrepresentinginfinitelymanyconcreteexecutiontreeswithasingleabstractanalysisgraph.Finite-nessofAO(P,p,λ,Dα)(andthusterminationofanalysis)isachievedbyconsideringanabstractdomainDαwithcertaincharacteristics(suchasbeingfinite,oroffiniteheight,orwithoutinfiniteascendingchains)orbytheuseofawiden-ingoperator[6].

Thegraphhastwosortsofnodes:thosewhichcorrespondtoatoms(calledor–nodes)andthosewhichcorrespondto

clauses(calledand–nodes).Or–nodesaretriples󰀕pi,λci,λs

i󰀖.

Asbefore,λciandλs

iare,respectively,apairofabstractcallandsuccesssubstitutionsfortheatompi.Forclarity,

inthefigurestheatompiissuperscriptedwithλctotheleftandλstotherightofpirespectively.Forexample,theor–node󰀕p(A),{},{A/a}󰀖isdepictedinthefigureas{}

p(A){A/a}.And–nodesarepairs󰀕Id,H󰀖whereIdisauniqueidentifierforthenodeandHistheheadoftheclausetowhichthenodecorresponds.Inthefigures,theyarerepresentedastrianglesandHisdepictedtotherightofthetriangles.Notethatthesubstitutions(atoms)labelingand–nodesareconcretewhereasthesubstitutionslabelingor–nodesareabstract.Finally,squaresareusedtorepresenttheempty(true)atom.Or–nodeshavearcstoand–nodeswhichrepresenttheclauseswithwhichtheatom(possibly)unifies.And–nodeshavearcstoor–nodeswhichrepresenttheatomsinthebodyoftheclause.Notethatseveralinstancesofthesameclausemayexistintheanalysisgraphofaprogram.Inordertoavoidconflictswithvariablenames,clausesarestandardizedapartbeforeaddingtotheanalysisgraphthenodeswhichcorrespondtosuchclause.

Intuitively,analysisalgorithmsarejustgraphtraversalal-gorithmswhich,givenP,p,λ,andDα,buildAO(P,p,λ,Dα)byprocessingprogramclausesfromlefttoright,addingtherequirednodes,andcomputingsuccesssubstitutionsuntilaglobalfixpointisreached.ForagivenP,p,λ,andDαtheremaybemanydifferentanalysisgraphs.However,thereisauniqueleastanalysisgraphwhichgivesthemostpreciseinformationpossible.Thisanalysisgraphcorrespondstotheleastfixpointoftheabstractsemanticequations.Eachtimetheanalysisalgorithmcreatesanewor–nodeforsome

piandλciandbeforecomputingthecorrespondingλs

i,itcheckswhetherAnalysis(P,p,λ,Dα)alreadycontainsatu-plefor(avariantof)piandλci.Ifthatisthecase,theor–nodeisnotexpandedandthealreadycomputedλsistoredinAnalysis(P,p,λ,Dα)isusedforthator–node.Thisisdonebothforefficiencyandforavoidinginfiniteloopswhenan-alyzingrecursivepredicates.Asaresult,severalinstancesofthesameor–nodemayappearinAO,butonlyoneofthemisexpanded.Wedenotebyexpansion(N)thein-stanceoftheor–nodeNwhichisexpanded.IfthereisnotupleforpiandλciinAnalysis(P,p,λ,Dnodeisexpanded,λsαicomputed,and󰀕pi,λci,λs

),theor–

i󰀖addedtoAnalysis(P,p,λ,Dα).NotethatthesuccesssubstitutionsλsistoredinAnalysis(P,p,λ,Dα)aretentativeandmaybeupdatedduringanalysis.Onlywhenaglobalfixpointisreachedthesuccesssubstitutionsaresafeapproximationsoftheconcretesuccesssubstitutions.

Forclarityofthepresentation,intheexamplesbelowweusetheconcretedomainasabstractdomain.However,thiscannotbedoneingeneralsinceanalysismaynotterminate.Wewillpresentotherexampleswithmorerealisticdomainslaterinthepaper.

Example4.2.Considerthesimpleexampleprogrambe-lowtakenfrom[28].Figure1depictsapossibleresultofanalysisfortheinitialcallp(A)withAunrestricted.Thedottedarcindicatesthatthecorrespondingor–nodeshaverenamingsofthesameabstractcallsubstitution.p(X):-q(X),r(X).q(a).

q(X):-q(X).r(a).r(b).

Clearly,intheexampleprogramabovetheclauser(b)isuselessandcouldbeeliminated.Notethatanalysishas

Algorithm4.1(CodeGeneration).GivenAnalysis(P,p,λ,Dα)andAO(P,p,λ,Dα)generatedbyanalysisforaprogramPanatompwithabstractsubstitutionλ∈Dαdo:•ForeachtupleN=󰀕a(

t),λc,λs󰀖).

•EachpredicatepredNisdefinedbythesequenceofclauses

–(predN(tn):-b′n)whereexpansion(N,AO)=ONandchildren(ON,AO)=󰀕Id1,p1(

ti)󰀖::...::󰀕Idn,p(

ti1),...,prediki(

s

tij),λcij,λij󰀖),and

s

ti1),λcchildren(󰀕Idi,pi(i1,λi1󰀖::...::󰀕aiki(

t),λc,λs󰀖)=qiffq(

gen(AO(P,p,λ,Dα))thatP′istheprogramobtained

byapplyingAlgorithm4.1toAO(P,p,λ,Dα).CorrectnessofP′w.r.t.Pforallinitialcallspθwithθ∈γ(λ)isgivenbythecorrectnessoftheabstractinterpretationprocedure,astheextendedprogramP′isobtainedbysimplymateri-alizingthe(implicit)programwithmultipleversionsfromwhichtheanalysishasobtaineditsinformation.

Example4.3.Theprogramgeneratedbythecodegener-ationalgorithmfortheand–orgraphinFigure1isshownbelow.Theuselessclauser(b)hasbeeneliminated.

p(X):-q(X),r(X).q(a).

q(X):-q(X).r(a).

Theexampleaboveshowshowtheuseofand–orgraphsallowsremovinguselessclauses.Theexamplebelowshowshowgeneratingmultiplespecializedversionsofapredicatecanleadtooptimizationswhicharenotpossibleifonlyoneversionwereimplemented.

Example4.4.ConsideragaintheprogramPinExam-ple1.1.Theand–orgraphAO(P,p,⊤,Dα)whereDαisadomainwhichcapturesmodeinformationwillhavetwoor-nodesforpredicateplus/3withdifferentabstractcallsub-stitutions(weabbreviategroundbyg):

󰀕plus(X′,Y′,Z′),{Z′/var},{X′/g,Y′/g,Z′󰀕plus(X′′,Y′′,Z′′),{X′′/g,Y′′/g},{X′′/g,Y′′/g}󰀖/g,Z′′

and

/g}󰀖.Noweachofthesecallpatternscanbeoptimizedseparatelybyabstractlyexecutingthegroundnesstests.Thefinalspecializedprogramobtainedisshownbelow:

p(X,Y,Res):-plus1(X,Y,Tmp),plus2(1,Tmp,Res).plus1(X,Y,Z):-ground(X),ground(Y),!,ZisX+Y.plus2(X,Y,Z):-ZisX+Y.

Notethatthisprogramcouldbefurtherimprovedbyun-foldingthecallplus2(1,Tmp,Res).Thiswillbefurtherdis-cussedinSection7.Also,twoversionshavebeengenerated

forpredicateplus/3,namelyplus1/3andplus2/3.Inordertoavoidcodeexplosionoursystemperformsaminimizingstepaposterioriontheand–orgraphinordertoproducetheminimalnumberofversionswhilemaintainingallopti-mizations[45].

5.PROGRAMPARALLELIZATION

Thefinalaimofparallelismistoachievethemaximumspeed(effectiveness)whilecomputingthesamesolution(correctness)asthesequentialexecution.Thetwomaintypesofparallelismwhichcanbeexploitedinlogicpro-gramsarewellknown:or-parallelismandand–parallelism.Inthisworkweconcentrateonthecaseofand–parallelism.And-parallelismreferstotheparallelexecutionoftheliter-alsinthebodyofaclause.See,forexample,[18]anditsreferences.Ifonlyindependentgoalsareexecutedinparallel,bothcorrectnessandefficiencycanbeensured[23].

5.1TheTests

AnnotationProcessandRun-time

Theannotation(parallelization)processcanbeviewedasasource–to–sourcetransformationfromstandardPrologtoaparalleldialect.Herein,wewillusethe&operator[20].Executionofliteralsseparatedby&isperformedinparallelifsufficientprocessorsareavailable.Otherwisetheywillbeexecutedsequentially.

Theautomaticparallelizationprocessisperformedasfol-lows[37]:firstly,ifrequestedbytheuser,thePrologpro-gramisanalyzedusingoneormoreglobalanalyzers.Sec-ondly,sinceside–effectscannotbeallowedtoexecutefreelyinparallel,theoriginalprogramisanalyzedusingtheglobalanalyzerdescribedin[38]whichpropagatestheside–effectcharacteristicsofbuiltinsdeterminingthescopeofside–effects.Finally,theannotatorsperformasource–to–sourcetransformationoftheprograminwhicheachclauseisanno-tatedwithparallelexpressionsandconditionswhichencodethenotionofindependenceused.Indoingthistheyusetheinformationprovidedbytheglobalanalyzersmentionedbefore.

5.2AnExample:MatrixMultiplication

low.APrologprogramformatrixmultiplicationisshownbe-usedonlybyThethedeclaration(goaldependent):-module(mmatrix,[mmultiply/3]).analyzertodeterminethatisIncallsthiscallsdonetocasetousingthenommultiply/3mayappearintop-levelqueries.onepredicateinformationormoremmultiply/3isgivenaboutentrydeclarations(however,thearguments[2]).

thiscouldbein:-module(mmatrix,[mmultiply/3]).mmultiply([],

,[]).

multiply([V0|Rest],V1,[Result|Others]):-vmul(V0,V1,Result),multiply(Rest,V1,Others).vmul([],[],0).

vmul([H1|T1],[H2|T2],Result):-ProductisH1*H2,vmul(T1,T2,Newresult),ResultisProduct+Newresult.

If,forexample,wewanttospecializetheprogramforthecaseinwhichthefirsttwoargumentsofmmultiply/3aregroundvaluesandweinformtheanalyzeraboutthis,theprogramwouldbeparallelizedwithouttheneedforanyrun-timetests.Inourcasetheanalyzermustinprinciple

mm3igmm13i3im1m2g+3im3m4gFigure4:CallGraphofSpecializedmmatrix

assumenoknowledgeregardingtheinstantiationstateoftheargumentsatthemoduleentrypoints.

Figure3containstheresultofautomaticparalleliza-tionundertheseassumptions.if-then-elsesarewritten(cond->then;else),i.e.,usingstandardPrologsyn-tax.Thepredicatevmul/3isnotshowninFigure3be-causeautomaticparallelizationhasnotdetectedanyprof-itableparallelisminit(duetogranularitycontrol)anditscoderemainsthesameasintheoriginalprogram.

ItisclearfromFigure3thatagoodnumberofrun-timetestshasbeenintroducedduringtheparallelizationprocess.Ifthetestssucceedtheparallelcodeisexecuted.Otherwisetheoriginalsequentialcodeisexecuted.Thebooleantestindep(X,Y)succeedsifandonlyifXandYhavenovari-ablesincommon.Forconcisenessandefficiency,aseriesoftestsindep(X1,X2),...,indep(Xn-1,Xn)iswrittenasindep([[X1,X2],...,[Xn-1,Xn]]).

Clearly,thesetestsmaycauseconsiderableoverheadinrun-timeperformance,tothepointofnotevenknowingatfirstsightiftheparallelizedprogramwillofferspeedup,i.e.,ifitwillrunfasterthanthesequentialone.Wewilluseab-stractmultiplespecializationinordertoreducetherun-timeoverheadandincreasethespeedupofparallelexecution.Itisimportanttomentionthatabstractmultiplespecial-izationisabletoautomaticallydetectandextractsomein-variantsinrecursiveloops:onceacertainrun-timetesthassucceededitdoesnotneedtobecheckedinthefollowingrecursivecalls[17].Figure4showsthecallgraphofthespe-cializedparallelprogram.Theprogramitselfisnotshownforspacelimitationsbutcanbefoundin[45].Inthefigure,mmstandsformmultiply/3andmformultiply/3.Intheand–orgraphcomputedbyanalyistherearetwoor–nodesforpredicatemmultiply/3,fourformultiply/3,andeightforvmul/3.Theminimizationalgorithmcollapsesallor–nodesforvmul/3intoonesincethedifferentcallpatternsdonotleadtointerestingoptimizations.However,twover-sionsaregeneratedformm:mmandmm1andfourform.InFigure4edgesarelabeledwiththenumberoftestswhichareavoidedineachcalltothecorrespondingversionwithrespecttothenonspecializedprogram.Forexample,g+3imeansthateachexecutionofthisspecializedversionavoidsagroundnessandthreeindependencetests.Itcanbeseeninthefigurethatoncethegroundnesstestinanyofmm,m1,orm2succeeds,itisdetectedasaninvariant,andthemoreoptimizedversionsmm1,m3,andm4respectivelywillbeusedinallremainingiterations.

mmultiply([],_,[]).

mmultiply([V0|Rest],V1,[Result|Others]):-(ground(V1),indep([[V0,Rest],[V0,Others],[Rest,Result],[Result,Others]])->

multiply(V1,V0,Result)&mmultiply(Rest,V1,Others);multiply(V1,V0,Result),mmultiply(Rest,V1,Others)).multiply([],_,[]).

multiply([V0|Rest],V1,[Result|Others]):-(ground(V1),indep([[V0,Rest],[V0,Others],[Rest,Result],[Result,Others]])->

vmul(V0,V1,Result)&multiply(Rest,V1,Others);vmul(V0,V1,Result),multiply(Rest,V1,Others)).

Figure3:Parallelmmatrix

6.

OPTIMIZATIONOFDYNAMIC

SCHEDULING

Most“second-generation”logicprogramminglanguagesprovideaflexibleschedulinginwhichcomputationgener-allyproceedsleft-to-right,butsomecallsaredynamically“delayed”untiltheirargumentsaresufficientlyinstantiated.Thisgeneralformofscheduling,oftenreferredtoasdynamicscheduling,whichcanbeseenasa(restricted)classofcon-currency,increasestheexpressivepowerof(constraint)logicprograms.Unfortunately,italsohasasignificanttimeandspaceoverhead.

Inthissectionwepresentbymeansofexamplestwodiffer-entclassesoftransformations.Thefirstclasssimplifiesthedelayconditionsassociatedwithaparticularliteral.Thesecondclassoftransformationsreordersadelayedliteralandmovesitclosertothepointwhereitwakesup.Bothclassesoftransformationsessentiallypreservethesearchspaceandhencetheoperationalbehavioroftheoriginalpro-gram.However,reorderingmaychangetheexecutionorderofdelayedliteralsthatarewokenatexactlythesametime.Notethatthisorderissystemdependentanditisrareforprogrammerstorelyonaparticularordering.

UsingtheCiaoPPsystemwehavebuiltatoolwhichau-tomaticallyoptimizeslogicprogramswithdelayusingtheabovetransformations.Initialexperimentssuggestthatsim-plificationofdelayconditionsiswidelyapplicableandcansignificantlyspeedupexecution,whilereorderingislessap-plicablebutcanalsoleadtosubstantialperformanceim-provements.

6.1ProgramswithDelayingConditions

Indynamicallyscheduledlanguagestheexecutionofsomeliteralcanbedelayeduntilaparticulardelayconditionholds.Adelaycondition,Cond,takesthecurrentrun-timeenvironmentandreturnstrueorfalseindicatingifevalu-ationcanproceedorshouldbedelayed.Typicalprimitivedelayconditionsareground(X)andnonvar(X).ThelatterholdsiffXisboundtoanon-variableterm.Delaycondi-tionscanbecombinedtoallowmorecomplexdelaybe-haviour.Theycanbeconjoined,written(Cond1,Cond2),ordisjoined,written(Cond1;Cond2).

Adelayingliteralisoftheformwhen(Cond,L),whereCondisadelayconditionandLisaliteral.EvaluationofLwillbedelayeduntilCondholdsforthecurrentcon-straintstore.Delayinformationcanbepredicate-basedandliteral-based.Intheformer,thedelayingliteralappearsasadeclarationbeforethedefinitionofthepredicate,eachin-stanceofthepredicateinheritingthedelaycondition.In

thelatter,thedelayingliteralappearsinthebodyofsomeclauseonlyaffectingtheliteralL.Itisstraightforwardtousepredicate-baseddeclarationstoimitateliteral-basedde-lay,andviceversa.Forsimplicity,wewillrestrictourselvestoliteral-baseddelay.

Inlogicprogramswithdynamicscheduling,aliteralisei-theranatomoradelayingliteral.Weareassumingthatallruleheadsarenormalized,sincethissimplifiestheexamplesandcorrespondstowhatisdoneintheanalyzer.5Thisisnotrestrictivesinceprogramscanalwaysbenormalized.How-ever,soastopreservethebehaviouroftheoriginalprogramunderdynamicscheduling,thenormalizationprocessmustensurethatheadunificationsareperformedsimultaneously,thatis,groupedtogetherinoneprimitiveconstraint.

6.2SimplifyingDynamicScheduling

Delayconditionsmaybeevaluatedeachtimeavariableistouched.Simplifyingsuchconditionscanthenleadtosignif-icantperformanceimprovement.Essentiallythebehaviourofadelayconditionisonlyrelevantduringthelifetimeofthedelayingliteral.Hence,wecanreplaceonedelayconditionbyanother(moreefficient)conditioniftheyareequivalentforallconstraintstoresthatoccurduringthelifetimeofthedelayingliteral.

toExamplefollowingobtainmuch6.1.Dynamicschedulingcanbeusedinorderprogrammoreforgeneralnaivereverse:

code.Considerforexamplethe:-module(nrev,[nrev/2]).nrev([],[]).

nrev([X|Xs],Rs):-nrev(Xs,R),app(R,[X],Rs).app([],L,L).

app([X|Xs],Ys,[X|Zs]):-app(Xs,Ys,Zs).

list.TheY=[3,2,1]Fornrev/2example,predicatecanbeusedinordertoreverseapurities,suchwe.maySinceinthistheprincipleprogramcallnrev([1,2,3],Y)usedoesitbackwards,notcontainwillreturni.e.,anyim-anyasnrev(X,[1,2,3])shouldreturnY=[3,2,1].Inafact,callforlutionaPrologsecondsystemwouldcomputethat.However,ifweaskinnrev([X|Xs],thetorecursiveavoidsolution,thistheexecutionloops!Onepossibleso-clausebehaviourofistoreorderthetwoliteralsHowever,Rs):-app(R,nrev/2[X],,i.e.:

Rs),nrev(Xs,R).problemwhichcannowbethisprogramcannotbeusedforwards.Thisbothdirections.allowshavingsolvedSuchaadefinitionbymeansprogramofofdynamicschedulingisshownnrev/2below:

whichworksinnrev([],[]).

nrev([X|Xs],Rs):-when((nonvar(Xs);ground(R)),nrev(Xs,R)),

when((nonvar(R);nonvar(Rs)),app(R,[X],Rs)).app([],L,L).

app([X|Xs],Ys,[X|Zs]):-when((nonvar(Xs);nonvar(Zs)),app(Xs,Ys,Zs)).

Thishasthedisadvantagethatdynamicschedulingmayintroduceimportantrun-timeoverhead.However,wecanuseabstractspecializationinordertooptimizetheabovecodefortherequiredusage.Infact,ourprototypespe-cializerfordynamicscheduling[41]isabletooptimizetheprogrambacktotheoriginalcodewithoutdelaysshowninExample6.1ifitcaninferthatatthecallthefirstargumentisdefinitelyground.Also,itwillreorderthetwoliteralsintherecursiveclauseofappendifanalysisguaranteesthatcallshaveafreevariableinthefirstargumentandthesec-ondargumentisground.

thepartialsolution,i.e.,itisatestwhilegeneratealgorithmratherthanagenerateandtestone.

Ofcourse,anotheralternativewouldhavebeentowritebyhandaprogramwhichcheckssortednessofpartialsolu-tionsexplicitly.Thishasthedisadvantagethatitseparatesthecodeapartfromitsspecificationandthattheobviousresultingcodeisonceagainnotreversible.Example6.3.Inacallsuchasnaive

sort(List,Sorted):-permute(List,

Sorted),sorted

6.3ReorderingDelayingLiterals

Inspiteoftheapparentsimplicityofthespecializationofdynamicscheduling,itisindeedratherinvolved.First,theanalysishastobeabletohandlelogicprogramswithdynamicscheduling.Doingsoaccuratelyisacomplextask.Second,thepurposeofspecializationisnotthatthefinalprogramcanbeexecutedwithoutdelaysbutratherthattheoperationalsemantics,i.e.,thesearchspace,oftheprogramismaintained.

Example6.2.Inordertoillustratethisweshowthefol-lowingexampleinwhichanaivealgorithmforsortinglistsispresented.Itisbasedonthespecificationofthesortingalgorithm:theresultinglistmustbeapermutationoftheinputlistandbesorted.

naive_sort(List,Sorted):-when(nonvar(Sorted),sorted_list(Sorted)),permute(List,Sorted).sorted_list([]).

sorted_list([Fst|Oths]):-when(nonvar(Oths),sorted_list1(Fst,Oths)).sorted_list1(_,[]).

sorted_list1(Fst,[Snd|Rest]):-when((ground(Fst),ground(Snd)),Fst=permute(List,Result):-when((nonvar(List);nonvar(Oths)),

delete(Elem,List,Oths)),

Result=[Elem|Perm1],permute(Oths,Perm1).delete(Elem,[Elem|Oths],Oths).delete(Elem,List,Oths):-head(List,Oths)=head([Fst|TM],[Fst|R]),

when((nonvar(TM);nonvar(R)),delete(Elem,TM,R)).

Thankstotheuseofdynamicschedulingthecodeabovehasthefollowingdesirablefeatures:(1)itcanbeusedinordertosortalist;(2)ifthesecondargumentisground,itcanbeusedinordertogenerateallthepossiblelists(per-mutations)ofagivensortedlist;(3)thoughitisnotafastsortingalgorithm,itbehavesrelativelywellforsmalllistsduetoco-routining:generationofthepermutationisinter-leavedwithtestsofitssortednessasnewitemsareaddedto

becausedynamicschedulinglookssettobecomeincreas-inglyprevalentin(constraint)logicprogramminglanguagesbecauseofitsimportanceinimplementingconstraintsolversandcontrollingsearchaswellasforimplementingconcur-rency.Inallthesecontexts,delaydeclarationsareautomat-icallyintroducedbythecompiler.Thishastheadvantagethatitavoidsthetediousanderrorpronetaskofhavingtodoitbyhand.Also,theyareacleartargetforabstractspecialization.

7.

INTEGRATIONWITHPARTIALEVAL-UATION

Mostofthepracticalalgorithmsforprogramspecializa-tionuse,toagreaterorlesserdegree,informationgeneratedbystaticprogramanalysis.Asalreadymentioned,oneofthemostwidelyusedtechniquesforstaticanalysisisabstractinterpretation[6].Infact,someoftherelationsbetweenab-stractinterpretationandpartialevaluationhavebeeniden-tifiedbefore[12,17,9,5,43,32,25,42,29,47,7].

However,theroleofanalysisissofundamentalthatitisnaturaltoconsiderwhetherpartialevaluationcouldbeachieveddirectlybyageneric,top-downabstractinterpre-tationsystem.

7.1And–OrGraphsVs.SLDTrees

Almostallexistingapproachestothe(on-line)partialevaluationoflogicprogramsusethesameoperationalse-mantics,i.eSLDresolution,forbothprogramexecutionandpartialevaluation.DifferentalternativederivationsofSLDresolutionwhichmayoccurduringexecutionconstitutedif-ferentbranchesintheSLDtree.Seeforexample[34].InpartialdeductionaslightmodificationtothissemanticsisrequiredinordertoallowincompletederivationsandthusincompleteSLDtrees.

However,itisknown[32]thatthepropagationofsuccessinformationduringpartialevaluationisnotoptimalcom-paredtothatpotentiallyachievablebyabstractinterpre-tation.ThehigheraccuracyofabstractinterpretationhasalreadybeenhintedinExample4.2.

Wenowshowafurtherexampleofthepowerofabstractinterpretation.Thistime,ratherthantheconcretedomainwewillusetheabstractdomaineterms[50]currentlyim-plementedintheCiaoPPsystem,andwhichisbasedontheconceptofregulartypes[13].Notethatinthisexampletheconcretedomaincannotbeusedstraightaway,sincethesetofvalueswhichneedtoberepresentedisinfinite.

Example7.1.Considerthefollowingprogramandtheinitialcallr(X)

r(X):-q(X),p(X).q(a).q(f(X)):-q(X).p(a).p(f(X)):-p(X).p(g(X))

:-p(X).

Itcanbeobservedthatthethirdclauseforpcanbeelim-inatedinthespecializedprogram,sincethecallsubstitutionforp(X)(i.e.,thesuccesssubstitutionforq(X))isoftheformX=aorX=f(a)orX=f(...f(a)...).Thus,theclausep(g(X)):-p(X).isuseless.OurimplementationoftheabstractdomainetermsisabletodeterminethatthevalueofXinanycalltop(X)isdescribedbytheregulartypertwhosedefinitionasaregularunaryPrologprogramfollows:

rt(a).

rt(f(A)):-rt(A).

Ourspecializerisinfactabletousethisinformationinordertoremovetheuselessclausementionedabove.Notethatstandardpartialevaluationalgorithmsbasedonunfoldingwillnotbeabletoeliminatethethirdclauseforp,sinceanatomoftheformp(X)willbe6

produced,nomatterwhatlocalandglobalcontrolisused.Inadditiontoallowingtheeliminationofuselessclauses,ourspecializationsystemisabletoperformmoreaggressiveoptimizations,asshownintheexamplebelow.

finesExampleapredicate7.2.flattenConsiderthesort/2following.

programwhichde-flatten_and_sort(Struct,Sorted_List):-sorted_int_list(Struct),

Sorted_List=Struct.

flatten_and_sort(Struct,Sorted_List):-int_list(Struct),

sort(Struct,Sorted_List).

flatten_and_sort(Struct,Sorted_List):-list_of_int_lists(Struct),

flatten_list(Struct,Unsorted_List),sort(Unsorted_List,Sorted_List).

flatten_and_sort(Struct,Sorted_List):-tree(Struct),

flatten_tree(Struct,Unsorted_List),sort(Unsorted_List,Sorted_List).

TheargumentStructisadatastructurewhichcanbe:asortedlistofintegers,alistofintegers,alistoflistsofinte-gers,oratreewhichstoresanintegerineachnon-leafnode.Thepredicatefirstdetermineswhichofthefourpossibilitiesmentionedaboveisthecaseandthen,ifneeded,itusestheappropriateprocedureforflatteningbeforesortingthelistofarguments,whichistheoutputoftheprocedure.Clearly,iftheinputdatastructureisalistofintegersthereisnoneedforflatteningthelist.Furthermore,ifitisalreadysorted,thereisnoneedtosortiteither.Thoughwecoulddefineaflattenpredicatewhichisabletoflattenbothlistsandbinarytrees,itisoftenthecasethatdistinctpredicatesforflatteninglistsandforflatteningtreesalreadyexist(indifferentsortedWeshowlibraries).

Itlist/1below,theintPrologdefinitionofofthepropertiesunarycanbeobservedthatthelasttwopredicateslists/1.ularlogicprogramswhichcorrespondtodeterministicareindeedreg-regtypetypes..

ThisisindicatedtoCiaoPPwiththedeclarationsorted_int_list([]).

sorted_int_list([N]):-int(N).

sorted_int_list([A,B|R]):-int(A),int(B),

A=int_list([H|L]):-int(H),int_list(L).:-regtypelist_of_int_lists/1.list_of_int_lists([]).

list_of_int_lists([H|L]):-int_list(H),list_of_int_lists(L).:-regtypetree/1.tree(void).

tree(t(L,N,R)):-int(N),tree(L),tree(R).

TheregtypedeclarationischeckedbyCiaoPPagainstthecodedefiningtheproperty.Ifthecodedoesnotcorrespondtoadeterministicregulartype,anerrormessageisissued.Ifitis,thisinformationcanbeusedbythespecializerinordertobeabletoabstractlyexecutetothevaluetruethewholeexecutionofthepredicate.Thesufficientconditionsforthisare(1)thepredicatedoesnotperformanyside-effects,and(2)thecallingabstractsubstitutionmustbeequalormoreparticularthanthesuccesssubstitutionforthepredicate.Notethatabstractlyexecutingapredicatecalltofalseusingregulartypesdoesnotneedtheregtypedeclaration.Anycalltoapredicatepcanbeabstractlyexecutedtofalseif(1)executionofpisguaranteednottoperformanyside-effects(2)thecallsubstitutionisincompatiblewiththesuccesssub-stitutionofporequivalently,thesuccesssubstitutionusinggoal-dependentanalysisforpandλcpistheemptysubstitu-tion⊥.ThisisfurtherdiscussedinSection7.3.Forexample,ifwecallsortedlist(Struct)withStructboundtoabinarytree,thesystemcandeterminethatthiscallisin-compatiblewiththesuccesstypeofsortedlist,whichfortheregulartypeanalysisisapproximatedbyint

list(L),append(L,[3],L1),flatten

sort(L1,

and

list/2asshownbelow.

flattensort(Struct,Sortedint

List).

flattensort(Struct,Sorted

List).

sortedlist([]).sortedlist([N]).

sorted

list([A,B|R]):-A=list([B|R]).

Sinceanalysisusingetermsinfersthatthecalltoflattensort/2hasgotanon-emptylistofintegersasfirstargument,thespecializerisabletoabstractlyexecutethetestsforlistint

and

int

gen(AO′′)istheprogram:

p(a).p(b).

{}p(A){}p(X){}{}{}{}AOr(b){}q(X)r(X)r(a)q(a){}{}{}q(b){}{}{}{}{}p(A){}{}p(A){}p(a){}{}r(a)r(a){}{}{}{}p(b){}r(b)r(b){}AO{}p(a){}{}p(b){}AO’AO’’Figure5:ExampleNodeUnfoldings

Animportantquestionisthemomentatwhichnode-unfoldingisperformed,i.e.,duringorafterbuildingAO.Thesimplestpossibilityistoperformnode-unfoldingofanor–nodepriortocomputingitssuccesssubstitution.Thiscorrespondstowhatisdoneinpartialdeduction:localcon-trolisperformedfirstandthenatomsarepassedtoglobalcontrol.Itallowsperformingnode-unfoldingaftercomput-ingthesuccess-substitutionofanor-node,evenaftercom-putingthefinaland–orgraph.Thisallowshavingmoreinformationpriortodecidingwhethertounfoldanodeornot.Thus,weconsideritamorechallengingapproach.Themaindifficultyliesinbeingabletoefficientlyrebuildtheanalysisand–orgraphsoastoreachafixpointafterthegraphismodifiedbynode-unfolding.Webelievethatthiscostcanbekeptquitereasonablebytheuseofincrementalanalysistechniquessuchasthosepresentedin[22,44].

Wenowdiscusstwoclassesofdomainswhichhavetheabovementionedfeatures.Oneclassisbasedonsetsofdepth-ksubstitutionswithsetunionastheleastupperboundoperator.However,uniformdepthboundsareusu-allyeithertooimprecise(ifkistoosmall)orgeneratemuchredundancyiflargervaluesofkarechosen.Onewaytoelim-inatethedepth-boundkintheabstractdomainistodependonasuitablewideningoperatorwhichwillguaranteethatthesetofor–nodesremainsfinite.Manytechniqueshavebeendevelopedforglobalcontrolofpartialevaluation.Suchtechniquesmakeuseofadvanceddatastructuressuchascharacteristictrees[11],[27](relatedtoneighborhoods[49]),trace-terms[14],andglobaltrees[36],andcombinationsofthem[31].Thus,itseemspossibletoadaptthesetechniquestothecaseofabstractinterpretationandformalizethemaswideningoperators.

Thesecondclassofdomainsarethosebasedonregular-types[13,19,50]andseemverygoodcandidates,theirmaindrawbackbeingthatinter-argumentdependenciesarelost.IndependentlyofourworkinCiaoPP,recentlytherehasbeenalotofinterestintheapplicationofregulartypesforimprovingpartialevaluation[15,30].Theuseofnon-deterministicregulartypes[16]presentsaninterestingtrade-offsinceononehandtheyallowimprovedaccuracybutontheothertheyrequireahighercomputationalcostandtheirapplicabilitytoprogramspecializationshouldbefurtherexplored.

7.2.3AbstractDomainsandWideningsforPartial

Evaluation

Wenowaddressthefeatureswhichanabstractdomain(andassociatedwideningoperators)shouldhaveinordertobeappropriateforperformingpartialevaluationwithintheabstractspecializationframework.Theyshould(1)simulatetheeffectofunfolding,whichishowbindingsarepropagatedinpartialevaluation.Theabstractdomainhastobecapableoftrackingsuchbindings.Thissuggeststhatdomainsbasedontermstructurearerequired.Inaddition,thedomain(2)needstocapturedisjunctiveinformation.Thismakesitpos-sibletodistinguish,inasingleabstractsubstitution,severalbindingsresultingfromdifferentbranchesofcomputation.Atermdomainwhoseleastupperboundisbasedonthemsg(mostspecificgeneralization),forinstance,willrapidlyloseinformationaboutmultipleanswerssinceallsubstitutionsarecombinedintoonebinding.

7.3CodeGenerationusingSuccessSubstitu-tions

Oneimportantfeatureofabstractspecializationnotavail-ableinpartialevaluationisthatforeachor-node,inadditiontoacallsubstitution,thereisalsoanabstractsubstitutionwhichdescribesthesuccessofthecall.Iftheproperties

capturedbytheabstractdomainaredownwardsclosed(asisthecasewithvariablebindings),itisnaturaltoconsiderspecializationw.r.t.successsubstitutionsratherthancallsubstitutions(only).Wefirstrecallsomenotationfrom[47].Definition7.4(partialconcretization).Afunc-tionpartconc(λ)θ′′.

part

conc(λ)is{X/f(Z)}.Notealsothat

part

t):-fail.,asitisknowntoproduceno

answers.Evenifthesuccesssubstitutionλsfor󰀕p,λc,λs󰀖isnot⊥,individualclausesforpwhosesuccesssubstitutionis⊥(uselessclauses)fortheconsideredλcareremovedfromthefinalprogram.

Notethatthespecializedprogrammayfailfinitelywhiletheoriginaloneloops.Webelievethiskindofoptimizationsaredesirableinmostcases.However,optimizationw.r.t.answersisoptionalinoursystem.

8.RELATEDWORK

Abstractspecializationisaframeworkwhichcanbeusedsuccessfullyindifferentcontexts.Wehavediscusseditsap-plicationtoprogramparallelizationandoptimizationofdy-namicscheduling.Theframeworkisgenericinthatitcanbeinstantiatedwithdifferentabstractdomainswhichprovidedifferentkindsofinformationaccordingtotheoptimizationswhichweaimatperforming.Iftheabstractdomaincap-turestermstructurethenitispossibletoobtaininforma-tionwhichcanthenbeusedtoperformoptimizationswhichareveryrelatedtothosewhichtakeplaceduringpartialevaluation.

Theintegrationofpartialevaluationandabstractinter-pretationhasbeenattemptedbefore,bothfromthepar-tialevaluationandtheabstractinterpretationperspectives.Somepreliminarystudiesare[12,9]inwhichanintegrationisattemptedfromthepointofviewofpartialevaluation.Anotherintegrationinthecontextoffunctionalprogramsispresentedin[5].Ontheotherhand,thedrawbacksoftradi-tionalpartialevaluationtechniquesforpropagatingsuccess

informationareidentifiedin[32]andsomeofthepossibleadvantagesofafullintegrationofpartialevaluationandab-stractinterpretationarepresentedin[25].

Fromanabstractinterpretationperspective,theintegra-tionhasalsoreceivedconsiderableattention.Thefirstcom-pleteframeworkformultiplespecializationbasedonab-stractinterpretationispresentedin[51].Thefirstim-plementationandexperimentalevaluationappearsin[43].However,thesesystemsdonotperformunfolding.

Tothebestofourknowledge,thefirstrelativelysatisfac-toryframeworkfortheintegrationofabstractinterpretationandpartialevaluationis[42,47].

Acompletelydifferentframeworkfortheintegrationofpartialdeductionandabstractinterpretationispresentedin[29].Inthisformulationatop-downspecializationalgo-rithmispresentedwhichassumestheexistenceofanabstractunfoldingandanabstractresolutionoperationandwhichgeneralizesexistingalgorithmsforpartialevaluation.Suchframeworkprovidesinterestinginsightsontheproblemsin-volvedtogetherwithcorrectnessconditionswhichcanbeusedtoprovethatagivenspecializationframework,whichpossiblyusesabstractinterpretation,iscorrect.Oneim-portantdifferenceisthatinourapproachasingle(andal-readyexisting)top-downabstractinterpretationalgorithmaugmentedwithanunfoldingruleperformspropagationofboththecallandsuccesspatternsinanintegratedfashion,whereasin[29]thesuccesspropagationusedisaddedinanadhocwayandisnotmultivariant,andthuslessprecise.Anotherdifferencebetweenthetwoapproachesisthat[29]iscapableofdealingwithconjunctionsandnotonlyatoms.Theneedformoregeneralinformationthantheconcretesubstitutionshandledbypartialevaluationhasbeeniden-tifiedrepeatedlyinpreviouswork,suchas[5,39].Thoughtheaimsofabstractspecializationandthoseof[39]arequitesimilar,themeansproposedtoachievethemarecompletelydifferent.Also,abstractinterpretationisnotusedanditstickstothemoretraditionalSLDsemantics.

Morerecently,[7]presentsaverygeneralviewwhichinte-gratesprogramtransformationandabstractinterpretation.Thisresultallowsformalizingpartialevaluationasanab-stractinterpretation(asdonebyabstractspecialization).Thisnewformalizationofprogramtransformationmayen-ableothernovelprogramoptimizationtechniques.

9.CONCLUSIONS

Abstractspecializationcanbeseenasasemanticap-proachmuchinthesamewayasexistingframeworksforpartialdeduction[35,26,10,28]andalsoasotherattemptsattheintegrationofpartialevaluationandabstractinter-pretationoflogicprograms[29,15,30].Oneofthemaindifferencesbetweenabstractspecializationandtheafore-mentionedtechniquesistheunderlyingsemantics.Abstractspecializationisbasedonand–ortreeswhereastherestarebasedonSLDtrees.ThoughSLD-treeshavetheconceptualadvantagethatthesemanticsusedforprogramspecializa-tionisalmostidenticaltothatusedduringprogramexecu-tion,ourapproachhasotherpracticalandconceptualad-vantages.Forexample,optimizationsbasedonand–ortreescanbedonetopreservenumberandorderofsolutions,anissueoftenoverlookedbytraditionalpartialdeductionsys-tems.Furthermore,theyallowperformingoptimizationsnotachievablebymeansofunfolding,includingthedetectionofinfinitefailure.

Apragmaticmotivationforthisworkistheavailabilityofoff-the-shelfgenericabstractinterpretationenginessuchastheoneinCiaoPP[21]7whichgreatlyfacilitatetheefficientimplementationofanalyses.Suchanalysiscandealwithallfeaturesofrealprograms[2]inanaccurateway,includingbuiltins,librariesandmodules[46].But,moregenerally,wearguethattheexistenceofsuchanabstractinterpreterinadvancedoptimizingcompilersislikely,andthususingtheanalyzeritselftoperformpartialevaluationcanresultinagreatsimplificationofthearchitectureofthecompiler.

Acknowledgments

ThisworkhasbeenfundedinpartbyEUISTFETprojectASAP(IST-2001-38059)andbyMCyTprojectsCUBICO(TIC02-0055)andADELA(HI2000-0043).TheauthorswouldliketothankF.Buenoforhishelpintheimplemen-tationofthetoolshereinpresented.ThanksarealsoduetoM.Garc´ıadelaBanda,PJ.Stuckey,andK.Marriottwhohaveparticipatedinthedevelopmentofsomeoftheappli-cationspresented,toJ.P.Gallagher,whohascollaboratedinthestudyoftherelationbetweenabstractinterpretationandpartialevaluation,andtoC.Vaucheretforhisimple-mentationoftheetermsdomain.

10.REFERENCES

[1]M.Bruynooghe.APracticalFrameworkforthe

AbstractInterpretationofLogicPrograms.JournalofLogicProgramming,10:91–124,1991.

[2]F.Bueno,D.Cabeza,M.Hermenegildo,and

G.Puebla.GlobalAnalysisofStandardProlog

Programs.InEuropeanSymposiumonProgramming,number1058inLNCS,pages108–124,Sweden,April1996.Springer-Verlag.

[3]R.M.BurstallandJ.Darlington.Atransformation

systemfordevelopingrecursiveprograms.JournaloftheACM,24(1):44–67,1977.

[4]C.ConselandO.Danvy.TutorialNotesonPartial

Evaluation.InACMSIGPLAN-SIGACTSymposiumonPrinciplesofProgrammingLanguagesPOPL’93,pages493–501,1993.ACM.

[5]C.ConselandS.Koo.Parameterizedpartial

deduction.ACMTransactionsonProgrammingLanguagesandSystems,15(3):463–493,July1993.[6]P.CousotandR.Cousot.AbstractInterpretation:a

UnifiedLatticeModelforStaticAnalysisofProgramsbyConstructionorApproximationofFixpoints.InFourthACMSymposiumonPrinciplesof

ProgrammingLanguages,pages238–252,1977.[7]P.CousotandR.Cousot.SystematicDesignof

ProgramTransformationFrameworksbyAbstractInterpretation.InPOPL’02:29STACM

SIGPLAN-SIGACTSymposiumonPrinciplesof

ProgrammingLanguages,pages178–190,2002.ACM.[8]M.G.delaBanda,K.Marriott,andP.Stuckey.

EfficientAnalysisofConstraintLogicProgramswithDynamicScheduling.InInternationalLogicProgrammingSymposium,1995.MITPress.

[9]J.Gallagher.StaticAnalysisforLogicProgram

Specialization.InWorkshoponStaticAnalysis

[26]J.Komorovski.AnIntroductiontoPartialDeduction.

InMetaProgramminginLogic,ProceedingsofMETA’92,volume649ofLNCS,pages49–69.Springer-Verlag,1992.

[27]M.Leuschel.Ecologicalpartialdeduction:Preserving

characteristictreeswithoutconstraints.InM.Proietti,editor,Proc.LOPSTR.Springer-Verlag,1995.

[28]M.Leuschel.AdvancedTechniquesforLogicProgram

Specialisation.PhDthesis,K.U.Leuven,May1997.[29]M.Leuschel.ProgramSpecialisationandAbstract

InterpretationReconciled.InJointInt.ConferenceandSymposiumonLogicProgramming,June1998.[30]M.LeuschelandS.Gruner.Abstractconjunctive

partialdeductionusingregulartypesanditsapplicationtomodelchecking.InLogicProgramSynthesisandTransformation(LOPSTR),number2372inLNCS.Springer,2001.

[31]M.LeuschelandB.Martens.Globalcontrolforpartial

deductionthroughcharacteristicatomsandglobaltrees.InO.Danvy,R.Gl¨uck,andP.Thiemann,

editors,Proceedingsofthe1996DagstuhlSeminaronPartialEvaluation,LNCS1110,pages263–283,SchloßDagstuhl,1996.

[32]M.LeuschelandD.Schreye.Logicprogram

specialisation:Howtobemorespecific.InH.KuchenandS.Swierstra,editors,Proceedingsofthe

InternationalSymposiumonProgrammingLanguages,Implementations,LogicsandPrograms(PLILP’96),LNCS1140,pages137–151,Aachen,Germany,September1996.

[33]M.Leuschel,D.D.Schreye,andD.A.deWaal.A

conceptualembeddingoffoldingintopartialdeduction:towardsamaximalintegration.In

M.Maher,editor,ProceedingsoftheJointInt,.Conf.andSymp.onLogicProgramming(JICSLP’96).MITPress,1996.

[34]J.Lloyd.FoundationsofLogicProgramming.

Springer,second,extendededition,1987.

[35]J.LloydandJ.Shepherdson.PartialEvaluationin

LogicProgramming.JournalofLogicProgramming,11(3–4):217–242,1991.

[36]B.MartensandJ.Gallagher.Ensuringglobal

terminationofpartialdeductionwhileallowingflexiblepolyvariance.InL.Sterling,editor,

ProceedingsICLP’95,pages597–611,ShonanVillageCenter,Japan,June1995.MITPress.

[37]K.Muthukumar,F.Bueno,M.G.delaBanda,and

M.Hermenegildo.AutomaticCompile-time

ParallelizationofLogicProgramsforRestricted,Goal-level,IndependentAnd-parallelism.JournalofLogicProgramming,38(2):165–218,February1999.[38]K.MuthukumarandM.Hermenegildo.Completeand

EfficientMethodsforSupportingSideEffectsinIndependent/RestrictedAnd-parallelism.In1989InternationalConferenceonLogicProgramming,pages80–101.MITPress,June1989.

[39]A.PettorossiandM.Proietti.Atheoryoflogic

programspecializationandgeneralizationfordealingwithinputdataproperties.InSpringer-Verlag,editor,DagstuhlSeminaronPartialEvaluation,number1110inLNCS,1996.

[40]G.Puebla,F.Bueno,andM.Hermenegildo.An

AssertionLanguageforConstraintLogicPrograms.InP.Deransart,M.Hermenegildo,andJ.Maluszynski,editors,AnalysisandVisualizationToolsforConstraintProgramming,number1870inLNCS,pages23–61.Springer-Verlag,September2000.[41]

G.Puebla,M.G.delaBanda,K.Marriott,andP.Stuckey.OptimizationofLogicProgramswithDynamicScheduling.In1997International

ConferenceonLogicProgramming,pages93–107,Cambridge,MA,June1997.MITPress.

[42]

G.Puebla,J.Gallagher,andM.Hermenegildo.TowardsIntegratingPartialEvaluationina

SpecializationFrameworkbasedonGenericAbstractInterpretation.InM.Leuschel,editor,ProceedingsoftheILPS’97WorkshoponSpecializationofDeclarativePrograms,October1997.PostILPS’97Workshop.[43]

G.PueblaandM.Hermenegildo.ImplementationofMultipleSpecializationinLogicPrograms.InProc.ACMSIGPLANSymposiumonPartialEvaluationandSemanticsBasedProgramManipulation,pages77–87.ACMPress,June1995.

[44]

G.PueblaandM.Hermenegildo.Optimized

AlgorithmsfortheIncrementalAnalysisofLogicPrograms.InInternationalStaticAnalysis

Symposium,number1145inLNCS,pages270–284.Springer-Verlag,September1996.

[45]

G.PueblaandM.Hermenegildo.AbstractMultipleSpecializationanditsApplicationtoProgram

Parallelization.J.ofLogicProgramming.SpecialIssueonSynthesis,TransformationandAnalysisofLogicPrograms,41(2&3):279–316,November1999.[46]

G.PueblaandM.Hermenegildo.SomeIssuesinAnalysisandSpecializationofModularCiao-PrologPrograms.InSpecialIssueonOptimizationandImplementationofDeclarativeProgrammingLanguages,volume30ofElectronicNotesinTheoreticalComputerScience.Elsevier-NorthHolland,March2000.

[47]

G.Puebla,M.Hermenegildo,andJ.Gallagher.AnIntegrationofPartialEvaluationinaGenericAbstractInterpretationFramework.InO.Danvy,editor,ACMSIGPLANWorkshoponPartialEvaluationandSemantics-BasedProgram

Manipulation(PEPM’99),numberNS-99-1inBRISCSeries,pages75–85.UniversityofAarhus,Denmark,January1999.

[48]

H.TamakiandM.Sato.Unfold/FoldTransformationsofLogicPrograms.InSecondInternational

ConferenceonLogicProgramming,pages127–138,Uppsala,Sweden,1984.

[49]

V.Turchin.Thealgorithmofgeneralizationinthesupercompiler.InD.B.rner,A.Ershov,andN.Jones,editors,Proc.oftheIFIPTC2WorkshoponPartialEvaluationandMixedComputation,pages531–549.North-Holland,1988.

[50]

C.VaucheretandF.Bueno.Morepreciseyetefficienttypeinferenceforlogicprograms.InInternationalStaticAnalysisSymposium,number2477inLNCS,pages102–116.Springer-Verlag,September2002.[51]

W.Winsborough.MultipleSpecializationusing

Minimal-FunctionGraphSemantics.JournalofLogicProgramming,13(2and3):259–290,July1992.