Generics: type-list vs method-based constraints -- not orthogonal?

[ben...@gmail.com]

Hi folks,

This thread on lobste.rs made me wonder if the difference between type-list constraints and method-interface constraints is going to cause a bunch of issues or code duplication. There's a lack of orthogonality here that makes me uneasy.

For example, the Smallest() function in this proposal takes a slice of []T, where T is "type T constraints.Ordered", a type-list based constraint. That means Smallest() will only work with the built-in types specified in the type list (or types with one of those as an underlying type), and can't be used with more complex struct types.

For it to work for other types, you'd have to write a second version of Smallest() -- code duplication -- that took a method-interface based constraint like so:

type CustomOrdered(type T) interface {

Less(other T) bool

}

Arguably Smallest() would still be quite useful even if it only works for builtin integer and float point types, but with the type-list Ordered it wouldn't work for (say) big.Int, a custom Decimal type, or a more complex struct type.

But I think this is worse for ordering-based *data structures* like Tree of T. If done with the type-list Ordered, the tree could only store built-in types, which isn't that useful. Using a constraint like CustomOrdered would work and be more flexible ... but then a basic Tree(int) wouldn't work. You'd have to do Tree(MyInt) and convert everything from int to MyInt on the way in, and MyInt back to int on the way out -- a bunch of type conversion boilerplate.

Or you'd end up writing two versions of your generic Tree: BuiltinTree that uses Ordered (type lists), and CustomTree that uses CustomOrdered (interface with Less). Not very nice.

(Here's some Go2Go code which shows this for Smallest: https://go2goplay.golang.org/p/Rbs374BqPWw)

I'm not sure how the proposal solves this for something like Smallest() ... I don't think it does. For ordered data structures, like the Map example, it passes in a custom "compare" function to the initializer and kind of side-steps the issue. Which isn't bad for data structures as it'd still eliminate a lot of code, but it would be kind of a pain for little algorithms like Smallest().

Thoughts?

-Ben

[Ian Lance Taylor]

What you say is true. I don't know of a way around the basic problem
other than introducing methods on basic types. That would be a big
change to the language, and would require introducing a large number
of new names.

The way I would suggest handling your Tree example is by making the
basic data structure take a comparison function. Then you can write
tiny wrappers that create the function for any ordered type, or for
any type with a Less method. Or people can just pass their own
comparison function. You suggest that the Map example sidesteps the
issue by using a comparison function, which is true, but the Map data
structure is also more flexible with a comparison function. For
example, it lets you store the same type in multiple types with
different sorting.

The Smallest example is a case where we don't need to store the value,
so you can take an approach like the sort example in the design draft
(https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#sort).

I'm not going to claim that these are perfect solutions, but they seem
workable to me. It would be interesting to hear of real cases where
they are problematic.

Ian

[Ben Hoyt]

Thanks. You're right about the Map with the comparison function being
more flexible. That helps allay my concerns for ordered data
structures.

I guess what I'm worried about is for someone writing a "slices"
library and wants to include a function like slices.Smallest(). Do
they give it an Ordered type-list constraint or an constraint with a
Less method? How will they know which of the following to do?

1) Only include Smallest() and hope nobody who uses big.Int comes along.
2) Include two versions, Smallest(type T Ordered)(s []T) for int and
float64 etc, and SmallestCmp(type T)(s []T, func (x, y T) int) so
people can use SmallestCmp(bigs, big.Int.Cmp)?
3) Something else, like Smallest() plus a SmallestCustom() that uses
CustomOrdered

Can you flesh out what you're thinking of w.r.t Smallest() and taking
"an approach like the sort example"?

-Ben

[Steven Blenkinsop]

Passing in two type parameters, one which is the type used by the caller and one which implements the interface, would almost work if conversions were allowed between type parameters with the same underlying types:

https://go2goplay.golang.org/p/ylchcyACuV7

You have to double parameterize everywhere explicitly, though. I'm not quite clear what the advantage would be compared to passing in the comparator, other than the tradeoffs for static vs. dynamic.

Another option for abstracting over builtin and custom type cases would be to add namespaced extension methods. Basically, a package could add methods to a builtin type which are namespaced by the package, and then interfaces could qualify their method names with the particular package whose methods they want to use. Downstream packages would be able to satisfy these methods only for the types they define, like with normal "free" methods. This change would potentially have a far reaching impact, but it would sidestep needing to add a lot of names to the language.

type CustomOrdered(type T) interface {

package.Less(other T) bool

}

func (x int) package.Less(y int) bool {

return x < y

}

It would be nice if you could do this for all types that implement constraints.Ordered in one definition, but that's a whole other can of worms.

One way to address this would be if you could

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/7f471eba-be08-4d32-a50a-22939f63b76dn%40googlegroups.com.

[Ian Lance Taylor]

On Thu, Jul 2, 2020 at 9:02 PM Ben Hoyt <ben...@gmail.com> wrote:
>
> Thanks. You're right about the Map with the comparison function being
> more flexible. That helps allay my concerns for ordered data
> structures.
>
> I guess what I'm worried about is for someone writing a "slices"
> library and wants to include a function like slices.Smallest(). Do
> they give it an Ordered type-list constraint or an constraint with a
> Less method? How will they know which of the following to do?
>
> 1) Only include Smallest() and hope nobody who uses big.Int comes along.
> 2) Include two versions, Smallest(type T Ordered)(s []T) for int and
> float64 etc, and SmallestCmp(type T)(s []T, func (x, y T) int) so
> people can use SmallestCmp(bigs, big.Int.Cmp)?
> 3) Something else, like Smallest() plus a SmallestCustom() that uses
> CustomOrdered
>
> Can you flesh out what you're thinking of w.r.t Smallest() and taking
> "an approach like the sort example"?

I was thinking of a comparison function, with a wrapper that uses a
little comparison function that calls Less. It's more work on the
package writer side, but it seems pretty straightforward on the part
of the caller of the function.

I think we are always going to face this dichotomy unless we introduce
a large set of standard methods for builtin types, or add some way for
people to define operator methods for their own types. Both seem like
big changes to the language, and while they would be convenient for
certain uses of generics it's not clear to me that they are essential.
That is, I think generics can be useful even without those features,
and I don't think generics precludes adding those features later if
they seem useful.

Ian

[Ian Lance Taylor]

On Thu, Jul 2, 2020 at 9:48 PM Steven Blenkinsop <stev...@gmail.com> wrote:
>
> Another option for abstracting over builtin and custom type cases would be to add namespaced extension methods. Basically, a package could add methods to a builtin type which are namespaced by the package, and then interfaces could qualify their method names with the particular package whose methods they want to use. Downstream packages would be able to satisfy these methods only for the types they define, like with normal "free" methods. This change would potentially have a far reaching impact, but it would sidestep needing to add a lot of names to the language.
>
> type CustomOrdered(type T) interface {
> package.Less(other T) bool
> }
>
> func (x int) package.Less(y int) bool {
> return x < y
> }
>
> It would be nice if you could do this for all types that implement constraints.Ordered in one definition, but that's a whole other can of worms.

The trick with this kind of approach is understanding what should
happen if the type with a package-specified method is converted to an
empty interface type, handed to some other package, and then in some
way handed back to the original package. Does the package-specified
method survive these conversions? Why or why not? Also, how does
type reflection work: can it discover such methods? Can it discover
them in a different package? There may be answers here but they don't
jump out as obvious.

Ian

[Steven Blenkinsop]

On Fri, Jul 3, 2020 at 3:16 PM, Ian Lance Taylor <ia...@golang.org> wrote:

The trick with this kind of approach is understanding what should
happen if the type with a package-specified method is converted to an
empty interface type, handed to some other package, and then in some
way handed back to the original package.  Does the package-specified
method survive these conversions?  Why or why not?  Also, how does
type reflection work: can it discover such methods?  Can it discover
them in a different package?  There may be answers here but they don't
jump out as obvious.

In order to be consistent, the package-qualified method should survive conversions the same way as a normal method would. Even unexported methods do this. Interface satisfaction is a property of the type, not the value. This would require that packages have the ability to register any extension methods they define in the runtime representation of an external type somehow. However, package-qualified methods would never satisfy an unqualified method constraint in an interface, regardless of any interface conversions.

Reflection would be able to discover these methods, provided the package defining them is linked into the binary. Importing a package for its side effects is already a thing, so that aspect shouldn't be too surprising. You also don't have the same visibility concerns you have with unexported methods; there's no particular issue with a package discovering an extension method defined in a different package at runtime.

One thing that I've found tricky is how to deal with embedding. If these methods can be promoted, then you have method instances which no single package owns. The package that defines a struct embedding a type and a package defining extension methods on the same type don't necessarily know about each other.

I would think that, in order to have extension methods be promoted, it would need to be done explicitly. If you could embed a type like pkg(T) which layered the extension methods defined in package pkg on top of the inherent methods of type T, then extension methods wouldn't need to be promoted in the general case. Otherwise, extension methods most likely just wouldn't be promoted.