> @jrose @fclc People who want NaN in their integers are welcome to do that in the privacy of their own bedrooms with new types they invent for this purpose.
That reminds me of OCaml's 63 bit integers. In the privacy of OCaml's own bedroom, they use one bit of their integers as a flag to distinguish pointers from integers.
The results are quite.. interesting. However, it does go to show that having slightly weird private integer types is actually totally workable, so the quote from the discussion might be meant as trolling, but it's less crazy than it sounds like.
The difference is that (a) that bit in OCaml has a purpose, while disregarding 0x80..00 hasn't; and (b) I assume that it was in OCaml from the beginning, so it wouldn't break existing software in probably very interesting ways (hence the suggestion that this should be done only "in the privacy of their own bedrooms with new types", i.e. not for already-used types)...
abs() of this value also happens to exceed the maximum positive value. Which means that in C, a simple negation can cause signed integer overflow -(-32768), and therefore UB.
Yeah, I think it is funny that in a standard binary, it would replace negative zero and makes some sense. In two's complement, it replaces the minimum value.
Fair that sentinel value is sentinel value, I suppose. But it is not like it is not a known and unique number in that encoding.
> > @jrose @fclc People who want NaN in their integers are welcome to do that in the privacy of their own bedrooms with new types they invent for this purpose.
And yet I bet they use IEEE754 floats without second thought.
I agree with the quote and use IEEE754 floats with second thought every time. In my perfect world floats don’t have inf, nan and base-2 exponent. And integers are 0-sized exponent floats.
It's quite clearly decimal floats, with instant trapping instead of bad values.
IMO, with the sheer amount of silicon modern processors use for incredibly specialized gains, there's no reason our computers should be specialized for scientific computations when they could support daily computations too.
You obviously do not want decimals on your GPU, but the choice on the CPU is out of wack.
Floats seem to be pretty good for running graphics processing. (I would also say AI training and inference, but the machine learning people are constantly experimenting with weird new number formats.)
The 'daily computations' you mention only need a tiny amount of computational power. So it's fair for our CPUs to simulate them via library code.
You should however complain about a programming language that makes it unnecessarily hard to use those 'daily computation' numbers. As a positive example, Python automatically gives you unlimited size integers by default, and only gives you size limited integers, if you explicitly ask for them.
Good question. Today we are incredibly biased into base-2, using it many times where we should be using base-10 instead. So the performance of our current software is not a good example.
But maybe we can get a good example if we just divide our current numbers by instruction types and multiply the FP time by ~100.
I have seen many studies that measure how much time software spends on FP instruction. But unfortunately, we live in a web search dark age, so I don't have references. I remember that FP-heavy code spends 10% to 20% of the time on those, what means that emulation will increase your execution time up to something on the 10x - 20x range. That's perfectly fine for a lot of applications, but does limit several niches.
But as far as I know, the question of how FP-heavy is the FP-heavy software that does daily calculation is unanswered.
What kinds of applications do you have in mind that are (a) CPU bound (or GPU bound), and (b) would benefit from your 'saner' numbers?
Eg graphics in general or video decoding specifically is definitely something that does a lot of processing; but I don't see how it would benefit from eg base-10 numbers?
Spreadsheets might benefit from base-10 numbers by default; but they are not CPU bound at all. Mostly they just sit around and wait for user input.
ERP is all about numbers, and lots of them. While you may rightfully argue that it's a job for SQL servers, the lack of fast base-10-exp numbers in apps creates a very inconvenient and performance-bound gap in development of these systems.
Also, ieee754 floats usually leak into most general purpose scripting languages from the fast-ish category, cause there's no hardware alternative. Two main issues with this are: 1. people who do scripting may be unaware of numeric issues related to base-mismatch, 2. "domestic" calculations and formatting still become cumbersome for those who know. Another issue is that to properly build decimals in (think native + - / * operators), you have to modify the language model around that, and it comes with all sorts of prices.
In short, people want the results to compare correctly to their pocket calculators. "A human number is [+-]<decimals>.<decimals> in a ~20-digit-max window" is an idiom everyone is familiar with and all business requirements assume that by default.
You can do that, but I think for most applications where you want decimal, you can get away with fixed point computation?
Eg if you want to calculate with money, just specify everything in terms of cents (or 0.001 of a cent or whatever), and then use an integer data type. Perhaps even an unlimited size integer data type.
And don't forget to adjust after multiplication, e.g. ($ * kg) = (price * qty) / (10 ^ qty_scale).
But not before you finished with a "sequence-point" in calculations, cause otherwise rounding will accumulate, e.g. ((price * qty) * (100 * (10 ^ pct_scale) - discount)) / (10 ^ (qty_scale + pct_scale)).
Thus no operator[+-*/%^] magic for you either. Also, all these temporary ...0000000s will bite into your "mantissa" part along the way. Fixed point sounds reasonable until you have to actually implement a sales/debt/tax/trade-related routine that takes a couple of pages with proper decimals alone.
The downside of rationals is that they degrade extremely quickly as soon as you take a sqrt or do trig. Decimal floating point has the advantage of losing accuracy in the places people are used to.
I believe that for almost all rationals trig functions never return a rational so you must have some kind of rounding tecnique.
An advantage of rationals is that you have much more freedom in handling how the rounding works, for example you can limit your rounding to produce fractions n/2^m and then they behave sort of like floats or n/10^m and then they behave like decimals while still being able to know that basic arithmetic operations (+, *, -, /, <, <=, <>, mod, exponentiation by integer) work as precisely as you want them to.
GPUs, ML, an massive numericall processing will want to always use floats, ints, posits[0] with operations that can be efficiently implemented in hardware but most apps could easily afford to use bigint/bigint rationals for most things.
Typically in the unsafe languages under discussion they use the IEEE754 types without even a first thought. For example you can expect them to sort such types (you can define rules for sorting them, but if you just didn't in C too bad your program has Undefined Behaviour, while in C++ today it's even worse you've silently not written a C++ program at all and it never had any defined behaviour even before it tried to execute your invalid sort)
std::sorting floats is perfectly well defined in C++ as long as you respect the precondition that there are no NaNs in your range. In other words the subset of floats without NaNs respects strict weak ordering.
edit: when using the default comparison. With a custom comparator you can do whatever you want, including using std::weak_order to sort NaNs.
std::sort is defined in terms of a semantic requirement Compare - a constraint on types - which forbids types which don't have Equivalence. Specifically, our type needs to have some equivalence predicate equiv(A, B) such that equiv(A, A) is true, and the provided comparisons for floating point types in C++ do not meet this requirement.
I would be astonished if you're not correct at runtime in practice of course, but "It works in my environment" and "This is correct by the standard" are two different things.
> Requirements are stated in terms of well-defined expressions that define valid terms of the types that meet the requirements.
I'd read this as separating the values of a type into valid and invalid terms, where the valid terms can be any arbitrary set of values that's closed under the required operations. (This is explicitly clarified for concepts in [structure.requirements]/8, saying that the functions and conditions don't have to be total over all values of the type.)
In this case, NaN would be considered an invalid term for std::sort(), so the compiler could break the program at a point only if it could statically guarantee that a NaN will inevitably make its way into std::sort().
Staring at that text just gives me a headache, in particular "This does not affect whether a type models the concept".
I'm sure that everybody proposing and voting on this text was sure they agreed with it, however I'm doubtful that they all had the same meaning in mind, and I have no idea which one the author intended.
What is "this" here? The example, of a type which clearly doesn't model the concept it syntactically conforms to? The requirement? All of the preceding text ?
> What is "this" here? The example, of a type which clearly doesn't model the concept it syntactically conforms to? The requirement? All of the preceding text ?
Generally, pronouns in the standard are scoped to the paragraph they're in. In this case, I read it as saying that the type (e.g., float) can still model a concept even if the semantic requirements are violated for some particular values. (That is, "this" is "whether the required operation is partial or total".)
To support this reading, we can see from [res.on.requirements]/1 ([0]) that 'modeling' a concept is defined as meeting its associated semantic requirements:
> A sequence Args of template arguments is said to model a concept C if Args satisfies C ([temp.constr.decl]) and meets all semantic requirements (if any) given in the specification of C.
And 'meeting a semantic requirement' is mediated by [structure.requirements]/4, which I read to say that semantic requirements aren't universal rules for all values of a type, but necessary preconditions for values to be valid terms that can be passed into standard-library APIs.
By that logic, even though an operation might not "meet the semantic requirements of [a] concept when operating on NaNs", it doesn't kill the entire type, it just rules out NaNs from being valid terms.
I think the weirdness here is that the set of valid terms of any type is up in flux, to be defined by the ultimate user. But even if the operations don't meet the semantics over that entire set, the compiler has no way to prove that the program is ill-formed until the user actually generates one of the offending values, asserting that it truly is a valid term.
The problem with your interpretation is that it defies causality. The question of whether this is a well-formed C++ program isn't one that can be delayed until runtime, it either was, or was not, a well-formed C++ program when it was compiled - so if your reading requires that we don't know until runtime then it cannot be a correct reading.
Instead the models are about types, not about individual values or groups of values (except in the sense that a type "is" all its possible values). Unlike individual values, the types are known at compile time, so at compile time the types used mean it is or is not a well-formed C++ program in this regard. If we use a type which matches the syntactic requirements but does not model the Concept, our program is Ill-Formed and No Diagnostic is Required, we've written nonsense, we don't win a prize and our program has no defined meaning.
You seem hung up on the fact that we often can't be sure, that's Rice's Theorem, the option we'd prefer (accept exactly the set of programs with the desired semantics) is mathematically impossible, Henry Rice got his PhD for showing that a lifetime ago. If you want non-trivial semantic properties (and in a language like C++ you certainly do) then you have two practical ways to resolve this and get a working language. The first way is the one C++ chose, you can reject some obviously unacceptable programs, but whenever you aren't sure you assume the desired property is satisfied and don't worry about it further.
The other option (which I happen to think is the only reasonable choice) is the one Rust took - only programs which we can show have the desired semantic properties will compile, other programs are rejected. This means the compiler will reject some correct programs, which is somewhat annoying if it happens to you, but effort put into the compiler can reduce the frequency of its occurrence (and it did in Rust, that's what the Non-Lexical Lifetimes change was and what Polonius is all about)
> The problem with your interpretation is that it defies causality. The question of whether this is a well-formed C++ program isn't one that can be delayed until runtime, it either was, or was not, a well-formed C++ program when it was compiled - so if your reading requires that we don't know until runtime then it cannot be a correct reading.
Alas, the same issues with causality arise with the idea of "time-travelling UB". Suppose I write a program that prints a welcome message, reads a number from the standard input, then either exits if it's 0, or causes UB if it's 1. By the rules of the standard, if the implementation could presciently predict at the start of the program that I am about to enter 1, then it could skip the welcome message.
But of course, in the real world, causality is a higher law than the rules in the standard: if there's a possibility at any point that UB might not occur, then it must keep functioning as expected. So there's no way it can skip the welcome message, even though the standard allows it.
I see the question of ill-formedness from invalid terms as the same. At the start of each execution of the program, each type that must satisfy a requirement gets an invisible "set of valid terms" with respect to that requirement. However, this set exists only in the mathematical sense, in that it cannot yet be known by anyone, since it depends on future information. This is just like "the number that I will eventually enter" in my last example: it mathematically has some value (assuming that I do eventually enter something), but neither I nor the implementation can know whether it's 0 or 1 until I actually enter it.
Thus, the implementation is once again bound by the possibility that the "set of valid terms" might truly satisfy the requirement. It must execute the program as if it is well-formed, right up until the point where it is no longer possible that it is well-formed. And that point will generally correspond to a particular witness value (e.g., a NaN) that is passed into a standard function but makes an operation fail to meet its requirements.
If you want to put it into properly-causal terms, you could start the program with a really big "set of possible sets of valid terms". Then, each time at runtime that the program passes a value to a function with the requirement, you filter the sets to only those containing the value. If there are no sets left after this, then the program is now known for certain to have been ill-formed all along (there's no possibility remaining), so you can do whatever you want.
Of course, this does assume that a program being well-formed can change between each execution, even with the same source file. But it's hardly the only IFNDR in the standard that depends on behavior rather than syntax.
> The other option (which I happen to think is the only reasonable choice) is the one Rust took - only programs which we can show have the desired semantic properties will compile, other programs are rejected. This means the compiler will reject some correct programs, which is somewhat annoying if it happens to you, but effort put into the compiler can reduce the frequency of its occurrence (and it did in Rust, that's what the Non-Lexical Lifetimes change was and what Polonius is all about)
Since you mention Rust, I'd note that it has the same causality wackiness, just to a far lesser extent than C/C++, in the form of "angelic nondeterminism" (which is a term you can Google). Suppose that you have a pointer to the end of one slice and a pointer to the start of another slice, which happen to be equal, but don't have access to each other's slices due to provenance. Then, you convert both those pointers to integers, and convert that integer value back to a pointer.
Which slice should the new pointer have access to? Since integers have no provenance, the compiler has no way of knowing which pointer the address came from! Thus, the compiler uses "angelic nondeterminism" to decide: defying causality, it picks whichever of the two slices will make the program valid. If neither choice is valid (e.g., the program tries to access both slices from the new pointer), then it's instant UB.
Once again, to do this in the real world, the compiler must maintain a conceptual set of possible pointers that the new pointer might have come from, then whittle them down based on what memory is actually accessed. If there are no possible pointers left, then UB is known.
> Of course, this does assume that a program being well-formed can change between each execution
Which can't be right.
> has the same causality wackiness, just to a far lesser extent than C/C++, in the form of "angelic nondeterminism"
It's OK, I don't need to Google, you'll find me in a conversation with Martin Uecker in a previous HN thread about PNVI-ae-udi which is the way C or C++ people would think about the matter.
And actually as usual Rust is ahead of the game here, you say "the compiler has no way of knowing" - actually with Aria's experiment in play we can insist on always telling the compiler what's going on, and as a reward we get both more assurance of correctness because the tools work (Miri for example) and better performance. The experiment is about whether most Rust software can live with this restriction ("Strict Provenance") and the answer IMNSHO is clearly yes.
Rust's pointers get to have member functions (as do its primitive integers and any other types) and Aria's experiment adds the method with_addr() to pointers, so now we can tell a pointer (which has provenance) that we want a different pointer with a different address inside it (but preserving the provenance) via the method.
More pertinently to our discussion, even with PNVI-ae-udi plus a mistake that results in an impossible pointer this is a cause of Undefined Behaviour, which occurs at runtime, it is not a semantic requirement of the language, our Rust program was well formed and correctly translated into machine code if we did this wrong, it's just that it had Undefined Behaviour at runtime as a result of us writing bad unsafe code.
Because Rust defaults to rejecting programs it knows always panic there can be the false impression that such programs are not well-formed. You can just insist to the compiler that you want the results anyway, it will duly spit out an executable which... always panics. Not sure what you want that for, but you're welcome to it.
> And actually as usual Rust is ahead of the game here, you say "the compiler has no way of knowing" - actually with Aria's experiment in play we can insist on always telling the compiler what's going on, and as a reward we get both more assurance of correctness because the tools work (Miri for example) and better performance. The experiment is about whether most Rust software can live with this restriction ("Strict Provenance") and the answer IMNSHO is clearly yes.
The standard counterexamples being XOR linked lists, or manual paging with mmap, or manipulating addresses as integers within asm!(), or literally any situation where you can't afford to keep the address as a single value-with-provenance sitting at a known location in program memory until you need it.
Strict provenance is sufficient for most use cases, but far from all of them, so there's no viable way to tear the whole concept of exposed addresses out of the language. In any case, removing it would violate basic expectations of stability, given that users have been converting pointers to integers and back since the very beginning of the language.
> More pertinently to our discussion, even with PNVI-ae-udi plus a mistake that results in an impossible pointer this is a cause of Undefined Behaviour, which occurs at runtime, it is not a semantic requirement of the language, our Rust program was well formed and correctly translated into machine code if we did this wrong, it's just that it had Undefined Behaviour at runtime as a result of us writing bad unsafe code.
My point is that there's no difference in semantics, nor any difference with respect to causality, between an "ill-formed program" that's only ill-formed under certain conditions, and a program with "Undefined Behavior at runtime". The standard ascribes no requirements on the entire execution, start to finish, in either case. But practically, if the implementation doesn't have enough information to distinguish a valid execution from an invalid execution until a certain point (i.e., runtime-dependent UB or ill-formedness), then it must behave properly right up until that point, by the laws of causality.
Still, I agree that just calling requirement violations UB would be far less confusing.
> The standard counterexamples being XOR linked lists, or manual paging with mmap, or manipulating addresses as integers within asm!(), or literally any situation where you can't afford to keep the address as a single value-with-provenance sitting at a known location in program memory until you need it.
Well there's a crucial distinction in play here. The XOR linked lists, and some related tricks can be done with address exposure, we expose the pointer and get the integer address, then later when we reconstruct that integer we're allowed to turn it back into a pointer. Rust of course has (as part of the same experiment) APIs for that, you're just paying in terms of worse performance and no tooling (the tooling is disabled if you want these APIs).
But the other cases are just voodoo magic, we don't have a model to explain why they should work, which also makes it very hard to, for example, debug them if they don't. They're platform specific. As with the inline assembler, Rust takes no responsibility for whether you can write a correct program in these circumstances, good luck.
I don't agree that there isn't a practical difference between IFNDR and UB, I see attempts to confuse these as part of a desire to pretend that C++ isn't markedly worse at correctness than competitors, without the hard work to actually stop it from being markedly worse.
A well-formed C++ program is one that is "[...] constructed according to the syntax and semantic rules" (4.65).
And of course adherence to many semantic rules in C++ cannot generally be verified statically: "A conforming implementation executing a well-formed program shall produce the same observable behavior as one of the possible executions of the corresponding instance of the abstract machine with the same program and the same input. However, if any such execution contains an undefined operation, this document places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation)." (4.1.2.5).
It sucks but that's the way C++ work, and it would be hard for it to be any other way without GC or going full rust.
> A well-formed C++ program is one that is "[...] constructed according to the syntax and semantic rules" (4.65).
Yes, my argument is that as a result a C++ program which sorts floats in the standard way is not well-formed. The type "float" matches the syntax rules, but does not match the (unchecked) semantic rules for ordering. This is Ill-Formed No Diagnostic Required, IFNDR.
Not checking is a choice. You mentioned "full Rust" as the alternative here, but lest that be misinterpreted, the other choice isn't to do everything Rust does, only to make the same choice in this specific respect: Rust chooses to reject programs unless it can see that they meet the semantic rules, while C++ chooses to accept programs unless it can see why they cannot.
Rice's Theorem forbids the obviously ideal outcome (accept exactly the set of programs which have the desired semantic properties) but either of these alternatives delivers an implementable system, and I believe of those two options one is clearly unacceptable.
> my argument is that as a result a C++ program which sorts floats in the standard way is not well-formed.
I think the argument is flawed: if any program that sorts floats is not well-formed because a float could be a NaN, then any program that dereferences a pointer is not well-formed as a pointer could potentially be null. Do you agree that's obviously not what's intended?
I will grant you that the standard is very much less than clear, but I think generically it uses the term "program" to refer to programs, part of programs or execution of programs.
re: full rust, yes I meant "reject programs unless it can see that they meet the semantic rules".
I agree that dereferencing a nullptr is merely UB and your program isn't Ill-Formed as a result.
I distinguish sort because it requires the sorted type to match a bunch of concepts and those are defined such that if your type doesn't match the syntax requirements it just won't compile, but if your type doesn't match the semantic requirements (the "model" of the concept), which are just text in the standards document, well, too bad IFNDR.
I think you can attempt to read the Concepts wording as if it's not about types but groups of runtime values, but I think that gets to the causality problem, where we're deciding at runtime whether our program's text was ill formed before it was compiled.
Obviously C++ 17 sort didn't do any of this, because C++ 20 Concepts didn't get standardised until C++ 20 -- hence my reference to "C++ today". I believe in C++ 17 similar code just has UB.
Edited to add Also: Unrelated to our main topic, I think C++ 17 should have insisted on a Quality of Implementation requirement here which says yeah, if you gave us faulty comparison function, your data does not get "sorted" whatever that could mean, but we're not going to give you Undefined Behaviour. After all C++ did eventually forbid naive Quicksort, which is a QoI decision.
Rust can cheerfully "sort" a bunch of my misfortunate::Always types, which insist they exhibit Total Order but are lying. Obviously after we've "sorted" them they're not "sorted" because that's meaningless, but Rust isn't going to run off the end of a buffer or cause other nonsense, we broke it => we bought it, no more than that.
std::sort has a semantic requirement on the type of Compare, but Compare itself only has a constraint on the values it is comparing. From the 27.8.1.3 [1]:
"comp shall induce a strict weak ordering on the values."
It is not terribly clear what "values" is referring to, but form context it must be all values that are being sorted, as opposed to all possible values of T.
The only explicit constrain on T is that it must be Move Assignable and Constructible.
I see what you're saying about defining "values" as specifically only the values which, at runtime, we happen to be using Compare on, which is an idea I hadn't considered before - but I'm not sure how to square that with the way the rest of the language is defined.
Maybe one day the proposed "Appendix" of all UB and IFNDR will actually explain clearly what the intended rules are. Corentin Jabot's "UB? In My Lexer?" showed that the ISO document is still very uh, unpolished after decades of effort.
My argument is that what's happening here in C++ is not merely Undefined Behaviour.
UB is a runtime thing, at runtime your program tried to do this operation we said mustn't ever happen, so all bets are off. C++ also has this idea of programs which are Ill-Formed, No Diagnostic Required, meaning that this was never a C++ program, the ISO document doesn't tell you what this program will do, and a compiler isn't expected to tell you that you didn't write a C++ program in these cases either, so too bad but it's not our fault.
IFNDR is there because these are non-trivial semantic properties, so by Rice's Theorem they're Undecidable, the compiler cannot be sure if every arbitrary program meets the semantic requirement. The ISO C++ document would need to document a check which can be performed, allowing compilers to accept only programs which pass that check, or something similar giving enough rope for them to avoid cases where your program compiles in Clang but not MSVC or vice versa, that sounds awkward to write, instead it just YOLOs the whole problem with IFNDR -- if any program unknowingly does not meet these requirements it was silently never a C++ program anyway, not our fault it doesn't work.
As it has grown over the decades, C++ has added more, and more, and more IFNDR to the text, because it sure is easier to wave away such programs as "That isn't C++" than to either insist compiler vendors write more diagnostics (Boring! Expensive!) or define the language more carefully so as to make the wrong programs impossible to write. They do not have a comprehensive list of IFNDR (nor UB) in their language today.
My belief (and some well known C++ people agree) is that the vast majority of real world C++ programs today are Ill-Formed by these definitions and so do not have and never had any meaning by the text of the standard. I think this is substantially worse than the situation in C.
> FNDR is there because these are non-trivial semantic properties, so by Rice's Theorem they're Undecidable, the compiler cannot be sure if every arbitrary program meets the semantic requirement.
As pointed out elsewhere, Rice's theorem does not force this choice. You could also be conservative: insist on only disallowing all 'bad' programs at the price of banning some 'good' programs. C++'s type system already disallows plenty of 'good' programs anyway.
> My belief (and some well known C++ people agree) is that the vast majority of real world C++ programs today are Ill-Formed by these definitions and so do not have and never had any meaning by the text of the standard. I think this is substantially worse than the situation in C.
Thanks! That's the kind of answer I was trying to get!
> @jrose @fclc People who want NaN in their integers are welcome to do that in the privacy of their own bedrooms with new types they invent for this purpose.
That reminds me of OCaml's 63 bit integers. In the privacy of OCaml's own bedroom, they use one bit of their integers as a flag to distinguish pointers from integers.
See https://blog.janestreet.com/what-is-gained-and-lost-with-63-...
The results are quite.. interesting. However, it does go to show that having slightly weird private integer types is actually totally workable, so the quote from the discussion might be meant as trolling, but it's less crazy than it sounds like.