posts `for_` publish

Forking and ContT (I)


Introduction

This is the first article in a series about continuations, forking, and monad transformers. Next article.

Motivation

When using StateT or ReaderT over IO, we sometimes would like to fork and still remain in this “monadic context”, but alas:

For StateT this makes a good deal of sense - what does “forking” mean for the state? But that leaves two questions: 1) What about ReaderT? For that, the semantics should be unproblematic; 2) What if we do not even want to continue the stateful computation in main? I.e. we want to “move” the StateT Int IO instead of forking it.

Is this possible without any hassle of manually tracking state/environment and passing it between threads?

Continuations are a well-known tool for turning your ordinary control flow into headache-inducing control rapids. They can be seen as the “goto” of functional programming. For some background knowledge, I can recommend the following sources:

Considering just implementations in haskell, we can find the following monads:

  1. newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r } from the transformers package;
  2. newtype CPS3 m a = CPS3 { unCPS3 :: (a -> m Void) -> m Void } mentioned in [6];
  3. newtype Codensity m a = Codensity { runCodensity :: forall b. (a -> m b) -> m b } e.g. in the kan-extensions package.
  4. newtype LogicT m a = LogicT { unLogicT :: forall r. (a -> m r -> m r) -> m r -> m r } from the logict package and the underlying paper [2].
  5. data FFree f a where Pure :: a -> FFree f a; Impure :: f x -> (x -> FFree f a) -> FFree f a from the “Freer Monads, More Extensible Effects” paper [8]

This article will focus on the deterministic, undelimited, but forkable continuations, and for now we will stick with the simplest/most permissive definition 1).

Forking is in haskell represented by the primitive forkIO :: IO () -> IO ThreadId operation. In the context of continuations however we can come up with more than one notion:

These are not new inventions, for example this thread on reddit [3] implements at least the first two (their implementation is different, but intended semantics are same).

Being essentially the equivalent of forkIO, the first of these is not too interesting. Instead, we will have a closer look at moveToNewThread.

The moveToNewThread Primitive

To clarify, some equivalences

reminder: evalContT :: Monad m => ContT r m r -> m r, i.e. the type of the whole expression must be IO ()

This last example shows a bit how moveToNewThread “flattens” the notation of moving an execution to a different thread (similarly to how e.g. EitherT flattens a series of actions that return Eithers).

Below are some use-cases for this expressiveness. However, there is at least one more curious property to this, having to do with transformer stacks and lifting. For this, we look back to plain forkIO and how it interacts with lift (we will use StateT Int as some simple, specific transformer):

Where the argument unfortunately still is IO () and not StateT Int IO (), so this does not work too well. For forkCont1, the base monad is ContT () IO, but the problem is essentially the same: forking “loses the state”. However:

Isn’t that neat? If the base of our stack is ContT () IO, we can lift “forks” (and “moves”). This gives some expressiveness to transformer stacks I was not aware of previously. So while in general ContT can easily become more confusing than useful, this expressiveness is sufficient motivation to consider this a bit more closely. So how does this behave?

Note how we have to manually carry over the intermediate state s' to the forked thread when using forkIO, while we only need one top-level evalStateT with moveToNewThread.

Applications, in ascending complexity:

First application: Blocking, but not

This is a straight-forward translation of using callbacks to cope with blocking operations: We can conditionally fork if we are about to block the current thread. For example, a new version of readMVar:

So while we still block, we don’t block the “initial” thread (the one calling evalContT or similar). In an event processing loop, we might write something like

where the MVar will never block this whole loop, and we only fork when it is necessary. However there is a downside: If we use readMVarMoving multiple times, we create a new thread for each time we block. We could just fork once and then block without worrying about blocking the main loop. Which of these two approaches ultimately results in less forks globally depends on the rate at which the tryReadMVar succeeds (i.e. on contention of our resources in general). Plus, threads are cheap in haskell, so the gains might be irrelevant either way.

