Abstract
Spivey has recently presented a novel functional representation that supports the efficient composition, or merging, of coroutine pipelines for processing streams of data. This representation was inspired by Shivers and Might’s three-continuation approach and is shown to be equivalent to a simple yet inefficient executable specification. Unfortunately, neither Shivers and Might’s original work nor the equivalence proof sheds much light on the underlying principles allowing the derivation of this efficient representation from its specification.
This paper gives the missing insight by reconstructing a systematic derivation in terms of known transformation steps from the simple specification to the efficient representation. This derivation sheds light on the limitations of the representation and on its applicability to other settings. In particular, it has enabled us to obtain a similar representation for pipes featuring two-way communication, similar to the Haskell pipes library. Our benchmarks confirm that this two-way representation retains the same improved performance characteristics.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Böhm, C., Berarducci, A.: Automatic synthesis of typed lambda-programs on term algebras. Theor. Comput. Sci. 39, 135–154 (1985). https://doi.org/10.1016/0304-3975(85)90135-5
Church, A.: The Calculi of Lambda-Conversion. Princeton University Press, Princeton (1941)
Claessen, K.: Parallel parsing processes. J. Funct. Program. 14(6), 741–757 (2004). https://doi.org/10.1017/S0956796804005192
Ghani, N., Uustalu, T., Vene, V.: Build, augment and destroy, universally. In: Chin, W.-N. (ed.) APLAS 2004. LNCS, vol. 3302, pp. 327–347. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30477-7_22
Gonzalez, G.: Haskell Pipes library (2012). http://hackage.haskell.org/package/pipes
Kammar, O., Lindley, S., Oury, N.: Handlers in action. In: Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013, pp. 145–158. ACM, New York (2013) https://doi.org/10.1145/2500365.2500590
Lindley, S., McBride, C., McLaughlin, C.: Do be do be do. In: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, pp. 500–514. ACM, New York (2017). https://doi.org/10.1145/3009837.3009897
Mogensen, T.: Efficient self-interpretation in lambda calculus. J. Funct. Program. 2(3), 345–364 (1992). https://doi.org/10.1017/S0956796800000423
O’Sullivan, B.: Haskell Criterion library (2009). http://hackage.haskell.org/package/criterion
Shivers, O., Might, M.: Continuations and transducer composition. In: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2006, pp. 295–307. ACM, New York (2006). https://doi.org/10.1145/1133981.1134016
Snoyman, M.: Haskell Conduit library (2011). http://hackage.haskell.org/package/conduit
Spivey, M.: Faster coroutine pipelines. In: Proceedings of the ACM Programming Languages, 1(ICFP), 5:1–5:23, August 2017. https://doi.org/10.1145/3110249
Acknowledgements
We would like to thank Nicolas Wu, Alexander Vandenbroucke and the anonymous PADL reviewers for their feedback. This work was partly funded by the Flemish Fund for Scientific Research (FWO).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Pieters, R.P., Schrijvers, T. (2019). Faster Coroutine Pipelines: A Reconstruction. In: Alferes, J., Johansson, M. (eds) Practical Aspects of Declarative Languages. PADL 2019. Lecture Notes in Computer Science(), vol 11372. Springer, Cham. https://doi.org/10.1007/978-3-030-05998-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-05998-9_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-05997-2
Online ISBN: 978-3-030-05998-9
eBook Packages: Computer ScienceComputer Science (R0)