Associated Effects: Flexible Abstractions for Effectful Programming
Article No.: 163, Pages 394 - 416
Abstract
We present associated effects, a programming language feature that enables type classes to abstract over the effects of their function signatures, allowing each type class instance to specify its concrete effects.
Associated effects significantly increase the flexibility and expressive power of a programming language that combines a type and effect system with type classes. In particular, associated effects allow us to (i) abstract over total and partial functions, where partial functions may throw exceptions, (ii) abstract over immutable data structures and mutable data structures that have heap effects, and (iii) implement adaptors that combine type classes with algebraic effects.
We implement associated effects as an extension of the Flix programming language and refactor the Flix Standard Library to use associated effects, significantly increasing its flexibility and expressive power. Specifically, we add associated effects to 11 type classes, which enables us to add 28 new type class instances.
References
[1]
Torben Amtoft, Flemming Nielson, and Hanne Riis Nielson. 1997. Type and behaviour reconstruction for higher-order concurrent programs. Journal of Functional Programming, 7, 3 (1997), https://doi.org/10.1017/s0956796897002700
[2]
Jonathan Immanuel Brachthäuser, Philipp Schuster, and Klaus Ostermann. 2018. Effect handlers for the masses. Proceedings of the ACM on Programming Languages, 2, OOPSLA (2018), https://doi.org/10.1145/3276481
[3]
Jonathan Immanuel Brachthäuser, Philipp Schuster, and Klaus Ostermann. 2020. Effekt: Capability-passing style for type- and effect-safe, extensible effect handlers in Scala. Journal of Functional Programming, 30 (2020), https://doi.org/10.1017/s0956796820000027
[4]
Edwin Brady. 2013. Programming and reasoning with algebraic effects and dependent types. In Proceedings of the 18th ACM SIGPLAN international conference on Functional programming. https://doi.org/10.1145/2500365.2500581
[5]
Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, and Simon Marlow. 2005. Associated types with class. ACM SIGPLAN Notices, 40, 1 (2005), https://doi.org/10.1145/1047659.1040306
[6]
Manuel M. T. Chakravarty, Gabriele Keller, and Simon Peyton Jones. 2005. Associated type synonyms. ACM SIGPLAN Notices, 40, 9 (2005), https://doi.org/10.1145/1090189.1086397
[7]
Kung Chen, Paul Hudak, and Martin Odersky. 1992. Parametric type classes. In Proceedings of the 1992 ACM conference on LISP and functional programming. https://doi.org/10.1145/141471.141536
[8]
Lukas Convent, Sam Lindley, Conor McBride, and Craig McLaughlin. 2020. Doo bee doo bee doo. Journal of Functional Programming, 30 (2020), https://doi.org/10.1017/s0956796820000039
[9]
Luis Damas. 1984. Type assignment in programming languages. Ph. D. Dissertation. The University of Edinburgh.
[10]
Stephen Dolan and Alan Mycroft. 2017. Polymorphism, subtyping, and type inference in MLsub. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. https://doi.org/10.1145/3009837.3009882
[11]
Dominic Duggan and John Ophel. 2002. Type-checking multi-parameter type classes. Journal of Functional Programming, 12, 02 (2002), https://doi.org/10.1017/s0956796801004233
[12]
Martin Elsman and Troels Henriksen. 2023. Parallelism in a Region Inference Context. Proceedings of the ACM on Programming Languages, 7, PLDI (2023), https://doi.org/10.1145/3591256
[13]
Ronald Garcia, Jaakko Jarvi, Andrew Lumsdaine, Jeremy G. Siek, and Jeremiah Willcock. 2003. A comparative study of language support for generic programming. In Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications. https://doi.org/10.1145/949305.949317
[14]
Colin S. Gordon. 2021. Polymorphic Iterable Sequential Effect Systems. ACM Transactions on Programming Languages and Systems, 43, 1 (2021), https://doi.org/10.1145/3450272
[15]
Niels Hallenberg, Martin Elsman, and Mads Tofte. 2002. Combining region inference and garbage collection. In Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementation. https://doi.org/10.1145/512529.512547
[16]
Daniel Hillerström and Sam Lindley. 2016. Liberating effects with rows and handlers. In Proceedings of the 1st International Workshop on Type-Driven Development. https://doi.org/10.1145/2976022.2976033
[17]
Roger Hindley. 1969. The principal type-scheme of an object in combinatory logic. Transactions of the American Mathematical Society (AMS).
[18]
Koen Jacobs, Dominique Devriese, and Amin Timany. 2022. Purity of an ST monad: full abstraction by semantically typed back-translation. Proceedings of the ACM on Programming Languages, 6, OOPSLA1 (2022), https://doi.org/10.1145/3527326
[19]
Mark P. Jones. 1993. A system of constructor classes: overloading and implicit higher-order polymorphism. In Proceedings of the conference on Functional programming languages and computer architecture. https://doi.org/10.1145/165180.165190
[20]
Mark P. Jones. 1999. Typing Haskell in Haskell. In Haskell Workshop.
[21]
Mark P. Jones. 2000. Type Classes with Functional Dependencies. Springer Berlin Heidelberg, 230–244. isbn:9783540464259 issn:0302-9743 https://doi.org/10.1007/3-540-46425-5_15
[22]
Steve Klabnik and Carol Nichols. 2023. The Rust programming language. No Starch Press.
[23]
Daan Leijen. 2014. Koka: Programming with Row Polymorphic Effect Types. https://doi.org/10.48550/ARXIV.1406.2061
[24]
Daan Leijen. 2017. Type directed compilation of row-typed algebraic effects. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. https://doi.org/10.1145/3009837.3009872
[25]
Xavier Leroy and François Pessaux. 2000. Type-based analysis of uncaught exceptions. ACM Transactions on Programming Languages and Systems, 22, 2 (2000), https://doi.org/10.1145/349214.349230
[26]
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. https://doi.org/10.1145/2103786.2103798
[27]
Sam Lindley, Conor McBride, and Craig McLaughlin. 2017. Do be do be do. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. https://doi.org/10.1145/3009837.3009897
[28]
J. M. Lucassen and D. K. Gifford. 1988. Polymorphic effect systems. In Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL ’88. https://doi.org/10.1145/73560.73564
[29]
Matthew Lutze, Magnus Madsen, Philipp Schuster, and Jonathan Immanuel Brachthäuser. 2023. With or Without You: Programming with Effect Exclusion. Proceedings of the ACM on Programming Languages, 7, ICFP (2023), https://doi.org/10.1145/3607846
[30]
Magnus Madsen and Ondřej Lhoták. 2020. Fixpoints for the masses: programming with first-class Datalog constraints. Proceedings of the ACM on Programming Languages, 4, OOPSLA (2020), https://doi.org/10.1145/3428193
[31]
Magnus Madsen and Jaco van de Pol. 2020. Polymorphic types and effects with Boolean unification. Proceedings of the ACM on Programming Languages, 4, OOPSLA (2020), https://doi.org/10.1145/3428222
[32]
Magnus Madsen and Jaco van de Pol. 2023. Programming with Purity Reflection: Peaceful Coexistence of Effects, Laziness, and Parallelism. In 37th European Conference on Object-Oriented Programming. https://doi.org/10.4230/LIPICS.ECOOP.2023.18
[33]
Robin Milner. 1978. A theory of type polymorphism in programming. J. Comput. System Sci., 17, 3 (1978), https://doi.org/10.1016/0022-0000(78)90014-4
[34]
Adriaan Moors, Frank Piessens, and Martin Odersky. 2008. Generics of a higher kind. In Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications. https://doi.org/10.1145/1449764.1449798
[35]
Martin Odersky, Philippe Altherr, Vincent Cremet, Burak Emir, Sebastian Maneth, Stéphane Micheloud, Nikolay Mihaylov, Michel Schinz, Erik Stenman, and Matthias Zenger. 2004. An overview of the Scala programming language.
[36]
Martin Odersky, Martin Sulzmann, and Martin Wehr. 1999. Type inference with constrained types. Theory and Practice of Object Systems, 5, 1 (1999), https://doi.org/10.1002/(sici)1096-9942(199901/03)5:1<35::aid-tapo4>3.0.co;2-4
[37]
Dominic Orchard and Tomas Petricek. 2014. Embedding effect systems in Haskell. ACM SIGPLAN Notices, 49, 12 (2014), https://doi.org/10.1145/2775050.2633368
[38]
Lionel Parreaux. 2020. The simple essence of algebraic subtyping: principal type inference with subtyping made easy (functional pearl). Proceedings of the ACM on Programming Languages, 4, ICFP (2020), https://doi.org/10.1145/3409006
[39]
Lionel Parreaux and Chun Yin Chau. 2022. MLstruct: principal type inference in a Boolean algebra of structural types. Proceedings of the ACM on Programming Languages, 6, OOPSLA2 (2022), https://doi.org/10.1145/3563304
[40]
Simon Peyton Jones, Mark Jones, and Erik Meijer. 1997. Type classes: an exploration of the design space. In Haskell Workshop.
[41]
Gordon Plotkin and Matija Pretnar. 2009. Handlers of Algebraic Effects. Springer Berlin Heidelberg, 80–94. isbn:9783642005909 issn:1611-3349 https://doi.org/10.1007/978-3-642-00590-9_7
[42]
François Pottier and Didier Rémy. 2004. Advanced topics in types and programming languages. MIT press.
[43]
Taro Sekiyama and Hiroshi Unno. 2023. Temporal Verification with Answer-Effect Modification: Dependent Temporal Type-and-Effect System with Delimited Continuations. Proceedings of the ACM on Programming Languages, 7, POPL (2023), https://doi.org/10.1145/3571264
[44]
Mads Tofte and Jean-Pierre Talpin. 1997. Region-Based Memory Management. Information and Computation, 132, 2 (1997), https://doi.org/10.1006/inco.1996.2613
[45]
Dimitrios Vytiniotis, Simon Peyton Jones, and Tom Schrijvers. 2010. Let should not be generalized. In Proceedings of the 5th ACM SIGPLAN workshop on Types in language design and implementation. https://doi.org/10.1145/1708016.1708023
[46]
Dimitrios Vytiniotis, Simon Peyton Jones, Tom Schrijvers, and Martin Sulzmann. 2011. OutsideIn(X) Modular type inference with local assumptions. Journal of Functional Programming, 21, 4–5 (2011), https://doi.org/10.1017/s0956796811000098
[47]
P. Wadler and S. Blott. 1989. How to make ad-hoc polymorphism less ad hoc. In Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL ’89. https://doi.org/10.1145/75277.75283
Index Terms
- Associated Effects: Flexible Abstractions for Effectful Programming
Recommendations
Associated type synonyms
Proceedings of the tenth ACM SIGPLAN international conference on Functional programmingHaskell programmers often use a multi-parameter type class in which one or more type parameters are functionally dependent on the first. Although such functional dependencies have proved quite popular in practice, they express the programmer's intent ...
Associated type synonyms
ICFP '05: Proceedings of the tenth ACM SIGPLAN international conference on Functional programmingHaskell programmers often use a multi-parameter type class in which one or more type parameters are functionally dependent on the first. Although such functional dependencies have proved quite popular in practice, they express the programmer's intent ...
Associated types with class
Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languagesHaskell's type classes allow ad-hoc overloading, or type-indexing, of functions. A natural generalisation is to allow type-indexing of data types as well. It turns out that this idea directly supports a powerful form of abstraction called associated ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
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: 20 June 2024
Published in PACMPL Volume 8, Issue PLDI
Check for updates
Badges
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 1,152Total Downloads
- Downloads (Last 12 months)1,152
- Downloads (Last 6 weeks)187
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in