Exceptions without polymorphic effects

[kyouko-taiga]

I'm opening this discussion to talk about the design of exceptions we'd like for Hylo.

There are two things I'd like to achieve ideally, none of which is properly addressed by Swift:

1. Keep the syntactic ceremony to a minimum.
2. Avoid the proliferation of polymorphic effects.

Note that I don't consider avoiding function coloring a goal. That is because if we opt for a world where functions are non-throwing by default (and I currently have a strong bias toward such a world), then we need a way to stop the propagation of exceptions and satisfy the contract of a non-throwing function anyway. So we may as well require a try-catch statement to call a throwing function.

If we take Swift as a starting point, none of my goals are properly addressed. That's because Swift wants a try before every throwing outermost expression and because the ability to throw is an effect that has to appear in the API of every maximally generic higher-order function. The first issue is easy to lift, though: just allow any throwing function to be called without ceremony from another throwing function. The second is more tricky but arguably even more important. We'll have unsafe as another effect and I would be very sad if all maximally generic higher-functions had to be written <E>([E](T) throws unsafe -> U) rethrows reunsafe -> V.

One thing I'd like to try is to encode the capability to throw as an object rather than an effect, which is an idea coming from research around Scala. Here is how the basics would look in Hylo:

// In the standard library:
@intrinsic
fun throw(_ e: any Error, throws?: Throws) -> Never

// In user land:
fun risky_business(_ n: Int, throws?: Throws) -> Int {
  // Note: no syntactic ceremony here
  n + even_riskier_business()
}

fun even_riskier_business(throws?: Throws) -> Int {
  throw(Catastriphe() as _)
}

public fun main() {
  try {
    let x = risky_business()
  } catch {
    case let e: Catastrophe { print(e.description()) }
    case _ { print("Something failed") }
  }
}

An instance of Throws represents the capability to throw an exception. Here, both risky_business and even_riskier_business are throwing because they take such a capability as parameter. We can call the latter from the former without ceremony because we already know that risky_business is throwing. However, we need a try-catch statement in main, which is not throwing.

The question marks after the names of some parameters indicate that they are implicit, saving us from having to pass throws explicitly to every function. Implicit parameters are necessary to alleviate the syntax burden of capabilities are object (and that's why they've been implemented). Their syntax is still subject to bikeshedding, but that is orthogonal to this discussion.

To guarantee that we cannot call throw outside of a try-catch statement, we must make sure that instances of Throws can only be construced in a try-block and can never escape it. Fortunately our type system can do that. We only need to make Throws a non-copyable type with no constructor and have the try-catch statement "project" it the try-block. Another way to think about this setup is to imagine that the try-catch statement is implemented by the following function:

@intrinsic
fun try<E1, E2>(
  _ action: [E1](throws?: let Throws) -> Void,
  catch handler: [E2](any Error) -> Void
) -> Void

Since throws is a let parameter that isn't copyable, it cannot escape a call to action.

The advantage of passing throws as a parameter instead of using an effect is that we can no longer need polymorphic control effects on higher order functions. For example, consider Collection.map:

public extension Collection {
  public map<E, T>(_ transform: [E](Element) -> T) -> Array<T> {
    ...
  }
}

We don't have to make any change to this function to let it accept throwing and non-throwing function (or even unsafe functions!) That is because the ability to throw can be captured in the environment of the lambda passed to transform. For example:

public fun main() {
  let things: Array = [1, 2, 3]
  try {
    let other_things = things.map((x) => risky_business(x))
  } catch {
    case _ { print("Something failed") }
  }
}

In the call things.map((x) => risky_business(x)), the lambda is implicitly capturing throws, which is an implicit value available in the try-block. The type of the lambda is [remote let Throws](Int) -> Int, meaning that it is throwing, and we can happily specialize Collection.map for [Self: Array<Int>, E: remote let Throws, T: Int].

[Note: Using eta-expansion we could even write things.map(risky_business).]

The next challenge is to compile this thing! Here I think there are two main ways we can approach the problem. The first is to say that every function is in fact allowed to throw under the covers. Then we could implement transfer of control back to the caller the same way a C++ implementation does. I'm sure other people know waaaaay better than me about how that works, so I'll let them jump in if necessary.

The second approach would be to translate a throwing function into one that returns either a result or an error. In other words, we would compile fun f(_ x: T, throws?: Throws) -> U as though it has been written fun f(_ x: T) -> Union<U, any Error>, where any Error is an existential containing th thrown error.

The problem with this strategy is that in general a higher-order function has to assume that it received a throwing function, and therefore it must be compiled as though it was throwing. That means a lot of functions would have Union<U, any Error> in their ABI, just in case they are called with a throwing function.

Note that we're only talking about ABI here. At the language level, you would not have to wrap a call [1, 2, 3].map((x) => x + 1) in a try-catch statement even if map was sitting behind an ABI boundary. The compiler would simply force-unwrap the result.

The proliferation of these Union results is a little sad but note that it would only be necessary for higher-order functions. In a world where functions are non-throwing by default, we can know for a fact that (Int) -> Int never throws. Further, allocating Union<U, any Error> instead of just U is probably not that bad, but maybe I'm too naive on this point.

Finally, in places where we can monomorphize everything, we would be be able to conclude that a higher-order function is in fact not throwing. That is because once we've determined that Throws doesn't occur in the parameters or environment of a lambda, then that lambda can't possibly throw. More generally, we can determine whether a lambda can throw if its type doesn't have any existentials or generic parameters.

[dabrahams]

Function arguments aren't the only place where throw effects can (in principle) become polymorphic. For example:

protocol X {
  foo() throws
  bar() throws
}

struct A: X {
  foo() /* throws */ { ... }
  bar() /* throws */ { ... }
}

f<T: X>(b: X) rethrows(if T:X throws) { ... } // mythical syntax
f(A()) // nonthrowing

I'm not saying we should cover this kind of case, but if we are not going to, we should understand why we're not doing it!

[dabrahams]

One argument against might be: C++ noexcept has exactly this kind of expressivity and nobody ever knows how far to go in describing throwing effects (my fault!).

This reminds me that sometimes there will be code that a programmer knows can't throw, but where that fact can't be encoded in the type system, either because of expressivity limitations or because it's only dynamically knowable. I guess we can have an assert_nonthrowing(somelambda) call to clean those cases up.

[dabrahams]

I must admit that although I have also had a long-held preference for a world where functions are non-throwing by default, I'm beginning to question whether that makes sense for Hylo. There are two reasons:

1. By making partially-mutated objects inaccessible (as we plan to), we are creating a world where a programmer very seldom needs to care which things might throw
2. I've been told by concurrency folks like @ericniebler that in highly-concurrent programs, almost everything needs to be cancellable—and cancellation is going to be implemented by throwing.

What's left are those functions used in error recovery, which must be non-throwing.
I'm also not sure I'm thinking about this question clearly 😉
Anyway, I'd be more comfortable with our choice if we thought through the implications of an alternative model with the opposite default.

[dabrahams]

It seems to me that putting that kind of error reporting, and especially exception-eating (except when a different strategy for success is available—which is extremely rare), in any work that is ever spawned is an anti-pattern. If you're going to do it, you had better be aware of how it plays out in a concurrent context, and so you can catch cancellation in a separate clause and do whatever you're going to do with that.

[ericniebler]

Sorry, are you referring to Dimi's code, which I appropriated?

[dabrahams]

I'm referring to both the examples in your post. Maybe I'm missing something, but it seems to me that that kind of error handling code should almost always be at the "top level" of code, outside of spawns, and if code that is spawned ever does that, it had better be aware that it was or could have been spawned, or the reporting would lead to chaos. Awareness is all you need in order to explicitly handle cancellation properly.

In other words, yes, cancellation is not failure, but I'm not sure acknowledging that in the language design is worth the wrinkles it will cause.

[lucteo]

On concurrent code always being cancellable.

I would tend to disagree (in the absence of empirical studies that gives us a better idea on the usage of general concurrent code).

First, cancellation is not something that is specific to concurrency. There is no intrinsic reason for making a concurrent sort cancellable while making a single-threaded sort non-cancellable. This needs to be left at user's discretion, and this needs to be application-specific. Some applications may require the sort calls to be cancellable, while others may require them to be not cancellable.

