Edwin Brady

Programming and Reasoning with Algebraic Effects and Dependent Types

I have just submitted a new paper to ICFP 2013:

Programming and Reasoning with Algebraic Effects and Dependent Types,
Edwin Brady

One often cited benefit of pure functional programming is that pure code is easier to test and reason about, both formally and informally. However, in order to be useful, programs must interact with the outside world. Haskell solves this problem using monads to capture details of possibly side effecting computations — it provides monads for capturing State, I/O, exceptions, non-determinism, libraries for practical purposes such as CGI and parsing, and many others, as well as monad transformers for combining multiple effects.

Unfortunately, useful as monads are, they do not compose very well. Monad transformers can quickly become unwieldy when there are lots of effects to manage, leading to a temptation in larger programs to combine everything into one coarse-grained state and exception monad. In this paper I describe an alternative approach based on handling algebraic effects, implemented in the Idris programming language. I show how to describe side effecting computations, how to write programs which compose multiple fine-grained effects, and how, using dependent types, we can use this approach to reason about states in effectful programs.

You can find the draft here. As usual, comments are very welcome.