Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T05:59:38.811Z Has data issue: false hasContentIssue false
  • English
  • Français

Doo bee doo bee doo

Part of: Effects and Handlers

Published online by Cambridge University Press:  31 March 2020

LUKAS CONVENT Open the ORCID record for LUKAS CONVENT [Opens in a new window] ,
SAM LINDLEY ,
CONOR MCBRIDE  and
CRAIG MCLAUGHLIN
LUKAS CONVENT
Affiliation:
University of Lübeck, Lübeck, Germany, (e-mail: [email protected])
SAM LINDLEY
Affiliation:
The University of Edinburgh, EdinburghEH8 9YL, UK and Imperial College London, LondonSW7 2BU, UK, (e-mail: [email protected])
CONOR MCBRIDE
Affiliation:
University of Strathclyde, GlasgowG1 1XQ, UK, (e-mail: [email protected])
CRAIG MCLAUGHLIN
Affiliation:
The University of Edinburgh, EdinburghEH8 9YL, UK and University of New South Wales, Kensington, Australia and Data61, CSIRO, Australia, (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We explore the design and implementation of Frank, a strict functional programming language with a bidirectional effect type system designed from the ground up around a novel variant of Plotkin and Pretnar’s effect handler abstraction. Effect handlers provide an abstraction for modular effectful programming: a handler acts as an interpreter for a collection of commands whose interfaces are statically tracked by the type system. However, Frank eliminates the need for an additional effect handling construct by generalising the basic mechanism of functional abstraction itself. A function is but the special case of a Frank operator that interprets no commands. Moreover, Frank’s operators can be multihandlers which simultaneously interpret commands from several sources at once, without disturbing the direct style of functional programming with values. Effect typing in Frank employs a novel form of effect polymorphism which avoids mentioning effect variables in source code. This is achieved by propagating an ambient ability inwards, rather than accumulating unions of potential effects outwards. With the ambient ability describing the effects that are available at a certain point in the code, it can become necessary to reconfigure access to the ambient ability. A primary goal is to be able to encapsulate internal effects, eliminating a phenomenon we call effect pollution. Moreover, it is sometimes desirable to rewire the effect flow between effectful library components. We propose adaptors as a means for supporting both effect encapsulation and more general rewiring. Programming with effects and handlers is in its infancy. We contribute an exploration of future possibilities, particularly in combination with other forms of rich type systems.

Type
Research Article
Information
Journal of Functional Programming , Volume 30 , 2020 , e9
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2020. Published by Cambridge University Press

References

Abel, A. & Pientka, B. (2013) Wellfounded recursion with copatterns: A unified approach to termination and productivity. In ICFP. ACM, pp. 185–196.Google Scholar
Adams, M. D. & Ağacan, Ö. S. (2014) Indentation-sensitive parsing for Parsec. In Haskell. ACM.Google Scholar
Ahman, D. (2017) Fibred Computational Effects. Ph.D. thesis, School of Informatics, The University of Edinburgh.Google Scholar
Atkey, R. (2015) An Algebraic Approach to Typechecking and Elaboration. https://bentnib.org/posts/2015-04-19-algebraic-approach-typechecking-and-elaboration.htmlGoogle Scholar
Atkey, R. & McBride, C. (2013) Productive coprogramming with guarded recursion. In ICFP. ACM, pp. 197–208.Google Scholar
Bauer, A. & Pretnar, M. (2014) An effect system for algebraic effects and handlers. Log. Methods Comput. Sci. 10(4), 1–16. https://link.springer.com/chapter/10.1007/978-3-642-40206-7_1CrossRefGoogle Scholar
Bauer, A. & Pretnar, M. (2015) Programming with algebraic effects and handlers. J. log. Alg. Meth. Program. 84(1), 108–123.Google Scholar
Biernacki, D., Piróg, M., Polesiuk, P. & Sieczkowski, F. (2018) Handle with care: Relational interpretation of algebraic effects and handlers. PACMPL 2(POPL), 8:1–8:30.Google Scholar
Biernacki, D., Piróg, M., Polesiuk, P. & Sieczkowski, F. (2019) Abstracting algebraic effects. PACMPL 3(POPL), 1–28.Google Scholar
Biernacki, D., Piróg, M., Polesiuk, P. & Sieczkowski, F. (2020) Binders by day, labels by night: Effect instances via lexically scoped handlers. PACMPL 4(POPL), 48:1–48:29.Google Scholar
Brachthäuser, J. I. & Schuster, P. (2017) Effekt: Extensible algebraic effects in Scala (short paper). In SCALA@SPLASH. ACM, pp. 67–72.CrossRefGoogle Scholar
Brachthäuser, J. I., Schuster, P. & Ostermann, K. (2018) Effect handlers for the masses. PACMPL 2(OOPSLA), 111:1–111:27.Google Scholar
Brachthäuser, J. I., Schuster, P. & Ostermann, K. (to appear) Effekt: Capability-passing style for type- and effect-safe, extensible effect handlers in Scala. J. Funct. Program. 30.CrossRefGoogle Scholar
Brady, E. (2013a) Idris, a general-purpose dependently typed programming language: Design and implementation. J. Funct. Program. 23(5), 552–593.CrossRefGoogle Scholar
Brady, E. (2013b) Programming and reasoning with algebraic effects and dependent types. In ICFP. ACM, pp. 133–144.Google Scholar
Convent, L. (2017). Enhancing a Modular Effectful Programming Language. MSc thesis, School of Informatics, The University of Edinburgh.Google Scholar
Convent, L., Lindley, S., McBride, C. & McLaughlin, C. (2020) Frank repository. Available at: https://www.github.com/frank-lang/frank.Google Scholar
Cooper, E., Lindley, S., Wadler, P. & Yallop, J. (2006) Links: Web programming without tiers. In FMCO. LNCS, vol. 4709. Springer, pp. 266–296.Google Scholar
Dolan, S., White, L., Sivaramakrishnan, K. C., Yallop, J. & Madhavapeddy, A. (2015) Effective concurrency through algebraic effects. In OCaml Workshop.Google Scholar
Dunfield, J. & Krishnaswami, N. R. (2013) Complete and easy bidirectional typechecking for higher-rank polymorphism. In Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming. ICFP’13. New York, NY, USA: ACM, pp. 429–442.Google Scholar
Filinski, A. (1999) Representing layered monads. In POPL. ACM, pp. 175–188.CrossRefGoogle Scholar
Filinski, A. (2010) Monads in action. In POPL. ACM, pp. 483–494.Google Scholar
Forster, Y., Kammar, O., Lindley, S. & Pretnar, M. (2017) On the expressive power of user-defined effects: Effect handlers, monadic reflection, delimited control. PACMPL 1(ICFP), 13:1–13:29.Google Scholar
Forster, Y., Kammar, O., Lindley, S. & Pretnar, M. (2019) On the expressive power of user-defined effects: Effect handlers, monadic reflection, delimited control. J. Funct. Program. 29, e15.CrossRefGoogle Scholar
Fournet, C. & Gonthier, G. (1996) The reflexive CHAM and the join-calculus. In POPL. ACM, pp. 372–385.CrossRefGoogle Scholar
Geron, B. (2019) Defined Algebraic Operations. Ph.D. thesis, University of Birmingham.Google Scholar
Gundry, A., McBride, C. & McKinna, J. (2010) Type inference in context. In MSFP. ACM.CrossRefGoogle Scholar
Gundry, A. M. (2013) Type Inference, Haskell and Dependent Types. Ph.D. thesis, University of Strathclyde.Google Scholar
Hancock, P., & Hyvernat, P. (2006) Programming interfaces and basic topology. Ann. Pure Appl. Logic 137(1–3), 189–239.CrossRefGoogle Scholar
Hillerström, D. (2015) Handlers for Algebraic Effects in Links. MSc thesis, School of Informatics, The University of Edinburgh.Google Scholar
Hillerström, D. (2016) Compilation of Effect Handlers and their Applications in Concurrency. MSc(R) thesis, School of Informatics, The University of Edinburgh.Google Scholar
Hillerström, D. & Lindley, S. (2016) Liberating effects with rows and handlers. In TyDe@ICFP. ACM, pp. 15–27.Google Scholar
Hillerström, D., Lindley, S. & Atkey, R. (2020) Effect handlers via generalised continuations. J. Funct. Program. 30, e5.CrossRefGoogle Scholar
Huet, G. P. (1997) The zipper. J. Funct. Program. 7(5), 549–554.CrossRefGoogle Scholar
Hughes, J. (2004) Programming with arrows. In Advanced Functional Programming, Vene, V. & Uustalu, T. (eds). Lecture Notes in Computer Science, vol. 3622. Springer, pp. 73–129.Google Scholar
Inostroza, P. & van der Storm, T. (2018) Jeff: Objects for effect. In Onward! ACM, pp. 111–124.Google Scholar
Jensen, K. & Wirth, N. (1974) Pascal User Manual and Report. Berlin, Heidelberg: Springer-Verlag.CrossRefGoogle Scholar
Kammar, O., Lindley, S. & Oury, N. (2013) Handlers in action. In ICFP. ACM, pp. 145–158.Google Scholar
Kiselyov, O. & Ishii, H. (2015) Freer monads, more extensible effects. In Haskell. ACM, pp. 94–105.CrossRefGoogle Scholar
Kiselyov, O., Sabry, A. & Swords, C. (2013) Extensible effects: An alternative to monad transformers. In Haskell. ACM, pp. 59–70.CrossRefGoogle Scholar
Kmett, E. A. (2015). Trifecta (1.5.2). Available at: http://hackage.haskell.org/package/trifecta-1.5.2.Google Scholar
Leijen, D. (2014) Koka: Programming with row polymorphic effect types. In MSFP. EPTCS, vol. 153, pp. 100–126.CrossRefGoogle Scholar
Leijen, D. (2017) Type directed compilation of row-typed algebraic effects. In POPL. ACM, pp. 486–499.Google Scholar
Leijen, D. (2018) Algebraic Effect Handlers with Resources and Deep Finalization. Technical report. Microsoft Research.Google Scholar
Leijen, D. & Martini, P. (2015) Parsec (3.1.9). Available at: http://hackage.haskell.org/package/parsec-3.1.9.Google Scholar
Levy, P. B. (2004) Call-By-Push-Value: A Functional/Imperative Synthesis. Semantics Structures in Computation, vol. 2. Springer.Google Scholar
Lindley, S. (2014) Algebraic effects and effect handlers for idioms and arrows. In WGP@ICFP. ACM, pp. 47–58.Google Scholar
Lindley, S., McBride, C. & McLaughlin, C. (2017) Do be do be do. In POPL. ACM, pp. 500–514.Google Scholar
Lucassen, J. M. & Gifford, D. K. (1988) Polymorphic effect systems. In POPL. ACM, pp. 47–57.Google Scholar
MacQueen, D. B. (1984) Modules for standard ML. In LISP and Functional Programming, pp. 198–207.CrossRefGoogle Scholar
McBride, C. (2007) How might effectful programs look? In Workshop on Effects and Type Theory. Available at: http://cs.ioc.ee/efftt/mcbride-slides.pdf.Google Scholar
McBride, C. (2011) Kleisli arrows of outrageous fortune. Available at: https://personal.cis.strath.ac.uk/conor.mcbride/Kleisli.pdf.Google Scholar
McBride, C. (2012) Frank (0.3). Available at: http://hackage.haskell.org/package/Frank.Google Scholar
McBride, C. (2015) Turing-completeness totally free. In MPC. Lecture Notes in Computer Science, vol. 9129. Springer, pp. 257–275.Google Scholar
McBride, C. (2016). Shonky. Available at: https://github.com/pigworker/shonky.Google Scholar
McBride, C. & Paterson, R. (2008) Applicative programming with effects. J. Funct. Program. 18(1), 1–13.CrossRefGoogle Scholar
Papert, S. (1980) Mindstorms: Children, Computers, and Powerful Ideas. New York, NY, USA: Basic Books.Google Scholar
Pierce, B. C. & Turner, D. N. (2000) Local type inference. ACM Trans. Program. Lang. Syst. 22(1), 1–44.CrossRefGoogle Scholar
Piróg, M., Polesiuk, P. & Sieczkowski, F. (2019) Typed equivalence of effect handlers and delimited control. In FSCD. LIPIcs, vol. 131. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 30:1–30:16.Google Scholar
Plotkin, G. D. & Power, J. (2001a) Adequacy for algebraic effects. In FoSSaCS. LNCS, vol. 2030. Springer, pp. 1–24.Google Scholar
Plotkin, G. D. & Power, J. (2001b) Semantics for algebraic operations. Electr. Notes Theor. Comput. Sci. 45, 332–345.CrossRefGoogle Scholar
Plotkin, G. D. & Power, J. (2002) Notions of computation determine monads. In FoSSaCS. Lecture Notes in Computer Science, vol. 2303. Springer, pp. 342–356.CrossRefGoogle Scholar
Plotkin, G. D. & Power, J. (2003) Algebraic operations and generic effects. Appl. Categ. Struct. 11(1), 69–94.CrossRefGoogle Scholar
Plotkin, G. D. & Pretnar, M. (2013) Handling algebraic effects. Log. Methods Comput. Sci. 9(4), 1–36.CrossRefGoogle Scholar
Pretnar, M. (2009) The Logic and Handling of Algebraic Effects. Ph.D. thesis, School of Informatics, The University of Edinburgh.Google Scholar
Pretnar, M. (2014) Inferring algebraic effects. Log. Methods Comput. Sci. 10(3), 1–43.CrossRefGoogle Scholar
Schrijvers, T., Piróg, M., Wu, N. & Jaskelioff, M. (2019) Monad transformers and modular algebraic effects: What binds them together. In Haskell@ICFP. ACM, pp. 98–113.Google Scholar
Schrijvers, T., Wu, N., Desouter, B. & Demoen, B. (2014) Heuristics entwined with handlers combined: From functional specification to logic programming implementation. In PPDP. ACM, pp. 259–270.Google Scholar
Shivers, O. & Turon, A. J. (2011) Modular rollback through control logging: A pair of twin functional pearls. In ICFP. ACM, pp. 58–68.Google Scholar
Swamy, N., Guts, N., Leijen, D. & Hicks, M. (2011) Lightweight monadic programming in ML. In ICFP. ACM, pp. 15–27.Google Scholar
Swierstra, W. (2008) Data types à la carte. J. Funct. Program. 18(4), 423–436.CrossRefGoogle Scholar
Talpin, J.-P. & Jouvelot, P. (1994) The type and effect discipline. Inf. Comput. 111(2), 245–296.CrossRefGoogle Scholar
van der Ploeg, A. & Kiselyov, O. (2014) Reflection without remorse: Revealing a hidden sequence to speed up monadic reflection. In Haskell. ACM, pp. 133–144.Google Scholar
Vonnegut, K. (1982) Deadeye Dick. Delacorte.Google Scholar
Wadler, P. (1992) The essence of functional programming. In POPL. ACM, pp. 1–14.Google Scholar
Wadler, P. & Blott, S. (1989) How to make ad-hoc polymorphism less ad-hoc. In POPL. ACM, pp. 60–76.Google Scholar
Wu, N. & Schrijvers, T. (2015) Fusion for free - efficient algebraic effect handlers. In MPC. Lecture Notes in Computer Science, vol. 9129. Springer, pp. 302–322.Google Scholar
Wu, N., Schrijvers, T. & Hinze, R. (2014) Effect handlers in scope. In Haskell. ACM, pp. 1–12.Google Scholar
Zhang, Y. & Myers, A. C. (2019) Abstraction-safe effect handlers via tunneling. PACMPL 3(POPL), 5:1–5:29.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.