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