Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Pointers Are Complicated II, or: We need better language specs

ralfj.de

Post reply on HN
Print view View original

111–120 of 135 posts

Re: Pointers Are Complicated II, or: We need better language specs

#111

Post by ralfj »

adwn wrote: post #106
andrewflnr wrote: post #97

For purposes of future language design: why not just ban conversion from integers to pointers? Pointers have metadata that integers can't provide, therefore the conversion is impossible, QED. What's the use case for it outside of, say, binary executable loaders?

> What's the use case for it outside of, say, binary executable loaders? If you're doing low-level optimizations, and you know that your pointed-to objects are, say, 8-byte-aligned, then you can use the lower 3 bits of your pointer for storing metadata. In certain cases, that can be immensely useful. Some GC implementations use this trick, for example.

One could imagine a specific primitive operation in the language that lets you adjust the low bits of a pointer without casting it to an integer and back.

Re: Pointers Are Complicated II, or: We need better language specs

#112

Post by ralfj »

astrange wrote: post #63
dbaupp wrote: post #9

Earlier quoted context omitted.

It’s enough of an issue for C at least that a fully formally verified compiler exists: https://en.m.wikipedia.org/wiki/CompCert . That is, there’s proof that its (limited) optimisation passes are correct. There’s other approaches to assurance of compiled code too, such as seL4 which has proofs that the binary itself is correct, I believe.

Note that fuzzing CompCert has still found bugs in it - because the entire compiler actually isn't verified. They've extended the proof over time. (Note that "formally verified" still does not mean "bug free", it just means it's a refinement of a proof that is also a program which can have bugs in it. And "formally" sounds like a weasel word.)

Yeah, there were some bugs in the frontend and I think one in the backend. But there were zero bugs in the optimization pipeline, which is where typically the most subtle bucks lurk.

For more details, see https://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf

Re: Pointers Are Complicated II, or: We need better language specs

#113

Post by ralfj »

jcranmer wrote: post #61
brundolf wrote: post #44

Before reading this I thought working on compilers might be a fun career direction

To be fair, this kind of complication is relatively rare in compiler work. On the other hand, when it does come up, it does tend to create several hours-long meetings where there are more opinions on what the "obvious" semantics should be than people present. I've always been a stickler for trying to actually specify the obvious semantics to try to forestall these conversations.

Seeing how long the story of poison/undef is dragging out for LLVM, I'd say it's more of a years-long process than an hours-long one. ;) But still, the most important part is that there's a discussion at all, and the desire to properly solve this problem.

Re: Pointers Are Complicated II, or: We need better language specs

#114

Post by ralfj »

Asooka wrote: post #62

Personally I just compile my code with "-fwrapv -fno-strict-aliasing". It's not standard C, but every compiler supports an analogue to those class and it saves so many headaches from UB-optimising passes, the tiny loss in performance is worth it. Integer overflow and pointer aliasing are way too easy to accidentally hit in a C program, the two should have never been made UB, but perhaps added as a pragma to annotate…

Note that all of the optimizations I used in the main part (not the warm-up) of my post are still performed even with "-fwrapv -fno-strict-aliasing". So this does not avoid the issues I am talking about.

Re: Pointers Are Complicated II, or: We need better language specs

#115

Post by mehrdadn »

lmm wrote: post #110
mehrdadn wrote: post #105

Earlier quoted context omitted.

Interesting. So I went back to look at the standard. Like you said, for the relational operators =, and >, they do explicitly say comparing unrelated objects is undefined behavior. But as you suggest, for == and != equality operators, they don't say anything about undefined behavior for comparing pointers to unrelated objects; in fact they do say that unrelated pointers can point to adjacent memory locations if the i…

"Analogous" generally means similar but not the same; if it's a normative description it's underspecified, whereas the "if and only if" description of the semantics of == and != for pointers is definitely normative. I'm sure the standard could be clearer but I do think there's only one defensible interpretation.

