21 Mar 2017

Extensible Numeric Types

Programming languages deal with arithmetic overflow in different ways. Some, like Python, automatically create an unlimited-size integer when an int overflows. Others, like Swift, signal an error. Java wraps around. In C++, this is undefined, which means anything can happen, such as a random result, a crash, or even other variables becoming corrupted. These four languages handle overflow in four different ways!

Which of these behaviors should a language adopt?

The fallacy is in assuming that there should be only one. Swift, for example, normally signals an error on overflow, but offers an alternative &+ operator that wraps around. We can take this one step further, and offer several addition functions [1]:

- add(), which throws an exception on overflow.
- add_promote(), which returns an int one size bigger than its arguments, like int64 if the arguments are int32 [1].
- add_wrap_around()
- add_unsafe(), which is like C++, where overflow is results in undefined behavior, which is C++-speak for "anything can happen".

That way, you can use whichever type of addition is appropriate for the task at hand.

Once you have different kinds of addition, you can define + as an alias for add(), which is a safe default. When you need performance, you can always use another addition method. Even in performance-sensitive code, only a small fraction of the code accounts for most of the execution time, so there's no reason to sacrifice safety globally.

Some of these addition functions may be implemented using others, but that's an implementation detail.

You could also define a new type of addition. For example, if I'm processing images, I wouldn't want a pixel value to wrap around and have a bright pixel in the sky become dark. I would instead want the value to get saturated at maximum, like 255. I could implement that defining an add_saturate() function. That's the benefit of getting out of the straitjacket of thinking there must be only one kind of addition operator.

T add_saturate(T a, T b) {
  try {
    return a + b;
  } catch (OverflowException e) {
    return T.maxValue;
  }
}

With generics, your definition works for all types for which addition is defined.

This is exensible not just to new types of addition, but to new number types as well. Suppose you're doing scientific calculations, and you want to track floating-point error bounds in addition to the result, like 9 ± 0.1. You could define a new data type for this, and implement arithmetic operators for it. For example, you could consider two ranges to be equal if they overlap. For less than comparisons, you could choose not to implement <, instead defining two functions definitely_less_than() and probably_less_than(). The former returns true if the max of the first range is less than the min of the second range, and the latter returns true if the mean of the first range is less than the mean of the second range.

A financial program may use a decimal integer to accurately record paise and cents. Other programs may want rational numbers. Or complex numbers. Again, with the ability to overload operators, so that everything works as expected [3].

For custom numeric types to fit well into the language, we also need implicit promotions as in C++, like converting a double to a complex [4]. And conversely, if you have an unsigned_double type that's just a double with an assertion that it's >= 0, you should be able to implicitly convert it to a normal double.

Conversions should be implicit only when there's no loss of accuracy. Implicitly converting a rational to a double is probably a bad idea since you lose accuracy: converting 1/3 to a double and then multiplying it by 3 may not result in 1, exactly.

To facilitate custom numeric types, the language should also let us define data types, without a heap allocation, or other overhead like runtime type information that primitive types don't have. Performance considerations aside, custom numeric types will be natural to use only if they have the same syntax and semantics (like pass by value) that primitive types have [5].

[1] Named functions are more readable than cryptic operators like &+ or #+. It's anybody's guess what that means.

[2] add_promote isn't defined on Int64, since there isn't a bigger type to promote to. This assumes a statically typed language.

[3] Since + is just an alias for a function named add(), when I say operator overloading, I really mean template specialisation — specialising the add() template for a particular type.

[4] Assuming a complex is a pair of doubles.

[5] If primitives are passed by reference, as in dynamically typed languages, so should custom numeric types. The point is consistency.

No comments:

Post a Comment