21
$\begingroup$

Consider the following C# snippet:

Object bad= null;
Console.WriteLine(bad.ToString());

This is valid C#. It will raise a NullReferenceException which can be caught and handled. On the other hand, the most obvious equivalent code in C or C++ (dereferencing a null reference or pointer) corresponds not to the defined behavior of throwing an exception, but to undefined behavior.

How, generally, are such situations handled when transpiling code with defined behavior in one language into another language in which a close literal translation of the code would result in undefined behavior?

The following seem like reasonable options:

  • Refuse to translate.
  • Generate code to raise an exception, if the target language has exception handling structures.
  • Substitute some type of zero behavior, such as performing a nop or returning 0 or an empty string as applicable.
  • Do anything - the behavior of the transpiler is undefined. The transpiled code in the target language might erase the developer's hard disk, spam naughty pictures all over the Stack Exchange Network, hack the Pentagon, or raise the dead.

Is there a standard practice?

A similar situation could happen when transpiling from a language in which integer overflow results in odometer wraparound (and thus might be a common practice or shortcut) into a language in which integer overflow is undefined behavior. Would a transpiler be expected to implement odometer wraparound checks and handling into the transpiled code, or would raising an error or terminating the program on wraparound be acceptable?

$\endgroup$
2
  • $\begingroup$ As another option, How about trap the NULL pointer dereference and throw it? $\endgroup$
    – Joshua
    Jun 30, 2023 at 4:19
  • 4
    $\begingroup$ Is this PLDI's first Hot Network Question? If so, congrats! :D $\endgroup$ Jul 1, 2023 at 4:27

6 Answers 6

34
$\begingroup$

The default approach for any transpiler is to match the source language semantics, producing additional code to ensure this. Sometimes that can be quite a lot of additional code. Most transpilers aren't striving for line-for-line correspondence or human editability, so in itself this isn't an issue.

In this case, that would be your "generate code to raise an exception" option — that means that any dereference that could be null needs a guard generated for it, and you may need to implement an exception system in your output runtime or align the existing one with your source language. Virtually all transpilers need to add some additional code like this in the output where the languages are not extremely close to one another, and it ensures that the output code does something very close to what the programmer expected, preserving the behaviour of their program.

Sometimes this won't be worthwhile, or is barely possible. It's reasonable to make one of the other choices too, particularly when transpiling to very limited targets. Both rejecting programs that use features you don't (yet) want to implement, and blindly generating undefined behaviours in the output are not uncommon. Sometimes they do both, when precisely identifying what to reject is too hard to be worthwhile; in these cases you're essentially telling the user to validate the code themselves.


This is not unique to transpilation, and compilers for restricted platforms commonly need to make the same choices (e.g. the architecture has a more limited word size). This may not be a problem in practice for the purposes of your compiler; it's also possible to allow disabling the safety checks at the user's option. As a default, matching the source-language semantics is the usual starting point, but deciding to compromise on this in specific cases is both reasonable and common.

Some transpilers are aiming more at translating code from one language to another one time, with the idea that the output will be taken and edited manually from then on. There have long been "Java to C#" translators, and vice-versa, Python's 2to3, and so on. For these, human legibility is more valuable, and indicating where manual review is required may be more useful.

$\endgroup$
2
  • 5
    $\begingroup$ The point in your 2nd-to-last paragraph is important. Consider that many programming languages have array bounds checks, but most hardware doesn't. So array indexes must all be compiled into code that checks the index (except for constant indexes in arrays with static size). $\endgroup$
    – Barmar
    Jun 29, 2023 at 14:01
  • $\begingroup$ It is also possible to implement this particular check on many platforms without adding null checks throughout. In fact, that's how the C# runtime implements null checks for field offsets below 64kB - it installs a segfault handler (access violation, in Windows terms) which, depending on the details of the segfault, throws an exception and continues. $\endgroup$
    – user253751
    Jul 24, 2023 at 18:26
21
$\begingroup$

You can of course choose to do any of the options you listed (or anything at all, really), though some of them may make your users rather unhappy. But let’s suppose we agree that it is valuable to aim for a sound translation of the source language: we want to ensure all of its guarantees are preserved.

One strategy that satisfies this soundness criterion is to reject all programs. No accepted program fails to preserve the source language’s guarantees, so the criterion trivially holds. Of course, this is not very helpful, either. We generally also want to strive for completeness: we want our compiler to accept all valid source programs.

