Continuations and transducer composition

ABSTRACT

On-line transducers are an important class of computational agent; we construct and compose together many software systems using them, such as stream processors, layered network protocols, DSP networks and graphics pipelines. We show an interesting use of continuations, that, when taken in a CPS setting, exposes the control flow of these systems. This enables a CPS-based compiler to optimise systems composed of these transducers, using only standard, known analyses and optimisations. Critically, the analysis permits optimisation across the composition of these transducers, allowing efficient construction of systems in a hierarchical way.

REFERENCES

• 1: O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
• 2: John Launchbury , Tim Sheard, Warm fusion: deriving build-catas from recursive definitions, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.314-323, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224223]
• 3: Olin Shivers, The semantics of Scheme control-flow analysis, ACM SIGPLAN Notices, v.26 n.9, p.190-198, Sept. 1991
• 4: B. Liskov, A HISTORY OF CLU, Massachusetts Institute of Technology, Cambridge, MA, 1992
• 5: John H. Reppy, CML: A higher concurrent language, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.293-305, June 24-28, 1991, Toronto, Ontario, Canada
• 6: Olin Shivers. Continuations and threads: Expressing machine concurrency directly in advanced languages. In Proceedings of the Second ACM SIGPLAN Workshop on Continuations, January 1997, Paris. Also available as BRICS Notes Series NS-96-13, University of Aarhus, Denmark.
• 7: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 8: Matthew Might , Olin Shivers, Environment analysis via ΔCFA, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.127-140, January 11-13, 2006, Charleston, South Carolina, USA
• 9: Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990
• 10: Sanjeev Kumar , Yitzhak Mandelbaum , Xiang Yu , Kai Li, ESP: a language for programmable devices, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.309-320, June 2001, Snowbird, Utah, United States
• 11: Philip Wadler, The essence of functional programming, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143169]
• 12: Andrew Gill , John Launchbury , Simon L. Peyton Jones, A short cut to deforestation, Proceedings of the conference on Functional programming languages and computer architecture, p.223-232, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165214]
• 13: Philip Wadler, Monads for Functional Programming, Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques-Tutorial Text, p.24-52, May 24-30, 1995
• 14: Todd A. Proebsting , Scott A. Watterson, Filter fusion, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.119-130, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237760]
• 15: Control-Flow Analysis of Higher-Order Languages. Ph.D. dissertation, Carnegie Mellon University, May 1991. Technical Report CMU-CS-91-145, School of Computer Science. (Also available via anonymous ftp as URL ftp://cs.cmu.edu/afs%2Fcs.cmu.edu%2Fuser%2Fshivers%2Flib%2Fpapers/diss.ps.Z.)
• 16: Olin Shivers, The anatomy of a loop: a story of scope and control, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 17: Philip Wadler. Linear types can change the world. Programming Concepts and Methods, Ed. M. Broy and C. Jones, North Holland.
• 18: Chih-Ping Chen , Paul Hudak, Rolling your own mutable ADT—a connection between linear types and monads, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.54-66, January 15-17, 1997, Paris, France [doi>10.1145/263699.263708]
• 19: E. Moggi, Computational lambda-calculus and monads, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.14-23, June 1989, Pacific Grove, California, United States
• 20: David Andrew Kranz , Paul Hudak, Orbit: an optimizing compiler for scheme, 1988
• 21: Alan J. Perlis, Special Feature: Epigrams on programming, ACM SIGPLAN Notices, v.17 n.9, p.7-13, September 1982 [doi>10.1145/947955.1083808]
• 22: Ivan E. Sutherland , Gary W. Hodgman, Reentrant polygon clipping, Communications of the ACM, v.17 n.1, p.32-42, Jan. 1974 [doi>10.1145/360767.360802]
• 23: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 24: R. Hieb , R. Kent Dybvig , Carl Bruggeman, Representing control in the presence of first-class continuations, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.66-77, June 1990, White Plains, New York, United States
• 25: R. Kelsey , P. Hudak, Realistic compilation by program transformation (detailed summary), Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.281-292, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75302]
• 26: David N. Turner , Philip Wadler , Christian Mossin, Once upon a type, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.1-11, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224168]
• 27: Josef Svenningsson, Shortcut fusion for accumulating parameters & zip-like functions, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.124-132, October 04-06, 2002, Pittsburgh, PA, USA
• 28: Olin Shivers. Useless-variable elimination. In proceedings of Workshop on Static Analysis of Equational, Functional and Logic Programs, Université Bordeaux I, LaBRI, Bordeaux, France, October, 1991.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Coroutines; Control structures

General Terms:
Design, Languages, Performance

Keywords:
calculus, continuation-passing style (CPS), continuations, coroutines, flow analysis, functional languages, fusion, lambda, language design, program analysis, stream processing