A fast, flexible, fused effect system for Haskell
fused-effectsis an effect system for Haskell that values expressivity, efficiency, and rigor. It provides an encoding of algebraic, higher-order effects, includes a library of the most common effects, and generates efficient code by fusing effect handlers through computations. It is suitable for use in hobbyist, research, and industrial contexts.
Readers already familiar with effect systems may wish to start with the usage instead. For those interested, this talk at Strange Loop outlines the history of and motivation behind effect systems and
fused-effectsitself.
In
fused-effectsand other systems with algebraic (or, sometimes, extensible) effects, effectful programs are split into two parts: the specification (or syntax) of the actions to be performed, and the interpretation (or semantics) given to them.
In
fused-effects, effect types provide syntax and carrier types provide semantics. Effect types are datatypes with one constructor for each action, invoked using the
sendbuiltin. Carriers are monads, with an
Algebrainstance specifying how an effect’s constructors should be interpreted. Carriers can handle more than one effect, and multiple carriers can be defined for the same effect, corresponding to different interpreters for the effect’s syntax.
Unlike some other effect systems,
fused-effectsoffers higher-order (or scoped) effects in addition to first-order algebraic effects. In a strictly first-order algebraic effect system, operations like
localor
catchError, which specify some action limited to a given scope, must be implemented as interpreters, hard-coding their meaning in precisely the manner algebraic effects were designed to avoid. By specifying effects as higher-order functors, this limitation is removed, meaning that these operations admit a variety of interpretations. This means, for example, that you can introspect and redefine both the
localand
askoperations provided by the
Readereffect, rather than solely
ask(as is the case with certain formulations of algebraic effects).
As Nicolas Wu et al. showed in Effect Handlers in Scope, this has implications for the expressiveness of effect systems. It also has the benefit of making effect handling more consistent, since scoped operations are just syntax which can be interpreted like any other, and are thus simpler to reason about.
In order to maximize efficiency,
fused-effectsapplies fusion laws, avoiding the construction of intermediate representations of effectful computations between effect handlers. In fact, this is applied as far as the initial construction as well: there is no representation of the computation as a free monad parameterized by some syntax type. As such,
fused-effectsavoids the overhead associated with constructing and evaluating any underlying free or freer monad.
Instead, computations are performed in a carrier type for the syntax, typically a monad wrapping further monads, via an instance of the
Carrierclass. This carrier is specific to the effect handler selected, but since it isn’t described until the handler is applied, the separation between specification and interpretation is maintained. Computations are written against an abstract effectful signature, and only specialized to some concrete carrier when their effects are interpreted.
Since the interpretation of effects is written as a typeclass instance which
ghcis eager to inline, performance is excellent: approximately on par with
mtl.
Finally, since the fusion of carrier algebras occurs as a result of the selection of the carriers, it doesn’t depend on complex
RULESpragmas, making it easy to reason about and tune.
The
fused-effectspackage is organized into two module hierarchies: * those under
Control.Effect, which provide effects and functions that invoke these effects’ capabilities. * those under
Control.Carrier, which provide carrier types capable of executing the effects described by a given effect type.
An additional module,
Control.Algebra, provides the
Algebrainterface that carrier types implement to provide an interpretation of a given effect. You shouldn’t need to import it unless you’re defining your own effects.
Each module under the
Control.Effecthierarchy provides a set of functions that invoke effects, each mapping to a constructor of the underlying effect type. These functions are similar to, but more powerful than, those provided by
mtl. In this example, we invoke the
getand
putfunctions provided by
Control.Effect.State, first extracting the state and then updating it with a new value:
action1 :: Has (State String) sig m => m () action1 = get >>= \ s -> put ("hello, " ++ s)
The
Hasconstraint requires a given effect (here
State) to be present in a signature (
sig), and relates that signature to be present in a carrier type (
m). We generally, but not always, program against an abstract carrier type, usually called
m, as carrier types always implement the
Monadtypeclass.
To add effects to a given computation, add more
Hasconstraints to the signature/carrier pair
sigand
m. For example, to add a
Readereffect managing an
Int, we would write:
action2 :: (Has (State String) sig m, Has (Reader Int) sig m) => m () action2 = do iRunning effects
Effects are run with effect handlers, specified as functions (generally starting with
run…) unpacking some specific monad with aCarrierinstance. For example, we can run aStatecomputation usingrunState, imported from theControl.Carrier.State.Strictcarrier module:example1 :: Algebra sig m => [a] -> m (Int, ()) example1 list = runState 0 $ do irunStatereturns a tuple of both the computed value (the()) and the final state (theInt), visible in the result of the returned computation. Thegetfunction is resolved with a visible type application, due to the fact that effects can contain more than one state type (in contrast withmtl’sMonadState, which limits the user to a single state type).Since this function returns a value in some carrier
m, effect handlers can be chained to run multiple effects. Here, we get the list to compute the length of from aReadereffect:example2 :: Algebra sig m => m (Int, ()) example2 = runReader "hello" . runState 0 $ do list(Note that the type annotation on
listis necessary to disambiguate the requested value, since otherwise all the typechecker knows is that it’s an arbitraryFoldable. For more information, see the comparison tomtl.)When all effects have been handled, a computation’s final value can be extracted with
run:example3 :: (Int, ()) example3 = run . runReader "hello" . runState 0 $ do listrunis itself actually an effect handler for theLift Identityeffect, whose only operation is to lift a result value into a computation.Alternatively, arbitrary
Monads can be embedded into effectful computations using theLifteffect. In this case, the underlyingMonadic computation can be extracted usingrunM. Here, we use theMonadIOinstance for theLiftCcarrier to liftputStrLninto the middle of our computation:example4 :: IO (Int, ()) example4 = runM . runReader "hello" . runState 0 $ do list(Note that we no longer need to give a type annotation for
list, sinceputStrLnconstrains the type for us.)Required compiler extensions
When defining your own effects, you may need
-XKindSignaturesif GHC cannot correctly infer the type of your constructor; see the documentation on common errors for more information about this case.When defining carriers, you’ll need
-XTypeOperatorsto declare aCarrierinstance over (:+:),-XFlexibleInstancesto loosen the conditions on the instance,-XMultiParamTypeClassessinceCarriertakes two parameters, and-XUndecidableInstancesto satisfy the coverage condition for this instance.The following invocation, taken from the teletype example, should suffice for most use or construction of effects and carriers:
{-# LANGUAGE FlexibleInstances, GeneralizedNewtypeDeriving, MultiParamTypeClasses, TypeOperators, UndecidableInstances #-}Defining new effects
The process of defining new effects is outlined in
docs/defining_effects.md, using the classicTeletypeeffect as an example.Project overview
This project builds a Haskell package named
fused-effects. The library’s sources are insrc. Unit tests are intest, and library usage examples are inexamples. Further documentation can be found indocs.This project adheres to the Contributor Covenant code of conduct. By participating, you are expected to uphold this code.
Finally, this project is licensed under the BSD 3-clause license.
Development
Development of
fused-effectsis typically done usingcabal v2-build:cabal v2-build # build the library cabal v2-test # build and run the examples and testsThe package is available on hackage, and can be used by adding it to a component’s
build-dependsfield in your.cabalfile.Testing
fused-effectscomes with a rigorous test suite. Each law or property stated in the Haddock documentation is checked using generative tests powered by thehedgehoglibrary.Versioning
fused-effectsadheres to the Package Versioning Policy standard.Benchmarks
To run the provided benchmark suite, use
cabal v2-bench. You may wish to provide the-O2compiler option to view performance under aggressive optimizations.fused-effectshas been benchmarked against a number of other effect systems. See also @patrickt’s benchmarks.Related work
fused-effectsis an encoding of higher-order algebraic effects following the recipes in Effect Handlers in Scope (Nicolas Wu, Tom Schrijvers, Ralf Hinze), Monad Transformers and Modular Algebraic Effects: What Binds Them Together (Tom Schrijvers, Maciej Piróg, Nicolas Wu, Mauro Jaskelioff), and Fusion for Free—Efficient Algebraic Effect Handlers (Nicolas Wu, Tom Schrijvers).Contributed packages
Though we aim to keep the
fused-effectscore minimal, we encourage the development of externalfused-effects-compatible libraries. If you’ve written one that you’d like to be mentioned here, get in touch!
fused-effects-lensprovides combinators to use the
lenslibrary fluently inside effectful computations.
fused-effects-exceptionsprovides handlers for exceptions thrown in the
IOmonad.
fused-effects-resumableprovides resumable exceptions, which can also serve as a limited form of coroutines.
fused-effects-mwc-randomprovides a performant, high-quality source of random data, as well as values from common numerical distributions.
fused-effects-readlineprovides a REPL effect that interfaces with
haskelinefor its UI.
fused-effects-parserprovides parser-combinator style effects similar to parsing libraries such as
trifecta.
fused-effects-opticsprovides combinators for the
opticsecosystem.
fused-effects
semantic, a program analysis toolkit
now-haskell, a client library for AWS Lambda
mtl
mtl,
fused-effectsprovides a library of monadic effects which can be given different interpretations. In
mtlthis is done by defining new instances of the typeclasses encoding the actions of the effect, e.g.
MonadState. In
fused-effects, this is done by defining new instances of the
Carriertypeclass for the effect.
Also like
mtl,
fused-effectsallows scoped operations like
localand
catchErrorto be given different interpretations. As with first-order operations,
mtlachieves this with a final tagless encoding via methods, whereas
fused-effectsachieves this with an initial algebra encoding via
Carrierinstances.
In addition,
mtland
fused-effectsare similar in that they provide instances for the monad types defined in the
transformerspackage (
Control.Monad.Reader,
Control.Monad.Writer, etc). This means that applications using
mtlcan migrate many existing
transformers-based monad stacks to
fused-effectswith minimal code changes.
fused-effectsprovides its own hierarchy of carrier monads (under the
Control.Carriernamespace) that provide a more fluent interface for new code, though it may be useful to use
transformerstypes when working with third-party libraries.
Unlike
mtl, effects are automatically available regardless of where they occur in the signature; in
mtlthis requires instances for all valid orderings of the transformers (O(n²) of them, in general).
Also unlike
mtl, there can be more than one
Stateor
Readereffect in a signature. This is a tradeoff:
mtlis able to provide excellent type inference for effectful operations like
get, since the functional dependencies can resolve the state type from the monad type.
Unlike
fused-effects,
mtlprovides a
ContTmonad transformer; however, it’s worth noting that many behaviours possible with delimited continuations (e.g. resumable exceptions) are directly encodable as effects.
Finally, thanks to the fusion and inlining of carriers,
fused-effectsis only marginally slower than equivalent
mtlcode (see benchmarks).
freer-simple
freer-simple,
fused-effectsuses an initial encoding of library- and user-defined effects as syntax which can then be given different interpretations. In
freer-simple, this is done with a family of interpreter functions (which cover a variety of needs, and which can be extended for more bespoke needs), whereas in
fused-effectsthis is done with
Carrierinstances for
newtypes.
Unlike
fused-effects, in
freer-simple, scoped operations like
catchErrorand
localare implemented as interpreters, and can therefore not be given new interpretations.
Unlike
freer-simple,
fused-effectshas relatively little attention paid to compiler error messaging, which can make common (compile-time) errors somewhat more confusing to diagnose. Similarly,
freer-simple’s family of interpreter functions can make the job of defining new effect handlers somewhat easier than in
fused-effects. Further,
freer-simpleprovides many of the same effects as
fused-effects, plus a coroutine effect, but minus resource management and random generation.
Finally,
fused-effectshas been benchmarked as faster than
freer-simple.
polysemy
polysemy,
fused-effectsis a batteries-included effect system capable of scoped, reinterpretable algebraic effects.
As of GHC 8.8,
fused-effectsoutperforms
polysemy, though new effects take more code to define in
fused-effectsthan
polysemy(though the
Control.Carrier.Interpretmodule provides a low-friction API for rapid prototyping of new effects). Like
freer-simpleand unlike
fused-effects, polysemy provides custom type errors if a given effect invocation is ambigous or invalid in the current context.
eff
effis similar in many ways to
fused-effects, but is slightly more performant due to its representation of effects as typeclasses. This approach lets GHC generate better code in exchange for sacrificing the flexibility associated with effects represented as data types.
effalso uses the
monad-controlpackage to lift effects between contexts rather than implementing an
Algebra-style class itself.
The authors of fused-effects would like to thank:
fused-effects;
eff,
polysemy, and
capabilities, for their exploration of the space.