source: doc/proposals/exceptions-assert.md@ 2ec81ca

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.

Syntax and Usage
----------------
The throws annotations is new a syntax. The design is not final, but for
examples we will use: `throws (EXCEPTIONS)`, where EXCEPTIONS is a comma
separated list of exception signatures. This can happen within the scope of a
forall clause so it can be polymorphic with the rest of the function.

There is no syntax to declare exceptions, although one could be added, they
are effectively declared in the throws annotations.

Throw statements remain, but now they are joined by throw expressions. The
throw expressions return their response value. Throw statements can
(Throw expressions with a response of `void` can be a void expression, in the
few places where a void expression is allowed.)
```
throw Name(Exprs,...)
```
Along with the addition of the expression form, the main change is that the
exception is not an expression, but a literal name and a series of
expressions.

Try statements are the same as the current design except for the catch clauses.
```
catch Name(Arguments...) { ... }
```
Exceptions thrown in the try block are checked for matching handlers. The
match is simply preformed by label name. (Although with type annotations on
the arguments or for the return type, could be extended to involve full
resolution on the signature of the exception.) When an exception is thrown
the matching catch is put onto the stack and run. Running off the end, or
otherwise exiting the catch block, causes a termination and unwinds the
stack.

In addition there is a new statement that can only be used inside a catch
statement (and only in one that can return to the throw).
```
resume [EXPR];
```
This is like a return statement, the expression is required if the exception
expects a value in response. If the expression is present, it is evaluated
before the resume occurs. When the resume occurs, we exit the handler and the
throw finishes execution, resulting in the evaluated value as appropriate.

### Exception Signature Polymorphism
We have everything to make a functional exception handling mechanism.
However, to get a flexible (especially in regards to higher order functions)
system we need a basic level of polymorphism.

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

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.

Examples
--------

### Noreturn Example (Enumeration succ)
A simple example from the enumeration traits, there is a `succ_unsafe`
function in the Serial trait that is wrapped by a `succ` function that adds
some checks and aborts if they fail.

Instead of aborting, it could have an assertion-like exception:
```
int succ(int value) throws(noreturn out_of_range()) {
    if (value == MAX) {
        throw out_of_range();
    }
    return value + 1;
}
```
This serves the same role as the existing function, but combines the succ
with a range check the caller can respond to.

For an example of catching this, consider creating a wrapper to get the
current succeed or abort implementation:
```
forall(T | { T succ(T) throws(noreturn out_of_range(); })
T succ_abort(T val) {
  try {
    return succ(val);
  } catch out_of_range() {
    abort("Attempt to succ to non-existant successor.");
  }
}
```

### Value Resume Example (lookup)
For an example of catching and resuming with a value, consider a map lookup
that throws when you attempt to lookup a key not in the map and a wrapper
that provides 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));
}

forall(K, V | relational(K))
V lookup(map(K, V) const & mapping, K & key, V & defaultValue) {
  try {
    return lookup(mapping, key);
  } catch NoFound(_key) {
    resume defaultValue;
  }
}
```

This may not be the most efficient way to implement a lookup-with-default
function, but it would work. Practically, one would handle the NoFound
directly, even running more complex code or using information not passed
to the lookup, as showed here:

```
// local_var is declared up here.
try {
  function_that_calls_lookup(args);
} catch NoFound(key) {
  if (is_special_key(key)) {
    resume build_default_value(key, local_var);
  } else {
    resume simple_default_value;
  }
}
```

### Void Resume/Terminate Example (Out of Memory)
The third type of resumption is a void return, which you may resume but do
not pass any data back to the throw.

```
try {
  ...
} catch NoMem(size_t target_size, Buffer * buff) {
  if (void * new_buff = realloc(buff->data, target_size)) {
    buff->data = new_buff;
    resume;
  }
}
```

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.

### Polymorphism Example (Save/Restore)
Higher order functions can handle types simply need to polymorphic on the
same exception type as the functions they take as parameters.
```
forall(T, exception E)
T isolate_state(T (*func)() throws (E), State state) {
  // SavedState wraps a State and restores it on deconstruction.
  SavedState _saved = save_state();
  set_state(state);
  return func();
}
```
This isolates a function by saving and restoring state around the function,
where that state is some generic global state. The wrapped function can raise
any of those exceptions and they will pass through the isolateState. When
one of those exceptions terminate or func returns, _saved's destructor runs.

### Polymorphic Error Example (foreach)
Here is a simple example of polymorphism over a higher order function.

```
void print_widget(Widget &) throws (noreturn FormatError());

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

forall([N])
void print_widgets(array(Widget, N) & widgets) {
  // FormatError not handled.
  foreach(print_widget, widgets);
}
```
It is infact too simple as foreach will have the same exception signature
as print_widget and that means print_widgets is not handling the function
nor passing it to its caller.

However, this example (or a version that catches FormatError) will work
because the exception signatures all match.
```
forall([N])
void print_widgets(array(Wiget, N) & widgets) throws (noreturn FormatError()) {
  foreach(print_widget, widgets);
}
```

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

### Rethrows and Conditional Catch
As extension to the core system, we could add rethrowing or conditional
catching to try blocks. There purpose is the same, to allow a handler to
use non-type information to decide if it can handle an exception or not.

If an exception is rethrown or the condition evaluates to false, exception
propogation continues up the stack. As far as control flow goes this should
be the same as not catching it at all.

A rethrowing or conditional catch does not remove the exception it could
catch and handle from the unhandled exception set. Because it may not, so
the type system has to account for that.

### 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.

### 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.