It's underspecified, but it is normative. While it's not mathematically inconsistent for the sentence to be redundant/superfluous, it would be rather silly and misleading. It's reasonable to assume it's there for a reason (i.e. it makes a difference whether it's there or not). Given they spell out pretty much everything else anyway, it would seem this point is where it would make a difference.

Moreover, I have a hard time justifying this on first principles. It seems rather arbitrary to make relational operators UB but make equality operators well-defined for unrelated objects. After all, if you can tell if two pointers to unrelated objects are the same, that means you're willing and able to canonicalize them to a common-denominator representation, in which case you already have an ordering based on that same canonicalization too... why forbid that? It would make sense to prevent comparing pointers derived from unrelated objects (due to future performance & extensibility considerations), and it would certainly also make sense to allow it (more convenient/intuitive/etc.)... but to allow one but not the other just doesn't make sense as far as I can see it. You end up with something that's both unintuitive for the user and restrictive for the implementation. So it's a little tough to swallow that that's really what they intended.

Re: Pointers Are Complicated II, or: We need better language specs

#116

Post by UncleMeat »

mjevans wrote: post #99
saagarjha wrote: post #75

Earlier quoted context omitted.

This is untenable in the general case. For example, consider this function: int dereference(int *p) { return *p; } What should the compiler do in this case? If I pass (int *)0x1283412 into this function, that's undefined behavior…should it just always warn?

The compiler isn't __changing any programmer dictated behavior__. There are no UB sourced 'optimizations' being implicitly disabled and none have been expressly enabled. As long as valid code compiles it's on the humans that wrote the code (or that triggered it's writing in some higher level synthesis tool). Expanding on this; I don't want compilers _making_ optimizations based on UB. I want them educating the progra…

But this is a misunderstanding. The “compiler changing behavior” isn’t actually happening in those cases. The program’s behavior never changed. We just have a wrong understanding of the program’s behavior as humans reading the source. If we were to codify and write down all of the expectations we might have about what behavior a source file might represent so that the compiler can match it exactly.... that’d be the standard and we are back where we started.

Re: Pointers Are Complicated II, or: We need better language specs

#117

Post by UncleMeat »

tsimionescu wrote: post #96
klodolph wrote: post #23

Earlier quoted context omitted.

I've heard this proposal thrown around a lot on HN, but how would that even work? Can you describe how the compiler would do this, what patterns it would look for, and what error messages it would produce? For example, consider this: int factorial(int n) { int r = 1; for (int i = 1; i Since there are two instances of possible UB in the above function, what error messages would you like the compiler to produce? First…

For your first example, I think most people want integer overflow to be unspecified behavior instead of undefined behavior - this is how most other languages treat it, it is how all C compilers behaved for a long time, and it is unreasonably difficult to actually write C code that makes sure not to cause integer overflow. Your example is in fact perfect for why that should be the case: consider the following code: in…

If signed integer overflow is implementation defined rather than undefined then it isn’t an error and we cannot make compiler features that warn or reject when we can prove it will occur. In your case we’ve managed to get the worst of both worlds (a buggy program and no capacity for the compiler to stop you).

Re: Pointers Are Complicated II, or: We need better language specs

#118

Post by lmm »

mehrdadn wrote: post #115
lmm wrote: post #110

Earlier quoted context omitted.

"Analogous" generally means similar but not the same; if it's a normative description it's underspecified, whereas the "if and only if" description of the semantics of == and != for pointers is definitely normative. I'm sure the standard could be clearer but I do think there's only one defensible interpretation.

It's underspecified, but it is normative. While it's not mathematically inconsistent for the sentence to be redundant/superfluous, it would be rather silly and misleading. It's reasonable to assume it's there for a reason (i.e. it makes a difference whether it's there or not). Given they spell out pretty much everything else anyway, it would seem this point is where it would make a difference. Moreover, I have a hard…

> After all, if you can tell if two pointers to unrelated objects are the same, that means you're willing and able to canonicalize them to a common-denominator representation, in which case you already have an ordering based on that same canonicalization too... why forbid that?

UB wasn't meant to forbid anything, it was meant to allow implementers to offer different behaviour. Implementers who want to represent pointers internally as integers and have comparisons just compare the underlying integers can do that. Implementers who have something more complicated e.g. segmented architectures are required to support equality comparison (which they can do easily by just having pointers to different segments always compare nonequal) but are not required to define an ordering between different segments.

To me it seems like the kind of compromise the standard makes all the time (which is not to say I agree with it). Requiring everyone to define an ordering on all kinds of pointers would be too burdensome for implementers (or maybe some implementers wanted to trap on unrelated pointer comparison, because if you're doing pointer arithmetic with unrelated pointers you've probably got a bug). Whereas making equality comparisons UB would be way too burdensome for users; it would mean you couldn't e.g. have a list of pointers and check whether a given pointer was in the list by searching through its elements.

Re: Pointers Are Complicated II, or: We need better language specs

#119

Post by mehrdadn »

lmm wrote: post #118
mehrdadn wrote: post #115

Earlier quoted context omitted.

It's underspecified, but it is normative. While it's not mathematically inconsistent for the sentence to be redundant/superfluous, it would be rather silly and misleading. It's reasonable to assume it's there for a reason (i.e. it makes a difference whether it's there or not). Given they spell out pretty much everything else anyway, it would seem this point is where it would make a difference. Moreover, I have a hard…

> After all, if you can tell if two pointers to unrelated objects are the same, that means you're willing and able to canonicalize them to a common-denominator representation, in which case you already have an ordering based on that same canonicalization too... why forbid that? UB wasn't meant to forbid anything, it was meant to allow implementers to offer different behaviour. Implementers who want to represent point…

> UB wasn't meant to forbid anything, it was meant to allow implementers to offer different behaviour.

That's unspecified behavior, not undefined behavior. Unspecified behavior can literally do anything or nothing at all, including aborting the program nondeterministically. That effectively forbids invocation of UB for the programmer since you can't reason about the program after it's invoked, unless you've verified your implementation has actually defined the behavior for you (despite not being required to). That's quite different from unspecified behavior where the implementation is required to pick some sane behavior (often among a set of acceptable behaviors) and stick with it in a self-consistent manner.

> Requiring everyone to define an ordering on all kinds of pointers would be too burdensome for implementers

I don't see how it'd be more burdensome, and I don't think burden is the issue here anyway. Implementers already have to implement canonicalization for equality comparisons, and they already have to implement casting to uintptr_t too. Just put the two together you get comparisons. One reason to not want to do this is that it might be too expensive to canonicalize to an integer under the hood (maybe it's complicated arithmetic or whatever), but if they're already willing and able to jump through all the hoops just for the sake of equality comparisons, ordering is hardly any different.

> (or maybe some implementers wanted to trap on unrelated pointer comparison, because if you're doing pointer arithmetic with unrelated pointers you've probably got a bug).

Not at all. You want to linear-search in a list and want equality to work for that? Well I want to binary search in an array/BST and need comparisons to work for that. This was such an obvious thing to want to do that C++ made it work out-of-the-box for std::less and whatnot.

Re: Pointers Are Complicated II, or: We need better language specs

#120

Post by jcranmer »

ralfj wrote: post #113
jcranmer wrote: post #61

Earlier quoted context omitted.

To be fair, this kind of complication is relatively rare in compiler work. On the other hand, when it does come up, it does tend to create several hours-long meetings where there are more opinions on what the "obvious" semantics should be than people present. I've always been a stickler for trying to actually specify the obvious semantics to try to forestall these conversations.

Seeing how long the story of poison/undef is dragging out for LLVM, I'd say it's more of a years-long process than an hours-long one. ;) But still, the most important part is that there's a discussion at all, and the desire to properly solve this problem.

Oh, finishing the meetings may take months or years, but the meetings themselves are only a few hours long.
Post reply on HN