Algebraic effects - a survey

At ICFP this year, KC Sivaramakrishnan gave two talks that put OCaml 5 in the spotlight: his keynote, “Retrofitting Concurrency - Lessons from the Engine Room,” and the opening presentation of the OCaml workshop, “OCaml 5.0 - Concurrent and Parallel Programming.” Effect Handlers feature heavily, as they are the foundations on which concurrency primitives were added to OCaml. Since I knew very little about effects in this context, I asked KC for some pointers on where to start with learning about them. He pointed me to the Koka programming language, encouraging me to set it up, play with it, and see how its type systems work with effects and effect handlers.

Following the usual tradition of learning something by committing to give a talk on it, I signed up to speak about algebraic effects at my local functional programming meetup, FP-SYD. I figured that I would have a friendly audience that would be forgiving of excessive hand waving! :)

Brain Food

I had an absolute blast learning about algebraic effects! Koka was really easy to install and use. Its rich set of examples and excellent documentation make it work really well as a place to explore the concepts of effect systems.

That got me started, but what really hooked me was discovering Andrej Bauer’s paper, What is Algebraic about Algebraic Effects and Handlers. As a mathematician, I found it to be an accessible way of getting to the topic’s theoretical underpinnings (see here for the paper and videos). Next, Matija Pretnar’s tutorial, An Introduction to Algebraic Effects and Handlers, complimented Bauer’s work really well.

As I learned more about the topic, I realised just how deep an area this is — and I realised how little I would know about it in four weeks of enthusiastic (but decidedly surface-level) reading. So, I decided to pitch the talk as an overview or a survey of the field. To make things concrete, I would also focus on examples from the effect handling systems of Koka and OCaml 5.

The Talk

October’s FP-SYD was on the 19th. Around 6pm in Sydney’s Central Business District, about twenty people showed up, ate pizza, and settled into general functional programming-related geekery. Haskell is very strongly represented in this community, and it turned out that most of the audience had not spent much time with effect systems, as their tools for working with effects have been Monads, Monad Transformers, and accompanying abstractions.

I enjoyed talking through what I had learned about Algebraic Effects. Since I’ve worked on Haskell teams, I connected with the community on the various ways computational effects are handled between pure and impure functional languages. It was great to reference Alexis King’s recent work that resulted in delimited continuations being added to GHC. The examples from Koka helped give folks a taste for the type systems that include effects and values. I also leaned on the excellent work of KC and the Tarides team, borrowing heavily from the material they have written on effect handlers for the OCaml manual.

The talk certainly delivered, as it got me started on the vast topic of algebraic effects. It also piqued the curiousity of at least a few people in my community, so that’s not nothing! :)

Acknowledgements

I am particularly grateful to KC for getting me curious and giving me material and inspiration to get started. Thanks also to Sudha Parimala for putting together a comprehensive tutorial on parallelism and effects in OCaml and for answering questions and making helpful suggestions. My colleague and friend Tim McGilchrist runs the FP-SYD meetup, so he helped by asking a lot of really good questions, listening to a draft version of the talk, and generally providing support and encouragement. Thanks, Tim! :)

The slides of my talk are available on the FP-SYD repository.