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

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

Closed
griesemer opened this issue Mar 30, 2023 · 31 comments
Assignees
Labels
generics Issue is related to generics okay-after-rc1 Used by release team to mark a release-blocker issue as okay to resolve either before or after rc1 Proposal Proposal-Accepted release-blocker TypeInference Issue is related to generic type inference
Milestone

Comments

@griesemer
Copy link
Contributor

griesemer commented Mar 30, 2023

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.

@griesemer griesemer added Proposal TypeInference Issue is related to generic type inference labels Mar 30, 2023
@griesemer griesemer added this to the Go1.21 milestone Mar 30, 2023
@griesemer griesemer self-assigned this Mar 30, 2023
@griesemer griesemer modified the milestones: Go1.21, Proposal Mar 31, 2023
@griesemer griesemer added the generics Issue is related to generics label Mar 31, 2023
@zigo101
Copy link

zigo101 commented Mar 31, 2023

This is cool!

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

@griesemer
Copy link
Contributor Author

@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
Copy link

zigo101 commented Mar 31, 2023

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

@earthboundkid
Copy link
Contributor

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
Copy link

leaxoy commented Apr 3, 2023

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
Copy link
Contributor

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
Copy link
Contributor

@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
Copy link

kalexmills commented Apr 3, 2023

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
Copy link
Contributor

@kalexmills Yes, that example should work.

@mdempsky
Copy link
Member

mdempsky commented Apr 4, 2023

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
Copy link
Contributor

rogpeppe commented Apr 6, 2023

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
Copy link

kalexmills commented Apr 6, 2023

@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
Copy link
Contributor

rsc commented Apr 6, 2023

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
Copy link
Contributor

@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
Copy link
Contributor Author

@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
Copy link
Contributor

rsc commented Apr 19, 2023

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

@gopherbot
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

gopherbot pushed a commit that referenced this issue May 3, 2023
…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>
gopherbot pushed a commit that referenced this issue May 3, 2023
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
Copy link
Contributor

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

gopherbot pushed a commit that referenced this issue May 3, 2023
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
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

gopherbot pushed a commit that referenced this issue May 4, 2023
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>
gopherbot pushed a commit that referenced this issue May 4, 2023
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>
gopherbot pushed a commit that referenced this issue May 4, 2023
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>
gopherbot pushed a commit that referenced this issue May 4, 2023
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
Copy link
Contributor

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

@gopherbot
Copy link
Contributor

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

gopherbot pushed a commit that referenced this issue May 10, 2023
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>
gopherbot pushed a commit that referenced this issue May 10, 2023
…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
Copy link
Contributor

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

@mdempsky mdempsky reopened this May 11, 2023
gopherbot pushed a commit that referenced this issue May 16, 2023
… 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
Copy link
Contributor

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

gopherbot pushed a commit that referenced this issue May 31, 2023
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 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
@aclements
Copy link
Member

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

@griesemer griesemer modified the milestones: Backlog, Go1.21 Jul 25, 2023
@griesemer
Copy link
Contributor Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
generics Issue is related to generics okay-after-rc1 Used by release team to mark a release-blocker issue as okay to resolve either before or after rc1 Proposal Proposal-Accepted release-blocker TypeInference Issue is related to generic type inference
Projects
Status: Accepted
Development

No branches or pull requests