proposal: cmp: add CompareBool

[dsnet]

We just did a migration switching over usages of slices.SortFunc from func(T, T) bool to func(T, T) int and noticed that many comparisons between booleans suddenly became more complex.

Given that cmp.Compare can't be used on bools because bools are not ordered, I propose the addition of:

// CompareBool returns
//
//  -1 if x is less than y,
//   0 if x equals y,
//  +1 if x is greater than y,
//
// where false is ordered before true.
func CompareBool[T ~bool](x, y T) int {
    switch {
    case x == false && y == true:
        return -1
    case x == true && y == false:
        return +1
    default:
        return 0
    }
}

Alternatively, we could add a helper function that converts false to 0 and true to 1.

\cc @bradfitz @danderson

[Jorropo]

Alternatively, I guess that has been propsed but I can't find it. Make bool a type alias of uint1 which would be a 1 bit twos complement number. The usual number conversion rules would apply.

[robpike]

How often does sorting boolean values arise? Surprised to hear this is a pain point.

[robpike]

As for your suggestion of a conversion from bool to int, something I have used myself, it's so easy to do that I can't see it needs to be in the standard library. No one's going to get it wrong and it's less text than this reply of mine. Far less.

[jimmyfrasche]

I've sorted on bool many times, always on some property like "new" or "featured" that means it should jump to the top of a list presented to a person, but it's never been on just that property: always sort on flag then title/date/etc. I'm not sure how much help this would be in those scenarios unless there was also some kind of cmp.And(cmp.Bool(x.Flag, y.Flag), cmp.Compare(x.Title, y.Title))

I would love bool↔int conversions, though. Not hard to write but neither was min/max and those get to be builtins. I may have even written those more than I have various min/max's

[randall77]

Part of the problem with a bool->int function is that there are several. In the compiler we have two, one that converts to int64 and one that converts to int32.

[dsnet]

How often does sorting boolean values arise? Surprised to hear this is a pain point.

In our migration, ~20% of conversions required expanding the logic for boolean comparisons.

[ericchiang]

As another observation. I recently implemented a comparison for protobuf messages, and also wrote this by hand

[renthraysk]

This I think is one area where the compiler could do better*, the return early style in simple functions like this causes more branching than necessary, as it fails to realize it could be using conditional sets or moves.

The compiler can write this without branches.

func CompareBool[T ~bool](x, y T) int {
    r := 0
    if x != y {
        r = 1
        if y {
            r = -1
        }
    }
    return r
}

• Whether it's worth improving, I have no idea.

[benhoyt]

How often does sorting boolean values arise? Surprised to hear this is a pain point.

In our migration, ~20% of conversions required expanding the logic for boolean comparisons.

@dsnet Would you be able to give a couple of concrete examples of this?

[dsnet]

@benhoyt, our examples are very similar to what @jimmyfrasche mentioned. It's wanting to sort on boolean properties. Our situation is networking specific(e.g., whether DNS is set, whether an IP address is v4 or v6, whether a node is rejected, whether a key is revoked, etc.).

[robpike]

Maybe comparison operators should work on bools. They did in C. false < true.

[dsnet]

Alternatively (or perhaps additionally), we could permit bool(T) to convert numeric T types to a bool and T(bool) to convert bool types to a numeric type.

[AndrewHarrisSPU]

Alternatively (or perhaps additionally), we could permit bool(T) to convert numeric T types to a bool and T(bool) to convert bool types to a numeric type.

I think this would worry me a bit ... for T(bool), it's defining a specific mapping from the set of booleans to the set of T values. Programmatic schemes where a fairly specific {bool -> T} mapping (bitwise, enum-like, etc.) are not unusual (or, schemes with multiple useful {T -> bool} mappings). It's as if T(bool) makes an implicit conversion between one mapping to another, I think that would be a hazard.

I think bool(T) is easier to reason about, but can we just write t != zero soon?

[atdiar]

@AndrewHarrisSPU just wondering out of curiosity what would be dangerous about int(false) being 0 and int(true) being 1?

[AndrewHarrisSPU]

For example, if int(bool(int(-1))) is 1, it’s greater than int(bool(int(0))) - I’ve never missed this kind of thing in Go.

[atdiar]

@AndrewHarrisSPU isn't the issue the conversion of a number into a boolean? That's this conversion that I find a bit dubious, from a number to a boolean. From a boolean to a number however feels ok? (of course, and especially since it's not symmetric, it can just be a function instead of a type conversion)

[jimmyfrasche]

@AndrewHarrisSPU

I think this would worry me a bit ... for T(bool), it's defining a specific mapping from the set of booleans to the set of T values. Programmatic schemes where a fairly specific {bool -> T} mapping (bitwise, enum-like, etc.) are not unusual (or, schemes with multiple useful {T -> bool} mappings). It's as if T(bool) makes an implicit conversion between one mapping to another, I think that would be a hazard.

T(bool), for numeric T, mapping false to 0 and true to 1 is explicit and does not preclude defining another explicit nonstandard mapping by defining a function with a different name. It's just making the standard mapping simple. I'd be fine with defining just it and not bool(T) which is not especially useful and can easily be written as v != 0 as noted.

[merykitty]

@AndrewHarrisSPU I don't understand the argument. int64(int32(int64(1 << 32))) < int64(int32(int64(1))), you are converting a wider range of values to a narrower one and converting back, of course it is going to be lossy.

[merykitty]

Maybe comparison operators should work on bools. They did in C. false < true.

@robpike bools in C do not hold values true and false they hold values 1 and 0 so of course one is larger than the other. And for C++ I believe comparison operator is not defined for types smaller than int, and smaller types such as bool are implicitly promoted to int with which false is promoted to 0 and true is promoted to 1.

[ianlancetaylor]

Converting between boolean and numeric types has been previously considered and rejected in #9367 and #45320.

[jimmyfrasche]

I'd be happy with something like:

package math
func Bool[T number](v bool) T {
  if v {
    return 1
  }
  return 0
}

Although that would still leave the original request as something like

cmp.Compare(math.Bool(x.Flag), math.Bool(y.Flag))

[rsc]

The package docs for cmp say "Package cmp provides types and functions related to comparing ordered values." The simple fact is that bools are not ordered values in Go. I don't believe it makes sense to add "plus a special case for bools" to the package summary. If we changed the language to make bools ordered, then cmp.Compare would start supporting them. Until that point, it seems very wrong to take a package whose entire API is:

Package cmp provides types and functions related to comparing ordered values.

func Compare[T Ordered](x, y T) int
func Less[T Ordered](x, y T) bool
type Ordered interface{ ... }

and add a special-case CompareBool that does not have any relationship to the Go language definition.

As many people have already noted, it would be trivial to put CompareBool in any code that needs it, or in a third-party package. That seems much better than adding a special-case to this otherwise very well-defined package.

As Ian noted, we've also already considered allowing an explicit conversion int(b) for boolean b and any integer type. If we were going to make any change in this area, I think that would be the direction to go, and then people who want comparison of bools can convert them to ints first. But again it is trivial to write that function. #9367 and #45320 both ended up declined for lack of strong evidence. It seems unlikely the situation has changed much since then, but if you do have evidence, opening a new proposal for that seems like the right path.

[mibk]

The package docs for cmp say "Package cmp provides types and functions related to comparing ordered values." The simple fact is that bools are not ordered values in Go. I don't believe it makes sense to add "plus a special case for bools" to the package summary.

This is related to a comment I made: https://github.com/golang/go/issues/60204#issuecomment-1642020414.

[rsc]

This proposal has been added to the active column of the proposals project and will now be reviewed at the weekly proposal review meetings. — rsc for the proposal review group

[rsc]

Even if we add cmp.Or and expand the scope to "comparing values", the fact remains that bools are not ordered in Go, so ordering them in a library function seems inconsistent.

[dsnet]

For the record, I'm not tied to cmp.CompareBool. I'm open to alternatives like making bools ordered in the language, or the ability to convert bools to an ints. My goal is the ability to write something like cmp.CompareBool as a single-line expression.

[fzipp]

or the ability to convert bools to an ints

package math

// IversonBracket returns 1 if b is true; 0 otherwise.
func IversonBracket(b bool) int {
    if b {
        return 1
    }
    return 0
}

https://aplwiki.com/wiki/Ken_Iverson#Iverson_bracket

This would have a prominent advocate: "Donald Knuth has argued strongly for its wider use."

It should feel right at home next to math.Floor and math.Ceil.

[rsc]

Based on the discussion above, this proposal seems like a likely decline. — rsc for the proposal review group

[jimmyfrasche]

@fzipp I brought similar up earlier in the thread. I filed #61915

[dsnet]

Given that #45320 was closed before the introduction of slices.CompareFunc, should we re-open it for consideration now that there are more potential usages for it?

[adonovan]

Perhaps it is time to re-litigate the declined proposal #9367 to support explicit bool(int) conversions. That proposal foundered because: (a) it mentioned code generation efficiency, which is an orthogonal concern, and was since addressed separately; (b) "it is yet another very small convenience that can be replaced with a short function", but our attitude toward that concern has changed somewhat since 2014; (c) "the language is basically done and frozen", much like C++ was 20 years ago; ;-) (c) "It's not clear whether bool(0) should return false or true" because UNIX system calls and errno encode success as zero. But errnos are not bools, just as errors are not bools, so I don't find that a serious objection.

If accepted then CompareBool would be int(x) - int(y).

[dsnet]

(b) "it is https://github.com/golang/go/issues/9367#issuecomment-143128337 that can be replaced with a short function", but our attitude toward that concern has changed somewhat since 2014;

I mentioned elsewhere that a helper function cannot be used in the construction of a Go constant.

[dsnet]

I filed #62049 as a possible compiler optimization that does constant propagation for bool-to-int conversions.

[rsc]

It still seems like this one is a decline. I said above:

9367 and #45320 both ended up declined for lack of strong evidence. It seems unlikely the situation has changed much since then, but if you do have evidence, opening a new proposal for that seems like the right path.

I think that's still true.

[rsc]

No change in consensus, so declined. — rsc for the proposal review group

[cespare]

Yeah, we had exact the same experience as @dsnet. It's unfortunate that the old reflect-y sort.SliceFunc is so much easier to use when bools are involved than the new slices.SortFunc, due to the new function taking a cmp callback (vs less) and bools being annoying to compare.

[gopherbot]

Change https://go.dev/cl/550235 mentions this issue: go/analysis/passes/boolconv: analyzer to find int(bool) conversions