spec: infer type arguments from assignments of generic functions (reverse type inference)

[griesemer]

This proposal suggests a generalization of type inference where type parameters of generic function values are inferred from assignments of those values to variables. Similar ideas have been suggested in the past, e.g. see #53138 and related issues mentioned in that issue.

Background

At the moment, and even with the proposed reformulation of type inference (#58650), type inference determines the type arguments of a generic function based on (partially) provided type arguments and function arguments passed to that generic function.

We propose that missing type arguments of generic functions be inferred when such generic function values are assigned to variables of function type. That is, rather than inferring the type arguments of the function being called (and values being passed to), we infer the type arguments of the function being passed from the function being called (hence reverse type inference for lack of a better term).

For instance, the generic function g

func g[P, Q any](x P) Q { ... }

may be assigned to a variable of function type

var f func(int) bool = g

and type inference will infer that P must be int and Q must be bool. The function g may also be partially instantiated, so this assignment (after f is declared) would be allowed as well

f = g[int]

More importantly, passing a generic function as a function value to another (possibly generic) function may infer the type arguments of the function value (and possibly of the generic function being called). Given

func less[P Ordered](x, y P) bool { return x < y }
func sort[Q any](list []Q, less func(x, y Q) bool) { ... }

we can call

sort(list, less)

and the type argument Q of sort will be inferred from the list argument, and the type argument P of less will be inferred from passing less to sort.

Proposal

A generic function may not be fully instantiated when its (function) value is assigned to a variable of matching function type. In that case, type inference will infer any unknown type arguments, if possible.

For the purpose of this proposal, initialization expressions (to fully typed variables) in variable declarations, assignments to redeclared (and thus fully typed) variables in short variable declarations, returning results to function result parameters, and passing values to (user-defined) functions in function calls are considered assignments where this form of type inference will be applicable.

This is the entire proposal.
(Together with @ianlancetaylor.)

Implementation

We have a partial implementation (currently disabled in the dev branch) that implements significant aspects of this proposal (assignments and return statements, except passing arguments to generic functions) so that we can explore the ramifications. If this proposal is accepted, we hope to make the feature available for Go 1.21.

[zigo101]

This is cool!

BTW, shouldn't the type constraint in sort be also Ordered instead of any?

[griesemer]

@go101 The sort example is hypothetical, but here I meant Ordered to mean types that support <. So while the list elements supplied to sort must be ordered in some way, that way is entirely defined by the supplied less function argument (the elements could be structs that have some order defined on them, but < is not permitted on structs). If sort is called with say a []int list, than we infer P (of the supplied less function) to be int which satisfies the Ordered constraint. (And if we called sort with a []struct{...} we would get an error if we were to use the provided less function, because struct{...} does not satisfy Ordered. In that case we'd provide a different function whose constraint would not be Ordered). So in short, no, the constraint in sort does not have to be Ordered, at least not the Ordered that implies < is permitted.

[zigo101]

OK, I get it now. (BTW, it looks the type of list should be []Q instead. Otherwise, it doesn't compile).)

[earthboundkid]

OK, I get it now. (BTW, it looks the type of list should be []Q instead. Otherwise, it doesn't compile).)

Yeah:

func less[P Ordered](x, y P) bool { return x < y }
func sort[Q any, QS ~[]Q](list QS, less func(x, y Q) bool) { ... }

But []Q works too, since the QS type isn't returned.

[leaxoy]

Can this proposal infer type indirectly. For example:

type Values[V any] struct {
	inner *vector.Vector[V]
}

func (m HashMap[K, V]) Values() Values[V] {
        // vector type param V should infer to V by Values returns Values[V] lazily
        // or interred by values.Append(v)
	values := vector.New()
	for _, v := range m.inner {
		values.Append(v)
	}
	return Values{inner: values}
}

[timothy-king]

FWIW I think if I came across the partial instantiation f = g[int] in the wild, I would [potentially incorrectly] conclude g takes one type parameter.

What is the benefit of allowing partial instantiations, e.g. f = g[int]? (Compared to supporting both f = g and f = g[int, bool].) Does someone have an example where partial instantiations would help readability?