Index: doc/proposals/exceptions-assert.md =================================================================== --- doc/proposals/exceptions-assert.md (revision 2ec81ca5d342fd71e6a860a7a29ad59792257970) +++ doc/proposals/exceptions-assert.md (revision 2ec81ca5d342fd71e6a860a7a29ad59792257970) @@ -0,0 +1,387 @@ +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.