go
go copied to clipboard
golang
proposal: spec: add sum types / discriminated unions
This is a proposal for sum types, also known as discriminated unions. Sum types in Go should essentially act like interfaces, except that:
- they are value types, like structs
- the types contained in them are fixed at compile-time
Sum types can be matched with a switch statement. The compiler checks that all variants are matched. Inside the arms of the switch statement, the value can be used as if it is of the variant that was matched.
This has been discussed several times in the past, starting from before the open source release. The past consensus has been that sum types do not add very much to interface types. Once you sort it all out, what you get in the end is an interface type where the compiler checks that you've filled in all the cases of a type switch. That's a fairly small benefit for a new language change.
If you want to push this proposal along further, you will need to write a more complete proposal doc, including: What is the syntax? Precisely how do they work? (You say they are "value types", but interface types are also value types). What are the trade-offs?
See https://www.reddit.com/r/golang/comments/46bd5h/ama_we_are_the_go_contributors_ask_us_anything/d03t6ji/?st=ixp2gf04&sh=7d6920db for some past discussion to be aware of.
I think this is too significant a change of the type system for Go1 and there's no pressing need. I suggest we revisit this in the larger context of Go 2.
Thanks for creating this proposal. I've been toying with this idea for a year or so now. The following is as far as I've got with a concrete proposal. I think "choice type" might actually be a better name than "sum type", but YMMV.
Sum types in Go
A sum type is represented by two or more types combined with the "|" operator.
type: type1 | type2 ...
Values of the resulting type can only hold one of the specified types. The type is treated as an interface type - its dynamic type is that of the value that's assigned to it.
As a special case, "nil" can be used to indicate whether the value can become nil.
For example:
type maybeInt nil | int
The method set of the sum type holds the intersection of the method set of all its component types, excluding any methods that have the same name but different signatures.
Like any other interface type, sum type may be the subject of a dynamic type conversion. In type switches, the first arm of the switch that matches the stored type will be chosen.
The zero value of a sum type is the zero value of the first type in the sum.
When assigning a value to a sum type, if the value can fit into more than one of the possible types, then the first is chosen.
For example:
var x int|float64 = 13
would result in a value with dynamic type int, but
var x int|float64 = 3.13
would result in a value with dynamic type float64.
Implementation
A naive implementation could implement sum types exactly as interface values. A more sophisticated approach could use a representation appropriate to the set of possible values.
For example a sum type consisting only of concrete types without pointers could be implemented with a non-pointer type, using an extra value to remember the actual type.
For sum-of-struct-types, it might even be possible to use spare padding bytes common to the structs for that purpose.
@rogpeppe How would that interact with type assertions and type switches? Presumably it would be a compile-time error to have a case on a type (or assertion to a type) that is not a member of the sum. Would it also be an error to have a nonexhaustive switch on such a type?
For type switches, if you have
type T int | interface{}
and you do:
switch t := t.(type) {
case int:
// ...
and t contains an interface{} containing an int, does it match the first case? What if the first case is case interface{}?
Or can sum types contain only concrete types?
What about type T interface{} | nil? If you write
var t T = nil
what is t's type? Or is that construction forbidden? A similar question arises for type T []int | nil, so it's not just about interfaces.
Yes, I think it would be reasonable to have a compile-time error to have a case that can't be matched. Not sure about whether it's a good idea to allow non-exhaustive switches on such a type - we don't require exhaustiveness anywhere else. One thing that might be good though: if the switch is exhaustive, we could not require a default to make it a terminating statement.
That means that you can get the compiler to error if you have:
func addOne(x int|float64) int|float64 {
switch x := x.(type) {
case int:
return x + 1
case float64:
return x + 1
}
}
and you change the sum type to add an extra case.
For type switches, if you have
type T int | interface{}
and you do:
switch t := t.(type) { case int: // ... and t contains an interface{} containing an int, does it match the first case? What if the first case is case interface{}?
t can't contain an interface{} containing an int. t is an interface type just like any other interface type, except that it can only contain the enumerated set of types that it consists of. Just like an interface{} can't contain an interface{} containing an int.
Sum types can match interface types, but they still just get a concrete type for the dynamic value. For example, it would be fine to have:
type R io.Reader | io.ReadCloser
What about type T interface{} | nil? If you write
var t T = nil
what is t's type? Or is that construction forbidden? A similar question arises for type T []int | nil, so it's not just about interfaces.
According to the proposal above, you get the first item in the sum that the value can be assigned to, so you'd get the nil interface.
In fact interface{} | nil is technically redundant, because any interface{} can be nil.
For []int | nil, a nil []int is not the same as a nil interface, so the
concrete value of ([]int|nil)(nil) would be []int(nil) not untyped nil.
The []int | nil case is interesting. I would expect the nil in the type declaration to always mean "the nil interface value", in which case
type T []int | nil
var x T = nil
would imply that x is the nil interface, not the nil []int.
That value would be distinct from the nil []int encoded in the same type:
var y T = []int(nil) // y != x
Wouldn't nil always be required even if the sum is all value types? Otherwise what would var x int64 | float64 be? My first thought, extrapolating from the other rules, would be the zero value of the first type, but then what about var x interface{} | int? It would, as @bcmills points out, have to be a distinct sum nil.
It seems overly subtle.
Exhaustive type switches would be nice. You could always add an empty default: when it's not the desired behavior.
The proposal says "When assigning a value to a sum type, if the value can fit into more than one of the possible types, then the first is chosen."
So, with:
type T []int | nil
var x T = nil
x would have concrete type []int because nil is assignable to []int and []int is the first element of the type. It would be equal to any other []int (nil) value.
Wouldn't nil always be required even if the sum is all value types? Otherwise what would var x int64 | float64 be?
The proposal says "The zero value of a sum type is the zero value of the first type in the sum.", so the answer is int64(0).
My first thought, extrapolating from the other rules, would be the zero value of the first type, but then what about var x interface{} | int? It would, as @bcmills points out, have to be a distinct sum nil
No, it would just be the usual interface nil value in that case. That type (interface{} | nil) is redundant. Perhaps it might be a good idea to make it a compiler to specify sum types where one element is a superset of another, as I can't currently see any point in defining such a type.
The zero value of a sum type is the zero value of the first type in the sum.
That is an interesting suggestion, but since the sum type must record somewhere the type of the value that it currently holds, I believe it means that the zero value of the sum type is not all-bytes-zero, which would make it different from every other type in Go. Or perhaps we could add an exception saying that if the type information is not present, then the value is the zero value of the first type listed, but then I'm not sure how to represent nil if it is not the first type listed.
So (stuff) | nil only makes sense when nothing in (stuff) can be nil and nil | (stuff) means something different depending on whether anything in stuff can be nil? What value does nil add?
@ianlancetaylor I believe many functional languages implement (closed) sum types essentially like how you would in C
struct {
int which;
union {
A a;
B b;
C c;
} summands;
}
if which indexes into the union's fields in order, 0 = a, 1 = b, 2 = c, the zero value definition works out to all bytes are zero. And you'd need to store the types elsewhere, unlike with interfaces. You'd also need special handling for the nil tag of some kind wherever you store the type info.
That would make union's value types instead of special interfaces, which is also interesting.
Is there a way to make the all zero value work if the field which records the type has a zero value representing the first type? I'm assuming that one possible way for this to be represented would be:
type A = B|C
struct A {
choice byte // value 0 or 1
value ?// (thing big enough to store B | C)
}
[edit]
Sorry @jimmyfrasche beat me to the punch.
Is there anything added by nil that couldn't be done with
type S int | string | struct{}
var None struct{}
?
That seems like it avoids a lot of the confusion (that I have, at least)
Or better
type (
None struct{}
S int | string | None
)
that way you could type switch on None and assign with None{}
@jimmyfrasche struct{} is not equal to nil. It's a minor detail, but it would make type-switches on sums needlessly(?) diverge from type-switches on other types.
@bcmills It wasn't my intent to claim otherwise—I meant that it could be used for the same purpose as differentiating a lack of value without overlapping with the meaning of nil in any of the types in the sum.
@rogpeppe what does this print?
// r is an io.Reader interface value holding a type that also implements io.Closer
var v io.ReadCloser | io.Reader = r
switch v.(type) {
case io.ReadCloser: fmt.Println("ReadCloser")
case io.Reader: fmt.Println("Reader")
}
I would assume "Reader"
@jimmyfrasche I would assume ReadCloser, same as you'd get from a type-switch on any other interface.
(And I would also expect sums which include only interface types to use no more space than a regular interface, although I suppose that an explicit tag could save a bit of lookup overhead in the type-switch.)
@bcmills it's the assigment that's interesting, consider: https://play.golang.org/p/PzmWCYex6R
@ianlancetaylor That's an excellent point to raise, thanks. I don't think it's hard to get around though, although it does imply that my "naive implementation" suggestion is itself too naive. A sum type, although treated as an interface type, does not have to actually contain direct pointer to the type and its method set - instead it could, when appropriate, contain an integer tag that implies the type. That tag could be non-zero even when the type itself is nil.
Given:
var x int | nil = nil
the runtime value of x need not be all zeros. When switching on the type of x or converting it to another interface type, the tag could be indirected through a small table containing the actual type pointers.
Another possibility would be to allow a nil type only if it's the first element, but that precludes constructions like:
var t nil | int
var u float64 | t
@jimmyfrasche I would assume ReadCloser, same as you'd get from a type-switch on any other interface.
Yes.
@bcmills it's the assigment that's interesting, consider: https://play.golang.org/p/PzmWCYex6R
I don't get this. Why would "this [...] have to be valid for the type switch to print ReadCloser" Like any interface type, a sum type would store no more than the concrete value of what's in it.
When there are several interface types in a sum, the runtime representation is just an interface value - it's just that we know that the underlying value must implement one or more of the declared possibilities.
That is, when you assign something to a type (I1 | I2) where both I1 and I2 are interface types, it's not possible to tell later whether the value you put into was known to implement I1 or I2 at the time.
If you have a type that's io.ReadCloser | io.Reader you can't be sure when you type switch or assert on io.Reader that it's not an io.ReadCloser unless assignment to a sum type unboxes and reboxes the interface.
Going the other way, if you had io.Reader | io.ReadCloser it would either never accept an io.ReadCloser because it goes strictly right-to-left or the implementation would have to search for the "best matching" interface from all interfaces in the sum but that cannot be well defined.
@rogpeppe In your proposal, ignoring optimization possibilities in the implementation and subtleties of zero values, the main benefit of using a sum type over a manually crafted interface type (containing the intersection of the relevant methods) is that the type checker can point out errors at compile time rather than runtime. A 2nd benefit is that a type's value is more discriminated and thus may help with readability/understanding of a program. Is there any other major benefit?
(I am not trying to diminish the proposal in any way, just trying to get my intuition right. Especially if the extra syntactic and semantic complexity is "reasonably small" - whatever that may mean - I can definitively see the benefit of having the compiler catch errors early.)
@griesemer Yes, that's about right.
Particularly when communicating messages over channels or the network, I think it helps readability and correctness to be able to have a type that expresses exactly the available possibilities. It's common currently to make a half-hearted attempt to do this by including an unexported method in an interface type, but this is a) circumventable by embedding and b) it's hard to see all the possible types because the unexported method is hidden.
@jimmyfrasche
If you have a type that's io.ReadCloser | io.Reader you can't be sure when you type switch or assert on io.Reader that it's not an io.ReadCloser unless assignment to a sum type unboxes and reboxes the interface.
It you have that type, you know that it's always an io.Reader (or nil, because any io.Reader can also be nil). The two alternatives aren't exclusive - the sum type as proposed is an "inclusive or" not an "exclusive or".
Going the other way, if you had io.Reader | io.ReadCloser it would either never accept an io.ReadCloser because it goes strictly right-to-left or the implementation would have to search for the "best matching" interface from all interfaces in the sum but that cannot be well defined.
If by "going the other way", you mean assigning to that type, the proposal says:
"When assigning a value to a sum type, if the value can fit into more than one of the possible types, then the first is chosen."
In this case, a io.ReadCloser can fit into both an io.Reader and an io.ReadCloser, so it chooses io.Reader, but there's actually no way to tell afterwards. There is no detectable difference between the type io.Reader and the type io.Reader | io.ReadCloser, because io.Reader can also hold all interface types that implement io.Reader. That's why I suspect it might be a good idea to make the compiler reject types like this. For example, it could reject any sum type involving interface{} because interface{} can already contain any type, so the extra qualifications don't add any information.
@rogpeppe there are a lot of things I like about your proposal. The left to right assignment semantics and the zero value is the zero value of the leftmost type rules are very clear and simple. Very Go.
What I'm worried about is assigning a value that's already boxed in an interface to a sum typed variable.
Let's, for the moment, use my previous example and say that RC is a struct that can be assigned to an io.ReadCloser.
If you do this
var v io.ReadCloser | io.Reader = RC{}
the results are obvious and clear.
However, if you do this
var r io.Reader = RC{}
var v io.ReadCloser | io.Reader = r
the only sensible thing to do is have v store r as an io.Reader, but that means when you type switch on v you can't be sure that when you hit the io.Reader case that you don't in fact have an io.ReadCloser. You'd need to have something like this:
switch v := v.(type) {
case io.ReadCloser: useReadCloser(v)
case io.Reader:
if rc, ok := v.(io.ReadCloser); ok {
useReadCloser(rc)
} else {
useReader(v)
}
}
Now, there's a sense in which io.ReadCloser <: io.Reader, and you could just disallow those, as you suggested, but I think the problem is more fundamental and may apply to any sum type proposal for Go†.
Let's say you have three interfaces A, B, and C, with the methods A(), B(), and C() respectively, and a struct ABC with all three methods. A, B, and C are disjoint so A | B | C and its permutations are all valid types. But you still have cases like
var c C = ABC{}
var v A | B | C = c
There a bunch of ways to rearrange that and you still get no meaningful guarantees about what v is when interfaces are involved. After you unbox the sum you need to unbox the interface if order is important.
Maybe the restriction should be that none of the summands can be interfaces at all?
The only other solution I can think of is to disallow assigning an interface to a sum typed variable, but that seems in its own way more severe.
† that doesn't involve type constructors for the types in the sum to disambiguate (like in Haskell where you have to say Just v to construct a value of type Maybe)—but I am not in favor of that at all.
@jimmyfrasche Is the use-case for ordered unboxing actually important? That's not obvious to me, and for the cases where it is important it's easy to work around with explicit box structs:
type ReadCloser struct { io.ReadCloser }
type Reader struct { io.Reader }
var v ReadCloser | Reader = Reader{r}