https://github.com/golang/go/issues/76949
Algebraic data types, comprised of product and sum types, are alone sufficient to express any bit sequence, and therefore all serialized data. Go already has product and sum types, but whereas its anonymous product types (struct types) are generalized for users to use, its sum types are not. Instead, Go has a fixed set of predeclared sum types, such as numbers and maps, with special semantics, that users must make do with. It is possible to map own's own sum types to integers, for example, but doing so is cumbersome, error-prone, and not type-safe, and having special semantics increases the size of the language and decreases the orthogonality of its features.
I propose that Go adds anonymous sum types, and changes predeclared types to be in terms of anonymous sum types.
A struct type (struct in Go) represents a sequence of zero or more named types called fields. A struct type's bits are its first field's bits, followed by its second field's bits, and so on. A struct type's zero value is the zero value of all its fields.
A sum type represents a selection of one out of a sequence of one or more named types called fields. A sum type's bits are the smallest number of bits that represent the unsigned integer that indicates the selected field (called the field index) (the first field's index is 0), followed by the bits of the selected field's value. A sum type's zero value is the zero value of the type of its first field.
I will call anonymous sum types and the types they underly generalized sum types, as opposed to predeclared sum types as they are today.
A bit can be represented as a sum type with two zero-size field types:
type Bit sum {
Zero struct{}
One struct{}
}
Bit has two fields, so its field index size is always 1 bit. Since both of its fields have zero size, the total size of Bit is always 1 bit.
The syntax and semantics of sum types are like that of struct types, except only one field can be assigned at a time, reading an unassigned field is a runtime error, and fields are not addressable. Field assignment can be tested with comma-ok/two-value assignments, like map keys.
var b Bit
ok := b == Bit{} // True
ok = b == Bit{Zero: struct{}{}} // True
b = Bit{Zero: struct{}{}}
v0 := b.Zero
v0, ok = b.Zero // True
v1 := b.One // Panic
v1, ok = b.One // False
b = Bit{One: struct{}{}}
v0 = b.Zero // Panic
v0, ok = b.Zero // False
v1 = b.One
v1, ok = b.One // True
b.Zero = struct{}{} // Selects field Zero; field One has no value
b.One = struct{}{} // Selects field One; field Zero has no value
_ = &b.Zero // Illegal
switch b {
case Bit{Zero: struct{}{}}: // Doesn't match
case Bit{One: struct{}{}}: // Does match
}
Conditional execution based on structural pattern matching is done by switch-match statements. They must handle every field for struct and sum types unless a default case is used. There cannot be equivalent patterns in the same switch-match statement.
type Engineer struct {
Name string
Specialty string
}
type Manager struct {
Name string
Reports int
}
type Employee sum {
Engineer Engineer
Manager Manager
}
// Struct type
var eng Engineer
switch v := eng.(match) {
case Engineer{}: // Matches all values
// v is of type Engineer
case Engineer{_, _}: // Matches all values
case Engineer{name, specialty}: // Matches all values
case Engineer{name, "Go"}: // Matches all Gophers
case Engineer{Name: "John"}: // Matches all Johns
case Engineer{"John", "Go"}: // Matches only Engineer{Name: "John", Specialty: "Go"}
default: // Matches anything else
// v is of type Engineer
}
switch eng.(match) {
case {}: // Type name can be omitted
case {_, _}:
case {"John", "Go"}:
case {name, "Go"}:
case {name, specialty}:
case {Name: "John"}:
case {"John", "Go"}
}
// Sum type
var emp Employee
switch v := emp.(match) { // v's type is the assigned field's type if there is a specific match
case Employee{Manager: Manager{}}: // Doesn't match
fmt.Println(v.Reports)
default: // Does match
fmt.Println(v) // v is the same as emp because there is no specific match
}
switch emp.(match) {
case {Engineer: Engineer{}}: // Same as Employee{Engineer: Engineer{}}
case {Manager: Manager{}}:
}
switch emp.(match) {
case {Engineer: {}}: // Same as {Engineer: Engineer{}}
case {Manager: {}}: // Type name can be omitted from prefix of struct type literal
}
switch emp.(match) {
case {Engineer}: // Same as {Engineer: {}}
case {Manager}:
}
switch emp.(match) {
case {Engineer: {name, specialty}}: // Struct type sub-pattern ({name, specialty}) inside sum type pattern
case {Manager: {name, 123}}: // Sum type sub-pattern (123) inside struct type sub-pattern ({name, 123}) inside sum type pattern
}
Enums are a special case of sum type where all field types are zero-size and are therefore immutable and can therefore be omitted:
type Bool enum {
False
True
}
b := Bool{False}
b = Bool{True}
ok := b == Bool{True} // True
b.False = struct{}{} // Illegal
b.True = struct{}{} // Illegal
switch b {
case Bool{False}: // Doesn't match
case Bool{True}: // Does match
}
The size of Bool, like Bit, is always 1 bit.
Using only struct and sum types without special syntax or semantics, we can represent various generally useful types not specific to Go.
An array type of size N and element type E is a struct type with N fields of type E:
// Pseudocode
type Array0[E any] struct{} // == [0]E
type Array1[E any] struct{Elem1 E} // == [1]E
type Array2[E any] struct{Elem1, Elem2 E} // == [2]E
type Array3[E any] struct{Elem1, Elem2, Elem3 E} // == [3]E
...
type ArrayN[E any] struct{Elem1, Elem2, ..., ElemN E} // == [N]E
A list type with dynamic length N and element type E is a sum type that enumerates all array lengths for element type E, where the field index bits represent the length of the array:
// Pseudocode
type List[E any] sum {
Length0 struct{}
Length1 struct{Elem1 E}
Length2 struct{Elem1, Elem2 E}
Length3 struct{Elem1, Elem2, Elem3 E}
...
}
A map type with key type K and value type V is a list of key-value pairs:
type Map[K comparable, V any] List[struct{
Key K
Value V
}]
An optional type with element type T is a sum type with two fields, one with the element type and one without:
type Optional[T any] sum {
No struct{}
Yes T
}
Predeclared Go types can be redefined in terms of generalized sum types.
For example, predeclared number types can be defined in terms of arrays of Bits (arrays being defined as above). An array of 8 Bits has a size of 8 bits, and so on.
type Int8 [8]Bit // Pseudocode: Array8[Bit]
type Int16 [16]Bit
type Int32 [32]Bit
type Int64 [64]Bit
For these types, operations are syntactic sugar for method calls, method calls are inlined where possible, and number literals are syntactic sugar for the corresponding sum type zero value.
func (Int8) Add(Int8) Int8 // Implemented in assembly
func (Int8) Sub(Int8) Int8
...
var x Int8 = 1 // `1` is syntactic sugar for Int8{Bit{}, Bit{}, Bit{}, Bit{}, Bit{}, Bit{}, Bit{}, Bit{One: struct{}{}}}
var _ = x.Add(x) // Function call is inlined
var _ = x + x // Syntactic sugar for x.Add(x), which is inlined
var _ func(Int8) Int8 = x.Add // x.Add is a normal function
var _ interface { Add(Int8) Int8 } = x // Int8.Add is a normal method
Every other predeclared type can be redefined this way too:
type Channel[...] sum {
Nil struct{}
notNil ...
}
type Map[...] sum {
Nil struct{}
notNil ...
}
type Pointer[...] sum {
Nil struct{}
notNil ...
}
type Slice[...] sum {
Nil struct{}
notNil ...
}
where operations are syntactic sugar for method calls, method calls are inlined where possible, and nil literals are syntactic sugar for the corresponding sum type zero value.
var b Bool
var c Channel[Int8] // Zero value is Channel[Int8]{Nil: struct{}{}}
var m Map[Int8, Int8] // Zero value is Map[Int8, Int8]{Nil: struct{}{}}
var p Pointer[Int8] // Zero value is Pointer[Int8]{Nil: struct{}{}}
var s Slice[Int8] // Zero value is Slice[Int8]{Nil: struct{}{}}
_ = b == false // Equivalent to: b == Bool{False}
_ = c == nil // Equivalent to: c == Channel[Int8]{Nil: struct{}{}}
_ = m == nil // Equivalent to: m == Map[Int8, Int8]{Nil: struct{}{}}
_ = p == nil // Equivalent to: p == Pointer[Int8]{Nil: struct{}{}}
_ = s == nil // Equivalent to: s == Slice[Int8]{Nil: struct{}{}}
func (Channel[T]) Send(T) // Implemented in assembly
func (Channel[T]) Recv() (T, bool)
...
c.Send(b) // Function call is inlined
c <- b // Syntactic sugar for c.Send(b), which is inlined
var _ func(Bool) = c.Send // c.Send is a normal function
var _ interface { Send(Bool) } = c // Channel[Bool].Send is a normal method
Turning operations into methods means that you can assign predeclared types to non-empty, normal interfaces, which means you can treat them just like you do user-defined types. For example, you do not need two generic functions to handle predeclared and user-defined types separately, as is the case with slices.Sort and slices.SortFunc and many other functions in that package and elsewhere.
Since dealing with zero values is common with sum types, there is a shorthand for it:
var _ Bit = {}
var _ Bool = {}
var _ Int8 = {}
var _ Map[K, V] = {}
var _ Pointer[T] = {}
var _ Slice[T] = {}
var _ struct{} = {}
var _ interface{} = {}
Since dealing with struct types of zero size is common with sum types, there is a shorthand for it:
type unit = struct{} // Universe block
type Optional[T any] sum {
No unit
Yes T
}
(The unit type has only one value, which is the case for struct{}.)
By default, types are encoded such that field bits and field-index bits are padded as appropriate to align them for memory. Arrays are encoded without padding. However, types don't have to be padded in all cases, which can be useful when reading serialized data from files.
Note that there are multiple ways to achieve the same bit sequence:
type Int2 [2]Bit
type Int2 enum {
Zero
One
Two
Three
}
Note that adding a field to a sum type breaks switch-match statements that handle it without a default case. This is intentional and is beneficial: it forces you to handle the new field in all the places you handle the sum type. Imagine adding a new case (a new number) to an Int8 type that can already represent 0–255 and not updating all the code that handles the type; it makes little sense. If you want to add cases to your code without worrying about updating the handling code, use an interface instead. Sum types are probably best for small scopes like Optional or well-understood domains like Int8, not cases where you're throwing in new fields haphazardly.
That being said, sometimes sum types must evolve, such as a sum type that represents the Go grammar, and sometimes programs would remain valid even though they do not handle the new fields, in which case using a default case in a switch-match statement to avoid a break is appropriate.
Related Issues
Related Discussions
(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)
switch b {
case Bit{Zero: product{}{}}: // Doesn't match
case Bit{One: product{}{}}: // Does match
}
Any syntax that does not allow me to refer by just the named type (b.Zero / b.One) is a non starter for me.
The bulk of this proposal is a sketch of how to reexpress Go's type system constructively starting from only the zero type struct{} and the + and × operators on types. While this is a fun exercise I don't think it addresses the interesting questions. There have been a number of proposals for sum types and/or pattern matching in Go. (See the gabyhelp links above for a start.) I wonder whether you have looked at them and considered where they fall short. Some of the open questions or problems are:
- the nil value problem (for approaches based on interfaces);
- the zero value problem (which case of the sum is the default?);
- the evolution problem (adding a field breaks every switch; some argue this is a feature, others a bug);
- the race escalation problem (races on union-typed variables make it easy to accidentally convert nonpointers to pointers, similar to interfaces but worse);
- whether pattern matching can be generalized beyond sum types, perhaps giving most of the benefit without the need for actual sum types;
- how much additional robustness results in practice from greater type-safety (e.g. by replacing implicit nil *T dereferences by explicit Option[T].Must operations).
Go already has product and sum types, but whereas its anonymous product types (structs) are generalized for users to use, its sum types are not. Instead, Go has a fixed set of predeclared sum types, such as numbers and strings
I'm not quite sure what you are getting at by mentioning numbers and strings here. (Those are the types for which the sum T+T is defined, but I don't think that is your point. Sum types--called unions--also have a role as constraint types for generic interfaces, but again I don't think that's your point.) Go's current notion of sum types is certainly weaker than products, but it is not limited to numbers and strings. To express a sum type in Go today, one defines an interface with a fixed set of implementation types, such as ast.Expr and *ast.CallExpr, etc. The main downsides of the interface-based approach compared to, say, sum types in Standard ML, are:
- 1. the inability to force a closed set of implementation types (the Expr.exprNode marker method is only a partial solution);
- 2. the requirement to permit nil as a value of the sum type; and
- 3. the lack of pattern-matching syntax.
The inefficiency of the memory representation, requiring one word for the type descriptor versus just ceil(log2(24)) = 5 bits of type discrimination for the 24 implementation types, is a consequence primarily of item 1, though technically it is an implementation detail, as a sufficiently smart whole-program compiler could perform this optimization once the complete "implements" relation is known.
As a language change proposal, this seems like a duplicate of #76920. If this is not a duplicate, could you explain how it differs?
In the proposal text, I find writing product where current Go uses struct to be very confusing. Go is not going to replace the keyword struct with the keyword product. A language change proposal needs to start from where the language is today.
Any syntax that does not allow me to refer by just the named type (b.Zero / b.One) is a non starter for me.
@doggedOwl b.Zero isn't a type, so I'm not sure what you're saying. b.Zero is a field. There are examples of referring to only the field name in a switch-match statement.
The bulk of this proposal is a sketch of how to reexpress Go's type system constructively starting from only the zero type struct{} and the + and × operators on types.
@adonovan Not concretely, but perhaps that's equivalent, depending on what you mean by "struct{} and the + and × operators."
I wonder whether you have looked at them and considered where they fall short. Some of the open questions or problems are:
I'm not aware of any other proposal that has this proposal's specific semantics (even just focusing on anonymous sum types and their field assignments, no switch-match statement, enums, predeclared type changes, etc.), and I do read other sum type proposals when I see them. If you're aware of one, please link to it.
This proposal addressed the applicable points with deliberate design decisions, or at least that was my intent. Perhaps some people consider those problem domains open questions even with this solution, but I do not, obviously. If you have specific questions or points about trade-offs or pros/cons, I'm all ears.
the nil value problem (for approaches based on interfaces);
This approach doesn't use interfaces or anything "nil-able" in the current Go sense.
I'm aware that there was a past proposal to add a zero-value syntax for all types, the {} syntax was discussed, and the proposal was declined. I voted on it. I may have even commented on it. I didn't agree with the outcome. However, its inclusion here isn't just a plain repeated proposal of the idea, disregarding the prior discussion and consensus. I included it in this proposal because, as the section name "Quality of life improvements" and preamble "Since dealing with zero values is common with sum types" suggest, the addition of anonymous sum types makes sum types much more prevalent than they already are, and in my judgment tips the value balance in favor of better expressiveness by increased concision. In short, the calculation changes. This line of thinking generally underlies any element of this design you find similar or identical to past proposals. The fundamental nature of anonymous sum types (and therefore their long and deep reach into the language) is underscored for a reason.
As with anything, take what you like and leave the rest. If you don't like the zero-value syntax, then consider the proposal without it.
the zero value problem (which case of the sum is the default?);
Whether the zero value is the first field or identified by a default keyword or by some other means is beyond the scope of the proposal at this point, although what I chose to present is what I personally think is best. There are pros and cons for both approaches. In my mind, the overriding concern here is the consistent syntax between product and sum types. Sum type syntax isn't some weird new thing you have to learn. There's a keyword, some curly braces, and a list of fields, just like product types. The only difference is what the fields mean. The keyword distinguishes the semantics.
the evolution problem (adding a field breaks every switch; some argue this is a feature, others a bug);
This was addressed:
Note that adding a field to a sum type breaks switch-match statements that handle it without a default case. This is intentional and is beneficial: it forces you to handle the new field in all the places you handle the sum type. Imagine adding a new case (a new number) to an Int8 type that can already represent 0–255 and not updating all the code that handles the type; it makes little sense. If you want to add cases to your code without worrying about updating the handling code, use an interface instead. Sum types are probably best for small scopes like Optional or well-understood domains like Int8, not cases where you're throwing in new fields haphazardly.
That being said, sometimes sum types must evolve, such as a sum type that represents the Go grammar, and sometimes programs would remain valid even though they do not handle the new fields, in which case using a default case in a switch-match statement to avoid a break is appropriate.
If you see an issue with this aspect of the design, please explain how this aspect isn't also a problem for other languages that have it, such as Haskell.
the race escalation problem (races on union-typed variables make it easy to accidentally convert nonpointers to pointers, similar to interfaces but worse);
I don't see what you mean. Where are there pointers? How does this apply to, say, Int8 or Bool? As noted above, anonymous sum types aren't based on or use interfaces.
whether pattern matching can be generalized beyond sum types, perhaps giving most of the benefit without the need for actual sum types;
I addressed the need for sum types in the introduction:
It is possible to map own's own sum types to integers, for example, but doing so is cumbersome, error-prone, and not type-safe, and having special semantics increases the size of the language and decreases the orthogonality of its features.
Not only do you get a complete sum type solution that delivers generalized sum types, it does it in a way that can be applied to predeclared types in a backward-compatible way.
how much additional robustness results in practice from greater type-safety (e.g. by replacing implicit nil *T dereferences by explicit Option[T].Must operations).
Safety is only one dimension. Expressiveness, concision, consistency, and performance are other dimensions. However, considering just safety, the Go Team seems to have already judged there to be sufficient potential value by showing so much interest in https://github.com/golang/go/issues/57644 and https://github.com/golang/go/issues/76920 and past proposals for sum types. It doesn't seem that I need to make that argument myself. However, I can do so if this is a serious question posed to all sum type proposals, including the ones linked to in this paragraph.
I'm not quite sure what you are getting at by mentioning numbers and strings here. (Those are the types for which the sum T+T is defined, but I don't think that is your point.
I don't know what you mean by "the sum T+T." It would help if you referred to the ideas and terminology of this proposal where possible.
This was a late change in the wording. It used to say "numbers and maps," but "map" was used as a verb in the next sentence, so I changed "maps" to "strings" to avoid confusion. I think I didn't quite think that one through. Go strings are basically a pointer and a length—a product type—whereas the string type representation I had in mind was this simple, non-Go-specific representation:
type String List[Byte]
which is a sum type. I'll correct the wording.
Sum types--called unions--also have a role as constraint types for generic interfaces but again I don't think that's your point.
Correct, here they're not. They have nothing to do with the current "type unions" of generics. As pointed out in the proposal, such "type unions" wouldn't have been necessary with anonymous sum types.
Go's current notion of sum types is certainly weaker than products, but it is not limited to numbers and strings.
I didn't say it was limited to numbers and strings:
Go has a fixed set of predeclared sum types, such as numbers and strings
I listed those as examples. See the "Predeclared types" section for other examples.
To express a sum type in Go today, one defines an interface with a fixed set of implementation types, such as ast.Expr and *ast.CallExpr, etc. The main downsides of the interface-based approach compared to, say, sum types in Standard ML, are:
- the inability to force a closed set of implementation types (the Expr.exprNode marker method is only a partial solution);
- the requirement to permit nil as a value of the sum type; and
- the lack of pattern-matching syntax.
Partially correct, in my opinion. For reasons 1 and 2, according to the Wikipedia source I gave at the start of the proposal, they are not sum types, anymore than Java's Object is a sum type. Sub-types are not sum types.
Regarding reason 3, sum types don't require pattern matching (Go already has sum types but no pattern matching). This proposal does suggest adding it, but anonymous sum types can be added without it. Comma-OK/two-value assignments are sufficient to set and test sum type fields, as shown in the examples.
Thanks for reading!
As a language change proposal, this seems like a duplicate of https://github.com/golang/go/issues/76920. If this is not a duplicate, could you explain how it differs?
@ianlancetaylor Compared to https://github.com/golang/go/issues/76920, this proposal is different in that:
variable.Field syntax is always valid and has consistent semantics regardless of the field typev, ok = variable.Field syntax is always valid and has consistent semantics regardless of the field typeThis proposal doesn't mention comparability, but the assumed semantics are the same.
In the proposal text, I find writing product where current Go uses struct to be very confusing. Go is not going to replace the keyword struct with the keyword product. A language change proposal needs to start from where the language is today.
The introduction said:
Adjust the
productandsumkeyword syntax below for Go as needed. Obviously,productis alreadystructin Go. I use that syntax to hammer home how fundamental these types are.
I have updated the text to use "struct" instead of "product" where possible.
This feels less idiomatic to the language than #76920, though I do think pattern-matching could be expanded on as a dedicate proposal.