Promotion Difficulties

(This is neither the first or last document on this, its a tricky problem. This one doesn't try to suggest a big fix by modifying the NumPy logic. ?Some of the following represents the state in NumPy 1.20, which existed probably since 1.7)

This is just a draft to capture some of the most important problems and a few ideas/thoughts. If you are seriously interested in it, contact @seberg. I may add more information in the future

Most computer languages define promotion in a way so that associativity does not matter. For example if int32 + float16 -> float16 (because all floats above all integers), then it is possible to create a linear promotion hierarchy, which solves most of the issues in NumPy. However, NumPy does not do this! NumPy's promotion hierarchy is loosely based on whether a cast would lose information or not (think "safe casting", but don't overstress this).

In the following we will use ^ as the promotion operator. Note that promotion is not necessarily a binary operation.

Issues with the NumPy promotion:

• Promotion of int64 and uint64 goes to float64. This is not technically safe, and strange since it breaks "categories" (integer to float). From a promotion perspective, it is not a big issue, however.
• NumPy promotion is not associative: uint32 ^ int32 ^ float32 -> int64 ^ float32 -> float64 but uint32 ^ (int32 ^ float32) -> uint32 ^ float32 -> float32

If we consider additional user DTypes, more problems arise. My important constraint is that introducing a new int40 should not modify existing code relying on int32 ^ uint32 -> int64! Introducing a single DType seems relatively unproblematic, but introducing e.g. both uint24 and int40 creates a difficulty:

• Clearly: uint24 ^ int32 -> int40 could be acceptable (if users want this)
• (uint24 ^ int16) ^ uint32 -> int32 ^ uint32 -> int64 cannot promote to int40, unless some additional (non-binary) logic is used!

Even if we ignore this issue and say that both DTypes know nothing of each other, it would be nicer if uint24 ^ int32 ^ int48 is guaranteed to raise an error. But left-to-right "reduction" would result in int48, while reordering it to uint24 ^ int48 ^ int32 would raise.

The situation gets much more dire with value based logic (ignoring user DTypes for now):

• NumPy effectively has a uint7 (and uint15, uint31, uint63) internally to represent a value such as 127 which could be "minally" uint8 or int8. But it doesn't (correctly) try to solve the associativity, at least when floats are involved (there is an is-small-unsigned flag, which is not correctly propagated, however):

  >>> np.result_type(2**7, -1, np.float16, np.float16)
  dtype('float32')
  >>> np.result_type(np.float16(1.), 2**7, -1, np.float16)
  dtype('float16')
  

• Whether value based logic is used or not, depends on the categories boolean, integer, floating, other. Here, no difference is made between unsigned and signed integers.

---

Both of these issues are generally very hard to solve generically (if we allow users to add new DTypes). There may not even a "good" solution at all. We mostly have multiple inputs to result_type in the context of np.concatenate((arr1, arr2, arr3)) or ufuncs with many inputs (rare, although e.g. numexpr builds them). Another example is np.array([...]) where it seems even less disirable to have complicated logic that must may require multiple passes. (np.array(...) does not use value based logic at least.)

It seems the pragmatic solution is probably to live with a lot of the quirks especially for value based promotion. For example, at least for now, we will keep the logic that value-based promotion is never used when a user DType is involved. Another solution for the value-based promotion is the solution e.g. JAX takes: ignore the value completely. A Python integer is considered to be below uint8 and int8 (even if it is signed or too large), and the same for floats. This is at least easy to understand! But as of now, it also is not a good fit as long as value based logic is used even for 0D arrays (which have a dtype!).

---

Some approaches that could be helpful:

1. A binary promotion operator is nice, but it would be possible to use the __array_ufunc__ approach of asking all involved DTypes until one knows the result: DType.__common_dtype__(*DTypes) -> common_DType or NotImplemented, i.e. an n-ary operator/dunder. This is at least easy. For value based, it also requires passing the values as well. The downside is that the reduce logic must be implemented by all new DTypes. It would be possible to add this additionally to a binary operator as __common_dtype_reduce__ or similar.
2. The initial problem of uint32 ^ int32 ^ float32 can be solved by doing a pairwise reduce with potentially a second (limited) pass when necessary (given below). This ends up with the most generic DType (which must know everything).

 *           c
 *          / \
 *         a   \    <-- The actual promote(a, b) may be c or unknown.
 *        / \   \
 *       a   b   c
 *
 * The reduction is done "pairwise". In the above `a.__common_dtype__(b)`
 * has a result (so `a` knows more) and `a.__common_dtype__(c)` returns
 * NotImplemented (so `c` knows more).  You may notice that the result
 * `res = a.__common_dtype__(b)` is not important.  We could try to use it
 * to remove the whole branch if `res is c` or by checking if
 * `c.__common_dtype(res) is c`.

3. Option 2. could be combined with option 1. (or something like DType.__promote_to_next_higher__(other)) to also solve the problem of adding both uint24 and int40 that was listed above.
4. Actually introducing "categories" as first class concepts could work, but probably also hits a brick wall when introducing value based promotion.

However, value based promotion is even more complicated. Since it would currently require at least distinguishing between singed and unsigned integers. And it also requires passing around the value (which is easy for "option 1.", but otherwise seems undesirable). In the point 2. above, this could be deferred.