How are exceptions implemented under the hood? [closed]

Just about everyone uses them, but many, including me simply take it for granted that they just work.

I am looking for high-quality material. Languages I use are: Java, C, C#, Python, C++, so these are of most interest to me.

Now, C++ is probably a good place to start since you can throw anything in that language.

Also, C is close to assembly. How would one emulate exceptions using pure C constructs and no assembly?

Finally, I heard a rumor that Google employees do not use exceptions for some projects due to speed considerations. Is this just a rumor? How can anything substantial be accomplished without them?

Thank you.

Solution 1:

Exceptions are just a specific example of a more general case of advanced non-local flow control constructs. Other examples are:

• notifications (a generalization of exceptions, originally from some old Lisp object system, now implemented in e.g. CommonLisp and Ioke),
• continuations (a more structured form of GOTO, popular in high-level, higher-order languages),
• coroutines (a generalization of subroutines, popular especially in Lua),
• generators à la Python (essentially a restricted form of coroutines),
• fibers (cooperative light-weight threads) and of course the already mentioned
• GOTO.

(I'm sure there's many others I missed.)

An interesting property of these constructs is that they are all roughly equivalent in expressive power: if you have one, you can pretty easily build all the others.

So, how you best implement exceptions depends on what other constructs you have available:

• Every CPU has GOTO, therefore you can always fall back to that, if you must.
• C has setjmp/longjmp which are basically MacGyver continuations (built out of duct-tape and toothpicks, not quite the real thing, but will at least get you out of the immediate trouble if you don't have something better available).
• The JVM and CLI have exceptions of their own, which means that if the exception semantics of your language match Java's/C#'s, you are home free (but if not, then you are screwed).
• The Parrot VM as both exceptions and continuations.
• Windows has its own framework for exception handling, which language implementors can use to build their own exceptions on top.

A very interesting use case, both of the usage of exceptions and the implementation of exceptions is Microsoft Live Lab's Volta Project. (Now defunct.) The goal of Volta was to provide architectural refactoring for Web applications at the push of a button. So, you could turn your one-tier web application into a two- or three-tier application just by putting some [Browser] or [DB] attributes on your .NET code and the code would then automagically run on the client or in the DB. In order to do that, the .NET code had to be translated to JavaScript source code, obviously.

Now, you could just write an entire VM in JavaScript and run the bytecode unmodified. (Basically, port the CLR from C++ to JavaScript.) There are actually projects that do this (e.g. the HotRuby VM), but this is both inefficient and not very interoperable with other JavaScript code.

So, instead, they wrote a compiler which compiles CIL bytecode to JavaScript sourcecode. However, JavaScript lacks certain features that .NET has (generators, threads, also the two exception models aren't 100% compatible), and more importantly it lacks certain features that compiler writers love (either GOTO or continuations) and that could be used to implement the above-mentioned missing features.

However, JavaScript does have exceptions. So, they used JavaScript Exceptions to implement Volta Continuations and then they used Volta Continuations to implement .NET Exceptions, .NET Generators and even .NET Managed Threads(!!!)

So, to answer your original question:

How are exceptions implemented under the hood?

With Exceptions, ironically! At least in this very specific case, anyway.

Another great example is some of the exception proposals on the Go mailing list, which implement exceptions using Goroutines (something like a mixture of concurrent coroutines ans CSP processes). Yet another example is Haskell, which uses Monads, lazy evaluation, tail call optimization and higher-order functions to implement exceptions. Some modern CPUs also support basic building blocks for exceptions (for example the Vega-3 CPUs that were specifically designed for the Azul Systems Java Compute Accelerators).

Solution 2:

Here is a common way C++ exceptions are implemented:
http://www.codesourcery.com/public/cxx-abi/abi-eh.html

It is for the Itanium architecture, but the implementation described here is used in other architectures as well. Note that it is a long document, since C++ exceptions are complicated.

Here is a good description on how LLVM implements exceptions:
http://llvm.org/docs/ExceptionHandling.html

Since LLVM is meant to be a common intermediate representation for many runtimes, the mechanisms described can be applied to many languages.