Duplication and Partial Evaluation--- For a Better

,,1{40()cKluwerAcademicPublishers,Boston.ManufacturedinTheNetherlands.DuplicationandPartialEvaluation|ForaBetterUnderstandingofReectiveLanguages|[e-mail]nScience,FacultyofScience,TheUniversityofTokyo,7-3-1Hongo,Bunkyo-Ku,Tokyo,113,[e-mail]alEngineering,FacultyofEngineering,TheUniversityofTokyo,7-3-1Hongo,Bunkyo-Ku,Tokyo,113,[e-mail]nScience,FacultyofScience,TheUniversityofTokyo,7-3-1Hongo,Bunkyo-Ku,Tokyo,113,JapanReceivedOctober10,1993;RevisedAugust6,1994,March30,1995Editor:DanielP.FriedmanandAkinoriYonezawaAbstract.Thispaperpresentsageneralimplementationframeworkforreectivelanguages.Itallowsustosystematicallybuildreectivelanguageswhichhavethefollowingfavorableproper-ties:(1)userprogramsareallowedtoaccessandchange(partsof)metalevelinterpreters,(2)reectivefacilitiesareavailableateverylevel,(hencethereexistsconceptuallyaninnitetowerofinterpreters),and(3)theinterpreterrunsasecientlyastheconventional(directlyimplemented)metacircularinterpreterwhenreectionisnotused.Ourschemeisdividedintothreestages.First,wedeneinterpreterswhichgivetheoperationalsemanticsofeachlevel,andconceptuallyconstructtheinnitetoweroftheseinterpreters.Theyarethenduplicatedtoobtaindirectlyexecutedinterpreters,whileintroducingdoubleinterpretationtomaintainredenabilityofinter-preters.Finally,partialevaluationisemployedtocollapsethedoubleinterpretationintosingleinterpretation.WeillustrateourschemebyimplementingaparticularreectivelanguagecalledBlackinScheme,butitisgeneralenoughtobeappliedtootherreectivelanguages.ThepapergivesthecompleteSchemeimplementationofBlackanddemonstratessomeexamples.WealsoshowhowasystemwiththedeltaabstractionintroducedbyBlondcanbeconstructedinourframework.Keywords:reection,partialevaluation,metacircularinterpreter,directexecution,interpreta-tion,inniteregression\BlackisBlack|LosBravos1.IntroductionReectiveprogramminglanguagesprovidehighexibilityandextensibilitybyal-lowinguserprogramstoaccessandchangetheirlanguageimplementation(andtherebysemantics)fromwithinthemselves.Tochangethelanguagesemanticsinconventionalnon-reectivelanguages,weneedtofullyunderstandthelowlevel2implementationdetailsandcarefullyaltertheirimplementation(eitheraninter-preteroracompiler),whichisusuallywritteninlowerlevellanguages.Reectivelanguagesallowsuchmodicationswithinthesamelanguageframeworkusinghighlevelabstractionswithoutunderstandinglowlevelimplementation.Becauseofitsexibilityandextensibility,reectionisalsoimportantforpracticalpurposes,i.e.,asabasisfor\openimplementation[9].Animportantcharacteristicofreectivelanguagesistheirtowerstructure.Inreectivelanguages,userprogramsatthebaselevel(orlevel0)areinterpretedbytheinterpreterrunningatthelevelabove(level1,ormetalevel),whichisinturninterpretedbytheinterpreterrunningatlevel2,andsoon.Conceptually,thereisaninnitetowerofinterpreters.Reectivelanguagespermituserprogramstoexecuteprogramsatanylevelinthetower,possiblyaccessing(introspecting)ormodifyinginterpretersofupperlevels.However,theinnitetowerstructuremakesitdiculttoimplementreectivelan-guages.InconventionalLisp-basedreectivelanguages,suchasBrown[5][13]andBlond[2],thetowerissimulatedbylazilycreatinginterpreterswhicharedirectlyexecutedbymachine,insteadofbyinterpretationatthelevelabove.Althoughtheuseofdirectlyexecutedinterpretersispreferableforeciency,itbecomesimpos-sibleforuserprogramstoalter(partsof)theinterpretersselectively,sincetheyarealreadyinmachinecodeform.Forexample,supposewewanttomodifythemetalevelinterpretersothatitprintsoutalltheexpressionsitevaluates.Ifthestructureandimplementationofthemetalevelinterpreterwereavailabletouserprograms,wecouldachievethisjustbyinsertingaprintfunctionatanappropri-ateplaceintheinterpretercode.SuchmodicationsarenotpossibleinBrownandBlondsincetheinterpreterisdirectlyexecutedandavailableonlyasasinglemonolithicfunctioncalledmeaning.JeersonandFriedman,ontheotherhand,presentedaSimpleReectiveInter-preterIR[7],inwhichuserprogramsareallowedtoaccessandchangethemetalevelinterpreters.BecauseinIR,theinterpreterrunningateachlevelisimplementedasordinaryuser-denedfunctions,andactuallyinterpretedbytheinterpreteronelevelabove,wecanfreelyredeneittochangeitssubsequentbehavior.However,sinceIRisimplementedbyexecutingametacircularinterpreterontopofitself,ithastwodrawbacks:(1)itisextremelyinecientduetodouble(triple,etc.)interpretation,and(2)itrequirestheconstructionofaninnitetowerifwewanttoachievereectionateverylevel.Tobehighlyexibleandextensible,reectivelanguagesshouldfulllthefollowingrequirements:1.Userprogramsareallowedtoaccessandchange(partsof)metalevelinter-preters.2.Reectivefacilitiesareavailableateverylevel.3.Theinterpreterrunsecientlywhenreectionisnotused,andreasonablywellevenifpartsofitaremodied.3Inthispaper,wepresentageneralframeworkfortheimplementationofreectivelanguagesthatsatisfythesethreerequirements.Tobemorespecic,