Control structures in programming languages: from goto to algebraic effects
xavierleroy.org195 points by SchwKatze 7 days ago
195 points by SchwKatze 7 days ago
It's a pity that the section on exceptions didn't do a more detailed analysis on the criticism of exceptions; in my personal view I haven't liked exceptions, in a similar vein to how I'm not a huge fan of the implementation of POSIX signals or setjmp / longjmp.
Although I very much see the reason why it was developed, in effect it comes closer to a glorified form of "come from" (and people thought that goto was considered harmful).
I'm the opposite - I really like checked exceptions in Java because it's very easy to see how developers are handling errors and they also form part of the function signature.
Most functions will just pass on exceptions verbatim so it's better than error return values because with them the entire codebase has to be littered with error handling, compared to fewer try catch blocks.
setjmp, etc. are like unchecked exceptions, so I'm also not a fan, but I use this occasionally in C anyway.
>I really like checked exceptions in Java because it's very easy to see how developers are handling errors and they also form part of the function signature.
Errors as return values also form part of the function signature in many languages.
>Most functions will just pass on exceptions verbatim so it's better than error return values because with them the entire codebase has to be littered with error handling, compared to fewer try catch blocks.
The question is whether you think that calls that might pass an error up the call chain should be marked as such. I think they should be.
I wouldn't call this "littered with error handling" just because a certain language has decided to do this in a way that resembles industrial style fly-tipping rather than just littering.
Why would errors as return values have to propagate any farther in the codebase compared to errors as exceptions? If exceptions can be handled, so can the value based errors.
The criticism as I understand it isn't about where the errors are actually handled but the ceremony needed in an errors-as-values model, most obviously in Go where you've got to write a couple of lines of test and early return explicitly for each such possible error, compared to C++ where you write nothing.
Rust's Try operator is the minimal ceremony, a single question mark acknowledges that we might not succeed and if so we return early - but there was still ceremony for each such early return.
I happen to think exceptions are inherently a bad idea, but for a different reason.
You nailed it - that's my criticism :)
I've worked with a lot of code like this (particularly C libraries and litanies of return codes), and it's fine... But I prefer something like Java-style exceptions. And with Java lambdas or Kotlin the trend is unfortunately away from checked exceptions these days...
I too am interested in your other reasons!
See my other comment for this article: https://news.ycombinator.com/item?id=45864463
I believe that for today's large software which has multiple engineers, possibly not even working in the same group, involved in the final product, the key problem of exceptions (knowing what is or is not an "exceptional" situation for the software) is not soluble in the general case. Exceptions are a clever idea if you're a solo writing a soup to nuts piece of software, say the firmware for a thermostat, but are too flawed for the library author or the app developer.
I think the sweet spot is to use exceptions for bugs. If the error is expected, make it data.
"Exceptions should be exceptional" gets to the heart of the problem with the entire concept of Exceptions for non-trivial pieces of software where there's more than a single programmer maintaining the complete system.
Now the library programmer has to guess whether when you - the application programmer try to Wibble a Foozle - will have ensured all the Foozles can be Wibbled, and so not being able to Wibble the Foozle is an exceptional condition, or whether you want to just try to Wibble every Foozle and get an error return if it can't be Wibbled...
One option is for every such condition you bifurcate the API. Instead of three types with a total of eight methods, maybe there are six conditions for two of those methods, and so now it is three types with over 100 methods... ouch. Good bye documentation and product quality.
So - exceptions are for invariant violations? I'm essentially trying to work out what it is that makes something "exceptional"
Well, this obviously depends on a given programming language/culture, but in my mind I would say in case of parsing a string to an int it is an expected case that it could fail, so I would model it as a Return type of an Int or a ParsingError, or something like that.
Meanwhile, for a function doing numerous file copies and network calls I would throw an exception, as the number of possible failure cases are almost limitless. (Like you surely not want to have an ADT that models FileSystemFullErrors and whatnot).
It so happens that in this particular example one is pure and the other is side-effecting, but I'm not convinced that's a hard rule here.
In a good effect system exceptions as effects are isomorphic to error conditions as data, so the choice comes down to what is more ergonomic for your use case, just like the choice between these three isomorphic functions should is down to ergonomics:
frob1 :: Foo -> Bar -> R
frob2 :: (Foo, Bar) -> R
frob3 :: FooBar -> R
data FooBar = FooBar { foo :: Foo, bar :: Bar }Everybody chooses a favorite depending on their domain.
A function executes, and some error happens:
- Return error value: try to handle the error ASAP. The closer to the error the more detailed the information. Higher probability of recovery. Explicit error code handling throughout the code. Example: maybe you try again in one millisecond because the error is a very low probability but possible event.
- Exception: managing errors requires a high-level overview of the program state. Example: no space left on device, inform the user. You gather the detailed information where the error happened. The information is passed as-is or augmented with more information as it bubbles up the stack until someone decides to take action. Pros: separate error handling and happy path code, cleaner code. Cons: separate error handling and happy path code, unhandled errors.
Worst case scenario: you program in C. You don't have exceptions. You are forbidden to use setjmp because rules. A lot of errors are exposed directly to the programmer because this is a low-level language. You return error codes. Rules force you to handle every possible return code. Your code gets incorporated as an appendix to the Necronomicon.
This 2003 interview with Anders Hejlsberg gives considerations why he didn't add checked exceptions to C#. https://www.artima.com/articles/the-trouble-with-checked-exc...
Exceptions done well should outperform return value checking. However it’s very difficult to make it perform well and for some reason people prefer -> Result<T, E> instead of -> T throws E which is basically the same thing.
The difference is the monadic capabilities of the result type. Thrown exceptions pepper codebases in ways that are even more unfortunate than monadic composition, which is already kind of iffy, but at least has generic transforms for error recoveries, turning errors to successes of a different type and so on. You end up with far less boilerplate.
Well, PLs with effect systems are basically meant to solve exactly this problem.
E.g. a generic `map` function can become throwing if it handles throwing lambdas, but are otherwise non-throwing - this is pretty much the main pain point with Java's checked exceptions.
I’m not so sure. The page goes over how it works in Scala 3 and it’s a little bit cleaner. But there is some nicety in handling return and exception uniformly in some cases.
Although INTERCAL's "come from" provided the opportunity to implement a gloriously concise multi-threading syntax/mechanism [1]!
As some readers may not be familiar with the name Xavier Leroy, I just want to emphasize that he is one of the people behind OCaml and a leading figure promoting Rocq/Coq.
That, and the main author of CompCert [1], as well as (apparently) the author of the original threading support in the Linux kernel [2].
IIRC He was also the author of the original LinuxThread glibc pthread implementation back in the '90 until it was replaced by NPTL in the mid '00.
For French speaking people, Mr. Leroy gave a complete lecture at Collège de France. Available on Youtube.
Does implementing algebraic effects requires stack switching support? If so, I wonder what runtime cost we must pay when heavily using algebraic effects. Is there any empirical study on the performance of algebraic effects implementations?
Not necessarily. You can implement them using a monad. See https://dl.acm.org/doi/10.1145/2804302.2804319. That said, in GHC Haskell the implementation on top of stack switching seems to outperform other implementation strategies. See https://github.com/ghc-proposals/ghc-proposals/blob/master/p....
In OCaml 5, we’ve made it quite fast: https://kcsrk.info/papers/drafts/retro-concurrency.pdf. For us, the goal is to implement concurrent programming, for which a stack switching implementation works well. If you use OCaml effect handlers to implement state effect, it is going to be slower than using mutable state directly. And that’s fine. We’re not aiming to simulate all effects using effect handlers, only non-local control flow primitives like concurrency, generators, etc.
Kind of.
Suppose one of your effects is `read()`, and you want to be able to drop in an asynchronous implementation. Then you'll either require something equivalent to stack switching or you'll require one of the restrictions to asynchronicity allowing you to get away without stack shenanigans -- practical algorithms usually start requiring stack switching though.
You can get a lot of mileage out of algebraic effects without allowing such ideas though. Language constructs like allocation, logging, prng, database sessions, authorization, deteterministic multithreaded prng, etc, are all fairly naturally described as functions+data you would like to have in scope (runtime scope -- foo() called bar() -- as opposed to lexicographic scope), potentially refining or changing them for child scopes. That's a weaker effect system than you would get with the normal AE languages, but there are enough concepts you feasibly might want to build on such a system that it's still potentially worthwhile.
I found it interesting to read this with my Haskell effect system Bluefin[1] in mind.
Bluefin has what this book calls "exception capabilities"[2] (checked ones, as I guess all exception capabilities are), although Bluefin refers to "capabilities" as "handles" (i.e. "handles to an effect"). However, no special syntax or implicitly passed arguments are required. The handle is just a normal value that you pass around as a function argument. I often get the incredulous question "but won't that become really tedious?". My experience is no, quite the opposite, it's not tedious it's in fact very convenient and straightforward to be able to specify precisely where these capabilities go without having to rely on type inference. Passing capabilities as values also allows you to take advantage of language features around function arguments, such as unused argument warnings and the converse "you should have provided this argument but you didn't" errors.
I find the idea of "linear continuations in OCaml" (where the handlers are deep) amusing. It doesn't seem widely appreciated that these are already in basically every language, and called "function calls". That is in fact the implementation of Bluefin's Coroutine[3] type (and Stream[4], which is just a specialisation of Coroutine):
newtype Coroutine a b e = MkCoroutine (a -> Eff e b)
"Algebraic" effects in Bluefin can be obtained by defining Coroutine handles for every element of your algebraic signature, again no special syntax, no special typing rules, no special support in the run time system. However, there is one downside: because Bluefin just piggy backs off the host run time system all the continuations are "linear" or "single shot" (or perhaps more accurately, "affine" or "at most single shot", because exceptions use the continuation zero times). This simplicity plus the paucity of examples that truly require multishot continuations makes the trade off well worth it in the practical use cases I have.
When it comes to type systems, the simplicity of passing handles as normal Haskell values means that all complications to do with subtyping and row typing are absent. Rather than a "row type" of effects we just pass in as arguments the handles for effects we want available in a function. The only innovation of Bluefin in terms of the type system is to extend the state tracking of Haskell's ST monad[6] to arbitrary collections of effects[7], not just mutable state references.
In summary, if people are interested in checking out a production ready, battle tested, simple Haskell effect systems that overcomes every challenge raised in this article (apart from the support of multishot continuations) then I recommend they check out Bluefin[1]. You're welcome to ask questions or share comments at any time on the Bluefin issue tracker[8].
[1] https://hackage-content.haskell.org/package/bluefin-0.2.0.0/...
[2] https://hackage-content.haskell.org/package/bluefin-0.2.0.0/...
[3] https://hackage-content.haskell.org/package/bluefin-0.2.0.0/...
[4] https://hackage-content.haskell.org/package/bluefin-0.2.0.0/...
[5] https://hackage-content.haskell.org/package/bluefin-0.2.0.0/...
[6] https://www.stackage.org/haddock/lts-23.24/base-4.19.2.0/Con...
[7] https://hackage-content.haskell.org/package/bluefin-0.2.0.0/...