Structurally-Typed Condition Handling | Hacker News Reader

Structurally-Typed Condition Handling

journal.infinitenegativeutility.com

55 pointstodsacerdoti20 comments

Note to the reader: the article talks about modeling the Common Lisp condition system which is more general than an exception system.

In an exception system, when you signal a condition (“throw”) the stack is unwound until the exception is caught or the stack exhausted.

In a general condition system the stack is searched for a handler; that handler is free to return (at which point the stack is unwound, and then the handler exits, same as catching an exception) or continue (e.g. free some disk space and then have the write operation retry, or return infinity from a divide by zero error).

Fun fact: at one point in Rust's history, it too had conditions. They ended up being removed well before 1.0.

was is too costly (memory/instr) or too difficult to model/type properly ?

https://github.com/rust-lang/rust/issues/9795 and the various things linked from it (prs, commits, etc) are the best way to get the context.

So algebraic effects?

Yes -- I think historically the power of condition handling was not well understood and algebraic effect handlers were a "rediscovery" coming from well-studied category theory (Plotkin, Power, and Pretnar).

If you want to play with "structurally typed condition handling", then the Koka language has "row-typed algebraic effect handlers" that compile to C: <http://koka-lang.org>

Yes, algebraic effects. They are equivalent to the Common Lisp condition system, except they're formulated in a way that survives the static typing discipline that is not enforced by the compiler in dynamically-typed CL.

Lawvere theories are also relevant. Bartosz Milewski has a nice description at https://bartoszmilewski.com/2017/08/26/lawvere-theories/

What does this have to do with algebra?

"Algebraic Effects" is sort of a misnomer.

It's the name given to a specific idea being (re)explored in programming languages. Basically it's a try-catch except when you catch the error, you can do something, then return to where the exception was thrown and continue from there.

The second half of the article is similar to the idea of Algebraic Effects.

Here's another article explaining Algebraic Effects: https://overreacted.io/algebraic-effects-for-the-rest-of-us/

(Abstract) algebra is essentially the approach of 'what can I do with this?' (as opposed to, for example, 'what is this made of?', etc.). The nice thing about algebraic constructions is that they can be re-used in many different situations, as long as we can 'do the things' that it relies on.

In high-school algebra, the variables 'x', 'y', etc. are mostly assumed to stand for numbers; but we still solve problems by chaining-together some basic 'things we can do'. For example, if we're given 'a + b = 2 × b' and we want to find an expression for 'a', we can do the following:

    a + b = 2 × b             (given)
    (a + b) - b = (2 × b) - b (subtracting from both sides preserves equality)
    a + (b - b) = (2 × b) - b (re-group + and -)
    a + 0 = (2 × b) - b       (replace 'x - x' with '0')
    a = (2 × b) - b           (replace 'x + 0' with 'x')
    a = (b + b) - b           ('2 × x' with 'x + x')
    a = b + (b - b)           (regroup again)
    a = b + 0                 (another 'x - x')
    a = b                     (another 'x + 0')

Note that the above doesn't actually rely on 'a' and 'b' being numbers, or +/-/× being numeric addition/subtraction/multiplication; they can be anything, as long as they satisfy 'x - x = 0', 'x + 0 = x', etc.

"Interfaces", as found in Java, PHP, StandardML, etc. are algebras: as long as our value implements some interface Foo, we don't care what the implementation actually is. In fact, OOP was originally described in terms of "mini algebras" (what we would now call a "public interface", or "API").

The idea behind Algebraic Effects is that side-effects, like printing out strings, or sending network requests, can be treated in terms of 'what they do' (like an interface), rather than having to care about the implementation. A good example is code which has an input-reading effect: to run it, we must provide some implementation of 'input reading'; but the code will work the same regardless of whether we implement that effect by e.g. reading from the process's stdin handle, or from a GUI text box, or from a hard-coded string, or whatever.

Adding to your explanation, the connection with Common Lisp's condition handling (which is a sort of generalization of exception handling) is that the side effects are something that happens in addition (or instead) of the expression returning a value. But if we want to do stuff besides returning, operationally we might just pause the evaluation of the expression, do our stuff, and then either resume it, or abort it and do something else.

So to evaluate a expression print("a") we pause evaluation, do the printing, and then resume it by returning () (or whatever value that print returns). So a language that has algebraic effects (or, equivalently, Common Lisp condition system) will be able to implement expressions that print to the terminal.

Obligatory link to “ What is algebraic about algebraic effects and handlers?” https://arxiv.org/abs/1807.05923

