What is so hard about adding generics?

5837 views
Skip to first unread message

Theemathas Chirananhavat

unread,
Nov 28, 2014, 10:21:06 PM11/28/14
to golan...@googlegroups.com
Seriously, I don't understand why is it so hard to add generics to go. You might say that you don't need it, but library writers would definitely want generics. A language cannot be successful without good libraries.

From what I have read (e.g. https://golang.org/doc/faq#generics "Generics are convenient but they come at a cost in complexity in the type system and run-time."), there seems to be two types of problems about generics: (1) syntax and semantics (2) implementation and performance. However, both don't look like real problems to me.

As for syntax and semantics, the go interface system is already pretty similar to haskell's typeclasses, so I think it should be relatively easy to model generics after haskell's polymorphism.

As for implementation and performance, it probably wouldn't be much different from the existing implementation of interfaces, which is already sort of partially implemented generics.

Did I miss anything? Is generics really that problematic?

Michael Jones

unread,
Nov 28, 2014, 10:52:36 PM11/28/14
to Theemathas Chirananhavat, golang-nuts

You've missed a few years of discussion on the topic. A search through the group archive will be interesting for you.

You also missed "go generate", which is new scaffolding for the general task of generated code.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Dave Cheney

unread,
Nov 28, 2014, 10:53:47 PM11/28/14
to golan...@googlegroups.com
Generics cannot be added to the language without also adding support for inheritance, aka subtyping. Go does not support inheritance so generics cannot be added. 

It's as simple as that. 

Dave Cheney

unread,
Nov 29, 2014, 1:10:18 AM11/29/14
to Chandru, Go Mailing List
Most of the arguments for adding generic to Go is to support
collection types, sets, tries, etc. That isn't very interesting to me,
I'm sure it's interesting to others, but not to me; maps and slices
work just fine.

What is interesting to me is writing generic functions, the simple
example is Max. I want to write a Max function that _only works on
numbers_. It isn't sufficient to say

func Max(a, b T) T

because that does not constrain the types that can be substituted for
T. Ideally what you would write is

func Max(a, b <T extends Number>) (T extends Number>

To make up a random syntax. But in Go we cannot write that because
there is no supertype of int, uint, float64, complex128, etc. Even if
there were, is Number the supertype of type MyInt int ?

And, even if there was some notion of some kinds of types being
grouped together as numbers, that still leaves the problem of
overloading the arguments to a function. Ie

x, y := 100, 200
a, b := 1.0, 3.14

fmt.Println(Max(x,y), Max(a,b))

Go doesn't allow functions to be overloaded based on their arguments,
so some kind of templated code generation (which I think is what Rust
has), wouldn't work either. You can't have two Max functions defined
either by the programmer, or by the compiler in the same package.

Now that might be solvable, if the compiler appended some hidden
suffix, but that introduces even more problems

max := Max
f(max)

What is the type of Max ? If max is passed as a value what is the type
of the argument, if the arguments to Max are not specified til it is
invoked.

Dave

On Sat, Nov 29, 2014 at 4:40 PM, Chandru <chand...@gmail.com> wrote:
> I have read about the complexity in adding generics and Russ' Generic
> Dilemma, but I've never come across inheritance being necessary for it.
>
> Can you explain this a little more? For example, rust did not have
> inheritance in the sense of Java/C++ sub-classes, but has always had
> generics.
>
> --
> Chandra Sekar.S

wkharold

unread,
Nov 29, 2014, 1:20:29 AM11/29/14
to golan...@googlegroups.com
Yes, and yes. If it was easy, even relatively easy, don't you think go's designers would have included generics? Per Michael Jones, generics have been discussed extensively on this list since go's public release. Proposals and "solutions" are not in short supply. Workable ones, that don't permanently deface the language, however, have proved hard to come by.

minux

unread,
Nov 29, 2014, 2:21:42 AM11/29/14
to Dave Cheney, Chandru, Go Mailing List
On Sat, Nov 29, 2014 at 1:09 AM, Dave Cheney <da...@cheney.net> wrote:
Most of the arguments for adding generic to Go is to support
collection types, sets, tries, etc. That isn't very interesting to me,
In fact, even type safe generic collections are hard. Many of the existing proposals
don't even support list of list of T.

Tahir

unread,
Nov 29, 2014, 2:24:30 AM11/29/14
to golan...@googlegroups.com, chand...@gmail.com
I would add that it can make concurrency difficult. And generic collections are probably difficult to do because of alignment and type safety guarantees.

I still wish we could have some generic collections at some point though, and think that it could perhaps be doable via code generation. Importing a package that initializes a type at runtime which is basically a struct of arrays of some kind of predetermined size. That's just an idea though.

And funnily enough, my need for generic functions is quite limited since we have interfaces (for now at least, but I'm pretty sure I'm doing less interesting stuff than Dave). I have genericity of  behaviour in my current use cases. I just wish sometimes for more capabilities around the handling of types at runtime but it's coming incrementally in the reflect pkg and I have the good feeling we will have a way to deal with that in the future.

roger peppe

unread,
Nov 29, 2014, 3:04:09 AM11/29/14
to Dave Cheney, golang-nuts, Chandru

I think you have chosen a particularly problematic example there. I personally think that it would be fine to add generics to Go without providing the capability to perform arithmetic operations directly on generically typed values. That's the approach taken with interfaces (with the exception of ==) and it works well.

I don't see that subtype polymorphism is necessary or desirable in Go-with-generics.

My worry about generics is that everyone will instantly carry across their design patterns from other languages and we could lose the first order simplicity that most Go code currently exhibits.

chris dollin

unread,
Nov 29, 2014, 4:15:59 AM11/29/14
to Dave Cheney, golang-nuts
On 29 November 2014 at 03:53, Dave Cheney <da...@cheney.net> wrote:
> Generics cannot be added to the language without also adding support for
> inheritance, aka subtyping.

I don't see why; I'd regard ML's polymorphic functions and
datatypes as providing (one style of) generics, and there's no
inheritance there and the subtyping is "you can replace this type
variable uniformly with with this type".

"inheritance" and "subtyping" aren't the same thing.

> Go does not support inheritance so generics cannot be added.
>
> It's as simple as that.

It's never that simple.

Chris

--
Chris "allusive" Dollin

Gyu-Ho Lee

unread,
Nov 29, 2014, 4:28:01 AM11/29/14
to golan...@googlegroups.com
Rob Pike answer for this: http://youtu.be/u-kkf76TDHE?t=34m41s

Theemathas Chirananhavat

unread,
Nov 29, 2014, 4:34:25 AM11/29/14
to golan...@googlegroups.com, theem...@gmail.com
I already tried to search for the discussion about generics, but I just cannot find one that addresses this issue properly. Most of the stuff that I find are relatively recent posts.

Can you post a link to a good discussion?

chris dollin

unread,
Nov 29, 2014, 4:37:46 AM11/29/14
to Theemathas Chirananhavat, golang-nuts
On 29 November 2014 at 03:21, Theemathas Chirananhavat
<theem...@gmail.com> wrote:

> As for implementation and performance, it probably wouldn't be much
> different from the existing implementation of interfaces, which is already
> sort of partially implemented generics.

*Requiring* generics to be implemented with uniform sizing
and hence pointers (which are buried in interfaces) is *specifically*
not what the Go team want to do.

> Did I miss anything? Is generics really that problematic?

Yes. The devil is in the details.

Theemathas Chirananhavat

unread,
Nov 29, 2014, 4:41:58 AM11/29/14
to golan...@googlegroups.com, chand...@gmail.com
In that case, the type of Max (and also the type of max) would be something like "[for_all T assignable_to Number] func(T,T) T".

"Number" would be something similar to a "built in psudo-interface type", and "assignable_to" would be a generalized version of the criteria at http://golang.org/ref/spec#Assignability

Dave Cheney

unread,
Nov 29, 2014, 4:47:29 AM11/29/14
to Theemathas Chirananhavat, golang-nuts, Chandra Sekar S

But interfaces only specify behaviour, not data. This is the "boxing" issue that rsc referred to.

If Number was an interface that could hold any numeric type it would have to be 128 bits wide to accommodate the largest numeric type that Go supports.

Additionally if this Number interface was some sort of built in, how would it be extensible for other user declared numeric types like type Complex64 { real, image float32 }

Ultimately the reason I believe Go 1.x will not have generics is the overwhelming number of limitations and edge cades like these.

You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/smT_0BhHfBs/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.

Theemathas Chirananhavat

unread,
Nov 29, 2014, 4:48:29 AM11/29/14
to golan...@googlegroups.com, da...@cheney.net, chand...@gmail.com
Well... suppose you want a function that takes a slice of slices of Ts and returns a slice of slices of Ts, I can do something like: "[for_all T] func foo([][]T) ([][]T) {}" Right?

If you are talking about implementation details, that another story, though.

Theemathas Chirananhavat

unread,
Nov 29, 2014, 4:53:02 AM11/29/14
to golan...@googlegroups.com, chand...@gmail.com
How does generic programming make concurrency difficult? How is generic programming more difficult than interfaces about alignment and type safety? Generic programming is basically a type-safe version of "interface{}"

If you think you can use interfaces to do anything practical, how do you write a type-safe function that reverses a slice of anything?

Theemathas Chirananhavat

unread,
Nov 29, 2014, 4:56:44 AM11/29/14
to golan...@googlegroups.com, theem...@gmail.com
How are generics different from templates in that respect?

Theemathas Chirananhavat

unread,
Nov 29, 2014, 5:11:51 AM11/29/14
to golan...@googlegroups.com, theem...@gmail.com, chand...@gmail.com
Python's approach to extend built in functions/operators (e.g. len(), >, ==, +) to user-defined types is to use a specially named method. See https://docs.python.org/3/reference/datamodel.html#special-method-names and https://docs.python.org/3/reference/datamodel.html#emulating-numeric-types

Haskell's approach is to treat operators like functions with 2 arguments and defining the "Num" and "Integral" typeclasses (similar to go's interfaces, but they must be explicit). These typeclass requires a few operators/functions to be defined. See: http://hackage.haskell.org/package/base-4.7.0.1/docs/Prelude.html#t:Num and http://hackage.haskell.org/package/base-4.7.0.1/docs/Prelude.html#t:Integral (if you know haskell)

If you think it is too complex for Go 1.x, I think it might be the defining feature of Go 2.0.

Dave Cheney

unread,
Nov 29, 2014, 5:17:07 AM11/29/14
to Theemathas Chirananhavat, golang-nuts, Chandra Sekar S

Right, so now you are talking about adding operator overloading to the language.

This is why Go does not have generics, not because they are useless or a bad idea, but because implementing them well (there is no interest in a half baked implementation) would be such a fundamental change to the language that it is likely the core values of the language would not survive.

Theemathas Chirananhavat

unread,
Nov 29, 2014, 5:17:36 AM11/29/14
to golan...@googlegroups.com
Thank you. I would like to know the reason the language designer made it this way.

There is one problem, though. My computer's speakers are acting odd today. I can't hear what he said. :(

Theemathas Chirananhavat

unread,
Nov 29, 2014, 5:18:41 AM11/29/14
to golan...@googlegroups.com, da...@cheney.net
Kudos for mention of ML

Dan Kortschak

unread,
Nov 29, 2014, 5:24:58 AM11/29/14
to Theemathas Chirananhavat, golan...@googlegroups.com
On Sat, 2014-11-29 at 01:34 -0800, Theemathas Chirananhavat wrote:
> I already tried to search for the discussion about generics, but I just
> cannot find one that addresses this issue properly. Most of the stuff that
> I find are relatively recent posts.
>
> Can you post a link to a good discussion?

This is a good starting point: http://research.swtch.com/generic

There are many proposals where various issues have been raised though.

Theemathas Chirananhavat

unread,
Nov 29, 2014, 5:33:19 AM11/29/14
to golan...@googlegroups.com, theem...@gmail.com, chand...@gmail.com
What is the difference between "operator overloading" and "methods with the same name" anyway?

Go already uses "methods with the same name" for interfaces, and the interface system is already (IMHO) a "half-baked implementation" of generics.

One more approach to the problem: In scala, "a + b" and "a.+(b)" are the same. (That is a method called "+")

Starfish

unread,
Nov 29, 2014, 5:33:37 AM11/29/14
to golan...@googlegroups.com
Agreed! Generics is needed, and Go is not "sort of" generic. If it was, someone could implement something similar to LINQ.

Theemathas Chirananhavat

unread,
Nov 29, 2014, 5:34:06 AM11/29/14
to golan...@googlegroups.com, theem...@gmail.com
Thank you.

gordon...@gmail.com

unread,
Nov 29, 2014, 5:35:51 AM11/29/14
to golan...@googlegroups.com, chand...@gmail.com
On Saturday, November 29, 2014 10:53:02 AM UTC+1, Theemathas Chirananhavat wrote:
If you think you can use interfaces to do anything practical, how do you write a type-safe function that reverses a slice of anything?

This doesn't exactly answer your question, but:  http://golang.org/pkg/sort/#Reverse 

Actually, it does more than you ask for; it reverses any ordered collection type, not just slices.

Dave Cheney

unread,
Nov 29, 2014, 5:37:50 AM11/29/14
to Theemathas Chirananhavat, golang-nuts, Chandra Sekar S
On Sat, Nov 29, 2014 at 9:33 PM, Theemathas Chirananhavat
<theem...@gmail.com> wrote:
> What is the difference between "operator overloading" and "methods with the
> same name" anyway?

A vast difference, just ask the go-num folks who have been asking for
operator overloading for 5 years.

Dan Kortschak

unread,
Nov 29, 2014, 5:38:58 AM11/29/14
to Dave Cheney, Theemathas Chirananhavat, golang-nuts, Chandra Sekar S
Us? I don't think so.

Gordon Klaus

unread,
Nov 29, 2014, 5:39:51 AM11/29/14
to golang-nuts, chand...@gmail.com
I have to correct myself:  sort.Reverse doesn't do what I expected.  But it's easy to see how you could implement generic reversal for any type implementing sort.Interface. 

egon

unread,
Nov 29, 2014, 5:46:41 AM11/29/14
to golan...@googlegroups.com
On Saturday, 29 November 2014 05:21:06 UTC+2, Theemathas Chirananhavat wrote:
Seriously, I don't understand why is it so hard to add generics to go. You might say that you don't need it, but library writers would definitely want generics. A language cannot be successful without good libraries.

From what I have read (e.g. https://golang.org/doc/faq#generics "Generics are convenient but they come at a cost in complexity in the type system and run-time."), there seems to be two types of problems about generics: (1) syntax and semantics (2) implementation and performance. However, both don't look like real problems to me.

As for syntax and semantics, the go interface system is already pretty similar to haskell's typeclasses, so I think it should be relatively easy to model generics after haskell's polymorphism.

As for implementation and performance, it probably wouldn't be much different from the existing implementation of interfaces, which is already sort of partially implemented generics.

Did I miss anything? Is generics really that problematic?

The most important thing... what real world problem are you trying to solve with generics that you cannot currently solve with Go?

+ Egon
 

egon

unread,
Nov 29, 2014, 5:48:58 AM11/29/14
to golan...@googlegroups.com
On Saturday, 29 November 2014 12:33:37 UTC+2, Starfish wrote:
Agreed! Generics is needed, and Go is not "sort of" generic. If it was, someone could implement something similar to LINQ.

Sebastien Binet

unread,
Nov 29, 2014, 5:57:42 AM11/29/14
to Dave Cheney, Theemathas Chirananhavat, golang-nuts, Chandra Sekar S
On Sat, Nov 29, 2014 at 11:37 AM, Dave Cheney <da...@cheney.net> wrote:
> On Sat, Nov 29, 2014 at 9:33 PM, Theemathas Chirananhavat
> <theem...@gmail.com> wrote:
>> What is the difference between "operator overloading" and "methods with the
>> same name" anyway?
>
> A vast difference, just ask the go-num folks who have been asking for
> operator overloading for 5 years.

I don't think go-num did that.
we proposed to have a kind of multi-dimensional slice, but left
operator overloading off the table (of the "table" proposal)

-s

chris dollin

unread,
Nov 29, 2014, 6:00:56 AM11/29/14
to egon, golang-nuts
On 29 November 2014 at 10:46, egon <egon...@gmail.com> wrote:

> The most important thing... what real world problem are you trying to solve
> with generics that you cannot currently solve with Go?

Go's as Turning-complete as any other programming language.
The question isn't whether you /can/ solve he problem without
generics, it's whether having generics [1] makes solving problems
clearer or more efficient or subject to better checking by tools
or more fun to write in.

Chris

[1] For some value of "generics". And angsting about what
kind of generics we actually want is part of the problem ...

--
Chris "allusive" Dollin

Theemathas Chirananhavat

unread,
Nov 29, 2014, 6:01:19 AM11/29/14
to golan...@googlegroups.com, chand...@gmail.com, gordon...@gmail.com
Actually, that library demonstrates the problem caused by the lack of generics.


(start code)

type IntSlice []int

func (p IntSlice) Len() int           { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

(end code)

What if you want to sort "[]int16" or "[]int32" or "[]int64" or "[]uint16" or "[]uint32" or "[]uint64"?

You would have to copy and paste most of that code. If you want to sort "[]Time"? One more duplication. For tasks more complicated than that, it would quickly become unmanageable.

Dave Cheney

unread,
Nov 29, 2014, 6:01:26 AM11/29/14
to Sebastien Binet, Theemathas Chirananhavat, golang-nuts, Chandra Sekar S
I am very sorry. I spoke out of turn, this is not my area of expertise.

Gordon Klaus

unread,
Nov 29, 2014, 6:26:47 AM11/29/14
to Theemathas Chirananhavat, golang-nuts, chand...@gmail.com
On Sat, Nov 29, 2014 at 12:01 PM, Theemathas Chirananhavat <theem...@gmail.com> wrote:
Actually, that library demonstrates the problem caused by the lack of generics.


(start code)

type IntSlice []int

func (p IntSlice) Len() int           { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

(end code)

Yes, you have to write a tiny bit of boilerplate code to make a type sortable.  I don't personally find it worth complaining about.
 
What if you want to sort "[]int16" or "[]int32" or "[]int64" or "[]uint16" or "[]uint32" or "[]uint64"?

You would have to copy and paste most of that code. If you want to sort "[]Time"? One more duplication. For tasks more complicated than that, it would quickly become unmanageable.

A little duplication never hurt anyone; it is possible to go overboard with the DRY principle.  In reality, the duplication of three single-line methods is not unmanageable.

Dan Kortschak

unread,
Nov 29, 2014, 6:36:09 AM11/29/14