After finishing my master’s degree, I applied to several companies I was interested in. During one of the selection processes, the interviewer asked me to do the following exercise:
“Write a stack-based interpreted language (byte code) that includes: literals, arithmetic operations, variables, and control flow primitives. As a bonus, add asynchronous primitives such as fork and await.”
Fortunately, I was already familiar with the assignment because I implemented a statically typed programming language a year ago. Consequently, I decided to take this as a chance and do something different than the rest of the candidates. Spoiler: free monads!
Free monads
The concept of free monad comes from the field of category theory (CT). The formal definition requires a strong background in CT. So, to keep this pragmatic, we are going to consider the following definition:
For any functor $f$, there exists a uniquely determined monad called the free monad of the functor $f$.
Probably this definition is still too general, so let’s see how this is translated into Haskell. In particular, we are going to base our work on the encoding of free monads of the haskell package free by Edward Kmett et al. The definition is as follows:
1 |
|
Free f
is simply a stack of layers f
on top of a value a
.
The interesting part about Free f
is that Free f
is a monad as long as f
is a functor.
1 |
|
This will allow us to compose free actions by embedding new layers on the bottom of the stack of layers, which is essential to model domain specific languages.
In practise, the user builds a free monad stacking layers of their domain specific language modelled as a functor. Later, it executes iter
(or its corresponding applicative and monadic version) to interpret and collapse each layer into a single (effectful) value.
1 |
|
In the next section, we will see how to put that into practise.
Solving the assignment
When modeling an embedded domain specific language (eDSL) using free monads, you usually divide the problem in two parts:
- Define your language.
- Define the interpreter for your language.
Defining our eDSL
First, we need to define our language. We are free to model any kind of language, but the type that represents our language must be a functor. Otherwise, our language will not be able to be composed using bind (=<<)
.
Here is the sum type representing our byte code language:
1 |
|
Lit
instruction to instantiate literals (integer and boolean values).Load
/Write
instructions to load and write variables, respectively.BinaryOp
instruction to apply binary operations (+, *, <) on the top values of the stack.Loop
instruction to execute a set of instructions iteratively based on a certain condition.Ret
instruction to stop the program and return the value on top of the stack.Fork
/Await
instructions to start and await an asynchronous program, respectively.NewChan
/Send
/Recv
instructions to create a new asynchronous channel, send and receive a value through the channel, respectively. This channel allow to independent asynchronous programs to communicate.
The careful reader may have notice that our type ByteCodeF
has a type parameter next :: Type
. This type parameter is required for ByteCodeF
to be a functor. We can think of next
as the next instruction in our program. In fact, when we interpret the ByteCode
free monad, next will be replaced by the (evaluated) next instruction of our program.
Next, for each constructor of our ByteCodeF
, we need a function that lifts ByteCodeF
into ByteCode
. For example, here is the definition of that function for Lit
:
1 |
|
Implementing this for each constructor is tedious and error prone. This problem can be solved with metaprogramming. In particular, with template haskell (for an introduction to template haskell see my blog post). Fortunately, this is already implemented in Control.Monad.Free.TH.
Therefore, we are going to use makeFree
to automatically derive all these free monadic actions
1 |
|
which generates the following code
1 |
|
The actual signatures use MonadFree which is an mtl-style class that allow us to compose FreeT with other monad transformers. We were able to monomorphize the return value
MonadFree f m => m ~ Free ByteCodeF
thanks to the instanceFunctor f => MonadFree f (Free f)
.
Once we have the basic building blocks of our language, we can start building more complex primitives using monadic composition!
1 |
|
Interpreting our eDSL
Now that we have the building blocks to construct our domain specific programs, it is only remaining to implement an interpreter to evaluate this embedded DSL in our host language Haskell.
The interpreter is usually implemented using iterM:
1 |
|
iterM
allow us to collapse our Free f
into a monadic value m a
by providing a function f (m a) -> m a
(usually called an algebra) that operates on a single layer of our free monad. If you are familiar with recursion schemes, iterm
is a specialization of cataA.
This may sound confusing at first, but it is easier than it looks like. So, let’s see how it would look like in our example. First of all, we need to choose the monadic value m
. For our interpreted language, we choose m ~ Interpreter
1 |
|
where Ctx
is the current context of our program i.e. the state of the stack and the memory registers.
Then, we specialize iterM
to our example
1 |
|
The last step and usually the most difficult one is to implement the algebra of our DSL
1 |
|
Finally, we combine iterM
and algebra
to obtain
1 |
|
which allow us to interpret our embedded language in our host language. The result of interpret
can be composed with other effectful programs and it can also be evaluated using runByteCode
:
1 |
|
All together
So far, we have built the following components:
- An embedded stack-based language in Haskell with primitives like:
lit
,load
,write
,loop
… - An interpreter for that language:
interpret
andrunByteCode
.
Now that we have all the ingredients to create embedded stack-based programs and interpret them, we can put this into practise.
1 |
|
The following program
creates two asynchronous tasks that after a period of time, return the integer 1
through an asynchronous channel. The main program waits for these two asynchronous tasks to finish and outputs the sum of the results of the asynchronous tasks.
The source code from the examples can be found here.
Conclusion
In this post, we have introduced free monads and how they can be used to implement embedded domain specific languages. In particular, we have seen how to embed a stack-based language in Haskell. To see other examples of domain specific languages, we refer the reader to the examples of the free package.
This post only covered a half of the free package. In the next post of this series, we’ll explore the other half: church encoding, applicative free, cofree…