proposal: spec: sum types based on general interfaces

[ianlancetaylor]

This is a speculative issue based on the way that type parameter constraints are implemented. This is a discussion of a possible future language change, not one that will be adopted in the near future. This is a version of #41716 updated for the final implementation of generics in Go.

We currently permit type parameter constraints to embed a union of types (see https://go.dev/ref/spec#Interface_types). We propose that we permit an ordinary interface type to embed a union of terms, where each term is itself a type. (This proposal does not permit the underlying type syntax ~T to be used in an ordinary interface type, though of course that syntax is still valid for a type parameter constraint.)

That's really the entire proposal.

Embedding a union in an interface affects the interface's type set. As always, a variable of interface type may store a value of any type that is in its type set, or, equivalently, a value of any type in its type set implements the interface type. Inversely, a variable of interface type may not store a value of any type that is not in its type set. Embedding a union means that the interface is something akin to a sum type that permits values of any type listed in the union.

For example:

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

The types MyInt and MyFloat implement I1. The type MyOtherInt does not implement I1. None of MyInt, MyFloat, or MyOtherInt implement I2.

In all other ways an interface type with an embedded union 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 for type parameters when using such a type as a type parameter constraint. This is because in a generic function 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 set, 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 an embedded union 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 an implementation note, we could in some cases use a different implementation for interfaces with an embedded union type. We could use a small code, typically a single byte, to indicate the type stored in the interface, with a zero indicating nil. We could store the values directly, rather than boxed. For example, I1 above could be stored as the equivalent of struct { code byte; value [8]byte } with the value field holding either an int or a float64 depending on the value of code. The advantage of this would be reducing memory allocations. It would only be possible when all the values stored do not include any pointers, or at least when all the pointers are in the same location relative to the start of the value. None of this would affect anything at the language level, though it might have some consequences for the reflect package.

As I said above, this is a speculative issue, opened here because it is an obvious extension of the generics implementation. 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 or newer variants such as #54685. Thanks.

[dsnet]

This proposal does not permit the underlying type syntax ~T to be used in an ordinary interface type, though of course that syntax is still valid for a type parameter constraint.

Could you comment on why this restriction occurs? Is this simply to err on the side of caution initially and potentially remove this restriction in the future? Or is there a technical reason not to do this?

[ianlancetaylor]

The reason to not permit ~T is that the current language would provide no mechanism for extracting the type of such a value. Given interface { ~int }, if I store a value of type myInt in that interface, then code in some other package would be unable to use a type assertion or type switch to get the value out of the interface type. The best that it could do would be something like reflect.TypeOf(v).Kind(). That seems sufficiently awkward that it requires more thought and attention, beyond the ideas in this proposal.

[dsnet]

Is there a technical reason that the language could not also evolve to support ~T in a type switch? Granted that this is outside the scope of this proposal, but I think there is a valid use case for it.

[jimmyfrasche]

In a vacuum, I'd prefer pretty much any other option, but since it's what generics use, it's what we should go with here and we should embrace it fully. Specifically,

1. type I2 int | float64 should be legal
2. v, ok := i.(int | float64) follows from 1
3. in a type switch case int | float64: works like 2
4. string | fmt.Stringer should be legal even though that does not currently work with constraints

@dsnet I think comparable and ~T could be considered and discussed separately—if for no reason other than this thread will probably get quite long on its own. I'm 👍 on both.

[DeedleFake]

With the direct storage mechanism detailed in the post as an alternative to boxing, would it be possible for the zero-value not to be nil after all? For example, if the code value is essentially an index into the list of types and the value stores the value of that type directly, then the zero value with all-zeroed memory would actually default to a zero value of the first type in the list. For example, given

type Example interface {
  int16 | string
}

the zero value in memory would look like {code: 0, value: 0}.

Also, in that format, would the value side change sizes depending on the type? For example, would a value of Example(1) look like {code: 0, value: [...]byte{0, 1}) ignoring endianess, while a value of Example("example") would look like {code: 1, value: [...]byte{/* raw bytes of a string header */}}? If so, how would this affect embedding these interface types into other types, such as a []Example? Would the slice just assume the maximum possible necessary size for the given types? Edit: Never mind, dumb question. The size changing could be a minor optimization when copying, but of course anywhere it's stored would have to assume the maximum possible size, even just local variables, unless the compiler could prove that it's only ever used with a smaller type, I guess.

It would only be possible when all the values stored do not include any pointers, or at least when all the pointers are in the same location relative to the start of the value.

I don't understand this comment, which may indicate that I'm missing something fundamental about the explanation. Why would pointers make any difference? If the above Example type had int16 | string | *int, why would it not just be {code: 2, value: /* the pointer value itself, ignoring whatever it points to */}?

[apparentlymart]

The example in the proposal is rather contrived, so I tried to imagine some real situations I've encountered where this new capability could be useful to express something that was harder to express before.

---

Is the following also an example of something that this proposal would permit?

type Success[T] struct {
    Value T
}

type Failure struct {
    Err error
}

type Result[T] interface {
    Success[T] | Failure
}

func Example() Result[string] {
    return Success[string]{"hello"}
}

(NOTE WELL: I'm not meaning to imply that the above would be a good idea, but it's the example that came most readily to mind because I just happened to write something similar -- though somewhat more verbose -- to smuggle (result, error) tuples through a single generic type parameter yesterday. Outside of that limited situation I expect it would still be better to return (string, error).)

---

Another example I thought of is encoding/json's Token type, which is currently defined as type Token any and is therefore totally unconstrained.

Although I expect it would not be appropriate to change this retroactively for compatibility reasons, presumably a hypothetical green field version of that type could be defined like this instead:

type Token interface {
    Delim | bool | float64 | Number | string
    // (json.Token also allows nil, but since that isn't a type I assume
    // it wouldn't be named here and instead it would just be
    // a nil value of type Token.)
}

Given that the exact set of types here is finite, would we consider it to be a breaking change to add new types to this interface later? If not, that could presumably allow the following to compile by the compiler noticing that the case labels are exhaustive:

// TokenString is a rather useless function that's just here to illustrate an
// exhaustive type switch...
func TokenString(t Token) string {
    switch t := t.(type) {
        case Delim:
            return string(t)
        case bool:
            return strconv.FormatBool(t)
        case float64:
            return strconv.FormatFloat(t, 'g', -1, 64)
        case Number:
            return string(t)
        case string:
            return string
    }
}

I don't feel strongly either way about whether such sealed interfaces should have this special power, but it does seem like it needs to be decided either way before implementation because it would be hard to change that decision later without breaking some existing code.

Even if this doesn't include a special rule for exhaustiveness, this still feels better in that it describes the range of Decoder.Token() far better than any does.

EDIT: After posting this I realized that my type switch doesn't account for nil. That feels like it's a weird enough edge that it probably wouldn't be worth the special case of allowing exhaustive type-switch matching.

---

Finally, it seems like this would shrink the boilerplate required today to define what I might call a "sealed interface", by which I mean one which only accepts a fixed set of types defined in the same package as the interface.

One way I've used this in the past is to define struct types that act as unique identifiers for particular kinds of objects but then have some functions that can accept a variety of different identifier types for a particular situation:

type ResourceID struct {
    Type string
    Name string
}

type ModuleID struct {
    Name string
}

type Targetable interface {
    // Unexported method means that only types
    // in this package can implement this interface.
    targetable()
}

func (ResourceID) targetable() {}
func (ModuleID) targetable() {}

func Target(addr Targetable) {
    // ...
}

I think this proposal could reduce that to the following, if I've understood it correctly:

type ResourceID struct {
    Type string
    Name string
}

type ModuleID struct {
    Name string
}

type Targetable interface {
    ResourceID | ModuleID
}

func Target(addr Targetable) {
    // ...
}

---

If any of the examples I listed above don't actually fit what this proposal is proposing (aside from the question about exhaustive matching, which is just a question), please let me know!

If they do, then I must admit I'm not 100% convinced that the small reduction in boilerplate is worth this complexity, but I am leaning towards 👍 because I think the updated examples above would be easier to read for a future maintainer who is less experience with Go and so would benefit from a direct statement of my intent rather than having to infer the intent based on familiarity with idiom or with less common language features.

[ianlancetaylor]

@dsnet Sure, we could permit case ~T in a type switch, but there are further issues. A type switch can have a short declaration, and in a type switch case with a single type we're then permitted to refer to that variable using the type in the case. What type would that be for case ~T? If it's T then we lost the methods, and fmt.Printf will behave unexpectedly if the original type had a String method. If it's ~T what can we do with a value of that type? It's quite possible that these questions can be answered, but it's not just outside the scope of this proposal, it's actually complicated.

[ianlancetaylor]

@DeedleFake The alternative implementation is only an implementation issue, not a language issue. We shouldn't use that to change something about the language, like whether the value can be nil or some other zero value. In Go the zero value of interface types is nil. It would be odd to change that for the special case of interfaces that embed a union type element.

The reason pointer values matter is that given a value of the interface type, the current garbage collector implementation has to be able to very very quickly know which fields in that value are pointers. The current implementation does this by associating a bitmask of pointers with each type, such that a 1 in the bitmask means that the pointer-sized slot at that offset in the value always holds a pointer.

[ianlancetaylor]

@apparentlymart I think that everything you wrote is correct according to this proposal. Thanks.

[DeedleFake]

In Go the zero value of interface types is nil. It would be odd to change that for the special case of interfaces that embed a union type element.

It would be, but I think it would be worth it. And I don't think it would be so strange as to completely preclude eliminating the extra oddness that would come from union types always being nilable. In fact, I'd go so far as to say that if this way of implementing unions has to have them be nilable, then a different way of implementing them should be found.

The reason pointer values matter is that given a value of the interface type, the current garbage collector implementation has to be able to very very quickly know which fields in that value are pointers.

I was worried it was going to be the garbage collector... Ah well.

[merykitty]

A major problem is that type constraints work on static types while interfaces work on dynamic types of objects. This immediately prohibits this approach to do union types.

type Addable interface {
    int | float32
}

func Add[T Addable](x, y T) T {
    return x + y
}

This works because the static type of T can only be int or float, which means the addition operation is defined for all the type set of T. However, if we allow Addable to be a sum type, then the type set of T becomes {int, float, Addable} which does not satisfy the aforementioned properties!!!

[apparentlymart]

@merykitty per my understanding of the proposal, I think for the dynamic form of what you wrote you'd be expected to write something this:

type Addable interface {
    int | float32
}

func Add(x, y Addable) Addable {
    switch x := x.(type) {
    case int:
        return x + y.(int)
    case float32:
        return x + y.(float32)
    default:
        panic("unsupported Addable types %T + %T", x, y)
    }
}

Of course this would panic if used incorrectly, but I think that's a typical assumption for interface values since they inherently move the final type checking to runtime.

I would agree that the above seems pretty unfortunate, but I would also say that this feels like a better use-case for type parameters than for interface values and so the generic form you wrote is the better technique for this (admittedly contrived) goal.

[Merovius]

@merykitty No, in your example, Addable itself should not be able to instantiate Add. Addable does not implement itself (only int and float32 do).

[Merovius]

also, note that the type set never includes interfaces. So Addable is never in its own type set.

[mateusz834]

Is something like that going to be allowed?

type IntOrStr interface {
	int | string
}

func DoSth[T IntOrStr](x T) {
	var a IntOrStr = x
        _ = a
}

[zephyrtronium]

Let's say I have these definitions.

type I1 interface {
	int | any
}

type I2 interface {
	string | any
}

type I interface {
	I1 | I2
}

Would it be legal to have a variable of type I? Can I assign an I1 to it? What about string? any(int8)? int8?

[Merovius]

@mateusz834 Can't see why not.

@zephyrtronium

Would it be legal to have a variable of type I? Can I assign an I1 to it? What about string? any(int8)? int8?

I think the answer to all of these is "yes". For the cases where you assign an interface value, the dynamic type/value of the I variable would then become the dynamic type/value of the assigned interface. In particular, the dynamic type would never be an interface.

[Merovius]

FWIW my main issue with this proposal is that IMO union types should allow representing something like ~string | fmt.Stringer , but for well-known reasons this isn't possible right now and it's not clear it ever would be. One advantage of "real" sum types is that they have an easier time representing that kind of thing. Specifically, I don't think #54685 has that problem (though it's been a spell that I looked at that proposal in detail).