If you commit to both soundness and completeness as your goal, and the target language has no ability to reliably trap on such behaviors, then you have one option and only one option: insert additional dynamic checks unless you can statically prove they are unnecessary. In the case of null pointers, this means adding a dynamic check around every single pointer dereference that has any possibility of dereferencing null. In the case of integer overflow, this means adding a dynamic check around every arithmetic operation to ensure overflow does not occur.

Note that implementation-specific techniques for enabling trapping on null pointer dereferences or integer overflow are insufficient if you are compiling to a target where such things are truly undefined behavior (in the C sense) because the compiler will still optimize your program assuming they will never happen. So in order to preserve soundness, it is really your obligation to make absolutely certain they cannot and do not.

In some cases, compromising on completeness may be more practical. Perhaps certain programs can be statically rejected even though they are otherwise valid programs in the source language, and those restrictions are not so austere that your users find them unpalatable. But generally it is ill-advised to compromise on soundness, especially when you cannot limit the consequences of the soundness holes (as is the case with C-style UB).

One final option is, of course, to compile to a target where such things are well-defined (which could include generating machine code itself). But I imagine that, if you had that choice, you would not be asking this question.

$\endgroup$
6
  • $\begingroup$ ///...because the compiler will still optimize your program assuming they will never happen.// Of course, if a transpiler has to add extra code to prevent a compiler from converting a sequence of operations that would have been useful if processed "in a documented manner characteristic of the environment" into some broken and useless nonsense, that may make the code less efficient than it would be if targeting a compiler that didn't perform the "optimization". $\endgroup$
    – supercat
    Oct 5, 2023 at 19:50
  • $\begingroup$ @supercat Sure, but this is why targeting modern C implementations is essentially a tradeoff: you get very good portability and avoid having to reimplement low-level optimizations yourself, but you have to program to the model those implementations provide. If you want, you could choose to target some “portable assembly language”, like LLVM IR or C--, or you could even target a C implementation that doesn’t do those optimizations. But then you have to do a lot more work yourself. $\endgroup$
    – Alexis King
    Oct 5, 2023 at 20:01
  • $\begingroup$ In many cases, the only way from preventing clang and gcc from performing transforms that would be incompatible with application requirements would be to generate code that blocked useful optimizations as well, meaning a transpiler author who wants those optimizations will have to perform them in any case. The only question is whether the transpiler has to also include logic to block phony "optimizations". If clang and gcc had modes that held back the more aggressive optimizations without having to block the useful ones, that would make things much better, but as yet they don't. $\endgroup$
    – supercat
    Oct 6, 2023 at 17:17
  • $\begingroup$ @supercat That is a baseless assertion. Many optimizations are exposed after iterated program transformation, including inlining, constant propagation, and interprocedural analysis. These transformations can (and regularly do) expose opportunities to apply the optimizations enabled by UB, even if it is not immediately obvious from the structure of the sources. $\endgroup$
    – Alexis King
    Oct 6, 2023 at 21:52
  • $\begingroup$ Referring to the example in my answer, how could a transpiler benefit from an implementation's ability to optimize out functions whose results are never used, even in cases where the functions can't be proven to terminate, if the only allowable behaviors for a function that fails to terminate but has no other side effects would be to either hang or behave as a no-op? So far as I can see, the only correct way for a transpiler to uphold the latter requirement if it can't prove termination would be to add a dummy side effect, whose presence would prevent the useful optimization. $\endgroup$
    – supercat
    Oct 6, 2023 at 22:19
14
$\begingroup$

There are two approaches to transpilation: one is to preserve the structure of the code as much as possible, the other is to preserve the behaviour of the code as much as possible. This choice is probably the first one you will make in a project to create a transpiler, since it fundamentally determines what the transpiler is useful for.

Once you have made that decision, the answer is straightforward:

  • If you want to preserve the code structure rather than its behaviour, then you would generate code which is lexically similar to the source code but doesn't necessarily have the correct behaviour (even having undefined behaviour, in this example).
  • If you want to preserve the program's behaviour, then you would generate code which checks for null and throws an exception, because that's what the behaviour of the source program is. So you might write something like checkNull(bad).ToString(), where the helper function checkNull is part of a runtime library that the transpiled code relies on.

Of course, the above is a bit of a false dichotomy, since your project might have a goal of preserving behaviour in easy cases and preserving code structure where the alternative is impractical or expensive, even if not impossible. Still, this is the same fundamental decision you have to make based on what your transpiler is supposed to be useful for.


