Free Monads and Defunctionalized Interpreters

A program written against an abstract interface can be read in two ways. It can be executed immediately, in which case the interface’s implementation decides what each call does. Or it can be recorded as a sequence of requests, in which case the program is data, and a separate interpreter decides what the requests mean. The free monad is the construction that makes the second reading available without changing the source of the program: the same do block that would run under IO builds a syntax tree when the monad is the free one.

One layer per request

The starting point is the same fixed-point idea as catamorphisms over functors, applied to a functor whose recursive positions are continuations rather than subterms. For an interface with a single operation, “read a line and continue”, the layer functor is

data TeletypeF r = GetLine (String -> r) | PutLine String r

data Free f a = Pure a | Free (f (Free f a))

Pure is a program that has finished with a value. Free is one request, whose payload includes the continuation: a function from the request’s answer to the rest of the program. GetLine’s payload is a function because the answer is not known until the interpreter supplies it; PutLine’s payload is a plain continuation because the request has no answer.

The monad instance is the whole construction:

instance Functor f => Functor (Free f) where
  fmap g (Pure a)  = Pure (g a)
  fmap g (Free fa) = Free (fmap (fmap g) fa)

instance Functor f => Monad (Free f) where
  return = Pure
  Pure a   >>= k = k a
  Free fa  >>= k = Free (fmap (>>= k) fa)

The Monad equations are the left unit law and substitution into the continuation, and the recursion is the tree walk. >>= does not run anything. It rewrites the tree by composing k onto every leaf, and the Functor instance’s fmap is what pushes the composition through the request’s payload, because Free f is a functor only when f is one, at every depth.

The interpreter is a fold

Because a free monad is a recursive datatype, an interpreter is a catamorphism whose algebra replaces each request constructor with a real operation:

runIO :: Free TeletypeF a -> IO a
runIO (Pure a)              = return a
runIO (Free (PutLine s k))  = putStrLn s >> runIO k
runIO (Free (GetLine k))    = getLine >>= runIO . k

The algebra for PutLine performs the write and recurses into the continuation; the algebra for GetLine performs the read and applies the continuation to the result. A second interpreter with the same type but a different body replays the program against a script, counts the requests, or translates them into another language. The program text does not change.

This is the interpreter pattern with the dispatch made static. In an object-oriented encoding, each request is an object with a method, and the interpreter is a visitor; the set of requests is open for extension and the dispatch is dynamic. In the free-monad encoding, the set of requests is a functor, the interpreter is a fold, and the dispatch is a case analysis the compiler can inline. Adding a request means changing the functor, which is a closed-world operation: the trade is the opposite of the visitor’s.

The same construction is Reynolds’s defunctionalization seen from the other side. A higher-order program has closures; a defunctionalized program replaces each closure with a tag and a record of its free variables, and replaces the call site with a dispatch. A free monad’s request tree is exactly that: each Free node is a tag with its captured payload, and the interpreter is the dispatch. Writing an interpreter in continuation-passing style and then defunctionalizing its continuations is a standard route to this representation, and continuation-passing style is the direct-free version of the same program.

Composition: functor coproducts and the extensibility problem

A program that needs two interfaces, files and logging, needs a functor with both sets of requests. The naive approach is to write a new functor with the union of the constructors, which forces every interpreter to handle both and prevents reuse. Swierstra’s solution is the coproduct of functors:

data (f :+: g) r = InL (f r) | InR (g r)

instance (Functor f, Functor g) => Functor (f :+: g) where
  fmap h (InL x) = InL (fmap h x)
  fmap h (InR y) = InR (fmap h y)

A program’s type is Free (FileF :+: LogF) a, and a request is injected into the coproduct with a type class whose instance is resolved by the type checker. Each interpreter handles one summand and delegates the rest, so a file interpreter can be written once and reused in a program that also logs, provided the outer interpreter dispatches to it. The cost is that every injection is a wrapper constructor, and every dispatch is a nested case analysis whose depth grows with the number of summands.

The depth is the reason the coproduct encoding is not the final answer. With n interfaces, a request sits n constructors deep, and the interpreter’s case analysis is n levels of InL/InR before it reaches the request. The type-level machinery that resolves the injection is also n levels deep, which is where the compile-time cost of the encoding comes from. The freer monad removes both the functor requirement and the nesting by making the request a single GADT that stores the answer type as an existential, so no coproduct wrappers are needed, at the cost of a different and more elaborate type-level encoding.

The quadratic bind

The representation has a performance property that is not visible in the types. >>= as defined walks the entire left-hand tree, because it must compose the continuation onto every leaf. A chain of n binds built left-associatively therefore costs 1 + 2 + ... + n rewrites, which is O(n^2), before the interpreter runs. The same program written with the monad’s do notation is right-nested, and a right-nested chain costs O(n): each >>= only touches the outermost request. This is why do blocks are cheap and a foldl-built chain of binds is not.

The standard fix is a continuation-based representation, in which the tree is built in continuation-passing style and the bind is O(1):

newtype FFree f a = FFree { runFFree :: forall r. (a -> Free f r) -> Free f r }

The forall r is what makes the bind constant time: composing two continuations is function composition, and the tree is materialized only when the interpreter is applied. The representation is the Church encoding of the free monad, and it is the same trick as Church-encoded lists: the operations are cheap and the structure is expensive to inspect. An interpreter that pattern matches on the tree cannot see it at all, so the representation is only usable when the interpreter is also written as a fold over the operations.

What the free monad is not

The name suggests that the construction is the monad of an adjunction and that its laws are automatic. The laws are automatic for the syntactic monad, and the useful question is whether the interpreter respects them. An interpreter that runs a PutLine twice, or that reorders two requests, is a lawful fold of the tree and an unlawful implementation of the interface. The free monad guarantees that the program has a tree shape; it does not guarantee that the tree means what the interface says.

The second thing the free monad is not is an effect system. The type Free f a says nothing about which requests occur in the program, only that the program is built from f. Two programs of the same type may use disjoint subsets of the interface, and the type checker cannot distinguish them. Tracking which requests occur requires an indexed or row-based type, which is a stronger abstraction than the sequencing interface described in monadic sequencing.

The third is a performance claim. A free-monad program builds a tree and then folds it, which is two passes and an allocation per request, against a direct-style program’s zero. The interpreter can be fused into the tree construction by writing the program in continuation-passing style, and the result is a program with the same asymptotics as the direct version. The naive encoding is a specification; the fused encoding is the implementation, and the gap between them is the same gap that deforestation closes for lists.

Where the structure earns its cost

Three uses justify the tree.

Replay and inspection. A test can run a program against a scripted interpreter and compare the sequence of requests, which requires the requests to exist as data. The same source text can also be run against a real interpreter, which is the reason for keeping the interpreter a separate fold.

Multiple interpretations. A program that describes a database query can be interpreted as SQL, as an in-memory evaluation, or as a plan for a query optimizer, and each interpretation is a fold. The alternative, an interface with a method per operation and an implementation per backend, is the same idea with the dispatch made dynamic.

Staged execution. An interpreter that returns a description rather than performing an effect is a staging transformation: the outer fold chooses which inner interpreter to build. A compiler pass that lowers a program into a simpler language is exactly this, and the free monad’s tree is the intermediate representation.

The cost is the tree, the wrappers, and the interpreter. For a program that is run once against one implementation, the direct style is cheaper and clearer. The free monad pays when the same program must be read more than one way, which is why it appears in libraries that expose an interface to several backends rather than in application code that has one.