My Effects Bibliography

In the spirit of this bibliography of resources on effect systems and programming languages, I thought I’d compile a list of my personal favourites. These tended to be the ones that made certain things “click” during my dissertation research. It’s a blend of papers, blogs and videos from functional programmers and academic researchers. They’re all related to the topics of effects and design patterns with a focus on pure FP in Haskell and Scala. The list is loosely in chronological order, though several have contributions spanning years and decades. I’ve had to be selective; suffice to say there are plenty more great resources.

This aims to be a source of information on the theory and application of effects which is accessible to functional programmers without having to read an entire field’s worth of papers. I also wanted to acknowledge their contributions and praise the work. If I’ve misunderstood or misrepresented anything, please let me know. As I explore the domain further, I’ll try to keep this up to date with insightful content that’s either new to me or just new in general.

Perhaps the most important thing I’ve learnt is the value of sharing what you learn. Most of the people listed here do not earn a living through writing about software; they do it for fun. As a consumer, this distinction is surprisingly unimportant. Often we glean wisdom from a whole book or paper, but sometimes it’s a small sentence or two in a random chat app which makes something click. Producing as well as consuming content feels largely like a win-win, assuming that it doesn’t have the ability to cause harm but does have the potential to do good.

The Effects Bibliography

This is a curated collection of languages, libraries, and papers about topics relating to effects. It’s more comprehensive than this list, but leans more towards the academic literature. An essential resource for anyone wanting to understand the evolution of the field.

1989 - Conception, evolution, and application of functional programming languages

The narrative I developed was helped hugely by this early review of functional programming. It does a really good job of highlighting and comparing the core FP constructs defined in many of the early languages. It also includes a useful exposition around how effects such as nondeterminism and I/O were represented in FP and, later, pure FP languages.

2008 - Data types à la carte

Introduced a variation of the “free monad pattern” where DSLs can be defined independently, rather than being part of the same closed union. The trick is to use coproducts. Highly influential on both the academic domain and FP patterns in software development.

Generally very well written, concise and compelling as a narrative. Some familiarity with Haskell is needed, but I think it’s not much more difficult to understand than blog posts explaining the same topic. For that reason I’d recommend it to anyone interested in this domain or just functional programming in general. It’s as good an entry point as any into the programming languages research space. Technically it’s not a typical piece of research, but rather a “Functional Pearl”. Jeremy Gibbons characterises these as short, engaging stories based on interesting or novel programming patterns, proofs or concepts.

2007–2015 - Oleg Kiselyov

Coined extensible effects and his work has been a consistently important part of the academic literature. Particularly influential on the evolution of effects in Haskell and OCaml. Oleg has a great ability to communicate the essence of concepts and draw clear delineations between different parts of a field. This was particularly valuable when on a tight deadline and unable to spare the time to deep dive into everything. Highlights:

• 2007 - Finally Tagless, Partially Evaluated. Tagless final is less clearly coupled with effects, but the emergent design pattern is an important tool for any functional programmer. This was the original paper by Carette et al.

  This made it click that TF, type classes and effects are orthogonal rather than intrinsically linked. Reader, Writer, MonadError as we know them are just one representation of effect operations—as tagless final encoded type classes.

• 2012 - Typed Tagless Final Interpreters. A lecture walking through tagless final from first principles. Identifies the independent problems of type-safety and extensibility when writing DSLs. The solutions to these are, respectively, the “tagless” part and the “final” part.
• 2013 - Extensible Effects: An Alternative to Monad Transformers. Essential reading. Does a great job of outlining the problems with traditional effect systems and motivating extensible effects.

• 2014 - Extensible Effects vs Data types à la Carte. An example-driven exposition on the difference between extensible effects and free monads. Made the extensibility issues of DTalC hit home for me. In particular, composing DSLs with coproducts leads to a lack of extensibility in the interpretation. This is comparable to the original problem of sum types being closed unions, it’s just more subtle.

  It betrays that our DSL instruction sets are not independent after all: their individual interpretation semantics are coupled to one another. This is made apparent when trying to run an expression.

• 2015 - Freer Monads, More Extensible Effects. Follow up paper simplifying the mechanics—and performance ceiling—of extensible effects. Big ergonomic improvement which led to a bunch of extensible effect Haskell frameworks. These are gradually increasing in adoption.

2014–2021 - Wu, Schrijvers et al.

Wu, Schrijvers and colleagues are a prolific source of contributions to the literature and have influenced many implementations of extensible and algebraic effect systems. A few of the key resources:

