5 ms·

Is it even possible to have zero undefined behavior in languages that allow user-defined pointers? It seems like allowing even just one degree of memory indirec

by kortex 5y ago

Is it even possible to have zero undefined behavior in languages that allow user-defined pointers? It seems like allowing even just one degree of memory indirection creates a singularity beyond which any kind of formal guarantees become impossible. Seems like you'd have to allow only structures which hide memory implementation details if you truly want to avoid all UB. Same goes for any arithmetic which could overflow. That would require kernel devs to radically rethink how they interact with I/O, which would probably require specific architectures. In other words, writing a kernel portable on any of the existing ISAs that is also performant is basically impossible, barring some humongous breakthrough in compiler technology. Seems to me that when it comes to brass tacks, UB is kind of the "we are all adults here" engineering tradeoff that enables shipping fast and useful software, but is technically not strictly defined and thus usually does what you want, but can result in bugs.

immibis 5y ago
Even kernels only interact with memory in reasonably predictable ways. I think they could all be hidden behind such abstractions, BUT it will make the language a lot more complex.
CRConrad 5y ago
> Is it even possible to have zero undefined behavior in languages that allow user-defined pointers? It seems like allowing even just one degree of memory indirection creates a singularity beyond which any kind of formal guarantees become impossible. With untyped pointers, yes. But it seems to me that if you have strong typing for function pointers you could mostly avoid that. > UB is kind of the "we are all adults here" engineering tradeoff that enables shipping fast and useful software, but is technically not strictly defined Well, no, of course it isn't -- the clue is probably in the first half of the name, "Undefined Behaviour"... ;-)
ErikCorry 5y ago
Without concurrency you don't have to have UB to have user-defined pointers. x86 assembly language has no UB and has user-defined pointers.
- ahefner 5y ago
  CPUs can and do have UB in the instruction specifications. x86 definitely does.
  - secondcoming 5y ago
    Indeed, for example the BSR instruction: > If the content source operand is 0, the content of the destination operand is undefined. [0] https://www.felixcloutier.com/x86/bsr https://www.felixcloutier.com/x86/bsr
    - dooglius 5y ago
      No, this is not the same thing as "undefined behavior" in the sense the ISO C spec defines it. The content of the output being unspecified would not, for example, allow the processor to write to some part of memory if the source is zero, or change unrelated registers. x86 is doing "undefined" the right way, unlike the ISO C spec.
      - mpweiher 5y ago
        > No, this is not the same thing as "undefined behavior" in the sense the ISO C spec defines it. Well, it's not UB the way optimiser-extremists (mis-)interpret the ISO C standard.
      - kllrnohj 5y ago
        It's exactly the same as "undefined behavior" in C. The only difference is in the consequences that follow from it when optimizers get ahold of it. If it's undefined behavior if BSR is given 0, then therefore the compiler can assume the value passed to BSR isn't 0 (because it's defined that a well-formed program doesn't encounter undefined behavior). Therefore a check if the value is == 0 can be skipped, because it can't be zero since BSR didn't allow it. And since the code inside the if isn't reachable, that probably means now other things are no longer reachable and can similarly be removed. And etc... That's all the "undefined behavior allows the compiler to murder my cat!" really is - it's just the chain of consequences that result from the compiler following the rules it was told. It was given a rule that a parameter couldn't be null, and so it listened & did what it was told including deleting redundant null checks (since after all, the value was already specified to be not null!). To demonstrate the problem in a different language, let's say I have this code: float asFloat(@Nullable Integer i) { return i == null ? Float.NAN : i.floatValue(); } You'd expect the null check, right? But let's say I call it from this function: void sayHi(@NonNull Integer i) { println("Hello " + asFloat(i)); } The optimizer comes along and inlines the two together and now sees: void sayHi(@NonNull Integer i) { float temp = i == null ? Float.NAN : i.floatValue(); println("Hello " + temp); } Does it still need to keep the null check? After all, I defined that 'i' isn't null, so surely the null check is just unreachable code & can be eliminated, right? If it doesn't, it's obviously wasting performance. If it does, the internet gets angry about the compiler "abusing undefined behavior." Even though as far as the compiler is concerned it isn't undefined behavior! 'i' is defined to be not-null!
