Defunctionalisation – an underappreciated tool for writing good software
Patrick Stevens is a Developer at G-Research.
I work in an engineering team at G-Research dedicated to creating performant and correct libraries for our quant researchers to use. In the process of achieving this goal, we have settled on a number of patterns to make it easier to write code that is both correct and amenable to optimisation, and I’d like to explain one such pattern in this blog post. My personal motto distilled from these patterns is “load as much information as you can into the type system, so that the computer can tell you what to write”, and this post can be viewed as exploring an aspect of that philosophy.
We have talked about “initial algebras” at some length; this post is to discuss defunctionalisation as a complementary technique. Defunctionalisation is a well-known technique among compiler writers, but I consider it to be under-appreciated as a tool for writing good software more generally. It pairs up particularly well with the “initial algebra” pattern.
Recall that the initial algebra pattern, in a nutshell, is “don’t manipulate things, but instead manipulate descriptions of those things.” An ideal program written using the initial algebra pattern is essentially a “compilation pipeline” of successive refinements to these descriptions, until finally the descriptions contain all the information required to produce a performant program; whereupon it is easy to construct that program. More philosophically, “don’t throw away information; instead, refine the information as much as possible, and only turn it into an actual program as late as possible”.
The initial algebra pattern, used correctly, has a number of advantages, all related to each other.
- The “compilation pipeline” of successively refined descriptions is very inspectable. At any point during this “compilation”, you can explore the current structure of the descriptions you have made so far.
- Keeping as much information as possible means you have more scope to optimise. For example, if your library takes as input a description of what the user wants to do, you have complete freedom to notice any redundancy or inefficiency in the user’s description before you ever start producing any concrete output.
- Such programs are very easy to test. They are naturally modular in structure (as implied by the pipeline metaphor).
But while the initial algebra pattern helps a lot in writing correct software that can also be made performant, it is still very possible to use it such a way as to nullify the benefits above; and this is where defunctionalisation comes in.
In brief, “defunctionalisation” means “converting programs into specifications of programs, and only later on interpreting those specifications back into programs”. Defunctionalisation is to program structure as the initial algebra is to datatype structure; a defunctionalised program can be thought of as a program which first describes what it will do, and then does it. This might seem like needless complexity, but in fact it can be extraordinarily helpful to separate the logic of your programs in this way.
How could the initial algebra pattern be misused, and how does defunctionalisation help?
We will discuss the three benefits of the initial algebra pattern listed above, and we will indicate how these benefits can be subverted by careless design. The first two benefits will use the same example; the third (“testability”) is best demonstrated by adding a little more complexity, so will use a different example.
It’s true that both these examples are somewhat contrived; they are designed to highlight specific principles without any of the distractions that might make the code a little more realistic. Rest assured that the principles continue to hold in real code.
The first of the benefits listed above was “inspectability”.
For this section and the next, let us imagine the guts of a very basic calculator application, expressed in the initial algebra style. Perhaps this calculator has a graphical user interface with a
+ button and a unary
- button, and the GUI constructs an expression which represents the user’s input before that input is handed off to a library for processing. The library will take an
Expr as its input, defined below, and it will interpret that input into an
int, thereby performing the calculation specified.
type Expr = | Const of int | CustomOneArg of (int -> int) * Expr | CustomTwoArgs of (int -> int -> int) * Expr * Expr module Expr = let rec interpret (e : Expr) : int = match e with | Const a -> a | CustomOneArg (f, a) -> f (interpret a) | CustomTwoArgs (f, a, b) -> f (interpret a) (interpret b)
+ button on this calculator produces an
Expr which looks like a
CustomTwoArgs ((+), a, b); the
- button produces a
CustomOneArg ((fun x -> -x), a).
Now, what happens if you were to pause in the middle of execution, just after the user’s input has been parsed into an
Expr but before we go on to call
interpret? Well, in your hand, perhaps you have a
CustomTwoArgs (closure<49>, (Const 3), (CustomOneArg(closure<103>, Const 9))). But has this actually helped you?
The resolution to this problem is very likely obvious.
type OneArgFunction = | Negate | Custom of (int -> int) type TwoArgFunction = | Add | Subtract | Custom of (int -> int -> int) type Expr = | Const of int | OneArg of OneArgFunction * Expr | TwoArg of TwoArgFunction * Expr * Expr module OneArgFunction = let interpret (f : OneArgFunction) : int -> int = match f with | Negate -> (~-) | Custom f -> f module TwoArgFunction = let interpret (f : TwoArgFunction) : int -> int -> int = match f with | Add -> (+) | Subtract -> (-) | Custom f -> f module Expr = let rec interpret (e : Expr) : int = match e with | Const a -> a | OneArg (f, x) -> (OneArgFunction.interpret f) (interpret x) | TwoArg (f, x, y) -> (TwoArgFunction.interpret f) (interpret x) (interpret y)
Hook up the
+ button to produce the
Sum union case, and the
- button to produce the
Negate union case.
Now it’s very likely that the debugger tells you that we are currently processing a
Sum (Const 3, Negate (Const 9)). Much better than the previous
The trick was to describe what we wanted to do wherever possible, and then implement that description. Notice the kinship with the initial algebra pattern: in our first attempt, we were careful not to throw away the user’s input (after all, we could have hooked it up so that
3+3 was directly
6, rather than
CustomTwoArgs((+), Const 3, Const 3)), but it was only when we defunctionalised the operations that the power of the initial algebra really came into its own.
Note further that there is no loss of flexibility – we’ve still retained the
CustomTwoArgs cases. (Perhaps we do need this: perhaps the calculator library needs to take arbitrary functions from its consumers, and we genuinely might not be able to describe in advance what the user wants to do.) This goes to show that defunctionalisation can often be done incrementally – you can get significant benefits without completely rearchitecting your program. If after several rounds of defunctionalisation it turns out that the
CustomTwoArgs cases are no longer required, then we can simply delete them and end up with a fully defunctionalised datatype; but if they are required, we can just keep them around and still retain many of the benefits from the rest of the program’s defunctionalisation.
Remember, this particular instance of the problem is small, contrived, and designed to be easy to understand. The principle does still hold in real life, and indeed one of our most recent internal projects has seen great structural and performance improvements after a couple of rounds of defunctionalising its core in precisely the incremental “identify the things you want to use this library for, and special-case them with unique descriptions” way described above.
Scope for optimisation
The second of the benefits listed above was “keeping as much information as possible, leaving scope to optimise”.
Initial algebras naturally don’t lose much information; but it’s quite possible to lose the information you need very early in the refinement pipeline. In the toy calculator example, the original attempt (without
Negate as distinct cases) made certain optimisations completely impossible.
For example, it’s true that
-(-a) = a for every integer
a, so we might wish to optimise
Negate (Negate e) down to just
e for any expression
e. But if all we have is
OneArgFunction.Custom (_, OneArgFunction.Custom (_, e)), then we simply can’t do it. Despite the use of an initial algebra, we’ve still lost too much information because of being insufficiently defunctionalised.
The third of the benefits listed was “testability”. This one is easiest to demonstrate, and it’s probably the most tangible way I use these patterns day-to-day.
Consider a simple, contrived, program that has some validation requirements, and then does one of two different things depending on whether its input was negative.
let writeSmallOddToFile (input : int) : unit = if input % 2 = 0 then failwith "Input did not pass validation: input cannot be even." if input > 100 then failwith "Input did not pass validation: input cannot be over 100." if input < 0 then printfn "Number was negative: %i" input else System.IO.WriteToFile("output.txt", sprintf "%i" input)
How would you typically go about testing this? It’s easy: simply catch and handle the exception in your tests, and mock out the file system. (Of course, the function signature will need to be altered to take a file system as input.)
But there is a dual approach: using defunctionalisation to push the work forward, into the future. Instead of handing the file system dependency down into
writeSmallOddToFile from its caller, we have
writeSmallOddToFile hand its desired actions up into its caller.
The following example is written rather in longhand to demonstrate the general pattern.
type ValidationError = | Even of int | TooBig of int module ValidationError = let toString (error : ValidationError) = match error with | Even i -> sprintf "Input did not pass validation: input cannot be even." | TooBig i -> sprintf "Input did not pass validation: input cannot be over 100." type WriteInstruction = | Print of string | WriteFile of FilePath * string module WriteInstruction = let execute (instruction : WriteInstruction) : unit = match instruction with | Print s -> printfn s | WriteFile (fp, s) -> System.IO.WriteToFile (fp, s) let describe (input : int) : Result<WriteInstruction, ValidationError> = if input % 2 = 0 then Error (Even input) else if input > 100 then Error (TooBig input) else if input < 0 then Print (sprintf "Number was negative: %i" input) else WriteFile (System.IO.FilePath "output.txt", sprintf "%i" input) |> Ok let writeSmallOddToFile (input : int) : unit = match describe input with | Error e -> failwith (ValidationError.toString e) | Ok instruction -> WriteInstruction.execute instruction
Now it is incredibly simple to test the logic of the
describe function: there are no dependencies to mock, so we can simply call the function precisely as it will be called in production. The
WriteInstruction.execute function has similarly been stripped to the bare bones; to test this function, it will be necessary to mock out dependencies (though because the dependencies have been forced as far forward as possible, they are much easier to mock). Succinctly: the logic of deciding how to do things is completely decoupled from the logic of deciding what to do, and this separation makes it easier both to test what the program thinks it should do and how the program thinks it should do it.
If a more end-to-end test is required, a function
WriteInstruction -> unit could be injected into
writeSmallOddToFile, to be used instead of
WriteInstruction.execute. Note that this looks very similar to the object-orientation-inspired idea of mocking out the filesystem; but mocking an entire filesystem is very much overkill here, giving the caller much less of an idea of how the filesystem dependency is going to be used. By instead having
describe pass its intended actions up to its caller, and separating the interpretation of those actions in
execute, the requirements are made clear.
How can you start defunctionalising your programs?
One of the great benefits of defunctionalisation is that it can be introduced gradually to an existing system. When a data structure contains functions that you (the creator of a library) have put there, you can always pull off the following manoeuvre.
Imagine we have a discriminated union called
FunctionalType, which expresses several possible ways of getting information from the outside world for use in subsequent processing. One of these ways is an
InternetRequest, which takes an integer (say,
3), then requests
http://wellknown/3.txt and checks if that document exists.
type FunctionalType = /// Requests document '3.txt', say, under a well-known URL. /// Returns true if that document exists. | InternetRequest of (int -> bool) /// Some other possible things we might want to do | AnotherCase of (string -> float) | AThirdCase of (unit -> float) type Defunctionalising = | InternetRequest of Uri | AnotherCase of (string -> float) | AThirdCase of (unit -> float)
Imagine the call site used to look like the following (where I have assumed access to some helper functions in a hypothetical
Uri module, rather than writing out a complete implementation):
let makeFunctionalType () : FunctionalType = let remoteFileExists (i : int) = let document : string option = Uri.append (Uri.make "http://wellknown") (sprintf "%i.txt" i) |> Uri.fetch match document with | None -> false | Some _ -> true FunctionalType.InternetRequest remoteFileExists let doStuff (f : FunctionalType) (i : int) = match f with | FunctionalType.InternetRequest (f : int -> bool) -> if f i then 0.0 else 1.0 | AnotherCase (f : string -> float) -> f "hello!" | AThirdCase (f : unit -> float) -> f ()
Then in the new world, it could look like this:
let makeDefunctionalising () : Defunctionalising = Uri.make ("http://wellknown") |> Defunctionalising.InternetRequest let doStuff (f : Defunctionalising) (i : int) = match f with | Defunctionalising.InternetRequest (u : Uri) -> let document = Uri.append u (sprintf "%i.txt" i) |> Uri.fetch match document with | None -> false | Some _ -> true |> fun result -> if result then 0.0 else 1.0 | Defunctionalising.AnotherCase (f : string -> float) -> // This is unchanged: we haven't defunctionalised it yet f "hello!" | Defunctionalising.AThirdCase (f : unit -> float) -> f ()
This hasn’t actually decreased the complexity: all the same code is present in the old world as in the new world, though some of it has shuffled around. However, this new world enjoys some of the benefits discussed above, and without the need to make sweeping changes to the entire program: we have defunctionalised only one case where it seemed easy to do so.
Of course, if we would like to keep the
doStuff function short, then we can extract the rearranged code out into its own “interpreting” function with type signature
Uri -> (int -> bool).
What about more complex dependencies?
Sometimes there may be interdependencies knitted into the structure of your code, such that several DU cases have to be migrated together; but even this is not an insurmountable obstacle. By creating a structure that holds the dependencies, you can make sure you have them whenever you need them; and once all the relevant DU cases have been “nearly defunctionalised” so that they consist of a description and a blob of dependencies, then you can start to move the dependencies out again.
type Dependencies = Dependencies of (int ref) * OtherThings type Defunctionalising = /// The InternetRequest case is completely defunctionalised, as above. | InternetRequest of Uri /// The AnotherCase case is not completely defunctionalised, but is "nearly" so: /// it no longer contains a function string -> float, but instead a structure /// that contains all the information that would be required to create that function. | AnotherCase of Dependencies | AThirdCase of Dependencies * bool
Now, when we come to use the
Defunctionalising type, we can recreate the functions that were previously contained within the
FunctionalType‘s cases, even if there was lots of information shared between those cases. In this example, there is some shared mutable state (the
int ref of the
Dependencies object), which is why we didn’t want to migrate the two cases independently. But we can still move the construction of those functions forward, into the future, constructing them only at the point where they are needed and hence obtaining many of the benefits of defunctionalisation:
let doStuff (f : Defunctionalising) (i : int) = match f with | Defunctionalising.InternetRequest (u : Uri) -> // We already saw this defunctionalisation, so I won't repeat it failwith "etc." | Defunctionalising.AnotherCase (Dependencies (sharedState, otherThings)) -> let f (s : string) : float = sharedState := float (String.length s) sharedState f "hello!" | Defunctionalising.AThirdCase (Dependencies (sharedState, otherThings), b : bool) -> let f () : float = sharedState := sharedState + 1. sharedState f ()
The idea is that instead of having a function which closes over its dependencies implicitly, we bring those arguments out so they are explicitly represented in the defunctionalised data structure. Then we can get rid of the function itself from our data type, and rehydrate the function later on.
Once we have manipulated the data structures into this more cleanly separated form (that is, “a blob of stuff the function needs” and “the input to the function”), we could simply stop and consider our job to be done. It’s almost certainly produced a more inspectable, more testable data structure, with nice handy labels for everything that the debugger would previously have had to try its best at disentangling for us (in showing all the variables that had been closed over). Or we could go on and see how far forward in the “compilation pipeline” we can push the computations that create the
For example, we could discover that the
sharedState was actually only ever mutated by the functions contained in these two discriminated-union cases, and that it was safe to create this dependency later, omitting it from the
Dependencies object and therefore making the code simpler (since we can guarantee that nothing else is mutating that shared state):
type Defunctionalising = /// The InternetRequest case is completely defunctionalised, as above. | InternetRequest of Uri /// Even more "nearly" defunctionalised: we have successfully extracted the int ref /// from the `Dependencies` object that used to be part of these cases | AnotherCase of OtherThings | AThirdCase of OtherThings * bool let doStuff (f : Defunctionalising) (i : int) = // Now it's only `doStuff` which can be mutating this state! let mutable sharedMutableState = 0. match f with | Defunctionalising.InternetRequest (u : Uri) -> // We already saw this defunctionalisation, so I won't repeat it failwith "etc." | Defunctionalising.AnotherCase (deps : OtherThings) -> let f (s : string) : float = sharedMutableState <- float (String.length s) sharedMutableState f "hello!" | Defunctionalising.AThirdCase (deps : OtherThings, b : bool) -> let f () : float = sharedMutableState <- sharedMutableState + 1. sharedMutableState f ()
It’s entirely up to you to decide how far along the defunctionalisation path you wish to go.
It really is very hard to express in words how beautiful a “compilation pipeline” of initial algebras can be. Functional programming is in some sense “programming via data”, and while the initial algebra pattern lets you see what you’re going to do, it is only when you add in defunctionalisation to the “compilation pipeline” that the program can truly fall out into layer after layer of pure data transformations.
Defunctionalisation makes it easier to track the dependencies of your code, and it can simultaneously make your code more amenable to optimisation and more debuggable. Indeed, internally we have used this extra power to help create visualisations of the various stages of “compilation” underlying a particular one of our projects (since at any stage of “compilation” of an initial algebra, you can always choose to interpret your data structure not as a specification of a computation, but as a specification of a visualisation!). If you have never tried working while you have good visualisations of the internals of your programs, I strongly recommend giving it a try; it is mind-expanding.
Be on the lookout for opportunities to throw away less information, and the data structures will reward you.
Patrick Stevens – Developer