I am not aware of any library that provides such versions of common blocking functions (yet).

Second application: Moving between Threads

We can create worker threads that evaluate continuations passed to them, e.g. using

So moveToProcessor behaves like moveToNewThread but instead of a fresh thread, in moves to a specific worker thread. This might come in handy if we have thread-specific resources (FFI stuff). We might also use this construct as a synchronization/critical section/resource ownership mechanism, although I have a hard time coming up with examples where this would have advantages over simpler approaches to locking resources. Maybe something with exception-handling around the resources that “belong” to this worker thread? But exception-handling deserves its own, large chapter (read: its own article).

Third Application: Moving with Transformer-Stacks

(some liftIOs omitted)

will output

from main thread: our current state is 1
from new  thread: our current state is 3

Fourth Application: Forking with Transformer-Stacks

We can also truly fork (can you guess how this behaves?) (liftIOs omitted)

yeah?

Solution: It prints 1 after 1 second and 2 after 2 seconds. I.e. the state indeed splits, somewhat in the fashion of non-determinism monads such as LogicT. This may be undesired and become confusing quickly, so it might make sense to restrict the usage around this and either:

  1. Only use this around “harmless” stacks; e.g. ReaderT is fine;
  2. Don’t use the “true forking” functions, but permit those that call the continuation exactly once (moveToNewThread, moveToProcessor), which are still completely fine.

Fifth Application: Stateful Computations in Worker-Threads

This is essentially a combination of applications two and three. (liftIOs omitted)

from main thread: our current state is 1
from worker thread: our current state is 3

The interesting bit about this is that: The worker thread exposes and runs a plain ContT () IO () interface, but we still are able to pass it a stateful computation via lifting. And there is nothing stopping us from expanding on this some more:

Generalizations and Conclusion

We can apply at least two generalizations. Firstly the typical “mtl” approach, using this class:

Secondly we can generalize over forkIO. Together, we get:

Now moveToNewThread can be implemented as moveContWith (void . forkIO).

To answer the motivation:

Summary

is fixed using

And:

  • forkCont2With and moveContWith fork/move arbitrary monad stacks with the ContT () IO base.
  • Can fork state, for good or worse. That is, we accidentally got an answer to the “what does forking mean for state” question.
  • We somewhat have to assume that we are working with undelimited continuations, i.e. mixing of fork/move and callCC/resetT probably can become rather confusing (to be discussed).
  • Exceptions will blow up the current thread only. An evalContT wrapped in some catch will actually not catch an exception thrown after a moveToNewThread (to be discussed).
  • The “host” of continuations (in the simplest case forkIO) requires only the power of running plain IO (), even when our “client” monad stack contains arbitrary transformers. The host is independent of those transformers (and is blissfully unaware of their internal state).
  • As a trivial consequence, a host can run a series of continuations that have different monads (stacks).

Outlook

(or should I say: To be Continued With:)

The next article in this series will introduce an implementation for withLifted.

Addenda

forkSequential

moveToNewThread and forkCont2 share certain functionality, so a natural question is if we can express one in terms of the other. In that direction, we define:

and with that

And we can also go from 2 to n:

What about the ContT transformer?

How does t (ContT () IO) fare versus ContT () (t IO)? The latter seems nicer in that it does not force us to switch the base of our transformer stack. Unfortunately, this does not work. Just consider how we would have to define our simplest forking function:

Replacing m with t IO does not help:

withLifted

The riddle consists of the following signature:

We are looking for an implementation so that

prints

acquire a
acquire b
release b
release a
1

That is: We want to lift a “with-function” to an arbitrary transformer stack if the base monad is ContT () IO. If you take into account that the “host” only needs to “speak IO”, and the challenge here is to pass a monad stack through an “IO gate”, this is an interesting but solvable riddle.

Hint: You don’t even need forkIO, but you need an MVar.

References

Posted by Lennart Spitzner on 2018-09-09. Feedback to (blog at thisdomain) welcome!
Tags: . Source.