The cancellation is cooperative, and thus there is a cost associated to supporting cancellation, even for success cases. This means, that if we want to highly optimize the success case, we may not want to add support for cancellation. To have an informed opinion, the programmer probably needs some data with the ratio between success cases and failure cases, and determine the impact on the application that the two alternatives have.

Also, there are operations for which we always need a result. There is no point in cancelling them if the parent task needs its result too, assuming the result of the parent is always needed too.

In my mental model, cancellation is similar to throwing; that should happen only if the callee cannot produce a result value. Concurrent code shall be able to be fully encapsulated into a function, thus cancellation of the concurrent code is equivalent to the cancellation of a (possible single-threaded) function.

I don't think we have enough data to assume that, the general usage of concurrency will need cancellation. Until that point, I think it makes sense to keep things simple and don't assume cancellation at every step.

[lucteo]

On the difference between cancellation and errors

P1677R2 makes the distinction between serendipitous-success and errors, and then indicates that P0709R4 may be used/extended to support serendipitous-success. But, my understanding was that we were planning to use a mechanism close to P0709R4, so we should have a common mechanism to implement both errors and serendipitous-success.

Personally, I don't see good reasons to distinguish between errors and serendipitous-successes in Hylo. They are just "alternative ways" to exit a function/block.

I always like to think of functions as producing a Union<R, A1, A2, A3, ...>, expressing all the possible alternatives from returning values from that function. In many programming languages the values of types A1, A2, A3, ... we call errors. But the term error here is just a convention here. Having the result Union<R, E1, E2, E3, ..., SS1, SS2, SS3, ...> in which some of the alternatives are called errors and other alternatives are called serendipitous-successes, is just a different naming for the same convention.

Given that the mechanisms for implementing errors and serendipitous-successes is the same, I see no good reason to distinguish between the two.

I think we are having this discussion mostly because in C++ the term error has a long and complicated history; if we would have come from a different language (e.g., Haskell), I don't think this discussion would make much sense anymore.

[dabrahams]

We should talk about how/if this technique generalizes to unsafe. I'm quite unsure that it should do so.

If the idiom is “write safe components using unsafe constructs,” it seems to me,

let b = pointers.map((p) => unsafe p[])

doesn't need to be

let b = unsafe pointers.map((p) => unsafe p[])

(this is what happens with try in Swift incidentally). Uttering unsafe once is sufficient to mark the code for scrutiny. The only thing I want to be forced to do beyond that is explicitly mark the surrounding function safe or unsafe.

So what kind of effect threading is really needed here?

[kyouko-taiga]

You can write pointers.map((p) => unsafe p[]) but you may also want to write unsafe zip(p1, p2).map((a, b) => a[] + b[]). It should be possible to use only one unsafe introducer to run any number of nested unsafe operations in single expression.

[dabrahams]

Maybe; I'm not 100% sure I agree; but that's an entirely orthogonal question. The question I'm asking boils down to, "if I use an unsafe operation in a larger operation, must that larger operation be considered unsafe in the type system?" I think the answer may be no.

[kyouko-taiga]

I think the answer is: yes, unless you handled then unsafety in the nested operation.

From the perspective of the type system, I see unsafe the same way I see throws. It's a license to use an effect—applying unsafe operations—delivered by an explicit construct somewhere in the call stack. You enter an unsafe region by uttering unsafe, just like you enter a throwing region by uttering try so that you get license to call throws(_:).

The user (or maybe some external proof system) is responsible to guarantee that unsafe operations used in the unsafe region are used in a safe way. So there's nothing to catch, but I don't think the ability to handle an effect is necessary to call that thing an effect. If literature says otherwise, then I'm happy to use another term.

I think we agree that pointers.map((p) => unsafe p[]) is safe because the user (or the proof system) guaranteed the safety of the inner expression. I also claim that pointers.map((p) => p[]) should be a valid unsafe expression. One reason is that I don't want to utter unsafe in front of every pointer dereferencing if I compose them (unsafe p[] + unsafe q[] + unsafe r[] is much more difficult to read than unsafe p[] + q[] + r[]). But even more fundamentally, I want the ability to write that a function is unsafe. At the very least in the standard library we should be able to implement this:

