Referential Transparency in Imperative Languages

ReferentialTransparenyinImperativeLanguagesANTHONYC.DANIELSUniversityofKentatCanterburyWeformalisereferentialtransparenyofexpressionsinimperativelanguages.Weestablishtherelationshipbetweenreferentialtransparenyandside-eets,andexplaintherelatedpropertyofextensionalityoffuntions.Thenwepresentanewlanguagebasedontheseideas.Althoughsomeofitsfeaturesarepresentinotherlanguages,wegofurtherbyprovidingaproofthatourlanguageformallysatisespropertiessuhasreferentialtransparenyandextensionalitywithrespettoitsdenotationalsemantis.CategoriesandSubjetDesriptors:D.3.1[ProgrammingLanguages℄:FormalDenitionsandTheory|Semantis;D.3.3[ProgrammingLanguages℄:LanguageConstrutsandFeatures|Proedures,funtions,andsubroutines;F.3.2[LogisandMeaningsofPrograms℄:SemantisofProgrammingLanguages|Denotationalsemantis;F.3.3[LogisandMeaningsofPro-grams℄:StudiesofProgramConstruts|FuntionalonstrutsGeneralTerms:Languages,ReliabilityAdditionalKeyWordsandPhrases:ReferentialTranspareny,Eulid,oam,ImperativeLan-guages,Aliasing,Interferene1.INTRODUCTIONExpressionswerearuialinnovationintheearlyevolutionofhigh-levelprogram-minglanguages,providingaompatandreadablenotationforomputingvalues.Oneissuewhihisstillthesubjetofintenseinvestigationiswhethertheyshouldallowside-eets,bywhihwemeantheabilitytoupdatevariablesorperformIOduringexpressionevaluation.Intheirfavour,side-eetsanbeveryusefulandgivetheprogrammergreaterfreedomandontrol.Onthedownside,expressionswithside-eetsarelesstransparentandonsequentlyhardertounderstandandreasonabout,partiularlywhenside-eetsupdatevariablesintheexpression.Intheory,tounderstandanexpressionwithside-eetswemustfollowthelanguageimplementation’sdesriptionofexpressionevaluation(ifoneexists)andworkouttheside-eetsinallfuntionallsandsoon.Inpratie,thisisnotalwaysnees-sarybeausetheside-eetsanbeorthogonaltotheexpression,inthesensethattheydonotaetthevalueoftheexpression,andsoweanignorethemwhenweonsiderthevaluepartoftheexpression.However,theside-eetsanstillbedif-ulttounderstandbeausetheysometimesinterferewitheahotherresultinginverysubtleerrors.Expressionnotationhidestheseside-eetsandobsurestheor-Author’saddress:A.C.Daniels,ComputingLaboratory,UniversityofKentatCanterbury,Can-terbury,Kent,CT27NF,UK.Permissiontomakedigital/hardopyofallorpartofthismaterialwithoutfeeforpersonalorlassroomuseprovidedthattheopiesarenotmadeordistributedforprotorommerialadvantage,theACMopyright/servernotie,thetitleofthepubliation,anditsdateappear,andnotieisgiventhatopyingisbypermissionoftheACM,In.Toopyotherwise,torepublish,topostonservers,ortoredistributetolistsrequirespriorspeipermissionand/orafee.ACMTransationsonProgrammingLanguagesandSystems,Vol.TBD,No.TDB,MonthYear,Pages1{??.2AnthonyC.Danielsdertheyourin,whihisusuallytheorderofexpressionevaluation.Re-arranginganexpressionmayormaynotalteritsvalue,butitwillhangetheorderofanyside-eets.Mostimperativelanguagesoptforexibilityandallowunrestritedside-eets.Inontrast,Eulid[Lampsonetal.1977;Popeketal.1977℄andoam[INMOSLimited1988℄imposerestritionsonside-eets,butfordierentreasons:Eulidwasdesignedforverifyingprogramorretness,andtherestritionsonside-eetsmaketheproofrulesmuhsimpler;oamisaonurrentlanguage,andstritontroloverside-eetsisneessaryforpreventingunwantedinterferenebetweenproesses.(InSetion5wedisussapproahestakenbyotherlanguagestoombin-ingside-eetsandexpressions.)Althoughitiseasytounderstandtherationaleforthedesignoftheselanguages,itismorediÆulttostatepreiselythepropertiesthatEulidandoamhave(intheiroreimperativesubset)whihlessrestritivelanguagesdonot.Inthispaperweaddressthisbydeningandprovingpropertiesofvariousminiexpressionlanguages,designedtoaptureertainkeyfeatures.Considerpropertiesusedinequationalreasoninginvolvingarithmetiexpres-sions,forinstane,inthefollowingsteps,(x+1)*f(x)*(x-1)+f(x)=hommutativityandassoiativityof*if(x)*(x+1)*(x-1)+f(x)=hdistributivityof*over+if(x)*(x*(x-1)+1*(x-1))+f(x)=h:::manymoresmallsteps:::if(x)*x*xPropertiessuhasommutativityofadditionanbeprovenbyusingthesemantistoshowthatE1+E2=E2+E1holdsforanyE1andE2.Whensuhapropertyholdsthisisgenerallyquiteeasy.However,notiethateverysteprequiresthefollowingproperty:foranysubexpressionE1andequivalentexpressionE2,wemayreplaeE1withE2intheoverallexpressionwithouthangingitsmeaning.Thispropertymustholdforthelanguageifwearetouseequationalreasoningasitisrequiredineverystep.Weshallrefertothispropertyas\referentialtranspareny,butitisalsoknownas\substitutivityofidentityor\Leibnitz’slaw.InSetion2weinvestigatereferentialtransparenyforvariousexpressionlan-guages.Wendthatitsdenitionneedstailoringtotakeaountoffeaturessuhasvariables,funtionsandtypes,soitisnotanabsolutenotion.Foromparisonweanalysealanguagewithside-eetsandexplainformallytheonsequenesthattheinlusionofside-eetshasforreferentialtransparenyandforotherproperties.Wethenonsideruser-denedfuntionsandextensionality,whihisthepropertythatfuntionsalwaysyieldthesameresultgiventhesameinputvalue,regardlessofthestate.Finallyweprovereferentialtransparenyfortypedexpressions.So,inSetion2welarifytheintuit