Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: Go 2: generics: use operators for meta typing #41449

Closed
markusheukelom opened this issue Sep 17, 2020 · 49 comments
Closed

proposal: Go 2: generics: use operators for meta typing #41449

markusheukelom opened this issue Sep 17, 2020 · 49 comments

Comments

@markusheukelom
Copy link

@markusheukelom markusheukelom commented Sep 17, 2020

The current proposal for generics is based on interfaces with added type lists. In this proposal I'd like to explore the possibility of using operators instead.

Rationale: compactness and orthogonality with interfaces.

My main argument is that generics should not allow you to do something you can already do with interfaces. For example, if interfaces can be used for meta typing you then have to decide whether to take io.Reader as a parametric type or as an argument type when implementing some function that reads data. In almost all cases it is hard to decide which option is objectivily better (if any), however the question would arise for a lot of functions. Therefore it is better not to provide the option.

Furthermore, interfaces are complicated enough as they are and deal mostly with dynamic (runtime) behavior. Overloading the interface concept to also express generic type constraints does not align very well with the Go adagium of "orthogonality" and can become confusing. I think it is therefore better to not use interfaces for generic type constrains.

Instead of using interfaces, we could use operators directly. This is compact and allows to write functions and types that can currently not be specified with intefaces (and vica versa). The drawback of this approach is that no methods can be called directly on variables of parametric types. However, that can always be alleviated by using a helper (generic) function or (generic) interface.

Proposed syntax:

func Min[T <](a T) T {} // specify a single required operator (less than)

func Max[T >](a T) T {}				

func Find[T ==] (values []T) int {}  // T must be comparable on equality
	
func Must[T =] (result T, err error) T {  // any type can be indicated with = (or &) as all types support assignment
	if err != nil {
		panic(err)
	}
	return result
}

type Bimap[K, V ==] struct {   // K and V must both support ==
	forward map[K][V]
	reverse map[V][K]
}

type ListNode[T =] struct {   // T can be any type
	prev, next *ListNode[T]	
	Value T
}

func Abs[T (<,-)] (a T) T {   // multiple required operators must be parenthesized. 
	var zero T
	if a < zero {
		return zero - a 
	}
	return a
}

func Abs2[T (<,(-))] (a T) T {   // unary versions of operators that also have a binary version must be parenthesized
	if a < zero {
		return -a 
	}
	return a
}

func Negate[T ((-))](val T) T {   // double parens because (-) would be a list with only the binary minus operator
	return -val
}

func New[T &](value T) *T { 
	return &value 
}

// Deref returns the value pointed by ptr or the zero value for T if ptr is nil.
func Deref[T =](ptr *T) T { 
	if ptr == nil {
		var T zero
		return zero
	}
	return *ptr 
}

type Arith[T =] interface {   // a generic interface to any scalar type (can be implemented for floats, complex, big.Float,Rational etc)
	Add(T, T) T
	Sub(T, T) T
	Mul(T, T) T
	Div(T, T) T
}
func Dot[T =](a, b []T, ops Scalar[T]) T {}

@ianlancetaylor ianlancetaylor changed the title Proposal/idea: generics: use operators for meta typing proposal: Go 2: generics: use operators for meta typing Sep 18, 2020
@gopherbot gopherbot added this to the Proposal milestone Sep 18, 2020
@gopherbot gopherbot added the Proposal label Sep 18, 2020
@gopherbot gopherbot added the Proposal label Sep 18, 2020
@ianlancetaylor ianlancetaylor added Proposal and removed Proposal labels Sep 18, 2020
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 18, 2020

One place where people want to use generics is in containers. For a simple example, people want to be able to write a linked list package that can store values of any type without unnecessary overhead. With the current generics design draft, that might look like https://go.googlesource.com/go/+/refs/heads/dev.go2go/src/cmd/go2go/testdata/go2path/src/list/list.go2 . How could that be done with this approach?

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 18, 2020

Instead of any you would use = to specify "any type" (because all types support the assignment operator). The rest stays the same:

type Element[TElem =] struct {
next, prev *Element[TElem]
  
  // The list to which this element belongs.
  list *List[TElem]
   
  // The value stored with this element.
  Value TElem
  }

For most generic types the constraint will be either = for all types or == if T is used as map key. I have included examples in my original post.

@deanveloper
Copy link

@deanveloper deanveloper commented Sep 18, 2020

In my opinion the syntax is a bit cryptic. (-) ideally should mean the same thing as -, not to mention that the only time that i can recall where the legality of binary/unary operators differ where both are defined is with string (where the binary operator is defined, but not the unary operator).