• 2014 - Effect handlers in scope. A nice walkthrough of the different challenges we face when representing first-order and higher-order effect (HOE) operations, and a solution for algebraic / extensible effect systems. HOEs operate on programs, and therefore introduce the problem of scoping because effects raised within these programs must be handled differently to those in the outer scope. The most intuitive example is catch which needs to define a local scope for error handling. This has always been a challenging problem—lifting scoped HOEs is not safe with the MonadBaseControl solution in the context of monad transformers.

  The given example involves the classical composition of errors and state. It is not possible to achieve so-called “transactional semantics” (when state is discarded following an error) using either scoped handlers or tagged regions. This renders perfectly reasonable programs unrepresentable. My understanding of the underlying problem is that, when we have effects which modify control flow such as throw / catch, there are multiple possible continuations for the program, all with potentially different sets of effects being raised in their scope.

  The key contribution is establishing the infrastructure to permit representing functions like catch as syntax rather than as handlers or the other verbose approaches.

  It’s an important paper because many real world programs need to use higher-order effects such as errors, concurrency, resource management and tracing. It’s ideal to represent them in a manner consistent with other effects—a clear decoupling of syntax and semantics—without loss of flexibility. Sandy credited this paper and built upon it in the implementation of polysemy.

• 2015 - Fusion for Free: Efficient Algebraic Effect Handlers. Another influential paper focussing on the problem of performance when traversing trees of effect syntax fragments. The key idea is that we can fuse handler operations together to make the tree passes linear rather than O(N) in the number of handlers. This avoids several intermediate representations. This is particularly important for CPU-bound applications. The Github semantic team developed fused-effects, an extensible effects library based on this idea, and were able to achieve a 250x performance improvement. Patrick Thomson presented this case study in a great talk on the topic.

• 2021 - Reasoning about Effect Interaction by Fusion A more mathematical, less practical paper from Yang and Wu. I tend to focus more on the applied side, partly because learning the necessary symbolic vocabulary is pretty intimating, partly because… time. However, this contains a good summary of the formal characterisations of algebraic and extensible effects. It also demonstrates that so-called “modular handlers”, when composed, preserve the equational laws of the individual effects. As far as I can tell, the idea is to establish conditions under which handler functions can be safely composed.

  The practical utility of such work is that it can lead to correctness guarantees for, and optimisations of, real effectful programs. One can imagine a language that makes undesirable or confusing effect compositions unrepresentable at compile time—a huge win for programmer ergonomics.

Michael Snoyman (snoyberg)

Coined “The ReaderT Design Pattern” in 2017 and has consistently delivered useful talks and blog posts. The other FPComplete post I would highlight is the introduction of rio. It’s a great example of an opinionated effect system, designed to make things simple for users while sacrificing some flexibility. ZIO is a similar idea reincarnated in Scala and given an extra effect on top of reader (or environment): error handling. Of course, it’s mostly optimised for the JVM and seeks to serve a different community to Haskell, with different preferences.

Sandy Maguire (isovector)

Author of polysemy and advocate for DSL-driven development. Generally great writer and speaker. Made several things click for me.

• 2017 - Don’t Eff It Up: Free Monads in Action. As someone who does not use Haskell in production, this helped me understand how systems are written in the real world. Also puts forward a compelling argument for extensible effects.
• The polysemy documentation is great, and it’s generally an ergonomic library so a good introduction to extensible effects. There are also several blog posts discussing its internals as well as other key concepts, bridging the gap between the literature and practical software engineering.

Alexis King (lexi-lambda)

Generally great content on effect systems, predominantly in Haskell. Highlights:

• Several evergreen conversations on the Haskell subreddit. Provided great context / narrative of the field and how it relates to real world programming.

• 2020 - Effects for Less. Brilliant talk on the performance of effect systems in Haskell. Although its quite targetted in focus, I didn’t have time to deep dive on the topic of efficiency and this cleared up a lot of questions I had.

  Tl;dw: micro-benchmarks usually do not translate to any property of a real world application that we actually care about. It’s hard to tell when Haskell’s compiler optimisations will fire, so MTL may not even be faster than extensible effects in certain situations. Therefore, focus on the other dimensions that we care about first, such as ergonomics and maintainability. Optimise on a per-application basis. In my opinion the same reasoning applies to other languages such as Scala, whose performance characteristics will additionally depend on the runtime it targets (JVM, JS, native).

  Another general point on this is that extensible effects have a higher theoretical performance ceiling than MTL. This is not new—it was emphasised by Oleg in the original paper and has since been reiterated by Alexis and others.

• 2022 - The Effects Semantic Zoo. A well-presented play around with compositional semantics in MTL and extensible effect systems. This inspired my own exploration, summarised in a comparable table of results (Figure 7.4).

Fabio Labella (SystemFW)

It’s hard to pinpoint an exact resource, but Fabio’s list of his disparate writings from various online communities is a little goldmine. There’s something unique about following all the thought processes involved in someone else learning, as a way to facilitate your own. It’s an organic process. I think more people should record these sorts of nuggets of wisdom.

Daniel Spiewak and the Cats Effect maintainers

Covers similar territory to Alexis, but in functional Scala. Has squeezed performance out of Cats Effect and written extensively about the internals. The Cats Effect documentation is also a very good resource for how effect systems (and effect monads in particular) work. This covers both the user-facing API and the low-level internals like concurrency primitives.

Unison Abilities

Extensible effects can be thought of as, in very simple terms (waves hands), algebraic effects in the context of pure languages. They are mechanically similar for the end user in that you can raise and handle effects, but you don’t need to be within a monad to do so. Unison is one of the few languages using algebraic effects that has an industry focus and its documentation is :chefskiss:. Great resource, made for programmers.