[leighmcculloch]

@ianlancetaylor Does the proposal as-is allow both type sets and functions in an interface? It would have a remarkable property not typically present in sum types where you could have a closed set of types along with the ability to have those types implement some common functions and be used as an interface.

[zephyrtronium]

@leighmcculloch

To address this shortcoming, could we make interface types that contain type sets non-nullable by default, and require an explicit nil | in the type set list. For type sets that do not specify nil, the default value of the interface value would be the zero value of the first type listed.

For reference, this has been suggested a few times in #19412 and #41716, starting with #19412 (comment). Requiring nil variants versus allowing source code order to affect semantics is the classic tension of sum types proposals.

Sometimes discriminated unions have cases where no data is required. I don't think the proposal supports this.

The spelling of a type with no information beyond existence is usually struct{}, or more generally any type with exactly one value. void, i.e. the zero type, means something different: logically it would represent that your unconditional variant is impossible, not that it carries no additional information.

Does the proposal as-is allow both type sets and functions in an interface? It would have a remarkable property not typically present in sum types where you could have a closed set of types along with the ability to have those types implement some common functions and be used as an interface.

Yes, since the proposal is just to allow values of general interfaces less ~T elements, methods would be fine and would dynamically dispatch to the concrete type. I agree that's a neat behavior. Unfortunately it does imply that methods can't be defined on a sum type itself; you'd have to wrap it in a struct or some other type.