func ScanSqlResult[S .](row *sql.Row) (*S, error) { // S must support the lookup operator . and so is struct (this is useful for e.g. type safer ORM code)

This is not quite true - the . symbol is not an operator, but rather part of the Selector syntax which supports all types. Specifying that . only works for structs seems unintuitive to me.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 18, 2020

@susugagalala
Copy link

@susugagalala susugagalala commented Sep 19, 2020

Dunno why some downvoted without giving their reasons. I upvoted for 2 reasons: the proposer gave his honest (and I believe valid) take even if eventually his proposal would be rejected; the proposed syntax is clean albeit with some drawbacks - perhaps we could use a combination of operators for default and interfaces for others?

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 19, 2020

@deanveloper

You are right about the . "operator"; I will remove the example.

Regarding the (-) syntax: First note that the use case for the unary minus operator is rare. The only examples that I could come up with are Neg and Abs2. I considered having - imply both unary and binary but there's also the case of * which both binary multiplication and unary dereferencing operator. Because I think requiring the dereferencing operator or unary minus is so rare the double () syntax is better than a "this implies that" rule. But it's debatable and there's other options as well of course such as using -., etc.

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 19, 2020

@ianlancetaylor

Note that my proposal is to explicitly not support this as Go provides interfaces already for this:

// The caller can just construct the list with items an then call Stringify
// This aligns well with other "solutions" in Go where the  programmer is instructed to just write a simple for loop
func Stringify(list []fmt.Stringer) string {
	// ...
}

Note that this version is more general than the generic Stringify that you linked to: here the items in list can be of different underlying types while in the generic version they necessarily are of the same type. So in this case, allowing generics to specify methods would lead to a less general implementation (although possibly more performant) than what you can already do with interfaces.

Other arguments are in the original post. Of course, a generic solution with a helper function is still also possible:

func Stringify[T =](list []T, fn (val T) string) string {
	// ...
}
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 19, 2020

A slice of type []fmt.Stringer is not the same as a slice of type []T where T implements fmt.Stringer. There only way to convert the latter slice into the former is to write a loop. https://golang.org/doc/faq#convert_slice_of_interface

I agree that a helper function would work, but it's awkward. That seems to me that it might be a significant drawback to this proposal. Perhaps I am mistaken.

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 21, 2020

@ianlancetaylor

I may also be mistaken of course, I just hope to add to the discussion and understanding of what generics in Go should do.

What I meant is that the abstract functionality provided by interfaces is inherently more powerful than that of a generic list []T:

func Archive1(items io.Reader...) {
	// ...
}

buf := &bytes.Bufffer{}
file, _ := os.Open(...)

Archive1(buf, file)	// ok 

func Archive2[T io.Reader](items T...) {
	// ...
}
Archive2(buf, file)	// invalid

Interfaces are more powerful than generics in most cases because they can operate on heterogeneous types.

Therefore I think the interface version Archive1 should be preferred over Archive2[T]. The argument for Archive2 just to save writing a for loop for the uncommon case where []T needs to be converted to []io.Reader is not too convincing.

There are exceptions where using []T is better, however a solution with a helper function is not awkward but quite natural (and quite common):

func SortList[T =](list []T, less func(a, b T) bool) {
	// ...
}

This more succinct and more direct than:

type Lesser[T] interface {
	Less(other T) int // should return -1 if less than, 0 on equal and 1 if greater than
}

func SortList[T Lesser[T]](list T[]) {
	... 
}

Which requires defining an extra interface type and also requires the addition of Less as a method on T. Other examples are Map/Reduce. Of course the first example can be written in the current proposal; the point is that you don't need an interface meta type here.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 21, 2020

Just to be clear, it seems to me that the current generics design draft permits writing any kind of code that is permitted by this proposal, albeit with a different syntax. The current design draft also permits writing other kinds of code, that cannot be written with this proposal. Would you agree with that?

@deanveloper
Copy link

@deanveloper deanveloper commented Sep 21, 2020

How well would this support something like a Graph structure, where there is a relationship between the type parameters?

type Node[TEdge =] interface {
    Edges() []TEdge
}
type Edge[TNode =] interface {
    Nodes() (from, to TNode)
}

type Graph[TNode ??, TEdge ??] struct { ... }

There doesn't seem to be a good way to explain the relationship between TNode and TEdge in the Graph interface from what I can tell.

As for some feedback, I think this proposal offers a solution which really is trying to accomplish adding "operator interfaces" (allowing interfaces to describe operations on types), but doing it by tightly coupling it with the idea of type parameterization, when they are actually two entirely separate concepts. Because this proposal couples these ideas together, it would make it very hard to add more features to either of these concepts individually.

The current generics draft introduces these two concepts as two separate ideas. "Operator interfaces" are instead introduced as type lists, and type parameterization is introduced as such. For instance, consider the function func Abs(i Integer) uint64. There are no relationships between the parameters/return values, so I shouldn't need to use type parameterization. All I want to do is make sure that I can compare i to zero, and negate i if needed. However in this proposal, I would instead do func Abs[T (<,(-))](i T) uint64, which in my eyes is a bit of a cryptic syntax, as well as forcing me into using type parameterization where I wouldn't need it.

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 21, 2020

@deanveloper

Regarding the graph structure, that's not supported (by intention), because you can use functions or interface already. I think a simpler approaches that provide the same functionality is better because it is so much shorter, something like:

// ShortestPath returns the shortest path between two nodes. 
// Edges must the nodes that can be reached from each node.
func ShortestPath[Node ==](from, to Node, edges func(Node) []Node) []Node {
	// ...
}

Regarding your feedback. I am not trying to accomplish "operator interfaces" I think (I am not entirely sure want you mean with it). I started out by looking at what the minimal possible thing is that is needed to support T in any type: thats assignability ('any' currently) and comparison (on equality, for map keys)). With those you can express any generic type (except functions and methods). These are expressed in Go using = and == which are also short and so are the most direct way of expressing want you need. The next thing is Min, Max functions, etc. These can also easily be supported by allowing any operator instead of just = and ==, and also a list of operators. This is all still orthogonal to current expressibility in Go. If you want to be able to call methods on T, there's interfaces and functions already. Yes, this excludes examples like the graph example, but I couldn't find any convincing example for which it would be needed and for which there's no alternative with helper functions or generics. Maybe that's indeed incorrect, I'd love to see a convincing country example (that does not resemble C++ Boost or STL implementation).

