Polysemy: Chasing Performance in Free Monads

Polysemy

Chasing Performance in Free Monads


  • Sandy Maguire
  • sandy@sandymaguire.me

  • reasonablypolymorphic.com
  • github.com/isovector

Today’s slides:

  • reasonablypolymorphic.com/polysemy-talk

Our codebase was written by contractors.

Big ball o’ IO spaghetti.

Impossible to test.


Free monads are what I think programming will look like in 30 years.

Write your applications in domain specific language designed for your exact problem.

Run a series of transformations to compile your high-level specification into lower-level DSLs.


Most programs are easy to describe.

The majority of a codebase is spent dealing with nitty-gritty details.

This is where most of the bugs are.


Let’s turn implementation details into library code!


Example

Data ingestion service that:

  • reads encrypted CSV files
  • emits them in batches to a streaming HTTP service
  • records statistics in Redis


Open Effects:

{ Input Record, Output Record, Output Stat }


Open Effects:

{ FileProvider, Output Record, Output Stat }


Open Effects:

{ FileProvider, Output Record, Output Stat, Encryption }


Open Effects:

{ FTP, Output Record, Output Stat, Encryption }


Open Effects:

{ FTP, Output [Record], Output Stat, Encryption }


Open Effects:

{ FTP, HTTP, Output Stat, Encryption }


Open Effects:

{FTP, HTTP, Encryption, Redis}


Open Effects:

{ FTP, HTTP, Redis}


Open Effects:

{ FTP, Redis }


Open Effects:

{ Redis }


Open Effects:

{ }



But maybe we want to test this without a million mocked services?

And the program is correct under the test,

Then the program is correct under the real interpreter!

Correctness composes!


Two major players in the free monad space:

freer-simple

  • No boilerplate!
  • Friendly to use!
  • 35x slower than theoretically possible.
  • Incapable of expressing lots of desirable effects.

fused-effects

  • SO MUCH BOILERPLATE.
  • Not very friendly.
  • As fast as possible!
  • All effects are expressible!

Neither of these is a good trade-off!


My new library:

polysemy

  • No boilerplate!
  • Friendly to use!
  • As fast as possible!
  • All effects are expressible!

The best of both worlds!


We’ll discuss how this was possible!

echo is no longer conspicuous:

Combining Multiple Effects

We can nest effects as deeply as we want inside of Sum!


Effects a la Carte

Now we are polymorphic in our capabilities.


This is where freer-simple and fused-effects start to differ.

freer-simple diverges to get rid of the boilerplate.

fused-effects diverges to get more speed and expressiveness.

Unfortunately, it’s unclear how to merge the two differences.


How Does freer-simple eliminate the boilerplate?

Insight: because we can’t embed our effects, we can just keep them in a queue.

we can just write

(plus a little magic to thread the output of ReadLine to the input of WriteLine)


With this encoding, we no longer need to have continuations in our effects.

Doesn’t require Functor instances

Exactly parallels the types of the actions


This is a great change, and is \(O(n)\) faster than the naive encoding!

Unfortunately it has extremely high constant factors, due to needing to allocate the intermediary queue of actions.


Too Fast, Too Free

Two months ago, Li-Yao Xia:

I bet if you used the final encoding of Freer, it would be much faster.

What the heck is this thing??


Free is uniquely determined by its interpretation function:

We can reshuffle the Free argument first, and use this function as our definition of Freer.


Reshuffled:

Put a newtype constructor around it:


It took me a few days to work through the implications of this encoding.

To my surprise, it improved the constant factors of freer-simple by 35x.

But why?


Consider the humble ReaderT:

ReaderT lets you read a single, constant value of type r.

It is a zero-cost abstraction.


Anything look familiar?

Now:


What the heck is going on?

Now any time our free monad wants to use an action, it immediately runs it in the final monad.


Even freer freer monads










So free!


We’ve now shown how to solve the boilerplate and performance problems.

Lets rewind and look at the changes fused-effects makes.


Down the other trouser (where we left off)


An effect we’d like, but can’t have:

catch contains an embedded Free.


What we’d like:


Maybe

?

Unfortunately this type cannot be embedded inside a Union :(


Instead:

Just force m to be Free r:


Effects don’t need to use m if they don’t want to.


The Problem

How do State and Error interact?

How can we thread state changes through a Catch action?


The Solution: Functors!

What is a functor, really?

Just a value in some sort of context.

In particular, a value of f () is only a context!


We can abuse this fact, and wrap up the state of the world as some functor.

  • tk () is the state of the world when the effect starts

  • (∀ x. tk (m x) -> n (tk x)) is a distribution law for describing how to run effects in a context.

The “ice-cream cone” operator replaces the contents of a Functor:


The State effect needs to push its state through other effects’ subcomputations.

It can call weave to do this.

decomp can extract a single effect out of a Union; or prove that it was never there to begin with.

But it’s slow.

Now GHC is happy and will make our program fast!


Lots of the boilerplate in fused-effects comes from needing to write Effect instances.

But these instances are necessary for higher-order effects!

Are we cursed to always have this boilerplate?


No!

But all it means is we’ve delayed giving a meaning for Effect until we need to interpret it.


A problem:

The type of runFree doesn’t allow us to change the return type.

It seems like maybe we could just stick a functor in here.

Unfortunately this is no longer a Monad!


Recall that we’re allowed to pick any Monad for the result of runFree.

Instead of evaluating to the final monad m


Just transform it into StateT s m and immediately evaluate that!

But what we’ve built isn’t yet a joyful experience.

In particular, dealing with Yo is painful.


We can clean up the mess of writing effect handlers…

  • GetInitialState is the tk () parameter
  • HoistInterpretation is the distribution law

We’ve now simultaneously solved the boilerplate and performance problems, as well as put a friendly UX around the whole thing.


I’d like to leave you with a comparison.

First, the implementation of bracket in fused-effects:



data Resource m k
  = forall resource any output.
      Resource (m resource)
               (resource -> m any)
               (resource -> m output)
               (output -> k)

deriving instance Functor (Resource m)

instance HFunctor Resource where
  hmap f (Resource acquire release use k) =
    Resource (f acquire) (f . release) (f . use) k

instance Effect Resource where
  handle state handler (Resource acquire release use k)
    = Resource (handler (acquire <$ state))
               (handler . fmap release)
               (handler . fmap use)
               (handler . fmap k)

bracket :: (Member Resource sig, Carrier sig m)
        => m resource
        -> (resource -> m any)
        -> (resource -> m a)
        -> m a
bracket acquire release use =
  send (Resource acquire release use pure)

runResource :: (forall x . m x -> IO x)
            -> ResourceC m a
            -> m a
runResource handler = runReader (Handler handler) . runResourceC

newtype ResourceC m a = ResourceC
  { runResourceC :: ReaderC (Handler m) m a
  }
  deriving ( Alternative, Applicative, Functor, Monad, MonadFail, MonadIO, MonadPlus)

instance MonadTrans ResourceC where
  lift = ResourceC . lift

newtype Handler m = Handler (forall x . m x -> IO x)

runHandler :: Handler m -> ResourceC m a -> IO a
runHandler h@(Handler handler) = handler . runReader h . runResourceC

instance (Carrier sig m, MonadIO m) =>
      Carrier (Resource :+: sig) (ResourceC m) where
  eff (L (Resource acquire release use k)) = do
    handler <- ResourceC ask
    a <- liftIO (Exc.bracket
      (runHandler handler acquire)
      (runHandler handler . release)
      (runHandler handler . use))
    k a
  eff (R other) = ResourceC (eff (R (handleCoercible other)))

Compare to polysemy:



Shoutouts

My girlfriend Virginie for putting up with me talking about free monads for two months.

Li-Yao Xia for showing me the final encoding of Freer.

Rob Rix for sitting down with me and explaining how the heck fused-effects is so fast.


Thanks for listening!

Questions?

REASONABLY POLYMORPHIC
ARCHIVES