proposal: spec: infer function type parameters from generic interface arguments if necessary

[DeedleFake]

Author background

• Would you consider yourself a novice, intermediate, or experienced Go programmer?

Experienced.

• What other languages do you have experience with?

Ruby, JavaScript, Dart, Kotlin, Java, C, Python, and several others to varying degrees.

Related proposals

• Has this idea, or one like it, been proposed before?

Probably, considering that type inference has been kept simple purposefully but with an open door to look into it again after generics are out. Generics are out, so...

• Does this affect error handling?

Not directly, no.

• Is this about generics?

Yes.

Proposal

• What is the proposed change?

Currently, the following fails to compile:

type Simpler[T any] interface {
  Simple() T
}

type Complexer[T any] interface {
  Simpler[T]
  Complex(T)
}

func DoSomething[T any](s Simpler[T]) {}

func main() {
  var c Complexer[int]
  DoSomething(c) // Fails here. Works correctly if specified manually: DoSomething[int](c)
}

This makes dealing with complex type systems where there are overlapping interfaces with optional functionality somewhat annoying.

As an example of this issue coming up in real code, I have a package for state tracking that has a basic interface type that it exports and several types that extend it. Dealing with the extension types is noticeably more awkward than just dealing with the base type because of the lack of inference. For example,

type State[T any] interface {
  Listen(func(T))
}

type MutableState[T any] interface {
  State[T]
  Set(T)
}

// Get is gets the current value of a state, but the type inference fails if
// dealing with a MutableState[T]. It works as expected when dealing
// with just a State[T] directly, however.
func Get[T any](s State[T]) T { ... }

• Who does this proposal help, and why?

Anyone dealing with generics and basic interfaces and more complicated ones that build on top of those.

Costs

• Would this change make Go easier or harder to learn, and why?

Easier, I think. Fewer rules about how and where type inference works and doesn't work is simpler and easier to deal with.

• What is the cost of this proposal? (Every language change has a cost).

Unsure. I am not an expert on type systems, but I would guess that this would complicate the implementation somewhat, possibly resulting in compiler slowdown, at least in cases where this specific form of inference is used.

• How many tools (such as vet, gopls, gofmt, goimports, etc.) would be affected?

None, I think. Just the compiler.

• What is the compile time cost?

Possible increase in specific situations, but probably not terrible. I think.

• What is the run time cost?

None.

• Can you describe a possible implementation?

No.

• Do you have a prototype? (This is not required.)

No.

[ianlancetaylor]

Thanks. Putting on hold for consideration with other forms of type inference.

[EbenezerJesuraj]

Author background

Would you consider yourself a novice, intermediate, or experienced Go programmer?

Intermediate.

What other languages do you have experience with?

C, C++, Java, Python, and several others to varying degrees.
Related proposals

Has this idea, or one like it, been proposed before?

DeedleFake:
Probably, considering that type inference has been kept simple purposefully but with an open door to look into it again after generics are out. Generics are out, so...

EbenezerJesuraj's (support/feature-upvoting reply for go-generics based on other languages having it):
spec-proposal Go/Generics similar feat/spec found in TypeScript-generics

Similar feature proposal found in TypeScript-Generics:

https://stackoverflow.com/questions/59055154/typescript-generics-infer-type-from-the-type-of-function-arguments

Does this affect error handling?

Not directly, no.

Is this about generics?

Yes.

Who does this proposal help, and why?

Anyone dealing with generics and basic interfaces and more complicated ones that build on top of those.A Project which i am currently working on.

Do you have a prototype? (This is not required.)

No.

[kluevandrew]

Any changes here?

[ianlancetaylor]

Nothing has changed.

[w0rp]

I thought I'd mention that I work around this issue in my ranges library by having an identity function that accepts the sub type and returns the base type. https://github.com/w0rp/ranges/blob/4c2ae83006ec9f79ef267e10b9794b271ae9fe4e/ranges/primitives.go#L59 Hopefully optimisations will remove calls to the function.

[apparentlymart]

I was coming here today to propose something similar to what this issue represents. I think what I was going to propose is just more detail towards the same goal, so instead of opening a new proposal I'll add some notes here.

Below I first have some notes about concretely how this inference might work, and then some comparisons with similar features in the Rust programming language just as some broader context that might help while evaluating the proposal.

EDIT: Some days after writing this I realized that #41176 seems to be covering the same problem and discussion there seems to amount to the same thing I proposed here. I'm sorry I didn't see that issue before posting this. I'm going to leave this here since I already generated whatever notification noise it's going to generate, but I think the discussion over in that other issue is already covering the key pros and cons of what I proposed here.

Proposed Design

Currently I believe that the Go compiler wants to complete type inference first and then separately check whether the values being assigned to any interface-typed arguments are actually implementations of the designated interface. I expect this model means that the current type inference mechanism is largely naive about interfaces, and broadly treats all parameterized types the same.

I think this proposal entails having the inference algorithm include a special case for when an argument is a generic type whose underlying type is an interface and where the argument type has at least one type parameter that is a type parameter of the enclosing function. As far as I can tell, this can come as a separate step before the existing specified type inference algorithm: inferring the type parameters for an interface value is a separate step which can conclude before beginning function type parameter inference.

To make this more concrete, let's consider an example:

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

func SliceFromIterator[Elem any](iter Iterator[Elem]) []Elem {
    // ...
}

type IntRangeIter struct {
    // ...
}

func (r *IntRangeIter) Next() (int, bool) {
    // ...
}

The goal of the proposal is that it be possible to call SliceFromIterator with any implementation of Iterator for any T, and have the Go compiler infer that SliceFromIterator's Elem is that same T. Specifically, the following should compile, and slice should have type []int:

iter := &IntRangeIter{ /* ... */ }
slice := SliceFromIterator(iter)

To answer that question, the compiler must first answer this question: Does the static type of the given iter value implement Iterator[T] for any concrete T?

The compiler knows that any implementation of Iterator[T] must have a method named Next, so the first test is whether the type of argument iter has a method named Next. If it doesn't then inference fails and this algorithm halts.

After proving all of the required method names are present, the next step is to try to fit the signatures of those methods to those in the interface. To do this, we can choose any arbitrary method from the interface type's method set (in this case that just Next) and confirm that the following conditions hold:

• The number of arguments and the number of return values both match between Iterator.Next and IntRangeIter.Next. In this case, IntRangeIter must have zero arguments and two return values.
• For any part of an argument or return value where Iterator.Next has a concrete type or type kind, IntRangeIter.Next must have the same type. In this case, the first return value must be a slice (though it doesn't yet matter what of) and the second return value must be exactly bool.

If any of those conditions don't hold, inference fails and this algorithm halts.

The final step is then to check whether all of the placeholders T in the signatures of Iterator[T] correspond with equal concrete types in IntRangeIter. To decide this, visit each method (in arbitrary order) and then each type parameter placeholder across the method's argument types and return value types:

• For the first encountered mention of any type parameter, find the corresponding concrete type in IntRangeIter and record that the type parameter corresponds with that concrete type. In our concrete example, visiting the first return value of Next would determine that int corresponds with T.
• For any subsequent encounters of the same type parameter, find the corresponding concrete type in IntRangeIter. If that concrete type matches the one determined previously then continue. Otherwise inference fails and this algorithm halts.

If all of the above steps succeed then we should now have a single concrete type associated with each type parameter of Iterator[T], which in this case will be T = int. The function type parameter inference algorithm should therefore treat the first argument as being Iterator[int] and then begin the type inference algorithm as currently defined in the spec, which should then conclude that this is a call to SliceFromIter[int].

Error reporting

In the above I glossed over what happens when "inference fails". I think an important part of making this understandable will be to make sure the compiler can give actionable error messages for each of the different situations where inference fails.

• If a particular method name isn't present at all:

  cannot use Whatever{} (value of type Whatever) as type Iterator[T] in assignment:
      Whatever does not implement Iterator[T] (missing Next method)
  

  This is the same as the existing message for a method name not being present at all, regardless of type inference.

• If the method name is present but the non-type-parameter portions of its don't have a matching shape:

  cannot use Whatever{} (value of type Whatever) as type Iterator[T] in assignment:
      Whatever does not implement Iterator[T] (wrong type for Next method)
          have Next() int
          want Next() (T, bool)
  

  Again this is just a reuse of an existing error message from a similar case that exists today. This one is a bit trickier because it leaves the reader to conclude that the problem here is that the number of return values isn't correct and that the difference between int and T is not important.

  I know from experience that when folks encounter an error message that's unfamiliar to them they often latch on to the first potential difference they see and so can be distracted by information that isn't actually relevant, and so a potential alternative here would be to substitute T into all of the relevant locations in the "have" and don't draw any attention to the concrete type, which is irrelevant here:

  cannot use Whatever{} (value of type Whatever) as type Iterator[T] in assignment:
      Whatever does not implement Iterator[T] (wrong type for Next method)
          have Next() T
          want Next() (T, bool)
  

  Alternatively the compiler could employ some more specific forms of this error that point more directly to the problem, such as "have one return value, but want two return values", but that sort of thing feels out of scope for what I'm discussing here. (That improvement, were it valuable here, would be just as valuable for the non-type-inference form of this error message.)

• If the signatures are all of the right shape but different parameters or return values disagree on what they substitute for T then this is the most complicated situation to explain, because the compiler has no information from which to infer the author's intent and so it seems it must just arbitrarily choose two of the potentially-many disagreements to describe.

  My simple example here only has one mention of T in the interface so I'll need to use a more elaborate interface to illustrate this one:

  cannot use Whatever{} (value of type Whatever) as type Stack[T] in assignment:
      Whatever does not consistently implement Stack[T] (inconsistent types for T)
          Push(string) expects T as string
          Pop() (int, bool) expects T as int
  

  There is a variant of this where the same method uses T twice in its signature, where the implementation might then not use the same type for both. That one seems harder to explain concisely.

Appendix: Analogy to Rust

(This section is just some additional context, not actually part of the proposal.)

Interfaces in Go are roughly analogous to "traits" in Rust.

But in Rust there are two different ways to write a trait similar to my Iterator interface from earlier:

trait Iterator<Item> {
    fn next() -> Option<Item>
}

fn vec_from_iterator<T>(it: impl Iterator<T>) -> Vec<T> {
    // ...
}

struct IntRangeIter {
    // ...
}

impl Iterator<i64> for IntRangeIter {
    fn next() -> Option<i64> {
        // ...
    }
}

fn example() {
    let iter = IntRangeIter::new();
    let vec = vec_from_iterator(iter);
    // vec is Vec<i64>
}

trait Iterator {
    type Item;

    fn next() -> Option<Item>
}

fn vec_from_iterator<Iter: Iterator>(it: Iter) -> Vec<Iter::Item> {
    // ...
}

struct IntRangeIter {
    // ...
}

impl Iterator for IntRangeIter {
    type Item = i64;

    fn next() -> Option<i64> {
        // ...
    }
}

fn example() {
    let iter = IntRangeIter::new();
    let vec = vec_from_iterator(iter);
    // vec is Vec<i64>
}

The first example above seems the closest in syntax to the Go example I gave earlier, because the trait itself has a type parameter.

In the second example the Iterator trait is not itself generic but it has an associated type Item. Any implementation of the trait must specify as part of the implementation which type it will use for Item.

This difference is meaningful in Rust because in the first case it's possible for another type to implement the trait for multiple different Item types at once:

impl Iterator<i64> for IntRangeIter {
    fn next() -> Option<i64> {
        // ...
    }
}

impl Iterator<i32> for IntRangeIter {
    fn next() -> Option<i32> {
        // ...
    }
}

In the second case IntRangeIter must choose a single item type to use for its single implementation of Iterator. It is still possible to make this generic by making the struct type itself generic:

struct IntRangeIter<T> {

}

impl<T> Iterator for IntRangeIter<T> {
    type Item = T;

    fn next() -> Option<T> {
        // ...
    }
}

...but now the type must be decided by the caller of IntRangeIter::new() (now as IntRangeIter::<i32>::new()), so deciding between these two situations can lead to quite different usage patterns for callers, and so both can be valid in different situations.

After playing with this idea a little, I've concluded that what I proposed for Go above is actually more like the associated types approach in Rust, rather than making the trait itself generic, because:

• A particular implementation of Iterator[T] can only have one Next method and must therefore select only one type T that it is implemented for.
• If a particular type needs to implement Iterator[T] for several different T then that type itself must be generic, like type IntRangeIter[T Integer] struct if we assume that Integer is a constraint which admits all of Go's integer types.

At first this concerned me but I've become comfortable with it because it feels consistent with other decisions in Go: Interface implementation is implicit in Go, but trait implementation is explicit in Rust. It seems reasonable then that an implementation of associated types (effectively what I proposed above) could include automatic inference of the associated types, whereas Rust requires explicitly assigning them.

My position is that Go's existing support for generic interfaces is already equivalent to Rust's idea of associated types, for the reasons given above, and that this is just adding the automatic inference for the associated types and for functions that use interfaces that have associated types.

Go does not currently have anything equivalent to generic traits in Rust, and that feels okay to me. Adding something equivalent to that would be a significant departure from the model of implicit interface implementation (it would require somehow allowing a type to have multiple methods of the same name) and so would be an entirely separate proposal.