3 ms·

This was posted as a comment on the article, where his comment system mangled my shifts thinking I was trying to use HTML: I'm not sure I like allowing invalid

This was posted as a comment on the article, where his comment system mangled my shifts thinking I was trying to use HTML: I'm not sure I like allowing invalid intermediate results. It means that there are many expressions whose correctness is dependent on a compiler, and more specifically a compilation target. It's not hard to come up with an example of an expression that is valid, but only calculable on specific architectures. If none of the examples that Arseniy came up with satisfy you, think of something absurd like (x << 20000) >> 19999. As it stands, no computer architecture I know of could calculate the proper result. But with a clever compiler you can derive an equivalent program that will execute correctly. If you have the clever compiler and allow invalid intermediate results, your program will execute correctly. If you have the same constraints and a slightly dumber compiler, then you will trap. There are probably examples that are flat out impossible to execute without trapping on particular architectures, but fine on others. As a result, architecture and compiler details will start bubbling up and affecting program correctness. The ways in which this will happen will be far more perfidious (if less common) than the current architecture details program writers often must consider such as word length.

repsilat 15y ago
Most of the time you'd want to use these sorts of integers you wouldn't use shift operators - as the author said, > Of course there are specialized domains like DSP that want > saturation and crypto codes that want wraparound; there’s > nothing wrong with having special datatypes to support > those semantics. More to the point, I think you'd want to standardise on the optimisations a compliant compiler can/must implement. Algebraic rearrangements might be the way to do it, but I'm not 100% sure even they're possible. For the example given: result = result * 10 + cursor - '0'; If `result` is unsigned then I think the compiler has to assume that `cursor` is greater than the character literal for zero. That's obviously true to us, but I'm not sure that sort of thing could be (reliably) implemented programmatically, even for simple cases.
- sirclueless 15y ago
  > More to the point, I think you'd want to standardise on the optimisations a compliant compiler can/must implement. That has two problems. 1. Once you start formalizing optimizations that must occur, you run the risk that some optimizations will be impossible or have horrible performance on some compilation targets. For example saying something like "an expression made up of only 32-bit addition operations must successfully evaluate if the result fits in a 32-bit integer" might be really painful to implement on an embedded system with only a few 32-bit registers. 2. Even if the correctness of an expression can be determined statically and reliably by the language standard, if the correctness of an expression depends on optimizations performed, then someone reading a program needs to know all of those optimizations. For example, it is often quite a laborious task to tell whether a C expression will evaluate correctly, because C has occasionally bizarre rules for the promotion of the types of operands. Fortunately there are some decently reliable heuristics that apply, that let you assume that an unsigned char added to an unsigned long will probably promote the unsigned char to a long and do the addition. Now imagine instead of understanding C's type system, you had to understand the algebraic reductions available to your compiler. The volume of arcana required to determine whether an expression will be correctly optimized or not would be absurd. And heaven forbid you tried to modify the expression. You might add a simple constant somewhere that breaks an optimization and suddenly the expression fails to evaluate when x is 2^31 - 1 or something. When you consider these things, hopefully you will see why it is so much more preferable to just enforce that all intermediate results must be valid, and have the program writer do the algebraic reductions necessary to make (x << 20000) >> 19999 evaluate with no invalid intermediate values.

repsilat 15y ago

Most of the time you'd want to use these sorts of integers you wouldn't use shift operators - as the author said, > Of course there are specialized domains like DSP that want > saturation and crypto codes that want wraparound; there’s > nothing wrong with having special datatypes to support > those semantics. More to the point, I think you'd want to standardise on the optimisations a compliant compiler can/must implement. Algebraic rearrangements might be the way to do it, but I'm not 100% sure even they're possible. For the example given: result = result * 10 + cursor - '0'; If `result` is unsigned then I think the compiler has to assume that `cursor` is greater than the character literal for zero. That's obviously true to us, but I'm not sure that sort of thing could be (reliably) implemented programmatically, even for simple cases.

sirclueless 15y ago
> More to the point, I think you'd want to standardise on the optimisations a compliant compiler can/must implement. That has two problems. 1. Once you start formalizing optimizations that must occur, you run the risk that some optimizations will be impossible or have horrible performance on some compilation targets. For example saying something like "an expression made up of only 32-bit addition operations must successfully evaluate if the result fits in a 32-bit integer" might be really painful to implement on an embedded system with only a few 32-bit registers. 2. Even if the correctness of an expression can be determined statically and reliably by the language standard, if the correctness of an expression depends on optimizations performed, then someone reading a program needs to know all of those optimizations. For example, it is often quite a laborious task to tell whether a C expression will evaluate correctly, because C has occasionally bizarre rules for the promotion of the types of operands. Fortunately there are some decently reliable heuristics that apply, that let you assume that an unsigned char added to an unsigned long will probably promote the unsigned char to a long and do the addition. Now imagine instead of understanding C's type system, you had to understand the algebraic reductions available to your compiler. The volume of arcana required to determine whether an expression will be correctly optimized or not would be absurd. And heaven forbid you tried to modify the expression. You might add a simple constant somewhere that breaks an optimization and suddenly the expression fails to evaluate when x is 2^31 - 1 or something. When you consider these things, hopefully you will see why it is so much more preferable to just enforce that all intermediate results must be valid, and have the program writer do the algebraic reductions necessary to make (x << 20000) >> 19999 evaluate with no invalid intermediate values.