source: doc/proposals/exceptions-assert.md@ b3609b2

Assertion Like Exceptions
=========================
This is a proposal for a rework to the existing exception system.

Motivation
----------
The current exception handling mechanism (EHM) is functional and has wide
use cases. However, there is a certain awkwardness to using them,
particularly the exceptions themselves.

Some of this is just feature incompleteness. But some of it comes down to
a paradigm mismatch. Traditional exceptions carry data and behaviour from
throw to catch - that is, they are objects - to allow for the transfer and
handling of the exception, but CFA does not have an OO design.
Now there are ways to at least lessen this strain (see `Exception.hfa`), but
those tend to limit functionality or are dependent on one or more upcoming
works (such as closed traits or modules).

Instead of trying to solve that fundamental mismatch, this proposal tries to
create exception handling that does not depend on OO-style features.
This restructures the EHM to try and use CFA's existing design patterns.

Design
------
To make exceptions fit better into the rest of Cforall, what if we reused
some of the design that is already in the language: assertions.
The result is a system of checked exceptions that could serve as at least a
partial replacement for the current exception handling mechanism and
exception declarations.

These exceptions work much like existing exceptions, they are raised from a
throw, traverse up the stack to a handler and run the handler.
Where control continues after the routine can vary to mimic both termination
and resumption throws.

An exception is formatted like a function call: `RetType Name(ArgTypes...)`.
The `Name` is a label only used for matching, the ArgTypes give the types of
the data passed from the throw to the handler and RetType can give the type of
the data passed from the handler back to the throw. RetType can also be
`void` to reply with no data, or a noreturn marker to say that control cannot
return to the throw.

This exception signature is usually only written out in full as part of
a function declaration, which says that this function may throw that
exception. Throws and catches will usually replace the ArgTypes with the
arguments or parameters to hold those values.

The actual termination vs. resumption divide comes from the handler. The
handler may `resume`, if it is handling a void or value exception, which
returns control to the throw creating a resumption. If controls runs out
of the handler block, it continues at the end of the try statement after
unwinding the stack.

Throwing expressions (throws or a throwing function calls) must be inside
a function that can throw the exception, or within a catch clause that can
handle it.

There is no case for unhandled exceptions because of the assertion-like part.
Functions are annotated with the exceptions that they throw (thrown within
the function or a called function and not handled). By ensuring that `main`
throws no exceptions, that means all throws will be matched to a try.

Features
--------
The detailed design of the proposal organized by feature.
There are core features (exception signatures, the throw expression and
try statement) followed by extra features. The core features form the minimal
working version of this system and should be understood together.

All syntax given is a mock-up and can be changed.

### Exception Signatures
Exceptions exist as assertion-like addition to a function signature.

An exception signature describes an exception, and consists of a response
type, a identifier as the name and the parenthesized list of comma separated
parameter types.
```
RESPONSE_TYPE NAME(PARAMETER_TYPES)
```
Each exception signature notes an exception that can be thrown.
The parameter types are the types of the values passed from the throw to
the handler and the response type is the type of the value that might be
passed from the handler back to the throw.

These are put into the throws clause of a function,
an optional part of the function signature.
The function signature is just the keyword throws followed by a parenthesized
and comma separated list of exception signatures.
```
throws(EXCEPTION_SIGNATURES)
```
By convention, this goes after the parameter list of the function,
unless the function has a forall list in which case it goes after that.

This doesn't actual do anything, it just annotes what exceptions can come
from this function. Or rather propagate from call expressions that use it.
Expressions and statements also - implicitly - have their own throws clause
of the exceptions that can come from them.
For most expressions and statements it is simply the combined set of
exceptions of their components.

The function's throws clause should match that of its body statement.
Any missing exceptions is a compile time error.
Any extra exceptions should be a warning,
some notation to silence the warning would be provided.

The throws clause does not participate in overload resolution. Once the
overload is choosen, the throws clauses are checked and errors raised
when there is a mismatch.

Two exceptions are the same exception if their name, parameter types and
response type are the same. It should follow the same pattern as function
resolution.

No Return Signature (iterator):
Consider an iterator interface, that returns a value and updates the iterator
in place to produce a value, and throws an exception to indicate the end of
iteration.
```
forall(T, I)
trait Iterator {
    I next(T &) throws(noreturn end_of_iteration());
}
```

Function Exception Separation (too-much-overloading):
Exceptions don't exist in the same space as functions and variables.
The places they can be used only accept exception names so there is no
confusion.
```
int f(char) throws(int f(char));

void g() throws(int f(char)) {
    ...
    int i = f('a');
    ...
}
```
This will always call the function as exceptions are in their own namespace
and do not interact with function names, variable names or trait names.

### Throw Expression
Exceptions come from throw expressions.

A throw expression is made of the keyword `throw`,
the exception name and the parenthesized list of argument expressions.
```
throw NAME(ARGUMENTS)
```
When the throw expression is evaluated all the arguments are evaluated
and then the exception is thrown.
If the handler responds to it, that is the value the expression evaluates to.
If an unwinding is triggered during the handling,
the unwinding starts at this expression.

The parameter types and response type are not explicitly given.
Since the exception must be given in context, it can resolve the expression
against the list of possible exceptions. Annotation casts can be used for
disambiguation when needed, but it shouldn't be a common occurrence.

Although throws are expressions they can, and in some cases should, be used
at the top level as a statement.
+   Value Returning: These should only be used as expressions, it is why they
    are expressions, so the response can be captured and used.
    There should be a warning if the value is not captured.
+   Void Returning: This can be use either as an expression (in a place where
    a void expression is allowed) or as a statement.
+   Non-Returning: As control will never return, they could be put anywhere
    but should only be used at the statement level for clarity of control
    flow.

Value Throw Example (lookup):
Here is a simple example of a throw that both passes a value and uses the
response. If the lookup finds a value, it is returns it, otherwise it uses
a throw to try and find a default value.
```
forall(K, V | relational(K)) throws(V NotFound(K &));
V lookup(map(K, V) const & mapping, K & key) {
    // Internal code equivilent too:
    node(K, V) * node = lookup_internal(mapping, key);

    return ((node) ? node->value : throw NotFound(key));
}
```

No Return Throw Example (iterator):
An iterator that uses an exception to note that the iterator is empty.
```
int next(Iter & iter) throws (noreturn end_of_iteration()) {
    if (iter.size <= iter.position) {
        throw end_of_iteration();
    }
    ++iter.position;
    return iter.data[iter.position - 1];
}
```

### Try Statement
The exceptions are handled by try statements.

The try statement is made up of the try keyword, the try block
and then one or more catch clauses.
```
try {
    BODY
} catch NAME(ARGS) {
    HANDLER
}
```
When the try statement is executed, the BODY is evaluated and then control
continues after the try statement. The try statement is the same as wrapping
the BODY in a compound statement unless an exception is thrown while BODY
is being executed.

When an exception is thrown in the BODY (either directly or indirectly)
that matches one of the catch clauses then that exception is handled by this
try statement. This means the exception does not continue outwards from here.
That binds to the values passed to the throw to the names in ARGS and then
runs the HANDLER code.

Within the HANDLER, you can also respond to the exception with a resume
statement, which is passing to it the response value.
```
resume EXPR;
```
(We also allow just `resume;` for void responses.)
You cannot respond to a noreturn statement, so you cannot use a resume
statement inside a handler for a noreturn expression.

Value Try Example (lookup):
Although you would probably want to implement a separate lookup with default
function, you could implement one as a wrapper:
```
forall(K, V | relational(K))
V lookup(map(K, V) const & mapping, K & key, V & defaultValue) {
  try {
    return lookup(mapping, key);
  } catch NotFound(_key) {
    resume defaultValue;
  }
}
```

Void Resume/Terminate Example (Out of Memory):
Here is an example of void resume (not passing back a value) and also a
termination, where the handler can trigger unwinding.
```
try {
  ...
} catch NoMem(size_t target_size, Buffer * buff) {
  if (void * new_buff = realloc(buff->data, target_size)) {
    buff->data = new_buff;
    resume;
  }
  // If the realloc fails, we go to a recovery path.
}
```
Here, the error cannot be fixed with information, but rather a correction to
the container state. This also shows how resumption is optional (for both
void and value throws) and the handler can instead decide to terminate and
unwind the stack.

No Return Try Example (succ):
There are few functions that are very hard to make complete, any could
require an awkward check before calling it, or the function can report that
with an exception.

For example, a checked successor function for enumerations:
`SomeEnum succ(SomeEnum) throws(noreturn out_of_range())`

This can be used as a check on a loop:
```
int sum = 0;
try {
    SomeEnum e = minimum;
    for () {
        e = succ(e);
        sum += transform(e);
    }
} catch OutOfRange() {
    return sum;
}
```

This pattern could also be used with iterators and be wrapped up in a
control-flow structure for ease of use, like with Python's StopIteration.

### Rethrow (Conditional Catch)
Sometimes the decision if an exception can be handled does not come down
to the location in code and the exception in question; which is how they
base try statements decide it.

This could be implemented one of two ways: a rethrow or conditional catch.
The conditional catch is a bit more straightforward so we will start there.

A conditional catch is part of a conditional clause, and adds an if keyword
followed by a parenthesized boolean expression, the condition.
```
catch NAME(ARGS) if(COND) {
    HANDLER
}
```
When the exception matches a catch clause, after the arguments are bound
to their names but before it commits to handling the exception,
the condition is evaluated.
If the condition evaluates to true the handler runs,
otherwise the exception continues to propagate out and up.

This is a change from the existing syntax `catch NAME(...; ...)` because
the declaration section of the clause (before the `;`) now is a comma
separated list, which could make it harder to see the `;` separator.
That might be fine but it was enough to change my mock-up syntax.

Conditional Catch Example (special key):
Although the predicate can be as complex as it needs to be, using catch
arguments, local varaibles and function calls, it is ultimately just a
conditional expression:
```
catch NotFound(key) if (is_special_key(key)) {
    resume make_special_value(key);
}
```

The rethrow is an equivalent feature, but is organized differently, in a way
that is more flexible but has the same structure. When the rethrow statement
(a `throw` with no exception) is executed the handler stops executing and
the exception propagation continues.
```
catch NAME(...) {
    ...
    throw;
    ...
}
```
Unlike in some other languages, a rethrow just continues the original throw
and doesn't create a new throw with the same or a new exception.

Rethrow Example (special key):
```
catch NotFound(key) {
    if (is_special_key(key)) {
        resume make_special_value(key);
    }
    throw;
}
```

Rethrow Variable Example (metadata):
The rethrow can weave in other code into the check more easily.
```
catch NotFound(key) {
    KeyData meta = get_metadata(key);
    if (is_set("ignore-default", meta)) {
        throw;
    }
    resume get_string("default", meta);
}
```

### Polymorphism
Functions polymorphic over exceptions in throws signature.

We extend forall clauses to include a new type of polymorphic parameters,
that declare exception sets: `exception VAR`. The declared variable may be
used in any throws clause, as you would include an exception in the list.

For example, a higher order function that passes all of its exceptions
through to its caller works like this:
```
forall(T, [N], exception E) throws(E)
void foreach(void op(T &) throws(E), array(T, N) & data) {
    for (i; N) op(data[i]);
}
```

It is important to note it is an exception set, not a single exception. If
the inner function throws one or more exceptions, then foreach throws the
same exceptions. If the inner function doesn't throw anything, then foreach
doesn't throw anything and its caller doesn't have to handle anything.

It should be noted that these exception sets to not interact with concrete
exceptions within the polymorphic functions themselves. They are logically
"packed" when they move from monomorphic to polymorphic code and "unpacked"
when it moves back from polymorphic to monomorphic code.

A new type of polymorphic parameter is added `exception` which is polymorphic
not on an exception, but a possibly empty of exceptions.
A set of exceptions is can be used in an exception signature in the same
way a single exception can be and are traced from callee to caller in the
same way a single exception is.
They do not interact with throws or catches as those work on concrete types.
At the top and bottom of the polymorph call stack concrete functions will
throw and catch the exception, passing through the polymorphic section.

Polymorphic Error Example (foreach):
Here is a simple example of polymorphism over a higher order function.
```
void print_widget(Widget &) throws (void FormatError(Widget &));

forall(T, [N], exception E) throws(E)
void foreach(void op(T &) throws(E), array(T, N) & data) {
  for (i; N) op(data[i]);
}

// Incorrect wrapping:
forall([N])
void print_widgets_ERROR(array(Widget, N) & widgets) {
    // FormatError not handled.
    foreach(print_widget, widgets);
}

forall([N])
void print_widgets(array(Widget, N) & widgets) {
    try {
        foreach(print_widget, widgets);
    } catch FormatError(Widget &) {
        sout | "Opaque Widget";
        resume;
    }
}
```

