After quite a marathon, I recently completed a part-time MSc in Software Engineering. This involved choosing a thesis project based on a theory, process, or implementation relating to software development. I chose the latter, with splashes of theory interleaved to provide context. The general field is design patterns in functional programming and involves a small program loosely resembling a real world backend application. The project needed to be distilled into a dissertation document and fleshed out with a narrative. The result is this hefty PDF: dissertation.pdf
Acknowledgements
I’d like to thank my supervisor Jeremy Gibbons for his sound advice and encouragement, relating to both academic best practices and the subject matter. The scope of this project not only grew but also became something of a moving target. Jeremy gave me confidence to choose the path I eventually went down.
My partner, friends and family also helped keep me mostly sane through a rough period.
Other resources that benefited me hugely are listed in this post.
High-level Summary
What’s the elevator pitch? The dissertation ended up as an evaluation of pure functional effect systems from first principles. In particular, it tries to operate at the cusp of the academic literature and real world software development. I’d argue that, in the context of pure FP, effect systems can be largely thought of as design patterns since the most difficult and, importantly, useful part of software design is figuring out how to manage the execution and composition of effects. Broadly, the patterns under scrutiny are:
- Raw monads such as Haskell’s
IO. - Monad transformer stacks.
- Tagless final.
- Free monads.
- The ReaderT pattern.
- Extensible effects.
The vehicle of comparison is a small example program chosen to demand four effects:
- Environment.
- State.
- Errors.
- I/O.
Several conventional tools and techniques are evaluated in the context of effects. Code is mostly Haskell, with sprinklings of Scala to illustrate the differences for a pure functional runtime (à la Cats Effect) atop a hybrid language. The evaluation is hung on the following criteria:
- Expressiveness. Can we express all effect compositions necessary for real world applications?
- Modularity. Can this be done in a way that sufficiently separates concerns such a business logic from lower-level effect operations?
- Extensibility. Can the system be extended with custom DSLs and standard effects without impacting existing programs or interpreters?
- Ergonomics. Holistically, is the system pleasant to use, understandable, free of unnecessary boilerplate and resistant to manual errors?
- Performance. What efficiency trade offs are involved?
This subject matter took me on an adventure from the origins of programming languages, imperative and functional, past the coining of effect systems as frameworks for managing computational effects, through to the early Haskell discoveries involving monads and monad transformers. This eventually led to a bunch of patterns for building useful, real world systems in a pure functional programming style. There are many different opinions regarding the benefits and drawbacks of each of these. A desire to understand the trade offs and nuances in this discussion is what drew me to the topic.
Reflection
This forced me to understand the origins of many concepts and techniques I took for granted in my experience as a professional software developer. It was a painful but, in hindsight, fun process. I now find myself viewing most software problems through the lens of effects, since they appear to provide a neat umbrella over many modern programming idioms.
The conclusion is a set of recommendations for the most appropriate situations in which to use each functional programming tool.
If I had to be pinned down to a single position: extensible effect systems broadly subsume those that came before as a general programming pattern and framework for structuring applications.
The ReaderT pattern can be a pragmatic, more familiar alternative and may be favoured if performance is paramount. However, I feel that performance should almost always be considered less important than the 4 other criteria since most real world applications are I/O bound so the differences are negligible. One example of a high-performance CPU-bound application using extensible effects is Github’s semantic code analysis tool; so it can be done. Free monads and the other standard transformers still have their uses in more specific situations.
It’s worth mentioning that languages with first-class support for extensible / algebraic effects will inevitably have better usability than any library. I’m unsure whether these effect systems bolted into the syntax of mature languages will be quite as compelling. That might be where we eventually land. There’s a lot of legacy software out there.
One caveat is that hybrid languages like Scala have less of a need for a fully-fledged effect system, even with the constraint of purity, since there are other mechanisms to plumb modules together (like OOP classes).
It’s a fairly strong position and perhaps sharing this can generate some kind of discussion. I’m happy to be told I’m wrong. In any case, I hope it can be useful to others interested in this domain. If anyone takes the time to read any of it, please do send corrections my way—comments are open.
Future Work
The dissertation focussed mostly on Haskell effect systems, but there are a few areas I’d like to investigate further.
Scala Effects
As mentioned, Scala made a few appearances. However, there wasn’t a rigorous analysis like with the Haskell techniques. There’s a natural comparison between RIO vs MTL-based tagless final in Haskell, and ZIO vs IO-based tagless final in Scala. ZIO is an opinionated effect system, much like RIO. Tagless final in Scala has similar properties as a pattern, though it doesn’t necessitate transformers at all; primarily due to alternative means of dependency injection. I’d like to see (or do) an honest appraisal of the two from the effect system angle. I might use the criteria established in the dissertation as a guide.
Another project I haven’t delved much into is eff, a Typelevel project implementing free-er extensible effects in Scala. I’m unsure whether anyone’s using this in production, but it presents a solid third option for comparison with Cats Effect and ZIO. I suspect it’ll be less user-friendly than the various Haskell extensible effect frameworks since Scala’s type system can’t compete when it comes to things like type inference and partial type application. Best to withhold judgement though.
Algebraic Effects
The original topic was going to be employing algebraic effect systems to solve real world problems. These may be seen as the analogue of extensible effect systems without the restriction of purity. Although I currently feel that pure FP is the most robust programming paradigm, I think languages built with a functional core and an algebraic effect system (Unison, for instance) have high potential for future adoption. Hopefully I can make time to explore the domain further and write-up what I learn.
Testing
In industry software, unit and integration testing of software components are an important part of a developer’s role. This topic receives less attention in pure functional programming communities than those of imperative languages. One reason for this is that we extract as much expressiveness as possible from static typing; the preference for “types over tests”. There are also different modes of thinking around the most effective testing strategies and their corresponding programming patterns. Being a real world software concern, the topic of testing is unsurprisingly absent from the literature. Therefore, an investigation into the relative merits of these effect systems with respect to testability is an interesting unexplored domain.