This adds more 'value' to the code for people than allowing them to switch their brains off because something is 'unlikely' to happen. A large class of bugs exists because people assume stuff is unlikely.
I also think one has to distinguish between API and actual code.
If you write a lib that takes inputs that should never be negative you can express this without writing a single line of documentation about it (or if you do, requiring the user to read it) by using unsigned types in these places.
You can still use signed types in your actual library code if you want/must/believe in that but do not pollute the outside API with them if unnecessary.
Imagine you have a bug in your program. If you intend for a value to be non-negative and use a signed integer, you get a negative value. Your code is broken. You didn't want a negative value. But you do have have a very easy way of checking for this at runtime, at least.
Now imagine you instead use an unsigned integer. The bug is still there but now it manifests as overflow or underflow. Your program is still broken. Nothing about using an unsigned integer saved you. And worse, you don't have an easy predicate to check that something has gone wrong.
I think this can only be a reasonable choice if you are working in a language that has dynamic checks for overflow and so using an unsigned integer enforces not only the predicate that the value is nonnegative but also that all operations stay within its expected arithmetic domain.
thread 'main' panicked at 'attempt to subtract with overflow'
Even more so now that custom profiles have been added to Cargo (yay), you can enable overflow checking in release, and add a `release-unchecked` or whatever.
3u64.checked_sub(4u64).expect("Overflow");
This allows you to spell out that you don't expect this to overflow, and Rust should panic if it does, regardless of your compiler flags.
Much simpler to just toggle on the relevant flag.
But surely that's almost never the case? Few programs actually desire or care for base 2 modular arithmetics, and when they do it tends to be for very specific tasks (usually cryptographic or cryptography-adjacent e.g. hashing, checksumming, ...).
Which is why it’s not so impractical to make an occasional exception.
However, changing - to perform checked_sub() leaves you with an Option, and this makes ordinary arithmetic look pretty clumsy:
let x = (a-b).unwrap()-c;
The intent is to land more types with intrinsic behaviour. Today only the Wrapping type is provided, so Wrapping<i32> is an i32 that definitely has Wrapping arithmetic and won't panic on overflow, but eventually Saturating<i16> will be possible (e.g. for CD audio PCM samples, saturating arithmetic is correct, if you try to make the loudest possible noise louder it just stays the same) and so will Unchecked<i8> if you really sure that you're doing 8-bit arithmetic that can't overflow and doesn't need Debug checks.
If it was an int at the function signature and you got -1 what would you expect to happen? It's the same thing.
How could you possibly check this using types that cannot represent what you are checking for?
`f(u32 a, u32 b) { assert a > b ... `
(if the hypothetical following operation is `a-b` as discussed higher in the thread)
Log the error and act accordingly, instead of believing this kind of issue only happens during development
If input data is faulty and the reason for that is not seen as part of your logic, then sure, log an error and skip.
I used to define my own assert macro to "ensure" my asserts aren't disabled, but I don't bother anymore. There's nothing wrong with assert, and you needn't define NDEBUG. It's important to be aware that there are different situations, and not all warrant aborting, as described above. Another differentation is that there can be asserts that must be disabled in release builds for performance reasons, and others that won't affect performance and can stay enabled.
The same thing, but worse, can happen with signed integers. (-3)-INT_MAX is either some huge positive number, or something crazy because it's undefined behavior and the compiler is allowed to do anything it wants.
I can understand where they come from, especially regarding error handling: for integers whose value must not be negative, it is easier to check for underflow by checking if the result is not negative rather than by checking that the result is not eg smaller than the previous value (eg for addition).
That being said, "number must not be negative" really ought to be encoded in the type system, so that the user of the type knows that they must actually look for underflow.
I guess that part of the problem is that we don't want to check for underflow after each operation, so checking the negativity is a way to "coalesce" several checks after multiple operations. However this is fragile, because the multiple operations could end up producing a positive value, even if some intermediate values where negative.
For full safety, I don't see how we could do better than checking after each operation right now. If we're doing this, I feel like checked_add and friends from rust is a better fit than cramming an unsigned int into a signed one.
I wonder if we could design an integer type with 63 bits of value, plus one bit of "overflow/underflow poison", such that any operation that would under/overflow would saturate that bit to one, but otherwise still perform the operation on the value part. That would allow to coalesce multiple checks while keeping safety even in the presence of multiple faulty operations. I wonder how it could be implemented efficiently though
[0] Supplemental Integer Safety, http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2868.pdf
There is something like that already for floating point. Whenever an overflow or underflow happens, it sets a sticky bit in a separate flags register. You can clear these flags, do a sequence of operations, and at the end, see if any of these flags are set. See https://man7.org/linux/man-pages/man3/fenv.3.html for the standard C API for it.
In terms of the C standard, "3-4" for unsigned ints is modular arithmetic, and the "wrong thing" is assuming that it will do anything other than wrap around. This is very clearly defined, and implied whenever you see an arithmetic expression on unsigned integers.
C made the right tradeoff IMO. You can protect yourself against overflow if you need to, but if it always signals errors you can’t turn that off.
Maybe you want to do some weird bit banging trickery, and that's fine too, but it should require an out-of-the-way function call.
Many languages optimize numeric operations and DX around numeric types for efficiency rather than correctness, and make the latter high-friction. (Wrap-around subtraction, decimal literals being treated as IEEE floats, etc.)
The exceptions (or cases where it is merely less true) tend to be very high level, dynamic languages.
Ada's "Positive" or "Natural" or
subtype X is Integer range Y..Z;
expresses intent (well expresses requirement really), it also enforces that constraint, so it's not merely an assumption.So, let's make an odd_int_less_than_20587 type and a billion of other types? "Not negative" normally helps only one tiny bit towards documenting anything about the accepted values. Making a separate type for that and complicating everything is ridiculous.
> If you write a lib that takes inputs that should never be negative
Have you ever compared the difference between two unsigned integers? Because unsigned integers don't have "natural" subtraction. Did you ever find the need for signed numbers to interact with unsigned numbers? Because if you did, it's a bad idea to separate them without need. Premature isolation is a prime cause of complexity.
Yes, what's wrong with that ? Every variable's type should be defined as precisely as possible when meaningful, that's the whole point (and C/C++ not easily allowing to do that is one of their biggest drawbacks imho.)
In fact most software is designed such that the physical sizes are chosen first, and then the practical bounds follow from that.
> void foo(ranged_int<1, 5> a, ranged_int<3, 7> b)
Why would I _ever_ write a function like that? Practical proofs need to be about runtime values, not just constants and types. They also need to put multiple values in relation. They need to handle type casts and many more things. Constant integer ranges might be of some use but it's a tiny fraction of the invariants that a programmer juggles in practice, and the source code is already blown up out of proportion just for these ranges. This thing is just not gonna fly.
Just multiply some "good" values a few times and there is no way that you can statically prove that the result is going to be in the range as well, even though it might always be the case due to how the values combine each time (simple example: offset + size that the code checked to be within array bounds). Invariants in practice are relations over the runtime values of multiple variables. The focus on single values is basically already where types fail as a correctness tool.
I don't understand, there's literally a CVE about that elsewhere in this thread, basically
struct my_structure {
int size;
int offset;
};
either you restrict both size and offset to e.g. 2^30 so that you can safely sum both, or you will have an issue because you'll be doing if(size + offset < max_size) and size + offset overflows because absolutely no one can be trusted to write overflow checks, you gotta use a library for that.Usually it's very easy - require that size and offset are validly indexing an object, and require that objects are of a sane size (I rarely have in-memory objects larger than a few megabytes, and for most code I posit that it is a mistake to not chunk and stream huge datasets). Done, no real need to worry.
If you cannot make any assumptions about the values contained in a "my_structure" then that means the code is at an API boundary, which is the perfect place where such check (if-statement) must be placed. At internal code places, checks are wasted effort, and at most a compiler switch to detect wraps (logic errors) would often be a much better choice than paranoid code where each line of code can't trust the previous line, and where one can't see actual work being done because it's all covered in mistrust. Unnecessary mistrust (i.e. mistrust at places strictly inside maintenance boundaries which are not strategic checkpoints) only makes it hard to write code that actually does something, and might possibly cause more bugs than it could ever save.
Bounded integer types have been extremely useful for me on a few occassions, and I wish more languages had type systems powerful enough to support them. They also address your concerns about subtraction.
Yees?
Bounded integers are a relatively common feature of programming languages (and one which is sorely missing from Rust, it's technically possible currently but not super fun, when fleshed out enough const generics should make them much nicer, possibly even built-in)
If you genuinely wanted to reason solidly about such limits, you do end up needing arbitrarily bounded integers. Of course, most people don't want to do that, for good reasons. And even if you wanted it, there's a reasonable question whether adding them to the language syntax is really the right thing to do.
Yes, and at least in C++ it isn't that difficult to trivially generate these types as you need them with a modicum of template-fu. You don't need that many integer type templates to capture most of the common cases and provide contextually sane operators. This might be a little more difficult in other languages.
This is pretty standard type safety practice and usually well worth it in terms of writing robust low-defect code.
I do database engines. This has been a standard part of code standards for a really long time, at least as long as the programming languages we used practically supported it. I've done it ever since. The only type that is allowed to flow through the code is size_t, where it makes sense.
Are there any open source examples to study this style? I don't know where to look, but admittedly studying C++ codebases is not what I do for fun.
In my personal experience, it never worked putting layers of abstractions to hide physical representations. That makes the implementation code really hard to grok, and your hands are bound in the code because you're not allowed to _assume_. What worked for me instead is making sure that certain decisions that are likely to change are contained inside a module and for the rest of the code hidden behind an API or simply not accessible. Runtime assertions can be useful too, but maybe that is part of what you are describing by "template-foo". Finally, I try to stay true to my decisions and am not trying to act like I could have to replace floats by doubles at every corner. Some code that I've seen was littered with templates for that single reason, and I'm pretty sure the developers didn't have an intimate understanding how floating points works.
Interestingly, size_t is one of the things that I tend to avoid, and in my perception a majority of the programmer population agrees it was a mistake to have it be an unsigned type. A type which can represent "the size of an object" is too general for all but maybe OS APIs IMO. Usually I know that the size of my objects is bounded by a certain size, well below what fits in 32 bits.
I see your point, but I think that (while not always), it can still be pretty helpful to add your custom types to make invalid states unrepresentable.
This can sound ridiculous on something like C, but if your language has refined types, it's not that bad.
For example, this doesn't look awful to me:
``` type WeirdId = Int Refined (Odd And Less[20587])
val myId: WeirdId = 5 // OK val myInt: Int = myId // Can be used as an Int val myRuntimeId: Either[String, WeirdId] = refineV[Odd And Less[20587]](myId + 2) // Runtime Check val myInvalidId: WeirdId = 6 // Compilation Error ```
My gut feeling is that the right way forward is to have a fairly standard type system visible in the source language augmented by contracts written in regular code. Basically a slight augmentation of assert(). A formal prover could internally reason about an extended type system where those contracts are automatically lifted to the type level if that helps for some reason, but programmers wouldn't be bothered with it.
This seems unlikely to be a genuinely novel idea, so I'd be curious to hear whether systems like that already exist.
There was a dialect of C#, Sing# or Spec#, that allowed you to specifying pre and post conditions in the same expression language as the main language, and they were checked at compile time. This is what comes closest I think.
This is one of the best features of the pascal family:
http://www.delphibasics.co.uk/Article.asp?Name=Sets
(look in "SubRanges")
That, plus the type incompatibility that arises from mixing such types with other integer types.
The ones that used it like it...
You could also argue that subtraction for unsigned numbers is only partially defined, just like for signed numbers. But that would be missing the point, since most numbers in practical programs are small, and for these numbers the signed range is indeed much more useful since subtraction is defined for signed integers (e.g. i32) for small numbers. This is not the case for unsigned, where 3u-4u is usually not what you want.
Perhaps the biggest issue all together is just that many languages will let you do 3u - 4u instead of outright making the syntax more obviously annoying to force you to think about the caveats and pick between {truncated, throwing, overflow} variants.
They are not. I write mostly Rust these days.
In reality, like all C keywords, it's completely misleading and actually really means "weird_arithmetic_mode_that_will_mess_you_up".
Not sure what they mean about it being misleading though. They might prefer it if they were called "modular integers" instead of "unsigned integers" but that would lead to confusion with modules IMO.
Modular integers to me would seem very confusing. They're integers without the sign, and they have some max value determined by the number of bits, I can't really think of a better name for them except for the fixed-width versions which include that bit information.
Extremely intuitive, simple English words, exactly what it says it is (integer without the sign bit).
In short, the operations on `unsigned int` do not really behave like "non-negative integer"; as such it's a weird match to use them for that purpose.
Whether the operation then errors out or wraps doesn't change anything about unsigned being the right name for it, because it's something you wouldn't expect unsigned to do.
The intersection of your two NonEmptySet produces an empty set. If you write that result into a NonEmptySet it's the same, it doesn't make sense for you to expect a NonEmptySet as a result of that operation.
- dangers of mixed signed/unsigned code (signed values MUST exist, but unsigned values don't have to)
- more cognitive load to read and understand unsigned underflow detection code + issues once you exceed the halfway point
This is why Java offered signed integer types only (I think they should have allowed unsigned as well, but for different reasons)
Please show me an example in the wild that could not be trivially caught/alleviated. With 'trivially' I mean the code that needs to be written to prevent it, not the thinking you need to do to consider it.
As for the latter: this is what I get paid for. Writing the code out is necessary but not what I really get paid for (unless I were a very slow typist, that is).
I find that most of the time I was simply too lazy. Or rather: I wrote C/C++ code for 20+ years. I used int and didn't think (unintended rhyme).
Now I write (mostly) Rust I find myself considering the edge cases regularly and also covering them because the compiler forces me to. See also this comment [1].
I.e. a - 1 + b where a is always positive (incl. 0) and b is always > 1 'just' works with int (and unsigned [overflow] too!) in C/C++.
In Rust you will get a panic when a = 0 which will then make you think what you're doing and simply reorder this to a + b - 1.
I find that this is the 'cognitive load' that needs to be applied commonly and I'm pretty fine with that.
> dangers of mixed signed/unsigned code
Alleviated by simply not mixing. There is a reason languages like Rust simply do not allow this without explicit typecasts. And those, in cases where one type is signed and the other is not and they have equal width translate to "all bets are off".
> more cognitive load to read and understand unsigned underflow detection code [...]
See first point. IMHO this is simply the same point expressed differently. Underflow happens when you subtract.
Ensure you do not subtract a larger value from a smaller. This is as easy as writing max(a, b) - min(a, b) or what author of [1] does.
Same as abs(a - b) but works with unsigned. Cognitive load? I do not see any and I agree with the author of the article that this is easier to read.
People WILL forget to check, or implement the check wrong (and it won't be discovered until the next black swan event), or some invariant will change in future and nobody will know to update this code. The code doesn't care because the compiler doesn't enforce the invariants, so you're left with bare and likely confusing (and probably eventually undefined) behavior.
I for one would LOVE it if popular languages could be instructed to inject invariant enforcement code (not asserts) at certain boundaries. It would help with a whole host of problems!
When you cross zero with a signed integer calculation, it's easy to find out, and the code has low cognitive overhead. Also, with code generally structured this way, bad input propagation tends to get stopped earlier because of the number of functions that check against negative values.
It's also possible to underflow check with unsigned, but the code is more complicated and can't stop propagation if it fails, and if you are allowing values > the signed positive limit (or unwittingly allowing it), your overflow detection code gets even more complicated (or wrong) due to the reduced overhead space. You COULD do a bunch of checks beforehand, but that's not always feasible due to the combination of operations being done on the operands, and once again people are people.
Even though many modern languages block uncast type conversions, that still doesn't protect you from converting a negative integer to an unsigned integer. Yes, you SHOULD be checking before the cast, buuuuuuut...
What we want to do is reduce the number of ways things can go wrong, reduce the fallout of an errant process, and minimize cognitive load to reduce bugs overall. Making that worse just to double the positive integer space doesn't make sense to me.
unsigned int length_a = 10;
unsigned int length_b = 20;
if (length_a - length_b < 0)
{
printf("negative diff\n");
}
else
{
printf("positive diff\n");
}
I would argue that there is plenty of code like that in the wild. It looks innocent and harmless but it gives a completely surprising result.This is a poor, poor substitute for contract checking.
My preference is to minimize surprise. If everyone is used to using signed types for everything, you better have a good reason for using something else, and leave that justification in a comment
Yes, and let's start with overflow behavior because it's much more relevant than the type domain.
If overflow isn't encoded by the type, there is just no way to correctly set a strict domain.
You see, doesn't make a lot of sense to distinguish between positive and negative in the end. From a mathematical point of view negative integers have the same dignity of positive integers since a couple of centuries. The same operations that apply on positive integers apply on negative integers, and not only that, an operation between two positive integers can as well result in a negative integer!
The unsigned type was created just to have one more bit if you *are sure* you have only positive integers. That could had a sense in the era of 8/16 computers. Nowadays that we have 32 or 64 bit computers does really that extra bit count that much? I don't think so... 2 billions is plenty enough for most usages.
I totally agree!
After some horrible bugs caused by unsigned integers in innocent looking C/C++ code, I'm 100% in the signed camp. The only time I use unsigned is when I need well-defined overflow behavior (which is rare).
As a bonus, using signed loop counters in C/C++ code enables certain kinds of compiler optimizations (based on the fact that signed integer overflow is undefined behavior): http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
The correct way is using ints, e.g. "int x = b[i] & 0xff;". Pretty much you should do math with int and long only. java.util.Integer/Long nowadays have static methods to work with unsigned types if you need them.
Once you remember that you need (the annoying) "0xff", you'll be free from errors. It has been there for 24 or so years. Other than that wrap your arrays into ByteBuffer and use provided utility.
The memory layout of the classes is quite immaterial here as the operation do happen within CPU registers.
[0]: https://docs.oracle.com/javase/specs/jvms/se12/html/index.ht... [1]: https://en.wikipedia.org/wiki/List_of_Java_bytecode_instruct...
static int square(int);
0: iload_0
1: iload_0
2: imul
3: ireturn
is java; compare to the c++ equivalent (used unsigned to avoid any possibility of undefined behavior): unsigned char square(unsigned char num) {
return num * num;
}
Which compiles to: mov eax, edi
imul eax, edi
ret
on x86 mul w0, w0, w0
ret
on arm.By this definition, c and c++ don't have "real" byte types either, because they undergo integer promotion for operations, and the generated code is operating on register sized values, not bytes. Java bytes use 8 bits as part of an object (with a fixed-cost padding); 8 bits as part of an array, etc. The fact that the bytecode has intermediate casts is not relevant to the actual code executed on CPU.
They're not actually operating on register-sized values: the code labelled x86 is also the x64 code, meaning GCC operates on 32b when the native registers are 64b. Likewise ARM.
Your assertion is even more debatable when Clang actually operates on 8-bit registers on x64:
mov eax, edi
mul al
ret
(it does not on ARM64 as `mul` is only defined for 32 and 64b)That Java has no support for unsigned integers is a very common complaint.
Several APIs in the VFX arena (Pixar OpenSubD, Pixar USD, and Foundry's Katana GeoLib API) all use signed ints for indices which I've occasionally argued against, with the response being "Google's coding standard says don't use them".
As for 64-bit values, unless you can foresee requiring > 8 quintillion, unsigned isn't buying you anything.
There are a number of ways to handle this:
- Use unsigned 32-bit (gives you a little bit more runway, but you'll still hit the end hard)
- Use 64-bit values (ends your problem once and for all, but costs double the memory so now you have a new problem)
- Use 40-bit values (Gives you a lot more runway, but costs CPU)
I looked at OpenSubdiv extensively. There are no good reasons to use signed in the cases I opened the ticket for and making sure the code inside the lib does the right thing with unsigned arithmetic is trivial.
But someone still needs to do that and writing that "Google (essentially) says you don't need to" in their style guide is much less work. ;-)
Timestamp arithmetic is a common case where unsigned integers with silent overflow is superior. You can avoid bounds checks and special cases by always computing a delta between a newer time and an earlier time. As long as you can guarantee that the sample period is less than the clock rollover period there will never be any ambiguity.
Ada tried imposing the purity of signed integers and had to add modular types to get these semantics because of their utility.
http://www.gotw.ca/publications/c_family_interview.htm
Gosling on why Java only has signed arithmetic.
> At the end of the day, code is for people, so keep it easy for people.
This is a dangerous heuristic, because people here means exclusively developers. It’s easy for us to trade annoying but mostly harmless bugs for rare but harmful ones.
But "unsigned by default" won't save you here; all it does is give you a little more breathing room for your special case code (and hey, maybe that doubled positive integer space is all you needed, in which case congrats).
But all of the other problems are still there. That's why I'm saying that "unsigned by default" is backwards. It should be "signed by default", and unsigned for special situations that warrant it.
A big one is dealing with currencies like Japanese yen in financial software.
The question is: Will the difference between 8 and 16 quintillion matter enough to say "unsigned by default"?
But currency types need to be signed anyway, so I guess that's that ;-)
I'm now back in the signed camp. Signed integers make it a lot easier to sanity check integer subtraction when negative values are disallowed (a common situation), and it's easy to reason about. Also, not converting between signed and unsigned avoids accidental conversion overflows due to different expectations, so keeping it signed bypasses that whole can of worms while maintaining maximum flexibility.
Unsigned gives you 2x the positive numeric range, which 99.999% of the time you'll never use (and if you did, underflow detection would become a nightmare).
I can't think of a single time I've heard someone complain "I wish Java's long type supported up to 16 quintillion instead of a paltry 8 quintillion"
At the end of the day, code is for people, so keep it easy for people.