Algebraic Effects for the Rest of Us
overreacted.io
overreacted.io
Doesn’t have a cool name like “algebraic effects”, and doesn’t have cool operational semantics written out, but it does something quite similar to what the article describes. Here is a little example I cooked up for a Julia programming audience. The code offers an API for computing roots of functions, and has a DIVERGENCE-ERROR condition and a handful of different restarts which handlers of said error can invoke. [2]
If you want to see what languages will look like in N years, it’s always wise to see what Common Lisp or Scheme are up to.
[1] http://www.gigamonkeys.com/book/beyond-exception-handling-co...
[2] https://github.com/stylewarning/lisp-random/blob/master/talk...
With that said, I’m not claiming they’re equivalent to algebraic effects. However, looking at the semantics provided by Pretnar [1], the Common Lisp condition system is quite close to the functionality offered in the purely functional formalism.
As a simple example, you can imagine data processing function for use in potentially interactive application, that reports progress and allows for aborting:
(define-condition progress ()
((amount :initarg :amount :reader amount)))
(defun process-partial-data (data)
"NOOP placeholder"
(declare (ignore data)))
(defun process-data (data)
(restart-case
(loop
initially
(signal 'progress :amount 0)
with total = (length data)
for datum in data
for i below total
do
(process-partial-data datum)
(signal 'progress :amount (/ i total))
;; Report progress
finally
(signal 'progress :amount 1)
(return :done))
(abort-work ()
(format *trace-output* "Aborting work!")
:failed)))
Now for the REPL sessions (-> denotes returned value). First, regular use:
CL-USER> (process-data '(1 2 3 4 5 6))
-> :DONE
CL-USER> (handler-bind ((progress (lambda (p) (format *trace-output* "~&Progress: ~F~%" (amount p)))))
(process-data '(1 2 3 4 5 6)))
Progress: 0.0
Progress: 0.0
Progress: 0.16666667
Progress: 0.33333334
Progress: 0.5
Progress: 0.6666667
Progress: 0.8333333
Progress: 1.0
-> :DONE
CL-USER> (handler-bind ((progress (lambda (p) (format *trace-output* "~&Progress: ~F~%" (amount p))
(when (>= (amount p) 0.5)
(invoke-restart 'abort-work)))))
(process-data '(1 2 3 4 5 6)))
Progress: 0.0
Progress: 0.0
Progress: 0.16666667
Progress: 0.33333334
Progress: 0.5
Aborting work!
:FAILED
N.b. your typical experience with restarts in Common Lisp is the interactive debugger that pops up when an error gets unhandled. This example serves as a reminder that restarts are not just for errors, and that you can invoke them programmatically - building applications that can figure out how to handle their own errors.
(with-progress-noted (datum data)
(process-partial-data datum))
The Lisp Machine OS had a system-wide progress bar at the bottom of the screen, which then would show the progress of some process - usually the front process or something related.
Not an expert on algebraic effects, but I suspect they are both more and less general.
On the one hand, "algebraic" hints at some constraints in the name of static typeability. Such restrictions wouldn't be present in Common Lisp.
On the other hand, Common Lisp only has single-shot downward continuations, so you won't get, e.g. nondeterminism-as-an-effect.
On Error { GoTo N | Resume Next }And the author (gaeron, aka Dan Abramov) replied:
> As far as I understand, the difference is that effects are actually typed (as part of your function signature), which I didn't go into — and so you have a lot more guarantees about what a function can or cannot do.
Algebraic effects are more aimed towards statically typed languages like Haskell or Ocaml. They can replace most uses of monad transformers, which has both cognitive and performance benefits.
As you showed, there are better ways of solving the problem in lisps.
Tagless final algebras are another much more popular alternative that has been proven very effective in practical software. In tagless final, one writes composable DSLs (which are just records of functions) with the nature and interpretation of effects left abstract.
One then writes interpreters which interpret the DSL, giving meaning to the effects. This achieves the same fundamental goals as algebraic effects, but just using the ordinary language features of static FP languages.
[0] https://docs.racket-lang.org/reference/eval-model.html#%28pa...
The main purpose of ideas like algebraic effects is to build on a firm understanding of a model of computation. Implementing algebraic effects (whether with call/cc or otherwise) lets one specify a program's behaviour more precisely.
Whether this seems useful or not is probably closely aligned with whether you think static types and purity are useful or not, perhaps.
From that perspective, algebraic effects make sense and look very interesting.
>Note, however, that algebraic effects are much more flexible than try / catch, and recoverable errors are just one of many possible use cases. I started with it only because I found it easiest to wrap my mind around it.
A generalization has to do everything that the specialization does, like dispatch on multiple processors.
The synchronous version of async/await is delay/force; that is just macrology over some lambdas.
As with all language features though, idiots will always take things too far.
Effects are about doing a computation dependent on wider context: IO, thread scheduling, non-deterministic computations, mutable references.
Now, in your example `A calling B calling C and having a well defined hierarchy and encapsulating complexity` you already have effects: threads are being scheduled by OS/runtime, IO is performed, memory cells are written.
The only difference your avg. imperative language with A calling B have is that Effects are implicitly baked into the language, while algebraic effects let you define your own effects as well.
So instead of `async val` you could simply do `(perform Async val)`, which would return val in the context of fiber scheduler (aka will do the necessary scheduling for continuing the computation). With effects you could extend your language with new effectful semantics without descending into metaprogramming hell/fixing the language.
In fact, you could think of Effects as of Monads, but composable.
Rather than needing to pass your file system accessor object, logging object, network interface, database connection provider, etc all the way through your call graph A -> B -> C, you can access those using apparently ambient authority, but still live the code testable, and all without IoC gymnastics.
I don't think the coupling argument is very strong when the effects are encoded in the type system. The kinds of effects that make sense are ambient authority operations which otherwise need explicit parameters. If they're encoded in the type system it's important that higher order functions are parameterized on possible effects to avoid unnecessarily limiting composition.
Of course all this is easier in a language with global type inference, since that will generate appropriately generic signatures that don't needlessly prevent flow of type information.
> Because algebraic effects are coming from statically typed languages, much of the debate about them centers on the ways they can be expressed in types. This is no doubt important but can also make it challenging to grasp the concept. That’s why this article doesn’t talk about types at all.
I'm only remotely familiar with algebraic effects, but I thought the whole point was to have a nice & composable way of dealing with effects in the type system, as an alternative to monads that generally do not mix well.
Also, Daan Leijen's papers on Koka are pretty accessible.
Meanwhile, if you want to add logging in Haskell via a monad, you don't just need to change the type of each calling function to make it monadic, but you need to rewrite the function to make it monadic. That is harder work than changing some types. Moreover it is harder to automate by an IDE.
Things I'd want more information on: what about errors in effect handlers (or would errors be reimplemented as effects?), effects with no handler, which handlers do effects inside handlers use? Is it really worth making it much harder to reason about apparently straight through local code in order to gain the benefits (imagine you check a condition that your later code relies on and then call a log function that unbeknownst to you happens to use effects and doesn't return control until much later when the condition no longer holds?) Can we provide timeouts to effects? Get progress updates? Where should we use effects and where should we use dependency injection? Can library code detect whether handlers are installed for the effects it might want to use up front and fail fast or provide defaults if they aren't there? Will our debuggers understand? What are the practical best practices to avoid the kind of insane spaghetti that this seems to invite?
That is, you write code that says it may perform any effects from the following list. At some central point, you execute that code in the context of a handler for those effects.
That's the same idea as using dependency injection to provide a service. The only difference is that the ergonomics are better. You can't forget to inject a service, the types prevent it.
A big problem this approach solves is that it avoids code that relies on injected code from needing to predict in advance all the things that injected code might need to do. This problem is much less pronounced in a dynamically typed language (since you haven't had to predict the type signature of the injected code).
In javascript the most significant time this is a problem is when the injected code might need to be asynchronous. In standard javascript, if that's the case, the surrounding code needs to know about it.
In Haskell, you have the same problem doing something as simple as debug logging.
My concern is just that adding effects reduces how much you know about what a particular function does just by looking at it, and this is true in both typed and untyped languages.
Monads have the problem that they don't commute, which is usually not what you want for handling events (if you've got handlers for two different types of event it shouldn't matter which event handler was registered first) Maybe the algebraic effects solve this problem.
>> Because algebraic effects are coming from statically typed languages,
Though in fact the origins come from dynamically typed languages like Lisp, where condition signalling systems were developed in the 1970s. When they started appearing in statically typed languages in the late 80s, they were only used for errors, and by the time they were caught the stack had already been unwound.
What's old is new again.
Instead most people here seem to focus on the semantics, which indeed boil down to call/cc + handlers or previous condition systems.
Computer science is a field that notoriously ignores the past, so these folks are far from the only people to reinvent something already well developed.
Conditions arose out of MIT's AI labs, a place full of entrepreneurial enthusiasm and practical work, conditions were described in the early 80s.
Algebraic effects come out of Endinborough, a place full of academic research focusing on abstract algebraic models of computing.
Algebraic effects builds on theoretical work by Wadler, Spivey, and Moggi on monadic computation, not on Lisp. Similarly, Lisp around that era built primarily on the previous work on Lisp out of MIT, not on models of computing from around the other side of the globe.
These labs had different focuses, goals, and approaches. Lisp is one of a dozen languages of the time that found clever ways to express control flow and exceptional flow, but none of them were trying to find a model for defining semantics.
Years later, we discover that many of those old constructions are almost equivalent to models derived by PL research. That's not surprising, as the models are meant to help us describe programming in general, and the problems were already there to be solved. Using the models usually (not always) gives a better end result than the ad-hoc approaches.
Or sometimes we keep ignoring the models because we've always done it some other way.
The curry-howard equivalence is only as useful as the strength of the type system. We ideally want proof irrelevance, that is, any program satisfying the types is sufficient, but while some things remain outside the type system this is only true up to a point (think: time and space costs). Putting effects into types helps this along.
However, what most people get wrong: you do not need higher-order control if you just want to resume after an error. This is demonstrated by Common Lisp, which doesn't have coroutines, algebraic effects, nor continuations, but _can_ resume after an error.
The main example of the article could be done just fine in Common Lisp, because it doesn't use any higher-order control.
These are capable of among other things, Prolog style nondeterministic choice and backtracking.
A more in depth introduction is here: https://www.eff-lang.org/handlers-tutorial.pdf (not really for 'the rest of us' - I struggled to understand this one, but found it interesting).
Lexical non-local transfer of control is effectively the ability to write code which looks like (made up JS like syntax):
function find(haystack, needle) {
iterate_big_datastructure(function(x) { if (x == needle) goto found; });
return false
found:
return true
}
This then allows conditions to be implemented by dynamically binding a list of condition handlers (functions which decide what to do when there is a condition) and restarts (functions which do the thing by non-locally transferring control out of themselves). Then instead of raising an exception and unwinding the stack, one signals a condition by creating the condition object, computing the set of restarts, and asking each handler in turn what to do until a handler invoked a restart which will unwind the stack to the right place to resume.
So one might ask how conditions (or rather lexical goto) are different to algebraic effects. The difference is that all these do is let you unwind the stack to specific places using closures and syntax to give the impression that control flow briefly jumps up the stack and back. Algebraic effects instead give you delimited continuations: when an effect is performed, the handler is given a continuation which is a bit like a return pointer plus the bit of the stack between the handler and the place the effect was performed, packaged up to look like a function. This means that one can put these continuations into data structures and do other things, effectively forking the stack. Lexical goto doesn’t let you implement something like async/await but algebraic effects do.
As a diagram, here is a schematic of the stack in the two language features. We’ll try to write down stack frames with dots, a bar for a condition/effect handler and > for the top of the control stack.
Condition system
........|..........>
Condition signalled
Call closure created by function at |
........|...........>
Find and invoke restart
e.g.
........|......>
or
......>
Effect system:
.........|...........>
perform effect
,.........*
.........|<
\.>
stack is now “forked”, control is at the effect handler
It can return control back to *, invoke another function (leaving the stack forked),
return up the stack (invalidating the continuations),
or otherwise transfer control (e.g. perform another effect).
Another way to do these effect like things is with monads which effectively convert one’s code into continuation passing style. These can make things slow if the compiler doesn’t like inlining/allocating/calling closures. Then one can have programs to evaluate these monads which work like the effect handlers because the program is already set up to put its continuations into the monad. It is hard to compose multiple monads (in particular if one doesn’t have typeclasses or a MTL equivalent) but it looks like algebraic effects will be more composable.
A common example for an application of algebraic effects would be implementing async/await like mechanisms. The effect handler would take the continuations and put them into a scheduler, so it’s stack would effectively be heavily forked.
A similar transformation would be converting to CPS with a big trampoline. Both of these differ from lexical goto and algebraic effects in a few ways:
- they require annoying manual/automatic code transformations that may make your code slower
- they don’t necessarily provide much safety
- they can be hard to type
- they can be hard to compose
These are issues which algebraic effects aim to solve.
Note that these techniques are strictly more powerful than lexical goto which only lets you unwind the stack to a particular tack frame (and recall unwinding means you forget about everything unwound).
So, in imperative/OOP languages, it's best to treat algebraic effects as inspiration for passing down objects to provide implementations; that gives you most of the same power, while using existing features of your language.
Some effect systems allow resuming multiple times, allowing more fancy features, but those features are niche, and even of questionable theoretical value because of their incompatibility with linearity.
Also, on another note, it's not really true that "things in the middle don’t need to concern themselves with error handling". That's what exception-safety is about. You very much do need to concern yourself with exception handling if you want to allow the possibility of a caller handling a callee's exception. Also see [2].
[1] https://docs.microsoft.com/en-us/windows/win32/debug/excepti...
[2] https://devblogs.microsoft.com/oldnewthing/20120910-00/?p=66...
EDIT: I guess the difference would be in Lua, yields return to where they were resumed each time, while in algebriac effects they return to the nearest handler for that case. You'd need some boilerplate to bubble up all effects you don't care about up another level at each handler in Lua.
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
^ except rare cases when embedded with lua_lock() defined as a thread locking routine. Then it becomes thread-safe, but still not multithreaded.
One obvious difference is that in a statically-typed language with algebraic effects the compiler checks that all the effects are being handled correctly. If you implement these in raw Lua a stray "coroutine.yield" can ruin everything if it doesn't return a properly formed tagged event object.
https://pypi.org/project/effect/ (Effect library)
https://www.youtube.com/watch?v=fM5d_2BS6FY (talk from PyConNZ 2015).
(Shameless plug: this is one of the libraries listed in https://github.com/sfermigier/awesome-functional-python ).
[1] https://github.com/ocaml-multicore/ocaml-multicore/projects/...
[2] https://github.com/pandaman64/effective-rust
[3] https://kcs1959.jp/archives/4387/general/algebraic-effects-f...
[4] https://qiita.com/__pandaman64__/items/9fd47af5a39f0d2a6bbb
Maybe that's where they got the name from? Although performing the effects directly through a pause/resume mechanism doesn't sound algebraic to me.
This sounds like a terrible idea. Especially given the nature of Javascript, this basically would mean that you would have to write every single bit of code to be re-entrant. What if you 'perform' and then the 'resume' doesn't happen until every single assumption made about the entire program state for the entirety of the function in which the perform occurs has been invalidated? After doing a 'perform', you would have to operate under the presumption that nothing done in the first portion of the function has any relevance any longer, no? The enumerateFiles example later in the article is an even better example. It performs in multiple places, but carries on like it's a normal function, not considering that at each of those performs, the entire state of the program could be changed, and none of the conditions established prior to those lines can be relied upon to still hold.
"Imagine that you’re writing code with goto, and somebody shows you if and for statements."
10 for a = 0 to 10
20 if a = 5 then goto 40
30 next
40 end
50 print "5"
60 goto 30
I lack imagination.
That said, algebraic effects sounds interesting indeed.
Totally separate from stylistic quibbles, I also think effect systems are often oversold by folks who like them (usually, in my experience, folks from a functional background).
Fundamentally, a lot of the code we write is the effectful IO plumbing. By that I mean: there are very few complicated algorithms, or really any hand-written algorithms at all, in a large amount of code written for modern systems. Instead, the complexity and value of the code is in the way it coordinates different external IO sources/sinks. This is pretty well illustrated in the article's toy directory enumeration/file handling example: with the IO/system specific stuff extracted into the effect receivers (processors? handlers?), the remaining code is not just simple, it's vacuously simple. The complexity and trickiness of handling IO, dealing with error conditions, etc. all remains, though, in the effect receivers. This is subjective, but that seems more akin to the "over-extracting methods to the point where all you do is increase the line count" school of refactoring than the "improving the comprehensibility/maintainability of the code" school. Generifying IO interactions behind an effect system in a codebase that is primarily occupied with gluing together external systems results in moving so much of the code into effect receivers that nothing useful remains behind.
Put another way: often, what we're doing is intimately coupled with how: like, sure, I'm technically "piping data from a source into a sink with a transformer in between", but they don't pay me to write "source |> transformer |> sink", they pay me to write (for example) the SELECT statement in the source, the column mapping/reformatting logic of the transformer, and the POST-to-endpoint in the sink. If those things already existed, it would be the one-liner above, but they don't for the business domain, so we make them. Once they're written, by all means, modularize them and make them easily usable in a streamable, convenient way. But most of the interesting code, once you peel back the curtain on "source" or "sink" is still going to be in its effectfulness.
Then there's the argument from modularity/swappability: that you can replace effect handlers with equivalent handlers for doing other things. If you're writing a system with many swappable backends, this may be useful. However, most systems don't have that property. Datastores and effect receivers change much less often than the data flow itself. And past a certain point you end up with "old Java"-style modularity: things abstracted so far away in service to unneeded pluggability that the code becomes harder to follow and maintain (especially given that the code may be primarily/near-exclusively concerned with specifics of IO flow).
To be sure, there are some cases where effect systems can really help. I just don't think those are as numerous as FP proponents think they are.
WalterBright: "Challenge accepted!"
Modern IDEs can detect exception types which don't exist yet, and create them on the fly while you try to use them for the first time.
Although in this case it simply seems a way to interact with some kind of environment, which in object oriented languages is easily achieved with dependency injection (which does mean you have to pass through an extra argument to every function, but that's not usually that big a problem, and it can give hints on how to combine and divide environments).
Step 2) Compile it to WebAssembly
Step 3) Validate those input fields
Step 4) Profit
Wasm doesn’t allow 1+2, since browsers dictate how io/device/extension-communicating code should be done and their native routines are not ready for techniques of the level higher than just a bare callback. Wasm is not a solution, since the platform and primitives are the same. It is basically the same javascript-in-a-browser model with syntax and scoping rules to be implemented by someone else.
One can emulate any language by turning js/wasm into a virtual machine, but that’s not speed or battery-friendly.
This is literally Common Lisp's condition system which a) decouples signaling conditions from handling conditions, b) allows you to execute arbitrary code in the place that signals, c) allows you to stack independent pieces of condition-handling code on one another so they run together, and d) allows you to unwind the stack or not unwind the stack at any moment, so your code may continue running even if it ends up signaling.
ANSI Common Lisp was standardized in 1994. This post is from 2019. That's reinventing a 25+ year old wheel the author is likely unaware of.
It just doesn't seem practical at all.
However, neither the linked paper nor the author of this article seem aware of Lisp's prior art in this space, which is a shame. In particular, it's not true that you "can't touch this" - you absolutely can touch a production-ready implementation of this, in Common Lisp, and could for the past 30 years.
The more interesting thing is not the wheel (aka the technology) itself, but how to make actual use of it...
It makes quite a bit of difference when I compare e.g. async programming in OCaml with Lwt/Async where I know I've at least hooked up the promises somewhat correctly with e.g. Python or JS where I will notice that it is wrong when the code is executed.
What exactly do you mean? Conditions are typed in Lisp with proper inheritance, and handlers can be bound only to particular types of conditions.
These comments are not helpful. React is a UI library and this concept would be new in this world. Who cares if it's done by the Simpsons already? It's a nice trivia, but what should we do with this information?
Without any sarcasm, communication is a hard and unsolved problem in general.
Second, React might be a UI library, but its need / uses / limits in using for something like "algebraic effects" could be similar to the ones encountered 30+ years ago in non-UI domains.
Not to mention the biggest fault in this comment: the domains where Dan got the idea of Algebraic Effects from are already non UI -- he got it from functional programming research in non-UI specific domains and languages.
Which means that he could just as well use the original, also non-UI, concepts, was he aware of them.
A more valid response along your reasoning would be that of course not everybody can/knows every prior art. That's true, and valid. But the argument that prior art is not relevant in this case because we're talking about UI is not...
>It's a nice trivia, but what should we do with this information?
Evaluate it, enrich our understanding of it, find prior uses and limits (and not just the current re-implementation of the concept) and so on?
Unfortunately I don't speak monad.
The example here to do with error handling only shows that this form of error handling is an (incredibly) specific (very limited) instance.
And nothing is being reinvented here. This is an article to communicate, in the simplest terms possible, decades of academic research. The author is not claiming to, nor has he, invented anything.
Continuation-passing is only one component.
Your whole approach to commenting here is, "I think I know what AE are, and on that basis, this is stupid!"
Both your premise and conclusion are false.
The author is likely unaware of Common Lisp's condition system because that's a completely random and arbitrary conceptual ancestor. It was predated by throw/callcc in Standard ML in particular, I believe (which, needless to say, draws a direct line to OCaml and thus this post). In fact, continuations in some form or another date back to 1964 according to: https://en.wikipedia.org/wiki/Continuation#History
Algebraic effects were introduced by Plotkin in 2001 (https://link.springer.com/chapter/10.1007/3-540-45315-6_1) as an extension of Moggi's 1991 work on monads (https://www.sciencedirect.com/science/article/pii/0890540191...), which in turn built on work from the 70s and 80s on understanding computing from the perspective of category theory.
The chief difference, IMO, is that Pitman defined terminology for a language feature in some LISP dialects, while Plotkin showed operational semantics for algebraic effects that are compatible with the denotational semantics (ie, adequacy). Pitman wrote his paper using the AI Labs' practical experience with LISP for the benefit of other LISP practitioners. Plotkin wrote his paper using previous work on lambda calculus and category theory for the benefit of programming language theorists.
Plotkin may have been unaware of CL's conditions system, but since conditions do not have formal semantics, and their behaviour is not particularly useful for probablistic non-determinism (the main thrust of Plotkin's effects article), I doubt that being aware of it would have made him any less motivated or likely to do the work he did.
Dolan et al (https://link.springer.com/chapter/10.1007/978-3-319-89719-6_...) discuss algebraic effects for concurrency in the setting of a dialect of OCaml, and reference CL conditions (amongst other things) as related work. It's a very brief mention observing only that conditions fail to convey the full continuation as a value to handlers, making them unsuited to the use case at hand.
TL;DR: no, conditions aren't the same thing, and if they were, they lack the rigour to be useful without the work that went into algebraic effects.
The Symbolics Lisp Machine Manual from 1984 documents the condition system for the Lisp OS written in Zetalisp:
http://bitsavers.org/pdf/symbolics/software/release_5/3B_Lis...
See the chapter 'COND' in Volume 3B, 'Lisp Language'