proposal: Go 2: sum types using interface type lists

[ianlancetaylor]

This is a speculative issue for discussion about an aspect of the current generics design draft. This is not part of the design draft, but is instead a further language change we could make if the design draft winds up being adopted into the language.

The design draft describes adding type lists to interface types. In the design draft, an interface type with a type list may only be used as a type constraint. This proposal is to discuss removing that restriction.

We would permit interface types with type lists to be used just as any other interface type may be used. A value of type T implements an interface type I with a type list if

1. the method set of T includes all of the methods in I (if any); and
2. either T or the underlying type of T is identical to one of the types in the type list of I.

(The latter requirement is intentionally identical to the requirement in the design draft when a type list is used in a type constraint.)

For example, consider:

type MyInt int
type MyOtherInt int
type MyFloat float64
type I1 interface {
    type MyInt, MyFloat
}
type I2 interface {
    type int, float64
}

The types MyInt and MyFloat implement I1. The type MyOtherInt does not implement I1. All three types, MyInt, MyOtherInt, and MyFloat implement I2.

The rules permit an interface type with a type list to permit either exact types (by listing non-builtin defined types) or types with a particular structure (by listing builtin defined types or type literals). There would be no way to permit the type int without also permitting all defined types whose underlying type is int. While this may not be the ideal rule for a sum type, it is the right rule for a type constraint, and it seems like a good idea to use the same rule in both cases.

Edit: This paragraph is withdrawn. We propose further that in a type switch on an interface type with a type list, it would be a compilation error if the switch does not include a default case and if there are any types in the type list that do not appear as cases in the type switch.

In all other ways an interface type with a type list would act exactly like an interface type. There would be no support for using operators with values of the interface type, even though that is permitted when using such a type as a type constraint. This is because in generic code we know that two values of some type parameter are the same type, and may therefore be used with a binary operator such as +. With two values of some interface type, all we know is that both types appear in the type list, but they need not be the same type, and so + may not be well defined. (One could imagine a further extension in which + is permitted but panics if the values are not the same type, but there is no obvious reason why that would be useful in practice.)

In particular, the zero value of an interface type with a type list would be nil, just as for any interface type. So this is a form of sum type in which there is always another possible option, namely nil. Sum types in most languages do not work this way, and this may be a reason to not add this functionality to Go.

As I said above, this is a speculative issue, opened here because it is an obvious extension of the generics design draft. In discussion here, please focus on the benefits and costs of this specific proposal. Discussion of sum types in general, or different proposals for sum types, should remain on #19412. Thanks.

[Merovius]

I'm having trouble understanding what you are trying to say.

What we're calling "underlying" in this thread, really just refers to a type's kind.

Not really. kind doesn't distinguish between different structs, but underlying does. Also, "underlying type" is an established concept from the go spec, kind isn't.

If we introduce underlying-matching; we introduce a type hierarchy.

Perhaps. Though I think it is useful to be more specific than just say "we introduce a type hierarchy". In particular, Go already has actual subtyping (the spec calls it "assignability", mainly affected by interface satisfaction), so having type hierarchies in general isn't necessarily a bad thing.

In this particular case, the matching only applies to generic type parameters. So while there are some contexts in which you can use a YourInt as a MyInt, you can't in general - so we don't have actual subtyping or an actual type-hierarchy. It could be argued that that's more confusing - but IMO "generic type parameters" are an easy enough to understand and distinguish context that it isn't much of a problem in general.

Types in Go1 are invariant. […] the rest of the language is strictly invariant.

I'm not sure what you mean here. "Invariance" is a property of type-constructors, not of types. And as far as I can tell, nothing really changes in this regard - Go won't get variant type constructors with the generic design, underlying type matching or not. You won't be able to use a func(X) as a func(Y), unless X and Y are the same type - that won't change.

You might intend to say that Go has no subtyping, but see above - it already does and has been since the Go1.0.

Do we even allow structs? Say we didn't.
Do we allow funcs? Say we didn't.
Do we allow maps/slices? Say we didn't.

Why would we say any of that? I don't see anything in the design or this proposal that would suggest structs, funcs or maps/slices aren't allowed, under exactly the same rules.

Does *MyInt match *int? (covariance)