[leighmcculloch]

Thanks @zephyrtronium. Taking your feedback into account, and also realizing that it is easy to redefine types, then I think points (2) and (3) I raised are not issues. Type definitions can be used to give the same type different semantics for each case. For example:

type ClaimPredicateUnconditional struct{}
type ClaimPredicateAnd []ClaimPredicate
type ClaimPredicateOr []ClaimPredicate
type ClaimPredicateNot ClaimPredicate
type ClaimPredicateBeforeAbsoluteTime Int64
type ClaimPredicateBeforeRelativeTime Int64

type ClaimPredicate interface {
    ClaimPredicateUnconditional |
    ClaimPredicateAnd |
    ClaimPredicateOr |
    ClaimPredicateNot |
    ClaimPredicateBeforeAbsoluteTime |
    ClaimPredicateBeforeRelativeTime
}

In the main Go code base I work in we have 106 unions implemented as multi-field structs, which require a decent amount of care to use. I think this proposal would make using those unions easier to understand, probably on par in terms of effort to write. If tools like gopls went on to support features like pre-filling out the case statements of a switch based on the type sets, since it can know the full set, that would make writing code using them easier too.

The costs of this proposal feel minimal. Any code using the sum type would experience the type as an interface and have nothing new to learn over that of interfaces. This is I think the biggest benefit of this proposal.

[ncruces]

To me, nil seems to be the big question here?

On the one hand, interface types are nilable and their zero value is nil.

On the other hand, union interface constraints made only of non-nilable types prevent a T from being nil, and that behaviour seems useful here as well. Is it that big a can of worms to say these can't be nil?

Exhaustiveness in type switches could potentially be left to tools.

[johnwarden]

This would avoid memory allocations if the T value is stored directly, and would be safer than a pointer.

I don't believe the value T can commonly be stored directly, for the same reason we can't do it in a regular interface.

In the proposal, Ian mentions that in some cases values could be stored directly, rather than boxed. This is impossible now because the exact type and size of an interface value's dynamic value can't be known at compile time. There may be other reasons, but I would guess interface { int64 } would be one case where the value could be stored directly.

Under this proposal, Option[T] offers no safety guarantees whatsoever over a *T.

because the value could not be accessed without first checking that it was valid. For example:

Of course it could. You can write x := optionalV.(float64). There is no safety difference between that and spelling it *x. And there is no meaningful difference between remembering to spell it if x, ok := optionalV.(float64); ok and spelling it if x != nil.

Oh yes you are absolutely right, I hadn't thought that through.

[leaxoy]

The proposal above illustrates how to add sum type (aka: union), but tagged union is more powerful and useful (which allows multiple occurrences of a type, use tags to distinguish different variants).

Real world designs:
https://doc.rust-lang.org/book/ch06-01-defining-an-enum.html
https://docs.swift.org/swift-book/LanguageGuide/Enumerations.html

[DmitriyMV]

@leaxoy sigma types issue is probably what you are looking for.

[jimmyfrasche]

Unlike most proposals, there are downsides to not accepting this one:

1. union elements in interfaces can only ever be used in constraints
2. if, hypothetically, there were a separate mechanism for sum or union types, it would be confusing that there is also this very similar mechanism that's unrelated

I think the second situation is unlikely. The bar would be much higher than any other language change, which is already pretty high.

I dislike the first situation. There are many uses for union types even if they have downsides compared to other more theoretically pure alternatives.

[leaxoy]

How about introduce new keyword enum or union and make it cannot be nil, just like struct. Nil in sum type is a big challenge.

[zephyrtronium]

@leaxoy Introducing a new keyword is not backward-compatible, because any code today using enum or union as variable names will cease to compile. We would also need to decide on what "it cannot be nil" actually means, because every type in Go must have a zero value. #19412 contains a great deal of discussion on this.

[leaxoy]

Perhaps this is a trade-off, although introducing new keywords breaks some compatibility, but handling nil is also tricky. Nil takes on too many features in go.

But after #56986 and #57001 and #60078, is there a mature way to introduce new features.

[Merovius]

FWIW this issue is specifically about using the existing syntax, because it seems dubious to have two different syntactical constructs to mean very similar things. Being able to reuse that syntax was, in fact, one of the (minor) arguments for introducing it to begin with.

[ydnar]

The proposal above illustrates how to add sum type (aka: union), but tagged union is more powerful and useful (which allows multiple occurrences of a type, use tags to distinguish different variants).

Real world designs: https://doc.rust-lang.org/book/ch06-01-defining-an-enum.html https://docs.swift.org/swift-book/LanguageGuide/Enumerations.html

This proposal can support tagged unions via specialized types:

type All struct{}

type None struct {}

type Some []string

type Filter interface {
	All | None | Some
}

func Select(f Filter) ([]string, error) {
	// ...
}

Empty struct values could be optimized away:

As an implementation note, we could in some cases use a different implementation for interfaces with an embedded union type. We could use a small code, typically a single byte, to indicate the type stored in the interface, with a zero indicating nil. We could store the values directly, rather than boxed.

Edit: "multiple values of a type:"

type Width uint32
type Height uint32
type Weight uint32

type Dimension interface {
	Width | Height | Weight
}

func f(d Dimension) ...

_ = f(Width(10))
_ = f(Height(20))

[ydnar]

In particular, the zero value of an interface type with an embedded union 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.

@ianlancetaylor would you consider a form that would disallow nil?

Some hypothetical syntax:

type I1 interface! {
    int | float64
}

1. What would the zero value be? The zero value of the first type in the union?
2. How would the compiler enforce assignment to variables of type I1?

[zephyrtronium]

@ydnar The question of "what would the zero value be" is exactly the one that needs to be answered for that kind of proposal. Syntax aside, the concept of non-nillable interfaces or sum types has been suggested many times between here, #19412, and other proposals. None of them have answered the zero value question in a way that satisfies even a majority of people (including those that have tried the answer "that of the first type in the union").

[DeedleFake]

Sum types in most languages do not work this way

That's true, but I think most languages also don't have a concept of zero values in the way that Go does. Rust, for example, requires all values of any type to always be explicitly set to something, even if it's a default value.

Random thought that might be terrible: What if Go did allow nil sum interfaces but with an unusual caveat: A variable of a sum interface type can't be set to nil manually. In other words, a declared but unassigned sum interface variable would be nil, but once changed it would be impossible to get it back to being nil, with a runtime check on assignment to make sure that an assignment of a dynamic value doesn't do that, either. Then it'll have a useful zero value, but one with minimal impact.

