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 Select, Then and 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 readLine, or launchMissilesAndShowStatus?

In this post we’ll look at another way of representing side-effecting (and other) operations that addresses this drawback.

Motivation

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

let helloWorld() =
    Console.WriteLine "Hi, what's your name?"
    let name = Console.ReadLine()
    Console.WriteLine ("Hello " + name)

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 helloWorld from 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 helloWorld program, WriteLine and 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:

type Terminal =
    | WriteLine of string * Terminal
    | ReadLine of (string -> Terminal)
    | EndProgram

• WriteLine – takes a string to write, and the next Terminal to run.
• ReadLine – takes a function which, given a string read in via an input source, will return the next Terminal to 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 helloWorld and 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:

let helloWorld2 : Terminal =
    WriteLine ("Hi, what's your name?",
        ReadLine (fun name ->
            WriteLine ("Hello " + name, EndProgram)))

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.

Interpreting operations

We’ve separated the definition of helloWorld from its execution. Now we can define an interpreter that will execute not just helloWorld2, but any Terminal program.

let rec interpretIO (term:Terminal) : unit =
    match term with
        | WriteLine (s, next) -> Console.WriteLine s; interpretIO next
        | ReadLine f          ->
            let read = Console.ReadLine()
            interpretIO (f read)
        | EndProgram -> ()

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

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

Pure interpreters

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

let interpretPure (input:string Stack) (term:Terminal) : string list =
    let rec step i o t =
        match t with
            | WriteLine (s, next) -> step i (s :: o) next
            | ReadLine f          ->
                let (line, i') = pop i
                let next = f (line |?? "")
                step i' o next
            | EndProgram -> List.rev o
    step input [] term
(* fsi:
    > interpretPure (Stack ["World"]) helloWorld2;;
    val it : string list = ["Hi, what's your name?"; "Hello World"]
*)

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

Composing Terminal programs

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:

type Terminal<'a> =
    | WriteLine of string  * 'a
    | ReadLine of (string -> 'a)
type FreeTerm<'a> =
    | Pure of 'a
    | FreeTerm of Terminal<FreeTerm<'a>>

We now have a funny looking Terminal definition. 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:

let helloWorld3 =
    FreeTerm (WriteLine ("Hi, what's your name?",
                FreeTerm (ReadLine (fun name ->
                    FreeTerm (WriteLine (("Hello " + name), Pure ()))))))

We’ll also need to update both our interpreters to match FreeTerm instead of Terminal. For example, the side-effecting interpreter becomes:

let rec interpretIO (term:FreeTerm<'a>) : 'a =
    match term with
        | FreeTerm (WriteLine (s, next)) -> Console.WriteLine s; interpretIO next
        | FreeTerm (ReadLine f) ->
            let read = Console.ReadLine()
            interpretIO (f read)
        | Pure a -> a

Combining programs

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 'a to 'b.

let mapTerm (f : 'a -> 'b) (term : Terminal<'a>) : Terminal<'b> =
    match term with
        | WriteLine (s, value) -> WriteLine (s, f value)
        | ReadLine fn          -> ReadLine (f << fn)

This mapTerm function lets us define bind to chain together FreeTerm values, and liftF to take a Terminal<'a> operation and wrap it in the FreeTerm<'a> type:

let rec bind (f : 'a -> FreeTerm<'b>) (term : FreeTerm<'a>) : FreeTerm<'b> =
    match term with
        | Pure value -> f value
        | FreeTerm t -> FreeTerm (mapTerm (bind f) t)

let liftF (term:Terminal<'a>) : FreeTerm<'a> =
    FreeTerm (mapTerm Pure term)

We can use these as the basis for some combinators to help us express our terminal IO programs:

let (>>=) = fun term f -> bind f term
let (>>.) = fun t1 t2 -> t1 >>= fun _ -> t2
let writeLine s : FreeTerm<unit> = liftF (WriteLine (s, ()))
let readLine : FreeTerm<string> = liftF (ReadLine id)

let helloWorld4 : FreeTerm<unit> =
    writeLine "Hi, what's your name?" >>.
    readLine >>= fun name ->
    writeLine ("Hello " + name)

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:

type TermBuilder() =
    member x.Bind(term, f) = bind f term
    member x.Return(value) = Pure value
    member x.Combine(term1, term2) = term1 >>. term2
    member x.Zero() = Pure ()
    member x.Delay(f) = f()
let termIO = new TermBuilder()

let helloWorld5 = termIO {
    do! writeLine "Hi, what's your name?"
    let! name = readLine
    do! writeLine ("Hello " + name)
}

Generalising

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

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

type FreeX<'a> = Pure of 'a | Free of X<FreeX<'a>>

let rec bind (f : 'a -> FreeX<'b>) (term : FreeX<'a>) : FreeX<'b> =
    match term with
        | Pure value -> f value
        | Free t -> Free (mapX (bind f) t)

let liftF (term : X<'a>) : FreeX<'a> = Free (mapX Pure term)

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.

Conclusion

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.

In addition to the normal benefits of purity, this separation of a program’s definition from its execution gives us some big advantages over the deferred execution approach to IO:

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

Further reading

• 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