Unfortunate definition of `Base.widen`

[PatrickHaecker]

Currently calling @define_integers defines Base.widen to be BigInt if the type with twice the bits does not exist yet.

This is unfortunate in my opinion:

using BitIntegers
@define_integers 24
@define_integers 48
widen(Int24)

results in BigInt, whereas (in a new REPL)

using BitIntegers
@define_integers 48
@define_integers 24
widen(Int24)

results in Int48.

The order of type definitions in Julia typically can make the difference between a valid and an invalid program (Exception), but does not implicitly change the program. Here we have an implicit effect on runtime, memory (e.g. going from 3 byte (4 bytes depending on how you count) for Int24 to 16 bytes for BigInt) and result in addition to the unintuitive behavior. I think at the very least this behavior should be prominently documented.

However, I think the current implementation is even more problematic. The documentation of widen states

If x is a type, return a "larger" type, defined so that arithmetic operations + and - are guaranteed not to overflow nor lose precision for any combination of values that type x can hold.

Therefore, I think the natural result of widen(Int24) according to the citation is Int32. However, if you want to multiply two arbitrary Int24s, you probably want to widen either to Int48 or to Int64. It won't get easier if you think about what widen should do for Int40, Int48 and Int56: Depending on the situation it should either be the next 8 bit larger type, Int64, the type with twice the number of bits, Int128 or BigInt.

In addition, the documentation contains this ambiguous sentence

For fixed-size integer types less than 128 bits, widen will return a type with twice the number of bits.

I am pretty sure that this is meant as

For predefined fixed-size integer types less than 128 bits, widen will return a type with twice the number of bits.

We can get that changed, I think.

The main problem of the current implementation is that the methods are defined by the macro call and therefore in the caller's namespace. Therefore, the user can't define widen themself. I therefore suggest to not define widen at all in @define_integers and instead provide examples in the documentation how the user can define it depending on their needs.

[rfourquet]

Thanks for raising the issue, I agree that this should probably be changed.

I think I would still lean towards defining a default widen, perhaps with a catch-all generated function (not in the @define_integer macro), which chooses the smallest integer type defined in this package (Int256, Int512, Int1024) which either has at least twice the number of bits. This would fix the problem of definition order, and still allow users to define their own widen.

Perhaps defining widen to give a type which is only 8 bits larger has value for some usecases, but this would break widemul, so wouldn't be good as a default.

We could also imagine convenient syntax to define widen easily, e.g. @define_integers 24 (Int24 < Int48) (UInt24 < UInt48), but that can certainly happen later.

[PatrickHaecker]

Thanks for considering this issue.

I would still lean towards defining a default widen

I think a default implementation of some abstract type, which can be overridden for each specific type, should work if the problem is also prominently documented.

but this would break widemul

I think as long as we define widemul(x, y) to be at least sizeof(x) + sizeof(y) we should be fine. In other words, I think there is value to distinguish between addition and multiplication and therefore between widen and widemul. But this difference is made a lot less intense in Base than I would like.

[rfourquet]

But this difference is made a lot less intense in Base than I would like.

Yes totally agree. It's just that I'd rather have integers from this package behave as closely as possible to their Base cousins; so I would prefer not defining widemul here and have the default method work. And then document that widen can be specialized (in which case widemul should be taken into account by the user).

[adienes]

I just hit something similar: would it be at all feasible for BitIntegers.@define_integers 2048 to make widen(UInt1024) == UInt2048 ?

[PatrickHaecker]

Thanks, @adienes, for bringing this up again.

I think I've found a Julia-generic improvement idea and haven't realized until now that it also applies to this issue. It would solve the problem that the user can't define it's own widen method while still having a default widen method. It would not solve, however, the problem of the order-dependent definitions (but it may provide a path towards that if we think more about it, but one step after the other) and therefore the discussion of which method should be the default one.

I'll first make it specific. We can have it abstract afterwards.

The idea is that UInt24 does not have AbstractBitUnsigned as its direct supertype. Instead, it has AbstractUInt24 as its direct supertype, which has AbstractBitUnsigned as its own direct supertype, so we have:

UInt24 <: AbstractUInt24 <: AbstractBitUnsigned # <: …

and therefore

Type{UInt24} <: Type{<:AbstractUInt24} <: Type{<:AbstractBitUnsigned}  # <: …

BitIntegers will then define its methods for AbstractUInt24 or Type{<:AbstractUInt24}. Besides the change of the direct supertype (visible when supertype is explicitly or implicitly called) nothing changes for the user per default. However, they can now define their own, e.g.,

widen(x::UInt24) = UInt32(x)

method (with their favorite definition), which is more specific than the default definition and therefore will take precedence.

Generically, @define_integers would need to define the two abstract types Symbol("Abstract", SI) and Symbol("Abstract", UI) having AbstractBitSigned and AbstractBitUnsigned as supertypes, respectively, and using the new abstract types in the following method definitions.

Instead of using, e.g. AbstractUInt24 we could shorten it to AUInt24, because type constraints tend to become quite long when we prefix every type with Abstract. The A could be the abbreviation for Abstract, but it also makes sense and reads well on its own in type constraints: When we constraint to AUInt24 we want a (like in any) type behaving like the concept of a UInt24 type. UInt24 fulfills this, as it is a UInt24, or in short AUInt24. There could be other types which fulfill this (having AUInt24 as superclass), but at least in the beginning there would be none (this is the provided path hinted above: We (or the user) could provide several types inheriting from AUInt24 with different defaults for widen, WSI or WUI).

I can create the PR if this was too abstract (pun intended).