[tinne26]

A variable of a sum interface type can't be set to nil manually.

You could still set values to nil with:

type Bits64 interface { int64 | uint64 | float64 }
type Dummy struct { Field64 Bits64 }
func (d *Dummy) SetField64(value Bits64) {
    d.Field64 = value
}
func main() {
    var d1, d2 Dummy
    var value uint64
    d1.SetField64(value) // d1.Field64 stops being nil
    d1.SetField64(d2.Field64) // d1.Field64 is nil again...
}

To prevent this you would have allow only the concrete types listed in the sum type be assignable to sum type variables. Which is way, way much more restrictive. But yeah, it may be the only real alternative to fully nilable sum types if we want to make them be based on interfaces.

[Merovius]

@DeedleFake I don't believe that would be practically feasible. x := make([]T, 42) is an "assignment of zero values", so would have to panic - and, less obviously, x = append(x, someNonNilThing) - so we couldn't have slices. _, ok := m[x] as well, so you couldn't check if an element is in a map. x, ok := <-ch would be an assignment of a zero value, if the channel is closed, so you couldn't use that as a select-case. Etc. We would have to exhaustively list exceptions to that rule of "assigning a zero value is a runtime check and causes a panic" to make this work. It's not practical.

And without that runtime check, there is no real benefit, because you still have to code against the possibility of it being nil.

@tinne26 Under @DeedleFake's suggestion, that code would panic, because passing d2.Field64 as an argument is an assignment (from the language POV) so it would panic, as it is nil.

[gophun]

including those that have tried the answer "that of the first type in the union"

I don't remember, what was the problem with it? It's a straightforward rule that can be easily explained. It also appears to be intuitive, as it's the default response for most proposers when posed with the question.

[Merovius]

@gophun Currently, | in an interface is commutative - interface{ a | b } and interface{ b | a } mean the same thing. That would no longer be the case. There's also the question of what would happen with something like interface{ a | b ; b | a }. "first" is sometimes not super straight forward.

[gophun]

@Merovius
Yes, it would be awkward if interface is reused for union types. But if we made them separate (adding a keyword is not completely ruled out) with the "zero value based on first type" rule:

type foo union { a | b }

Then these

interface { a | b }
interface { a | b ; b | a }

could be short form for:

interface { union{ a | b } }
interface { union{ a | b } ; union{ b | a } }

Here the order wouldn't matter.

[Merovius]

@gophun This issue is about using general interfaces for unions. #19412 is about other options - which each have their own set of problems, but that discussion doesn't belong here. And FWIW, adding a union keyword like you suggest has been discussed over there at length.

[gophun]

@Merovius Thank you for the pointer; I'll take it over there. The keyword option was criticized solely on the grounds of being "not backwards compatible," a stance that has been clearly contradicted by the Go project lead.

[Merovius]

The keyword option was criticized solely on the grounds of being "not backwards compatible,"

That is not true. But again, that discussion doesn't belong here.

[zephyrtronium]

It would not, for a couple reasons:

1. The type parameter T is set at compile time. &m.Value is a *T where T is one of the elements of constraints.Integer, constraints.Float, string, or []byte, not a sum type. This proposal is about allowing run-time values of interface types that contain union elements; it is mostly orthogonal to type parameters.
2. constraints.Signed &c. use ~T elements. This proposal does not allow values of interface types when those interfaces contain ~T elements.

I think what you want is #45380.

[zephyrtronium]

Seeing this example, it occurs to me that #57644 (comment) actually seems to be wrong. Consider these definitions:

type bytestring interface {
    string | []byte
}

func f[T bytestring]() {}

Type bytestring itself can instantiate f if bytestring satisfies bytestring, which it does if bytestring implements bytestring. Since bytestring is an interface, it implements any interface of which its type set is a subset, which trivially includes itself. Therefore f[bytestring] is a legal instantiation.

So, it seems that we need additional adjustments to the spec to make interfaces with union elements legal. Otherwise every type constraint which includes a union element and no ~T terms gains a non-empty set of members, all of interface type, which will be illegal in almost every case.