What is so hard about adding generics?

5730 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
to Gordon Klaus, Theemathas Chirananhavat, golang-nuts, chand...@gmail.com
And by defining a LenSwapper interface, you only need two lines per type.

Tahir

unread,
Nov 29, 2014, 6:45:09 AM11/29/14
to golan...@googlegroups.com, chand...@gmail.com

For generics into the type system, you are probably going to need more full memory fences I imagine. 
The reason is that you cannot guarantee that your generic type holds into a single machine word. Therefore it will have a huge impact on performance.

That's the reason why using collection of interfaces is not necessarily a good thing too. Besides, the indirection (an interface is basically 2 pointers) does not guarantee contiguity in memory.

If you want, template-like generics, then we are going to fight (just kidding, that may be a personal thing, but <int,float> is a code uglifier. Besides my personal opinion, it will make some kind of concurrency programming difficult too)

A lot of us add the same feelings about generics. But after a few months / weeks ? / days ?, you realize that maybe you don't need them as much as you thought anyway.

Now I'm not saying that they are a few things that I think couldn't make life easier, but I don't think I would ever want to trade the simplicity of the language as it is for a code writing convenience that I don't need most of times. If I have to write more code, from time to time, so be it. And I'm sure that the way to solve the issue of generic programming is actually not in having generics.

Milan P. Stanic

unread,
Nov 29, 2014, 8:01:17 AM11/29/14
to golan...@googlegroups.com
On Sat, 2014-11-29 at 03:45, Tahir wrote:
[...]
> Now I'm not saying that they are a few things that I think couldn't make
> life easier, but I don't think I would ever want to trade the simplicity of
> the language as it is for a code writing convenience that I don't need most
> of times. If I have to write more code, from time to time, so be it. And
> I'm sure that the way to solve the issue of generic programming is actually
> not in having generics.

+1 (Nicely said.)

[...]

Gyu-Ho Lee

unread,
Nov 29, 2014, 1:50:27 PM11/29/14
to golan...@googlegroups.com
+99999 please don't add generics. I don't want to go back to c++

chris dollin

unread,
Nov 29, 2014, 2:02:57 PM11/29/14
to Gyu-Ho Lee, golang-nuts
On 29 November 2014 at 18:50, Gyu-Ho Lee <gyuh...@gmail.com> wrote:
> +99999 please don't add generics. I don't want to go back to c++

Adding "generics" [1] doesn't enforce committing to the C++ model.

Chris

[1] Of some kind. It's a woolly term.

--
Chris "sheepish" Dollin

Sebastien Binet

unread,
Nov 29, 2014, 2:36:22 PM11/29/14
to chris dollin, Gyu-Ho Lee, golang-nuts
On Sat, Nov 29, 2014 at 8:02 PM, chris dollin <ehog....@googlemail.com> wrote:
> On 29 November 2014 at 18:50, Gyu-Ho Lee <gyuh...@gmail.com> wrote:
>> +99999 please don't add generics. I don't want to go back to c++
>
> Adding "generics" [1] doesn't enforce committing to the C++ model.
>
> Chris
>
> [1] Of some kind. It's a woolly term.
a wibbly-wobbly timely-wimely [term].

-s

Tahir

unread,
Nov 29, 2014, 5:23:23 PM11/29/14
to golan...@googlegroups.com
From the recent C++ conf I've watched, it looked `to me` more like C++ was planning to move toward Go ;-)

Just to be clear, I'm wary of the 'generics' from the other languages but I would be in favor of any solution that doesn't penalize everyone and looks good (I mean, really looks clear visually in terms of code).

Reified types with the first class functions of Go could be quite cool. Have to see where the reflect pkg goes.

But you can really fiddle with interfaces. (that will require to not use the builtin types but define your own types on top.. There is still the issue of doing operations on objects that implement the same interface but are different, yet I guess an "explicit" conversion would have to happen in those cases, anyway).  Most of the time, it's the need for genericity of the return value of functions that is a problem.

A bit like that ( please don't chastize me  : http://play.golang.org/p/9rR3Askxpe ) although I understand that you have to redefine the operators, that a simple computation now looks ugly etc etc. really just a mere example.

Chandru

unread,
Nov 29, 2014, 6:00:49 PM11/29/14
to Dave Cheney, Go Mailing List

Ian Lance Taylor

unread,
Nov 29, 2014, 6:18:37 PM11/29/14
to Theemathas Chirananhavat, golang-nuts, chand...@gmail.com, gordon...@gmail.com
On Sat, Nov 29, 2014 at 3:01 AM, Theemathas Chirananhavat
<theem...@gmail.com> wrote:
>
> From https://golang.org/src/pkg/sort/sort.go lines 233-237:
>
> (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.

That is hyperbolic. Copying three lines per type that needs to be
sorted is clearly not ideal. However, it will never become
unmanageable. Copying becomes unmanageable when there is a series of
patches that must be applied to each copy. These three lines are
simple enough that that will never happen.

I agree that this is a case that would benefit from some form of
generics, but this can't be the main argument for adopting them.

Ian

Ian Lance Taylor

unread,
Nov 29, 2014, 6:24:06 PM11/29/14
to Theemathas Chirananhavat, golang-nuts, chand...@gmail.com
On Sat, Nov 29, 2014 at 2:33 AM, Theemathas Chirananhavat
<theem...@gmail.com> wrote:
>
> What is the difference between "operator overloading" and "methods with the
> same name" anyway?

1) Syntax. 2) The number of surprises when reading code.


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

