Two failed attempts at extensible effects
June 14, 2014
After I had published The problem with mtl, many people wondered what my proposed solution was. If you, like them, are impatient to find out, feel free to peek at the slides from my kievfprog talk, or directly at the code on github.
Still, I’ll continue this series at my own pace. Today we’ll look at two failed solutions to the problem described in the previous article.
The approach based on free monads, proposed in the original Extensible Effects paper by Oleg Kiselyov, Amr Sabry, and Cameron Swords, and implemented in the corresponding package indeed addresses our problem. My plan for ZuriHac was to revise its API and measure and possibly improve its performance.
I started the hackathon by writing a benchmark to compare different free monad implementations, to decide which one to use internally in the library.
The competing free monad implementations were:
- Free: the standard
Pure a | Free (f (Free f a))free monad
forall b. (a -> f b) -> f b, as described in Asymptotic Improvement of Computations over Free Monads
forall w. (a -> w) -> (f w -> w) -> w, as described in Free Monads for Less. This is the Church- (or Boehm-Berarducci-) encoded version of
- NoRemorse, as described in Reflection without Remorse (code taken from Atze van der Ploeg’s repository)
The benchmark compared the performance of
State-like monads implemented on top of each free monad. I also added a plain
State from the transformers package to this comparison.
What surprised me most was not the relative performance of different representations, but how the
State monad implemented through free monads did relatively to the
State from transformers.
The free monad based
State consistently performed up to two orders of magnitude slower than the transformers’ version. And the free monad version was essentially
Free State, even without the
Typeable-based open unions (which certainly carry an overhead of their own).
Thus, it became clear that if an extensible effects library is to perform well, it has to be based on raw transformers, not free monads.
If, as I wrote in the previous article, the functional dependency is an issue in mtl, can we simply get rid of it?
Well, we could, but that by itself wouldn’t help much. You see, mtl’s classes work by having instances that lift, say,
MonadState actions through
WriterT, and other transformers known to mtl:
instance MonadState s m => MonadState s (ReaderT r m) where get = lift get put = lift . put state = lift . state
In order to make multiple
MonadState instances work, we’d have to write a similar instance for lifting
StateT itself. But in that case GHC would become confused: it wouldn’t know whether to lift a given
get through a
StateT, or attempt to execute it right there. It just isn’t smart enough to make a decision based on the type of the
My solution to this problem is exactly to teach GHC to make such a decision. We’ll see how it works in the next article.