kps 5y ago
The original C committee wrote, as part of its guiding principle to “Keep the spirit of C”, that “To help ensure that no code explosion occurs for what appears to be a very simple operation, many operations are defined to be how the target machine’s hardware does it rather than by a general abstract rule.”¹ That is, if you write `a = b + c` you expect the compiler to generate an `add a, b, c` instruction, and if that happens to trap and burn your house down, well, that's not C's problem. I'm convinced that the original UB rule was intended to capture this, and the wording was an error later seized by compiler developers. As evidence, consider Dennis Ritchie's rejection of `noalias` as “a license for the compiler to undertake aggressive optimizations that are completely legal by the committee's rules, but make hash of apparently safe programs”². If anyone at the time had realized that this is what the definition of UB implied, it would have been called out and rejected as well. ¹ https://www.lysator.liu.se/c/rat/a.html#1-1 https://www.lysator.liu.se/c/rat/a.html#1-1 ² https://www.lysator.liu.se/c/dmr-on-noalias.html https://www.lysator.liu.se/c/dmr-on-noalias.html
- gpderetta 5y ago
  > if you write `a = b + c` you expect the compiler to generate an `add a, b, c` this could be violated even by simple optimizing compilers that do constant propagation or strength reductions. Again, if you do not want optimizations -O0 is always available.
  - mpweiher 5y ago
    Hmmm... "To help ensure that no code explosion occurs for what appears to be a very simple operation" How does constant propagation cause code explosion?
  - kps 5y ago
    The statement, in context, is a simple illustration of the principle that C operator semantics were defined by the target hardware. Not a treatise on compiler construction.
  - naniwaduni 5y ago
    It would be nice if optimizing compilers' -O0 weren't completely insane on the assumption that the insanity would get optimized out.
foxfluff 5y ago
> Is it even possible to have zero undefined behavior in languages that allow user-defined pointers? It kinda boils down to what exactly you mean by defined behavior. A C programmer's take might be that you can run a conforming program in an emulated abstract machine and get defined results out of it. And then you can run the same thing on real hardware and expect to get the same result (modulo implementation defined behavior). This definition leaves some things out (e.g. performance, observable effects in the "real world") but it captures the computational semantics. Another programmer's take might be more akin to a portable assembler. In that case, you certainly could define reads and writes for arbitrary pointers, in the sense that they must cause corresponding (attempted) loads and stores at the machine level. However, the definition wouldn't be complete since it inevitably leaves much to the underlying implementation. Thus you could have "defined" C programs that show completely different behaviors depending on which implementation and hardware you used. It would be impossible to say what the program's output must be "in the abstract." For someone who just wants to output assembly, maybe that's fine. I'm not sure other people would be too satisfied with it. An out of bounds write could still blow up your program and be remotely exploitable; practically the same thing as undefined behavior, except that now your compiler is also barred from optimizing. There's quite a bit of tension between these two camps. Alternatively, you could fully define it at a great runtime cost and potential exclusion of real hardware implementations.
remram 5y ago
Undefined behavior means something specific in the standard, it's not just an operation that might do different things on different compilers and machines. It means that if it happens, the program is allowed to do anything and everything, even before the UB is reached. Undefined behavior is breaking an assumption that the compiler is allowed to make. It is probably impossible to make a low-level language with no implementation-defined behavior, but it is certainly possible to make one with no undefined behavior. For example, you can put in your spec that overflowing an unsigned integer can give any value; that is different that putting in your spec that it doesn't happen and if you write it the variable might have no value, multiple values, or burn your socks off. https://en.wikipedia.org/wiki/Undefined_behavior https://en.wikipedia.org/wiki/Undefined_behavior
- comp54321 5y ago
  It's actually impossible as far as I can see as long as you have unsafe memory access via pointers and memory is used to hold information about control flow and local variables, because overwriting memory can then do weird and wonderful things to the state of the program. E.g. local variables can magically change values, but worse, the control flow of your program can be hijacked in pretty arbitrary ways. It would be great if this wasn't possible, because then you wouldn't have a whole class of security vulnerabilities. On older systems without memory protection, the situation is even worse - you could scribble all over the OS memory as well and who knows what happens then.
  - spc476 5y ago
    It's been attempted. Intel tried doing this with the Intel 432, but it never got beyond the prototype stage as it was very slow, even by the standards of the day (1982).
  - remram 5y ago
    This happens in C because compilers are allowed a wide range of optimisations. I'm just saying it's probably possible to build a low-level language without UB. Of course no one would use it because optimizing compilers are desirable and skipping optimizations just so broken code is handled to spec won't happen.
pornel 5y ago
If by user-defined pointers you mean arbitrary integer-to-pointer casts, then this is a kryptonite for static analysis, and I don't think you can have a language that is both fast and fully predictable (UB-free) in their presence. It breaks pointer provenance and aliasing analysis, and existing compilers already struggle with such casts in C. But apart from that, you can have pointers, with many levels of indirection, as long as there are rules that prevent use-after-free, unsynchronized concurrent access, and other UB-worthy problems. Rust's borrow checker with rules for no mutable aliasing and Send/Sync markers for concurrent access comes close, but it has to give up on generality for safety (e.g. it can't reason about circular data structures).

by kortex 5y ago

immibis 5y ago

Even kernels only interact with memory in reasonably predictable ways. I think they could all be hidden behind such abstractions, BUT it will make the language a lot more complex.

CRConrad 5y ago

> Is it even possible to have zero undefined behavior in languages that allow user-defined pointers? It seems like allowing even just one degree of memory indirection creates a singularity beyond which any kind of formal guarantees become impossible. With untyped pointers, yes. But it seems to me that if you have strong typing for function pointers you could mostly avoid that. > UB is kind of the "we are all adults here" engineering tradeoff that enables shipping fast and useful software, but is technically not strictly defined Well, no, of course it isn't -- the clue is probably in the first half of the name, "Undefined Behaviour"... ;-)

ErikCorry 5y ago

Without concurrency you don't have to have UB to have user-defined pointers. x86 assembly language has no UB and has user-defined pointers.

ahefner 5y ago
CPUs can and do have UB in the instruction specifications. x86 definitely does.
- secondcoming 5y ago
  Indeed, for example the BSR instruction: > If the content source operand is 0, the content of the destination operand is undefined. [0] https://www.felixcloutier.com/x86/bsr https://www.felixcloutier.com/x86/bsr
  - dooglius 5y ago
    No, this is not the same thing as "undefined behavior" in the sense the ISO C spec defines it. The content of the output being unspecified would not, for example, allow the processor to write to some part of memory if the source is zero, or change unrelated registers. x86 is doing "undefined" the right way, unlike the ISO C spec.
    - mpweiher 5y ago
      > No, this is not the same thing as "undefined behavior" in the sense the ISO C spec defines it. Well, it's not UB the way optimiser-extremists (mis-)interpret the ISO C standard.
    - kllrnohj 5y ago
      It's exactly the same as "undefined behavior" in C. The only difference is in the consequences that follow from it when optimizers get ahold of it. If it's undefined behavior if BSR is given 0, then therefore the compiler can assume the value passed to BSR isn't 0 (because it's defined that a well-formed program doesn't encounter undefined behavior). Therefore a check if the value is == 0 can be skipped, because it can't be zero since BSR didn't allow it. And since the code inside the if isn't reachable, that probably means now other things are no longer reachable and can similarly be removed. And etc... That's all the "undefined behavior allows the compiler to murder my cat!" really is - it's just the chain of consequences that result from the compiler following the rules it was told. It was given a rule that a parameter couldn't be null, and so it listened & did what it was told including deleting redundant null checks (since after all, the value was already specified to be not null!). To demonstrate the problem in a different language, let's say I have this code: float asFloat(@Nullable Integer i) { return i == null ? Float.NAN : i.floatValue(); } You'd expect the null check, right? But let's say I call it from this function: void sayHi(@NonNull Integer i) { println("Hello " + asFloat(i)); } The optimizer comes along and inlines the two together and now sees: void sayHi(@NonNull Integer i) { float temp = i == null ? Float.NAN : i.floatValue(); println("Hello " + temp); } Does it still need to keep the null check? After all, I defined that 'i' isn't null, so surely the null check is just unreachable code & can be eliminated, right? If it doesn't, it's obviously wasting performance. If it does, the internet gets angry about the compiler "abusing undefined behavior." Even though as far as the compiler is concerned it isn't undefined behavior! 'i' is defined to be not-null!

kps 5y ago

The original C committee wrote, as part of its guiding principle to “Keep the spirit of C”, that “To help ensure that no code explosion occurs for what appears to be a very simple operation, many operations are defined to be how the target machine’s hardware does it rather than by a general abstract rule.”¹ That is, if you write `a = b + c` you expect the compiler to generate an `add a, b, c` instruction, and if that happens to trap and burn your house down, well, that's not C's problem. I'm convinced that the original UB rule was intended to capture this, and the wording was an error later seized by compiler developers. As evidence, consider Dennis Ritchie's rejection of `noalias` as “a license for the compiler to undertake aggressive optimizations that are completely legal by the committee's rules, but make hash of apparently safe programs”². If anyone at the time had realized that this is what the definition of UB implied, it would have been called out and rejected as well. ¹ https://www.lysator.liu.se/c/rat/a.html#1-1 https://www.lysator.liu.se/c/rat/a.html#1-1 ² https://www.lysator.liu.se/c/dmr-on-noalias.html https://www.lysator.liu.se/c/dmr-on-noalias.html

gpderetta 5y ago
> if you write `a = b + c` you expect the compiler to generate an `add a, b, c` this could be violated even by simple optimizing compilers that do constant propagation or strength reductions. Again, if you do not want optimizations -O0 is always available.
- mpweiher 5y ago
  Hmmm... "To help ensure that no code explosion occurs for what appears to be a very simple operation" How does constant propagation cause code explosion?
- kps 5y ago
  The statement, in context, is a simple illustration of the principle that C operator semantics were defined by the target hardware. Not a treatise on compiler construction.
- naniwaduni 5y ago
  It would be nice if optimizing compilers' -O0 weren't completely insane on the assumption that the insanity would get optimized out.

foxfluff 5y ago

> Is it even possible to have zero undefined behavior in languages that allow user-defined pointers? It kinda boils down to what exactly you mean by defined behavior. A C programmer's take might be that you can run a conforming program in an emulated abstract machine and get defined results out of it. And then you can run the same thing on real hardware and expect to get the same result (modulo implementation defined behavior). This definition leaves some things out (e.g. performance, observable effects in the "real world") but it captures the computational semantics. Another programmer's take might be more akin to a portable assembler. In that case, you certainly could define reads and writes for arbitrary pointers, in the sense that they must cause corresponding (attempted) loads and stores at the machine level. However, the definition wouldn't be complete since it inevitably leaves much to the underlying implementation. Thus you could have "defined" C programs that show completely different behaviors depending on which implementation and hardware you used. It would be impossible to say what the program's output must be "in the abstract." For someone who just wants to output assembly, maybe that's fine. I'm not sure other people would be too satisfied with it. An out of bounds write could still blow up your program and be remotely exploitable; practically the same thing as undefined behavior, except that now your compiler is also barred from optimizing. There's quite a bit of tension between these two camps. Alternatively, you could fully define it at a great runtime cost and potential exclusion of real hardware implementations.

remram 5y ago

Undefined behavior means something specific in the standard, it's not just an operation that might do different things on different compilers and machines. It means that if it happens, the program is allowed to do anything and everything, even before the UB is reached. Undefined behavior is breaking an assumption that the compiler is allowed to make. It is probably impossible to make a low-level language with no implementation-defined behavior, but it is certainly possible to make one with no undefined behavior. For example, you can put in your spec that overflowing an unsigned integer can give any value; that is different that putting in your spec that it doesn't happen and if you write it the variable might have no value, multiple values, or burn your socks off. https://en.wikipedia.org/wiki/Undefined_behavior https://en.wikipedia.org/wiki/Undefined_behavior

comp54321 5y ago
It's actually impossible as far as I can see as long as you have unsafe memory access via pointers and memory is used to hold information about control flow and local variables, because overwriting memory can then do weird and wonderful things to the state of the program. E.g. local variables can magically change values, but worse, the control flow of your program can be hijacked in pretty arbitrary ways. It would be great if this wasn't possible, because then you wouldn't have a whole class of security vulnerabilities. On older systems without memory protection, the situation is even worse - you could scribble all over the OS memory as well and who knows what happens then.
- spc476 5y ago
  It's been attempted. Intel tried doing this with the Intel 432, but it never got beyond the prototype stage as it was very slow, even by the standards of the day (1982).
- remram 5y ago
  This happens in C because compilers are allowed a wide range of optimisations. I'm just saying it's probably possible to build a low-level language without UB. Of course no one would use it because optimizing compilers are desirable and skipping optimizations just so broken code is handled to spec won't happen.

pornel 5y ago

If by user-defined pointers you mean arbitrary integer-to-pointer casts, then this is a kryptonite for static analysis, and I don't think you can have a language that is both fast and fully predictable (UB-free) in their presence. It breaks pointer provenance and aliasing analysis, and existing compilers already struggle with such casts in C. But apart from that, you can have pointers, with many levels of indirection, as long as there are rules that prevent use-after-free, unsynchronized concurrent access, and other UB-worthy problems. Rust's borrow checker with rules for no mutable aliasing and Send/Sync markers for concurrent access comes close, but it has to give up on generality for safety (e.g. it can't reason about circular data structures).