What’s stopping Julia from using Boolean values as Singleton types?

To keep type stability for functions with conditional arguments, folks often write branches like…

if arg == Val{true}
    return A
else
    return B
end

What would be the downside of making a special case for boolean values, since there are only two of them?

The keyword true would be of type True<:Boolean. Likewise for false.

This would remove the need for wrapping conditional arguments in Val{…} for type stability.

I’m sure there’s a good reason I’m missing for why boolean values were not designed this way. I just had this thought and was curious.

3 Likes

It would make logic operations (&& and ||) type unstable.

6 Likes

Is that true? Since the output type is easily determined from the input type, I think it wouldn’t be. I.e. if Bools are encoded in the type domain then those functions are type-domain → type domain so I don’t think that’s really where the issue is; it’s the value domain → type domain functions like == which would be type unstable.

Are you suggesting that booleans always should be singletons, or to introduce aliases for Val{true} and Val{false}?

Keep in mind that dynamic dispatch is generally much slower than a simple branch.

2 Likes

Yes, I am not sure if && and || would be type-unstable but they would probably incur in dynamic dispatch frequently.

1 Like

This would make working with an array of Bools more complicated as the array would be abstractly typed.

For cases where you want to be able to dispatch on whether something is true or false so it compiles away, it’s better to bake properties into the types under consideration if you can.

3 Likes

It’s less about && and || and more about the fact that it would make every single function that returns a boolean type-unstable.

Operations as basic as a < b or a == b, which are as low-level and performance-critical as it gets, would become type unstable.

11 Likes

Yeah, for this to be an option we’d need both proper dependent typing as well as a proper big SAT solver in the compiler. This would probably explode compile times.

I’d also point out that most of the benefits this would give are already achieved by aggressive constant propagation, which Julia already does. Quite a bit more aggressively than other languages too, since we already have a call site when we set out to compile something.

14 Likes

There are definitely cases where using Val{true} for keyword arguments to a function results in better performance and TTFX, (mainly because it forces specialization?). In the case I am linking below, turning a keyword from true to Val{true} was the way to remove spurious allocations, but that might be because of some related allocation bugs in Julia: https://github.com/Krastanov/QuantumClifford.jl/commit/e8f94e95cc7b8d7a093a16f8022823daf5b8cb61#diff-855d2c6204b74fc940c414de72963f46190780b39a98c07035600c291b97c40cL746

Before this single change, the code was slow due to allocations, but the allocations were not reported in --track-allocations, rather only seen in @benchmark. After that change, everything is fine and there are no ghost allocations. Probably related to https://github.com/JuliaLang/julia/issues/35800

It might result in better performance, but it would almost certainly not result in better TTFX. Those are almost always at odds with each other. Specialization is mostly the enemy of TTFX unless the code is so slow without specialization that compiling a specialized version and running it gets results faster than running an unspecialized version. Interpretation versus compilation is just the extreme case of this where specialization is on the actual code being run (see Futamura projections)

3 Likes

In Static.jl there are True and False types that work with a generic ifelse method. The benefits of using this are:

  1. Many traits follow the pattern Trait(x) which returns IsTrait or IsNotTrait. Using is_trait(x) -> True/False is immediately intuitive so that users don’t have to learn a new set of traits types to use your is_trait method.
  2. It acts like a boolean type in more cases. For example, let’s say is_trait(x) returns True() when a certain quality is known at compile time but returns true when it is known dynamically (similarly with False() and false). A chain of is_trait(x) | is_trait(y) | ... can return a compile time known value. I’ve only had a handful of situations where this is useful, but the amount of code to support all the Bool methods (~100 lines) is too much for this to be something worth implementing independently every time you need it.

As one of the authors of Static.jl, do I think it would it be nice if if True() ... else ... end worked? Yes, because then you could use the above example to do if is_trait(x) ... else ... end. Would this help improve speed? Probably not, because of constant propagation (as previously stated). Clearly we would need changes internal to base for this syntax to work, and we can’t trust that users will always define their is_trait in a type stable way. So we’d need something like istrue(x::Bool) = x, istrue(::True) = true, istrue(::False) = false at branch points to ensure we know what we’re working with. I imagine that even this simple addition could have non trivial consequences on compile times without careful implementation.

I have no idea how to do something internal like that, so If I made a PR to Base porting that code I’d really be asking a developer who knows the compiler to finish the other half of my PR. I occasionally lurk on some of the compiler development, and there’s a lot going on that has a measurable effect on compile time and run time performance.

So to answer the original question, I’d conjecture that the reason we don’t have a singleton type ever act as a boolean value in Base Julia is because the implementation is non-trivial and the only benefit of it being in Base instead of a package is a very specific syntactic nicety.

4 Likes

Compile times aside, having truthy/falsy (as this would need) in a language is a big pet peeve of mine. It IMO leads to confusing code, like e.g. if [] in python is false because the list is empty, while if [1] is true. Using a variable, both look the same (if list), but since there’s no clue about what type that variable is, it’s impossible to find out what will happen without knowing both type & “truthiness” implementation for that type (if desired to be user extendable). Worse yet, if you assumed this would always be a list and not switch to a None somewhere along the way, you may have a else branch expecting a list that will then only throw there, instead of at the if already…

I personally prefer the much clearer if isempty(list) (and similar explicit queries for other types), which greatly increases readability & maintainability of that piece of code.

6 Likes

I should have clarified that in my example I wouldn’t suggest istrue be generic or manually used at the if-else call sight. I’d expect it to be a built-in that can’t have any other definitions and be processed in the background. These sort of optionally static values can be tricky and for the time being it’s usually easier for isempty(list) always be Bool so it doesn’t break code that dispatches on Bool. But I don’t see any reason why Julia 2.0 couldn’t have the static version.

1 Like

Thanks everyone!

1 Like

I thought so too but was surprised to see that constant prop is not that agressive when the function is non trivial : https://github.com/JuliaLang/julia/issues/44330

1 Like