Introduce `UInt1` type to replace misuse of `Bool`

[TotalVerb]

This will solve a whole bunch of problems.

• UInt1 is a lot more intuitive than Bool as a identity element for promote_type.
• true + true === 2 won't be inconsistent with every other unsigned type; we can have UInt1(1) + UInt1(1) === UInt1(0) as expected.
• Bool can be made non-numeric. (cc @StefanKarpinski)

I think the current system is really not ideal; it's worse than a method pun: it's punning a type for two very different things.

[TotalVerb]

If we decide to commit to UInt1 as an identity element for promote_type, then a lot of advantages fall out. For instance, sum([]) and prod([]) could return a usable result.

[stevengj]

sum([]) still can't return a usable result, because UInt1 is only an usable as an identity element for promotion of numeric types.

[TotalVerb]

sum([]) should return UInt1(0), and prod([]) should return UInt1(1). Because most Julia code is type-stable, it is easy to forget that some code cannot be made type-stable.

Here's an example: map(length, []) returns Any[], because methods of length can return anything. So prod(map(length, [])) currently fails. This is not the most efficient code (mapreduce works better) but demonstrates a case where the current situation of bailing out because there's no one(Any) is just not appropriate.

[ararslan]

Because most Julia code is type-stable, it is easy to forget that some code cannot be made type-stable.

Then in the interest of maintaining as much type stability as possible, wouldn't it make more sense to continue to error on sum([]) and prod([]) rather than returning something of a different type?

[TotalVerb]

sum(::Vector{Any}) is already type-unstable, and it couldn't be any way else. The only time where it fails is when the vector is empty, which is a very annoying inconsistency.

[oxinabox]

Am I understand this right? This would be a large change to the behaviour of addition of Bools.

I suspect making true + true == false will break a lot of code. For example I often calculate the accuracy of a binary classifier by:

mean(output .== ground_truth)

However this is probably bad. It doesn't work in most languages.

I am in-favor of breaking lots of code, to get the language right, prior to hitting v1.0

[TotalVerb]

@ararslan I cannot stress enough that Vector{Any} is an important case that should be dealt with properly, because this is commonly what is produced whenever code can't be made perfectly type-stable. As it stands, to find the sum of elements in a Vector{Any}, the code must be isempty(xs) ? 1 : sum(xs). This is not just a theoretical concern; it comes up in practice in extremely common areas.

[TotalVerb]

@oxinabox I propose that Bool be made non-numeric, and that UInt1 be introduced to model F₂. Note that the common notational meaning of + and * on Bool is | and & respectively; these already have symbols in Julia and so defining + and * on Bool is not necessary and can be removed.

To calculate the accuracy of a binary classifier, you can just convert the Bools to Float64 first: mean(Float64(x) for x in output .== ground_truth).

[ararslan]

For @oxinabox's specific case there, you can pass a function/type constructor as the first argument to mean (same goes for sum and prod), so you can do mean(Float64, output .== ground_truth).

[andyferris]

+1 for UInt1 - it sounds really useful to have Z2. What will a bit in a BitArray be, though? Will we need BoolArray?

I also kind-of like having true + true == 2 but I agree it is kind-of disgusting at the same time.

As it stands, to find the sum of elements in a Vector{Any}, the code must be isempty(xs) ? 1 : sum(xs)

I assume that is meant to be a zero, not a one. We could specialize sum(::AbstractVector{Any}) etc to do exactly this. Or even better, why not just define a method for zero(Any) and one(Any)? For instance, if zero(::Type{Any}) = 1 (or 1.0, maybe) then zero(Any)::Any so it's all very consistent.

(As an aside, in other contexts I've also been wanting a singleton One() and Zero(), which might be useful here? For a simple example. consider Float64(Zero) (meaning roughly convert(Float64, Zero())) instead of zero(Float64). We don't have pi(Float64) but we do have Float64(pi) - because it makes sense that way!).

[stevengj]

sum([]) should return UInt1(0)

@TotalVerb, the problem is that UInt1(0) is the additive identity only for numbers, whereas sum (by design) works for anything with a + operation (and ideally zero too). There is simply no satisfactory way to define sum for Any[], because there is no additive identity that works for any conceivable type defining +.

This is why zero(Any) is undefined.

[andyferris]

because there is no additive identity that works for any conceivable type defining +.

Maybe this plays nicer with my suggestion of Zero() such that MyType(::Zero) should be defined along with +. We can have Any(::Zero) = Zero() and sum([]) = Zero() and if you try to add that result to anything else that supports + then it would all work out (we could have +(x, ::Zero) = x, etc, already defined in Base). It won't always be type stable, but it might always be "logically stable".

[stevengj]

@andyferris, honestly, it seems like an opaque Zero() will confuse a typical user, it won't work with lots of methods (imagine a user doing sin(sum(A)) and passing A=[]), and it adds one more obscure method to the list of things a type needs to implement. Anyone who understands Zero() can surely use T[] instead of [].

[TotalVerb]

How often does one take the sum of non-numbers? Nobody is actually writing sum([]). This is about handling the empty case sanely, in 90% of cases at least, which is a strict improvement over an error, which handles 0% of cases.

[ararslan]

How often does one take the sum of non-numbers?

I would venture a guess that it's rather common amongst people coming to Julia from R. That said, I don't think sum(::Vector{Bool}), akin to Lyndon's example, is what should actually be used in Julia; that's why we have count.

I think another important question we should ask is: how often does one take the sum of Array{Any}? IMHO it might even make more sense to have all reduction operations fail on Array{Any}, not just the empty case, perhaps saying something like "Cannot reduce an array of type Any. Convert the elements of the array to a common type first." I think that may be annoying in some cases, but folks will end up with type-stable code as a result.

If UInt1 becomes a thing, I think we'll have to think carefully about deprecation so as not to suddenly and mysteriously break things that relied on these kinds of operations on Bools that we didn't foresee.

[stevengj]

@tkelman, it's not that uncommon to sum arrays of arrays of numbers, for example. And note that we throw an error for sum(Vector{Int}[]) too; it would be weird if loosening the array type made it "work" (but probably not give what you want).

Giving something that is definitely wrong 5% of the time is worse than giving an error 100% of the time, in my opinion.

@ararslan, Julia is a still a dynamic language. In many other contexts, we allow objects of type Any and determine method applicability at runtime. I don't see why sum of non-empty Any[...] arrays shouldn't be the same — if + works, it should work.

[stevengj]

Anyway, this discussion is a bit derailed. Whether a UInt1 type makes sense is independent of whether zero(::Type{Any}) = UInt1(0), and the empty case of sum can be (and has been) discussed elsewhere.

[stevengj]

See also e.g. #8092, #12461, #6994, #6069 for discussions of sum and the empty-array case.

[TotalVerb]

@stevengj It is precisely because all those are closed that I'm discussing this here. Furthermore, I'm reminded of

julia> map(() -> 2)
2

which is a generalization to the empty case that has a similar objection—it is an incorrect generalization in some cases; perhaps I would have expected [2] or [2, 2, 2]. But yet in this case, we do not throw an error, because returning the simplest possible result is sane in many situations.

[TotalVerb]

Also, I disagree that this discussion is irrelevant to UInt1. The existence of a zero or a one that can promote upward to any numeric type is a strong endorsement of returning those zeros or ones as a degenerate base case for certain operations. The current situation with Bool is unfortunate, and it is understandable why sum([]) should not return false, for a variety of reasons including user bewilderment.

[TotalVerb]

A naïve implementation of the Flatten iterator type demonstrates why a sane default is really not such a bad thing.

immutable Flatten
    xs
end
length(itr::Flatten) = sum(length, itr.xs)  # seems reasonable enough?

Then length(Flatten([])) breaks down.

[stevengj]

The map case is very different, because it is a question of dispatch on the argument signature, not on the values.

[TotalVerb]

I disagree that it is very different. It is just as conceivable to imagine map(f, xs...) as it is to imagine sum(xs).

[StefanKarpinski]

I'm not convinced that we need or want UInt1. If people want Z2 modular arithmetic, it seems like a modular arithmetic package would be a better way to get it.

[TotalVerb]

But we need a type that can be promoted upward to any other type. Currently we're using Bool for this, but UInt1 makes more sense.

[StefanKarpinski]

What do we need it for? There's not a lot of use cases that aren't inherently type unstable.

[TotalVerb]

For instance, im = Complex(false, true), ε = DualNumber(false, true), etc.

[StefanKarpinski]

Yeah, I'm not entirely sure those are a good idea anymore. Having an Imaginary type may be better.

[TotalVerb]

I disagree. Should we have three Quaternion types, one for each axis?

[andyferris]

Yeah, I'm not entirely sure those are a good idea anymore. Having an Imaginary type may be better.

I disagree. Should we have three Quaternion types, one for each axis?

Sorry to beat the same drum, but we only need two special types for all these cases and more:

