Julia: make Bool <: Unsigned (i.e. UInt1)

[StefanKarpinski]

Original title: "make Bool not a subtype of Number"

C.f. https://github.com/JuliaLang/julia/issues/18367. I propose simply changing the type hierarchy so that Bool is not a subtype of Number since it is so often an exceptional case. We could still keep useful arithmetic behaviors like true + true == 2, etc. – arithmetic need not only work for numbers. Once upon a time UInt8 + UInt8 produced an Int, but that's no longer the case, so now Bool is the "odd man out". If we make !(Bool <: Number) then we can at least make the behavior of Number completely consistent.

[carlobaldassi]

Are there any problems caused by not having a completely consistent behavior of Number, i.e. of having an exception in their promotion rules as opposed to having that same "exception" outside of Numbers? (It's an honest question, I'm not trying to be polemic.)

[jiahao]

Would we still allow an idiom like sum(data .< 5) to count the number of entries smaller than 5? I find this particular idiom very useful.

[andyferris]

count(data .< 5) could count the number of entries greater than 5.

That said, Stefan explicitly stated that arthmetic ops like + (used by sum) could stay the same.

Overall, I think this is a great move. Bool is also unique in that it is the only type accepted by if, unlike in C, which is why I always thought it odd that Bool shared the same basket as integers.

[StefanKarpinski]

Are there any problems caused by not having a completely consistent behavior

Dispatch ambiguities used to be a big problem but since we don't warn about those anymore, they're less of a problem now. Otherwise, it's just a matter of making it harder to describe and anticipate what generic code is going to do.

[JeffreySarnoff]

:100: (_so many months of Bool mucking about the Integer subtyping tree_)

[StefanKarpinski]

@JeffBezanson wants to know what problems this change would solve, and I'm drawing a blank. Probably because I've been on an issue triage call for six hours, so if people can post problems this causes, that would be helpful.

[JeffreySarnoff]

omg -- any new type that subtypes Real pulls in Bool and that (in every case I have encountered) necessitates weird, nonintuitive method dispatch definitions involving Bool to keep the ambiguity away.

For me, this has been a real drag all along. And I have other's source with comments like # this has to be defined or many conflicts arise at runtime. Then there is the reasonable distinction between Signed and Unsigned into which Bool really should not Venn. I passed on a package for time-related logic because the type hierarchy has had Bool sequestered in a way that makes extending AbstractLogic to TemporalLogic while keeping boolean stuff along for the ride very difficult.

abstract type AbstractLogic end
primitive type Bool < Unsigned 8  end # why should the multivalue true,false be Signed?
abstract type TemporalLogic <: AbstractLogic end
struct AllenLogicalPredicate <: TemporalLogic
   ...
end

[JeffBezanson]

The ambiguities might arise just from the methods like *(y::Number, x::Bool). We might be able to remove those.

We have Bool <: Integer, but not <: Signed or Unsigned. Would Unsigned be better?

[JeffreySarnoff]

yes

[StefanKarpinski]

Resolved:

• try making Bool <: Unsigned instead of Bool <: Integer
• try removing very generic methods like *(b::Bool, x::Number) = b ? x : zero(x)

[mschauer]

Will false stay a strong zero? I.e. x + NaN*false = x?

[JeffBezanson]

Ah, that must be what those * methods are for. In that case, they can at least be restricted to AbstractFloat like + is.

But, is there any motivation for having that special behavior other than trying to make Complex{Bool} act like an imaginary unit?

[mschauer]

There is some discussion in #22733.
The behaviour is convenient, see Complex{Bool} and the ability to capture the logic of sparse linear algebra, see fill(false,1,1) * fill(NaN,1,1) == sparse(zeros(1,1)) * sparse(fill(NaN,1,1)). Then there is also https://arxiv.org/pdf/math/9205211.pdf

[JeffBezanson]

Ah, nice reference!

[GunnarFarneback]

See also #5468.

[JeffBezanson]

I'm experimenting with making Bool <: Unsigned. It generally goes fine, but we have some definitions for mixed signed-unsigned operations (div, fld, rem, and mod) that prefer Unsigned (e.g. div when the first argument is unsigned). This is a bit odd, since any mixed-type operation with Bool might as well just use the type of the other argument. This is arguably already an issue for other small unsigned types, e.g.

julia> div(0x10, 2)
0x0000000000000008

[JeffreySarnoff]

what are these intended to convey
where op is one of { div, fld, cld } or { rem, mod }

 res1 = op(5, false)    ;  res2 = div(false, 5)
 res1 = op(5, true)     ;  res2 = op(true, 5)
 res1 = op(0x05, false) ;  res2 = op(false, 0x05)
 res1 = op(0x05, true)  ;  res2 = op(true, 0x05)

[JeffreySarnoff]

abstract  type Integer <: Real end

abstract  type Unsigned <: Integer     end
primitive type UInt8    <: Unsigned  8 end
primitive type UInt16   <: Unsigned 16 end
..

abstract  type Signed <: Integer   end
primitive type Int8   <: Signed  8 end
primitive type Int16  <: Signed 16 end
..

abstract  type Logical <: Integer   end
primitive type Bool    <: Logical 8 end

(making it easier to develop through the Logical abstraction)

primitive type Tribool <: Logical  8 end # false indeterminant true
primitive type Perhaps <: Logical  8 end # false perhapsnot uninformed perhaps true
primitive type Fuzzy   <: Logical 16 end # bit indexed degrees of membership

compare

primitive type Bool    <: Unsigned  8 end # false indeterminant true
primitive type Tribool <: Signed    8 end # false indeterminant true
primitive type Perhaps <: Signed    8 end # false perhapsnot uninformed perhaps true
primitive type Fuzzy   <: Unsigned 16 end # bit indexed degrees of membership

[TotalVerb]

Does this idea include true + true === false? The current state of affairs is quite inconvenient; most types don't overflow to a larger type on addition.

[StefanKarpinski]

If true + true == false then we can't use addition of bools to count how many things are true, which is a very common and useful pattern. How is the current state of affairs inconvenient?

[TotalVerb]

I ran into this issue with #22825; it's tough to handle Bool sanely in sum because one has to deal with zero(::Bool) + x::Bool !== x::Bool. Note that sum(::Vector{Bool}) wouldn't be changed; just x::Bool + y::Bool + z::Bool.

[StefanKarpinski]

Just do (b1 + b2) % Bool or more generally (x + y) % T and it should work fine for generic types.

[TotalVerb]

That's not the reason for the trouble; when determining what thing to sum when summing an iterable, we somehow need to make the decision of whether to promote to system size or not. Inconveniently, because of types that aren't closed under +, the only way to do this is to check the type of zero(x) + x instead, and it means the system cannot work for both sums and products.

julia> sum(Any[true])
1

julia> prod(Any[true])
true

[TotalVerb]

It's fair that (x > 0) - (x < 0) is convenient notation and we'd not want to lose it, so I suppose the extra complexity in reductions is not terrible. However, I'd guess there are other parts of Base and packages where it is generally assumed that types are closed under +, and it may be worth revisiting them.

[JeffBezanson]

I don't think we can change Bool arithmetic; that's just too much. The current behavior is useful enough that it's worth special-casing in various places.

For this issue, I don't really see enough value in Bool <: Unsigned.