Programming languages are constantly being developed everywhere. However, many new languages don’t appear to bring anything new to the table. This isn’t a problem at all; it’s usually a good idea to stick to tried-and-tested language design principles, and it’s very hard to get programmers to learn and accept novelty.
However, innovation is always exciting, and necessary for the field of language design to evolve and progress. In this article, I’d like to describe a (somewhat) novel concept in language design: algebraic effects.
What are algebraic effects?
Algebraic effects (or just “effects”) are a way to reason about the semantics of a procedure. In other words, they are a more formal way to describe what side effects a function can perform.
Side effects
For example, consider this simple program:
int add(int x, int y) {
printf("Hello there!\n");
return x + y;
}
int main() {
int five = add(2, 3);
printf("Two plus three is %d\n", five);
}The add() function is able to sneakily print a message to the console without the caller (the main() function) knowing. This is because in C, any function is allowed to have any arbitrary side effect(s), including printing to the console.
This lack of transparency regarding the side effects of a function could be a problem, especially if add() is in a different file or part of a library. In fact, the above example was pretty harmless; other possible side effects could include reading/writing files, or accessing the network. add() doesn’t even have to add 2 numbers — it could choose to divide by 0, generate a random number, or loop indefinitely! And the caller would never know about it until the code is executed.
Reasoning about side effects
Algebraic effects could help to state the side effects of a function, so that the callers would have to handle it. An effect is defined as a set of operations that the caller must define in order to call an effectful function. Let’s rewrite the above example using an algebraic effect.
effect console {
int printf(const char* format, ...);
}In a made-up syntax, we define an effect named console, which will represent any operation involving reading and writing to the terminal. Now we can use it (again, the syntax is made up):
int add(int x, int y) console {
printf("Hello there!\n");
return x + y;
}
int main() console {
int five = add(2, 3);
printf("Two plus three is %d\n", five);
}Now, add() includes the console effect in its signature, declaring that it can interact with the console. Any caller of the function will now be aware of this, meaning that functions can’t accidentally cause unintended side effects, which are a common source of bugs and security vulnerabilities.
The compiler would check the side effects declared in a function against any side effects used in the body of the function, reporting an error if there is a mismatch.
Effect handlers
One half of the effect system is tracking the side effects of functions and forcing the programmer to handle them. However, how can the operations of algebraic effects be implemented?
The other half of the effect system is the effect handler. The console effect must be provided with an implementation of its operations, which we call the effect handler. This is actually just a function that takes the input to the effect.
The above example actually assumes that the language has some sort of built-in default handler for printf(). If there isn’t a handler provided, the effect can’t be removed (“discharged”) and must be propagated to the caller. For example, if we want to discharge the effect by ourselves:
int add(int x, int y) console {
printf("Hello there!\n");
return x + y;
}
int native_printf(const char *format, ...) { /* native implementation... */ }
int main() {
handle console : native_printf {
int five = add(2, 3);
printf("Two plus three is %d\n", five);
}
}native_printf() is just a native function that prints to stdout (we won’t worry about its implementation). Notice that the console effect of main() has been discharged, because we have registered an effect handler for it. Therefore, a function must either handle its side effects (main()) or propagate them to the caller (add()).
If we assume that console isn’t provided with a built-in default implementation by the compiler (the effects must stop somewhere!), then it would be an error for main() to propagate the effect, since the compiler doesn’t know what to do when console is used.
Another neat feature of effect handlers is that we can use them to abstract over an effectful operation. For example, if we were writing a library and wanted to do some logging, we could declare that our API uses the log effect, and leave it up to the library user to handle this effect. This lets them choose what to do with it. For example, log could be provided with a handler that prints log messages to stdout, or stderr, or writes to a log file, and the library author wouldn’t have to worry about it.
Why?
Purity & separation of concerns
One guideline for writing idiomatic code is to separate the “business logic” of the program from implementation details like I/O. While this isn’t always possible, especially if the code is optimized for performance, it often results in simpler and more maintainable code.
Pure programming languages like Haskell do this by enforcing that all I/O operations be distinct from pure computations, although Haskell achieves this through the type system and monads instead of algebraic effects. This can bring multiple advantages, especially for reasoning about the semantics of code and preventing arbitrary side effects.
However, complete purity can sometimes be frustrating to work with, especially when the programmer has to keep track of the effects of functions indirectly through types (or type errors, if you’re unlucky). Sometimes, you just want to print out a value for debugging or use dependency injection for unit testing. In this case, an impure language would make this simpler and smoother to do.
Effects are perfect for this: these impure operations can be abstracted away into an effect, like the log effect we had before, without tainting our “pure” code with I/O. For dependency injection, a testing framework could provide an effect to inject the necessary dependencies into the same code for testing code, without having to write any extra boilerplate infrastructure code just for testing, or worse, worry about structuring our code to be testable.
Abstraction
As demonstrated before, effects provide us with the ability to abstract away the details behind effectful operations and allow us to easily swap out the implementation of an operation without having to change the code.
A programming language could take this concept even further. Typically, we classify programming languages as either “high-level” or “low-level” (see Ousterhout’s dichotomy). Some languages, like Java or Go lie somewhere between on the spectrum. We choose “high-level scripting languages” like Python, Bash or Lua for tasks such as automating tasks or configuring scriptable applications, and prefer languages like C, C++, Rust and Zig for their performance and low-level control they give us.
However, effects allow us to escape this dichotomy. We can use effects to let programmers easily write high-level, concise code, but when they need it, they can provide custom effect handlers to take back control over low-level implementation details.
For example, consider allocating memory on the heap. We could abstract this into an alloc effect with operations for allocating and deallocating memory. Then the language could provide a default effect handler that uses the system allocator for allocations, saving programmers that don’t care about these low-level details from having to manage memory themselves.
However, the programmer could also choose to swap out the handler, for example changing to mimalloc, using an arena allocator, or automatically managing memory with tracing GC or reference counting. A single program could use many different allocators by simply swapping out the alloc handler to switch allocators. If the alloc effect is standardized in the language’s standard library, programmers could even publish packages containing effect handlers, making using a custom allocator as simple as adding a package dependency and registering the alloc handler.
This technique could be applied to the filesystem as well. On most systems, the “filesystem” means the literal filesystem provided by the kernel. However, a fs effect could allow us to use the same unified API to represent filesystem operations with FUSE or the File System Access Web API.
Applications
Control flow abstractions
Since effects are one way to reason about side effects as well as control flow, they are an apt choice for defining custom control flow abstractions.
For example, iteration can be implemented as an effect, by defining iter as an effect with a yield() operation to yield items, akin to generators in Python. Exceptions could be implemented with an exn effect with a throw() operation to throw errors. Even asynchronous programming can be defined with effects, as shown in this paper.
More novel applications could be threading state through functions, implementing fine-grained reactivity, modeling non-determinism, or even parsers.
Implementing language features as libraries
Algebraic effects provide an extremely solid semantic foundation to base control flow abstractions on. This means that instead of implementing language features directly into the compiler, they can be implemented in the standard library or third party libraries.
Implementing language features as libraries might sound like a weird idea. However, manually baking support into the compiler for all of these language features separately could be problematic, as language designers and compiler engineers would have to consider how all of the separate language features interact as a whole. This could also make implementing changes more challenging.
For example, the tokio Rust crate re-implements a large portion of the standard library just to support async/await. In fact, the types in std and tokio are incompatible, causing a division in the ecosystem. This is nothing more than a minor inconvenience for application developers, but having a synchronous and asynchronous version of the standard library could pose a larger development and maintenance burden to the library authors. Implementing asynchronicity with algebraic effects might reduce this code duplication, and perhaps might even get rid of colored functions.
Considering the Rust ecosystem again, implementing common functionality in libraries works great in practice. Since Rust’s std is quite minimal compared to other languages, libraries like serde provide a common interface for the common task of (de)serialization. If you don’t like serde bloating your binaries due to Rust’s monomorphization, you could swap it out for something like nanoserde.
Conclusion
Algebraic effects are a powerful programming abstraction that provides a structured and composable way to handle side effects in programs. They offer several advantages over traditional approaches, including better modularity, code reuse, and extensibility.
However, effects are not a silver bullet. Due to their novelty (in programming languages), few programmers have heard of them or have experience with them. Learning a new concept or skill is always a burden for programmers. No mainstream language currently implements an effect system, although there are many research languages displaying promising results.
Regarding algebraic effects themselves, there are still language design issues. Effects can make control flow harder to track, as they abstract away side effects to effect handlers by definition. This is a common criticism of using exceptions for error handling as well. In addition, to implement language features as libraries successfully, there must be some level of standardization, in order to prevent the ecosystem from naturally diverging as more solutions are developed.
Clearly, there are problems with algebraic effects yet to be solved. However, in the future, effects may become a practical and viable tool for building scalable and maintainable applications.
Appendix: interesting implementations of algebraic effects
- Koka implements algebraic effects and handlers, and presents common use cases for them, including a paper on async effects
- Flix uses its effect system to track purity and impurity of expressions, and enables polymorphic effects to track purity on higher-order functions. It also implements “region-based local mutation”, which allows mutation within a pure function that doesn’t cause side effects outside the function. It also supports “purity reflection”, which allows metaprogramming with effects.
- Unison supports mechanisms similar to affects called “abilities”. It also heavily innovates in other areas of language design, particularly distributed computing and code storage/sharing.