Oleg Kiselyov
ABSTRACT
We present a rational reconstruction of extensible effects, the recently proposed alternative to monad transformers, as the confluence of efforts to make effectful computations compose. Free monads and then extensible effects emerge from the straightforward term representation of an effectful computation, as more and more boilerplate is abstracted away. The generalization process further leads to freer monads, constructed without the Functor constraint. The continuation exposed in freer monads can then be represented as an efficient type-aligned data structure. The end result is the algorithmically efficient extensible effects library, which is not only more comprehensible but also faster than earlier implementations. As an illustration of the new library, we show three surprisingly simple applications: non-determinism with committed choice (LogicT), catching IO exceptions in the presence of other effects, and the semi-automatic management of file handles and other resources through monadic regions. We extensively use and promote the new sort of `laziness', which underlies the left Kan extension: instead of performing an operation, keep its operands and pretend it is done.
- H. Apfelmus. The Operational monad tutorial. The Monad.Reader, 15:37–56, 2010.Google Scholar
- S. Awodey. Category Theory, volume 49 of Oxford Logic Guides. Oxford University Press, 2006.Google ScholarCross Ref
- P. Bahr. Composing and decomposing data types: a closed type families implementation of data types à la carte. In WGP@ICFP, pages 71–82. ACM Press, 31 Aug. 2014. Google ScholarDigital Library
- A. Bauer and M. Pretnar. Programming with algebraic effects and handlers. arXiv:1203.1539 {cs.PL}, 2012.Google Scholar
- J.-P. Bernardy and N. Pouillard. Names for free: polymorphic views of names and binders. In Haskell {11}, pages 13–24. Google ScholarDigital Library
- E. Brady. Programming and reasoning with algebraic effects and dependent types. In ICFP {15}, pages 133–144.. Google ScholarDigital Library
- R. Cartwright and M. Felleisen. Extensible denotational language specifications. In M. Hagiya and J. C. Mitchell, editors, Theor. Aspects of Comp. Soft., number 789 in LNCS, pages 244–272. Springer, 1994. Google ScholarDigital Library
- K. Claessen. Parallel parsing processes. J. Functional Programming, 14(6):741–757, 2004. Google ScholarDigital Library
- O. Danvy and A. Filinski. Abstracting control. In Proceedings of the 1990 ACM Conference on Lisp and Functional Programming, pages 151–160. ACM Press, 27–29 June 1990. Google ScholarDigital Library
- M. Fluet and J. G. Morrisett. Monadic regions. J. Functional Programming, 16(4–5):485–545, 2006. Google ScholarDigital Library
- Haskell. Haskell Symposium, 2013. ACM.Google Scholar
- Haskell. Haskell Symposium, 2014. ACM.Google Scholar
- R. Hinze. Deriving backtracking monad transformers. In ICFP ’00, pages 186–197. ACM Press, 2000. Google ScholarDigital Library
- J. Hughes. The design of a pretty-printing library. In First Intl. Spring School on Adv. Functional Programming Techniques, pages 53–96, London, UK, UK, 1995. Springer-Verlag. Google ScholarDigital Library
- ICFP. ICFP ’13, 2013. ACM Press.Google Scholar
- P. Johann and N. Ghani. Foundations for structured programming with GADTs. In POPL ’08, pages 297–308. ACM Press, 2008. Google ScholarDigital Library
- O. Kammar, S. Lindley, and N. Oury. Handlers in action. In ICFP Google ScholarDigital Library
- , pages 145–158.Google Scholar
- O. Kiselyov. Iteratees. In Proc. of the 11th International Symposium on Functional and Logic Programming, pages 166–181, 2012. Google ScholarDigital Library
- O. Kiselyov and C.-c. Shan. Lightweight monadic regions. In Proc. 2008 Haskell Symposium, pages 1–12. ACM Press, 2008. Google ScholarDigital Library
- O. Kiselyov, C.-c. Shan, D. P. Friedman, and A. Sabry. Backtracking, interleaving, and terminating monad transformers (functional pearl). In ICFP ’05, pages 192–203. ACM Press, Sept. 2005. Google ScholarDigital Library
- O. Kiselyov, A. Sabry, and C. Swords. Extensible effects: an alternative to monad transformers. In Haskell {11}, pages 59–70.. Google ScholarDigital Library
- S. Liang, P. Hudak, and M. Jones. Monad transformers and modular interpreters. In POPL ’95, pages 333–343. ACM Press, 1995. Google ScholarDigital Library
- C.-k. Lin. Programming monads operationally with Unimo. In ICFP ’06, pages 274–285. ACM Press, 2006. Google ScholarDigital Library
- C. Lüth and N. Ghani. Composing monads using coproducts. In ICFP ’02, pages 133–144. ACM Press, 2002. Google ScholarDigital Library
- L. Naish. Pruning in logic programming. Technical Report 95/16, Department of Computer Science, University of Melbourne, 1995.Google Scholar
- G. Plotkin and M. Pretnar. Handlers of algebraic effects. In ESOP ’09, pages 80–94, Berlin, Heidelberg, 2009. Springer-Verlag. Google ScholarDigital Library
- N. Sculthorpe, J. Bracker, G. Giorgidze, and A. Gill. The constrainedmonad problem. In ICFP {15}, pages 287–298. Google ScholarDigital Library
- T. Sheard and E. Paˇsali´c. Two-level types and parameterized modules. J. Functional Programming, 14(5):547–587, Sept. 2004. Google ScholarDigital Library
- G. L. Steele, Jr. Building interpreters by composing monads. In POPL ’94, pages 472–492. ACM Press, 1994. Google ScholarDigital Library
- W. Swierstra. Data types à la carte. J. Funct. Program., 18(4):423– 436, July 2008. Google ScholarDigital Library
- A. van der Ploeg and O. Kiselyov. Reflection without remorse: revealing a hidden sequence to speed up monadic reflection. In Haskell {12}, pages 133–144.. Google ScholarDigital Library
- N. Wu and T. Schrijvers. Fusion for free: Efficient algebraic effect handlers. In MPC 2015, 2015. URL /Research/papers/mpc2015.Google Scholar
- pdf.Google Scholar
- N. Wu, T. Schrijvers, and R. Hinze. Effect handlers in scope. In Haskell {12}, pages 1–12. Google ScholarDigital Library
Index Terms
- Freer monads, more extensible effects
Recommendations
Freer monads, more extensible effects
Haskell '15We present a rational reconstruction of extensible effects, the recently proposed alternative to monad transformers, as the confluence of efforts to make effectful computations compose. Free monads and then extensible effects emerge from the ...
Extensible effects: an alternative to monad transformers
Haskell '13: Proceedings of the 2013 ACM SIGPLAN symposium on HaskellWe design and implement a library that solves the long-standing problem of combining effects without imposing restrictions on their interactions (such as static ordering). Effects arise from interactions between a client and an effect handler (...
Extensible effects: an alternative to monad transformers
Haskell '13We design and implement a library that solves the long-standing problem of combining effects without imposing restrictions on their interactions (such as static ordering). Effects arise from interactions between a client and an effect handler (...
Comments