Parallel Algebraic Effect Handlers
Article No.: 262, Pages 756 - 788
Abstract
Algebraic effect handlers support composable and structured control-flow abstraction. However, existing designs of algebraic effects often require effects to be executed sequentially. This paper studies parallel algebraic effect handlers. In particular, we formalize λp, a lambda calculus which models two key features, effect handlers and parallelizable computations, the latter of which takes the form of a for expression, inspired by the Dex programming language. We present various interesting examples expressible in our calculus. To show that our design can be implemented in a type-safe way, we present a higher-order polymorphic lambda calculus Fp that extends λp with a lightweight value dependent type system, and prove that Fp preserves the semantics of λp and enjoys syntactic type soundness. Lastly, we provide an implementation of the language design as a Haskell library, which mirrors both λp and Fp and reveals new connections to free applicative functors. All examples presented can be encoded in the Haskell implementation. We believe this paper is the first to study the combination of user-defined effect handlers and parallel computations, and it is our hope that it provides a basis for future designs and implementations of parallel algebraic effect handlers.
References
[1]
Danel Ahman. 2017. Handling fibred algebraic effects. Proc. ACM Program. Lang., 2, POPL (2017), Article 7, dec, 29 pages. https://doi.org/10.1145/3158095
[2]
Mario Blažević and Jacques Légaré. 2017. Packrats parse in packs. In Proceedings of the 10th ACM SIGPLAN International Symposium on Haskell (Haskell 2017). Association for Computing Machinery, New York, NY, USA. 14–25. isbn:9781450351829 https://doi.org/10.1145/3122955.3122958
[3]
Jonathan Immanuel Brachthäuser, Philipp Schuster, and Klaus Ostermann. 2020. Effects as capabilities: effect handlers and lightweight effect polymorphism. Proc. ACM Program. Lang., 4, OOPSLA (2020), Article 126, nov, 30 pages. https://doi.org/10.1145/3428194
[4]
Paolo Capriotti and Ambrus Kaposi. 2014. Free Applicative Functors. In MSFP. https://api.semanticscholar.org/CorpusID:17313426
[5]
Koen Claessen. 1999. A poor man’s concurrency monad. Journal of Functional Programming, 9, 3 (1999), 313–323.
[6]
Koen Claessen and Michał H. Pał ka. 2013. Splittable pseudorandom number generators using cryptographic hashing. In Proceedings of the 2013 ACM SIGPLAN Symposium on Haskell (Haskell ’13). Association for Computing Machinery, New York, NY, USA. 47–58. isbn:9781450323833 https://doi.org/10.1145/2503778.2503784
[7]
Olivier Danvy and Andrzej Filinski. 1990. Abstracting control. In Proceedings of the 1990 ACM Conference on LISP and Functional Programming (LFP ’90). Association for Computing Machinery, New York, NY, USA. 151–160. isbn:089791368X https://doi.org/10.1145/91556.91622
[8]
Stephen Dolan, Spiros Eliopoulos, Daniel Hillerström, Anil Madhavapeddy, KC Sivaramakrishnan, and Leo White. 2018. Concurrent system programming with effect handlers. In Trends in Functional Programming: 18th International Symposium, TFP 2017, Canterbury, UK, June 19-21, 2017, Revised Selected Papers 18. 98–117.
[9]
Richard A. Eisenberg and Stephanie Weirich. 2012. Dependently typed programming with singletons. In Proceedings of the 2012 Haskell Symposium (Haskell ’12). Association for Computing Machinery, New York, NY, USA. 117–130. isbn:9781450315746 https://doi.org/10.1145/2364506.2364522
[10]
Yannick Forster, Ohad Kammar, Sam Lindley, and Matija Pretnar. 2017. On the expressive power of user-defined effects: effect handlers, monadic reflection, delimited control. Proc. ACM Program. Lang., 1, ICFP (2017), Article 13, aug, 29 pages. https://doi.org/10.1145/3110257
[11]
Dan Ghica, Sam Lindley, Marcos Maroñas Bravo, and Maciej Piróg. 2022. High-level effect handlers in C++. Proc. ACM Program. Lang., 6, OOPSLA2 (2022), Article 183, oct, 29 pages. https://doi.org/10.1145/3563445
[12]
Google. 2020. JAX PRNG Design. https://github.com/google/jax/blob/main/design_notes/prng.md
[13]
Maurice Herlihy. 1991. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13, 1 (1991), jan, 124–149. issn:0164-0925 https://doi.org/10.1145/114005.102808
[14]
Daniel Hillerström and Sam Lindley. 2016. Liberating effects with rows and handlers. In Proceedings of the 1st International Workshop on Type-Driven Development (TyDe 2016). Association for Computing Machinery, New York, NY, USA. 15–27. isbn:9781450344357 https://doi.org/10.1145/2976022.2976033
[15]
Ohad Kammar, Sam Lindley, and Nicolas Oury. 2013. Handlers in action. In Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming (ICFP ’13). Association for Computing Machinery, New York, NY, USA. 145–158. isbn:9781450323260 https://doi.org/10.1145/2500365.2500590
[16]
Ohad Kammar and Matija Pretnar. 2017. No value restriction is needed for algebraic effects and handlers. Journal of functional programming, 27 (2017), e7.
[17]
Oleg Kiselyov and Hiromi Ishii. 2015. Freer monads, more extensible effects. In Proceedings of the 2015 ACM SIGPLAN Symposium on Haskell (Haskell ’15). Association for Computing Machinery, New York, NY, USA. 94–105. isbn:9781450338080 https://doi.org/10.1145/2804302.2804319
[18]
Oleg Kiselyov, Amr Sabry, and Cameron Swords. 2013. Extensible effects: an alternative to monad transformers. In Proceedings of the 2013 ACM SIGPLAN Symposium on Haskell (Haskell ’13). Association for Computing Machinery, New York, NY, USA. 59–70. isbn:9781450323833 https://doi.org/10.1145/2503778.2503791
[19]
Daan Leijen. 2014. Koka: Programming with Row Polymorphic Effect Types. In MSFP’14, 5th workshop on Mathematically Structured Functional Programming. https://doi.org/10.4204/EPTCS.153.8
[20]
Sam Lindley. 2014. Algebraic effects and effect handlers for idioms and arrows. In Proceedings of the 10th ACM SIGPLAN Workshop on Generic Programming (WGP ’14). Association for Computing Machinery, New York, NY, USA. 47–58. isbn:9781450330428 https://doi.org/10.1145/2633628.2633636
[21]
Sam Lindley and James Cheney. 2012. Row-based effect types for database integration. In Proceedings of the 8th ACM SIGPLAN workshop on Types in language design and implementation (TLDI’12). 91–102. https://doi.org/10.1145/2103786.2103798
[22]
Sam Lindley, Connor McBride, and Craig McLaughlin. 2017. Do be do be do. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL’17). 500–514. https://doi.org/10.1145/3009837.3009897
[23]
Simon Marlow, Louis Brandy, Jonathan Coens, and Jon Purdy. 2014. There is no fork: an abstraction for efficient, concurrent, and concise data access. In Proceedings of the 19th ACM SIGPLAN International Conference on Functional Programming (ICFP ’14). Association for Computing Machinery, New York, NY, USA. 325–337. isbn:9781450328739 https://doi.org/10.1145/2628136.2628144
[24]
Simon Marlow, Simon Peyton Jones, Edward Kmett, and Andrey Mokhov. 2016. Desugaring Haskell’s do-notation into applicative operations. In Proceedings of the 9th International Symposium on Haskell (Haskell 2016). Association for Computing Machinery, New York, NY, USA. 92–104. isbn:9781450344340 https://doi.org/10.1145/2976002.2976007
[25]
Conor McBride and Ross Paterson. 2008. Applicative programming with effects. J. Funct. Program., 18, 1 (2008), jan, 1–13. issn:0956-7968 https://doi.org/10.1017/S0956796807006326
[26]
Dave Menendez. 2013. Free Applicative Functors in Haskell. https://www.eyrie.org/ zednenem/2013/05/27/freeapp Accessed: 2024-02-25
[27]
Adam Paszke, Daniel D. Johnson, David Duvenaud, Dimitrios Vytiniotis, Alexey Radul, Matthew J. Johnson, Jonathan Ragan-Kelley, and Dougal Maclaurin. 2021. Getting to the Point: Index Sets and Parallelism-Preserving Autodiff for Pointful Array Programming. Proc. ACM Program. Lang., 5, ICFP (2021), Article 88, Aug., 29 pages. https://doi.org/10.1145/3473593
[28]
Simon Peyton Jones, Andrew Gordon, and Sigbjorn Finne. 1996. Concurrent Haskell. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’96). Association for Computing Machinery, New York, NY, USA. 295–308. isbn:0897917693 https://doi.org/10.1145/237721.237794
[29]
Luna Phipps-Costin, Andreas Rossberg, Arjun Guha, Daan Leijen, Daniel Hillerström, KC Sivaramakrishnan, Matija Pretnar, and Sam Lindley. 2023. Continuing WebAssembly with Effect Handlers. Proc. ACM Program. Lang., 7, OOPSLA2 (2023), Article 238, oct, 26 pages. https://doi.org/10.1145/3622814
[30]
Ruben P. Pieters, Exequiel Rivas, and Tom Schrijvers. 2020. Generalized monoidal effects and handlers. Journal of Functional Programming, 30 (2020).
[31]
Maciej Piróg, Tom Schrijvers, Nicolas Wu, and Mauro Jaskelioff. 2018. Syntax and Semantics for Operations with Scopes. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS ’18). Association for Computing Machinery, New York, NY, USA. 809–818. isbn:9781450355834 https://doi.org/10.1145/3209108.3209166
[32]
Gordon D. Plotkin and John Power. 2003. Algebraic Operations and Generic Effects. Applied Categorical Structures, 11, 1 (2003), 69–94. https://doi.org/10.1023/A:1023064908962
[33]
Gordon D. Plotkin and Matija Pretnar. 2009. Handlers of Algebraic Effects. In 18th European Symposium on Programming Languages and Systems (ESOP’09). 80–94. https://doi.org/10.1007/978-3-642-00590-9_7
[34]
Matija Pretnar. 2015. An Introduction to Algebraic Effects and Handlers. Invited Tutorial Paper. Electron. Notes Theor. Comput. Sci., 319, C (2015), Dec., 19–35. issn:1571-0661 https://doi.org/10.1016/j.entcs.2015.12.003
[35]
Enno Scholz. 1995. A concurrency monad based on constructor primitives: or, being first-class is not enough.
[36]
KC Sivaramakrishnan, Stephen Dolan, Leo White, Tom Kelly, Sadiq Jaffer, and Anil Madhavapeddy. 2021. Retrofitting Effect Handlers onto OCaml. Association for Computing Machinery, New York, NY, USA. 206–221. isbn:9781450383912 https://doi.org/10.1145/3453483.3454039
[37]
Nikhil Swamy, Juan Chen, Cédric Fournet, Pierre-Yves Strub, Karthikeyan Bhargavan, and Jean Yang. 2011. Secure distributed programming with value-dependent types. In Proceedings of the 16th ACM SIGPLAN International Conference on Functional Programming (ICFP ’11). Association for Computing Machinery, New York, NY, USA. 266–278. isbn:9781450308656 https://doi.org/10.1145/2034773.2034811
[38]
Wenhao Tang, Daniel Hillerström, Sam Lindley, and J. Garrett Morris. 2024. Soundly Handling Linearity. Proc. ACM Program. Lang., 8, POPL (2024), Article 54, jan, 29 pages. https://doi.org/10.1145/3632896
[39]
Birthe van den Berg, Tom Schrijvers, Casper Bach Poulsen, and Nicolas Wu. 2021. Latent effects for reusable language components. In Asian Symposium on Programming Languages and Systems. 182–201.
[40]
Andrew K Wright. 1995. Simple imperative polymorphism. Lisp and symbolic computation, 8, 4 (1995), 343–355.
[41]
Nicolas Wu, Tom Schrijvers, and Ralf Hinze. 2014. Effect handlers in scope. In Proceedings of the 2014 ACM SIGPLAN Symposium on Haskell (Haskell ’14). Association for Computing Machinery, New York, NY, USA. 1–12. isbn:9781450330411 https://doi.org/10.1145/2633357.2633358
[42]
Ningning Xie, Jonathan Brachthäuser, Phillip Schuster, Daniel Hillerström, and Daan Leijen. 2020. Effect Handlers, Evidently. In 25th ACM SIGPLAN International Conference on Functional Programming (ICFP’2020). https://doi.org/10.1145/3408981
[43]
Zhixuan Yang, Marco Paviotti, Nicolas Wu, Birthe van den Berg, and Tom Schrijvers. 2022. Structured handling of scoped effects. In European Symposium on Programming. 462–491.
Recommendations
Gradual Typing for Effect Handlers
We present a gradually typed language, GrEff, with effects and handlers that supports migration from unchecked to checked effect typing. This serves as a simple model of the integration of an effect typing discipline with an existing effectful typed ...
Algebraic effects and effect handlers for idioms and arrows
WGP '14: Proceedings of the 10th ACM SIGPLAN workshop on Generic programmingPlotkin and Power's algebraic effects combined with Plotkin and Pretnar's effect handlers provide a foundation for modular programming with effects. We present a generalisation of algebraic effects and effect handlers to support other kinds of effectful ...
Effects as capabilities: effect handlers and lightweight effect polymorphism
Effect handlers have recently gained popularity amongst programming language researchers. Existing type- and effect systems for effect handlers are often complicated and potentially hinder a wide-spread adoption.
We present the language Effekt with the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2024
1031 pages
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 15 August 2024
Published in PACMPL Volume 8, Issue ICFP
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Natural Sciences and Engineering Research Council of Canada
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 242Total Downloads
- Downloads (Last 12 months)242
- Downloads (Last 6 weeks)102
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in