The Shift Programming Language and Run-time System

TheShiftProgrammingLanguageandRun-timeSystemforDynamicNetworksofHybridAutomataAkashDeshpande,AleksGolluandLuigiSemenzatofakash,gollu,[e-mail]lEngineeringandComputerSciencesUniversityofCaliforniaatBerkeley,Berkeley,CA94720Abstract.Shiftisaprogramminglanguagefordescribingandsimulatingdynamicnetworksofhybridautomata.Suchsystemsconsistofcomponentsthatcanbecreated,interconnectedanddestroyedasthesystemevolves.Componentsexhibithybridbehavior,consistingofcontinuous-timephasesseparatedbydiscrete-eventtransitions.Componentsmayevolveindepen-dently,ortheymayinteractthroughselectedstatevariablesandevents.Theinteractionnetworkitselfmayevolve.Shiftiscurrentlyusedintwoapplications:automatedhighwaysystemsandcoordinatedsubmarinesystems.TheShiftmodeloerstheproperlevelofabstractionfordescribingtheseandotherapplicationssuchasairtraccon-trolsystemsandroboticshop-oorswhosedynamicrecongurationscannotbecapturedeasilybyconventionalmodels.Wehaveimplementedacompilerandarun-timesystemforShift.ThecompilertranslatesaShiftprogramintoaCprogram,which,whenrun,simulatesthedesignspeciedintheShiftsourceprogram.MoreinformationaboutShiftcanbefoundatgurablehybridsystems.Ourprimaryapplicationisthespecica-tionandanalysisofdierentdesignsforautomaticcontrolofvehiclesandhighwaysystems[22].Weneedtocapturethebehaviorofvehicles,sensors,actuators,com-municationdevicesandcontrollersinastructuredandmodularspecication[6].Modelsforthesecomponentsareprovidedbydierentgroupsofexpertsandthenintegratedindierentwaysforcomparativeanalysis.Fromourpreviousexperienceinmodeling[14,9],analysis[20,5,12]andimplementation[8,10],weadoptedthehybridsystemsapproachformodelingthesystemcomponents.Sincespatialrela-tionshipsbetweenvehicleschangeastheymove,ourapplicationischaracterizedbyadynamicallychangingnetworkofinteractionsbetweensystemcomponents.Wedecidedtokeepthelanguagesimpleandsmall.Shifthasonlyonenumbertype(correspondingtotheCdoubletype),nofunctions(althoughitcanuseexternalfunctionswritteninC)andithasnomemorymanagementprimitives,relyingongarbagecollectioninitsimplementation.Inspiteofitssimplicity,Shiftprogramsaresurprisinglypowerfulyetcompact,thankstoitshigh-levelsystemabstractionswhichincludedierentialequations,statetransitionsandsynchronouscompositions,allwithintheframeworkofdynamicnetworksofhybridautomata.WhereastheinitialapplicationthatledtothedevelopmentofShiftwasmodel-ingandsimulationofvehiclesandhighways,theShiftlanguagehassincealsobeenusedincoordinatedautonomoussubmarines[21],airtraccontrolsystems[15],andmaterialhandlingsystems.Intherestofthissection,weexamineotherworkrelatedtotheShiftapproach.Insection2,wedescribethemainfeaturesoftheShiftlanguage|states,inputs,outputs,dierentialequationsandalgebraicdenitions,discretestatesandstatetransitions.Insection3,wegiveasimpliedversionoftheShiftmodel.Wediscussthemodelsofatype,acomponentandtheworldandgivetheformalsemanticsofthemodel.Insection4,weillustratethelanguageusingasimpleexample.1.1RelatedWorkShiftisusedtodescribemodelswithswitcheddierentialequations(suchasavehiclewithautomaticgearshift)andcoordinatedbehaviors(suchascommunicatingcontrollers).StandardsimulationtoolssuchasMatlaborMatrixX,whilesuitablefornumericalintegrationofxedsetsofdierentialequations,arediculttouseinapplicationswithrapidlychangingsetsofdierentialequations(duetotheevolutionofrelationshipsamongcomponents),complexevent-triggeringconditions(suchasexistentialqueriesonthestateoftheworld),andcomplexprogramlogic(suchassynchronouscompositionsofstatemachines).Thehybridsystemsapproach[1]satisesourneedsforcomponentmodelingbutitlacksthecapacitytomodeldynamicallyrecongurableinteractionsbetweencom-ponents.TheOmola/Omsim[18]languagehasaverysimilarapproachtohybridsystemmodelingasSHIFT.Bothsystemsprovideamodelinglanguagewithsimulationse-mantics;bothsupportdiscreteeventandcontinuoustimebehaviorrepresentation;bothhavethenecessaryconstructsforhierarchicalmodelingandspecicationreuse.However,Omolaisdesignedtorepresentstaticallyinterconnectedobjects.Further-more,itdoesnotprovidethemeansofqueryingsetsofcomponentsusingexistentialquantiers.InSHIFT,thesequeriesareusedtoexpressandcomputetheevolutionoftheinterconnectionsamongcomponentsastheworldevolves.Statecharts[13]andArgos[17],basedonStatecharts,areapproachesforsyn-chronousdiscreteeventmodeling.Theirfocusisonhierarchicalspecicationofnitestatemachines.Shiftdoesnotprovideexplicitfacilitiesforhierarchicalbehaviorspecication;instead,itprovidesasub-t