Go Programming Experience

Experienced

Other Languages Experience

No response

Related Idea

  • [ ] Has this idea, or one like it, been proposed before?
  • [ ] Does this affect error handling?
  • [x] Is this about generics?
  • [x] Is this change backward compatible? Breaking the Go 1 compatibility guarantee is a large cost and requires a large benefit

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

No.

Does this affect error handling?

No.

Is this about generics?

Yes.

It removes a restriction currently present for type parameters.

Proposal

Per the spec:

Within a type parameter list of a generic type T, a type constraint may not (directly, or indirectly through the type parameter list of another generic type) refer to T.

It seems that we should be able to remove this restriction. The respective examples don't seem to cause problems for the type checker anymore, at tip, now that issue #68162 has been addressed.

Language Spec Changes

No response

Informal Change

No response

Is this change backward compatible?

Yes.

Orthogonality: How does this change interact or overlap with existing features?

This feature will simply remove a restriction. It may interact with other possible cycles (to be investigated).

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

It would make Go easier to learn because there's fewer rules.

Cost Description

Currently, the type checker doesn't enforce this restriction anymore, so the implementation cost appears to be zero at the moment but for additional tests. That said, we may uncover as of yet unknown errors due to cycles that were not possible without this change.

Changes to Go ToolChain

Should be minimal because the relevant existing tools rely on the output produced by the type checker.

Performance Costs

There's no compile time cost. The implementation removed an extremely cheap 'if' statement.

Prototype

See fix for #68162.

Comment From: griesemer

cc: @adonovan @findleyr @mrkfrmn

Comment From: gopherbot

Change https://go.dev/cl/711422 mentions this issue: spec: remove cycle restriction for type parameters

Comment From: ianlancetaylor

What about this kind of cycle?

// T is a type such that the methods of P are the methods of T, and vice-versa.
type T[P T[P]] interface { P }

Comment From: griesemer

This case is not permitted because a "term" (P inside the interface) cannot be a type parameter. Per the spec, under General interfaces:

The type T in a term of the form T or ~T cannot be a type parameter, ...

Comment From: ianlancetaylor

Hmmm, but interface { P } isn't a general interface. It's an ordinary interface with an embedded type. Isn't this covered by the "Embedded interfaces" section? That section doesn't seem to prohibit embedding a type parameter. Though perhaps it should.

Comment From: griesemer

Ordinary interfaces are just a special case of general interfaces; i.e., a general interface with a single term that is an interface "degrades" into an ordinary interfaces. So I think this case is already covered.

The cycle restriction in this issue is specific to cycles that "pass through" the type parameter list, not other cycles.

Comment From: mrkfrmn

I'm generally supportive of this idea — in terms of cycle detection rules, I (at least at a glance) don't see why a cycle via constraints is to be avoided.

How would this affect something like:

type T[P T[P]] int

type I T[int]

Is I a valid instantiation? Can T be instantiated at all?

I've been confused by this specific case in the past, but worth discussing here.

Comment From: griesemer

Instantiation always proceeds in two steps:

1) The type argument is substituted for its corresponding type parameter. So P is replaced by int in the declaration of T and we get:

type T[int T[int]] int

2) After substitution, each type argument must satisfy the constraint. So we need to check if int satisfies T[int]; i.e. we need to check if int is in the typeset of the constraint. The constraint T[int] is a shortcut for interface{T[int]}, and T[int] is a instantiated named (and notably non-interface!) type, which is different from any other type, certainly different from int. So the type set consists of T[int] and int is not in the the typeset. Hence instantiation fails.

Because instantiation fails, this code is invalid.

(Note that the code would be valid if the declaration was an alias declaration T[P T[P]] = int because T[int] is an alias for int. Sadly that code crashes the type checker at the moment. See issue #75897.)

This particular definition cannot be instantiated at all because any instantiation produces a named non-interface type T[X] for some X and X is never in the type set interface{T[X]}.

But it looks different if the definition is, i.e., where T defines an interface type.

type T[P T[P]] interface{ m() }

This can be instantiated by (for instance):

type M struct{}
func (M) m() {}

because the constraint is now the interface T[M]and so the requirement is that M has a method m which it does.

Constraints are interfaces after all, and were initially meant to constrain method sets. It's the "type set feature" that we added to interfaces - while very useful in practice - leads to perhaps unusual behavior (in the initial example), not the other way round.

Comment From: findleyr

+1, there's no need for this restriction, by construction: constraints can be checked in an entirely separate pass, since they do not affect substitution.

I'll note that types.Instantiate does this in the wrong order: it verifies first. That probably doesn't matter since it's primarily used by importers, but we should get it right.

Comment From: aclements

@griesemer , could you add some examples of what doesn't work today but would work with this change?

Comment From: aclements

This proposal has been added to the active column of the proposals project and will now be reviewed at the weekly proposal review meetings. — aclements for the proposal review group

Comment From: griesemer

A typical example is a generic type that supports operations with arguments and results of the same type as "itself". For instance, one might want to implement a generic algorithm (function algo below) that operates on values that support "+" (Add method). One might express this as follows (playground):

type Addable[A Addable[A]] interface {
    Add(A) A
}

func algo[A Addable[A]](x, y A) A {
    return x.Add(y)
}

As another (similar) example, one could model a (mathematical) ring type as follows:

type Ring[T Ring[T]] interface {
    Zero() T
    One() T
    Add(y T) T
    Mul(y T) T
}

which then allows the implementation of algorithms that operate on rings. Here's a simple example:

// scale computes x + y*s
func scale[R Ring[R]](x, y, s R) R {
    return x.Add(y.Mul(s))
}

Such an algorithm would then work with any type that implements (is) a ring, for instance integers:

type myint int

func (x myint) Zero() myint       { return 0 }
func (x myint) One() myint        { return 1 }
func (x myint) Add(y myint) myint { return x + y }
func (x myint) Mul(y myint) myint { return x * y }

(See the playground for the complete example.)

Comment From: zephyrtronium

A real-world example arose in Bryan Boreham's GopherCon 2023 talk about implementing k-way merge in Prometheus and Loki. The type he showed for the tree data structure was:

type Tree[E any, S Sequence] struct {
    maxVal E
    less   func(E, E) bool
    nodes  []node[E, S]
}

but with this capability, it could have instead been:

type Value[T Value[T]] interface {
    Less(T) bool
}

type Tree[E Value[E], S Sequence] struct {
    maxVal E
    nodes  []node[E, S]
}

I would say this is harder to follow – I already wish I could have the compiler check my work, since I haven't used this pattern before myself – but it makes the comparison calls in the merge algorithm direct and eligible for inlining. That's likely to be a significant performance win, especially when that comparison is the < operator.