As well as several hours of video lectures that go along with it:

https://youtu.be/atYp386EGo8

Something similar can be achieved by using explicitly named continuations, though they carry more overhead in the happy path than exceptions (but are far cheaper to throw and catch!)

https://gitlab.com/xmdr/ananke/-/blob/master/drafts/notes/co...

Is it just me, or do restarts sound a bit like coroutines combined with ADTs? In Python or JavaScript, you can use the yield keyword to “yield” control to the calling code along with a current result. If the yield type was an enum/variant (for example, a result), then it would be similar to the concept of a restart.

This could work, I think, but you'd introduce a lot of complications and costs. Comparable to the decision to use exceptions (and some kind of try/catch) versus error propagation. Every single caller between the handler and condition site has to be able to handle both the happy path (got a result) and unhappy path (got a condition).

Another issue is just in performance. In an error or try/catch system you unwind the stack along the way. In a condition system, you don't. If you insisted on manually passing them up until you find a handler (or not, in which case it may become an effective noop), you have to touch all of that "is it a condition or result" logic all the way up, and then resume all the way back down, and then return to the top of a loop because you could get another condition. So you'd end up writing something more like this:

  do {
    result = call(...);
    if is_condition(result) {
      // possibly handle it or re-yield
      switch(result) {
        log: ...
        other_condition: ...
        default: yield result;
      }
    }
  } while(is_condition(result));

It should work, but it seems like it would be unpleasant to work with. With a condition system, you may implement it in a way that forces this kind of costly search through the call stack, or you could register the handlers and avoid this costly backtrack and resume operation.

> Every single caller between the handler and condition site has to be able to handle both the happy path (got a result) and unhappy path (got a condition).

This isn’t terrible, 2 relatively popular languages, Rust and Go, do not have exceptions and do require the caller explicitly handle errors. Rust even has a question mark operator to make error handling this way a bit more ergonomic.

> Another issue is just in performance. In an error or try/catch system you unwind the stack along the way. In a condition system, you don't.

That makes sense. I’m curious if this is something that can be optimized statically by a compiler.

This is a good article about the benefits of conditions and restarts, but I've always been a bit suspicious of adding special-purpose mechanisms for this. I think you can do something similar with normal functions (closures) and datatypes, but first some motivation:

One thing that exceptions don't interact with very well is concurrency. For example, the Alice ML programming language[1] had a nice approach to concurrency using futures where you could just insert a "spawn" keyword in front of any expression to make it run in a background thread, returning a (transparent) future for the eventual result. This was pretty neat, but it fell apart somewhat around the use of exceptions. That is, given code like the following:

  let x = some_computation()
  handle DivByZero() => ...

you can't just simply put a "spawn" in front of some_computation() because now any exception raised will happen in the background thread, which doesn't have the exception handler on the stack. (At least, that's how I remember Alice ML working, and that's how it works in most languages with exceptions).

My feeling at the time was that rather than exception handling walking up the stack to find a handler, the try/catch (or handle) statement should instead create a closure at the point it is executed that is then passed down as part of the dynamic environment to subsequent calls. The raise/throw statement would then find a matching closure from the dynamic environment and immediately call it at the point the exception is raised. This makes exception/condition handlers into normal functions, and also means that this dynamic environment can be copied to background threads when they are spawned.

In this approach, restarts can be handled via normal datatypes. That is, the code that was raising an error would do something like this (pseudocode):

  type restart = Skip | Retry | Abort
  if malformed(record):
    let restart = signal MalformedRecord(record)
    match (restart):
       on Skip -> /* do nothing */
       on Retry -> parse(record)
       on Abort -> return
    end
  end

and callers would then do something like:

  try parse(stuff)
   on MalformedRecord(record) -> Skip
  end

The language I was designing at the time was agent-based and a message sent to an agent would start a new transaction. There was a special "fail" statement that could be used to completely abort the current transaction and signal a failure back to the caller, providing an escape hatch when you really did want to unwind the whole stack (and cancel any spawned background tasks).

Anyway, this was fun to think about again. There's so much more design space to explore around error handling IMO.

Edit: I should add that this is pretty much how explicit promises work in most languages that use them, where error handlers are attached to a promise object that is passed down to asynchronous tasks. So in a sense my sketch here is just another form of syntactic sugar over that existing pattern.

[1]: https://en.wikipedia.org/wiki/Alice_(programming_language)

So, Koka?

Reply on news.ycombinator.com