5
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Welcome to PLDI! It might be useful to know how you handle overflow with signed+signed and unsigned+unsigned operations. Whether it's checked, wrapping, or UB might influence the decision for how to handle signed+unsigned $\endgroup$ Dec 5, 2023 at 19:12
  • $\begingroup$ @RydwolfPrograms, it's currently wrapping as I assume two's complement integer representation and compile with -fwrapv but I plan to implement overflow checks with transparent promotion to arbitrary precision integers in the future, like in Python and Ruby. $\endgroup$ Dec 5, 2023 at 19:38
  • $\begingroup$ I would introduce unsigned integers only as a special case of a general feature: User-defined integers with restricted value ranges, the way Ada does it (e.g. Small_Int on this page). $\endgroup$ Dec 6, 2023 at 18:34
  • $\begingroup$ You might like to consider having an unnamed union, so that you can then write x.uint rather than x.as.uint. $\endgroup$ Dec 10, 2023 at 13:30
  • $\begingroup$ @MartinKealey I've always used unnamed unions but since discovering the as idiom I've come to prefer it. Short, correct, reads like natural english, distinguishes union fields from regular types and makes the type punning explicit. $\endgroup$ Dec 10, 2023 at 18:51

9 Answers 9

5
$\begingroup$

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.

$\endgroup$
12
  • 2
    $\begingroup$ The structure seems bizarre but it's just a fat pointer structure. One word holds a descriptor, another holds the actual value which may be signed, unsigned, arbitrary pointer, or a pointer to a heap allocated language object. This lets me very easily work with primitives. I asked about it recently, on stack exchange and on reddit. I've grown to like it a lot and I'm almost done converting my entire interpreter to this approach. $\endgroup$ Dec 5, 2023 at 20:58
  • 8
    $\begingroup$ What is bizarre is distinguishing signed and unsigned types in a dynamically typed language. The discriminated union representation is completely standard. $\endgroup$
    – Moonchild
    Dec 5, 2023 at 22:06
  • 3
    $\begingroup$ What is weird about bitwise operations in python? I find them very simple and intuitive. $\endgroup$
    – Moonchild
    Dec 5, 2023 at 22:52
  • 1
    $\begingroup$ "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" this is really wise. I like this approach. $\endgroup$ Dec 6, 2023 at 17:18
  • 1
    $\begingroup$ @Barmar that is completely standard. $\endgroup$
    – Moonchild
    Dec 6, 2023 at 19:46
5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Why would it trap? Unsigned arithmetic in C is well-defined as modulo arithmetic. The result will be correct (if applicable, modulo 2^n) if interpreted as unsigned. It will, interestingly, also be "correct" if interpreted as signed; in the example, the result of the addition modulo 2^n, UINT_MAX-1, has the same bit representation as a signed -2 in 2's complement. In C it's also OK to convert the type through a union. $\endgroup$ Dec 6, 2023 at 18:46
  • $\begingroup$ Because integer promotion silently transforms unsigned into signed: reddit.com/r/C_Programming/comments/10jc3hu/… $\endgroup$ Dec 6, 2023 at 19:27
  • 1
    $\begingroup$ That case concerns an int which is wider than the uint32_t the operands have (i.e., do not rely on a 4 byte int assumption). In that case, lesser-than-int-ranked integer operands are promoted to int or unsigned int as part of the integer promotions (n1570, 6.3.1.1). But here, [unsigned] int is used already, so there is no promotion. The operands of unsigned int and int types then undergo the usual arithmetic conversions to arrive at a "common real type". In this case, the member is unsigned int and of equal rank to -4, so -4 is converted to unsigned int. $\endgroup$ Dec 6, 2023 at 19:49
3
$\begingroup$

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 (264-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 (264-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 263-1 to 264-1 and that's quite pointless in the grand scheme of things. Few values are ever greater than 263-1 in practice, and of those that are, they are quite likely to be greater than 264-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 264-3.

$\endgroup$
3
$\begingroup$

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 -263 up to 264-1, with the user having to choose between -263 up to 263-1 or 0 up to 264-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.

$\endgroup$
1
  • $\begingroup$ I'm inclined to agree. I thought I needed unsigned because the language will interface with low level Linux structures, but after all these answers I'm thinking that's not the case at all. I should just make all arithmetic signed. $\endgroup$ Dec 6, 2023 at 17:16
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 types1, 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?


1Yes, 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)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .