A Survey on Multi-Stage Programming Languages

ASurveyonMulti-StageProgrammingLanguagesZheYangJanuary16,19991IntroductionAtraditionalsoftwaresystemconsistsofmodulesofxedprogramcode;be-tweenthesemodulescomputeddataarepassed.Butitisalsonotuncommontoseeanotherformofsoftwareorganization,wheresomepartofthesoftwaregeneratescode(insteadofdata)tobeexecutedatalaterstage.Thiskindofprogrammingparadigmissometimesreferredtoasmeta-programming,becausecertainprogrammingtasksinvolvemanipulationofprogramcode.Itisalsocalledmulti-stageprogramming,becausethereisgenerallyacleardivisioninthecomputationstages,wheretheresultsfromearlierstagescanbethecodeforlaterstages.Examplesofmulti-stageprogrammingincludetranslatorssuchascom-pilers,run-timecodegeneration,andadvancedsyntaxabstractionmecha-nism(alsocalledmacrosystems)suchasthatofScheme’s.Compiler.Acompilerusuallyinvolvestwostages:compiletimeistherststage,whentargetcodeisgenerated;thegeneratedtargetcodeisexecutedatthesecondstage,runtime.Otherexamplesoftranslatorsrangefromparsergenerators,whichtranslategrammarlestoprogramcodeinmoreconventionallanguages,toembeddedSQLprocessors,whichtranslateSQLstatementsembeddedinaprogramwritteninsomehostlanguagetocodefragmentsofthishostlanguage.Mostofthesecanbethoughtofascompilersofsomespecicationlanguages.Run-timecodegeneration.Insteadofsupplyingxedargumentstothesameroutineagainandagain,generatingspecializedprogramcodeatrun-timetobereusedseveraltimesoftenoersasignicantimprove-mentintimeeciency.1TakethestandardexampleoftheUnixleaccessfunctions[25]:whenaleisopenedforaccess,variousmodes(read/read-write,text/binary,rewrite/append,etc.)aresuppliedandxed;later,whenthefunctionreadorthefunctionwriteisinvoked,thereneedstobealengthychecktoensurethatnoneoftheseaccessmodesareviolated.Thisoftenaddsasubstantialoverheadtotheessentiallycheapcostofreadandwrite,especiallywhenmostleaccesseshappeninthebuers,andnotthroughsecondarystorages.Bygeneratingspecializedcodeforthereadandwritefunctions,thesecheckscanbeeliminated.Advancedsyntax-abstractionmechanism.Somelanguages,suchasScheme,allowuserstodenesyntaxabstractions,whichcomputesourcecodefromcodethatconformstonewlyintroducedsyntacticforms.Withthismechanism,itisveryeasytoimplementdomain-speciclanguages[16]directlyinthislanguage;OlinShivers’sScsh(SchemeShell)system[28]givesoneexampleofsuchembeddedim-plementationofadomain-speciclanguage.Itisnothardtoseesomeoftheadvantagesoeredbymulti-stagepro-gramming:itdeliversgenerality(e.g.,acompilercandealwithvarioussourceprogramslikeaninterpreter)alongwitheciency(thecompiledre-sultofacompilerrunsmuchfasterthanrunningthesourceprogramusinganinterpreter);ithelpsdetecterrorsatearlystages(compilersfacilitatestaticdebugging,byperformingvariousstaticcheckssuchastypechecking);itmayaddexpressivenesstothelanguage|thecorrespondingfunctionformofsyntaxabstractionsoftenhaveanintriguingdependencybetweenthetypesanddataofitsarguments.Centraltotheseargumentsistheobser-vationthataresultfromarunofanearlystagemightbereusedseveraltimesinalaterstage,andtheamortizedcostofgeneratingspecializedcodeismuchsmallerthanthatoftherepeatedcomputation.Thesameargumentwasusedtodemonstratetheadvantageofpartialevaluation[15].Apartialevaluatortakesaprogramandsomeofitsin-putsandgeneratesaspecializedversionoftheprogram(calledtheresidualprogram),which,takingtheremaininginputs,givesthenalresult.Com-putationsthatdependsonlyontheknowninputsareperformedatthespecializationprocess,leavingaresidualprogramthatisoftenmuchmoreecientthantheoriginalone.Infact,partialevaluationiscloselyrelatedtomulti-stageprogramming.Thespecializationandtheexecutingoftheresidualprogramaretwostagesinthesenseofmulti-stageprogramming.Manyinstancesofthemulti-stageprogrammingparadigm,suchascompilersandrun-timecodegeneration,are2alsothestandardapplicationsofpartialevaluation.Ontheotherhand,thestudyofmulti-stageprogramming,especiallyitslanguagesupport,emergedfromthestudyofpartialevaluation,whenpeopleconsideredproblemssuchasthecorrectnessandtheusercontrollabilityofthespecializationprocess.Theparadigmofmulti-stageprogrammingisbackedupbythedesignphilosophyofmoderndigitalcomputers,whereprogramcodecanbema-nipulatedjustasusualdata.However,thereisstillverylittlehigh-levelprogramminglanguagesupportformulti-stageprogramming;bysuch\lan-guagesupportwemeanmechanismsthatmakeiteasytoconstructprogramcode,toguaranteecertainpropertiesofthegeneratedcodesuchasitstypecorrectness,andeventoexecutesuchprogramcode(i.e.,movetothenextstageofcomputation)inthesamerun.Multi-stageprogramminglanguageshavebeendevelopedinrecentyearstoprovideagoodbasisforthemulti-stageprogrammingparadigm.Theselanguagesallowuserstowritecodeconstructionsdirectlyintheformofsourcecode,insteadofnumerousdataconstructorsforaspecic\codetype;specialstagingannotationsareusedtoallowuserstospecifythesep-arationofcodeindierentstages.Thetypesystemsoftheselanguagesguaranteethatthegeneratedcodeiswell-formed,therebyguaranteeingthattheentireexecutionwillnot\gowrong.Thisisofparticularimportanceforapplicationssuchasrun-timecodegeneration,whereverifyingthe