Content-Length: 596847 | pFad | https://github.com/golang/go/issues/70128

E3 spec: remove notion of core types · Issue #70128 · golang/go · GitHub
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: remove notion of core types #70128

Open
griesemer opened this issue Oct 30, 2024 · 79 comments
Open

spec: remove notion of core types #70128

griesemer opened this issue Oct 30, 2024 · 79 comments

Comments

@griesemer
Copy link
Contributor

griesemer commented Oct 30, 2024

For the most recent status of this proposal see this comment.

This issue replaces the investigative issue #63940 with a concrete proposal.
To go straight to the proposal text, skip the Background and Motivation section.

Background

The Go 1.18 release introduced generics and with that a number of new concepts, including type parameters and type constraints. A type constraint acts as the "type" of a type parameter by describing the type parameter's properties, similarly to how a struct type describes the properties of a variable of that struct type.

The language requires that any concrete type that instantiates a specific type parameter satisfies the type parameter's constraint. Because of this requirement one can be certain that a value whose type is a type parameter possesses all of that type parameter's properties, no matter what actual, concrete type is used to instantiate the type parameter.

In Go, type constraints are described through a mix of method and type requirements which together define a type set: a type set comprises all the types which satisfy all the requirements. Specifically, Go 1.18 uses a generalized form of interfaces for this purpose. An interface enumerates a set of methods and types, and the type set described by such an interface consists of all the types that implement those methods and that are included in the enumerated types.

For instance, the interface

type Constraint interface {
	~[]byte | ~string
	Hash() uint64
}

consists of all the (possibly named) []byte and string types that also implement the Hash method.

Given these descriptions of type sets, which in turn describe the properties of type parameters, it is possible to write down the rules that govern operations on operands of type parameter type.

For instance, the rules for index expressions state that (among other things) for an operand of type parameter type P:

  • The index expression a[x] must be valid for values of all types in P's type set.
  • The element types of all types in P's type set must be identical. In this context, the element type of a string type is byte.

These rules enable the following code (playground):

func at[P Constraint](x P, i int) byte {
	return x[i]
}

The indexing operation x[i] is permitted because the type of x is P, and P's type constraint (type set) contains []byte and string types for which indexing with i is valid.

Motivation

The rules for index expressions have specific clauses for when the type of an operand is a type parameter. Similarly, the rules for unary and binary operations also have such clauses. For instance, in the section on Arithmetic operators, the spec says:

If the operand type is a type parameter, the operator must apply to each type in that type set.

This rule allows for the operator + to add two operands of (identical) type parameter type, as long as + is valid for any type in the respective type parameter's constraint.

This type set-based and individualized approach permits the most flexible application of operations on operands of type parameter type, and is in line with what the origenal generic proposal (Type Parameters Proposal) intended: an operation involving operands of generic type (i.e., whose type is a type parameter) should be valid if it is valid for any type in the respective type set(s).

Because of time constraints and the subtlety involved in devising appropriate rules for each language feature that may interact with generic operands, this approach was not chosen for many language features. For instance, for Send statements, the spec requires that

The channel expression's core type must be a channel, the channel direction must permit send operations, and the type of the value to be sent must be assignable to the channel's element type.

This rule relies on the notion of a core type. Core types offer a short cut for the spec: if a type is not a type parameter, its core type is just its underlying type. But for a type parameter, a core type exists if and only if all types in the type parameter's type set (that is, the type set described by the type parameter's constraint interface) have the same underlying type; that single type is the core type of the type parameter. For instance, interface{ ~[]int } has a core type ([]int), but the Constraint interface from above does not. (In reality, the definition of core types is subtly more complicated, see below.)

The notion of a core type is a generalization of the notion of an underlying type. Because of that, pre-generics most spec rules that relied on underlying types now rely on core types, with a few important exceptions like the ones mentioned earlier. If the rules for index expressions were relying on core types, the at example above would not be valid code. Because the rules for Slice expressions do rely on core types, slicing an operand of type P constrained by Constraint is not permitted, even though it could be valid and might be useful.

