Explaining the Prompt monad with a clearer representation

The MonadPrompt package is tricky to understand, as it uses a continuation-based representation. This post explains the Prompt monad with a clearer (though less efficient) representation.

Introduction to Prompt

When programming in Haskell, you want to keep code as pure as possible. This may be dogmatic, but it's valuable, and doesn't come automatically. Consider a simple chat server, where the code to handle a client has type:

serve :: ServerEnv -> ClientInfo -> IO ()

Implementing serve, and using it correctly, can be quite daunting, as several factors come into play:

• Concurrency - When the client sends us a message, we have to notify all the other server threads. When someone else sends us a message, we have to be notified.

• Exception safety - When the connection dies, we have to remember to remove our client's entry from the server's list of clients. If another thread might kill this one (e.g. a user connects from somewhere else), we have to make sure that we are prepared to receive an exception at any point.

• Windows - GHC currently does not have good IO support on Windows. If our server is running on Windows, and a client connection hangs, using killThread on the thread blocked on IO will not kill it. Quite the opposite: the thread calling killThread will block, too!

All of these problems are IO-related. Now consider a simpler example, a web server whose main function is:

serve :: Request -> Response

This is much easier to deal with. When implementing serve, we don't have to worry about concurrency, exception safety, or Windows. When calling serve, we don't have to worry about it hanging due to a bad network connection ¹.

But what if serve needs to read a file from disk?

The idea behind the Prompt monad is to have a pure function return an action it would like the caller to perform. To illustrate the concept, let's extend serve so it can ask to download a file:

serve :: Request -> Prompt

data Prompt = ReadFile FilePath (String -> Prompt)
            | Answer Response

Now serve is allowed to "perform" a carefully-chosen set of IO actions, and the caller has full control over how it happens.

The Prompt monad

A Prompt monad is described in The Monad.Reader Issue 15, and implemented in the MonadPrompt package. It handles the plumbing for us, and lets us define a type for requests. Each request may have a different return type, so we'll want to define our request type as a GADT:

data Request a where
    GetLine  :: Request String
    GetChar  :: Request Char
    PutStrLn :: String -> Request ()
    Print    :: Show a => a -> Request ()

If you are not familiar with GADTs, see the Monad.Reader article for more information.

Here's one possible implementation of the Prompt monad:

data Prompt p r
    = forall a. Ask (p a) (a -> Prompt p r)
    | Answer r

instance Monad (Prompt p) where
    return              = Answer
    Ask req cont >>= k  = Ask req (\ans -> cont ans >>= k)
    Answer x >>= k      = k x

prompt :: p a -> Prompt p a
prompt req = Ask req Answer

runPromptM :: Monad m => (forall a. p a -> m a) -> Prompt p r -> m r
runPromptM perform (Ask req cont) = perform req
                                >>= runPromptM perform . cont
runPromptM _       (Answer r)     = return r

A Prompt p r computation either has a value r, or needs some action p a to be performed before it can continue:

This is in fact the original formulation of Prompt. Unfortunately, left recursion of >>= takes quadratic time to evaluate (thanks for pointing this out, ryani).

Let's compare the formulation above to MonadPrompt's runPromptC function, and see how we'd implement it in terms of Ask and Answer:

runPromptC :: (r -> b)
           -> (forall a . p a -> (a -> b) -> b)
           -> Prompt p r
           -> b
runPromptC onAnswer onAsk p =
    case p of
        Ask req cont -> onAsk req $ runPromptC onAnswer onAsk . cont
        Answer r     -> onAnswer r

The interesting wrinkle is that we embed a recursive call inside of the continuation passed to onAsk. Thus, the caller does not have to do its own recursion. This simplifies the implementation of runPromptM, for example:

runPromptM :: Monad m => (forall a . p a -> m a) -> Prompt p r -> m r
runPromptM prm = runPromptC return (\p cont -> prm p >>= cont)

So while MonadPrompt's continuation-based representation may be harder to understand at first, it is more efficient, and perhaps even easier to use.

Takeaways:

• MonadPrompt uses a continuation-based representation to avoid a performance issue. The Ask/Answer formulation, however, may be easier to understand.

• A library implementing a network protocol should export a pure API (perhaps in addition to impure convenience functions), so the user can deal with concurrency, exception safety, and Windows on their own terms.

---

1. Actually, evaluating serve :: Request -> Response might hang if the Request contains lazy IO. In this case, it's not serve's fault, but the fault of whatever is producing the data.↩