Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Lightweight Monadic Programming in ML

Nikhil Swamy, Nataliya Guts, Daan Leijen, and Michael Hicks

Abstract

Many useful programming constructions can be expressed as monads. Examples include support for probabilistic computations, time-varying expressions, parsers, and information flow tracking, not to mention effectful features like state and I/O. In this paper, we present a type-based rewriting algorithm to make programming with arbitrary monads as easy as using ML's built-in support for state and I/O. Programmers write programs using monadic values of type M t as if they were of type t, and our algorithm inserts the necessary binds, units, and monad-to-monad morphisms so that the program typechecks. Our algorithm is based on Jones' qualified types and enjoys three useful properties: (1) principal types, i.e., the rewriting we perform is the most general; (2) coherence, i.e., thanks to the monad and morphism laws, all instances of the principal rewriting have the same semantics; (3) decidability; i.e., the solver for generated constraints will always terminate. Throughout the paper we present simple examples from the domains listed above. Our most complete example, which illustrates the expressive power of our system, proves that ML programs rewritten by our algorithm to use the information flow monad are equivalent to programs in FlowCaml, a domain-specific information flow tracking language.

Details

Publication typeInproceedings
Published inProceedings of the International Conference of Functional Programming (ICFP'11)
AddressTokyo, Japan
PublisherACM SIGPLAN

Previous versions

Nikhil Swamy, Nataliya Guts, Daan Leijen, and Michael Hicks. Lightweight Monadic Programming in ML, 24 March 2011.

> Publications > Lightweight Monadic Programming in ML