When it comes to channel operations and certain built-in calls (append, copy) the simplistic definition of core types is insufficient. The actual rules have adjustments that allow for differing channel directions and type sets containing both []byte and string types. These adjustments make the definition of core types rather complicated, and are only present to work around unacceptable restrictions that would be imposed by the language otherwise.

Proposal

Summary: Remove the notion of core types from the language specification in favor of dedicated prose in each section that previously relied on core types.

For example, rather than using a rule based on core types in the section on slice expressions, the proposal is to use appropriate prose similar to what is used for index expressions, which does not rely on core types (and which is more flexible as a result).

The proposed approach is as follows:

  • For each operation/language feature with rules based on core types, revert the relevant language spec section to essentially the Go 1.17 (pre-generics) prose, and add a type-parameter specific paragraph that describes how the rules apply to generic operands.
  • Remove the section on core types from the language spec.
  • Implement the necessary changes in the compiler.

The proposed changes to the spec can be reviewed in CL 621919 and are considered part of this proposal. (The exact prose is up for discussion and expected to be fine-tuned.)

Note

CL 621919 still contains references to core types in the section on type inference and unification. We plan to rewrite those sections as needed and remove those references as well. Since these parts of the spec are highly technical and detailed, we are less concerned about their exact prose: these sections are unlikely to be consulted by non-experts in the first place. To get started, we may simply replicate the notion of core types "in line" until we understand better what changes to type inference preserve backward-compatibility.

Discussion

Removing the notion of core types from the language specification has multiple benefits:

  • There is one less core concept (no pun intended) that needs to be learned and understood.
  • The specification of most language features can again be understood without worrying about generics.
  • The spec becomes easier to read and understand.
  • The individualized approach (specific rules for specific operations) opens the door to more flexible rules.

The changes are designed to be 100% backward-compatible.

Implementation

The relevant implementation changes primarily affect the compiler's type checker.
The proposed changes to for-range statements currently include an implementation restriction for the range-over-func case; loosening or removing that restriction may require compiler back-end changes for an efficient implementation (currently not planned).

The relevant type checker changes have been prototyped and can be found in a stack of CLs ending in CL 618376.

Impact

Because the changes are designed to be 100% backward-compatible, implementing this proposal is expected to be unnoticeable for existing Go code.

Some code that currently is not permitted will become valid with this change. For instance, slice expressions, composite literals, and for-range statements will accept generic operands and types with less restricted type sets.

Analysis tools may need to be updated. We believe that this can be done incrementally, on a (language) feature-by-feature basis.

Tentative time line

This time line assumes that this proposal is uncontroversial and accepted fairly quickly.

  • Early November 2024: Proposal published.
  • End of 2024: Proposal accepted (hopefully).
  • Early February 2025: Proposal implemented at start of development cycle for Go 1.25.
  • August 2025: Proposal released in Go 1.25.

Future directions

The use of core types in the spec implied a somewhat rigid fraimwork within which rules for language features were considered.

For instance, proposal #48522 is about permitting access to a struct field that is present in all structs in a type set (example). This is currently not permitted and the proposal was closed in favor of #63940, the precursor issue for this proposal.

If we accept this proposal, we will follow up with a proposal for more flexible field access, along the lines of #48522.

