Correctness of mixed signed/unsigned arithmetic

Question

I'm implementing signed and unsigned integers in my language. They are represented in C as signed long and unsigned long respectively.

struct value {
    enum type type; / SINT, UINT, ... */

    union {
          signed long sint;
        unsigned long uint;
        /* more types... */
    } as;
};

Basic arithmetic operations such as + and - may operate on integers of mixed signedness depending on the types of the operands:

struct value accumulator, argument;
/* ... */

/* accumulator.type == UINT && argument.type == SINT */
accumulator.as.unsigned_integer += argument.as.signed_integer;

This code causes the C compiler to emit warnings like:

warning: implicit conversion changes signedness: 'long' to 'unsigned long' [-Wsign-conversion]

Which makes me worried about the correctness of this implementation.

I considered simply making it an error to operate on values of mixed signedness. I feel this would make the language too annoying to use though since the programmer would be required to defensively convert the integers every single time.

I currently handle overflows by letting the values wrap around. I assume two's complement integer representation and compile with -fwrapv. I plan to implement overflow checks with transparent promotion to arbitrary precision integers in the future. I want to make integers work seamlessly just like they do in Python and Ruby.

So is there a correct way to implement this? Any pitfalls and footguns I should be considering? How do other languages do it?

Answer 1

So is there a correct way to implement this? Any pitfalls and footguns I should be considering? How do other languages do it?

Your proposed struct value is utterly bizarre and no language I know of works that way. Typically, a dynamically typed language will have just one integer type, and if it has a concept of a 'signed integer' or 'unsigned integer', that will be an annotation; you can check if a term satisfies the properties of an unsigned integer (being that it is an integer and it is non-negative), but it is still an integer, and if you add it to another integer, the result will also be an integer (the properties of which integer you can also check).

With that said, many languages include both integers and floating point numbers. The relationship between integers and floating point numbers is similar to the relationship between (fixed-width) integers and natural numbers (aka 'signed' and 'unsigned'), in that they are both subsets of the rational numbers, but neither is a subset of the other (so neither can losslessly be converted to the other's format). In that case, most languages make the result a floating-point number (it is a question whether it would be better to round once or twice, but I will ignore that for now). Why? Most 'common' integers (those with magnitude $\le 2^{53}$, and many others besides) are floating-point numbers, whereas a great many 'common' floating-point numbers (like 0.5) are not integers, so taking the result to be a floating-point number is more likely to be useful. You could similarly note that negative signed numbers with small magnitude are common, whereas unsigned numbers with very large magnitude are uncommon, so the result should be signed. But this is still incredibly error-prone and happens to be a major footgun in c.

Another source of inspiration could be machine codes. There, signed and unsigned integers are not distinguished at the data level—they are all just bitstrings—but rather by the operations we perform on them. Addition is the same always, but we can have a signed comparison or an unsigned comparison. You may also be interested in this paper.

Answer 2

This code causes the C compiler to emit warnings like: [...] Which makes me worried about the correctness of this implementation.

Let's examine this with an example:

accumulator.as.unsigned_integer = 2;
argument.as.signed_integer      = -4;

accumulator.as.unsigned_integer += argument.as.signed_integer;

So then accumulator.as.unsigned_integer will:

• have an small number, or;
• be near to 0xffff...ffff, or;
• will trap some math exception?

And, with another C compiler, or in another CPU, the reply above will remain?

---

This warning is telling you this code is not portable, because it contains behavior that is not guaranteed to hold (or even exist at all!) by C language standard (a.k.a., undefined behavior).

So yes, you should be worried that mixing signed with unsigned may produce weird results (as above) or produce different results (or no result at all) when compiling this code with another C compiler or in another CPU/architecture.

Answer 3

Warning

What is this warning about?

warning: implicit conversion changes signedness: 'long' to 'unsigned long' [-Wsign-conversion]

This does not necessarily indicate an error, but it does indicate the potential for one. The way C implements mixed integers arithmetic -- ie, arithmetic between integers of different types -- involve promoting one or both integers so they both end up with a common type, then performing the arithmetic in that type. When mixing signedness, the results may be unexpected, and unintended, thus the heads up.

Due to how wrapping arithmetic works, however, it is in your case benign. For example, adding -3 (signed long) to an unsigned long will result in converting -3 to an unsigned long (2⁶⁴-3) and adding that, which will cause the result to be 3 less, after wrapping... exactly matching the expected result.

Mixing

You may, however, still want to revise how your language should work with regard to mixed arithmetic. Mixing integers of various signedness (though same magnitude) may catch users unaware.

With wrapping arithmetic, it kinda works, but once you move to big integers, you'll face troubles. Suddenly that conversion from -3 to (2⁶⁴-3) will lead to a big integer, not the current unsigned value minus 3.

I would strongly recommend just ditching unsigned integers for calculus. They may be useful, at lower bit widths, for storage purposes, in languages aiming to provide compact storage, but that is not your case. For you, all you get is that the maximum shifts from 2⁶³-1 to 2⁶⁴-1 and that's quite pointless in the grand scheme of things. Few values are ever greater than 2⁶³-1 in practice, and of those that are, they are quite likely to be greater than 2⁶⁴-1 too.

It's just not worth the trouble you'll cause your users.

Yet

If you do insist in having both signed and unsigned, my advise would be to store them both as unsigned.

As mentioned, with wrapping arithmetic you'll get the same result anyway, so storing as two different types is artificial complexity with no upside. And if you have to pick one, you're better of with unsigned: you won't need a non-standard -fwrapv flag then as unsigned arithmetic is wrapping by default in C.

The only time you need to use the signed representation -- for comparisons -- you can just cast prior to comparing in the comparison implementation. That's ensure that -3 < 0, even if it's stored as 2⁶⁴-3.

Answer 4

I plan to implement overflow checks with transparent promotion to arbitrary precision integers in the future.

That's the key point driving my answer.

Right now, you only support a limited value range, covering -2⁶³ up to 2⁶⁴-1, with the user having to choose between -2⁶³ up to 2⁶³-1 or 0 up to 2⁶⁴-1. If some calculation overflows, the user gets mathematically wrong results.

In the future, your language will transparently handle integers of arbitrary magnitude. Then, types like unsigned-32, or signed-64 might only make sense for storage purposes, when interacting with "external" libraries, but not for calculations, and will hopefully throw an exception when trying to store a non-compliant value.

So, for the current intermediate state I don't see much benefit in supporting both signed and unsigned integer types. You burden yourself with the questions you stated above, and the user with the decision which type to use, and the reasoning in whixh cases the result will be what he expects.

My recommendation is to get rid of the unsigned type now. Java shows that a language can do rather well with only signed integer types. It has a few peculiarities, but nothing serious.

If you're trying now to come up with a sound definition e.g. whether adding a signed and an unsigned value should give a signed or an unsigned result, you're simply wasting time better spent in implementing the seamless-integer semantics.

You'll inevitably face lots of unsolvable situations where limited-size arithemetic yields unexpected results, you already have a very good plan to solve this in the future, so go and follow this plan.

BTW, I used to program a lot in Common LISP, and I very much appreciated its notion of unlimited-size integers, only under the hood distinguishing between fixed and variable size.

Answer 5

There seems to be three separate issues here:

1. exposing separate signed and unsigned types in a programming language;
2. having signed and unsigned data storage in the implementation.
3. working around the quirks of C when writing an implementation in C.

The second is easy: in general you want both, but in practice it's less cumbersome to use a single type (unsigned) for storage and to implement separate implementations of operators for those cases where results differ, especially ==, !=, <, <=, >, >=, >>, / & %.

You only need implementations of < and == as the rest can all be derived:

op	shorthand for
a!=b	not(a==b)
a<=b	not(b<a)
a>b	b<a
a>=b	not(a<b)

Unlike C, you should have multiple implementations of < and ==:

operator	operands	implementation
==	both same	naïve
==	mixed	false if not in common range
<	both unsigned	naïve
<	both signed	invert sign bits then as per unsigned
<	signed+unsigned	true if first operand is negative or second operand exceeds max_signed
<	unsigned+signed	false if first operand exceeds max_signed or second operand is negative

That also fixes the third issue: stick with just one, and be explicit about every type conversion. Write all your integer literals with an S or U suffix. Include guards to ensure assumptions actually hold, like: assert(sizeof(uint32_t) >= sizeof(int))

The first issue is less clear, since you've not said much about what's in your language.

Exposing "native size" signed and unsigned type is a known source of bugs, but that doesn't mean they're not useful.

I suggest that it would be less harmful to expose:

1. Unbounded integers, which use whatever available implementation is available, or throw an exception (or just abort) when there's no available implementation. This would use BigInt when you get around to implementing it.
2. Modulus integers, where the programmer (in your language) specifies the lower and upper bounds, and assignments to such a variable are implicitly mod-whatever. You can abort at compile time if you don't support their choice of bounds. In principle you could allow any pair of bounds, but initially you'd only want to allow the pairs that correspond to 8-, 16-, 32-, or 64-bit ints, signed and unsigned.

As for literals, I suggest copying what Go does: a numeric literal has its own notional type, but you can't declare a variable of this type. Instead, a literal is silently and implicitly converted to any numeric type (as long as it fits). If your language does type inference, then a numeric literal also has a preferred standard type. The compiler should perform all constant folding using "infinite precision" before using the results to generate code.

PS: having modulus apply on assignment means you actually need dual implementations of most arithmetic operators, one that traps on overflow, and one that ignores overflow (because it gets the right answer when later applying modulus). If you eventually get around implementing "arbitrary modulus", the target modulus needs to be included as a hidden third parameter to the non-trapping operators.

Answer 6

To prevent the warning, just use an explicit cast:

/* accumulator.type == UINT && argument.type == SINT */
accumulator.as.unsigned_integer += (unsigned long)argument.as.signed_integer;

This cast is well defined, and on a two's complement implementation it simply reinterprets the value as unsigned, there's no runtime overhead.

Answer 7

The real quastion you need to ask (and answer) is "what should happen if the result of the operation does not fit in the result type" (what happens on underflow and overflow). Related to this is "what is the result type of an operation on a signed and an unsigned type".

In C when you do an operation on a signed and unsigned value (at least for types at least as large as int) it does it as unsigned (converting the signed value to unsigned for the operation). That is largely because overflow of signed operations is undefined in C while overflow of unsigned is well-defined, so as long as you have unsigned types¹, you don't fall into undefined behavior.

If you don't care what happens on overflow, you can just ignore the warning and get whatever you get. If you do care, however, you need to decide what should happen first, and then you can write the code to get that result. Maybe converting to some bigint representation?

---

¹_{Yes, for unsigned types smaller than an int, they'll first be converted to (signed) int, which is sometimes unfortunate and annoying (and ends up requiring extra explicit cases to make things work properly)}

Answer 8

Unsigned integers may cause difficult to find bugs if they overflow into negative side (that is much more likely to happen than four byte int overflowing from unsigned four byte int):

  for (auto x = 0; x < myvector.size(); x++) {
    if (x - 1 < 1000) {
      // This code runs for x == 0 !
    }
  }

This generates no warning but does not work as expected. Subtracting 1 from 0 of the unsigned type (as inferred by auto) results a large number, more than 1000. Differently, using int would give as a warning about "mixing signed and unsigned" but it works.

In C++, many container and similar classes return unsigned integers without any real need. QT containers return sizes as signed integers.

Answer 9

You are getting a warning, not an error. The C or C++ standard tell exactly how mixing of signed and unsigned work, it is just that the rules are complicated and might not do what you expect or want, and therefore a warning is issued.

You need to decide what result exactly you want, and then you have to write the code to achieve these results. And if you add the exact conversions that the C rules would imply, then the warnings go away.