New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Static exception handlers (i.e. well-disciplined gotos!) #5879
Comments
Comment author: @alainfrisch Some micro-benchmarking: =================================================== exception Cont of int let f1 a x = let f2 a x = let f3 a x = let f4 a x = let () =
|
Comment author: @alainfrisch I've created a branch in the SVN (branches/static_exceptions) to experiment with this idea. |
Comment author: @bobzhang actually I have came across some bugs which the outer catch catches an inner exception(not I expected), this feature may help avoid such bugs |
Comment author: @gasche Could you maintain a specification of where static raises are valid? If I understand correctly, you currently explicit rule out static raises from function subexpressions, and try..with subexpressions. I must say I would more confident in an "opt-in" static validation (only explicitly selected forms are safe) rather than the current "opt-out" mechanism (explicitly forbid some constructs). I tried wreaking havoc with object methods, but they desugar into Pexp_function so they're safe by chance. let test = Fatal error: exception Failure("Unbound static exception Foo") I would suggest a post-translation validation pass, at the typed-tree level, that would just iterate on subexpressions of staticcatch and check that the raises are valid. That would allow to keep an implementation-specification simple and readable in one place, independently from the code sprinkled all along the Pexp->Texp translation pass. |
Comment author: @alainfrisch Static raises are also now explicitly disallowed under functors and classes. Indeed, it might be more robust to check well-formedness of static raises as a post-processing pass. Doing it on the typedtree will not be very different from doing the check during type-checking. I would rather do it on the Lambda code, where e.g. functors are already turned into functions. But we should then keep locations in the lambda code, which is not currently the case. Anyway, apart from implementation choices, the first question is whether such a new control flow feature deserves to be included in the language. |
Comment author: @alainfrisch I've lifted the restriction on try...with blocks: a static raise can traverse normal exception handlers. This gives a nice way to escape a try...with block in order to preserve tail recursion: let rec foo x = |
Comment author: @gasche If I understand correctly, the compilation strategy (either in bytecode or nativecode) is to, at the time of static raise, pops all the dynamic traps that where placed in the context since the static catch. In particular, this change does not affect the code generated (and the performances) for static raises that are outside any dynamic exception trap, such as all the static raises currently produced by the pattern matcher compiler. |
Comment author: @alainfrisch Gabriel: yes, exactly. |
Comment author: @alainfrisch I've written a blog post about this proposal: |
Comment author: @Chris00 Just a silly question: why is the local function not inlined? |
Comment author: @alainfrisch
This is not silly at all! My understanding is that the code of the local function is indeed inlined, but the reference to 'a' still points to the closure, which is thus still allocated. |
Comment author: @bobzhang I want to add that Stream parsers may benefit from such extension |
Comment author: @gasche As per my understanding, this feature got a big "meh" from the maintainers (with mention that OCaml exceptions are already much more efficient than the competion, you ungrateful folks!), so it's more or less on hold for now. |
Comment author: @lefessan Maybe an alternative approach would be:
By the way, I use local exceptions a lot... |
Comment author: @alainfrisch
Not from me! And apparently, Fabrice is also in favor of "something like that". Hongbo mentioned some interesting use for compiling stream parsers. So count at least three maintainers interested in the feature :-)
Performance is just one of the three reasons to motivate the feature (and we could add a forth one: avoid breaking tail-recursion); the most important one is in my opinion that the feature documents (i) the fact that the exception cannot escape; (ii) the fact that the exception is raised for control-flow with a well-defined target, not for error report with an unknown handler. This is really a very useful control flow feature... I should probably have called the proposal "intra-procedural gotos with arguments" instead of "local exceptions" (and used a different syntax as well). I would most often use it to share a "default" continuation in code like: try (sometimes with arguments) where I would certainly not introduce an exception...
I don't see the point of hiding a useful and light feature (no declaration) into a more heavy syntax, which changes the behavior (w.r.t. tail-recursion, backtrace) of an existing feature. If we add support something to the compiler, the best way to document it is with a proper syntax. |
Comment author: @gasche I think the "code sharing" aspect could be successfully worked around by an escape analysis for local function that are only used for code sharing in this way. It should be reliable (use the exact same static criterion to decide which call places are correct) and efficient. I'm a bit less convinced about the real-world use of the exception escape analysis for those that are really used for control flow instead of just avoiding code duplication in tail positions. Local exceptions are not idiomatic for now (you have my support on #5955, though), what I've seen in the wild is Exit, and in this case you must forbid any external calls, which I think rules out most code that could benefit from the feature (short of a much too serious may-raise analysis). That could still be interesting, so I'm not saying that nobody should consider working on it :-) On a more general point, Alain, here is "the point" you say you don't see: adding a fresh new feature to a language increases its width, which is the number of different concepts one must understand to work reasonably with code found in the wild or that oneself writes naturally. Each new feature addition must be weighted in terms of the added expressiveness vs. the cost of a feature addition (this increased "width", plus risk of implementation bugs, tools update, etc.). The C# language designers, for example, have an informal "-100" rule ( http://blogs.msdn.com/b/ericgu/archive/2004/01/12/57985.aspx ) where discussion of a new feature don't begin in the state "I don't know whether we want this feature", but in the state "We don't want it.": it is not enough for a language feature to simply be an improvement over not having it for the specific programs it was designed for. One "bad" thing with your feature is that it adds no new dynamic semantics, it doesn't allow to write shorter programs to do harder things, it is only motivated by "intentional" performance considerations (that in some designer's books are not part of the semantics surface of a programming language; they are in fact, but they're still the vilain petit canards of language design): it's not about what the programs compute, but how. If it is easy to get the same performance benefits by static analysis of an already-existing feature, there is absolutely no reason not to: you get the good performance bonus, without the bad enlargment of your language definition. On the other hand, some language feature allow "exponential" gain in expressivity: they are not expressible in a local way otherwise, or not having them badly breaks composability. For example, getting rid of first-order functions requires non-local transformations (not reasonable to expect of an user by hand). Even for "intentional" performance-oriented features, composability of the performance model can be important: getting rid of unboxed array and record for floats, relying instead only on the local-reference heuristic for float unboxing, breaks composability as you cannot anymore split a computation handling unboxed floats across several modules. I personally like static raises (and have thought about them before, but never dared to suggest that as a surface level feature) -- I'm the kind of people that likes the idea of an explicit "tail" keyword ("tail f x") for guaranteed-terminal calls. But it is in the middle ground between the features that are easy to replace by local optimization and a small compromize (I think the "code sharing" part of it fits this description), and those that cannot be expressed as local optimizations for composability reasons (I think the exception escape analysis part of it may be in this category, even though it might be reasonable with local exceptions; the fact that the feature fundamentally relies on static exceptions not crossing function boundaries forbids any kind of composability). So I understand that opinions differ, and that there are people for and people against the feature, with none of them being wrong. That said, it is a great feature for an intermediate language to have. |
Comment author: @alainfrisch
This would cover the example I gave, but not: try Also, how would you support: try If you replace the static raise by local function, you won't be able to express that the body of this local function is not covered by the (regular) exception handler. In addition (and related) to the semantical change, there is also the fact that if the shared continuation does a tail call, it might end up in non-tail position. But fundamentally, yes, I agree that a better compilation of local functions used to share continuations would already be an excellent thing.
Expressiveness is not the only good property of a language. Being able to express explicitly important invariants (checked by the compiler) and proposing a style which avoids programming mistake (unlike using "raise Exit" only to discover later that the exception can also escape from an inner function call; or using a local function, which will end up covered by an inner exception handler) and encourage code sharing are important as well. The fact that the same construction have these two qualities, plus a natural compilation scheme (and predictable performance, unlike compiler optimizations), while reusing existing machinery in the compiler back-end, is a good indication that this feature deserves to be considered as a first-class construction.
I don't know how many times I'll have to repeat that performance consideration is not the only reason for the proposal.
I can understand that people are not convinced, and I won't push too much for the feature, but I don't accept the "there is absolutely no reason". Yes, there are reasons to prefer an explicit construction. It makes the code more self-describing and more robust to future evolutions which could break the optimization. One reason I like OCaml is that I can get a good idea of the performance profile without having to understand potentially complex (and often ill-documented) automatic optimizations. Another reason is that it allows me to express invariants (like immutability of some data structures), even if this doesn't change expressiveness of the language or its performance. |
Comment author: @gasche Pardon me if I wasn't clear, the "there is no reason not to" part was of course not aimed at this precise language feature, for which I believe your reasons are well-articulated and convincing. It was an abstract remark of language features that are trivially subsumed by a static analysis (of which we don't have many examples of, as they tend to never become language features in the first place). Your latter examples are interesting but vicious :p. You mess with the difference between local sharing functions, that can only be optimized in tail contexts, and the static raises that in some sense create the tail contexts by themselves, making them applicable in some more cases. |
Comment author: @alainfrisch
You know you can always count on me :-)
The way I see it is that encoding the shared continuations as local functions is just a "trick", which works only in some cases and has negative side-effects (like breaking tail context). |
Comment author: @gasche Good points. It might be possible to also generate good code for local functions in non-tail contexts (with a 'call' and 'ret' but less heavy stuff in the middle), but we probably don't want to go into that. |
Comment author: @alainfrisch Cf #6242 for a proposal to improve compilation of local functions used to share a continuation. |
Comment author: @alainfrisch I've attached local_exn.diff, which extends the language with a new construction to create a local exception: let exception A of .... in It implements a simplification (in bytecomp/simplif.ml, enabled only in native code) to turn such exceptions into static ones (Lstaticcatch/Lstaticraise). For each declaration, the simplifier attempts to rewrite all try...with blocks in its scope in order to turn raises into staticraises (and eliminate the handler from the try...with block, and potentially the try..with block itself if it becomes empty). If this process allows to remove all occurrences of the exceptions, this is assumed to be valid. Otherwise, no optimization is done for the local exception. I'm confident (but not 100% sure) that this is sound. Anyway, this allows to use the existing notion of exception and get the benefits of my original proposal. One would certainly need some way to force the compiler to complain if a given local exception cannot be turned into a static one, though, because the optimization is rather fragile (e.g. we only need an inner "try..with" block with a catch-all case to prevent the simplification). This is a quick hack, very lightly tested. Comments are still welcome! |
Comment author: @gasche I think that, from a language design aspect, this is a good path to take (when you design for inclusion in an existing language). It would indeed be nice to have extension_points attributes for "this must be a local-raise" and "this must be tail-rec". |
Comment author: @lpw25 Would it not be simpler to detect all raises that are surrounded statically by a matching try..with block, and turn those into static raises? That would seem to be a more robust optimisation, and would work for exceptions that are not defined locally. This also seems somewhat related to Pierre's unboxing and inlining work, maybe it would fit in with the proposed new compilation phase. |
Comment author: @alainfrisch
Unfortunately, it's not that easy (and this is why I still consider that having a dedicated language feature would be a better solution):
let rec f x = If you cannot remove the try...with block (and you cannot do it if you don't control the Foo exception),
(It's very useful to be able to escape from one or several try...with blocks like that.) or even: try It's very hard to turn the "raise Foo" into a jump to the Foo handler. This assumes that Foo and Bar are different exceptions, but there is usually no way to prove it. Having the exception defined locally and enough restrictions to ensure it cannot escape seems to be a natural solution. |
Comment author: @alainfrisch Resolving as "won't fix". There is no strong support for adding a dedicated language feature that corresponds directly to the internal static jump construction. We will rather look into compiling existing idioms (locally-defined exceptions, local functions used only in tail position, etc) to make use of static jumps. |
Original bug ID: 5879
Reporter: @alainfrisch
Assigned to: @alainfrisch
Status: resolved (set by @alainfrisch on 2017-03-02T15:32:38Z)
Resolution: won't fix
Priority: normal
Severity: feature
Category: language features
Tags: patch
Related to: #4800 #6242
Monitored by: @whitequark @Drup @bobzhang meyer @gasche meurer @lefessan @diml @ygrek @chambart @jberdine @jmeber @hcarty @avsm @Chris00 @yakobowski @alainfrisch
Bug description
There is a class of uses of exceptions within a single function body to express interesting control flows:
Complex nested loops, with exceptional exit conditions.
Sharing continuations / early returns , as in:
try
match ... with
| Int x -> raise (Cont (string_of_int x))
| String s -> raise (Cont s)
| Tuple -> ...
| Foo -> ...
with Cont s -> "lit:" ^ s
(An alternative in this specific example is to introduce a local function, which works well because the raise is in terminal position.)
However, exceptions have there own drawbacks:
It is more difficult to reason with them; there is always the risk of forgetting to catch them locally and have them escape from the function.
Runtime cost (even if exceptions are very quick, there is still an allocation for the exception and some overhead associated to the handler).
Exceptions must be declared. If the exception arguments depend on some of the local type variables in a polymorphic, the exception must be defined locally within a local module (using locally abstract types). This is heavy syntactically and induces some extra runtime cost.
These drawbacks motivate a proposal for lightweight static local exceptions: such exceptions can only be raised locally within the catch-block body (and not inside a nested function). Technically, this can be implemented using the Lstaticcatch/Lstaticraise already available in the Lambda internal representation. I attach a very quick and dirty proof of concept for this proposal, which piggy-backs the syntax for standard exceptions (try/raise) and polymorphic variants, so as to allow writing:
try
... raise (`A (foo, bar)) ...
with `A (x, y) -> x + y
File attachments
The text was updated successfully, but these errors were encountered: