Free monads are quite a hot topic amongst the Haskell community at the moment. With a category-theoretic derivation, getting to grips with them can be rather daunting, and I have found it difficult to understand the engineering benefit they introduce. However, having finally come to grips with the fundamentals of free monads, I thought I’d write a brief introduction in my own terms, focussing on the benefit when designing interpreters and domain specific languages (DSLs). Certainly, the information described below can be found elsewhere, such as this Stack Exchange question or Gabriel Gonzalez’ excellent blog post.
The free monad interpreter pattern allows you to generate a DSL program as pure data with do-notation, entirely separate from the interpreter which runs it. Indeed, you could construct the DSL and generate DSL programs without any implementation of the semantics. Traditionally, your DSL would be constructed from monadic functions hiding the underlying interpreter, with these functions implementing the interpreter logic. For example, a DSL for a stack-based calculator might implement functionality to push an element to the stack as a function push :: Double -> State [Double] (). Our free monad pattern separates the specification from the implementation, so our calculator program would be represented first-class, which can be passed both to the ‘true’ interpreter, as well as any other we wish to construct.
Let’s stick with the example of constructing a DSL for a stack-based calculator. To begin with, we need to construct a functor representing the various operations we can perform.
data Op next
= Push Double next -- ^ Push element to the stack
| Pop (Maybe Double -> next) -- ^ Pop element and return it, if it exists
| Flip next -- ^ Flip top two element of stack, if they exist
| Add next -- ^ Add top two elements, if they exist
| Subtract next
| Multiply next
| Divide next
| End -- ^ Terminate program
deriving (Functor)
Our calculator programs will be able to push and pop elements from the stack and flip, add, subtract, multiply and divide the top two elements, if they exist. This definition may seem slightly strange: the datatype has a type parameter next which is included in each non-final instruction. In this way, each operation holds the following instructions in the program. The End constructor is special in that no instructions may follow it. Pop is special too: its field is a function, indicating that Maybe Double will be returned as a value in the context of the program (see below).
As I mentioned, Op needs to be a functor, which we derive automatically with the DeriveFunctor pragma. This will always be possible with a declaration of this style because there is exactly one way to define a valid functor instance.
As it stands, programs of different lengths will have different types, due to the type parameter next. For example, the program End has type Op next (next is a free type parameter here) while Push 4 (Push 5 (Add End)) has type Op (Op (Op (Op next))). Note that these look suspiciously like lists, the elements of which are Op‘s constructors. The free monad of a functor encodes this list-like representation while also providing a way to lift a value to the monadic context. For any functor f, the free monad Free f is the datatype data Free f a = Pure a | Free (f (Free f a)). Notice the similarity to the definition of list.
Suffice to say, Free f is a monad. I don’t want to dwell on the mathematical significance of Free or its application beyond interpreters: I’d rather focus on how they are used to define DSL programs using do-notation.
-- From Control.Monad.Free
type Program = Free Op
push :: Double -> Program ()
push x
= liftF $ Push x ()
pop :: Program (Maybe Double)
pop
= liftF $ Pop id
flip :: Program ()
flip
= liftF $ Flip ()
add :: Program ()
add
= liftF $ Add ()
subtract :: Program ()
subtract
= liftF $ Subtract ()
multiply :: Program ()
multiply
= liftF $ Multiply ()
divide :: Program ()
divide
= liftF $ Divide ()
end :: forall a. Program a
end
= liftF End
Program is the monad representing our DSL program, and is defined as Free Op (Free is defined in the free package). We need to provide functions to lift each constructor into Program, using liftF. Notice that almost all of the functions are of type Program (), except for pop, which yields the top of the stack as a Maybe Double in the monadic context, and end, whose existential type indicates the end of a program (this requires the RankNTypes language extension). With these, we can start defining some calculator programs. Remember, we’re simply defining data here: we’re haven’t defined an interpreter yet!
-- Compute 2 * 2 + 3 * 3, leaving result on top of stack
prog :: forall a. Program a
prog = do
push 2
push 2
multiply
push 3
push 3
multiply
add
end
pop allows us to read values into the Program context, meaning we can use pure Haskell functions in our programs:
-- Double the top element of the stack.
double :: Program ()
double = do
x <- pop
case x of
Nothing ->
return ()
Just x' ->
push $ x' * 2
Finally, let’s define an interpreter for our DSL, which returns the state of the stack after program execution.
modStack :: (a -> a -> a) -> [a] -> [a]
modStack f (x : x' : xs)
= f x x' : xs
modStack _ xs
= xs
-- The existential type of the parameter forces the program to be
-- terminated with 'end'.
interpret :: (forall a. Program a) -> [Double]
interpret prog
= execState (interpret' prog) []
where
interpret' :: Program a -> State [Double] ()
interpret' (Free (Push x next)) = do
modify (x :)
interpret' next
interpret' (Free (Pop next)) = do
stack do
put $ xs
interpret' $ next (Just x)
[] ->
interpret' $ next Nothing
interpret' (Free (Flip next)) = do
stack
put $ x' : x : xs
_ -> return ()
interpret' next
interpret' (Free (Add next)) = do
modify $ modStack (+)
interpret' next
interpret' (Free (Subtract next)) = do
modify $ modStack (-)
interpret' next
interpret' (Free (Multiply next)) = do
modify $ modStack (*)
interpret' next
interpret' (Free (Divide next)) = do
modify $ modStack (/)
interpret' next
interpret' (Free End)
= return ()
The interpreter logic is very simple: we pattern match against each Op constructor, mutating an underlying list of doubles where necessary, being sure to recurse on the remainder of the program represented by next. interpret' accepts an arbitrary Program a parameter which doesn’t necessarily have to be terminated by end, although we insist on this by wrapping the function in interpret which demands an existential type. This detail is not important here, although may be for more complex interpreters which require resource clean-up once the interpretation has terminated. end could also be automatically appended when interpreting, too.
The beauty of this programming pattern is the separation of concerns: we can freely define a different interpreter which can operate on the same DSL program. It is often very natural to want to define more than one interpreter: in this case, I may want to execute the program, additionally warning the user when illegal pops or flips are made. This is possible because the interpreter logic does not define the embedded language, unlike in the traditional approach, making this a very attractive design pattern for DSL and interpreter construction.
