Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: cmp: add CompareBool #61643

Closed
dsnet opened this issue Jul 28, 2023 · 38 comments
Closed

proposal: cmp: add CompareBool #61643

dsnet opened this issue Jul 28, 2023 · 38 comments
Labels
Milestone

Comments

@dsnet
Copy link
Member

dsnet commented Jul 28, 2023

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

@dsnet dsnet added the Proposal label Jul 28, 2023
@gopherbot gopherbot added this to the Proposal milestone Jul 28, 2023
@Jorropo
Copy link
Member

Jorropo commented Jul 28, 2023

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
Copy link
Contributor

robpike commented Jul 28, 2023

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

@robpike
Copy link
Contributor

robpike commented Jul 28, 2023

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
Copy link
Member

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
Copy link
Contributor

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
Copy link
Member Author

dsnet commented Jul 28, 2023

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
Copy link
Contributor

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

@renthraysk
Copy link

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
Copy link
Contributor

benhoyt commented Jul 30, 2023

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
Copy link
Member Author

dsnet commented Jul 30, 2023

@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
Copy link
Contributor

robpike commented Jul 30, 2023

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

@dsnet
Copy link
Member Author

dsnet commented Jul 30, 2023

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
Copy link

AndrewHarrisSPU commented Jul 30, 2023

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
Copy link

atdiar commented Jul 31, 2023

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

@AndrewHarrisSPU
Copy link

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
Copy link

atdiar commented Jul 31, 2023

@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
Copy link
Member

@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
Copy link

@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
Copy link

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
Copy link
Contributor

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

@jimmyfrasche
Copy link
Member

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
Copy link
Contributor

rsc commented Aug 1, 2023

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
Copy link
Contributor

mibk commented Aug 1, 2023

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: #60204 (comment).

@rsc
Copy link
Contributor

rsc commented Aug 2, 2023

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
Copy link
Contributor

rsc commented Aug 9, 2023

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
Copy link
Member Author

dsnet commented Aug 9, 2023

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
Copy link
Contributor

fzipp commented Aug 9, 2023

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
Copy link
Contributor

rsc commented Aug 9, 2023

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

@jimmyfrasche
Copy link
Member

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

@dsnet
Copy link
Member Author

dsnet commented Aug 14, 2023

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
Copy link
Member

adonovan commented Aug 14, 2023

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
Copy link
Member Author

dsnet commented Aug 14, 2023

(b) "it is #9367 (comment) 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
Copy link
Member Author

dsnet commented Aug 15, 2023

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

@rsc
Copy link
Contributor

rsc commented Aug 16, 2023

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
Copy link
Contributor

rsc commented Aug 16, 2023

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

@cespare
Copy link
Contributor

cespare commented Aug 17, 2023

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
Copy link
Contributor

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
Status: Declined
Development

No branches or pull requests