Modern Functional Programming: Part 2
Late last year, I wrote my thoughts on what the architecture of modern functional programs should look like.
The post generated vigorous discussion in the community, perhaps because I
railed against the
IO monad and advocated for
Free monads, which are now
used pervasively in Quasar Analytics Engine,
one of the open source projects that my company develops.
Since then, I’ve had a chance to read responses, look at equivalent architectures built upon Monad Transformers Library (MTL), and even talk about my recent experiments at LambdaConf 2016.
The result is a sequel to my original post, which consists of a newly-minted, tricked-out recommendation for architecting modern functional programs, along with new ways of thinking about the structure of this architecture.
The modern architecture for functional programming, which I will henceforth call the onion architecture (because of its similarity to a pattern of the same name), involves structuring the application as a series of layers:
- At the center of the application, semantics are encoded using the language of the domain model.
- Beginning at the center, each layer is translated into one or more languages with lower-level semantics.
- At the outermost layer of the application, the final language is that of the application’s environment — for example, the programming language’s standard library or foreign function interface, or possibly even machine instructions.
At the top-level of the program, the final language of the application is trivially executed by mapping it onto the environment, which of course involves running all the effects the application requires to perform useful work.
The Free Edge
The onion architecture can be implemented in object-oriented programming or in functional programming.
However, the limitations of type systems in most object-oriented programming languages generally imply that implementations are final. Pragmatically speaking, what this means is that object-oriented programs written using the onion architecture cannot benefit from any sort of runtime introspection and transformation.
Within functional programming, the choices are Monad Transformers Library (MTL), or something equivalent to it (the final approach, though note that the type classes from MTL can be subverted to build Free structures); or Free monads, or something equivalent to them (the initial approach).
It’s even possible to mix and match MTL and Free within the same program, which comes with the mixed tradeoffs you’d expect.
As shown by Oliver Charles, MTL can indeed quite simply implement the onion architecture, without any help from Free. However, the following caveats apply:
- Tangled Concerns. MTL implies a linear stack of monads. Since interpreter logic goes into type class instances, this involves tangling concerns. For example, a logging interpreter must also delegate to some other interpreter to expose the semantics of the logging class.
- No Introspection. MTL does not allow introspection of the structure of the program for the purpose of applying a dynamic transformation. For one, this means program fragments cannot be optimized. Other implications of this limitation are being explored as new ways are discovered to use free monads.
- Over-specified Operations. Monad classes in MTL must be over-specified for performance reasons. If one operation is semantically a composite of others, the type class must still express both so that instances can provide high- performance implementations. Technically, this is an implication of (2), but it’s important enough to call out separately.
Free monads have none of these drawbacks:
- Free monads permit more decoupling between interpreters, because one interpreter does not have to produce the result of the operation being interpreted (or any result at all, in fact).
- Free monads permit unlimited introspection and transformation of the structure of your program (EDIT: up to the information-theoretic limit; see my talk on Free applicatives, which support sequential code just like free monads but allow unbounded peek-ahead).
- Free monads allow minimal specification of each semantic layer, since performance can be optimized via analysis and transformation.
On the second benefit, I have previously discussed optimization of programs via free applicatives, and I also recently demonstrated a mocking library that exposes composable, type-safe combinators for building expectations — something not demonstrated before and apparently impossible using monad transformers.
For all these reasons, I endorse free monads as the direction of the future. However, most functional programming languages have derived approaches that reduce or eliminate some of the boilerplate inherent in the original approach (see FreeK and Eff-Cats in Scala, for example).
In my opinion, the wonderful polymorphism of monad type classes in MTL is the best thing about MTL (rather than the transformers themselves), and clearly superior to how early Free programs were built.
Nonetheless, Free has an equivalent mechanism, which I’m dubbing Free Transformers (FT), which goes head-to-head with MTL and even allows developers to target both MTL and Free, for portions of their code.
Old-fashioned Free code is monomorphic in the functor type. With functor injection, this becomes more polymorphic, but functor injection is just a special case of polymorphic functors whose capabilities are described by type classes.
Fortunately, we can replicate the success of type classes in MTL in straightforward fashion.
Let’s say we’re creating a semantic layer to describe console input. The first step is to define a type class which describes the operations of our algebra:
Notice that unlike in MTL,
Console is not necessarily a monad. This
weakening allows us to create instances for data types that capture the
structure of these operations but do not provide a context for composing them.
This allows code that is polymorphic in the type of data structure used to
represent the operations.
Of course, monadic instances may be defined for Free, and any code that requires monadic or applicative composition can use additional constraints:
Laws for type classes like this can be specified by embedding the functor into
a suitable computational context such as
The name “transformers” comes from the fact that functors compose when nested. The outer functor “transforms” the inner functor to yield a new composite functor, and Free programs are usually built from compositional functors.
The Free Transformers approach allows maximum polymorphism. In fact, there’s enough polymorphism that a lot of your code doesn’t need to care whether you implement with Free or monad transformers!
A Worked Example
Let’s work a simple example in the onion architecture using free monads and the Free Transformers approach to abstracting over functor operations.
Suppose we’re building a banking service with the following requirements:
- The accounts may be listed.
- The balance in an account may be shown.
- Cash may be withdrawn from an account in multiples of $20.
- Cash may be transferred from one account to another.
Our first step is to create a type class to represent the operations available in our domain model:
Our next step is to create a data structure for representing these operations independent of any computational context:
Now we can create an instance for Free that can be automatically derived from any suitable functor:
At this point, we can define high-level programs that operate in our business domain, without tangling other concerns such as banking protocols, socket communication, and logging:
After we’ve defined our high-level program, we can formally express the meaning of this program in terms of the next layer in the onion.
But before we do that, let’s first introduce a notion of
Interpreter that can
give one layer semantics by defining it in terms of another:
f ~< g (
F ~< G) provides a meaning for each term in
attaching a sequential program in
G. In other words, interpreters define the
meaning of one layer of the onion in terms of another.
(Other definitions of interpreters are possible and useful, but this suffices for my example.)
These interpreters can be composed horizontally, by feeding the output of one interpreter into a second interpreter, or vertically, by feeding values to two interpreters and then appending or choosing one of the outputs.
When using this notion of sequential interpretation, it’s helpful to be able to
define an interpreter that doesn’t produce a value, which can be done using the
Const-like construct shown below:
Then an interpreter from
g which produces no value is simply
f ~< Halt g (
F ~< Halt[G, ?]). These interpreters are used purely for their
effects, and arise frequently when weaving aspects into Free programs.
Now, let’s say that we create the following onion:
- Banking is defined in terms of its protocol, which we want to log.
- The protocol is defined in terms of socket communication.
- Logging is defined in terms of file IO.
Finally, at the top level, we define both file IO and socket communication
in terms of some purely effectful and semantic-less
Rather than take the time to define all these interpreters in a realistic fashion, I’ll just provide the type signatures:
After implementing these interpreters, you can wire them together by using a bunch of seemingly unfamiliar utility functions that ship with Free implementations (more on this later).
The final composed program achieves complete separation of concerns and domains, achieving a clarity, modularity, and semantic rigor that’s seldom seen in the world of software development.
In my opinion, this clarity, modularity, and semantic rigor — rather than the specific reliance on a Free monad — is the future of functional programming.
Now let’s take a peek into the structure of this approach and see if we can gain some additional insight into why it’s so powerful.
Higher-Order Category Theory
If you spend any time writing programs using Free, you’ll become quite good at composing interpreters to build other interpreters.
Before long, you will identify similarities between various utility functions
(such as free’s
liftF, which lifts an
f a into a
Free f a /
F[A] => Free[F, A]) and functions from the standard functor hierarchy (
In fact, these similarities are not coincidental. Due to language limitations, the notion of “functor” that we have baked into our functional programming libraries are quite specialized and limited.
Beyond this world lies another one, far more powerful, but too abstract for us to even express properly in the programming languages of today.
In this world, Free forms a higher-order monad, capable of mapping, applying, and joining ordinary (lower-order) functors!
If we want to express this notion in current programming languages, we have to introduce an entirely new set of abstractions — a mirror functor hierarchy, if you will.
These abstractions would look something like this:
Composing interpreters together becomes a matter of using ordinary functor machinery, albeit lifted to work on a higher-order!
These higher-order abstractions don’t stop at the functor hierarchy. They’re everywhere, over every bit of machinery that has a category-theoretic basis.
For example, we can define higher-order categories:
The advantage of recognizing these abstractions and pulling them out into type classes is that we can make our code way more generic.
For example, we can write code to compose and manipulate interpreters that
doesn’t depend on Free, but can operate on other suitable computational
contexts (such as
The discovery of whole new ways of building programs may depend on our ability to see past the crippled notions of category theory baked into our libraries. Notions ultimately rooted in the limitations of our programming languages.
Denotational semantics is a mathematical and compositional way of giving meaning to programs. The meaning of the program as a whole is defined by the meaning of the terms comprising the program.
Denotational semantics provide an unprecedented ability to reason about programs in a composable and modular fashion.
The onion architecture provides a way of specifying whole programs using denotational semantics, where the meaning of one domain is precisely and compositionally defined in terms of another domain.
Recursion schemes are generic ways of traversing and transforming data structures that are defined using fixed-point types (which are capable of “factoring out” the recursion from data structures).
Recursion schemes are useful in lots of places, but where they really shine is complex analysis and transformation of recursive data types. They are used in compilers for translating between higher-level layers (such as a program’s AST) to lower-level layers (such as an intermediate language or assembly language), and for performing various analyses and optimizations.
If you know about recursion schemes and start using free monads, eventually you
Free is a fixed-point type for describing value-producing
programs whose unfolding structure depends on runtime values.
What this means is that you can leverage suitably-generic recursion schemes to analyze and transform Free programs!
Any program written using the onion architecture can be viewed as a compiler. The source language is incrementally and progressively translated to the target language (through one or more composable intermediate languages).
With the onion architecture, all programs are just compilers!
Recall the rise and fall of domain specific languages (DSLs), which held enormous
promise, but were too costly to implement and maintain.
Free, combined with a
suitably powerful type system, provides a way to create type-safe domain-specific
languages, and give them precise semantics, without any of the usual overhead.
The onion architecture has proven an enormously useful tool for structuring large-scale functional programs in a composable and modular way. This architecture isolates separate concerns and separate domains, and allows a rigorous treatment of program semantics.
While the onion architecture can be implemented in many ways, I prefer
Free-like structures, because of the better separation
of concerns and potential for program introspection and transformation. When
combined with the Free analogue of MTL’s type classes, the approach becomes
easier to use and much more polymorphic.
This architecture’s connection to denotational semantics, the surprising emergence of higher-order abstractions from category theory that arise from composing interpreters, and the natural applicability of recursion schemes, are all promising glimpses at the future of functional programming.
To be clear, I don’t think
Free is the future of functional programming. The
Free structure itself is insufficiently rich, a mere special case of something
far more general. But it’s enough to point the way, both to a “post-Free” world,
and to a distinctly algebraic future for programming.
To get all the way there with high performance and zero boilerplate, we’re going to need not just new libraries, but most likely, whole new programming languages.
But there’s still a lot of development possible in our current programming languages, and lots of people are working in the space.
Stay tuned for more, and please share your own thoughts below.
EDIT: Please see this repository for an example implementation in Scala/Cats constructed by Denis Mikhaylov.