Faster coroutine pipelines

Abstract

Coroutine pipelines provide an attractive structuring mechanism for complex programs that process streams of data, with the advantage over lazy streams that both ends of a pipeline may interact with the I/O system, as may processes in the middle. Two popular Haskell libraries, Pipes and Conduit, support such pipelines. In both libraries, pipelines are implemented in a direct style by combining a free monad of communication events with an interpreter for (pseudo-)parallel composition that interleaves the events of its argument processes. These implementations both suffer from a slow-down when processes are deeply nested in sequence or in parallel. We propose an alternative implementation of pipelines based on continuations that does not suffer from this slow-down. What is more, the implementation is significantly faster on small, communication-intensive examples even where they do not suffer from the slow-down, and comparable in speed with similar programs based on lazy streams. We also show that the continuation-based implementation may be derived from the direct-style implementation by algebraic reasoning.

References

1. Magnus Carlsson and Thomas Hallgren. 1993. F UDGETS: A Graphical User Interface in a Lazy Functional Language. In Proceedings of the Conference on Functional Programming Languages and Computer Architecture (FPCA ’93). ACM, New York, NY, USA, 321–330.
2. Koen Claessen. 2004. Parallel Parsing Processes. J. Funct. Program. 14, 6 (2004), 741–757.
3. Gabriel Gonzalez. 2012. Haskell Pipes library. (2012). http://hackage.haskell.org/package/pipes
4. Ralf Hinze. 2000. Deriving backtracking monad transformers. In Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming (ICFP ’00), Montreal, Canada, September 18-21, 2000., Martin Odersky and Philip Wadler (Eds.). ACM, 186–197.
5. Ralf Hinze. 2012. Kan Extensions for Program Optimisation Or: Art and Dan Explain an Old Trick. In Mathematics of Program Construction - 11th International Conference, MPC 2012, Madrid, Spain, June 25-27, 2012. Proceedings, Jeremy Gibbons and Pablo Nogueira (Eds.). 324–362.
6. Paul Hudak, Antony Courtney, Henrik Nilsson, and John Peterson. 2002. Arrows, Robots, and Functional Reactive Programming. In Advanced Functional Programming, 4th International School, AFP 2002, Oxford, UK, August 19-24, 2002, Revised Lectures. 159–187.
7. Oleg Kiselyov. 2012. Iteratees. In Functional and Logic Programming - 11th International Symposium, FLOPS 2012, Kobe, Japan, May 23-25, 2012. Proceedings (Lecture Notes in Computer Science), Tom Schrijvers and Peter Thiemann (Eds.), Vol. 7294. Springer, 166–181.
8. Henrik Nilsson, Antony Courtney, and John Peterson. 2002. Functional Reactive Programming, Continued. In Proceedings of the 2002 ACM SIGPLAN Workshop on Haskell (Haskell ’02). ACM, New York, NY, USA, 51–64.
9. Ivan Perez, Manuel Bärenz, and Henrik Nilsson. 2016. Functional Reactive Programming, Refactored. In Proceedings of the 9th International Symposium on Haskell (Haskell 2016). ACM, New York, NY, USA, 33–44.
10. ReactiveX. 2015. Documentation for Observable. (2015). http://reactivex.io/documentation/observable.html
11. Olin Shivers and Matthew Might. 2006. Continuations and Transducer Composition. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’06). ACM, New York, NY, USA, 295–307.
12. Michael Snoyman. 2011. Haskell Conduit library. (2011). http://hackage.haskell.org/package/conduit
13. Ertugrul Söylemez. 2016. Haskell Netwire library. (2016). http://hackage.haskell.org/packages/netwire
14. Gordon Stewart, Mahanth Gowda, Geoffrey Mainland, Bozidar Radunovic, Dimitrios Vytiniotis, and Cristina Luengo Agullo. 2015. Ziria: A DSL for Wireless Systems Programming. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’15, Istanbul, Turkey, March 14-18, 2015, Özcan Özturk, Kemal Ebcioglu, and Sandhya Dwarkadas (Eds.). 415–428.
15. Valery Trifonov. 2003. Simulating quantified class constraints. In Proceedings of the ACM SIGPLAN Workshop on Haskell, Haskell 2003, Uppsala, Sweden, August 28, 2003. ACM, 98–102.
16. Atze van der Ploeg. 2013. Monadic functional reactive programming. In Proceedings of the 2013 ACM SIGPLAN Symposium on Haskell, Boston, MA, USA, September 23-24, 2013. 117–128.
17. Janis Voigtländer. 2008. Asymptotic Improvement of Computations over Free Monads. In Mathematics of Program Construction, 9th International Conference, MPC 2008, Marseille, France, July 15-18, 2008. Proceedings (Lecture Notes in Computer Science), Philippe Audebaud and Christine Paulin-Mohring (Eds.), Vol. 5133. Springer, 388–403.
18. Mitchell Wand and Dale Vaillancourt. 2004. Relating models of backtracking. In Proceedings of the Ninth ACM SIGPLAN International Conference on Functional Programming, ICFP 2004, Snow Bird, UT, USA, September 19-21, 2004, Chris Okasaki and Kathleen Fisher (Eds.). ACM, 54–65.

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Coroutines

      • Language types

        • Functional languages