This is an interesting question. A priori, I would assume "no" - the underlying type of *MyInt is *MyInt and that's not identical to *int. So you couldn't use a *MyInt to satisfy an interface{ type *int } constraint.

introducing underlying-matching fundamentally challenges Go1's design and opens a wholly new problem space much larger than what has been considered in this thread so far.

Perhaps. But I think it's also important to acknowledge that without it, type-parameters lists lose much of their utility - namely, allowing to write generic functions using operators. If you don't mach on the underlying type of a type-argument, you couldn't use a generic Max function with your MyInt, for example. (And the implications of using underlying type matching or abandoning it have been discussed in this thread already, I think :) )

[atdiar]

Yes, I think the confusion stems from the understanding of what underlying means. I think it's suposed to be used in case of a sumtype defined using the built-in types. So when the underlying is a built-in type.

Because if we take the initial post from Ian, if I define
type I3 interface{ MyInt2, MyFloat2 }
Even if the underlying implements I1, I don't think that I1 == I3

[edit] unless as @thwd was mentioning a type hierarchy which indeeed exist, we have

type OurInt that would be accepted in type interface{MyInt, Myfloat} since MyInt is an underlying of OurInt
Yet, type MyInt would not accepted in type interface{Outint, MyFloat} because it is not an underlying.

Also, yes, pointer dereference operator is not an issue. Think of it as a function from int to a Typed value and remember that there is no overloading in Go. No covariance/ contravariance either. No automatic conversion. All this is subtly linked.

Then, it just works because MyInt and int are different: they define disjoint sets of values.
That's also why we can't add MyInt and OurInt by using "+" especially in a sumtype relationship. Otherwise, that would be a misuse of overloading when really, the operands are not the same.

