Polymonadic Programming

Michael Hicks
(University of Maryland, College Park)
Gavin Bierman
(Microsoft Research)
Nataliya Guts
(University of Maryland, College Park)
Daan Leijen
(Microsoft Research)
Nikhil Swamy
(Microsoft Research)

Monads are a popular tool for the working functional programmer to structure effectful computations. This paper presents polymonads, a generalization of monads. Polymonads give the familiar monadic bind the more general type forall a,b. L a -> (a -> M b) -> N b, to compose computations with three different kinds of effects, rather than just one. Polymonads subsume monads and parameterized monads, and can express other constructions, including precise type-and-effect systems and information flow tracking; more generally, polymonads correspond to Tate's productoid semantic model. We show how to equip a core language (called lambda-PM) with syntactic support for programming with polymonads. Type inference and elaboration in lambda-PM allows programmers to write polymonadic code directly in an ML-like syntax–our algorithms compute principal types and produce elaborated programs wherein the binds appear explicitly. Furthermore, we prove that the elaboration is coherent: no matter which (type-correct) binds are chosen, the elaborated program's semantics will be the same. Pleasingly, the inferred types are easy to read: the polymonad laws justify (sometimes dramatic) simplifications, but with no effect on a type's generality.

In Paul Levy and Neel Krishnaswami: Proceedings 5th Workshop on Mathematically Structured Functional Programming (MSFP 2014), Grenoble, France, 12 April 2014, Electronic Proceedings in Theoretical Computer Science 153, pp. 79–99.
Published: 5th June 2014.

ArXived at: http://dx.doi.org/10.4204/EPTCS.153.7 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org