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: spec: allow type parameters in methods #49085

Open
mariomac opened this issue Oct 20, 2021 · 184 comments
Open

proposal: spec: allow type parameters in methods #49085

mariomac opened this issue Oct 20, 2021 · 184 comments
Milestone

Comments

@mariomac
Copy link

mariomac commented Oct 20, 2021

According to the Type parameters proposal, it is not allowed to define type parameters in methods.

This limitation prevents to define functional-like stream processing primitives, e.g.:

func (si *stream[IN]) Map[OUT any](f func(IN) OUT) stream[OUT]

While I agree that these functional streams might be unefficient and Go is not designed to cover this kind of use cases, I would like to emphasize that Go adoption in stream processing pipelines (e.g. Kafka) is a fact. Allowing type parameters in methods would allow constructing DSLs that would greatly simplify some existing use cases.

Other potential use cases that would benefit from type paremeters in methods:

  • DSLs for testing: Assert(actual).ToBe(expected)
  • DSLs for mocking: On(obj.Sum).WithArgs(7, 8).ThenReturn(15)
@gopherbot gopherbot added this to the Proposal milestone Oct 20, 2021
@fzipp
Copy link
Contributor

fzipp commented Oct 20, 2021

The document also explains what the problems are. So what are your solutions to these?

@go101
Copy link

go101 commented Oct 20, 2021

This proposal is good to define an io.ImmutableWriter {Write(data byteview)(int, error)} interface:
https://github.com/go101/go101/wiki/A-proposal-to-avoid-duplicating-underlying-bytes-when-using-strings-as-read-only-%5B%5Dbyte-arguments

@ianlancetaylor ianlancetaylor changed the title Proposal: Allow type parameters in methods proposal: spec: allow type parameters in methods Oct 20, 2021
@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Oct 20, 2021

This proposal is a non-starter unless someone can explain how to implement it.

@ianlancetaylor ianlancetaylor added the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Oct 20, 2021
@deanveloper
Copy link

deanveloper commented Oct 20, 2021

@ianlancetaylor from the generics proposal

Or, we could decide that parameterized methods do not, in fact, implement interfaces, but then it's much less clear why we need methods at all. If we disregard interfaces, any parameterized method can be implemented as a parameterized function.

I think this solution makes the most sense. They could then (under the hood) be treated a regular function. The reason why this would be useful is that methods do not only serve the purpose of implementing interfaces; methods also serve as a means of organization for functions that operate on particular structures.

It may be a bit of a challenge about how type-parameterized methods would appear in "reflect", though.

@go101
Copy link

go101 commented Oct 21, 2021

The problem would be simpler if the parameter type possibility set is known at compile time,

It may be a bit of a challenge about how type-parameterized methods would appear in "reflect", though.

One new problem I'm aware of is there might be many methods have the same name for a certain type.
So the Type.MethodByName might return a slice value (assume the parameter type possibility set is known at compile time).
Any other new problems?

@seankhliao seankhliao added the generics Issue is related to generics label Oct 21, 2021
@AndrewHarrisSPU
Copy link

AndrewHarrisSPU commented Oct 21, 2021

One new problem I'm aware of is there might be many methods have the same name for a certain type.

If we're ultimately talking about multiple dispatch, the languages that really cater towards this do a massive amount of overloading. One language I find fun and interesting with this style is Julia, where things like + or * or show have hundreds of overloads when booting the REPL. From a software engineering perspective, there are tradeoffs - I absolutely trust Go to compile long into the future, and to have fewer surprises about packages ... Remarkably and IMHO related to robustness, Go doesn't have programmers defining function overloads in source code - I'm not convinced generics should change this.

Particularly for stream-to-stream conversion, I do think that the List Transform example is useful. We have to provide a concrete T1 -> T2 conversion function, but in a sense we have to figure out how to convert T1 to T2 in any kind of system.

I think it's also often possible to have a higher-order function that generates conversion functions, while more specialized conversion functions are also naturally expressible in Go. Example: a very generic color conversion API might specify an interface with ToRGB() and FromRGB() methods, and this can go pretty far. We can express 8-bit to 16-bit RGB conversion here through the interfaces, the same as e.g. HSV or LAB conversions, but there's a faster bit-shifting path. With a sense of a generic default, something like bufio.Scanner seems plausible - where the default just works, but we can optionally provide a better color conversion the same way we can provide a different SplitFunc.

@DeedleFake
Copy link

DeedleFake commented Oct 21, 2021

@deanveloper

Even just that would allow for, for example, an iterator implementation, though it does require wrapping it in another type because of the lack of extension functions:

type Nexter[T any] interface {
  Next() (T, bool)
}

type NextFunc[T any] func() (T, bool)

func (n NextFunc[T]) Next() (T, bool) {
  return n()
}

type Iter[T any, N Nexter[T]] struct {
  next N
}

func New[T any, N Nexter[T]](next) Iter[T, N] {
  return Iter[T, N]{next: next}
}

func (iter Iter[T, N]) Map[R any](f func(T) R) Iter[R, NextFunc[R]] {
  return New(NextFunc[R](func() (r R, ok bool) {
    v, ok := iter.next.Next()
    if !ok {
      return r, false
    }
    return f(v), true
  })
}

// And so on.

Usage is still awkward without a short-form function literal syntax, though, unfortunately:

s := someIter.Filter(func(v int) bool { return v > 0 }).Map(func(v int) string { return strconv.FormatInt(v, 10) }).Slice()
// vs.
s := someIter.Filter(func(v) -> v > 0).Map(func(v) -> strconv.FormatInt(v, 10)).Slice()

@batara666
Copy link

batara666 commented Oct 23, 2021

This will add so much complexity

@deanveloper
Copy link

deanveloper commented Oct 23, 2021

@batara666 can you explain why? adding type parameters to methods doesn’t seem like it’d add that much complexity to me.

@Merovius
Copy link
Contributor

Merovius commented Oct 27, 2021

I think before we can think about if and how to do this, we should first address the "no higher level abstraction" restriction of generics, i.e. the inability to pass around a generic type/function without instantiation. The reason is that if we allowed additional type parameters on methods, we'd also de-facto allow to pass around generic functions without instantiation:

type F struct{}

func (F) Call[T any] (v T) { /* … */ }

func main() {
    var f F // f is now de-facto an uninstantiated func[T any](T)
}

Therefore, to allow additional type-parameters on methods, we also have to answer how to pass around uninstantiated generic functions.

Moreover, if we'd allow passing around uninstantiated generic types/functions, we could already build the abstractions given as motivations in the proposal-text.

So, given that solving "no higher level abstraction" is a strictly easier problem to solve, while providing most of the benefit of solving "no additional type parameters on methods", it seems reasonable to block the latter on solving the former.

Lastly, I'd urge everyone to consider that these limitations where not left in the generics design by accident. If they where really that easy to solve, the solution would have been in the design to begin with. It will take some time to solve them.

@ianlancetaylor ianlancetaylor removed the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Nov 3, 2021
@go101
Copy link

go101 commented Nov 12, 2021

The "type" concept almost means a memory layout.
If we could use the 1.18 constraint concept as general types,
then many problems will be solved.

A value of a subset type could be passed/assigned to a superset type.
A function with a superset type parameter could be used as a function with a subset type parameter.

For Go, the change would be too large.
It is best to experiment the idea on a new language.

@AndrewHarrisSPU
Copy link

AndrewHarrisSPU commented Nov 12, 2021

I was (far too) pleased (with myself) when I figured out this is possible: https://gotipplay.golang.org/p/1ixYAwxwVss

The part about lifting values into type system 'symbols' feels like a bit DIY and tricky, not sure there isn't something better here. I did feel like the dispatch() call is technically interesting. Inferring from the function/method supplied to dispatch() wasn't obvious to me at first. Without overloading methods, just different instantiations of the dispatch() function, it is plausible to arrive at the correct dispatch over a set of concrete implementations.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Nov 24, 2021

I'm putting this proposal on hold until we have more familiarity with the current generics implementation.

@mariomac
Copy link
Author

mariomac commented Dec 4, 2021

Playing with a new library that intensively uses generics, I provided an equivalence implementation between a Method and a Function:

https://github.com/mariomac/gostream/blob/bf84997953f02b94e28da0d6c4d38585d2677df2/stream/str_to_str.go#L5-L14

At the end, the difference is only where the parameter is placed (as a receiver, or as a first argument), but the function allows you map to a Stream of different type and with the method you can only generate streams of the same type.

With the code from the above link, I verified that this compiles:

type Mapper[IT, OT any] func(Stream[IT], func(IT)OT) Stream[OT]
var _ Mapper[int, float64] = Map[int, float64]

Simplifying, and obviating some internals from Go that I might ignore, I could see the generic Mapper type as a "single-method generic interface", that is implemented by the Map function, and it can be instantiated into a Mapper instance with concrete types.

In order to overcome the No parametrized methods issue pointed by @fzipp, from my partial view, I think that the example issue can be approached the same way as Java does: using interface{} behind the scenes and panic if the customer did a bad assignment (also the compiler could warn about the unsafe operation). Then for example the code from the example:

func CheckIdentity(v interface{}) {
	if vi, ok := v.(p2.HasIdentity); ok {
		if got := vi.Identity[int](0); got != 0 {
			panic(got)
		}
	}

Would be translated to something equivalent to:

func CheckIdentity(v interface{}) {
	if vi, ok := v.(p2.HasIdentity); ok {
		if got := vi.Identity(0).(int); got != 0 {
			panic(got)
		}
	}

Then the third line would panic if the v interface does not implement Identity[int]. The same way that Go does currently when you try to cast an identity{} reference to a wrong type.

In this case, we are translating the error check from the compile time to the runtime, but anyway this is what we actually have now if lack of parametrized methods forces us to continue using unsafe type castings.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Dec 4, 2021

In your rewrite of CheckIdentity what do we gain by using a type parameter with the method? If the code is not type checked at compile time, we can just return an interface type, which already works today.

@deanveloper
Copy link

deanveloper commented Dec 4, 2021

I think that the example issue can be approached the same way as Java does: using interface{} behind the scenes and panic if the customer did a bad assignment

This is a bad idea in my opinion - Type erasure is one of the most annoying limitations of generics in Java. I think it would go against the grain of the simplicity that Go aims for.

@mccolljr
Copy link

mccolljr commented Dec 7, 2021

I don't really have a horse in this race, but I find this proposal interesting and wanted to put down my thoughts.

Based on what I see here: https://go.godbolt.org/z/1fz9s5W8x
This:

func (x *SomeType) Blah() { /* ... */ }

And this:

func Blah(x *SomeType) { /* ... */ }

compile to nearly identical code.

If we have a type S:

type S struct {
    /* ... */
}

...and S has a method DoThing with a type parameter T:

func (s S) DoThing[T any](arg T) { /* ... */ }

...then we effectively have a generic function with the signature:

func DoThing[T any](s S, arg  T) { /* ... */ }

Of course, if we have a generic type G:

type G[T any] struct {
    /* ... */
}

...and G has a method DoStuff with a type parameter U:

func (g G[T]) DoStuff[U any](arg U) { /* ... */ }

...then we effectively have a generic function with the signature:

func DoStuff[T, U any](g G[T], arg U) { /* ... */ }

In order to use either of these "functions", all of the type parameters have to be known.

That means that in the case of S, the only way to refer to S.DoThing is to instantiate it: S.DoThing[int], S.DoThing[float64], etc.
The same is true for G, with the additional requirement that G is also instantiated: G[int].DoThing[float64], etc.

Within this limited context, it seems to me like it wouldn't be a huge leap to allow type parameters on methods - it ends up referring to what is essentially a generic function, and we know things about generic functions:

  1. They can't be used unless all type parameters are known statically at compile time, and
  2. Each unique instantiation results in a unique function, semantically speaking (the actual implementation of course may choose to use a single function and internally use type switching, etc, etc)

The mechanism by which this interacts with interface definitions/implementations is less clear to me. Though, I think it is reasonable to say that a generic interface can't be implemented directly - it must be instantiated first. I'm not as sure of this, but it seems that it might also be true that an interface can only be implemented by a fully instantiated type.

Even in code like this:

type GenericInterface[T any] interface {
    Foo() T
}

type GenericStruct[T any] struct {
    Bar T
}

func (g GenericStruct[T]) Foo() T {
    return g.Bar
}

func MakeGeneric[U any]() GenericInterface[U] {
    return GenericStruct[U]{}
}

It seems like, within the context of MakeGeneric[T], we could consider both GenericInterface[T] and GenericStruct[T] to be instantiated with the some specific type T, which is the type value given to the type parameter U in MakeGeneric[U]. The determination that GenericStruct[T] implements GenericInterface[T] in this context is different from making a general statement that "GenericStruct[T] implements GenericInterface[T] for all T", which is what I would think of as "implementation without instantiation"

One area that seems complex is interfaces whose methods have type parameters.

For example, if we had:

type Mappable[T any] interface {
    Map[U any](func(T) U) []U
}

What would it mean to "instantiate" Mappable[T]?
Can you use a type assertion such as blah.(Mappable[int]?
If Mappable[T].Map had the signature Map[U comparable](func(T) U) []U, would a type with a method
Map[U any](func(T) U) []U be treated as implementing Mappable[T]?
This kind of interface seems to introduce a lot of ambiguity that would be difficult to resolve in a satisfactory manner.

It seems much simpler to disallow that kind of interface entirely, and just require something like:

type Mappable[T, U any] interface {
    Map(func(T) U) []U
}

I think that could still be just as useful, depending on how interface implementation is handled when the underlying type has methods with generic parameters.

As an example:

// Slice[T] provides slice operations over a slice of T values
type Slice[T any] []T

// Map[U] maps a Slice[T] to a Slice[U]
func (s Slice[T]) Map[U any](func (T) U) Slice[U]

type Mappable[T, U any] {
    Map(func (T) U) Slice[U]
}

// In order for this assignment to be valid:
// 1. Slice[int] must have a method named Map ✅
// 2. Slice[int].Map must have the same number of arguments ✅
// 3. Slice[int].Map must have the same number of returns ✅
// 4. Slice[int].Map must have the same types for each argument and return ???
var _ Mappable[int, float64] = Slice[int]{1,2,3}

It seems reasonable to me to say that Slice[int] implements Mappable[int, float64], since the method Map on Slice[int] can be instantiated & called with a U set to float64.

In this case, assuming that methods with type parameters are allowed, I would think the compiler could do something like:

  1. Notice that Mappable[int, flloat64] is implemented for Slice[Int] when Slice[int].Map is insantiated with float64
  2. Generate the code for that instantiation of Slice[int].Map, and
  3. Use the pointer to that particular instantiation of Slice[int].Map in the vtable

If you're calling the method an the interface object, then you only have access to that one particular instantiation of
the Slice[int].Map method. If use a type assertion to get back the original Slice[int] type, then you can of course call any number of Map variants on it, because the compiler knows what the concrete type is again.

To summarize:

Given that it is a feature of go that interface implementation can be tested at runtime via type assertions, reflection, etc, I don't see any way around banning generic methods on interface definitions. However, because methods are more or less sugar for functions, it seems to me it would be possible to allow generic parameters on methods of concrete types, and to allow these methods to participate in implementation of fully instantiated interface types.

@Merovius
Copy link
Contributor

Merovius commented Dec 7, 2021

Given that it is a feature of go that interface implementation can be tested at runtime via type assertions, reflection, etc, I don't see any way around banning generic methods on interface definitions. However, because methods are more or less sugar for functions, it seems to me it would be possible to allow generic parameters on methods of concrete types, and to allow these methods to participate in implementation of fully instantiated interface types.

I don't think you are solving the problems from the design doc, though:

type IntFooer interface { Foo() int }
type StringFooer interface { Foo() string }
type X struct{}
func (X) Foo[T any]() T { return *new(T) }

func main() {
    var x X
    x.(StringFooer) // How does this work? Note that we can't use runtime code generation
    reflect.ValueOf(x).MethodByName("Foo").Type() // What is this type?
}

This fulfills all your criteria, it uses no parameterized interfaces and X is a concrete (non-parameterized) type. In particular, answering these questions here is the minimum required to make this feature useful.

It is very easy to look at the proposal text and think "this would be a useful feature to have, I obviously would like it in the language". But because it's such an obvious feature to put in, it would be great if people ask themselves why the Go team didn't put it in in the first place. Because there are reasons and these reasons need answering.

@alvaroloes
Copy link

alvaroloes commented Dec 7, 2021

I would like to drop an idea here which I think can be useful for the "type parameters in methods" topic. Maybe it has an obvious flaw I haven't seen or it has already been considered or discussed, but I couldn't find anything about it. Please, let me know if so.

With the current proposal, we can't have type parameters in methods but, couldn't we achieve the same effect if we put the type parameters in the type definition?

I mean, instead of doing this:

type Slice[T any] []T

func (s Slice[T]) Map[U any](func (T) U) Slice[U]

Do this (move the U type parameter from the method "Map" to the struct):

type Slice[T any, U any] []T

func (s Slice[T,U]) Map(func (T) U) Slice[U]

@Merovius Wouldn't this solve the issue you mentioned in the above comment? Your example would end up like this:

type IntFooer interface { Foo() int }
type StringFooer interface { Foo() string }
type X[T any] struct{}
func (X) Foo() T { return *new(T) }

func main() {
    var x X[int] // You are forced to specify the type parameter here with the current proposal. I guess it could be inferred it this were an initialization instead of a declaration only
    x.(StringFooer) // This would fail, as it doesn't conform to the interface
    x.(IntFooer) // This would pass
    reflect.ValueOf(x).MethodByName("Foo").Type() // "Foo(X) int"
}

I think this would work with the current proposal without changes.

As I said, I could be missing something obvious here. Let me know if that's the case.

@Merovius
Copy link
Contributor

Merovius commented Dec 7, 2021

@alvaroloes

couldn't we achieve the same effect if we put the type parameters in the type definition?

You can easily do this, but it's not the same effect. People who want this specifically want the type-parameter of the method to be independent of the type itself, to implement higher-level abstractions.

@alvaroloes
Copy link

alvaroloes commented Dec 7, 2021

I see, thanks. After thinking it twice, I now see that what I propose would be very limiting as, after instantiating the type, you could not call the method with different type parameters (for example, call "map" with a function that return strings one time and then another time with a function that return ints).

All right, I know there was something obvious here. Thanks for the response!

@mccolljr
Copy link

mccolljr commented Dec 7, 2021

I don't think you are solving the problems from the design doc, though:

I'm sure that's true, I probably would benefit from reviewing it again. To be fair, though, I wasn't trying to put together a concrete proposal - I understand why this is a complex topic and why it isn't in the first pass at generics, and why it may never be added to the language. I don't have a horse in this race beyond the fact that I find this interesting. My intent was to think out loud about what restrictions might make this more concretely approachable. Also, for what it's worth, I think that disallowing parameterized methods on interface types could be seen to addresses some of the problems put forth in the proposal.

type IntFooer interface { Foo() int }
type StringFooer interface { Foo() string }
type X struct{}
func (X) Foo[T any]() T { return *new(T) }

func main() {
    var x X
    x.(StringFooer) // How does this work? Note that we can't use runtime code generation
    reflect.ValueOf(x).MethodByName("Foo").Type() // What is this type?
}

[...] answering these questions here is the minimum required to make this feature useful.

I do not disagree. I feel as if you may have misinterpreted my intent. I am not saying "this is so easy, look at how we can do it" - I am saying "here is an interesting constraint that might make this more approachable, and which could perhaps be used as the basis for additional discussion"

I'm willing to brainstorm this, but again I am not proposing a concrete solution as much as attempting to provide a possible set of constraints for discussion. If that exercise shows that thia feature would too complex, that is a totally acceptable outcome in my opinion.

Obviously we cannot use runtime code generation, I don't recall proposing that nor do I think it is necessitated by anything said above. Given that, here are some possible (not exhaustive or comprehensive) directions the compiler could choose:

For x.(StringFooer)

  • The program could encode the types that a generic method/function/etc has been instantiated with. This would allow x.(StringFooer) to correctly select the implementation of Foo that applies. Of course, if X.Foo is never explicitly instantiated with string, then it could be surprising to a user that this fails. Perhaps the cost of that potential confusion is unacceptable. This failure could of course be solved by adding var _ StringFooer = X{} somewhere in the code, and perhaps the panic message could indicate that the failure was due to uninstantiated generic methods rather than uninstantiated

  • The compiler could generate a fallback implementation using interface{} or some minimum interface that it can use in these situations. In the case of type sets, the fallback could use a type switch. Perhaps if type switching on ~ types is implemented this becomes easier.

For reflect

  • Similar to above, the compiler could generate metadata about which instantiation were generated and this could be introspectable from reflect. A public IsGeneric flag could be added to the descriptor for methods and calls to method values could validate the given types against the instantiation list to verify the proper code had been generated.

  • Similar to above, the compiler could simply generate fallback implementations for generic methods (functions etc).

It is very easy to look at the proposal text and think "this would be a useful feature to have, I obviously would like it in the language". But because it's such an obvious feature to put in, it would be great if people ask themselves why the Go team didn't put it in in the first place. Because there are reasons and these reasons need answering.

This is exactly what I attempted to do here. I wrote this at 1am on the last legs of a cup of coffee, and it seems I failed to consider some scenarios in my comment. A simple "How would this address X and Y" would have accomplished the same effect without this lecture at the end.

@Merovius
Copy link
Contributor

Merovius commented Dec 7, 2021

To be clear, this is what the proposal says about this question:

We could instantiate it at link time, but in the general case that requires the linker to traverse the complete call graph of the program to determine the set of types that might be passed to CheckIdentity. And even that traversal is not sufficient in the general case when type reflection gets involved, as reflection might look up methods based on strings input by the user. So in general instantiating parameterized methods in the linker might require instantiating every parameterized method for every possible type argument, which seems untenable.

Or, we could instantiate it at run time. In general this means using some sort of JIT, or compiling the code to use some sort of reflection based approach. Either approach would be very complex to implement, and would be surprisingly slow at run time.

Or, we could decide that parameterized methods do not, in fact, implement interfaces, but then it's much less clear why we need methods at all. If we disregard interfaces, any parameterized method can be implemented as a parameterized function.

So while parameterized methods seem clearly useful at first glance, we would have to decide what they mean and how to implement that.

The solution you suggest seem a variation on the second option here.

@veqryn
Copy link

veqryn commented Oct 18, 2022

As far as I can see explicit interfaces bound the problem but they do not solve it. The key to the example is that p3 needs to know about p1, but it only knows about p2. Explicit interfaces would mean that anything that imports p4 would be given additional information about p1, but p3 doesn't import p4.

@ianlancetaylor
Going with my example above (which may have been missed with the recently flurry of comments: #49085 (comment) ), the complier would be able to know that p1's S type is explicitly implementing p2's HasIdentity interface. Then, whenever a package like p4 imports p1, as well as any other package like p3 that uses p2's interface, wouldn't the compiler then be able to go instantiate p1.S.Identity[int]?

Even if packages were imported out of order, the compiler could be keeping a running list of interfaces that use generics, as well as a running list of types that both use generics in their method signatures and explicitly implement any interfaces. Then whenever a new type like that is encountered/imported the compiler could go instantiate whatever more concrete types it needs based on if that interface is already used anywhere from the running list of interfaces. And likewise as new usages of "interfaces that use generics" are found, it could look at the running list of types with explicit interfaces to see if it needs to instantiate any of them.

@Merovius
Copy link
Contributor

Merovius commented Oct 18, 2022

@veqryn I'm not sure I completely understand your intent. As a clarification:

  • In your example, nothing mentions S.Indentity[int]. So in first order, the compiler still doesn't know that method is called, right?
  • You then intend to address that by instead looking at any usage of the HasIdentity interface and any instantiation of its Identity method, correct?
  • So, in effect, you are suggesting that whenever anything instantiates a generic method (of an interface in the scope of this example), any implementation of that interface gets a method with that argument instantiated, correct?

It might be wasteful, if there are many implementations of an interface but only few (or even none) of them actually ever get used with a given type parameter. But I think it would make this example work - as long as we ignore dynamic linking, which I'm not sure we want to.

I think we'd also still leave out reflect method calls, which don't have to mention an interface at all. That may be alright, though it would make me sad to have more impossible stuff in reflect than we already do.

@willfaught
Copy link
Contributor

willfaught commented Oct 18, 2022

Note that in Go it's not enough to just say "everything becomes any" because that doesn't give you a way to implement [...] because you can't use < with values of type any. The dictionary implementation approach is what is required to actually make that work

@ianlancetaylor With type erasure, type variables are replaced with their corresponding constraint type (the GJ paper quotation above called them bounding types), which may or may not be any.

I sketched out how type erasure would work for operations above:

Making built-in types normal types with methods that correspond to operators would have obviated the need for non-basic interface constraints, making type erasure a simple mapping from generic code to code with interfaces and type assertions.

In other words, this:

func Min[T Integer[T]](a, b T) T { if a < b { return a } return b }

var x, y int8 = 1, 2
var z int8 = Min(x, y) + 3

type Integer[T any] interface {
    LessThan(T) bool
    // ...
}

func (x int) LessThan(y int) bool
func (x int8) LessThan(y int8) bool
// ...

would be syntactic sugar for this:

func Min[T Integer[T]](a, b T) T { if a.LessThan(b) { return a } return b } // LessThan method instead of < operator

// ...

which would compile to this:

func Min(a, b Integer) Integer { if a.LessThan(b) { return a } return b } // generics gone

var x, y int8 = 1, 2
var z int8 = Min(x, y).(int8) + 3 // type assertion

type Integer interface { // generics gone
    LessThan(any) bool
    // ...
}

func (x int) LessThan(y int) bool
func (x int8) LessThan(y int8) bool

// bridge methods, search that GJ paper for "bridge"
func (x int) LessThan(y any) bool
func (x int8) LessThan(y any) bool
// ...

Note that the bridge methods above are just to show the idea of how Java does it. Go doesn't permit method overloading, obviously, so another strategy would have to be used for Go.

The link above is a detailed investigation of that approach with the reasons why it is quite difficult to implement for the gc compiler.

Thanks. I'll check it out.

A case where, as far as I can tell, Java-style type erasure doesn't work at all for Go is [...] Here it doesn't make sense to convert s to type any because any doesn't support indexing as in s[i].

E would be replaced with its constraint, any, so s would have type []any after erasure. Type erasure would still work in your example. (Note that the constraint would need to be comparable in your example.)

This:

func Index[E Comparable[E]](s []E, v E) int { for i := range s { if s[i] == v { return i } } return -1 }

type Comparable[T any] interface {
    Equals(T) bool
}

would be syntactic sugar for this:

func Index[E Comparable[E]](s []E, v E) int { for i := range s { if s[i].Equals(v) { return i } } return -1 }

// ...

which would compile to this:

func Index(s []Comparable, v Comparable) int { for i := range s { if s[i].Equals(v) { return i } } return -1 }

type Comparable interface {
    Equals(any) bool
}

@Merovius
Copy link
Contributor

Merovius commented Oct 18, 2022

E would be replaced with its constraint, any, so s would have type []any after erasure.

This isn't possible in Go, as slices are not covariant. You would have to do something like

type ErasedSlice interface {
    Get(int) any
    Set(int, any)
    Slice(int, int, int) ErasedSlice
    Append(...any) ErasedSlice
    Range() iter.Iter[any]
    …
}

That's, I believe, what Ian means by "Once we start waving our hands to make that work I think we pretty much wind up where the Go proposal already landed".

@willfaught
Copy link
Contributor

willfaught commented Oct 18, 2022

This is the same as saying "we do not allow the language to be implemented by some compilers". Our goal is to make it possible for the full language to be implemented by TinyGo (and others). It doesn't, currently, implement the entire language, but we want it to remain at least possible.

It would still be possible to implement, it just wouldn't perform well in that env. This is already an issue with interfaces, or really any other feature that entails boxing.

Otherwise, on a compiler which only implements a subset of the language, you couldn't use libraries which uses things it doesn't implement. You'd have to be recursively aware of whether or not the code you've written is compatible with the compiler you use. That's not something we like.

The same consideration could be made for language features that entail boxing. The point is that users can try out those features and then test whether the perf cost is feasible for their requirements. It could be the same for type abstraction values.

@Merovius
Copy link
Contributor

Merovius commented Oct 18, 2022

With interfaces, the overhead is at least syntactically clear. x.M() is a method call, it is clear that there is overhead. x[i] = v is not. And the overhead compounds.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Oct 19, 2022

@willfaught As @Merovius said, s can't have type []any. Let me add that we require that Index[struct { a, b string }] be callable as a function from some other function that doesn't know that Index is a generic function. That is, an instantiation needs to have exactly the same ABI as an ordinary function of the same type. So if you are going to represent s as a []any you need to have a conversion pass that creates a new slice and copies each element in, and then (because slices include a reference to the underlying array) you need to copy each element out again when the function returns or panics. For a long slice that is a considerable, and to the reader completely unexpected, overhead to add to each function call.

@willfaught
Copy link
Contributor

willfaught commented Oct 19, 2022

This isn't possible in Go, as slices are not covariant.

So if you are going to represent s as a []any you need to have a conversion pass that creates a new slice and copies each element in

I see what you both meant. Yes, there would have to be conversion between types in that case. I think also for converting an instantiated generic type to its equivalent underlying type, or vice versa. This is what we have to do by hand now, where I have a []int, but a func I want to call takes a []interface{}, or vice versa. That's definitely a cost. The erasure strategy is just basically doing automatically what we do by hand now.

With interfaces, the overhead is at least syntactically clear. x.M() is a method call, it is clear that there is overhead. x[i] = v is not. And the overhead compounds.

Good point. There's a little more context involved in spotting when type conversion would need to happen.

@Merovius
Copy link
Contributor

Merovius commented Oct 19, 2022

The erasure strategy is just basically doing automatically what we do by hand now.

I think the crux is that, if we can avoid it, we are not doing it by hand. If we try to pass an []int as an []any, we tend to see that this is problematic, that we'd have to write a loop and we try to use alternative strategies. The explicitness of the cost prompts us to avoid it. If the cost is there, but hidden, we no longer get that flashing warning sign.

@veqryn
Copy link

veqryn commented Oct 20, 2022

@Merovius

  • In your example, nothing mentions S.Indentity[int]. So in first order, the compiler still doesn't know that method is called, right?
  • You then intend to address that by instead looking at any usage of the HasIdentity interface and any instantiation of its Identity method, correct?
  • So, in effect, you are suggesting that whenever anything instantiates a generic method (of an interface in the scope of this example), any implementation of that interface gets a method with that argument instantiated, correct?

Yes, but only for explicit interfaces.
So S.Indentity[int] would only get instantiated if S explicity implements HasIdentity like so: type S implements p2.HasIdentity struct{}
IF S doesn't explicitly have implements p2.HasIdentity written on it, then it won't be allowed by the compiler to implement the interface at all (ie: not implicitly) because p2.HasIdentity is an interface with generics in it. So basically the same as right now.

It might be wasteful, if there are many implementations of an interface but only few (or even none) of them actually ever get used with a given type parameter. But I think it would make this example work - as long as we ignore dynamic linking, which I'm not sure we want to.

I think the requirement to explicitly implement an interface, and the interface having generics in it too, would cut down on how much it occurs. Not sure what you mean by dynamic linking in this context.

I think we'd also still leave out reflect method calls, which don't have to mention an interface at all. That may be alright, though it would make me sad to have more impossible stuff in reflect than we already do.

I don't know how reflect really works with generics right now, so I can't answer this one. It isn't allowed right now with or without reflect, so I guess reflect wouldn't be negatively impacted at least.

@Merovius
Copy link
Contributor

Merovius commented Oct 20, 2022

Not sure what you mean by dynamic linking in this context.

gc supports a couple of dynamically linked build modes, like -buildmode=shared and -buildmode=plugin (see go help buildmode and also plugin). A package built in one of these modes can be built separately from the executable and then gets loaded either on startup or later. In the example, if p3 is build as a plugin and the other packages as an executable, the [int] instantiation is not known to the compiler when building the executable.

@veqryn
Copy link

veqryn commented Oct 20, 2022

Not sure what you mean by dynamic linking in this context.

gc supports a couple of dynamically linked build modes, like -buildmode=shared and -buildmode=plugin (see go help buildmode and also plugin). A package built in one of these modes can be built separately from the executable and then gets loaded either on startup or later. In the example, if p3 is build as a plugin and the other packages as an executable, the [int] instantiation is not known to the compiler when building the executable.

Ah. In that case, I'm not so sure. I guess something would have to be done at link time or run time. Not sure how possible or easy that is to do.

@asv7c2
Copy link

asv7c2 commented Oct 23, 2022

Maybe just forbid checking and type casting to interface which have type parameters in methods?

@firelizzard18
Copy link
Contributor

firelizzard18 commented Oct 25, 2022

The generics proposal says (https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#No-parameterized-methods):

In Go, one of the main roles of methods is to permit types to implement interfaces. It is not clear whether it is reasonably possible to permit parameterized methods to implement interfaces.

and

Or, we could decide that parameterized methods do not, in fact, implement interfaces, but then it's much less clear why we need methods at all. If we disregard interfaces, any parameterized method can be implemented as a parameterized function.

So, sure, we could say that generic methods don't automatically implement interfaces. But then why do we need them?

@ianlancetaylor Expressiveness and encapsulation. A lot of the same reasons OOP was invented in the first place. Generic methods with the above restriction would be very useful to me for many of the same reasons I use methods today - I want those functions to be scoped to the receiver type. Permitting types to implement interfaces is a role of methods but it is certainly not the only role of methods. "One of the main roles of methods is to permit types to implement interfaces therefore there's no reason to add restricted generic methods" is a faulty argument. The Go team may decide that the complexity outweighs the benefits, but the implicit argument seems to be "methods that can't satisfy interfaces have no purpose" and that is objectively false. IMO if the Go team is unwilling to consider restricted generic methods you need to make a statement such as, "We will not consider restricted generic methods because the benefits do not clearly outweigh the cost of the added complexity." CC @Merovius

@Merovius
Copy link
Contributor

Merovius commented Oct 25, 2022

@firelizzard18 AIUI the only difference between your suggested phrasing

"We will not consider restricted generic methods because the benefits do not clearly outweigh the cost of the added complexity."

and the position taken so far on this topic by the Go team (and me) is that you want to close the door on this feature (you say "we will not consider", whereas our position is "at this moment it seems"). I don't understand the benefit of doing that, to anyone involved.

To re-emphasize the analogy, for 10 years Go did not have generics and the stance was "we would like to add them, but we haven't figured out how we want to implement them in a way that the benefits outweigh the costs yet. But we are still thinking about it". We had this same discussion for that decade, with some people asking to close the door on generics once and for all - "at least we'd know" - and some people asking to just do something, anything, to get generics now. The Go team did neither and continued to think on it, until they came up with a satisfying way to do it. And now we have generics.

This is no different. I don't understand why it is impossible to just be patient. To accept that the currently known options are indeed not considered satisfying, but that this also doesn't mean we'll never find an option. To me, it seems like a good thing for your opposition in a debate to say "we are open to the possibility that there are options and arguments we have not considered yet".

@firelizzard18
Copy link
Contributor

firelizzard18 commented Oct 25, 2022

@Merovius My frustration is not a matter of impatience, and I do not want a the Go team to say, "We're never doing this." My frustration is that a number of people have (at least implicitly) answered "then why do we need them" and as far as I've seen no one on the Go team has actually responded to those answers. The only response I've seen is quoting or paraphrasing the original proposal, which essentially says, "If you can't use them for interfaces what's the point?" "What's the point?" is not a valid response to "The point is X."

The original proposal asked "What's the point?" and we have answered. I am frustrated that the discussion appears to be stuck at "But then why do we need them?" when we've already answered that. I have answered it directly and specifically: I want generic methods (even with restrictions) for all the same reasons I use methods that don't correspond to any interface. IMO the discussion about restricted generic methods should move from "Why?" to considering the answers we've provided and whether they're sufficient justification for the change. So far it feels like those answers have been completely ignored by the Go team. It is the Go team's prerogative to say, "At this time we find the proposed justifications insufficiently compelling," but at least that's a direct response to our answers to "Why?" I'd prefer a discussion of the merits, and ideally consideration of a toolchain experiment to evaluate the utility of restricted generic methods, but at the very least I'd like a direct response instead of what feels like evasion or being ignored.

and the position taken so far on this topic by the Go team (and me) is that you want to close the door on this feature (you say "we will not consider", whereas our position is "at this moment it seems").

I did not carefully think through the phrasing of "we will not consider" and I'd prefer something that leaves the door open such as "at this moment it seems". What I want is some direct response to "{This} is why I think it's worth it."

@Merovius
Copy link
Contributor

Merovius commented Oct 25, 2022

@firelizzard18 I'm not on the Go team, so I obviously can't fulfill your wish. But just to add to your list: @ianlancetaylor has also said

You are proposing large and significant language changes, which make generic methods behave significantly different from non-generic methods. The benefit of these changes appears to be to permit call chaining. I don't think the benefit outweighs the cost.

I think there have been more, this is just one that came to mind. Overall, it has been my experience that @ianlancetaylor in particular has been very good at responding to arguments patiently and in good faith (and impressive volume).

It is true that not every person who individually brings up the same argument again, or a minor variation of a known argument gets an individualized response - but in my experience, that's also not really reasonable to demand, as Go programmers outnumber the Go team by several orders of magnitude and they have usually not followed the discussion for the entire time and know what has or has not been said already.

I also think it can be reasonably assumed that the Go team is aware that methods occupy a separate namespace, for example. So if they haven't done anything, it stands to reason that they feel even with that benefit mixed in, the benefits don't outweigh the cost. Which is to say, I feel like it's reasonable to extrapolate a bit from what they have said and the fact that they have not yet made a proposal to address this issue.

Lastly, I would hesitate to interpret the question "why do we need them" to be a literal question. I would, personally, interpret it as the statement that "the benefits we know does not outweigh the cost" - and, again, in regards to which of those benefits the Go team is aware of, I feel comfortable to extrapolate.

I don't want to just dismiss your concerns. But personally, while I'm not on the Go team, I have followed a lot of these discussions for a while. It just does not jibe with my own experience that the Go team is not clear on these things.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Oct 25, 2022

@firelizzard18 In general I agree with what @Merovius wrote.

I'm sorry for being a bit flip in asking why we need methods that don't implement interfaces. Yes, there are advantages to methods aside from implementing interfaces. But as much as possible Go aims for concepts to be orthogonal. Generic methods and standard methods would look very similar, and as people get used to writing generic functions it seems very natural for them to want to write generic methods (as we can see in this issue). I think it will be surprising for people to have two concepts that look so similar, and seem so natural, to behave differently in an important way. That's not orthogonal.

So as @Merovius suggests, let me rephrase. Do the benefits we get from generic methods outweigh the conceptual language complexity of adding a new kind of method that behaves differently than ordinary methods in an important way? To me, it seems that the cost is too high.

@mccolljr
Copy link

mccolljr commented Oct 26, 2022

I am making the assumption that the desire for concepts to be orthogonal stems from a desire for the language to be intuitive to use and learn.

I am only one person and I can only speak for myself, but:

I personally find the concept of dynamic dispatch to generic methods unintuitive. What I find appealing about go's approach to generics is the simplicity of the concepts, and the fact that they begin and end in the source code - running code has no knowledge of generic types beyond the instantiations that exist at compile time, so runtime reflection capabilities work exactly the same regardless of how you defined the type of a value.

The intuitive concept for me would be to have a similar set of restrictions for generic methods. If they are purely a compile-time concept, then there is no need to change existing reflect-based code to handle them, and none of the knowledge I have about how go values are represented at runtime needs to change.

My point is - I think there might be an assumption here that a design where generic methods are fully orthogonal to regular methods is the one that is most intuitive for developers. It might be interesting to include some questions about this in the next go developer survey to gage exactly what the community finds intuitive/unintuitive. If the existing assumptions hold, then that's fine, but perhaps there's something interesting to be learned by asking

@firelizzard18
Copy link
Contributor

firelizzard18 commented Oct 26, 2022

@ianlancetaylor Thank you for your response.

The exact nature of the problem depends greatly on what the mechanics of generic methods would be if they were implemented. I'd like to explore the possible mechanics so we're all on the same page with regards to the nature of the problem. Prior to 1.18:

func (myFooer) Foo()

type Fooer interface {
    Foo()
}

var fooer Fooer = myFooer{} // myFooer.Foo satisfies Fooer.Foo

With 1.18+ I can define the following:

func (myFooer) Foo[T]()

Personally, I would find it surprising if myFooer.Foo[T] satisfied Fooer.Foo because in my mind Foo[T]() is a different signature from Foo().

func (myIter) Next[T]() (T, bool)

type FooIter interface {
    Next() (Foo, bool)
}

I would still find it surprising if myIter.Next[Foo] satisfied FooIter.Next. As I see it, this is basically the same as covariance (or maybe it's contravariance?):

type Fooer interface {
    Foo()
}

type FooIter interface {
    Next() (Fooer, bool)
}

func (myFooer) Foo()
func (myFooIter) Next() (myFooer, bool)

// Invalid (compilation error) because `myFooIter.Next` does not satisfy `FooIter.Next`
// because Go does not support covariance
var fi FooIter = myFooIter{}

Essentially, I consider the type parameters to be part of the method signature, therefore a method with type parameters cannot satisfy an interface method without type parameters. If you agree, then unless I'm missing something the only way a generic method could possibly satisfy an interface is if the interface defines a generic method:

func (myFoo) Foo[T]()

type Fooer interface {
    Foo[T]()
}

Do you agree? If you do, I argue that it is logical to consider generic methods on concrete types separately from generic methods on interfaces. If we allow generic methods on concrete types but prohibit generic methods on interfaces, then the restriction that a generic method cannot implement an interface follows naturally.

@firelizzard18
Copy link
Contributor

firelizzard18 commented Oct 26, 2022

In case it wasn't clear, I want generic methods for far more than call chaining (I did see this comment). IMO using methods over functions leads to better, cleaner, and more readable code, independent of call chaining.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Oct 26, 2022

First, if we permit generic methods, I do think that this should compile:

type T[E any] ...
func (T) Read([]E) (int, error) { ... }
var r io.Reader = T[byte]

Second, if we permit types to have generic methods, it doesn't make sense to me to prohibit interface types from having generic methods. They are the same kind of thing. Sure, we could add that prohibition. But I think we would need a very very good reason to do so.

@firelizzard18
Copy link
Contributor

firelizzard18 commented Oct 26, 2022

I think the method in your snippet is missing [E] or [E any] - the method needs to be func (T[E]) Read([]E) (int, error), or func (T) Read[E any]([]E) (int, error) if you remove the type parameter from T. I modified your snippet for the first case and it compiles:

type T[E any] struct{}
func (T[E]) Read([]E) (int, error) { return 0, nil }
var r io.Reader = T[byte]{}

If you meant the second, do you expect the following to compile?

type T struct{}
func (T) Read[E any]([]E) (int, error) { return 0, nil }
var r io.Reader = T{}

In other words, do you expect the compiler to infer that it should create some kind of shim for T that passes [byte] to the method?

@mccolljr
Copy link

mccolljr commented Oct 26, 2022

If you meant the second, do you expect the following to compile?

type T struct{}
func (T) Read[E any]([]E) (int, error) { return 0, nil }
var r io.Reader = T{}

In other words, do you expect the compiler to infer that it should create some kind of shim for T that passes [byte] to the method?

One implication of this would be that this code should also compile:

type T struct{}
// I read the next F and next G value from the given slice, my signature has nothing to do with io.Reade4
func (T) Read[E, F, G any]([]E) (f F,  g G) { return f, g }
var r io.Reader = T{}

Or, maybe more nefariously, so should this:

type T struct{}
// I panic if `E` isn't a struct, or something weird like that
func (T) Error[E any]() E { /* ... */ }
var e error = T{}

Maybe this is ok,but I personally would find these scenarios undesirable. Obviously sufficiently descriptive method names would avoid this problem, but I think the potential for the footgun is still there.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Oct 26, 2022

@firelizzard18 Sorry, you're right, I got confused. I was trying to think of something more like the case that you wrote down. It seems to me that there should be some way to make that case work, but it does seem like a stretch for the language to simply infer the type of the method.

@firelizzard18
Copy link
Contributor

firelizzard18 commented Oct 29, 2022

Given a generic method with the type parameter [T C] where C is some constraint; if C is a pure interface (only methods), define C' to be an alias of C; otherwise, define C' to be an interface that contains all the methods of C.

What operations prevent the compiler from rewriting T to C' and compiling the method as non-generic? In other words, what operations cannot be expressed as runtime functions or methods of some pure interface?

  • Numeric (arithmetic, inequalities)
  • String (concatenate, compare)
  • Indexing (maps, slices)

Am I forgetting anything?

@Merovius
Copy link
Contributor

Merovius commented Oct 29, 2022

@firelizzard18 I'm not sure what you are asking. Every operation can be expressed as a runtime function, from what I can tell, given enough information about the type - that's how reflect can exist.

To your list, I would probably add at least copying, calls, selector-expressions, range, comparison, map-insertion/hashing, logical operators, conversions, assignments to interfaces, dereferencing… At least these are all "operations" you could do on a type parameter (not all of them are valid right now because of implementations restrictions, but it would be good if they where). I'm probably forgetting more. Basically "anything you can do with a value" is an operation to consider. Especially given that type-parameters can appear in "higher-order" positions (i.e. you can write func(T), if T is a type-parameter).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests