Realtime Signal Processing Dataflow, Visual, and F

RealtimeSignalProcessingData°ow,Visual,andFunctionalProgrammingHidekiJohnReekieSubmittedfortheDegreeofDoctorofPhilosophyattheUniversityofTechnologyatSydneyintheSchoolofElectricalEngineeringSeptember1995iiAbstractThisthesispresentsandjusti¯esaframeworkforprogrammingreal-timesig-nalprocessingsystems.Theframeworkextendstheexisting\block-diagramprogrammingmodel;ithasthreecomponents:averyhigh-leveltextuallan-guage,avisuallanguage,andthedata°owprocessnetworkmodelofcomputa-tion.Thedata°owprocessnetworkmodel,althoughwidely-used,lacksaformaldescription,andIprovideasemanticsforit.Theformalworkleadsintoanewformofactor.Havingestablishedthesemanticsofdata°owprocesses,thefunctionallanguageHaskellislayeredabovethismodel,providingpowerfulfeatures|notablypolymorphism,higher-orderfunctions,andalgebraicprogramtransformation|absentinblock-diagramsystems.AvisualequivalentnotationforHaskell,VisualHaskell,ensuresthatthispowerdoesnotexcludethe\in-tuitiveappealofvisualinterfaces;withsomeintelligentlayoutandsuggestiveicons,aVisualHaskellprogramcanbemadetolookverylikeablockdiagramprogram.Finally,thefunctionallanguageisusedtofurtherextenddata°owprocessnetworks,bysimulatingtimedanddynamically-varyingnetworks.Thethesisthusdrawstogetheranumberofpreviously-separateideas:areasonableexpectationofe±cientexecutionusingestablisheddata°owcom-pilationtechnology;apowerfulandhigh-levelprogrammingnotation;andablock-diagramstyleinterface.iiContents1Introduction11.1Motivation..............................21.2Bene¯ts................................41.3Overviewofthethesis........................51.4Previouslypublishedwork......................72BackgroundMaterial92.1Modelsofparallelism.........................92.1.1A\meta-modelofparallelism...............92.1.2Implicitparallelism......................112.1.3Dataparallelism.......................122.1.4Controlparallelism......................132.1.5TheLindamodel.......................142.1.6Pipelineparallelism.....................152.2Functionalprogrammingin¯veminutes..............162.2.1Objectsandfunctions....................162.2.2Bindings............................182.2.3Patterns............................192.2.4Curryingandhigher-orderfunctions............192.2.5let,lambda,andcase.....................202.2.6Polymorphismandtypeclasses...............212.3Evaluationmechanisms.......................222.3.1Graphreduction.......................222.3.2Strictness...........................232.3.3Parallelgraphreduction...................242.3.4Paralleldatastructures...................252.3.5Functionaloperatingsystems................262.3.6Functionalprocessnetworks.................272.3.7Skeletons...........................282.4Real-timesignalprocessing.....................292.4.1Discrete-timesignals.....................292.4.2Streamsandchannels....................302.4.3Functionsandsystems....................312.4.4Digitalsignalprocessors...................32iii2.5Summary...............................343Data°owProcessNetworks353.1Relatedwork.............................363.1.1Computationgraphs.....................363.1.2Synchronousdata°ow(SDF)................383.1.3Kahn'sprocessnetworks...................403.1.4Data°owprocesses......................423.1.5Firingrules..........................443.2Standard-formdata°owactors...................453.2.1Syntax.............................453.2.2Desugaring..........................483.2.3Semantics...........................483.2.4Consumptionandproductionvectors............523.2.5CanonicalSDFactors....................543.3Phased-formdata°owactors.....................553.3.1Syntax.............................563.3.2Phasegraphs.........................603.3.3Semantics...........................613.3.4Cyclo-staticandmulti-phaseintegerdata°ow.......643.3.5Executionmechanisms....................663.3.6Hierarchyandstrictness...................673.4Summary...............................704VisualHaskell714.1Relatedwork.............................724.2AnintroductiontoVisualHaskell..................754.3Visualsyntaxpreliminaries.....................794.3.1Visualelements........................794.3.2Specifyingthevisualsyntax.................804.3.3Asimplevisuallanguage..................824.3.4De-sugaring..........................854.4Thecoresyntax............................854.4.1Simpleexpressions......................854.4.2Structuredexpressions....................884.4.3Patterns............................914.4.4Bindings............................934.4.5Matchphrases........................934.5Improvingthevisualsyntax.....................964.5.1Visualsyntacticsugar....................964.5.2Iterationboxes........................984.5.3Unfoldedhigher-orderfunctions...............994.5.4Wiring.............................1004.6Summary...............................100iv5StaticProcessNetworks1035.1Relatedwork.............................1045.2Vectors................................1055.2.1TheVectordatatype.....................1055.2.2Iterators............................1