Previously we looked at using IO without side-effects in C# by deferring the execution of side-effects. Rather than immediately performing IO, we wrapped up side-effecting operations in an
IO type and used combinators like
SelectMany to work within that type, so we could use
IO values without having to give up the benefits of pure functions by executing the side-effect.
This is a useful technique, but it has the drawback that the
IO instances assembled with these combinators are opaque – there is no way for us to inspect them and work out what the represent. We know an
IO<String> is some IO operation that will result in a string, but is it
In this post we’ll look at another way of representing side-effecting (and other) operations that addresses this drawback.
The approach used here will work for any type of side-effecting program, but let’s stick with terminal IO as an example. We’ll also use F#, although we could probably do this in any language. It’s a bit easier in Haskell, and a bit more difficult in C#.
This representation combines definition and execution. We can isolate the rest of our program from the effects of this execution by wrapping it in an
IO type, but then we end up with an opaque box of
IO<Unit>. If a function returns an
IO<Unit>, there is no way we can inspect it to find out what it is doing. We can’t distinguish
launchMissiles, except by running them and hoping for the best.
What we’re going to try instead is separating the definition of this program from its execution. By representing programs that do terminal IO with a data type we can use it in different ways; inspecting it to see what it does, running it with a pure interpreter, or executing it and performing the effect it defines.
Representing operations with data
There are two main operations used by our
ReadLine. These operations are chained together in a specific order – we write a prompt, we read some input, we write a greeting based on that input, and then we end the program. Let’s represent these operations and the idea of chaining them together with a
Terminal data type:
WriteLine– takes a
stringto write, and the next
ReadLine– takes a function which, given a
stringread in via an input source, will return the next
Terminalto run. This means the next operation to run after reading a line can depend on the value read.
EndProgram– takes no arguments, so does not specify a next
Terminal. Once we get here our terminal program can have no more operations. It’s done.
We know that any
Terminal program can only do these operations. No confusing
launchMissiles anymore. As we’ll see later, we can also differentiate two
Terminal programs by inspecting their structures.
We can represent our original
helloWorld using the
Terminal data structure:
This is clumsy, but we’ll improve things as we go along. For now let’s fill in the gap between this and our original
helloWorld: executing the program.
We’ve separated the definition of
helloWorld from its execution. Now we can define an interpreter that will execute not just
helloWorld2, but any
This interpreter traverses the given
Terminal, translating each operation to an effect (reading or writing lines), and then recursively calling itself to interpret the next operation in the chain. The recursion stops at
> helloWorld();; Hi, what's your name? World Hello World val it : unit = () > interpretIO helloWorld2;; Hi, what's your name? World Hello World val it : unit = ()
We now have parity with our original program. We’ve split the program’s definition from its execution, giving us a pure, side-effect-free representation of a side-effecting program. But is it worth the increased complexity, the author asked rhetorically?
This split of definition and execution opens up some interesting possibilities. For example, we can interpret this program using a purely functional interpreter which reads from a stack of inputs and produces a list of outputs. We can use this for testing, including as a means to differentiate
We can also write other interpreters, say one that pretty prints a program so we can see exactly what an instance of
Terminal is doing for certain inputs.
The benefits of this separation don’t stop at terminal IO. We could model database operations like this, and have different interpreters to perform those operations against SQL Server, RavenDB, an in-memory datastore and the filesystem. The program is the definition, how we interpret it is up to us. 1
Our current implementation suffers from one big problem; we can’t combine
Terminal programs. We have to define a full
Terminal program upfront, as each operation also defines what the next operation is going to be. Speaking of which, assembling programs that are more complex than
helloWorld2 is going to get very messy.
For this separation of definition and execution to be really useful we need to be able to compose
Terminal programs so that it’s easy to assemble them.
Separating the recursion from the definition of operations
There first step towards composing these operations is removing the need for each operation to specify the next operation. We still need to be able to chain together operations, but we’ll separate this job out into another type. This will give us two data types: one defining the available operations, and another to handle the recursive part of the old
Terminal data type:
We now have a funny looking
WriteLine, for example, takes the
string to write, but also a value of some generic type
'a instead of the next
Terminal operation to execute. This generic parameter lets us define the
FreeTerm type which we can use to chain
Terminal operations together using the
FreeTerm of Terminal<FreeTerm<'a>> constructor, or to end the recursive definition using the
Pure of 'a constructor.
Using these two types, our program becomes:
We’ll also need to update both our interpreters to match
FreeTerm instead of
Terminal. For example, the side-effecting interpreter becomes:
Now we can define some general functions to help us update and combine these types, and from there build some helper functions to give us a much nicer way of defining our
Terminal IO programs.
The first function we need is
mapTerm, which will let us transform a
Terminal<'a> into a
Terminal<'b> if we have a way to convert
mapTerm function lets us define
bind to chain together
FreeTerm values, and
liftF to take a
Terminal<'a> operation and wrap it in the
We can use these as the basis for some combinators to help us express our terminal IO programs:
This gives us quite a nice mini DSL for defining pure terminal IO programs.
Computation expression syntax
I’m quite happy with
helloWorld4, but we can also use computation expressions to get what is possibly a more familiar-looking syntax:
Much of the work we did to define
FreeTerm and the relevant combinators can be eliminated by using a more general type called
Free. Rather than being tied to a specific type like
Terminal, it can be generalised to any type that supports a
We can see this for ourselves by replacing “Term” in our
FreeTerm definition with “X”; the code works fine with any type
X provided there is a
mapX defined for it. The rest of the code can remain unchanged.2
I’m not sure how to express the more general form in F#, but the fact it exists means defining a specific
FreeX type for each
X is quite a fast and mechanical process.
Freefor all types we can map over for, well, free. The full
helloWorldexample written in Haskell is available here.
We can get a pure representation of any side-effecty program (not just terminal IO) by defining a type for the primitive operations required for the program and using the
Free type and related functions to combine these operations into programs, all without side-effects. We then separately define the execution of these programs in one or more interpreters.
- We can limit the expressible programs of a specific type to a set of known operations, so we can immediately tell their potential and limitations just from the types (compared with general IO which could attempt anything).
- We can distinguish between two programs of the same type.
- We can run a single program in different ways, so we can run it with side-effects (or translate it to
IO), in a pure way for testing or differentiation, or in any other way we need.
- Why free monads matter, Gabriel Gonzalez
- Purify code using free monads, Gabriel Gonzalez
- Purely Functional I/O in Scala [PDF slides], Rúnar Óli Bjarnason
- Free: Intepreters and Little Languages [HTML slides], Mark Hibberd
I’m not sure just how far the potential for multiple interpreters for a single type can be pushed. Could we have an interpreter to translate
Terminalprograms to other platforms? Or have interpreters that optimise programs, batching certain operations to produce a new, more efficient program?↩
bindin terms of
map, and provides a
Pureor unit constructor, it gives us a monad for any functor (type that supports
map). Philip J-F explains the general form wonderfully in his answer to “What are free monads?” on StackOverflow.↩