1 In Combinators and Functional Programming Langua

1In:CombinatorsandFunctionalProgrammingLanguagesG.Cousineau,P-L.CurienandB.RobinetEditors,LectureNotesinComputerSciencen.242,Springer-Verlag,1986TheAmberMachineLucaCardelli1AT&TBellLaboratories,MurrayHill,NJ07974AbstractTheAmbermachineisastackmachinedesignedasanintermediatelanguageforcompilinghigher-orderlanguages.ThecurrentversionisspecializedfortheAmberlanguage.Themachinesupportsasetofbasicandstructureddatatypes,functionalclosures,signals,bitmapgraphics,persistentobjectsandmeta-levelexecution.ThelatterisneededastheAmbercompilerisentirelywritteninAmber(abovetheAmbermachinelevel)andneedstoswitchlevelwhenexecutingaprogramithasjustcompiled.Asetofimplementationstrategiesareadmissibleforthismachine,includingbyte-codeinterpretation,threadedcodeinterpretationandcompilationtonativecode.Thecurrentimplementationisbasedonabyte-codeinterpreterandaone-spacecompactingcollector,andrunsonaMacintosh.IntroductionTheAmbermachineisastackmachinedesignedasanintermediatelanguageforcompilinghigher-orderlanguages,inthetraditionofSECDmachines[Landin64]andcombinatormachines[Turner79][Curien86].ThisisarevisionoftheFunctionalAbstractMachinedescribedin[Cardelli83,Cardelli84],andisspecializedfortheAmberlanguage[Cardelli86].Theamountofspecializationrequiredforaparticularlanguageinthegeneralclassofhigher-orderalgorithmiclanguagesismarginal;itmostlyinvolvesthesetofprimitivedatatypesanddoesnotaffectthebasicorganizationofthemachine.Themachinesupportsasetofbasicdatatypes,functionalclosures,signals,persistentobjectsandmeta-levelexecution.ThelatterisneededastheAmbercompilerisentirelywritteninAmber(abovetheAmbermachinelevel)andneedstoswitchlevelwhenexecutingaprogramithasjustcompiled.Asetofimplementationstrategiesareadmissibleforthismachine,includingbyte-codeinterpretation,threadedcodeinterpretationandcompilationtonativecode.Thecurrentimplementationisbasedonabyte-codeinterpreterandaone-spacecompactingcollector,whilethesimilarFunctionalAbstractMachineforthe1Currentaddresss:DECSRC,130LyttonAve,PaloAlto,CA94301.2MLlanguageiscompiledtoVAXcodeandhasatwo-spacecompactingcollector.TheFormatLevelTheformatlevelisthelowestleveloftheAmbermachine.Thislevelislanguageindependentandcanbeconsideredasageneral-purposeheapmanager.Itsupportsgarbagecollectionanddatapersistence,withoutanyknowledgeofthelanguageoreventhedatastructuressupportedathigherlevels.Datacanbeboxedorunboxed.Unboxeddataexistsonthestackorinsideotherdatastructures,anddoesnotrequirememoryallocation.Wedistinguishtwokindsofunboxed:characters(normallyonebyte)andwords(normallyfourbytes).UnboxedCharPointer/IntegerValueMarksWordUnboxedwordsarefurtherstructured.Theycontainmarkbits(usedbythegarbagecollectorandthepersistencemechanism),aflagindicatingwhetherthisisanintegerorapointer(again,neededbythegarbagecollector),andanintegerorpointervalue.Boxedvaluesareallocatedintheheap.Theyhaveaheaderandadatasection:FormatSizeMarksHeaderDataBoxedTheheadercontainsmarkbits(thesameasinunboxedwords),acodeindicatingtheformatofthedatasection,andasize(numberofitemsinthedatasection).Correspondingtoeachkindofunboxeddata,thereisaformatofboxeddata.Ascalarisasequenceofunboxedcharacters,andavectorisasequenceofunboxed3words.sn0n-1Scalar0n-1VectornvThefollowingroutinesaresupportedforthemanipulationofdataformats:mkInt(i:int):WordconvertanordinaryintegertoanunboxedintegermkPtr(p:ptr):WordconvertanaddresstoanunboxedpointerisInt(w:Word):booltestwheteranunboxedwordisanunboxedintegerisPtr(w:Word):booltestwhetheranunboxedwordisanunboxedpointerdeInt(w:Word):intconvertanunboxedintegertoanordinaryintegerdePtr(w:Word):ptrconvertanunboxedpointertoanaddressallocScalar(n:int):BoxedallocateaboxedscalarofsizenallocVector(n:int):BoxedallocateaboxedvectorofsizenisScalar(b:Boxed):booltestwhetheraboxedisascalarisVector(b:Boxed):booltestwhetheraboxedisavectorscalarSize(b:Boxed):intgetthesizeofaboxedscalarvectorSize(b:Boxed):intgetthesizeofaboxedvectorscalarNth(b:Boxed,n:int):Chargetthen-thitemofaboxedscalarvectorNth(b:Boxed,n:int):Wordgetthen-thitemofaboxedvector4setScalarNth(b:Boxed,n:int,c:Char)setthen-thitemofaboxedscalarsetVectorNth(b:Boxed,n:int,w:Word)setthen-thitemofaboxedvectorAholdstackisprovidedtostoreboxeddatatemporarilyorpermanently.Thegarbagecollectortracesdatastartingfromtheholdstack,andrecyclesallthestructureswhicharenotaccessiblefromtheholdstack.Theholdstackisastackofindirectionsintotheheap;suchindirectionsarecalledholds.Oftenitisnecessarytomanipulateholds,insteadofdirectlymanipulatingdata,becausethegarbagecollectormayunexpectedlystartandinvalidatedirectpointerstodata.pushHold(b:Boxed):Holdpushaboxedontheholdstack,obtainingaholdtoitpopHold():Boxedpoptheholdstack,obtainingtheboxedontopofitdeHold(h:Hold):Boxedextractaboxedfromaholdcollect()garbagecollection,normallycalledbyallocScalarandallocVector.Garbagecollectioncanbeimplementedinavarietyofways.ThecurrentAmberimplementationusesaone-spacecompactingcollector.Thistechniquerequirestwomarkbitsinboxedandunboxeddata,andanextrarelocationwordforeveryboxeddatum(whichisprefixedtotheheaderfieldandisin