No, the interface system is a fully based implementation of structural
typing. Most people take generics to imply some variety of parametric
polymorphism, which is different.


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

I agree that if Go were to adopt operator overloading it would be
through a mechanism along those lines.

Ian

Ian Lance Taylor

unread,
Nov 29, 2014, 6:39:06 PM11/29/14
to Theemathas Chirananhavat, golang-nuts
On Fri, Nov 28, 2014 at 7:21 PM, Theemathas Chirananhavat
<theem...@gmail.com> 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.

And yet, they are real problems. If you are really interested in
this, I suggest that rather than simply stating that they are easy,
you spend some time building a full proposal. But you should only do
that for fun, not because you hope that it will be adopted.

Personally I would say that the main difficulties with generics in Go
are 1) types are different sizes and support different syntactic
operations, 2) Go is a fully compiled language, 3) fast compilation is
considered to be very important, 4) simplicity is considered to be
very important (Go programs should be easy to understand or, to put it
another way, the Obfuscated Go Contest should be boring).

Ian

Bakul Shah

unread,
Nov 29, 2014, 6:44:02 PM11/29/14
to chris dollin, Gyu-Ho Lee, golang-nuts
You're probably thinking of the "What is Generic Programming"
paper by Dos Reis and Järvi that looks this question in
exhaustive/ing detail but I think most people who bleat on
about "generics" would agree with the Wikipedia definition:

In the simplest definition, generic programming is a style
of computer programming in which algorithms are written in
terms of types to-be-specified-later that are then
instantiated when needed for specific types provided as
parameters.

Of course this too is fuzzy but you have shaved the sheep
pretty close!

Examples:

type T // we just say T is a type but nothing else about it
...
func Max(a, b T) T { if a > b { return a }; return b }

If Max is used on objects of a type for which > is not
defined, this can be caught at compile time.

type T1, T2
...
func Map(f func(T1)T2, in []T1) []T1 {
out := make([]T2, len(in))
for i,val := range in { out[i] = f(val) }
return out
}
...
sq := func (x int) { return x * x }
fmt.Printf("%v\n", Map(sq, []int{1,2,3,4,5}))
// should print [1 4 9 16 25]
...
func Fold(f func(T1,T2)T1, z T1, in []T2) []T1 {
out := make([]T1, len(in)+1)
out[0] = z
for i,val := range in { out[i+1] = f(out[i], val) }
return out
}
...
plus := func (x float64, y int) float64 { return x + float64(y) }
fmt.Printf("%v\n", Fold(plus, 0.5, []int{1,2,3,4,5}))
// should print [0.5 1.5 3.5 6.5 10.5 15.5]

etc. But given Go's design, type parameterization can never
get as complicated as C++ templates.

Of course, any such design has to dovetail with Go's existing
features and that is a tall order. And generic will make the
compiler more complicated (though this might be easier in Go
-- with each generic object you associate a "generator"
process that accepts concrete types and returns an error or a
concrete object).

PS: I don't like the way I declared T, T1 & T2 above as their
scope is global, but Max, Map and Fold just need local defns.

Matt Sherman

unread,
Nov 29, 2014, 7:50:53 PM11/29/14
to golan...@googlegroups.com, chand...@gmail.com
v4 of my gen tool (will merge to master this week) has the notion of Numeric, Comparable and Ordered type constraints for exactly this purpose. So one can implement a Max or a Sum and target only types meeting certain constraints.

The work to determine such "type classes" is done by the excellent types package.

On Saturday, November 29, 2014 4:41:58 AM UTC-5, Theemathas Chirananhavat wrote:
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

On Saturday, November 29, 2014 1:10:18 PM UTC+7, Dave Cheney 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,
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

Jesper Louis Andersen

unread,
Nov 29, 2014, 8:05:20 PM11/29/14
to Dave Cheney, golang-nuts

On Sat, Nov 29, 2014 at 4:53 AM, Dave Cheney <da...@cheney.net> wrote:
Generics cannot be added to the language without also adding support for inheritance, aka subtyping.

