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 ^{1}.

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.

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.↩

Hi Joey,

ReplyDeleteThe original version of prompt was exactly your concrete representation (with different constructor names), but it has a problem that left recursion of >>= takes quadratic time to evaluate (it's the same as the left-recursion of ++ problem!)

The continuation-based representation came from figuring out what type we need to implement 'ask', '>>=', 'return', and the different use cases of runPrompt, and using that instead.

I think explaining it in terms of this simpler representation is definitely easier, though. Do you mind if I link this post in the documentation?

> I think explaining it in terms of this simpler representation is definitely easier, though. Do you mind if I link this post in the documentation?

DeleteCertainly! I updated the blog post to mention why MonadPrompt uses the continuation-based representation.

Also, here's the original post: http://www.haskell.org/pipermail/haskell-cafe/2007-November/034830.html

ReplyDeleteSo, how to implement all of this?

and the datatype, which is exactly your type.

> data Prompt (p :: * -> *) :: (* -> *) where

> PromptDone :: result -> Prompt p result

> -- a is the type needed to continue the computation

> Prompt :: p a -> (a -> Prompt p result) -> Prompt p result