I doubt if you need any new language construct to introduce this. Could you not simply pass an error handling function/object with all your functions/methods, which is called when an error occurs? This function/object could then resolve the error or throw an exception if it cannot resolve the error. It is possible, and relatively easy, to chain such error handling functions/methods to implement complex error handling methods.
Yes, you're absolutely right. The article gives the impression that algebraic effects give a new ability to decouple the code that uses some effects from the implementation of those effects. But that's absolutely not so: Simply passing down the implementation as an argument provides all the functionality that was described in the article.
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.
Should the caller, callee, or somebody in between be allowed to decide what the handling function should be? How an error is handled depends highly on what context is available at the site of the error or in the stack frames above it.
The article only gives a limited example of algebraic effects. The thing that is required for a condition system (ie good resumable exceptions) is lexical non-local transfer of control and doesn’t need algebraic effects (Common Lisp had a condition system but not algebraic effects in the late 1980s).
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
}
And allows unwinding the stack to lexically scoped labels (whereas exceptions transfer control to dynamically bound labels). This is reliable because the stack-unwinding can’t really be stopped like it can with an exception.
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).
A final question is how algebraic effects are different from having delimited continuations and building an effect system on top. The answer is that they work in strongly typed languages where one must know what type will result from performing an effect and be sure that all a functions effects will be handled.
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.
One type of refactoring is to replace recursion with iteration. You could replace iterate_big_datastructure with an iteration class. I know, it will require dynamic memory allocation. But do not forget, that you can also run out of stack if you allow unlimited recursion. Usually, the heap is much bigger than the stack, especially if you are working with a lot of threads that all require their own stack. In a sense it would be like allocating one chunk of memory and use this for the 'recursive' invocations inside your iterator. An iterator like implementation would also allow you to 'jump' around and restart at a different location.
I don’t know if you’re trying to solve the problem in the first snippet or the more general problem. The first snippet is just to illustrate what a lexical goto can do rather than the only thing it can do.
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).
Question about forking: isn't this essentially the same thing as restarts, after the garbage collector gets rid of the original (and now dangling) stack branch? Or is there something you can do with both of these branches simultaneously that's not expressible in conditions/restarts system?
The second: once a restart is invoked, the stack is unwound and so whatever was happening at the tip is forgotten. With an effect handler one is given a continuation (this might be a function or, as in ocaml, a special function-like thing which may be called only once), and you can put this to one side and do something else.
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.
