5 ms·

There's been a lot of discussion about undefined behavior on HN recently, and I'm gradually starting to question if the conventional approach to compilers might

There's been a lot of discussion about undefined behavior on HN recently, and I'm gradually starting to question if the conventional approach to compilers might be a giant dead-end. In this case, our conventional languages provide no way for a programmer to say "I care about overflow". Because face it, the vast majority of programs a compiler sees are written extremely sloppily. Most of the time there's this huge disconnect between the amount of effort the programmer and the ghost of the compiler writer are putting into considering such situations. Now, most of the time this disconnect is a good thing. Division of labor ensures that the work of the compiler writer is amortized across many many programmers. But the discussion around undefined behavior is a sign that the load on the compiler writer has gotten too onerous, to the point that everybody is paying a cost (in reduced performance, in increased compiler complexity leading to reduced compiler stability, in compilers antagonistically interpreting standards like lawyers) for a level of correctness along one narrow dimension that only a tiny fraction of users actually care about. What if we instead said, "compilers will never ever consider overflow" and let those who care about overflow fend for themselves in the source language? Among other things that would allow integers to always be the word size of the computer they're running on. (My interest in these questions stems from trying to program in an idealized assembly language for the past year: http://github.com/akkartik/mu http://github.com/akkartik/mu. After writing 10kLoC of assembly to build a simple text editor (http://akkartik.name/post/mu http://akkartik.name/post/mu) I'm surprised to find it quite ergonomic. High level languages today seem to provide three kinds of benefits over traditional/ugly assembly: expressiveness (e.g. nested expressions, classes), safety (e.g. type checking) and automation (e.g. garbage collection). An idealized assembly language gives up some expressiveness, but doesn't seem to affect the other benefits. As such, it's at an extreme end of the trade-off I describe. I'm hoping my experience will largely translate even when Mu eventually implements a high-level language.) Edit 21 minutes later: For reference, here's how I've been thinking about undefined behavior while building Mu: https://github.com/akkartik/mu/blob/5dd82a8a70/001help.cc#L40 https://github.com/akkartik/mu/blob/5dd82a8a70/001help.cc#L4.... Comments most welcome.

mempko 11y ago
With every additional compiler check, you reduce the set of possible programs. It would be interesting if the checks could be easily programatically defined and inserted by those who care. I think Perl6 is probably the best modern compiler that allows this. I agree, it should not be the compilers job to decide the set of possible programs. The hardware guys figured this out long ago. Afterall, CPU registers are untyped.
- akkartik 11y ago
  Can you elaborate on what checks Perl6 permits programmers to ask for?
  - raiph 11y ago
    Aiui you can have any checks you want. Aiui, simplifying, every operation is a function call so you just write a function body that corresponds to what you want the operation to be with the checks you want.
nkurz 11y ago
In this case, our conventional languages provide no way for a programmer to say "I care about overflow". What if we instead said, "compilers will never ever consider overflow" and let those who care about overflow fend for themselves in the source language? Does specifying an an unsigned type like size_t (as the author suggests in the last paragraph) achieve most of this? It's slightly backward, in that it's telling the compiler that overflow is not explicitly prohibited, but I think it usually has the same effect of preventing optimizations based on the assumption that signed overflow is not allowed.
- akkartik 11y ago
  Yeah, it's probably as reasonable a hack as you can hope to find in the context of C. The thing to watch out for is that you'd end up with different semantics in arithmetic operations. Right-shift wouldn't sign-extend, for example, that's the first one that comes to mind. Weirdly enough, in my project above I ended up eschewing unsigned ints and just relying on signed numbers everywhere. I have to take a big hit on performance by adding a couple of asserts that consistently enable this without undefined behavior (and I might still be missing something), but performance hasn't been an issue so far. I just don't want to think about whether I might want to perform subtraction down the road when I create a new int. "Unsigned integer" is an oxymoron since integers are defined to include negative numbers.
  - nkurz 11y ago
    "Unsigned integer" is an oxymoron since integers are defined to include negative numbers. That's an odd definition of an oxymoron. While "integer" if unmodified does include negative numbers, isn't "unsigned" just an adjective, restricting the general category to the subset to the non-negative subset? For example, is "white swan" an oxymoron because swans can be both black and white? Interestingly, my first reaction reading your linked code was that not all "integer overflow" is undefined, only signed integer overflow. Regardless of technical correctness, I thought about suggesting that it would read more clearly if you specified "signed" and "unsigned" rather than using "integer" to refer to what programmers refer to as "signed".
jmgao 11y ago
> In this case, our conventional languages provide no way for a programmer to say "I care about overflow". GCC and clang have builtin operations that return whether they overflowed (bool __builtin_add_overflow(T a, T b, T* out), etc.). Similarly, Rust has wrapping, checked and saturating versions of all of the operations as methods on the integer types.

mempko 11y ago

With every additional compiler check, you reduce the set of possible programs. It would be interesting if the checks could be easily programatically defined and inserted by those who care. I think Perl6 is probably the best modern compiler that allows this. I agree, it should not be the compilers job to decide the set of possible programs. The hardware guys figured this out long ago. Afterall, CPU registers are untyped.

akkartik 11y ago
Can you elaborate on what checks Perl6 permits programmers to ask for?
- raiph 11y ago
  Aiui you can have any checks you want. Aiui, simplifying, every operation is a function call so you just write a function body that corresponds to what you want the operation to be with the checks you want.

nkurz 11y ago

In this case, our conventional languages provide no way for a programmer to say "I care about overflow". What if we instead said, "compilers will never ever consider overflow" and let those who care about overflow fend for themselves in the source language? Does specifying an an unsigned type like size_t (as the author suggests in the last paragraph) achieve most of this? It's slightly backward, in that it's telling the compiler that overflow is not explicitly prohibited, but I think it usually has the same effect of preventing optimizations based on the assumption that signed overflow is not allowed.

akkartik 11y ago
Yeah, it's probably as reasonable a hack as you can hope to find in the context of C. The thing to watch out for is that you'd end up with different semantics in arithmetic operations. Right-shift wouldn't sign-extend, for example, that's the first one that comes to mind. Weirdly enough, in my project above I ended up eschewing unsigned ints and just relying on signed numbers everywhere. I have to take a big hit on performance by adding a couple of asserts that consistently enable this without undefined behavior (and I might still be missing something), but performance hasn't been an issue so far. I just don't want to think about whether I might want to perform subtraction down the road when I create a new int. "Unsigned integer" is an oxymoron since integers are defined to include negative numbers.
- nkurz 11y ago
  "Unsigned integer" is an oxymoron since integers are defined to include negative numbers. That's an odd definition of an oxymoron. While "integer" if unmodified does include negative numbers, isn't "unsigned" just an adjective, restricting the general category to the subset to the non-negative subset? For example, is "white swan" an oxymoron because swans can be both black and white? Interestingly, my first reaction reading your linked code was that not all "integer overflow" is undefined, only signed integer overflow. Regardless of technical correctness, I thought about suggesting that it would read more clearly if you specified "signed" and "unsigned" rather than using "integer" to refer to what programmers refer to as "signed".

jmgao 11y ago

> In this case, our conventional languages provide no way for a programmer to say "I care about overflow". GCC and clang have builtin operations that return whether they overflowed (bool __builtin_add_overflow(T a, T b, T* out), etc.). Similarly, Rust has wrapping, checked and saturating versions of all of the operations as methods on the integer types.