zero = Zero()
one = One()
# (::Zero)(::Type{Float64}) = 0.0 (just saying that we can replace the function zero() entirely with call on singleton zero)
im = Complex(zero, one)
ε = DualNumber(zero, one)
q1 = Quaternion(zero, one, zero, zero)
q2 = Quaternion(zero, zero, one, zero)
q3 = Quaternion(zero, zero, zero, one)

I agree that it is potentially confusing to introduce these singletons, and it would be worryingly difficult to get it neat and tidy (e.g. an imaginary number Complex(zero, 1.23) would need two type parameters, Complex{T1,T2}), but I am suggesting these here as a useful alternative to UInt1 if you just want some number which promotes correctly to other numbers.

[TotalVerb]

@andyferris That is indeed a good idea. If we have these singletons, then I wouldn't mind if UInt1 were defined in a separate package.

However, I like Complex{T} better than Complex{T,T}.

[andyferris]

Making Complex{T1,T2} would possibly be the most breaking part. E.g. code that has Matrix{Complex{Float64}} will be a matrix of abstract types - so maybe not "breaking" but certainly slowing everything down by an order of magnitude (run-time as well as programmers having to type Complex{Float64, Float64} and Quaternion(Float64, Float64, Float64, Float64}.

But maybe more flexible?

[TotalVerb]

Since these are likely constant-folded at compile-time, Complex{Union{Zero, One}} is likely just fine for performance.

[andyferris]

having to type Complex{Float64, Float64}

Unless the language supported default arguments on type parameters, like immutable Complex{T1 <: Number, T2 <: Number = T1}.

Since these are likely constant-folded at compile-time, Complex{Union{Zero, One}} is likely just fine for performance.

Won't work for Imaginary, though.

[TotalVerb]

We simply don't need an Imaginary type; Complex does just fine.

The definition

const im = Complex{Union{typeof(zero), typeof(one)}}(zero, one)

should work.

We could even reuse the functions zero and one for these new numbers.

[andyferris]

We simply don't need an Imaginary type; Complex does just fine.

Well it does "just" fine, but Imaginary is a performance enhancement. Consider z * im with complex z. This calculation does two useless multiplications and two useless additions by 0 (or false). Have an imaginary type would effectively double the speed of this calculation.

Furthermore, having zero and one would remove the other useless multiplication by 1 (or true), making it even faster. @StefanKarpinski for these reasons I see these as complementary features/optimizations (i.e. removes the desire for Complex{T1,T2}).

We could even reuse the functions zero and one for these new numbers.

That is interesting. But we have to type typeof(zero) sometimes...

[TotalVerb]

If we must have this Imaginary{T} type, I would prefer it not have its own name, but be Complex{typeof(zero), T}. In any event, I disagree that im should have Imaginary type — it seems far more useful to have it be Complex.

[andyferris]

Furthermore, having zero and one would remove the other useless multiplication by 1 (or true),

I also wonder what we can do with constant propagation in this space, e.g. if multiplying by const(1) could be made a no-op in inference or something. Not sure how to make this user-extensible, though.

If we must have this Imaginary{T} type, I would prefer it not have its own name, but be Complex{typeof(zero), T}. In any event, I disagree that im should have Imaginary type — it seems far more useful to have it be Complex.

Not that I completely disagree, but I'm guessing that people would take a new type over huge breakage. But we haven't reached version 1.0 yet, so who knows?

[TotalVerb]

I would also rather target having the optimizer constant-fold the multiplication by im than distinguishing its type. This seems simple enough if * is inlined and the return value of false * x is a compile-time constant. In fact, I wonder if it is not done already.

[TotalVerb]

An Imaginary type is simply a major disaster for usability. Consider the vector [1+0im, 1im, -1+0im, -1im] which would suddenly have type Any. Sure, this can be fixed with 0+1im, but that is just unnecessary typing.

[TotalVerb]

For what it's worth,

julia> f(x) = x * im
f (generic function with 1 method)

julia> @code_native f(0+0im)
    .text
Filename: REPL[25]
    pushq   %rbp
    movq    %rsp, %rbp
Source line: 1
    movabsq $140696697704352, %rax  # imm = 0x7FF680B00FA0
    movb    (%rax), %cl
    movb    1(%rax), %r9b
    xorl    %r8d, %r8d
    andb    $1, %cl
    movq    (%rsi), %rdx
    movq    8(%rsi), %rsi
    movq    %rsi, %rax
    cmoveq  %r8, %rax
    testb   %cl, %cl
    movq    %rdx, %rcx
    cmoveq  %r8, %rcx
    andb    $1, %r9b
    cmoveq  %r8, %rsi
    subq    %rsi, %rcx
    testb   %r9b, %r9b
    cmoveq  %r8, %rdx
    addq    %rax, %rdx
    movq    %rcx, (%rdi)
    movq    %rdx, 8(%rdi)
    movq    %rdi, %rax
    popq    %rbp
    retq
    nopw    %cs:(%rax,%rax)

My x86 assembly is rusty but I don't see a mulq there. I suspect the optimization you're looking for is already done.

[JeffBezanson]

As a footnote, Prof. Kahan advocates using an Imaginary type, but purely for reasons of numerical accuracy.

[TotalVerb]

If it is necessary for numerical accuracy, then I could support an Imaginary type. But nevertheless, we still need a zero and one value, unless we want to define 3 types for Quaternion and 7 types for Octonian.

[andyferris]

My x86 assembly is rusty but I don't see a mulq there. I suspect the optimization you're looking for is already done.

Wow that is really long! It just has to reorder two numbers and apply minus to one of them. I've been staring at StaticArrays assembly a lot and 2-vector code is typically much, much shorter.

I think that LLVM does a lot of the optimizations for multiplying by 1, etc, not inference/codegen.

Consider the vector [1+0im, 1im, -1+0im, -1im]

Doesn't this run through promote_type and thus become Vector{Complex{Int}}? But, yes I imagine there are other just as annoying corner cases here with a very similar problem.

[andyferris]

For reference:

julia> f(z) = Complex(-z.im, z.re)
f (generic function with 1 method)

julia> @code_native f(0+0im)
        .text
Filename: REPL[2]
        pushq   %rbp
        movq    %rsp, %rbp
Source line: 1
        xorl    %eax, %eax
        subq    8(%rdx), %rax
        movq    (%rdx), %rdx
        movq    %rax, (%rcx)
        movq    %rdx, 8(%rcx)
        movq    %rcx, %rax
        popq    %rbp
        retq
        nopl    (%rax)

Really not optimal.

[TotalVerb]

This is an optimization that should be possible, so if it is not optimal, that should be fixed.

[TotalVerb]

@andyferris I've figured out the problem: the compiler won't constant-fold im. This works:

julia> macro im()
           :(Complex(false, true))
       end
@im (macro with 1 method)

julia> f(x) = x * @im
f (generic function with 1 method)

julia> @code_llvm f(0+0im)

define void @julia_f_71105(%Complex.68* noalias sret, %Complex.68*) #0 {
top:
  %2 = getelementptr inbounds %Complex.68, %Complex.68* %1, i64 0, i32 1
  %3 = getelementptr inbounds %Complex.68, %Complex.68* %1, i64 0, i32 0
  %4 = load i64, i64* %2, align 8
  %5 = sub i64 0, %4
  %6 = load i64, i64* %3, align 8
  %.sroa.0.0..sroa_idx = getelementptr inbounds %Complex.68, %Complex.68* %0, i64 0, i32 0
  store i64 %5, i64* %.sroa.0.0..sroa_idx, align 8
  %.sroa.2.0..sroa_idx1 = getelementptr inbounds %Complex.68, %Complex.68* %0, i64 0, i32 1
  store i64 %6, i64* %.sroa.2.0..sroa_idx1, align 8
  ret void
}

julia> @code_native f(0+0im)
    .text
Filename: REPL[16]
    pushq   %rbp
    movq    %rsp, %rbp
Source line: 1
    xorl    %eax, %eax
    subq    8(%rsi), %rax
    movq    (%rsi), %rcx
    movq    %rax, (%rdi)
    movq    %rcx, 8(%rdi)
    movq    %rdi, %rax
    popq    %rbp
    retq
    nopl    (%rax)

Due to the problem being an inability to constant-fold im, I suspect Imaginary will do nothing to fix this performance issue.

[TotalVerb]

See also https://github.com/JuliaLang/julia/issues/18387.

[andyferris]

OK, thanks @TotalVerb. If that is reliable, maybe some of the problems disappear (but not necessarily all of the things Imaginary could do).

[TotalVerb]

The only thing that Imaginary can do that Complex with constant folding can't is produce a more precise result, and Prof. Kahan asserts that there are situations where that can be the case. This can justify an Imaginary type, but I don't think it is appropriate to set im = Imaginary(true) — I think those cases where numeric accuracy are important can explicitly be annotated as Imaginary(x).