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).
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.
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 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).
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.