Using operators also does not need to make it very hard to add more features. For example you could add syntax to the language that give a name to the meta type constraint:

meta E ==  // any type that implements ==
meta Arith (+,-,*,/)

func Dot[T Arith]()

I am not saying that we should; it is not part of my proposal. Just an example of how it could be extended. If we want you can extend that and allow interfaces as well:

meta S fmt.Stringer // any type that implements the methods in fmt.Stringer
meta S2 (fmt.Stringer,+,-) //  any type that implements the methods in fmt.Stringer and supports +,-

Although I think this is not a good idea, for reasons explained earlier. But it's not hard to extend the syntax. In fact, I think that if you want to allow to call methods on T, you should also be able to access fields etc.

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 21, 2020

@ianlancetaylor

Just to be clear, it seems to me that the current generics design draft permits writing any kind of code that is permitted by this proposal, albeit with a different syntax.

Almost, but this proposal does not introduce 'any', 'comparable', type lists in interfaces and a multitude of additional rules on interfaces (can't call method expressed type list types only, comparable on being able to use as normal interface type, etc etc). It also does not convolute the concept of interface.

Almost, because I think my proposal would allow to make functions that operate on untyped constants which could be useful:

func Max[T <](a, b T) T
var my float64 = Max(math.Pi, math.E)   // Pi and E are not converted to float64 by Max

That's not possible with the current generics design without additional syntax. I also think that allowing parametrized methods are easier to allow, but I am not sure.

The current design draft also permits writing other kinds of code, that cannot be written with this proposal. Would you agree with that?

Yes, and vice versa (see above). I am not sure it is fruitful to compare proposals on syntax that they are being able to generate though. On a type safety level they can express the same functionality, although indeed the current generics proposal can write a succincter Stringify.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 21, 2020

On a type safety level they can express the same functionality.

That is exactly what I am questioning. It seems to me that the current generics design draft permits expressing functionality that this proposal does not permit. This is not a question of syntax, it's a question of semantics. Specifically I am thinking about examples like Stringify or the Graph examples mentioned above. Yes, of course you can write those in other ways by passing function closures or something. I believe that my basic point remains true: the design draft permits expression functionality that this proposal does not. That doesn't mean that this proposal is bad or wrong. I'm just trying to precisely clarify what is being suggested here.

The untyped Max is an interesting example but it would require additional language mechanisms that don't currently exist. Right now untyped constants can only be used in constant expressions. An untyped Max would also require untyped variables. It's not immediately clear to me how that would work. However it works, it appears that any implementation would absolutely require a specific implementation--monomorphization aka stenciling, and it would also require complete inlining of any function instantiated with untyped values. At least, I don't immediately see how to do it any other way.

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 22, 2020

@ianlancetaylor

Well, your basic point is true of course but it's a bit of a moot point because I stated that exactly in my proposal:

My main argument is that generics should not allow you to do something you can already do with interfaces.

You may disagree with that of course (and to be honest I would be very interested in opinions/convincing examples from anyone, I could be very wrong).

You are also absolutely right that you can't do Stringify[T](list []T) exactly with current go or with this proposal. But the majority of applications of interfaces are things linke iotuil.ReadAll(r io.Reader). But stating only that makes it seem that you flag this proposal as "not a good idea" just because of this, and it makes me think that my main point is missed.

Of course I might be very wrong and the use case for the Graph example and the Stringify example prove to be strong use cases. However it seem to me they are exotic wrt to at least the Go standard library. Especially the Graph example looks overly complex for what it achieves? Do we want that? Do we want people to write C++ Boost like libraries in Go? And if we allow method calls, what about calling free functions on T and accessing fields? Why the cut-off at methods? I think a convincing example to be able to access fields in generic code is the Sibling function that I mentioned earlier. This function cannot be written with the current generic proposal (nor the one in this issue).

// package bintree

func Sibling[Node ??](node *Node) *Node {
   if node.Parent == nil {
        return nil
   }
  if node.Parent.Left == node {
       return node.Right
  }
  return node.Left
}
func SearchDepthFirst[Node ??](node *Node, fn (*Node) bool( { ...}
// etc

This example convinces me because writing getter/setters accessor for every field seems silly if used in generic code especially combined with perfomance arguments.

Maybe this proposal is not a good idea at all. It could also be that's its a matter of taste and people just like to write generic code instead of using interfaces. I hope you and others will consider my arguments against overloading interfaces with applications to generics. I am a bit worried for fancy coding syndrome wrt to generics and the extra design choice you would have to make when writing a functions like iotuil.ReadAll(r io.Reader), i.e. take [T io.Reader] or (r io.Reader) . Maybe that worry is ungrounded.

Thank you for your notes on the Max wrt untyped constants. I am quite out of my depth on that area, but I agree inlining is indeed looks like to only way to realistically do it.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 22, 2020

My main argument is that generics should not allow you to do something you can already do with interfaces.

You may disagree with that of course (and to be honest I would be very interested in opinions/convincing examples from anyone, I could be very wrong).

I would agree with a slightly different statement: there is no reason to use generics to do something that you can already do with interfaces. But you seem to be saying that it is important that it should not be possible to use generics do things that can already be done with interfaces. I don't agree with that as a goal. There is no reason that generics should permit code that can already be written with interfaces. But I see no reason to go out of our way to ensure that generics cannot be used to write code that can already be written with interfaces. Among the important things about generics is that they are clear and straightforward, and that they are as orthogonal as possible to other language constructs. Ensuring that they cannot be used where interfaces can be used is not a priority.

Of course I might be very wrong and the use case for the Graph example and the Stringify example prove to be strong use cases. However it seem to me they are exotic wrt to at least the Go standard library.

This is close to a circular argument. The Go standard library was written in a language that doesn't have generics, so naturally it doesn't use generics. When we present a use case in which the Go standard library could use generics, it doesn't make a lot of sense to say that it doesn't fit the Go standard library because the Go standard library doesn't use generics. The whole point is to change the Go standard library to use generics. Now, of course, it may be a bad idea for other reasons. But this reason isn't one of them.

And if we allow method calls, what about calling free functions on T and accessing fields? Why the cut-off at methods?

You can already call free functions on variables of type T. Perhaps I misunderstand your point.

Methods are a general concept in Go that apply to all types, unlike struct fields. I'm not opposed to a generics proposal that permits accessing fields with known names and types. I agree that the current design draft doesn't support that.

I agree that your Sibling example can't be written using the generics design draft. But I'm not clear on why that matters. That kind of code is only useful if there are multiple different data structures with Parent, Left, and Right fields. If we have generics, it seems to me more likely that people would write a generic data structure with those fields. Or if we are looking for something more like the Graph example, it doesn't seem unreasonable to require Parent, Left, and Right methods.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Sep 23, 2020

Using your proposal, how would you express a generic function that increments a generic numeric integer argument by a given constant value, say 1234, and then returns that incremented value? Specifically, how would you express that you can't provide a byte argument because 1234 overflows byte? This is one of the problems one will need to address when constraining generic functions with operators, at least for Go.

Along similar lines, if one writes a generic function that uses * (multiplication) and down the road it turns out that the implementation can be made more efficient via a clever use of + (addition), would it be possible to change the implementation even if one had not foreseen the use of +; or would it require an API change?

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 23, 2020

@griesemer

Using your proposal, how would you express a generic function that increments a generic numeric integer argument by a given constant value, say 1234, and then returns that incremented value? Specifically, how would you express that you can't provide a byte argument because 1234 overflows byte?

func Inc[T +](a, b T) T {
	return a + b
}

func main() {
	var q byte
	const a = 1234
	Inc(q, 1234) // invalid: constant 1234 overflows byte
	Inc(q, a) // invalid: constant 1234 overflows byte
}

Maybe I am misinterpreting your question though: the code above expresses your requirement of "not being able to pass 1234 as a byte const", however it did not need to use type constraints for it (nor couldn't). It's already checked by Go on the call site.

(Note: I am assuming here that T=byte can be inferred from q with a being untyped. If that is problematic Inc[byte] must be used at the call site, but it's not related to your question I think. )

Along similar lines, if one writes a generic function that uses * (multiplication) and down the road it turns out that the implementation can be made more efficient via a clever use of + (addition), would it be possible to change the implementation even if one had not foreseen the use of +; or would it require an API change?

No, it would require an api change. If the api was SomeFunc[T *]() it will need to be changed to SomeFunc[T +](). I am not sure why that would matter that much though, all types that support * also support +.

Edit:

Regarding the first example, I think you meant this:

func Inc[T +](a T) T {
	return a + 1234
}

There is indeed no way in my proposal to specify that T cannot be a type that cannot store 1234. I also don't see an obvious solution, expect for disallowing constant integers in generic functions that are outside the range of the smallest int (byte). That might not be entirely unreasonable though.

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 23, 2020

@ianlancetaylor

Among the important things about generics is that they are clear and straightforward, and that they are as orthogonal as possible to other language constructs.

I agree, that's the reason I wrote this proposal. Would you agree that the current generic proposal is not as orthogonal as possible to other language constructs, especially with respect to interfaces?

@deanveloper
Copy link

@deanveloper deanveloper commented Sep 23, 2020

Would you agree that the current generic proposal is not as orthogonal as possible to other language constructs, especially with respect to interfaces?

I am still confused about how the current generics draft is not orthogonal to interfaces. The draft integrates with interfaces, but any features that are provided by interfaces are provided by interfaces, not parametric types.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Sep 23, 2020

Regarding your reply: Yes, I indeed meant

func Inc[T +](a T) T {
	return a + 1234
}

Basically, what you are saying is that one cannot type-check this function independently from a call site (which may not yet exist if this is a library function). It's not just bytes. What if the constant is 1000000? What if it is negative and we have uint types? Etc.

Also, changing an implementation such that it uses + rather than * (or - rather than +!) is not unusual and shouldn't require an API change. It also shouldn't require the author to anticipate such a change and require all "possibly needed operators" to be listed in the API.

These are some of the reasons why the current generics design draft doesn't try to use operator methods in its constraints. It seems that your proposal has all the problems of operator methods.

@changkun
Copy link
Contributor

@changkun changkun commented Sep 23, 2020

Why does no one mention the relation to operator functions? My impression is that supporting operator functions solves the issue generally. One can simply put the operator functions into a constraint. For instance:

type Int int

func NewRandInt() Int {
    return rand.Intn(100)
}

func (a Int) + (b Int) Int {
    return int(a) + int(b)
}

type Additive [T any] interface {
    T + (T) T // + operator function
}

func Add[T Additive](a ...T) T {
    switch l := len(a); l {
    case 0:
        return 0
    case 1:
        return a[0]
    default:
        var sum T
        for i := 0; i < l; i++ {
            sum = sum + a[i] // VALID   because +  operator function is in the Additive constraint
            // sum += a[i]   // INVALID because += operator function is not in the Additive constraint
        }
        return sum
    }
}

// Usage

a := NewRandInt()
b := NewRandInt()
Add(a, b) // VALID: Add[Int](a, b), Int implementes + operator function
@griesemer
Copy link
Contributor

@griesemer griesemer commented Sep 23, 2020

@changkun You mean "operator methods". But operator methods have the problem discussed here.

@changkun
Copy link
Contributor

@changkun changkun commented Sep 23, 2020

@griesemer I am so sorry that I somehow missed your message directly above mine. Thanks for pointing out. But I do have some further questions:

one cannot type-check this function independently from a call site

Why operators become an issue in type-checking when they are treated as method names eventually (type Int implements + method, equivalent to type Int implements Add method)?

changing an implementation such that it uses + rather than * (or - rather than +!) is not unusual and shouldn't require an API change

A generic implementation can only use methods from a constraint. Why shouldn't we need an API change? Could you maybe give some more detailed examples of the problem?

It also shouldn't require the author to anticipate such a change and require all "possibly needed operators" to be listed in the API.

"possibly needed operators" seems equivalent to "possibly needed methods," why are they be treated differently?

@griesemer
Copy link
Contributor

@griesemer griesemer commented Sep 23, 2020

The issue is not about + vs Add, the problem is related to the use of constants in the generic code. If the API says the argument type needs to provide + (or Add, same thing), and the type byte is provided, the API is satisfied. Yet, if inside the generic function I add the value 1024 to a value of that generic type (in this case byte) what should happen? In regular Go, I cannot write x + 1024 if x is of byte type because 1024 overflows byte's range. That is, if we want to preserve regular Go behavior for generic functions, we need to express somehow in the API that the argument type not only supports +, but also that it must be "big enough" to handle the constant 1024. Otherwise we cannot type-check the function independent of the invocation because we don't have any information about the type parameter besides that it supports +.

Regarding the * vs + problem: If I write a generic function

func double[T *](x T) T { return 2*x }

and later decide that x+x runs faster on my machine than 2*x, then I will need to change the function signature:

func double[T +](x T) T { return x+x }

even though the effect of the function didn't change. Sometimes such changes come about from refactoring. We don't want to need the API to change in such cases (and possibly break client code).

The current generics design draft doesn't have any of these problems because no operators are specified, only types (in an interface's type list). Given

func double[T interface{type int}] { return 2*x }

one can use any operation defined on an int type inside the double function. I can also use any constant that is accepted by an int type. Etc.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Sep 23, 2020

PS: Worse, what if the generic function requires + (or Add) in the signature, the function internally does x + 1 (works with any numeric type) and then the type argument is string?

@changkun
Copy link
Contributor

@changkun changkun commented Sep 23, 2020

we cannot type-check the function independent of the invocation because we don't have any information about the type parameter besides that it supports +.

Indeed this is an issue using operators for meta typing but still seems fine in operator methods because all applicable types are declared in the constraint.

and later decide that x+x runs faster on my machine than 2*x, then I will need to change the function signature

This seems natural, if the implementer decides to use + other than *, it means the implementer is expecting a new method from its constraint. Besides, such a change will only appear in custom types.

what if the generic function requires + (or Add) in the signature, the function internally does x + 1 (works with any numeric type) and then the type argument is string?

OK. This is a fair point because it will leads to the discussion that Go has no function overloading and SFINAE support eventually.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 23, 2020

Would you agree that the current generic proposal is not as orthogonal as possible to other language constructs, especially with respect to interfaces?

In a programming language orthogonality doesn't mean that there is only one way to do something. It means that there are no restrictions on how different concepts can be combined. See https://en.wikipedia.org/wiki/Orthogonality_(programming) .

That said, Go is not a perfectly orthogonal language. And the fact that in the current design draft interface types with type lists can only be used as type constraints is a failure in orthogonality. But the fact that interface types in general can be used as type constraints is, I think, reasonably orthogonal. We are adding another layer of meaning to interface types, but it is a layer consistent with what interface types already mean.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 23, 2020

Let me add something about the larger point here. In Go, interface types are already a form of generics. I mentioned that https://blog.golang.org/why-generics, and I explained why I don't think that is sufficient. Perhaps that will help explain why I think that the facts that you are pointing out are not a significant problem with the generics design draft. Thanks.

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 24, 2020

@griesemer

If the API says the argument type needs to provide + (or Add, same thing), and the type byte is provided, the API is satisfied. Yet, if inside the generic function I add the value 1024 to a value of that generic type (in this case byte) what should happen?

I fully understand the concern. Let me try to address them.

To use numerical constants, you must require at least (+,-); to use negative constants requires at least (+,-,(-)).

Regarding the 1024/1000000 example: what I meant was even under T (-,+,(-)), the allowed constant range that you can use is [-127,127] , because this is guaranteed to fit in any integer (likewise [0,255] for R (-,+)). To me that makes sense: writing a function AddMillion that guarantees no overflow would be not possible to express for the reason that T is abstract and so only 127 can be maximally guaranteed for T for the API. However, it can be still written if the guarantee is removed and just documented:

// AddMillion adds 10^6 to a. If T cannot store millions, the result may be incorrect.
func AddMillion[T (-,+,*)](a T) T {
	var ten T = 10 // valid becaulse < 128

	thousand := ten * ten * ten
	million := thousand * thousand
	return a + million
}

I don't think this is entirely unreasonable: many functions say something like 'if value is not a pointer the function panics`, etc.

(For floats there is no issue I think (not sure) because var m float64 = math.Pi is currently valid even though float64 cannot represent math.Pi exactly?).

That being said, another solution is of course to allow both (or either) operators and basic types as constraints. func MyC[T (complex64,complex128)](). I am cheating here because it's not part of my proposal, but maybe a logical and useful correction. The basic type is also allowed to be the underlying type of T. Operators would be still need because of = and ==, and very handing for '<' and math functions that don't use constants.

Please note that I don't know all the details of Go, although I try to, and so there may be more concerns that I am no aware of. Thanks for the explanations.

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 24, 2020

@ianlancetaylor

Thanks for the links and the explanations. My wording and use of "orthogonality" maybe didn't help. Please don't think I am just trying to bash the current proposal.

I kindly ask you to help me with the following worry that I have. If you have addressed it already somewhere, feel free to just provide a link.

In Go, interface types are already a form of generics.

I agree and it was the basis for me to write my proposal. My main worry is this:

type interface Reader {
	Read(p []byte) (int, error)
} 

func ReadAll1(r Reader) ([]bytes, error) {
	// ..
}

// and

func ReadAll2[T Reader](r T) ([]bytes, error) {
	// ..
}

I honestly don't know which would be better or how to chose which version to write. Yet, I write these kinds of functions quite often. So it adds a design question (that I don't know the answer to) to my daily work. I didn't have this question before. Now I have it, and I don't know the answer. I will default to the interface version, but many others may uses the generic version. That would make their code harder to read for me and vice versa.

The question is: can you explain me which one to chose here? (And why?). That would certainly take away my concerns. I have some other concerns, like the Graph example being too clever, that might be unjustified, but the above is my main concern.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Sep 24, 2020

@markusheukelom This is a great question. We absolutely need to develop good conventions and "best practices" around the use of generics.

I'll try to answer for your specific example: I believe in this case ReadAll1 (no generics) is the correct choice because of the following reasons:

  • There is no improvement in static type safety at the call site with the generic version: The results are fixed (don't depend on the argument type), both for the ReadAllX functions and the Read method. The provided reader may be nil in the ReadAll1 case which might lead to a panic inside that function, but note that ReadAll2 could be instantiated with a pointer or interface type, too, and then have the same problem.

  • There is (likely) no improvement in memory layout/use with the generic version: There is a single reader to pass, and while it may need to be packed into an interface, that cost is minimal.

  • There is (likely) no improvement in performance with the generic version: This makes some assumptions about the cost of a Read, but its likely that the cost of performing the Read dwarfs the cost of making the Read method call via the interface compared to having a (possibly) direct call of Read in the generic version.

On the other hand, there is a cost of having a generic version for each type of Reader, depending on how the compiler translates this code.

(Note, this specific situation may be a case where a compiler might choose to implement the generic version like the non-generic version.)

In summary, if the generic version doesn't improve the code along the axes of static type safety, memory use, and performance, choose the non-generic version.

Here's another way of looking at this: Generics are essentially a "glorified" version of macros. Would you use a macro in this case (because it might give you a significant benefit)? I think the answer would be a clear "no".

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 25, 2020

@griesemer

Thanks for this. I believe the arguments you provide would actually slightly favor the generics ReadAll version:

There is no improvement in static type safety at the call site with the generic version: The results are fixed (don't depend on the argument type), both for the ReadAllX functions and the Read method. The provided reader may be nil in the ReadAll1 case which might lead to a panic inside that function, but note that ReadAll2 could be instantiated with a pointer or interface type, too, and then have the same problem.

This argument seems void as it can be used for both versions.

There is (likely) no improvement in memory layout/use with the generic version: There is a single reader to pass, and while it may need to be packed into an interface, that cost is minimal.

This actually says that the generic version has possibly (although unlikely) better memory layout/use, and has zero packing costs (because there is no packing), while the interface version would always has non-zero packing costs (even if minimal).

Plus, as you say lower in your post, the compiler can always choose to implement with the non-generic version if it wants. So this seems to favor the use of the generics version.

There is (likely) no improvement in performance with the generic version: This makes some assumptions about the cost of a Read, but its likely that the cost of performing the Read dwarfs the cost of making the Read method call via the interface compared to having a (possibly) direct call of Read in the generic version.

This actually says that the generic version has potential improvement in performance (although unlikely), and the non-generic version is potentially (although not likely) slower. But hey it doesn't matter: the compiler can always choose to implement with the non-generic version if deemed better. So the programmer should just always use the generic version.


I would personally add the argument that the non-generic version is far more readable and therefore outweighs the unlikely added costs. Maybe that tips the scale towards the interface version, at least for some people, I don't know. In either case, it's very likely that a schism will develop under go programmers.

(Btw I do believe I have a possibly good argument for why Stringify should not be generic: the interface version has the added benefit that it works on lists of heterogeneous underlying types. Maybe this is something of interest to add to the "best practices" section. It has the drawback that you can't use it directly with []T (where T satisfies fmt.Stringer), but you can use a simple for loop in that case if needed.)

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 25, 2020

@griesemer

Here's another way of looking at this: Generics are essentially a "glorified" version of macros. Would you use a macro in this case (because it might give you a significant benefit)? I think the answer would be a clear "no".

I honestly don't know if I would. I don't think so, no. Well maybe I would because the compiler might in the future be better able to optimise my code. At least I won't lock out that opportunity. I don't know really. At least currently I don't have to think about this or make a decision because luckily Go doesn't have macros.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Sep 27, 2020

Generic features tend to add type complexity - generally, generic code is significantly more complicated to understand due to the extra abstraction. If you doubt that I encourage you to decipher some of the generic pieces of code submitted with some of the issues against the prototype.

Because of that, generic features should be used when all else fails; i.e., it's either not possible to write the code without it, it's massively slower, or it's significantly less type safe. I fail to see how that is the case with your specific question. You're of course free to code as you please, but personally, I'd go with the simpler solution that does the same thing.

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 27, 2020

(...) generic features should be used when all else fails

I agree. And I certainly agree with you in case of the ReadAll (On second thought I was exaggerating a bit).

I was voicing what I expect people will use as "excuse" to still use generics, as the arguments I gave have been used for the use of "template for everything" in for example libraries for C++. (Sorry for referencing other languages, I have tried not to for as long as possible).

Keep in mind that there are many programmers who use Go on an intermittent basis (other microservices might be written in Kotlin or Rust), or are learning Go on the side coming from Java/C/C++. They will know templates/macros, but the dynamic interface concept requires some more effort to fully understand (think of nil and type assertion syntax etc). Therefore I believe they will be inclined to use the generics version, especially because it leaves open the opportunities for optimisation by the compiler. To them the interface version might be harder to understand "with everything that's going on at runtime". In the end, the results are fixed so both work sort of equally well.

Of course if you think this will certainly not be an issue, I'll follow your lead.

Just to be absolutely sure, I do think generics are very useful (even in the current proposal). It would allow the containers packages to be type safe and allows for many other very useful stuff. The only thing that concerns me is that I personally probably don't ever need a way to call methods on T, because I have runtime interfaces. Therefore I believed a simpler version like the operator list in this proposal is worth exploring. That has be done by now, of course.

Thanks a lot for taking the time and effort to listen to the community.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Sep 27, 2020

Thanks for the clarification and bringing in the perspective of people that might be new to Go. That's certainly something to consider, especially if we want to establish a "best practices" document.

I agree that where interfaces work great now, generics are not needed. It's really situations where interfaces would be extremely cumbersome (because they need to model operators, or because we need extra type assertions) where generics should be considered. When you look at the examples in the design draft, it is noteworthy that most examples actually use constraints with type lists because we want to use operators in a generic way.

But I think it would be too restrictive to drop the ability to require methods in constraints, which is what your proposal essentially does.

(FWIW, the shortcomings I brought up earlier about problems with constants etc. could be addressed by making the constraint for a type parameter a type list. Or in other words, if we removed the ability to specify methods on constraints and only permitted type lists - and adjusted the syntax adequately - we'd arrive at the same place where you are with this proposal.)

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 28, 2020

(FWIW, the shortcomings I brought up earlier about problems with constants etc. could be addressed by making the constraint for a type parameter a type list. Or in other words, if we removed the ability to specify methods on constraints and only permitted type lists - and adjusted the syntax adequately - we'd arrive at the same place where you are with this proposal.)

Yes, that's true, although you'd still need the special comparable identifier.

Regarding the current proposal, would it be worth considering using just = and == instead of interface{}/any and comparable? I think that 95% of real world generics would use either of these two constraints so it sort of make sense to make that use case as direct and short as possible to express. The other 5% like math.Min/Max can use the interface with types lists or method for its constraint. It would also avoid introducing the comparable/any special identifiers. (I find my self naturally using T = and T == when toying around with generics because of its directness. Maybe try it for a bit).

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 28, 2020

Once you accept that a type constraint is an interface type, then to me it makes sense for the two special cases to also be interface types. So your suggestion is sort of like saying that = and == could be names for interface types, but to me that seems a bit weird.

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 29, 2020

Ha, yes I agree that it would be certainly weird to say = and == are names for interfaces. I just meant to say instead of two special interface identifiers (any and comparable), let's do two special case constraints = and == and then custom constraints are via interfaces. Maybe that's still weird of course, but it saves a lot of typing and it nicely pops out in the already complex syntax with generics. Of course, I am completely biased.

Btw, I see the point that any would make the other use of interface{} also visually cleaner, so that has certainly that benefit. (On the other hand, the currently valid type any = interface{} has not attracted that much use.)

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 29, 2020

Out of curiosity, comparable in the current proposal was certainly not meant as a an special interface right? because this code certainly doesn't make sense (to me):

func MyFunc(a, b comparable) bool {
     return a == b
}

I understood comparable to be a special type constraint (it is also named this in the proposal). (I meant == in the same way). I am still left a bit confused though:

type My interface {
    comparable
    fmt.Stringer
}

func A[T My](a, b T) // valid
func B(a, b My) // valid??  probably not?

So this probably means that not all interfaces can be used as function argument types?

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 29, 2020

In the current generics design draft comparable is only permitted as a type constraint. But I think it would be a very natural extension to permit comparable to be used as an ordinary type. A value of any comparable type could be assigned to a value of type comparable.

If we did permit that then your func B(a, b My) example would be valid.

@markusheukelom
Copy link
Author

@markusheukelom markusheukelom commented Sep 30, 2020

I see. So the comparable would work like an interface{}, but you couldn't assign values like maps, slices and function to them (and struct containing these). Calls like MyFunc("go", 2.0) (different types) are just fine but will always return false (as per the rules for interface).

I understand now that you see "comparable" as a property of a type instead of an operator between typed values (although it is defined like that for an interface). That might make sense indeed for a strictly typed language. It feels a bit weird to me that both these function would compile without problem:

func MyFunc1(a, b comparable) bool {
     return a == b
}
func MyFunc2(a, b interface{}) bool {
     return a == b
}

In while in contrast, these don't:

func MyFunc3(a fmt.Stringer) string {
     return a.String()
}
func MyFunc4(a interface{}) string {
     return a.String() // invalid
}

Maybe it just something to get used to as a special case.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 30, 2020

There is a difference between MyFunc1 and MyFunc2, of course: MyFunc2 might panic, but MyFunc1 never will.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Sep 30, 2020

@markusheukelom Presumably you meant func MyFunc4(a interface{}) string.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Sep 30, 2020

Thanks for the suggestion. We're going to move forward with the current generics design draft, at least for now (https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md).

This is a likely decline. We can revisit that decision if the current design draft is not adopted. Leaving open for four weeks for final comments.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Oct 27, 2020

No further comments.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants
You can’t perform that action at this time.