It might seem obvious that preserving program behaviour is always preferable ─ and for many use-cases it is ─ but nonetheless there are transpilers which don't aim for that, which evidently are useful for some people. One which comes to mind is Transcrypt, which transpiles from Python to Javascript, but in many cases doesn't preserve program behaviour exactly (e.g. it compiles Python's unbounded integers to Javascript's numbers, which are only exact integers in a certain range). Transcrypt's design rationale is explained here:

Starting out from the fact that Transcypt should be 100% CPython compatible would be very clear and unambigous, and in that sense attractive. However with current technology it’s also completely off-limits for any viable real world development, directly competing with JavaScript in the area of speed and compactness.

Transcrypt's users don't seem to be bringing out pitchforks over it, and indeed the project specifically exists because exactly preserving the behaviour of Python code is unnecessary for many users and requires much larger Javascript files.

$\endgroup$
8
$\begingroup$

I don't know if there is a standard practice, but this is what I would do: I would define each behavior and implement what I defined.

This would mean that sometimes, I would insert a check and raise an exception or crash if it fails (bounds check).

Sometimes, I would use a zero value, which I would define as the value returned by the no-argument constructor of the type (returning a value from an if statement that has no else and wasn't executed).

Personally, I would refuse to translate only if the construct itself is invalid in the source language.

And I would never just do anything if the construct is well-defined in the source language because that is breaking the contract of the language.

I'm writing a C backend for my language. All signed arithmetic is defined as two's-complement in my language, and you can use different operators for crashing on overflow, saturating on overflow, or wrapping around. But it is always defined.

How did I do it in C where signed arithmetic is famously full of UB? I wrote two's-complement arithmetic using unsigned arithmetic which is much better.

Then, to generate code for that arithmetic, I just generate calls to those functions I wrote instead of straight arithmetic. (I made the functions all static and defined them in a header, so they'll probably be inlined.)

Sometimes, you'll have to do the extra work for something like that.

But NEVER break the contract of the source language. Users would bring out pitchforks.

$\endgroup$
6
$\begingroup$

There is no standard practice, but I can give the example of the HotSpot Java runtime.

In Java, nulls are handled in various ways, with performance tradeoff going both ways depending on how relevant a technique is to a given situation:

Explicit runtime null check

The simplest approach is to insert code to check the nullness if a value before attempting a dereference, before every access, as you suggested yourself. This check adds branching instructions and will make the code bigger than not doing them at all (albeit not that much). It also adds a runtime speed penalty.

Static null check

If the compiler can statically prove that an object pointer cannot possibly be null, it can skip the aforementioned check. There are many situations in which this can happen.

Object obj = new Object();
obj.toString(); // obj is obviously not null at this point
if (obj != null) {
  obj.doStuff(); // The programmer already did the check for us
}
obj.x = 12; // An explicit null check guard will be inserted here
obj.y = 34; // ...but if the above line runs, obj has been proven to not be null

Implicit runtime null checks

Implicit null checks is the most complex approach, and isn't doable on all platforms as it relies on both hardware expectations and OS features.

Sometimes, thanks to runtime profiling in JIT-enabled interpreters, the compiler sees that a value (typically a function parameter) has never been null, but cannot prove it with absolute certainty. It may as a result skip the check altogether, but with a twist: a signal handler is registered at the OS level so that any page fault (including null dereference) would be caught by HotSpot, after which the engine can attempt deoptimizing the faulty method and restoring a stack in a stable state. This is very costly, so this optimization should only be done as a safety net when we don't expect a value to be ever null. After the deoptimization path has been taken, the function should be recompiled with a more traditional explicit null check in case other null values are encountered later.

Again, this assumes many things about the OS and the memory management unit: page 0 mustn't be mapped, the OS must allow userland programs from catching page faults, the OS must provide sufficient information on the state of the program at the time of the fault so that a stack can be restored, etc..

$\endgroup$
3
$\begingroup$

If one is targeting a language which leaves various behavios undefined in order to, among other things, accommodate (on a quality-of-implementation basis) dialects which extend the semantics of the language by defining the behavior of constructs in more cases than mandated by the Standard, it may make sense to have a transpiler specify that it is only intened for use with specific dialects of that language.

Suppose, for example, if a language specifies that a side-effect-free loop, even if infinite, will have no side effects beyond possibly delaying--maybe even indefinitely--the execution of some or all following actions. If one is targeting C implementations that do not offer such a guarantee, it may be necessary to generate code which performs a "dummy" side effects on each iteration of any loop that can't be proven to terminate. If, however, one targets dialects of C which guarantee not to add arbitrary side effects to loops, even if they would run infinitely, then one wouldn't need to add such side effects, and one could allow a compiler to perform useful optimizations which would otherwise be blocked by dummy side effects.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .