I recently read a paper titled Extensible Effects: An Alternative to Monad Transformers (2013). The paper describes a framework that is simultaneously more powerful than the monad transformer library, in the sense that more patterns can be expressed, but also more efficient, in that the run-time cost is lower. This sounded like a winning combination, so my interest was piqued.
Others have written on this subject. Edward provides some theoretic insight and history here, and Charles provides a practical take on the subject here,
My goal with this blog post is to distill some of what working with extensible-effects looks like from the eyes of someone who reads a lot of Haskell but has written very little.
The goal of the paper was to solve the problem of composing effects without imposing restrictions on their interactions. This immediately reminded me of the Effects library in Idris. A very interesting choice that the authors of the paper made when designing extensible effects was to model it after the mtl(Monad Transformer Library). As a result, they promise gains in efficiency and expressiveness with only minor changes to existing code.
To create some intuition for the system, allow me to define some terminology.
The benefit of this separation of effects as requests to a handler is that we need not commit to a static ordering when it doesn’t matter. There are limitations to this model, and extensible effects improves on this. These improvements are:
The paper goes on to describe the framework, what the problems are with mtl, and the implementation of extensible effects. I won’t elaborate on those sections here, for the sake of brevity.
Before moving on to the interface, I’d like to share an interesting quote from the paper that helped me understand the relationship between programs and effects better:
…the interpreter of requests as transformations on resources, is not part of the user program (just as the the operating system kernel is not part of the user’s process, and the interpreter of IO actions in Haskell is not part of the user program).
I share below an ASCII-ized version of the interface that the paper provides.
instance Monad (Eff r)
-- Pure computations
data Void
run :: Eff Void w -> w
-- Reader (or environment) effect
type Reader e
ask :: (Typeable e, Member (Reader e) r) => Eff r e
local :: (Typeable e, Member (Reader e) r) =>
(e -> e) -> Eff r w -> Eff r w
runReader :: Typeable e => Eff (Reader e :> r) w -> e -> Eff r w
-- Exceptions
type Exc e
throwError :: (Typeable e, Member (Exc e) r) => e -> Eff r a
catchError :: (Typeable e, Member (Exc e) r) =>
Eff r w -> (e -> Eff r w) -> Eff r w
runError :: Typeable e => Eff (Exc e :> r) w -> Eff r (Either e w)
-- State
type State s
get :: (Typeable s, Member (State s) r) => Eff r s
put :: (Typeable s, Member (State s) r) => s -> Eff r ()
runState :: Typeable s => Eff (State s :> r) w -> s -> Eff r (w,s)
-- Non-determinism
type Choose
choose :: Member Choose r => [w] -> Eff r w
makeChoice :: Eff (Choose :> r) w -> Eff r [w]
-- Tracing
type Trace
trace :: Member Trace r => String -> Eff r ()
runTrace :: Eff (Trace :> Void) w -> IO w
-- Build-in effects (e.g., IO)
type Lift m
lift :: (Typeable1 m, MemberU2 Lift (Lift m) r) => m w -> Eff r w
runLift :: (Monad m, Typeable1 m) => Eff (Lift m :> Void) w -> m wThese are just the effects that are provided by the library. It’s possible to define more effects, and Charles shows how to do so to create a Logging effect.
This is my first time seeing type-level operators. It’s really interesting how (:>) is used via type-level pattern-matching to extract an effect from the “stream of requests”.
I also like how effect-less computations are modeled by the Void empty data type. For me, this made it clear how to navigate between effecting and effect free code. The composition feels intuitive to me.
So, let’s actually get to the part where we play around with extensible-effects! This section was tested only with GHC 7.8.2. With other versions of the GHC compiler, your mileage may vary.
First, create a sandbox and install the library:
$ cabal sandbox init
$ cabal install extensible-effectsHere’s the sample we’ll be working with, borrowed from page 3 of the paper and extended with a main and required language extensions:
{-# LANGUAGE FlexibleContexts #-}
module Main where
import Control.Eff
import Control.Eff.Reader.Strict
t2 :: (Member (Reader Int) r, Member (Reader Float) r) => Eff r Float
t2 = do
v1 <- ask
v2 <- ask
return $ fromIntegral (v1 + (1 :: Int)) + (v2 + (2 :: Float))
main :: IO ()
main = print $ run $ runReader (runReader t2 (10 :: Int)) (20 :: Float)Here’s a minimal cabal file to get us running:
name: exteff
version: 0.1.0.0
build-type: Simple
cabal-version: >=1.10
executable exteff
main-is: Main.hs
build-depends: base >=4.7 && <4.8,
extensible-effects>=1.4.1
default-language: Haskell2010Let’s compile this program and run it:
$ cabal run
...
33.0Great! It’s encouraging when sample code from a paper runs as expected. Now let’s modify the implementation and see what the type system captures for us:
t2 :: (Member (Reader Int) r, Member (Reader Float) r) => Eff r Float
t2 = do
v1 <- ask
return $ fromIntegral (v1 + (1 :: Int)) + (v1 + (2 :: Float))Here’s the error output:
Couldn't match type ‘Int’ with ‘Float’
Expected type: Eff r Float
Actual type: Eff r Int
In a stmt of a 'do' block:
return $ fromIntegral (v1 + (1 :: Int)) + (v1 + (2 :: Float))So from that, I gather that we’re trying to use an effect of type Eff r Int where one of Eff r Float is expected. Looking at the offending line, the offender seems to be (v1 + (2 :: Float)). Alright, let’s see what happens if we change that to an Int computation:
t2 :: (Member (Reader Int) r, Member (Reader Float) r) => Eff r Float
t2 = do
v1 <- ask
return $ fromIntegral (v1 + (1 :: Int)) + fromIntegral (v1 + (2 :: Int))No compile error this time. What happens when it runs?
$ cabal run
23.023.0 - that’s not the 33.0 from earlier. What happened? It turns out that type inference determined that the environment to read from was the Reader Int, which makes sense. There was no compiler error since all the effects were consumed because of the main, though not every effect was used in t2. This makes sense, too, given that sometimes we want environments (Reader) to be passed down a call-stack without being used at each point. Nifty!
What happens if we don’t consume all the effects? Let’s modify main:
We get the following compiler error:
No instance for (Member (Reader Float) ())
arising from a use of ‘t2’
In the first argument of ‘runReader’, namely ‘t2’This tells us that we failed to consume an effect of type Reader Float. This is useful, since if we choose to add or remove effects during a refactoring, errors of this form tell us where changes need to be made.
Extensible effects looks like a very promising concept. I’m eager to see what kinds of things are built with it, what kinds of problems are found with the approach, and what the limits are.
It took me some time to write this post. There’s a lot that I don’t yet understand, and a fear of presenting details inaccurately slowed me down. I’m writing this section for others that might be facing similar difficulties in the hopes that it helps.
I pondered on how to write this post for some time.
At first, I thought it might be interesting to review the state of the art in effects management. There’s certainly a lot of literature out there - even over the past year! - about how to handle effects with the aid of a type system. However, I quickly found myself beyond my depth and running out of time.
I still wanted this post to happen, so I narrowed my scope.
Next, I wanted to take a more practical spin on the topic. I wanted to show how extensible effects improves over monad transformers. To accomplish this, I thought I might provide comparative code samples to show how extensible effects compares to mtl. However, I’ve never actually worked with monad transformers. I’m not that far along in my Haskell journey! I attempted to make a monad transformer example mimicking the behavior of some of the samples in the extensible effects paper, but failed to get anything to compile. I was finding myself close to my personal deadline, so I moved on.
I narrowed even further.
Finally, what I was able to do was provide a few “In Action” snippets of working with the extensible-effects library. That’s how this post came to be.
It’s likely there’ll be a part [2..] here in the future, when my ratio of reads to writes for Haskell narrows. When that happens, I’d like to address the points I couldn’t here, namely: