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

griesemer · 2023-03-30T23:35:29Z

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.

The text was updated successfully, but these errors were encountered:

go101 · 2023-03-31T03:29:12Z

This is cool!

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

griesemer · 2023-03-31T03:57:41Z

@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.

go101 · 2023-03-31T08:21:16Z

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

earthboundkid · 2023-03-31T20:08:47Z

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 · 2023-04-03T13:23:54Z

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 · 2023-04-03T22:02:58Z

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?

ianlancetaylor · 2023-04-03T22:11:40Z

@leaxoy No, that is not this proposal.

@timothy-king I would say that the benefit of allowing partial instantiations is consistency with other forms of type inference. If we omitted them some people would ask why that case does not work.

kalexmills · 2023-04-03T22:39:43Z

I would say that the benefit of allowing partial instantiations is consistency with other forms of type inference. If we omitted them some people would ask why that case does not work.

It does seem weird to me as well, at least as far as the syntax goes, but maybe I just need to get used to it.

If I'm reading it correctly then what we're really proposing is adding inference which works on all of the following assignments:

func g[P, Q any](x P) Q { ... }
var f func(int) bool
f = g            // infers P = int, Q = bool
f = g[int]       // infers Q = bool
f = g[int, bool] // infers nothing

On a related note, would this edge case also be covered by the proposal?

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

func h[P any](x P) {
  var f func(P) bool

  f = g[P]       // infers Q = bool
  f = g[P, bool] // infers nothing
}

I don't foresee any issues with admitting the above but that doesn't mean they might not be lurking in a dark corner.

ianlancetaylor · 2023-04-03T23:42:34Z

@kalexmills Yes, that example should work.

mdempsky · 2023-04-04T22:58:07Z

Overall seems reasonable.

I'm curious about some corner cases though. Is there an easy way to experiment with the prototype?

For example, given:

func f[T any](T) (_ int) { return }
func g[T any](int) (_ T) { return }
func h[T any](T, T)      {}

then currently h(f[int], g[int]) type checks. Will this proposal allow h(f, g) to be inferred?

rogpeppe · 2023-04-06T10:54:06Z

Would it be reasonable to do the same thing for generic struct literals?

For example:

type Pair[A, B any] struct {A A, B B}

var P Pair[int, string] = Pair{12, "hello"}

kalexmills · 2023-04-06T13:34:18Z

@rogpeppe fair warning; that might well need to be a separate proposal depending on the current compiler implementation. I'm sure a maintainer will be able to comment further.

In your example, why not go further? There's enough type information to infer the type of at least the second type parameter on the LHS of the =. Per the convention setup in this proposal, with enough type inference we may one day be able to write...

type Pair[A, B any] struct {A A; B B}

var P Pair[int, string] = Pair{12, "hello"}
var Q Pair[int] = Pair{12, "hello"} // ...this...
R := Pair{12, "hello"}              // ... or even this!

That last one might raise some concerns, but I don't think it's much worse than the below, which is already possible in Go.

x := 12

rsc · 2023-04-06T15:32:35Z

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

ianlancetaylor · 2023-04-06T17:52:44Z

@rogpeppe Thanks, that is a different proposal.

To me it also seems less useful. Not to say that we shouldn't do it. But the impetus for this proposal is passing generic functions to other functions, such as a generic Less function. That kind of case seems less common for a generic struct.

griesemer · 2023-04-10T22:27:38Z

@mdempsky In your example, I would think that h(f, g) should be permitted and infer the correct types.

Currently, this kind of inference for parameter passing is not yet prototyped. But it is there for ordinary assignments and returns. To play with it, you could enable it in the compiler by setting the flag EnableReverseTypeInference when setting up the respective types2.Config.

rsc · 2023-04-19T18:03:06Z

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

gopherbot · 2023-05-01T22:29:38Z

Change https://go.dev/cl/483935 mentions this issue: go/types, types2: implement reverse type inference for function arguments

gopherbot · 2023-05-02T17:29:10Z

Change https://go.dev/cl/491475 mentions this issue: cmd/compile: enable reverse type inference

…ents Allow function-typed function arguments to be generic and collect their type parameters together with the callee's type parameters (if any). Use a single inference step to infer the type arguments for all type parameters simultaneously. Requires Go 1.21 and that Config.EnableReverseTypeInference is set. Does not yet support partially instantiated generic function arguments. Not yet enabled in the compiler. Known bug: inference may produce an incorrect result is the same generic function is passed twice in the same function call. For #59338. Change-Id: Ia1faa27a28c6353f0bbfd7f81feafc21bd36652c Reviewed-on: https://go-review.googlesource.com/c/go/+/483935 Auto-Submit: Robert Griesemer <gri@google.com> Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Robert Griesemer <gri@google.com> Run-TryBot: Robert Griesemer <gri@google.com>

For #59338. Change-Id: I8141d421cdc60e47ee5794fc1ca81246bd8a8a25 Reviewed-on: https://go-review.googlesource.com/c/go/+/491475 Reviewed-by: Robert Findley <rfindley@google.com> Auto-Submit: Robert Griesemer <gri@google.com> Run-TryBot: Robert Griesemer <gri@google.com> Reviewed-by: Robert Griesemer <gri@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

gopherbot · 2023-05-03T22:00:27Z

Change https://go.dev/cl/492455 mentions this issue: cmd/compile: fix compilation of inferred type arguments

Previously, type arguments could only be inferred for generic functions in call expressions, whereas with the reverse type inference proposal they can now be inferred in assignment contexts too. As a consequence, we now need to check Info.Instances to find the inferred type for more cases now. Updates #59338. Fixes #59955. Change-Id: I9b6465395869459c2387d0424febe7337b28b90e Reviewed-on: https://go-review.googlesource.com/c/go/+/492455 Auto-Submit: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Robert Griesemer <gri@google.com> Run-TryBot: Matthew Dempsky <mdempsky@google.com>

gopherbot · 2023-05-04T01:39:47Z

Change https://go.dev/cl/492516 mentions this issue: go/types, types2: rename generic function arguments

gopherbot · 2023-05-04T01:39:48Z

Change https://go.dev/cl/492515 mentions this issue: go/types, types2: make Checker.renameTParams work on any type

gopherbot · 2023-05-04T04:41:52Z

Change https://go.dev/cl/491797 mentions this issue: go/types, types2: consider generic functions in inference simplify step

gopherbot · 2023-05-04T05:10:19Z

Change https://go.dev/cl/491798 mentions this issue: go/types, types2: remove Config.EnableReverseTypeInference flag

This permits the rewrite of type parameters in arbitrary types, not just tuples. Preparation for fixing #59956. For #59338. Change-Id: I9ccaac1f163051cb837cae2208763cafb1d239cb Reviewed-on: https://go-review.googlesource.com/c/go/+/492515 TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> Run-TryBot: Robert Griesemer <gri@google.com> Auto-Submit: Robert Griesemer <gri@google.com> Reviewed-by: Robert Griesemer <gri@google.com>

For correct inference, if the same generic function is provided more than once as an argument to another function, the argument function's type parameters must be unique for each argument so that the type parameters can be correctly inferred. Example: func f(func(int), func(string)) {} func g[P any](P) {} func _() { f(g, g) } Here the type parameter P for the first g argument resolves to int and the type parameter P for the second g argument resolves to string. Fixes #59956. For #59338. Change-Id: I10ce0ea08c2033722dd7c7c976b2a5448b2ee2d8 Reviewed-on: https://go-review.googlesource.com/c/go/+/492516 Reviewed-by: Robert Griesemer <gri@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Robert Findley <rfindley@google.com> Run-TryBot: Robert Griesemer <gri@google.com> Auto-Submit: Robert Griesemer <gri@google.com>

After type arguments for all type parameters have been determined, the type arguments are "simplified" by substituting any type parameters that might occur in them with their corresponding type arguments until all type parameters have been removed. If in this process a (formerly) generic function signature becomes non-generic, make sure to nil out its (declared) type parameters. Fixes #59953. For #59338. Change-Id: Ie16bffd7b0a8baed18e76e5532cdfaecd26e4278 Reviewed-on: https://go-review.googlesource.com/c/go/+/491797 Reviewed-by: Robert Findley <rfindley@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Robert Griesemer <gri@google.com> Run-TryBot: Robert Griesemer <gri@google.com> Auto-Submit: Robert Griesemer <gri@google.com>

Proposal #59338 has been accepted and we expect this feature to be available starting with Go 1.21. Remove the flag to explicitly enable it through the API and enable by default. For now keep an internal constant enableReverseTypeInference to guard and mark the respective code, so we can disable it for debugging purposes. For #59338. Change-Id: Ia1bf3032483ae603017a0f459417ec73837e2891 Reviewed-on: https://go-review.googlesource.com/c/go/+/491798 Run-TryBot: Robert Griesemer <gri@google.com> Reviewed-by: Robert Griesemer <gri@google.com> Reviewed-by: Robert Findley <rfindley@google.com> Auto-Submit: Robert Griesemer <gri@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

gopherbot · 2023-05-09T22:13:27Z

Change https://go.dev/cl/494115 mentions this issue: go/types, types2: explicitly look for nil type arguments in infer

gopherbot · 2023-05-09T23:25:19Z

Change https://go.dev/cl/494118 mentions this issue: go/types, types2: control type inference in Checker.funcInst via infer argument

Don't assume we have all type arguments if the number of type arguments matches the number of type parameters. Instead, look explicitly for nil type arguments in the provided targs. Preparation for type inference with type arguments provided for type parameters of generic function arguments passed to other functions. For #59338. Change-Id: I00918cd5ed06ae3277b4e41a3641063e0f53fef0 Reviewed-on: https://go-review.googlesource.com/c/go/+/494115 Reviewed-by: Robert Griesemer <gri@google.com> Run-TryBot: Robert Griesemer <gri@google.com> Reviewed-by: Robert Findley <rfindley@google.com> Auto-Submit: Robert Griesemer <gri@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>

…r argument If the infer argument is true, funcInst behaves as before. If infer is false and there are not enough type arguments, rather then inferring the missing arguments and instantiating the function, funcInst returns the found type arguments. This permits the use of funcInst (and all the checks it does) to collect the type arguments for partially instantiated generic functions used as arguments to other functions. For #59338. Change-Id: I049034dfde52bd7ff4ae72964ff1708e154e5042 Reviewed-on: https://go-review.googlesource.com/c/go/+/494118 Reviewed-by: Robert Griesemer <gri@google.com> Run-TryBot: Robert Griesemer <gri@google.com> Auto-Submit: Robert Griesemer <gri@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Robert Findley <rfindley@google.com>

gopherbot · 2023-05-10T20:09:40Z

Change https://go.dev/cl/494116 mentions this issue: go/types, types2: permit partially instantiated functions as function arguments