### Exception Tunnelling
Exceptions can pass through functions they should not interact with.

(Credit to Mike for the original idea.)

Higher order functions that take functions as parameters can "erase"
exceptions from the throws list (including all of them).
If it does so those exceptions can no longer be handled by that function or
any of its callees. If the passed function raises any exceptions, they
skip forward and appear from the call expression where the "erasing" happens.

Here is an overview of some interactions:
```
int high(int op(int, int) throws(A, C)) throws(D);
int passed(int, int) throws(A, B);

int res = high(passed);
```
+   The exception(s) A are not thrown from this expression.
    Thrown by passed and handled by high. Either by being caught by high (or
    some other function between it and the calling of passed) or by also
    being part of D.
+   The exception(s) B are thrown from this expression.
    These are the tunnelled exceptions that pass from the call site of passed
    to this call site of high.
+   The exception(s) C are not thrown from this expression.
    This is just to show that throwing extra exceptions is fine.
+   The exception(s) D are thrown from this expression.
    No interaction with exception tunnelling, they come from high.

Tunnelling Error Example (foreach):
Here is an example of an exception tunnelling though a higher order function.
```
void print_widget(Widget &) throws (void FormatError(Widget &));

forall(T, [N])
void foreach(void op(T &), array(T, N) & data) {
  for (i; N) op(data[i]);
}

// Incorrect wrapping:
forall([N])
void print_widgets_ERROR(array(Widget, N) & widgets) {
    // FormatError not handled.
    foreach(print_widget, widgets);
}

forall([N])
void print_widgets(array(Widget, N) & widgets) {
    try {
        foreach(print_widget, widgets);
    } catch FormatError(Widget &) {
        sout | "Opaque Widget";
        resume;
    }
}
```

Tunnelling Thunk Expansion (sort):
Although the implementation is not set,
the behaviour of tunnelling can also be described by creating a thunk.

Consider the following example were a sort is called with a less than
operation that throws in some way the sort did not expect.
```
forall(T, [N] | { bool ?<?(T &, T &); })
void sort(array(T, N) & data);

struct SomeType { ... };

bool ?<?(SomeType & lhs, SomeType & rhs) throw(RType except(AType)) {
    ...
}

void example_function() {
    ...
    sort(data);
    ...
}
```

Internally this creates an thunk that contains some special code, probably
in the form of some special annotations, but we can represent most of it
with a try statement.
```
void example_function() {
    ...
    RaisePoint: bool ?<?'thunk(SomeType & lhs, SomeType & rhs) {
        try {
            return ?<?(lhs, rhs);
        } catch except(AType data) {
            // Captures the frame and code location.
            RType value = magic_resume_from RaisePoint except(data);
            resume value;
        }
    }
    sort(data);
    ...
}
```

Thunks do lead to issues in life-time management and contribute to the general
thunk problem. (Thunks may also be created when we pass a function to a
function pointer that throws more exceptions, even though there should be
no change in behaviour.)

### Finally Clauses
You could add `finally` clauses to try statements to run when they unwind.

This is a classic tool used to ensure proper scoping of resources, a dual to
destructors which are a OO-ish (not true OO) way of handling the problem.
We can bring the syntax over to the new system:
```
try
    TRY_BLOCK
finally
    FINALLY_BLOCK
```

However, although this does fire with the same timing, when the try statement
is removed from the stack, this does interact with the change in unwind
timing in a perhaps unexpected way. It will run after the exception passes
it and the handler decides to unwind.

A separate construct would be needed if you wanted to run code when the
search leaves that section of the stack, because then you might need a paired
construct to run code when you re-enter it.

Details And Additional Notes
----------------------------

### Performance (Where to Pay Costs)
Although the behaviour has been laid out, the performance has not. We would
like "good" performance of course, but there is a choice between fast tries
and fast throws.

The current system uses fast tries, which means it is designed for very rare
cases, almost always errors.

Fast throws mean that entering and leaving a try block is now more expensive,
but it means throws can be common. Exceptions can now be used for alternate
returns and other relatively frequent cases.

A single choice doesn't have to be made for the entire language. It could
choose differently for different cases or even let the user decide for
different exceptions.

### Implementation
The implementation has not been specified. See the performance section for
fast tries vs fast throws.

The current implementation could be adapted if we want to stay with fast
tries. The exception could become an id and a pointer to stack allocated
storage. If the id can even be contextual and if a function doesn't handle
the exception, it gives a new id to pass onto its owner.

(You might need to modify libunwind to allow returning successfully from an
unwind call without unwinding, but last time I checked that change could be
made in a platform independent part of libunwind.)

### Polymorphic Tracing Details
For simplicity, polymorphic exceptions should probably just be black boxed
and not interact with any other handlers or exceptions except at the edges
where it is boxed and unboxed.

The programming language Flix has effect polymorphism (but not polymorphic
effects, avoid confusing those), which has many of the same design
constraints.

### Polymorphism Ease of Use
It would be nice if the language's defaults were set up in such a way that
the common usage pattern is the simplest/most natural way to write a
function.

For a point of comparison, consider otype (object-type) parameter `(T)` as
compared to the dtype (data-type) parameter `(T &)`. Although dtype is
the more primitive/simplest form, the simplest syntax goes to otype, which is
the most common form. Something similar could be done for higher-order
polymorphic functions.

Something like if a polymorphic function takes another function and none of
them have explicit exception signatures, a exception polymorphic argument
could be added and all the functions may throw that. Details may depend on
how widening works. Also, you must be able to explicitly say that functions
do not throw, doing this to one of the functions (by convention, the main
function, not any function parameters) would disable this feature.

The exact rules should come from usage patterns that emerge once the feature
is implemented.

### Unwind Timing
Although the current implementation can mimic both termination and resumption
exceptions. There is one major difference in the behaviour of the termination
throw and catch, the unwinding of the stack now occurs after running the
handler instead of before.

When the handler is short and operates locally, this is unlikely to matter.
In fact, this can fix some life-time issues (see implementation).
However, if there is a lot of work in the handler we haven't cleared the
stack up or freed up other resources (the destructors haven't run, things
are still taking up stake space, etc.).

If this turns out to be a problem, there should either be a way to force an
unwind in the handler, or make sure local control flow can take us to an
external block to handle the exception.

### Exceptions in Traits
In another way to make exceptions like assertions, they could be added into
traits. They can probably just mixed into the bodies with assertions.

This would generally just be a short-hand, but also offers a tool to
organize exceptions like in effects, which can have multiple options.

### Cancellation
This system is narrower than the current exception system. Rather than trying
to cover every use case directly/with one feature, I would propose another
feature to handle some of the important cases not seen covered here.

The biggest other cases are the non-recoverable cases. These may not be
caught are all (in which case they are the same as an abort) or are caught
and the operation is abandoned. Control then continues from a main loop
(as in an engine or server dispatcher).

For these cases, an unchecked exception that only supports catch-all or our
cancellations might work better. They only information they need to carry is
enough for a user facing error message.

### THE CHECKED EXCEPTION PROBLEM
Yes, this gets an all caps title (it almost got its own section) because the
single biggest concern about this system is the additional workload of
maintaining checked exception lists on all functions. This is a real concern
but I believe this proposal avoids the worst of it.

One part of "the worst of it" is the annotating of many functions that call
some distant helper function that throws an unhandled exception.
At this point, it can be impossible to preform any sort of detailed recovery.
In these cases the exceptions should be converted to cancellations.

In my experiance the majority of exception throws (writen, not fired) are
effectively assertion failures that are only catchable exceptions out of
princible (or are in a long running program were individual operations can
just be written off). Cancellation replaces all of these cases instead of
the new exception system.

Another part is the interaction with higher order functions.
If a higher order function only works with particular exceptions thrown from
the function passed to it, it loses a lot of its flexibility.
Both polymorphism and exception tunnelling are ways to address this problem.
These stratagies both mean you don't need many different variations of those
functions, and hopefully have little (or no) additional code.

### Default Exception Handlers
Handling every exception has often proven more work than people want to put
in. Now, this may not be an issue with fewer more significant exceptions,
but if it is default exception handling within a program might help.

This could be a universal thing, such as triggering an abort or cancellation
if an exception is not handled, or something narrower using assertions or
configuration on the exception itself.