I'm almost positive you can take the interface concept as a system of structural subtyping. A ReadCloser is a Reader and a Closer, so it is a subtype of both (it is more specific, hence a subtype). Whenever the code mandates a Reader, you can use something of type ReadCloser as well. In general, inheritance != subtype, the latter being a more general concept.

The problems has to do with:

* compilation speed
* linking speed and/or performance of linked programs
* complexity: Benjamin C. Pierce, "Types and programming languages" chapter 15 (subtyping) and chapter 26 (bounded quantification) has all the details of why generics are hard to add to languages if they also employ a construction of subtyping.

In type theory, a feature by itself is easy to implement. It is in the interplay between different type features that things become hard to implement correctly.



--
J.

Dave Cheney

unread,
Nov 29, 2014, 8:08:10 PM11/29/14
to Jesper Louis Andersen, golang-nuts
How does an interface help me write a max function that only operates on numbers? Interfaces only specify behaviour, not data.


Tahir

unread,
Nov 29, 2014, 8:22:31 PM11/29/14
to golan...@googlegroups.com, jesper.lou...@gmail.com

Matt Harden

unread,
Nov 29, 2014, 9:36:22 PM11/29/14
to Jesper Louis Andersen, Dave Cheney, golang-nuts
If you don't allow generic interfaces, then the subtyping issue disappears. This doesn't mean generic types couldn't implement interfaces, however.

--

Jsor

unread,
Nov 30, 2014, 12:55:10 AM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com
On Saturday, November 29, 2014 5:08:10 PM UTC-8, Dave Cheney wrote:
How does an interface help me write a max function that only operates on numbers? Interfaces only specify behaviour, not data.


I think in some way, what a lot of us are looking for is sort of the idea of type-safe interfaces and functions. This problem also kind of affects things like Heap to a degree. There's no good way to ensure at compile time that only MyType is pushed onto a heap, and only MyType is popped off a heap, because of the Interface thing. If I want to write a function that has a priority queue of Fooers, I can't enforce that, the user needs to pass in any old heap.Interface, and when I call heap.Pop I have to type switch myself every time.

Okay, they could define another interface that wraps a heap.Interface, where MyHeap.Pop does the type assertion itself, but it's messy and involves frequent assertions.

As you note, this is especially dicey with numeric routines. What if I have some function called SuperComplicatedMathFunction, that takes in two numbers, but the only basic operations it needs to work are addition or division? The typical Go paradigm suggests

type AddDivider interface {
    Add(AddDivider) AddDivider
    Divide(AddDivider) AddDivider
}

func SuperComplicatedMathFunction(a,b AddDivider)

But the problem here is that there's absolutely no way to ensure a and b can actually be added together. Both an int and a float64 are AddDividers, but only within the same type -- not across types. Trying to actually implement this leads to a mess of type switches.

I did write a not-very-serious proposal for something that solves this particular problems here: https://gist.github.com/Jragonmiris/b69757366709d0fe884f

But I think go generate fills close to the same void if I understand the tool right.

Theemathas Chirananhavat

unread,
Nov 30, 2014, 1:28:19 AM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com
This is probably the main reason to add generics. However, numeric routines are not the only routines that need generics. Custom data structures also need them.

An example is designing a segment tree library for solving the generalized version of dynamic RMQ. You only need values that has some notion of "less than", but go can't do it with proper type safety.

Theemathas Chirananhavat

unread,
Nov 30, 2014, 1:50:57 AM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com
There are at least two ways to solve this with generics.

1. Use generic interfaces that allow some sort of self-reference. Create a new type or use an existing type that satisfies an interface. (Something like "type Comparable interface { (self T) IsLess(other T) bool; }" ). Pass values of that type to the functions/methods that manipulate the data structure.

2. Use generic functions. Create a function or use an existing function that compares two values. (Something like "type [T]CompareFunc func(T,T) bool".) Pass that function to the (second-order) function that creates the data structure.

Personally, I feel that the latter approach is cleaner and simpler. Self-reference might lead to less boilerplate code if the corner cases can be properly dealt with, though.

Gyu-Ho Lee

unread,
Nov 30, 2014, 1:55:11 AM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com
Just question out of ignorance. 

What do you mean by `solving the generalized version of dynamic RMQ`?

What do you mean by `go can't do it with proper type safety`? 

Why do we need generics to solve this problem? 


Thanks!

Tahir

unread,
Nov 30, 2014, 3:00:48 AM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com
I think you would can abstract the type switches away (you would have needed some sort of conversion anyway).
I don't think you can be safe at compile time fully if you want genericity (well, or it is going to be costly)

You can probably define the identity of data in the method set even though it is not necessarily optimal.
The issue I see is bigger interfaces depending on someone's use case.

But I think Jesper is right, at least in theory. The practice might be something else.

Example of a Max function generalized to int64 and float64 : http://play.golang.org/p/rznK07-CY8