… arguments This CL changes Checker.genericExprList such that it collects partially instantiated generic functions together with their (partial) type argument (and corresponding) expression lists, instead of trying to infer the missing type arguments in place or to report an error. Special care is being taken to explictly record expression types where needed (because we can't use one of the usual expr evaluators which takes care of that), or to track the correct instance expression for later recording with Checker.arguments. The resulting generic expression list is passed to Checker.arguments which is changed to accept explicit partial type argument (and corresponding) expression lists. The provided type arguments are fed into type inference, matching up with their respective type parameters (which were collected already, before this CL). If type inference is successful, the instantiated functions are recorded as needed. For now, the type argument expression lists are collected and passed along but not yet used. We may use them eventually for better error reporting. Fixes #59958. For #59338. Change-Id: I26db47ef3546e64553da49d62b23cd3ef9e2b549 Reviewed-on: https://go-review.googlesource.com/c/go/+/494116 Reviewed-by: Robert Findley <rfindley@google.com> Auto-Submit: Robert Griesemer <gri@google.com> Reviewed-by: Robert Griesemer <gri@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Run-TryBot: Robert Griesemer <gri@google.com>

gopherbot · 2023-05-31T20:54:52Z

Change https://go.dev/cl/499282 mentions this issue: doc/go1.21: document type inference changes

For #39661. For #41176. For #51593. For #52397. For #57192. For #58645. For #58650. For #58671. For #59338. For #59750. For #60353. Change-Id: Ib731c9f2879beb541f44cb10e40c36a8677d3ad4 Reviewed-on: https://go-review.googlesource.com/c/go/+/499282 TryBot-Bypass: Robert Griesemer <gri@google.com> Reviewed-by: Ian Lance Taylor <iant@google.com> Reviewed-by: Robert Griesemer <gri@google.com>

aclements · 2023-07-14T15:25:03Z

Marking as a release-blocker to track the pending changes to the spec document. This does not have to block any RCs.

griesemer · 2023-07-25T18:33:05Z

This has been described in the spec a while back.
(What is currently missing in the spec is the more up-to-day description of unification, which is in progress. But unification is used for inference in general and is not specific to this issue.)
Closing.

griesemer added Proposal TypeInference Issue is related to generic type inference labels Mar 30, 2023

griesemer added this to the Go1.21 milestone Mar 30, 2023

griesemer self-assigned this Mar 30, 2023

griesemer mentioned this issue Mar 31, 2023

proposal: generic should infer type from variable definition #50285

Open

griesemer modified the milestones: Go1.21, Proposal Mar 31, 2023

griesemer added the generics Issue is related to generics label Mar 31, 2023

ianlancetaylor mentioned this issue Apr 3, 2023

proposal: spec: avoid repeating concrete type parameters when generic arguments are passed to generic functions #53138

Closed

rsc added the Proposal-FinalCommentPeriod label Apr 19, 2023

mdempsky closed this as completed May 11, 2023

mdempsky reopened this May 11, 2023

Merovius mentioned this issue May 12, 2023

cmp: new package with Ordered, Compare, Less; min, max as builtins #59488

Closed

Merovius mentioned this issue Jun 1, 2023

slices: Use ~[]E throughout #60546

Closed

aclements added release-blocker okay-after-rc1 Used by release team to mark a release-blocker issue as okay to resolve either before or after rc1 labels Jul 14, 2023

griesemer modified the milestones: Backlog, Go1.21 Jul 25, 2023

griesemer closed this as completed Jul 25, 2023

septemhill mentioned this issue Aug 11, 2023

cmd/compile: cannot use generic type without instantiation #61948

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

griesemer commented Mar 30, 2023 •

edited

go101 commented Mar 31, 2023

griesemer commented Mar 31, 2023

go101 commented Mar 31, 2023

earthboundkid commented Mar 31, 2023

leaxoy commented Apr 3, 2023 •

edited

timothy-king commented Apr 3, 2023

ianlancetaylor commented Apr 3, 2023

kalexmills commented Apr 3, 2023 •

edited

ianlancetaylor commented Apr 3, 2023

mdempsky commented Apr 4, 2023

rogpeppe commented Apr 6, 2023

kalexmills commented Apr 6, 2023 •

edited

rsc commented Apr 6, 2023

ianlancetaylor commented Apr 6, 2023

griesemer commented Apr 10, 2023

rsc commented Apr 19, 2023

gopherbot commented May 1, 2023

gopherbot commented May 2, 2023

gopherbot commented May 3, 2023

gopherbot commented May 4, 2023

gopherbot commented May 4, 2023

gopherbot commented May 4, 2023

gopherbot commented May 4, 2023

gopherbot commented May 9, 2023

gopherbot commented May 9, 2023

gopherbot commented May 10, 2023

gopherbot commented May 31, 2023

aclements commented Jul 14, 2023

griesemer commented Jul 25, 2023

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

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

Comments

griesemer commented Mar 30, 2023 • edited

Background

Proposal

Implementation

go101 commented Mar 31, 2023

griesemer commented Mar 31, 2023

go101 commented Mar 31, 2023

earthboundkid commented Mar 31, 2023

leaxoy commented Apr 3, 2023 • edited

timothy-king commented Apr 3, 2023

ianlancetaylor commented Apr 3, 2023

kalexmills commented Apr 3, 2023 • edited

ianlancetaylor commented Apr 3, 2023

mdempsky commented Apr 4, 2023

rogpeppe commented Apr 6, 2023

kalexmills commented Apr 6, 2023 • edited

rsc commented Apr 6, 2023

ianlancetaylor commented Apr 6, 2023

griesemer commented Apr 10, 2023

rsc commented Apr 19, 2023

gopherbot commented May 1, 2023

gopherbot commented May 2, 2023

gopherbot commented May 3, 2023

gopherbot commented May 4, 2023

gopherbot commented May 4, 2023

gopherbot commented May 4, 2023

gopherbot commented May 4, 2023

gopherbot commented May 9, 2023

gopherbot commented May 9, 2023

gopherbot commented May 10, 2023

gopherbot commented May 31, 2023

aclements commented Jul 14, 2023

griesemer commented Jul 25, 2023

griesemer commented Mar 30, 2023 •

edited

leaxoy commented Apr 3, 2023 •

edited

kalexmills commented Apr 3, 2023 •

edited

kalexmills commented Apr 6, 2023 •

edited