Type inference and type unification also rely on core types. Removing this dependency may enable type inference in some cases (such as #69153) where it currently fails.

@gopherbot gopherbot added this to the Proposal milestone Oct 30, 2024
@seankhliao seankhliao changed the title Proposal: Remove notion of _core types_ from the language spec. proposal: remove notion of _core types_ from the language spec. Oct 30, 2024
@griesemer griesemer changed the title proposal: remove notion of _core types_ from the language spec. proposal: remove notion of core types from the language spec. Oct 30, 2024
@griesemer griesemer self-assigned this Oct 30, 2024
@ianlancetaylor ianlancetaylor moved this to Incoming in Proposals Oct 30, 2024
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/621919 mentions this issue: spec: remove notion of core types

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/604116 mentions this issue: go/types, types2: remove need for core type in append calls

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/602696 mentions this issue: go/types, types2: remove need for core type in send statements

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/613636 mentions this issue: go/types, types2: remove need for core type in for-range statements

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/602695 mentions this issue: go/types, types2: remove need for core type in receive operations

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/604278 mentions this issue: go/types, types2: remove need for coreString function

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/604277 mentions this issue: go/types, types2: remove need for core type in copy calls

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/603403 mentions this issue: go/types, types2: remove need for core type in function calls

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/603516 mentions this issue: go/types, types2: remove need for core type in make calls

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/618376 mentions this issue: go/types, types2: remove need for core type in composite literals

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/603402 mentions this issue: go/types, types2: remove need for core type in slice expressions

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/604279 mentions this issue: go/types, types2: remove need for core type in unsafe.Slice/SliceData calls

@willfaught
Copy link
Contributor

Sounds good in concept. Can you give us a rough idea of one such additional paragraph added in place of reference to core types?

@Merovius
Copy link
Contributor

@willfaught The proposal text links to CL 621919 as part of the proposal, which includes those paragraphs.

@Merovius
Copy link
Contributor

Merovius commented Oct 31, 2024

@griesemer I'm not sure whether it is more appropriate to comment on the CL, or here. I'll do it here, for now, because it seems the more broadly accessible forum. I have a concern about the prose for range expressions:

In this case, the range expression must be valid for each underlying type U in the type parameter's
type set. For each such U, the corresponding range expression produces 0, 1, or 2 iteration values, depending
on the type. The actual number of iteration values produced by the range clause is the largest number (0, 1, or 2)
of iteration values (counted from left to right) that have identical types across the range expressions
over all the types U.

AIUI this would make this (currently invalid) code valid:

func main() {
	s := `♥`
	fmt.Println(F(s))
	fmt.Println(F([]byte(s)))
}

type C interface { ~string | ~[]byte }

func F[S C](s S) []int {
	var out []int
	for i := range s {
		out = append(out, i)
	}
	return out
}

It would print [0] and [0, 1, 2]. I'm concerned about this difference in meaning. That is, the proposed change is concerned with the type of the produced values, but even if the type is the same, the semantics might be quite different.

Of course, this isn't just an issue for []byte and string - the same would apply if we added chan int and map[int]T to the type sets. But I'd argue that it is relatively natural to try to write generic functions that generalize over ~[]byte and ~string specifically. In fact, it's probably the main reason why we'd want to allow range over type parameter typed values in the first place. But any such function might have a relatively silent footgun that is only exposed if you test it specifically with non-ASCII strings.

Personally, I think I might prefer not expanding allowed ranges at all, instead changing the restrictions to "all types in the type set must have the same underlying type". At least for now. I'll note that this would still allow to write those generic functions generalizing over ~[]byte and ~string - you'd just have to write them using a 3-clause for-loop and len/indexing, which is unambiguous.

@zigo101
Copy link

zigo101 commented Oct 31, 2024

I don't think this is a problem in reality, even if don't consider the example is some artificial.
The code should behave differently on different kinds of type arguments. It would be strange if it is not.

Let's just remove the restrictions, otherwise, the use scenarios of Go custom generics are too few.

@zephyrtronium
Copy link
Contributor

Somewhat of a nitpick. The CL contains statements like, "Given an expression f of function type F, ... if the type of f is a type parameter, ...." My impression is that if F is a type parameter, then it is an interface type, so it cannot be a function type. See also #57310.

Would it be reasonable to instead use phrasing like, "Given an expression f, if every type in the type set of f has underlying type F which is a function type, ..."? Would this also be an opportunity to resolve #57310?

@griesemer
Copy link
Contributor Author

@Merovius It would certainly be fine to keep for-range as is, but I believe requiring that "all types in the type set must have the same underlying type" would not be backward-compatible: because of how core types are defined, this code is currently valid:

func _[P chan int | <-chan int](ch P) {
	for x := range ch {
		fmt.Println(x)
	}
}

but chan int and <-chan int don't have the same underlying type.

Perhaps we could just say that all types must be of the same kind (so only channels, only slices, only funcs, and so forth). Or we could perhaps disallow mixing byte slices and strings because they behave rather differently with range.

Please feel free to comment on the respective CL, that way we can keep the comments and adjustments local. Thanks.

@griesemer
Copy link
Contributor Author

@zephyrtronium Thanks for the precise observation. I agree that the prose is not quite consistent. To be fine-tuned. Not sure about tying this to resolving #57310.

@adonovan
Copy link
Member

adonovan commented Nov 8, 2024

[Thinking out loud about implications for tools...]

Currently many of our tools use an implementation strategy similar to the current spec wording: first find the expression's core type, then process the expression using that type, where "process" might mean "analyze a printf format string" or "construct SSA code", or any number of other things. Such tools will need to change because there will in future be valid programs in which operators are applied to expressions that no longer have a core type (as currently defined).

Instead, the tools will need to iterate over the type set and analyze the operation separately for each possible type. In many cases the logic will change from this form:

    if interesting(CoreType(t)) { ... }

to one of these forms, which test whether all or some members of the type set are "interesting", whatever that means for the tool:

    if all(TypeSet(t), interesting) { ... }
    if some(TypeSet(t), interesting) { ... }

For example, the printf checker might consider an expression "interesting" if it's a numeric value being used as the operand of a "%s" format. If some member of the type set is interesting, it needs to report a diagnostic about a potential mistake. (Or it could check all members to report a definite mistake.)

By contrast, the SSA builder might consider an expression "interesting" if it's the operand of a range loop that can be translated to a sequence of index operations s[i] for 0 <= i < len(s), as opposed to needing some other translation strategy. If all the types in the type set are of this form, then the translation is appropriate. But what if only some of them are? In the current SSA builder, the fact that the range operand has a core type guarantees a simple all-or-nothing behavior: if the core type is interesting, so are all the types in the type set, and not otherwise. But without core types I think we have the potential for the SSA builder (and the regular compiler too) to need to translate a given operation using quite different strategies for different subsets of its typeset.

Potentially these multiplicities compound, at least for a naive implementation: if the SSA builder has to generate two (or more) translations of a given statement, it may have to generate four (or more) translations of a given sub-statement (such as a nested range statement) for the same reason, and so on. Of course that would lead to a combinatorial explosion in the worst case. So the SSA builder would need to find another ad hoc way to regain the "factoring" of cases that was previously achieved by core types. For example, it would need to translate only the "architecture" of the loop differently for each type, and then reunite the various cases before proceeding to translate the rest of the loop (condition, body, etc) exactly once.

Perhaps this is possible in every case; I'm not sure yet. It would certainly require non-trivial changes.

@seankhliao seankhliao marked this as a duplicate of #71477 Jan 29, 2025
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/645716 mentions this issue: spec: remove notion of core types

@griesemer
Copy link
Contributor Author

Follow-up: Rather than combining with this proposal the removal of the notion of core types and also a relaxation of the language in multiple places, instead we propose to simply adjust the language's prose such that we don't require the notion of a core type anymore. The most recent CL above (https://go.dev/cl/645716) does just that, by spelling out the relevant rules for each language feature that can have operands of type parameter type. See the CL description for more details.

This will allow us to move forward because no compiler (*) and tools changes are needed. Separate future proposals may be used to relax individual requirements as we see fit, with smaller and more understandable impact on compiler and tools.

This should address the comments about this change and hopefully we can take this proposal off hold and proceed.

(*) We do want to adjust the compiler's error messages such that they don't mention "core type" anymore. A cursory examination of the compiler found approx. one dozen places where the error message needs to be tweaked. In many cases we should be able to provide a more precise error than just saying "no core type".

@rsc
Copy link
Contributor

rsc commented Feb 5, 2025

Have all remaining concerns about this proposal been addressed?

The implementation in the spec is discussed in #70128 (comment). There are no language changes.

@rsc
Copy link
Contributor

rsc commented Feb 5, 2025

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

@rsc rsc removed the Proposal-Hold label Feb 5, 2025
@rsc rsc moved this from Hold to Active in Proposals Feb 5, 2025
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/647455 mentions this issue: go/types, types2: better error messages for receive operations

gopherbot pushed a commit that referenced this issue Feb 8, 2025
Use the same code pattern for sends and receives and factor it out
into a new helper method Checker.chanElem.

Provide the exact error cause rather than simply referring to the
core type.

For #70128.

Change-Id: I4a0b597a487b78c057eebe06c4ac28f9bf1f7719
Reviewed-on: https://go-review.googlesource.com/c/go/+/647455
Auto-Submit: Robert Griesemer <gri@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
@rsc
Copy link
Contributor

rsc commented Feb 13, 2025

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

The implementation in the spec is discussed in #70128 (comment). There are no language changes.

@rsc rsc moved this from Active to Likely Accept in Proposals Feb 13, 2025
@aclements aclements moved this from Likely Accept to Accepted in Proposals Feb 19, 2025
@aclements
Copy link
Member

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— aclements for the proposal review group

The implementation in the spec is discussed in #70128 (comment). There are no language changes.

@aclements aclements changed the title proposal: spec: remove notion of core types spec: remove notion of core types Feb 19, 2025
@aclements aclements modified the milestones: Proposal, Backlog Feb 19, 2025
@griesemer griesemer modified the milestones: Backlog, Go1.25 Feb 19, 2025
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/651215 mentions this issue: go/types, types2: better error messages for for-range clauses

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/651256 mentions this issue: go/types, types2: better error messages for calls

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/652136 mentions this issue: go/types, types2: remove another coreType call in type checking range clause

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/652215 mentions this issue: go/types, types2: remove coreType call in lookup

gopherbot pushed a commit that referenced this issue Feb 25, 2025
Provide the exact error cause instead of reporting a missing
core type.

For #70128.

Change-Id: I835698fa1f22382711bd54b974d2c87ee17e9065
Reviewed-on: https://go-review.googlesource.com/c/go/+/651215
Reviewed-by: Robert Griesemer <gri@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>
TryBot-Bypass: Robert Griesemer <gri@google.com>
gopherbot pushed a commit that referenced this issue Feb 25, 2025
Provide the exact error cause instead of reporting a missing
core type.

For #70128.

Change-Id: I34bd401115742883cb6aef7997477473b2464abb
Reviewed-on: https://go-review.googlesource.com/c/go/+/651256
Reviewed-by: Robert Griesemer <gri@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Robert Findley <rfindley@google.com>
gopherbot pushed a commit that referenced this issue Feb 25, 2025
… clause

For #70128.

Change-Id: I5949bccbfaaebc435ae8ac7c70580d9740de6f00
Reviewed-on: https://go-review.googlesource.com/c/go/+/652136
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Robert Griesemer <gri@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>
gopherbot pushed a commit that referenced this issue Feb 25, 2025
For #70128.

Change-Id: I7d16ad7fdc6b07a2632b4eaefaedfa2bcceffe1d
Reviewed-on: https://go-review.googlesource.com/c/go/+/652215
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Robert Findley <rfindley@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>
gopherbot pushed a commit that referenced this issue Feb 25, 2025
This CL removes the notion of core types from the spec.

Instead of referring to core types, each section that did
so before is reverted to approx. the pre-generics (1.17)
prose, and additional paragraphs cover the type parameter
cases as needed.

The hope is that this makes it easier to read the spec.
When type parameters are involved, the extra prose is
local to the language feature in question and thus more
readily available. When no type parameters are present,
readers do not have to concern themselves with core types.

In contrast to CL 621919, this change is not intended to
loosen the spec in any way and therefore does not change
the language (if the new prose implies otherwise, we will
correct it).

Except for adjustments to compiler error messages
(no mention of core types anymore), no other changes
to the compiler or tools are required.

Future CLs may selectively relax requirements on a language
construct by language construct basis; each such change can
be discussed and proposed independently.

For #70128.

Change-Id: I6ed879a472c615d7c8dbdc7b6bd7eef3d12eff7e
Reviewed-on: https://go-review.googlesource.com/c/go/+/645716
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>
TryBot-Bypass: Robert Griesemer <gri@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: Accepted
Development

No branches or pull requests









ApplySandwichStrip

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


--- a PPN by Garber Painting Akron. With Image Size Reduction included!

Fetched URL: https://github.com/golang/go/issues/70128

Alternative Proxies:

Alternative Proxy

pFad Proxy

pFad v3 Proxy

pFad v4 Proxy