Trying that with a complex number should result in a runtime error. That's simply the result of needing genericity.
But you can  absolutely define order relations as methods.

Theemathas Chirananhavat

unread,
Nov 30, 2014, 4:52:04 AM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com
By "generalized", I mean doing it on any value with a well-defined connotation of "less than".

By "proper type safety", I mean doing it without any type assertions. Anywhere.

Theemathas Chirananhavat

unread,
Nov 30, 2014, 5:00:12 AM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com, da...@cheney.net
I think that the subtyping (aka interface embedding) issue can be easily be solved for generic interfaces.

Example (in generic psudo-go):

type Foo [T]interface {
   
Something() T
}

type
Bar [T3][T2]interface {
   
Foo[T2]
   
Something2() T3
}

type
NonGeneric interface {
   
Bar[int][string]
}

Message has been deleted

egon

unread,
Nov 30, 2014, 5:46:32 AM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com, da...@cheney.net
This discussion doesn't seem to be going anywhere...

You (huge generalization) are discussing only how to implement generics, but not the important points!

IMHO the important points are:

1. How many problems does "generics" actually solve?
2. What are those problems?
3. How common are these problems in programs? (Do 1%, 5%, 10%, 25% of programs need it? What kinds of programs need it?)
4. Is "generics" the best solution to those problems?
5. What will the longer term effect will be on the generics?

And when I mean problems, I mean actual problems, not "I want to implement this thing with generics", or "I can't implement LINQ"; those are just about implementing a solution and ignoring the problem.

The more I look at these questions, the less I find reasons to introduce generics.

+ Egon

Gyu-Ho Lee

unread,
Nov 30, 2014, 6:00:38 AM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com, da...@cheney.net
Well said +1.  

Go team created Go to solve their problems in `Google` scale.
If they needed generics, they should have implemented by now.

Wonder what kind of real problems cannot be solved by not having generics.

Jeff Juozapaitis

unread,
Nov 30, 2014, 6:45:45 AM11/30/14
to egon, golang-nuts, jesper.lou...@gmail.com, da...@cheney.net
I don't really care about generics, my main issue is still type safety. Go is very strict about types, it doesn't even allow auto-addition of floats and ints. However, it also denies the ability to cleanly assure type matching. Often I don't care that a and b are floats, I care that a and b are merely the same basic numeric type. This has been very true in 3D linear algebra, geometry, and graphics packages for me, where aside from some hand-written SIMD code the vast majority of the code duplication could be trivially removed if I could use mostly the same code for 32-bit and 64-bit types. At the moment I use a Makefile that's mostly just cp and gofmt -r. 

(Note that I'm not arguing that in theory deduplication of this sort of code can't be done without generics, I managed to write it generically at one point with a general Scalar type and large amounts of magic, but it benchmarked really poorly for performance-sensitive rendering-focused numeric code and had some really, really ugly typing and conversion shenanigans going on).

I also worry about the type safety of heap. It seems far too easy to accidentally pollute a heap with the wrong type since it deals with interface{}s. Admittedly, this is almost dynamic typing, it's nothing I'm not used to with Python, but it's a bit odd for a language that normally has such strict, static typing. Sure, the language will end up panicking the second your container's Push is called due to trying to insert a bad type into a slice or whatever. But relegating basic container/collection type safety to a runtime panic concern seems contrary to Go's general safe, static typing philosophy to me. This is also more of an academic concern, every time I've used a heap it's been limited in scope to a single function/struct where you can be reasonably certain that you code will always push/pop the right types, but then that raises the question of why I'm doing a type assertion on every push and pop if I know the type a priori.

Go generate is going to make this a bit easier once I get a better generator script written for my numeric code, but it's still a bit annoying. Is it important? Not really, it's a small annoyance, and I'd wager that in reality generics probably really affects <10% of developers meaningfully. Personally, I don't think Go should really add them, but I like posting in these discussions because I find theorycrafting a palatable model for them fun.

Jesper Louis Andersen

unread,
Nov 30, 2014, 10:05:17 AM11/30/14
to Dave Cheney, golang-nuts

On Sun, Nov 30, 2014 at 2:07 AM, Dave Cheney <da...@cheney.net> wrote:
How does an interface help me write a max function that only operates on numbers? Interfaces only specify behaviour, not data.

Come to think of it, I'm not even sure people mean the same thing when they say "generics". It is more likely that people have different opinions on what generics constitutes and what the goals of such a solution happens to be. What I am trying to say is that the interplay between features is complicated and there is no simple solution. The interplay I am trying to argue against is that if you allow generically varying data in the language, you will have to address that one can pass an interface type as a value and since interfaces define a subtyping lattice, then the touch-move rule of chess applies: any solution will be forced into handling interface values at some point or the other. And since interfaces obviously defines a subtyping lattice, your type soundness can only be addressed by adding something like bounded quantification[0]

Personally, I'd much