#freemonads

Free Monads are a powerful abstraction for modeling operations in your program. While there are many articles about free monads, there are relatively few about using free monads.

At my current work we have a large Free Monad that abstracts various actions one might do against data in our system. We also have three interpreters: a pure interpreter for unit testing, a psql-backend interpreter for the back end of our data service, and a http-client interpreter for clients using the data service over HTTP.

One difficulty I’ve encountered several times has been how to properly model errors and exceptions. I’m not talking about the much-adored EitherT vs ErrorT vs ExceptT debate, but rather differentiating between:

Semantic Errors: attempting to perform an action that doesn’t make sense. For example, adding an edge between non-existent nodes in your graph.

Interpreter Errors: attempting to do something illegal within your interpreter. For example, submitting a malformed sql query which causes an error.

Runtime Errors: your code is correct but the outside world is not. For example, the database goes down causing an exception in your connection pool.

In this post I want to discuss a general approach to modeling and distinguishing these three classes of errors. I will then show my own approach that, combined with the Type Famillies extension I wrote about earlier, presents a simple and type-safe solution.

Worlds of Error

Semantic Errors

Interpreter Errors

Runtime Errors

Using Type Families to Encode Errors

Worlds of Error

{-# LANGUAGE DataKinds #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE GADTs #-} {-# LANGUAGE TypeFamilies #-} module FreeMonadErrors where import Control.Monad.Catch import Control.Monad.Error import Control.Monad.Free (Free(Free, Pure)) import Control.Monad.Trans.Either (EitherT)

While cache-invalidation and naming things are the pride of hard problems, proper error handling is a close third. When to throw? Where to catch? What errors are kept pure? This problem is exasberated in the context of Free Monads because we have a clean separation between program and interpreter.

To properly model errors in free monads, we first recognize that one advantage of Free Monads is the separation between program, interpreter, and outside world:

+--------------------------+ +--------------------+ +----------+ | | ---> | | <-> | | | Programs described | ---> | interpreter(s) | <-> | outside | | by our Free Monad | ---> | | <-> | world | | | ---> | | <-> | | +--------------------------+ +--------------------+ +----------+

Next we recognize that “errors” or “bad behaviour” may manifest in each world, reducing our problem to:

Identifying errors that stay within their respective zone and how they are handled

Identifying errors that are propogated into the interpreter

Identifying errors that are propogated to the outside world

Semantic Errors

Semantic errors are errors that are expected outcomes of your problem domain. Some examples of semantic errors:

fetching a User with id = 324, but that user does not exist.

adding an edge between non-existent nodes in your graph.

For semantic errors, you want the person writing the program within the Free Monad to handle this kind of error. These errors should not propogate into the interpreter. Often this involves ensuring the return type of a value in your algebra encodes the error. For example:

-- a simple user data User = User { userId :: Int, userName :: String } deriving Eq -- a functor describe the algebra of our programs. data AlgebraF1 a = CreateUser1 Int String (User -> a) | GetUser1 Int (Either String User -> a) instance Functor AlgebraF1 where fmap f (CreateUser1 i s g) = CreateUser1 i s (f g) fmap f (GetUser1 i g) = GetUser1 i (f g)

As you can see in GetUser1, we’ve ensured that when fetching a user, the program’s author must handle the case where a user with an id may not exist (via the Left part of Either String User). An example program may look like:

-- check if the user with the given id has the name. fooProgram :: Int -> String -> Free AlgebraF1 (Either String Bool) fooProgram fooUserId name = do user <- Free (GetUser1 fooUserId Pure) return $ fmap ((==) name userName) user

Semantic errors should not propogate into the interpreter. This makes sense until you consider the fact that you may want to log such errors. To which I respond: logging should be part of your Free Monad transformer stack!

Interpreter Errors

Errors in the interpreter arise when your interpreter does not behave correctly. For example, your interpreter may create inappropriate SQL queries or emit bad C programs. Ultimately, there is not much you can do with these types of errors aside from encoding as much as possible in your types, verifying the correctness of your interpreter (via encoding laws or equational reasoning), and testing. It’s likely errors of this form will not manifest themselves until runtime, as they will immediately be propagated to the outside world and reflected back at us rather harshly.

In some cases interpreter errors can be identified by catching the right runtime error. We’ll discuss this later.

Runtime / Outside World Errors

Runtime errors are bound to manifest. Database connections are dropped or errors propogated from the interpreter are reflected back at us. A user writing a program within a Free Monad should not be concerned with these errors. They will be handled (or thrown) within the interpreter, usually via throwM or catch, and any program running an interpreter against a free monad will need to handle exceptions that may be raised.

-- foo interpreter fooInterpreter :: (MonadError String m, MonadCatch m) => Free AlgebraF1 a -> m a fooInterpreter _ = throwError "I'm a runtime error, can you catch me?"

Using Type Families to Encode Errors

Thus far we’ve discussed various scenarios where semantic, interpreter, and runtime errors can occur. How can we model these?

If we use the approach of encoding actions within our Free Monad as a universe of types from my previous blog post Type Families Make Life and Free Monads Simpler, then there exists a nice encoding of semantic, interpreter, and runtime errors.

First, let us describe our Free Monad:

-- our universe of actions data Algebra = CreateUser | GetUser -- singleton data SAlgebra (a :: Algebra) :: * where SCreateUser :: SAlgebra 'CreateUser SGetUser :: SAlgebra 'GetUser -- type family representing data required to produce action. type family InputData (a :: Algebra) :: * where InputData 'CreateUser = (Int, String) InputData 'GetUser = Int

Semantic Errors

We want to encode semantic errors into our OutputData type family (which we’ve not defined yet) so that errors are handled within our free monad (via an action’s return type). When we encounter an error, we will want to know what action in our algebra caused the error and in which world (semantic, interpreter, runtime) we are in.

-- a universe of errors data ErrorUniverse = Semantic | Interpreter | Runtime -- singleton encoding of our error universe data SErrorUniverse (e :: ErrorUniverse) :: * where SSemantic :: SErrorUniverse 'Semantic SInterpreter :: SErrorUniverse 'Interpreter SRuntime :: SErrorUniverse 'Runtime -- | our custom error type, tagged by an error universe and carrying runtime information -- about an action. data AlgebraError (e :: ErrorUniverse) :: * where AlgebraError :: Show (InputData a) -- Show instance so we can log => SErrorUniverse e -- error singletone -> SAlgebra a -- the action causing the error -> InputData a -- the input data supplied to the action (for logging) -> AlgebraError e

Note that our AlgebraError encodes all the information related to an action in our algebra (the specific action via SAlgebra and its input data via InputData a (handy for logging)). With AlgebraError defined, we are now ready to define the OutputData type family.

-- output data for our free monad type family OutputData (a :: Algebra) :: * where OutputData 'CreateUser = User OutputData 'GetUser = Either (AlgebraError 'Semantic) User -- our Algebra as a functor data AlgebraF next :: * where AlgebraF :: SAlgebra a -> InputData a -> (OutputData a -> next) -> AlgebraF next -- Functor instance instance Functor AlgebraF where fmap f (AlgebraF a i o) = AlgebraF a i (f o) -- our free monad type FreeAlgebra a = Free AlgebraF a -- some smart constructors to make our life easier createUser :: (Int, String) -> Free AlgebraF User createUser d = Free (AlgebraF SCreateUser d Pure) getUser :: Int -> Free AlgebraF (Either (AlgebraError 'Semantic) User) getUser i = Free (AlgebraF SGetUser i Pure)

Let’s take note of a few things.

There is no semantic error for the CreateUser action. This is because we assume, semantically, that if you provide the correct data you will create a User. If any errors occur at this point they must be interpreter or runtime errors.

The GetUser action returns Either (AlgebraError 'Semantic) User, indicating that when “getting” a user, we may encounter an error. In this case, the error we’ll encounter is simply that the user does not exist.

It may be the case that there are multiple semantic errors for a single action. In this scenario, you can simply add a sum type to InputData a to encompass various types of error (there are other ways to do this as well).

With the above we are able to write programs in our Free monad and handle error. For example, here is one that creates a user, fetches the user, and checks that they’re the same:

createAndCheck :: Free AlgebraF (Either (AlgebraError 'Semantic) Bool) createAndCheck = do newUser@(User newUserId _) <- createUser (37,"Heitkotter") fetchedUser <- getUser newUserId return ( fmap (== newUser) fetchedUser )

Within createAndCheck the client was forced to handle the case where one might fetch a user that does not exist (a semantic error).

Runtime Errors

Where do runtime errors pop-up? In the interpreter! I won’t write an interpreter within this blog post, but I will state an example type signature:

-- free monad interpreter used at megacorp. megacorpInterpreter :: Free AlgebraF a -> EitherT (AlgebraError 'Runtime) IO a megacorpInterpreter = error "to be defined" -- an alternative interpreter using mtl megacorpMtlInterpreter :: MonadError (AlgebraError 'Runtime) m => Free AlgebraF a -> m a megacorpMtlInterpreter = error "to be defined"

When the interpreter is run, errors encountered here are reflected in the type (via EitherT or MonadError in the above examples), therefore the client running the interpreter needs to handle these in whatever way makes sense for the program.

Translating Semantic and Interpreter Errors to Runtime Errors

You can imagine that a small program in our free monad may return a value with the type Free AlgebraF (Either (AlgebraError 'Semantic) User. When we run our megacorpInterpreter against this program, we’ll get EitherT (AlgebraError 'Runtime) IO a. So, where did our semantic error go? Well, in your interpreter, there should be some code that translates these semantic errors into a meaningful type within the interpreter. For example, one might perform case analysis on the Either and responds to it (either by logging or generating an interpreter-specific error (e.g. an HTTP error code like 400 or a retry for an http client)).

You may also have the opportunity to catch certain interpreter errors. For example, the postgresql-simple client has an error type for poorly formed sql queries. You may be able to catch this and translate it into a runtime error within the interpreter.

Conclusion

When using free monads it’s a good idea to clearly separate various kinds of errors. In this blog post we identified three kinds of errors: semantic, interpreter, and runtime. Semantic errors can be handled by the user writing programs in your Free Monad and should reference domain-specific nuances. Runtime errors are handled in your interpreter. Interpreter errors manifest at runtime but are interpreter-implementation specific, and therefore they should be caught and translated to runtime errors.

Additionally, we showed that by representing actions in our free monad by an algebra and by creating a universe of error types we were able to reflect action- and error-specific types in our free monad and interpreter.