Add(MyInt, int) can be transformed to Add(MyInt, MyInt) but Add(MyInt, OurInt) can not be specified. (or another name for this function/method/operator should be used, i.e. can't use the "+" symbol because no operator overloading and it would be left at the discretion of the user to define what that even means think adding celsius + meters)

For type switches, again, it's important that the types in a sumtype/union type be disjoint in terms of conxeptual method set (still taking a type as a conceptual go interface which, if not built-in, has a unique-name returning method) .
So while passing an int to type interface{MyInt, MyFloat} is ok, it's not for type Interface{MyInt, MyInt2} . Because by implementation int can be either one of them. So the underlying should be boxed into one of the types. We may find this issue again when type switching.

[bcmills]

@atdiar

Yes, I think the confusion stems from the understanding of what underlying means.

The definition that applies here is the one in the language spec (https://golang.org/ref/spec#Types):

Each type T has an underlying type: If T is one of the predeclared boolean, numeric, or string types, or a type literal, the corresponding underlying type is T itself. Otherwise, T's underlying type is the underlying type of the type to which T refers in its type declaration.

[bcmills]

For type switches, again, it's important that the types in a sumtype/union type be disjoint in terms of conxeptual method set (still taking a type as a conceptual go interface which, if not built-in, has a unique-name returning method).

I don't agree that that is important. This proposal describes types that function more as unions than as algebraic data types, and that's ok: the concrete types themselves function as algebraic constructors, so the sum types don't need to also provide that functionality.

[atdiar]

Yes, thank you. Indeed I had also gone back to the spec and figured out underlying is defined there. The proposal does define a subtyping relationship then as @thwd was alluding to in terms of type hierarchy. I do no think it's necessarily problematic after thinking about it.

As for your second point, the issue that could possibly occur for me is when the types in a union are interfaces. How to type switch on that if a concrete type implements several interfaces.
Also, if two different types implement the same interfaces that would have been in a union, are we sure these interfaces can really interop? (especially if they are not in a subtyping relationship)

[beoran]

One solution for the type switch problem for the union proposed in this issue wiuld be to require the type switch to consist of all members of the union, each nominally, nothing more and nothing less. If any member is not exported then the type switch is only allowed in the defining package. This idea is simple and Go-like, I think.

[millergarym]

@ianlancetaylor @griesemer
Based on Go's orthogonality principle and personal research / experience of simple algebraic type system, I strongly feel a discriminated union type would be superior to type lists (or at minimum the list part).

To fully replace type lists and not just the list part would require changes to interfaces types to match fields as well as methods (unfortunately this change to the language seems to have already been ruled out #23796).

Below is an example of rewriting the initial example using a type union, only replacing the list is types lists, followed by an example of replacing type lists with union type where interfaces can match fields.

Both these examples achieve the semantically of types lists, but also allow for discriminated unions to be used in other places.

Example of replacing list with union type

type MyInt int
type MyOtherInt int
type MyFloat float64
type MyNumber union {
    MyInt
    MyFloat
}
type Number union {
    int
    float64
}
type I1 interface {
    type MyNumber
}
type I2 interface {
    type Number
}

Example of replacing type lists with union type

type MyInt int
type MyOtherInt int
type MyFloat float64
type MyNumber union {
    MyInt
    MyFloat
}
type Number union {
    int
    float64
}
type I1 interface {
    MyNumber
}
type I2 interface {
    Number
}

Above the unions are using embedded branches (a branch being analogous to a field in a struct or a signature in an interface).
Unions would be syntactically similar to interfaces and structs, but with different semantics.

Discriminated unions would be similar to interfaces in their implementation.
They both can be thought of as "fat pointers" containing 1. a pointer the data and 2. a discriminator specifying which data is being pointed at.
Also similar to interfaces a type switch over the different types is possible.
They differ from interfaces as they are closed (new branches can't be added out side of their declaration) and type switches must be exhaustive else the compiler will complain.

I appreciated this comment is unlikely to get much traction as the prevailing opinion seems to be strongly against unions and fields in interfaces. I was motivated to write this as Robert explicitly called into question type lists in interfaces.
Not a conclusive reason, but discriminated unions exist in many other languages.

[bcmills]

@millergarym, alternatives involving discriminated unions have been discussed at length on #19412.

This issue is specifically focused on generalizing the type-list interfaces suggested by #43651. I don't think that the semantics required by #43651 are compatible with the union semantics you describe.

[millergarym]

@bcmills sorry, didn't read the initial message well enough.

Discussion of sum types in general, or different proposals for sum types, should remain on #19412. Thanks.

Picking up on

In discussion here, please focus on the benefits and costs of this specific proposal.

and responding to

I don't think that the semantics required by #43651 are compatible with union semantics.

In simple algebraic type systems unions are sum types.
If type lists are only kinda sum types it will be another wart on the Go type system.
As pointed out in Featherweight Go, Go has two types.
It only needed one.
Type lists, as proposed are exacerbating this design flaw by widening the gap between interfaces and structs.

I appreciate the issues are deeply embedded in the Go type system
eg

• interfaces are structurally sub-typed, struct are not
• pointer to an interface is not a pointer to the data
• type definition on data are different from a struct with a single embedded field where as type defs on interfaces are the same
• and as mentioned earlier, interface can't match fields

But isn't generic and Go2 an opportunity try tack these issues?

[ianlancetaylor]

The current generics proposal is explicitly backward compatible.

It is unlikely that Go will ever make large backward incompatible changes, as discussed at https://go.googlesource.com/proposal/+/refs/heads/master/design/28221-go2-transitions.md.

[fzipp]

I already posted this in the thread of the type parameters proposal, but I think here is the correct place.

Type lists + interfaces instead of type lists in interfaces

Current type parameters design

type FooBar interface {
	/* type list */
	/* methods */
}

Usage:

[T FooBar]

var x FooBar  // not allowed

Suggested change

type Foo /* type list (syntax tbd) */

type Bar interface {
	/* methods */
}

Usage:

[T Bar]
[T Foo]       // exact type matching for Foo
[T (Foo)]     // underlying type matching for Foo
[T Foo+Bar]   // composition, only possible inside type parameter lists; exact type matching for Foo
[T (Foo)+Bar] // composition, only possible inside type parameter lists; underlying type matching for Foo

var x Foo     // allowed; exact type matching for Foo (sum type)
var x Bar

Interfaces are left untouched.
The resulting sum type stands on its own feet, and it's not just a pale imitation of a sum type.
The (...) notation to shift the type matching rules for constraint usage is admittedly a bit odd and subtle,
e.g. [T (constraints.Ordered)] vs. [T constraints.Ordered].

[ianlancetaylor]

Retracting in favor of #45346 (which may in time lead to another proposal similar to this one, but different).

[ianlancetaylor]

I filed #57644 to update this for the final implementation of generics adopted into the language.