proposal: Go 2: refined generics design #39328
Comments
ianlancetaylor
added
generics
|
I don't think I really understand your proposal. At the very end you suggest that you may need something like Can you show how to write some of the examples at https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-contracts.md#examples using your proposal? Thanks. |
Sure. As far as I understand, it is not clear what the differences are between this proposal and the existing one (which I will call "current design" in this comment)? Of course, I would like to show a few points with examples that could be named major changes.
Current design advantages: 1.1. The reason of contracts is the author does not want explicitly list types, but wants to do describe them. 1.2. The second reason is there are to many combinations with types to include them to the standard library. Current design disadvantages: 1.1. Still author says we need something important like 1.2. Contracts act like interfaces, so why we do not just use the interfaces? In the current design there is an example: contract stringer(T) {
T String() string
}This is such a strange syntax for me, why no to write just like this? type Stringer interface{
String() string
}Sure, You can say You can combine contracts in such way as bellow and interfaces are not suitable for this: contract NumericAbs(T) {
Numeric(T)
T Abs() T
}But instead this is what I propose: type Numeric int8 | int16 | int32 | ... // Still I think this type can be defined somewhere, like in package `generic` or maybe built in to the language, since it is an important case too.
// generic interface Abser when instantiated (specialized) with type `int32`, for example, becomes an interface matching any type with method `Abs() int32`
type Abser(type T Numeric) interface{
Abs() T
}Usage: type X struct{}
func (X) Abs() int {
return 0
}
func main() {
// Abser(int) means interface{Abs() int}
var x Abser(int) = X{}
fmt.Println(x.Abs())
}
So, this explicit code having explicit type X int32 | int64
func Add(type T) func(a, b X) X {
switch T {
case int32:
// 1
return func(a, b int32) int32 {
return a + b
}
case int64:
return func(a, b int64) int64 {
return a + b // the issue is we have the same code for each type, though it could be different.
}
}
}Usage: func main() {
// add is now the function 1
add := Add(int32)
fmt.Println(add(4, 6))
}Turns into this code having the same operations implicit: type X int32 | int64
func Add(type T) func(a, b X) X {
// := here is not an assignment operator
// it is a "type instantiation" operator
// which means it takes generic type T and returns a certain type of it at compile time when the Add function is specialized
// so, Z is holding either `int32` or `int64` but not a generic type int32 | int64
// and compiler can check that both `int32` and `int64` types allow `+` operation no matter what X is
switch Z := T {
return func(a, b Z) Z {
// if Z is int32 then + is the int32 + int32 operator
// if Z is int64 then + is the int64 + int64 operator
// since we need expression Add(int32) return a specific function func(a, b int32) int32
// but not a func(a, b T) T which i think must be impossible
return a + b
}
}
}Usage: func main() {
// add is now a func(a, b int32) int32 {
// return a + b
// }
add := Add(int32)
fmt.Println(add(4, 6))
}A bigger and more complicated example. Before: // OrderedNumeric matches numeric types that support the < operator.
contract OrderedNumeric(T) {
T int, int8, int16, int32, int64,
uint, uint8, uint16, uint32, uint64, uintptr,
float32, float64
}
// Complex matches the two complex types, which do not have a < operator.
contract Complex(T) {
T complex64, complex128
}
// OrderedAbs is a helper type that defines an Abs method for
// ordered numeric types.
type OrderedAbs(type T OrderedNumeric) T
func (a OrderedAbs(T)) Abs() OrderedAbs(T) {
if a < 0 {
return -a
}
return a
}
// ComplexAbs is a helper type that defines an Abs method for
// complex types.
type ComplexAbs(type T Complex) T
func (a ComplexAbs(T)) Abs() T {
r := float64(real(a))
i := float64(imag(a))
d := math.Sqrt(r * r + i * i)
return T(complex(d, 0))
}Usage? If I got it right, the usage is: func main() {
// OrderedAbs is still a generic type holding a value -5?
// Or is it now an int variable?
var a OrderedAbs = -5
// what method Add of what type do we call?
a.Add()
}After: Abs defined as a function (not a method): // ordered is a generic type which can be specialized as int, int8 and so on
type ordered int | int8 | int16 | int32 | int64 | uint | uint8 | uint16 | uint32 | uint64 | uintptr | float32 | float64
type complex complex64 | complex128
// Numeric is a generic type which can be specialized to any type of ordered or to any type of complex
type Numeric ordered | complex
// Abs is a function calculating an absolute value
// it has one implementation for real numbers
// and a completely different one for complex ones
// while having absolutely the same simple interface and usage
func Abs(type T Numeric) func(T) T {
switch T {
case Z := ordered:
// 1
return func(a Z) Z {
if a < 0 {
return -a
}
return a
}
case Z := complex:
// 2
return func(a Z) Z {
r := float64(real(a))
i := float64(imag(a))
d := math.Sqrt(r * r + i * i)
return Z(complex(d, 0))
}
}
}Usage: func main() {
var a int = -5
// abs is now a function 1 from the previous code
// having func(int) int signature
abs := Abs(int)
fmt.Println(abs(a)) // prints 5
}Shorter version: func main() {
var a int = -5
fmt.Println(Abs(int)(a)) // prints 5
}Even shorter version with inference from the compiler: func main() {
var a int = -5
fmt.Println(Abs(a)) // prints 5
}I do not think it is okay to define methods using contracts, since it allows to define a method for If You want to define a method - it must be defined for a specific type: type Number int
func (a Number) Add(b Number) Number {
return a + b
}Since it must be a concrete implementation for a concrete type fitting a certain interface. If You want The issue You need to "specialize" somewhere - You need to call this method Add from a certain type and pass a type that You want to specialize with, but how can you call a method of a type that is not specialized? If we have a type If You do not "specialize" - You are risking to generate too many unused code, since who knows where it can be used. // ComplexAbs is a helper type that defines an Abs method for
// complex types.
type ComplexAbs(type T Complex) TSo, if it is a helper type, it is not an But what if You want add a variable of that type to an Here is a simple case: type MyType int
func main() {
fmt.Println(MyType(2) + int(2))
}But in case MyType is a "helper" type but generic, how the conversion must look like? That is why I did my example using a function not a method. Still it is possible to design some imaginary syntax. These are the tricky examples I want to use as an arguments for my design. I will provide a few more in a short time just to show some more easy cases. |
Dot Product ExampleBefore: // Numeric is a contract that matches any numeric type.
// It would likely be in a contracts package in the standard library.
contract Numeric(T) {
T int, int8, int16, int32, int64,
uint, uint8, uint16, uint32, uint64, uintptr,
float32, float64,
complex64, complex128
}
func DotProduct(type T Numeric)(s1, s2 []T) T {
if len(s1) != len(s2) {
panic("DotProduct: slices of unequal length")
}
var r T
for i := range s1 {
r += s1[i] * s2[i]
}
return r
}Usage? After: // Numeric is a generic type allowing to be specialized to any of the listed types
type Numeric int | int8 | int16 | int32 | int64 | uint | uint8 | uint16 | uint32 | uint64 | uintptr | float32 | float64 | complex64 | complex128
// DotProduct is a generic function definition returning a concrete function for each type
// function(s1, s2 []int) int for ints
// function(s1, s2 []float32) float32 for floats
func DotProduct(type T Numeric) func(s1, s2 []T) T {
switch T {
case Z := T:
return func(s1, s2 []Z) Z {
if len(s1) != len(s2) {
panic("DotProduct: slices of unequal length")
}
var r T
for i := range s1 {
r += s1[i] * s2[i]
}
return r
}
}
}Usage: func main() {
dotProduct := DotProduct(int)
fmt.Println(dotProduct([]int{1,2,3}, []int{5,6,7})) // prints some number which is a dot product
}We can make compiler infer many things, but I think explicit code is better for illustration purposes. Yeah, I still can make minor mistakes since it kinda hard to write code without any suggestions and checks, but I hope it made it clear. Did I? |
|
Could also the guy who put a dislike comment out issues he found, please. |
|
Thank You for the link, I know the sum types proposal is there, but I believe there is a slight difference. I do not get what is the exact question. Do You ask what is the difference? It is very tricky to understand and answer this question, but let me try. Sum types are much like a unions in C: #19412 (comment) Generic type is not a type at all, so a variable of "generic type" cannot hold a value. Instead a generic type is an expression evaluating to a type. Example 1My Proposaltype X int32 | int64 // generic type X that can specialize to int32 or int64
func main() {
// You cannot write it like this
// ok, the compiler can conduct some inference, but let's assume it is not there for this demo
var x X = int32(5)
// instead You need to write it like this and z becomes exactly an int variable
var z X(int32) = int32(5)
z = int64(17) // error: z is an int32, this doesn't work
}Sum Type ProposalA sum type can handle a value of any of its types: type X int32 | int64 // creates a type taking 64-bits in memory
func main() {
var x X = int32(5) // ok
x = int64(17) // still ok
}Example 2My Proposaltype X int | int32
func main() {
var x X // doesn't work
var x X(int) // ok
fmt.Println(reflect.TypeOf(x)) // prints int
}Sum Type Proposaltype X int | int32
func main() {
var x X // ok
fmt.Println(reflect.TypeOf(x)) // prints X?
}If the sum proposal is accepted, we can change the syntax of generic types to avoid any conflicts. I think also sum type cannot be implemented without a compiler tweaking and a real language change. Since it needs to hold somewhere a real union and manage it. My proposal can be implemented with a not complicated codegen and adds almost no overhead. It can be really considered a syntax sugar allowing type parametrization. I hope I made it clear, did I answer Your question? |
|
Can you show us how you would write something like the |
Ordered Map ExampleBeforeThe link: https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-contracts.md#containers CriticismI still think the generics are not good for defining functions with receivers. In my opinion it is a bottleneck and a weak place in the current design. And I also believe "generic functions having a receiver" is a whole separate proposal with a really different implementation. Mostly, because we cannot define a function having a primitive type receiver (like type T // generic type
func (t T) Do() {
fmt.Println(t)
}
func main() {
x := 6
x.Do() // how does this work?
y := "hello"
y.Do() // should this work too?
}The second reason is, as I said in the previous comments, we do not really know what function we are going to call. // file /a/a.go
package a
type T
func (t T) Do() {
fmt.Println("hello")
}
// file /b/b.go
package b
type T
func (t T) Do() {
fmt.Println("world")
}
// file /main.go
package main
func main() {
x := 5
x.Do() // hello or world? how did we import type T?
}So, You can say we can do this: func main() {
var x a.T = 5
var y b.T = "test"
x.Do() // "hello"
y.Do() // "world"
}But no, we cannot, because of this: func Check(x a.T) {
fmt.Println(x)
}
func main() {
var x a.T = 5 // x is kinda an int
var y b.T = "test" // and y is kinda a string, right?
x.Do() // "hello" // but how can we call a method of an int? so it is a variable of type a.T, right?
y.Do() // "world" // so this is a b.T
Check(y) // and this must fail, since it expects an a.T and we pass a b.T?
}The And the most important argument is such a feature involves too much code generation. We cannot expect the compiler will just substitute all T's with the type provided (or not) later somewhere. Methods are a part of a type. We define them and do not care if someone will use them, they just exist. What if we define a method And I understand this can be tweaked and checked somehow by the compiler, and I understand such a problem can potentially be solved just like it is solved in some languages allowing contracts. Still I am afraid it is too complicated and costly both for implementation and use. I also may be wrong, this is just my honest opinion. It was freaking tricky to explain, hope my point is clear, useful and no one is offended. AfterBefore rewriting, I had to figure out the original problem. So, the problem is to write a map with a binary tree under the hood. I found one major issue with the solution from the example: it must be just a binary tree implementation, allowing finding a node just by its value. I mean, why to have So, this code from the example: type node(type K, V) struct {
key K
val V
left, right *node(K, V)
}Can be rewritten just like this: type node(type T) struct {
value T
left *node(T)
right *node(T)
}The next thing is we do not really need // file /tree/tree.go
package tree
type Node(type T) struct {
Value T
Left *Node(T)
Right *Node(T)
}
type Comparator(type T) func(T, T) int
func Find(type T) func(root *Node(T), value T, compare Comparator(T)) *Node(T) {
switch T {
// capturing type T, as I explained in examples bellow,
// so Z is a specific type, and the compiler can infer it
// after the specialization (instantiation)
case Z := T:
return func(root *Node(Z), value Z, compare Comparator(Z)) *Node(Z) {
currentNode := root
for currentNode != nil {
switch cmp := compare(value, currentNode.Value); {
case cmp < 0:
currentNode = currentNode.Left
case cmp > 0:
currentNode = currentNode.Right
default:
return currentNode
}
}
return currentNode
}
}
}
func Insert(type T) func(root *Node(T), value T, compare Comparator(T)) bool {
switch T {
case Z := T:
return func(root *Node(Z), value Z, compare Comparator(Z)) bool {
currentNode := Find(root, value, compare)
if currentNode != nil {
currentNode.Value = value
return false
}
// again, we can specialize generic type to a specific type
// only using a specific type as a parameter
// since value is Z (which is specific, inferred by the compiler)
// and Node(Z) is struct{Value Z; Left *Node(Z); Right Node(Z)}
// it is okay
*currentNode = Node(Z){Value: value}
return true
}
}
}
// file /main.go
package main
import "tree"
type KeyValue struct {
Key string
Value int
}
// Imagine we really want to compare just by the key length
func CompareKeyValueByKeyLen(a KeyValue, b KeyValue) int {
aKeyLen := len(a.Key)
bKeyLen := len(b.Key)
if aKeyLen > bKeyLen {
return 1
}
if aKeyLen == bKeyLen {
return 0
}
return -1
}
func main() {
var myTreeBasedMap tree.Node(KeyValue)
insert := tree.Insert(KeyValue)
// inserting a bunch of nodes
insert(myTreeBasedMap, KeyValue{"xxx", 5}, CompareKeyValueByKeyLen)
insert(myTreeBasedMap, KeyValue{"xxxxx", 17}, CompareKeyValueByKeyLen)
insert(myTreeBasedMap, KeyValue{"xx", -13}, CompareKeyValueByKeyLen)
find := tree.Find(KeyValue)
node := find(myTreeBasedMap, KeyValue{Key: "xx"}, CompareKeyValueByKeyLen)
fmt.Println(node) // should print {xx, -13}
}We can use closures in the func main() {
var myTreeBasedMap tree.Node(KeyValue)
insert := tree.Insert(KeyValue)(CompareKeyValueByKeyLen)
// inserting a bunch of nodes
insert(myTreeBasedMap, KeyValue{"xxx", 5})
insert(myTreeBasedMap, KeyValue{"xxxxx", 17})
insert(myTreeBasedMap, KeyValue{"xx", -13})
find := tree.Find(KeyValue)(CompareKeyValueByKeyLen)
node := find(myTreeBasedMap, KeyValue{Key: "xx"})
fmt.Println(node) // should print {xx, -13}
}Also we can use a // file /tree/tree.go
package tree
type Comparable(type T) interface{ Compare (T) int }
type Node(type T Comparable) struct {
Value T
Left *Node(T)
Right *Node(T)
}
func Find(type T) func(root *Node(T), value T) *Node(T) {
switch T {
case Z := T:
return func(root *Node(Z), value Z) *Node(Z) {
currentNode := root
for currentNode != nil {
switch cmp := value.Compare(currentNode.Value); {
case cmp < 0:
currentNode = currentNode.Left
case cmp > 0:
currentNode = currentNode.Right
default:
return currentNode
}
}
return currentNode
}
}
}
func Insert(type T) func(root *Node(T), value T) bool {
switch T {
case Z := T:
return func(root *Node(Z), value Z) bool {
currentNode := Find(root, value)
if currentNode != nil {
currentNode.Value = value
return false
}
*currentNode = Node(Z){Value: value}
return true
}
}
}
// file /main.go
package main
import "tree"
type KeyValue struct {
Key string
Value int
}
func (a KeyValue) Compare(b KeyValue) int {
aKeyLen := len(a.Key)
bKeyLen := len(b.Key)
if aKeyLen > bKeyLen {
return 1
}
if aKeyLen == bKeyLen {
return 0
}
return -1
}
func main() {
var myTreeBasedMap tree.Node(KeyValue)
insert := tree.Insert(KeyValue)
// inserting a bunch of nodes
insert(myTreeBasedMap, KeyValue{"xxx", 5})
insert(myTreeBasedMap, KeyValue{"xxxxx", 17})
insert(myTreeBasedMap, KeyValue{"xx", -13})
find := tree.Find(KeyValue)
node := find(myTreeBasedMap, KeyValue{Key: "xx"})
fmt.Println(node) // should print {xx, -13}
}Another trick is to use generic functions for a method implementations. It gets kinda tricky, but here is the code: // Tree definition
type Comparable(type T) interface{
Compare(T) int
}
type Tree(type T Comparable) interface{
Value T
Left() T
Right() T
Find(T) T
Insert(T) bool
}
// Map implementation
type KV struct {
Key string
Value int
}
func (a KV) Compare(b KV) int {
return 0 // imagine we are actually comparing it by the key
}
// MyMap becomes struct {
// Value KV
// Left *KV
// Right *KV
// }
type MyMap tree.Node(KV)
func (m MyMap) Value() KV {
return m.Value
}
func (m MyMap) Left() KV {
return m.Left
}
func (m MyMap) Right() KV {
return m.Right
}
func (m MyMap) Find(i KV) KV {
return tree.Find(KV)(m, i) // yeah, we are using it from our previously written package
}
func (m MyMap) Insert(i KV) bool {
return tree.Insert(KV)(m, i) // and again
}
func main() {
var myAwesomeMap Tree(KV) = MyMap{}
myAwesomeMap.Insert(KV{"a", 14})
myAwesomeMap.Insert(KV{"b", 25})
myAwesomeMap.Insert(KV{"c", -9})
myAwesomeMap.Find(KV{"c"})
}In this way we are implementing our map as a specific structure having some methods, but we kinda have a generic tree interface here and we are using generic implementations of the find and insert algorithms (which are specialized before the uses with a specific So, yeah, I guess, this approach still helps a user to write generic containers both in functional style (with plain functions and closures) and OOP (with objects and methods), while this design can be implemented in a simple pre-processor generating zero unused code. I did not show any example on Let me know if You need anything more, and please provide some feedback on the examples. |
|
One of the main reasons that people want generics is the ability to write container types like In all honesty it seems to me that the |
Basically we can think my proposal allows people to write generic functions like I totally understand and accept this downside of the proposal. But I also think it would be great if someone else also considered it. Or maybe someone has a better idea on "generic function with receiver" proposal. I guess it is up to You to decide whether to close this issue and decline the proposal or not. Thank You for Your time. |
Refined Generics Design
Hey, dear community. Here is my vision on generics.
Features
I believe I have got achieved this qualities with my design. Still I could make some mistakes. So here is what I at least aimed at:
Abstract
Contracts Concept
Current design is great. Still I believe the issue with the contracts concept is that they have too much granularity. My arguments are:
Contracts boil down to specifying what types do we basically support. So why not to specify them directly, not just by saying what operators do we want them to support?
What if we do want some function to be implemented only for, say,
int8andint32for some weird reason. Do the contracts help much?Golang has types that support several kinds of operators at once. But, for example, it doesn't have any type
bitwisethat has bitwise operators support only.That's to say, we cannot write such a code:
Defining a contract supporting bitwise operations means involving
int8,int16and so on.Proposed Design
Basically, we got two problems when we think generics are the solution. First one is when we need to convert an
[]intvariable to an[]interface{}one (or similar). The second is when we need to convert afunc(a int)variable to afunc(a interface{})one (or similar). Or vise-versa. Let's call these two processes "generalization" and "specialization" like in the previous design draft.So, we are introducing 6 new expressions to the language:
Generic function is a function having a generic parameter (like
t T). But it can have 0 parameters and be generic too. More precise definition and full syntax is on the next pointThe compiler can easily infer the type of
doIntFunction generalization is a separate expression in the language evaluating to a function. And it can also have a "switch by generic type" expression in it.
Do we really need to flip
type TintoT type? I guess no, since we've got no first-class types and do not support runtime specialization.When we write
type T- it really defines some internal type called T and parametrizes a type or function.When we write
T type- that means we have an argument of typetypewhich is kinda strange.Here is an example of function that uses a generic type, but it specializes it staying specialized too (and not generic).
There is no problem with defining a generic function with several parameters.
This design also compatible with functions having receivers. But it does not really make them useful:
What about interfaces?
But I do not really find generalized interface types that useful.
The syntax of all the things can be tweaked a bit, but I think it is a matter of taste:
The whole idea is that, You need specialize before use. If You want to use a generic type in a function - generalize the function too.
Conclusion
Does this generic concept solves "same api for all types" problem?
Well, yes and no. You still need to define different functions for each type, though the usage is simpler.
What You need is some kind of macro or codegen support, since
int + intis not the same expression asint32 + int32. And that is really a different problem not really related to generics.As a workaround an internal
addabletype can be introduced in the language, and aaddable + addableoperation can be defined.Conclusion
I believe this proposal brings generics syntax on a new level providing a new understanding and vision of it, while remaining familiar. Please, let's start a discussion, I would really appreciate any feedback!
The text was updated successfully, but these errors were encountered: