Causal commutative arrows and their optimization

ABSTRACT

Arrows are a popular form of abstract computation. Being more general than monads, they are more broadly applicable, and in particular are a good abstraction for signal processing and dataflow computations. Most notably, arrows form the basis for a domain specific language called Yampa, which has been used in a variety of concrete applications, including animation, robotics, sound synthesis, control systems, and graphical user interfaces. Our primary interest is in better understanding the class of abstract computations captured by Yampa. Unfortunately, arrows are not concrete enough to do this with precision. To remedy this situation we introduce the concept of commutative arrows that capture a kind of non-interference property of concurrent computations. We also add an init operator, and identify a crucial law that captures the causal nature of arrow effects. We call the resulting computational model causal commutative arrows. To study this class of computations in more detail, we define an extension to the simply typed lambda calculus called causal commutative arrows (CCA), and study its properties. Our key contribution is the identification of a normal form for CCA called causal commutative normal form (CCNF). By defining a normalization procedure we have developed an optimization strategy that yields dramatic improvements in performance over conventional implementations of arrows. We have implemented this technique in Haskell, and conducted benchmarks that validate the effectiveness of our approach. When combined with stream fusion, the overall methodology can result in speed-ups of greater than two orders of magnitude.

REFERENCES

• 1: Pascalin Amagbegnon, Loc Besnard, and Paul Le Guernic. Implementation of the data-flow synchronous language signal. In In Conference on Programming Language Design and Implementation, pages 163--173. ACM Press, 1995.
• 2: Robert Atkey. What is a categorical model of arrows? In Mathematically Structured Functional Programming, 2008.
• 3: Per Bjesse, Koen Claessen, Mary Sheeran, and Satnam Singh. Lava: Hardware design in haskell. In ICFP, pages 174--184, 1998.
• 4: P. Caspi, N. Halbwachs, D. Pilaud, and J.A. Plaice. Lustre: A declarative language for programming synchronous systems. In 14th ACM Symp. on Principles of Programming Languages, January 1987.
• 5: Paul Caspi and Marc Pouzet. A Co-iterative Characterization of Synchronous Stream Functions. In Coalgebraic Methods in Computer Science (CMCS'98), Electronic Notes in Theoretical Computer Science, March 1998. Extended version available as a VERIMAG tech. report no. 97--07 at www.lri.fr/~pouzet.
• 6: Eric Cheng and Paul Hudak. Look ma, no arrows -- a functional reactive real-time sound synthesis framework. Technical Report YALEU/DCS/RR-1405, Yale University, May 2008.
• 7: Mun Hon Cheong. Functional programming and 3d games, November 2005. also see www.haskell.org/haskellwiki/Frag.
• 8: Jean-Louis Colaço, Alain Girault, Grégoire Hamon, and Marc Pouzet. Towards a higher-order synchronous data-flow language. In EMSOFT '04: Proceedings of the 4th ACM international conference on Embedded software, pages 230--239, New York, NY, USA, 2004. ACM.
• 9: Antony Courtney. Modelling User Interfaces in a Functional Language. PhD thesis, Department of Computer Science, Yale University, May 2004.
• 10: Antony Courtney and Conal Elliott. Genuinely functional user interfaces. In Proc. of the 2001 Haskell Workshop, September 2001.
• 11: Antony Courtney, Henrik Nilsson, and John Peterson. The Yampa arcade. In Proceedings of the 2003 ACM SIGPLAN Haskell Workshop (Haskell'03), pages 7--18, Uppsala, Sweden, August 2003. ACM Press.
• 12: Duncan Coutts, Roman Leshchinskiy, and Don Stewart. Stream fusion: From lists to streams to nothing at all. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP 2007, April 2007.
• 13: Conal Elliott and Paul Hudak. Functional reactive animation. In International Conference on Functional Programming, pages 263--273, June 1997.
• 14: G. H. Mealy. A method for synthesizing sequential circuits. Bell System Technical Journal, 34(5):1045--1079, 1955.
• 15: George Giorgidze and Henrik Nilsson. Switched-on yampa. In Paul Hudak and David Scott Warren, editors, Practical Aspects of Declarative Languages, 10th International Symposium, PADL 2008, San Francisco, CA, USA, January 7-8, 2008, volume 4902 of Lecture Notes in Computer Science, pages 282--298. Springer, 2008.
• 16: N. Halbwachs, P. Raymond, and C. Ratel. Generating efficient code from data-flow programs. In J. Maluszy'nski and M. Wirsing, editors, Proceedings of the Third International Symposium on Programming Language Implementation and Logic Programming, number 528, pages 1--13207--218. Springer Verlag, 1991.
• 17: Masahito Hasegawa. Recursion from cyclic sharing: traced monoidal categories and models of cyclic lambda calculi. pages 196--213. Springer Verlag, 1997.
• 18: L. Huang, P. Hudak, and J. Peterson. Hporter: Using arrows to compose parallel processes. In Proc. Practical Aspects of Declarative Languages, pages 275--289. Springer Verlag LNCS 4354, January 2007.
• 19: P. Hudak. Building domain specific embedded languages. ACM Computing Surveys, 28A:(electronic), December 1996.
• 20: Paul Hudak. Modular domain specific languages and tools. In Proceedings of Fifth International Conference on Software Reuse, pages 134--142. IEEE Computer Society, June 1998.
• 21: Paul Hudak, Antony Courtney, Henrik Nilsson, and John Peterson. Arrows, robots, and functional reactive programming. In Summer School on Advanced Functional Programming 2002, Oxford University, volume 2638 of Lecture Notes in Computer Science, pages 159--187. Springer-Verlag, 2003.
• 22: Paul Hudak, Paul Liu, Michael Stern, and Ashish Agarwal. Yampa meets the worm. Technical Report YALEU/DCS/RR-1408, Yale University, July 2008.
• 23: John Hughes. Generalising monads to arrows. Science of Computer Programming, 37:67--111, May 2000.
• 24: John Hughes. Programming with arrows. In Advanced Functional Programming, pages 73--129, 2004.
• 25: Patrik Jansson and Johan Jeuring. Polytypic compact printing and parsing. In ESOP, pages 273--287, 1999.
• 26: Sam Lindley, Philip Wadler, and Jeremy Yallop. The arrow calculus (functional pearl). Draft, 2008.
• 27: Hai Liu and Paul Hudak. Plugging a space leak with an arrow. Electronic Notes in Theoretical Computer Science, 193:29--45, nov 2007.
• 28: Conor McBride and Ross Paterson. Applicative programming with effects. J. Funct. Program., 18(1):1--13, 2008.
• 29: Eugenio Moggi. Notions of computation and monads. Inf. Comput., 93(1):55--92, 1991.
• 30: Henrik Nilsson. Dynamic optimization for functional reactive programming using generalized algebraic data types. In ICFP, pages 54--65, 2005.
• 31: Clemens Oertel. RatTracker: A Functional-Reactive Approach to Flexible Control of Behavioural Conditioning Experiments. PhD thesis, Wilhelm-Schickard-Institute for Computer Science at the University of Tübingen, May 2006.
• 32: Ross Paterson. A new notation for arrows. In ICFP'01: International Conference on Functional Programming, pages 229--240, Firenze, Italy, 2001.
• 33: John Peterson, Gregory Hager, and Paul Hudak. A language for declarative robotic programming. In International Conference on Robotics and Automation, 1999.
• 34: John Peterson, Paul Hudak, and Conal Elliott. Lambda in motion: Controlling robots with Haskell. In First International Workshop on Practical Aspects of Declarative Languages. SIGPLAN, Jan 1999.
• 35: John Peterson, Zhanyong Wan, Paul Hudak, and Henrik Nilsson. Yale FRP User's Manual. Department of Computer Science, Yale University, January 2001. Available at http://www.haskell.org/frp/manual.html.
• 36: Simon Peyton Jones et al. The Haskell 98 language and libraries: The revised report. Journal of Functional Programming, 13(1):0--255, Jan 2003. http://www.haskell.org/definition/.
• 37: John Power and Hayo Thielecke. Closed freyd- and kappa-categories. In ICALP, pages 625--634, 1999.
• 38: Jan J. M. M. Rutten. Algebraic specification and coalgebraic synthesis of mealy automata. Electr. Notes Theor. Comput. Sci, 160:305--319, 2006.
• 39: Robert Stephens. A survey of stream processing. Acta Informatica, 34(7):491--541, 1997.
• 40: Ross Howard Street, A. Joyal, and D. Verity. Traced monoidal categories. Mathematical Proceedings of the Cambridge Philosophical Society, 119(3):425--446, 1996.
• 41: William Thies, Michal Karczmarek, and Saman P. Amarasinghe. Streamit: A language for streaming applications. In CC '02: Proceedings of the 11th International Conference on Compiler Construction, pages 179--196, London, UK, 2002. Springer-Verlag.
• 42: Tarmo Uustalu and Varmo Vene. The essence of dataflow programming. In Zoltán Horváth, editor, CEFP, volume 4164 of Lecture Notes in Computer Science, pages 135--167. Springer, 2005.
• 43: William W. Wadge and Edward A. Ashcroft. LUCID, the dataflow programming language. Academic Press Professional, Inc., San Diego, CA, USA, 1985.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Languages, Performance, Theory

Keywords:
arrows, dataflow language, functional programming, functional reactive programming, program optimization, stream processing