extension Pointer {
  public fun pointee(_ unsafe?: Unsafe) -> Pointee {
    return base as* (remote sink Pointee)
  }
}

We can certainly say that a pointer-to-address cast is an unsafe operation and add unsafe before the return expression. But I think it is the wrong approach because if unsafe e means "I know that e is unsafe, but I did the extra homework to make sure all is well", then AFAICT there's no way to notionally write an unsafe operation like pointee. And if we have to ask the unsafe capability in the API of pointee anyway (no matter how), then I think asking for an extra unsafe token in front of every unsafe operation is just creating noise, just like asking for try in front every throwing expression in a throwing function.

That is why I believe pointers.map((p) => p[]) is a valid expression, only one that requires an unsafe capability to be executed.

[dabrahams]

I think the answer is: yes, unless you handled then unsafety in the nested operation.

What does “handled” mean? The presumption of the compiler must be that you used the unsafe operation correctly once you have marked it. And there's no way for it to know whether you've done that.

Let me say up front that I think I now see how all this works in the type system, so the rest of what I have to say is about the language ergonomics.

just like you enter a throwing region by uttering try so that you get license to call throws(_:).

That's not the only way; if you are in a function marked throws, you don't have to utter try.

But I doubt the same should apply to unsafe, because there are very often still plenty of safe operations in such functions and the unsafe markings help with vetting.

I just don't think the programming model for throwing and unsafe are anything alike. You really don't/shouldn't care about where the throwing operations are, and you shouldn't be relating to them as though they are dangerous. Unsafe operations are still dangerous and calling attention to them is, generally speaking, important.

I think asking for an extra unsafe token in front of every unsafe operation…

Let's say for the time being that I want you to mark any statements having unsafe operations in them.

We can certainly say that a pointer-to-address cast is an unsafe operation and add unsafe before the return expression.

This is a bad example for the purposes of this discussion because it relies on primitives not accessible to normal users. I don't care whether those need to be marked. The question is about the programming dynamic for functions that aren't using these primitives.

I also think that to issue unsafe operations in a function you should have to explicitly declare its implementation either safe or unsafe. Otherwise, a function that uses unsafe operations but is not itself declared unsafe is implicitly claiming to be safe. It seems to me that claim needs to be scrutinized when the function is vetted for correctness, and I'd rather have an explicit marker in the code that says to do so. Of course safe would not affect the API or be part of the function type.

[kyouko-taiga]

Let's keep this discussion about error handling. I continued here #1265.

[dabrahams]

The problem with this strategy is that in general a higher-order function has to assume that it received a throwing function, and therefore it must be compiled as though it was throwing. That means a lot of functions would have Union<U, any Error> in their ABI, just in case they are called with a throwing function.

Isn't it true that any function with parameters has to assume it received an argument containing a throw capability (unless it can see all the details of the type and there is no type-erasure, e.g. an existential, involved)?

[kyouko-taiga]

Yes, that is true. Thanks for pointing that out. It was an oversight on my part.

For the record, here's a one possible way to build a throwing function without mentioning Throws in its signature using my proposal. There are many others.

fun f<A>(x: A) {
  let g = x as! [{remote let Throws}]() -> Void
  g(throws)
}

public fun main() {
  try {
    f(() => throw SomeException())
  }
}

[dabrahams]

Then this approach moves the hylo much further from the implementation tradeoffs of Swift (where you know exactly which things can throw) and much closer to those of C++, where the ABI assumes everything must throw unless otherwise specified. A check-and-branch for errors after every call is presumably a performance-killer. C++ implementations typically use a table-based implementation to avoid that cost in the non-error case, at the expense of poor/unpredictable performance in the error case. This is typically an unacceptable result for low-level systems programmers. I'm not sure this arrangement leaves Hylo with a story for those people. Make of that what you will.

[kyouko-taiga]

You know far better than me about Swift ABI, so I'm ready to take your word for it. But I'm not sure Swift operates that differently, at least across ABI boundaries. To test my assumptions, I compiled this function:

public func foo(_ f: () throws -> [Int]) rethrows -> [Int] {
  try f() + [1]
}

Here's an excerpt of the LLVM IR produced by swiftc, with all optimizations enabled:

define swiftcc %swift.bridge* @"$s4main3fooySaySiGACyKXEKF"(
  i8* nocapture readonly %0,
  %swift.opaque* %1,
  %swift.refcounted* nocapture readnone swiftself %2,
  %swift.error** noalias nocapture swifterror dereferenceable(8) %3
) #1 {
entry:
  %4 = bitcast i8* %0 to %swift.bridge* (%swift.refcounted*, %swift.error**)*
  %5 = bitcast %swift.opaque* %1 to %swift.refcounted*
  %6 = tail call swiftcc %swift.bridge* %4(%swift.refcounted* swiftself %5, %swift.error** noalias nocapture nonnull swifterror dereferenceable(8) %3)
  %7 = load %swift.error*, %swift.error** %3, align 8
  %.not = icmp eq %swift.error* %7, null
  br i1 %.not, label %8, label %common.ret
...
}

We got only one version of foo, which has been compiled as though f was throwing. So even if it gets an argument that can never throw, it still has to branch at the end of the entry. If I read this correctly, that is the same check-and-branch that you're worried about.

Presumably the caller of foo can know whether or not the call can throw because it knows about the effect of the argument that it passed. So it should be able to skip the check. I tried to confirm my intuition with this code:

public func bar(_ g: () -> [Int]) -> Int {
  foo(g).count
}

To my surprise, I discovered that the unoptimized IR of bar does check for an error. The optimized form, however, just inlines the call. A more thorough test would look at the optimized IR of a variant of bar that would call foo behind an ABI boundary.

We should be able to make similar optimizations as Swift. The problem with the model would be that a call to any generic function should be considered throwing in general, before optimizations can prove otherwise. Swift only has to consider calls to functions marked with throws or rethrows. The proof is probably easy to make within a module but probably impossible through an ABI boundary. But in those instances, the user would already be paying for existentialization so I'm not sure the cost of a branch would be relevant. Of course I'm just speculating at this point.

Note that there's probably a few restrictions we could place on Throws to make it impossible to smuggle a capability through type erasure. So if those branches are truly unacceptable, there's still hope for a system that can remove them reliably, even across ABI boundaries.

[dabrahams]

To test my assumptions, I compiled this function:

public func foo(_ f: () throws -> [Int]) rethrows -> [Int] {
  try f() + [1]
}

If you generalize from that example, you will confirm your own assumptions. From an ABI standpoint, that is a declared-to-be throwing function where the caller is allowed not to write try if the closure they pass is nonthrowing. But in Swift, the vast majority of functions are not declared to be throwing.

Also looking at a small example like bar is not all that instructive. Yes, Hylo can make all the same optimizations as Swift when it can see into everything, but then again so can any other programming language. IIUC whole-program (or whole resilience-domain) optimizations are expensive and when programs get big optimizers eventually give up and assume the worst. Up until now, Hylo has had a very (potentially-)efficient ABI model before any interprocedural analysis happens, which makes it attractive for systems programming because of a predictably efficient performance baseline. An “everything can throw” model probably changes that.

[adevress]

C++ implementations typically use a table-based implementation to avoid that cost in the non-error case, at the expense of poor/unpredictable performance in the error case. This is typically an unacceptable result for low-level systems programmers. I'm not sure this arrangement leaves Hylo with a story for those people. Make of that what you will.

If it is of any interest, I can confirm that. Most safety critical code in C++ will de-factor ban exception for this exact reason. This reason is also made worst that the fact that throwing an exception generally dynamically allocate under the hood in C++ due to the fact any type can be an exception.

The few implementations that succefully allowed exceptions in certified code generally:

• Have a statically allocated buffer on startup for the exceptions and a defined maximum size of exception ensured by static analysis.
• Went to a much more rigorous safety certification with heavy static analysis to "simulate" exception annotation

Apex.AI with their work on ROS is one of them. Their slides is a good read about that if the topic interest someone