What is so hard about adding generics?

5,909 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 rather see a system closer to Haskell's type classes/families or something like StandardML/OCaml functors. Having done away with deep class hierarchies in Go already, it feels wrong to add another tool from the OO toolset that turns out to have failed in practice.

Go's strength when considering its interfaces is the loosely coupled, implicitly maintained, compositional structure. The fact you don't have to declare/nominate a relationship before using it is a great help to programmers since it makes programmer interaction more on-demand. A good addition to the expressibility of the language must maintain this strength at all costs. And chances are generics in some form or the other destroys this property. In addition to the destruction of other good properties like fast compilation speeds, or good execution speed.

[0] Of course, there is a chance I am totally wrong here. But the Go language does not enjoy the benefit of having a formal semantics, so it is hard to say exactly, formally, how interfaces operate.


--
J.

Matt Harden

unread,
Nov 30, 2014, 10:26:01 AM11/30/14
to Jesper Louis Andersen, Dave Cheney, egon...@gmail.com, golang-nuts
+Jesper Louis Andersen​, I completely agree with you. Personally I think of Haskell's type classes as form of "generics" but the term is so overloaded that people end up talking past one another. Now, how could we add type classes to Go or extend interfaces to something more like type classes, and as +egon​ asked, what real problems would the proposal solve, and at what cost in terms of compile- or run-time speed and complexity?

--

Nick Craig-Wood

unread,
Nov 30, 2014, 11:34:43 AM11/30/14
to Jeff Juozapaitis, egon, golang-nuts, jesper.lou...@gmail.com, da...@cheney.net
On 30/11/14 11:45, Jeff Juozapaitis wrote:
> 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.

If you want a heap with a specific type then gotemplate + go generate
will do that for you today.

https://github.com/ncw/gotemplate

and

https://github.com/ncw/gotemplate/tree/master/heap

--
Nick Craig-Wood <ni...@craig-wood.com> -- http://www.craig-wood.com/nick

Haddock

unread,
Nov 30, 2014, 12:14:38 PM11/30/14
to golan...@googlegroups.com


Am Samstag, 29. November 2014 04:53:47 UTC+1 schrieb Dave Cheney:
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.

Just as a side note: Rust has templates, but doesn't have inheritance, either. 

akwillis

unread,
Nov 30, 2014, 12:18:05 PM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com, da...@cheney.net
The problems are:
1. code reuse. Right now I am editing the type information for the value of a Set struct everytime I use it within a project that uses a different type. Basically I'm using the original like a template. That is no good.

2. Set theory. Anywhere I feel the builtin types(array, slice, map) are not flexible enough.

3. This issue is common among all my work.

4. Yes. Some class of generics would be useful. The problem is that every time this subject is broached it gets generalized into countless different models. The model I'm most interested about in regard to generic programming is type parameterization. And Yes, this would be the best solution, the only other solution would be to rewrite each package everytime I need to use a different type. Using the silly interface hack works but is very inefficient. 

5. Code reuse.

Set theory and efficient data types are my problems(it is my work) and right now the builtin types aren't enough. Using go generate as a preprocessor is a step in the right direction but I'd like a less commands on type of approach.
Message has been deleted

akwillis

unread,
Nov 30, 2014, 12:35:37 PM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com, da...@cheney.net


On Sunday, November 30, 2014 6:00:38 AM UTC-5, Gyu-Ho Lee wrote:
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.

 Just for starters, code reuse.

Nigel Vickers

unread,
Nov 30, 2014, 1:35:46 PM11/30/14
to golan...@googlegroups.com, jesper.lou...@gmail.com, da...@cheney.net


On Sunday, 30 November 2014 18:35:37 UTC+1, akwillis wrote:


On Sunday, November 30, 2014 6:00:38 AM UTC-5, Gyu-Ho Lee wrote:
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.

 Just for starters, code reuse.

I think you should be called on this. Effective "code reuse" is possible. It requires an inordinate amount of shop discipline and rarely achieves the levels of adoption claimed. It is not bound to generics. It is mostly "application domain" specific. It is more of "Marketing Hype" than serious benefit.

Viktor Kojouharov

unread,
Nov 30, 2014, 5:57:41 PM11/30/14
to golan...@googlegroups.com, chand...@gmail.com
Imho the big problem here is that go doesn't support function overloading. If programmers were allowed to create different Max functions depending on their input (and why not output) arguments, some sort of `go generate` templating solution would be sufficient for anyone wanting to generalize a piece of code. And that's personally one of the few gripes I have with the language (whereas with generics, I really couldn't care less whether they exist or not). 

And since I don't really understand anything about compilers, can someone say what's the difficulty about implementing function overloading?
> On Sat, Nov 29, 2014 at 9:23 AM, Dave Cheney <da...@cheney.net> wrote:
>>
>> 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.
>>
>>
>> On Saturday, 29 November 2014 14:21:06 UTC+11, 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?
>>

Dave Cheney

unread,
Nov 30, 2014, 6:01:38 PM11/30/14
to Viktor Kojouharov, golang-nuts, Chandra Sekar S
If function overloading was added to the language, what would happen
to this piece of code.

f := math.Max // just assume there is a max function for all numeric types
fmt.Printf("%T", f) // what is the type of f ?

And then we come to the problem of type aliasing

x := math.Max(time.Second, Time.Millisecond) // oops, doesn't compile

Function overloading _is_ important to be able to support generic
functions, but without some notion of inheritance, it would be deeply
flawed.
> 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

Viktor Kojouharov

unread,
Nov 30, 2014, 6:22:18 PM11/30/14
to golan...@googlegroups.com, vkojo...@gmail.com, chand...@gmail.com
-- f := math.Max // just assume there is a max function for all numeric types 
That shouldn't compile, throwing some sort of ambiguity error. You'd have to specify the proper function via some sort of specialized syntax, such as:
f := math.Max[...int][int]
or
f := math.Max[int, int][int]
or in some crazy generic world:
f := math.Max[T oneof int,int64,float32][T]

But this in itself is not really an impassable obstacle for implementing overloading.

Also, you currently already cannot assign the built-in functions (like the generic append) to variables (though I assume for different reasons).

-- x := math.Max(time.Second, Time.Millisecond) // oops, doesn't compile 
This is already the case anyway, and unless go adds support for using any alias where applicable, this won't change (I have no idea why there is such a restriction in place). Still, this example illustrates a problem with implementing generics, not overloading.

-- without some notion of inheritance, [function overloading] would be deeply flawed
I'm genuinely curious as to why this would be the case in the context of go (as I've said, I'm not familiar with how languages are implemented). 

Dave Cheney

unread,
Nov 30, 2014, 6:37:25 PM11/30/14
to golang-nuts
Viktor, I'm not having a go at you, or anyone in this thread
specifically, but I do ask that everyone who has proposed a solution
look at what you are suggesting.

Every single suggestion; covariant functions, operator overloading,
interfaces that contain data, etc, do _more_ damage to the language in
the form of restrictions on the previously logical and orthogonal
feature set, than the potential gain from generics.

Please, ask yourself, how much of the character of Go are you prepared
to forgo to have templated types ?

For me, I've already made my choice, I'll take Go as it is and use
code generation, or just write the code N times (where N really is not
unlimited despite what others would suggest) where necessary.

Dave

On Mon, Dec 1, 2014 at 10:22 AM, Viktor Kojouharov

Dave Cheney

unread,
Nov 30, 2014, 7:16:37 PM11/30/14
to Tahir, golang-nuts, Jesper Louis Andersen
So now all the built in types have to implement methods ? This is just
getting worse and worse.

Ian Lance Taylor

unread,
Nov 30, 2014, 7:57:51 PM11/30/14
to Dave Cheney, Chandru, Go Mailing List
On Fri, Nov 28, 2014 at 10:09 PM, 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,
> 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 ?

I think that one way to handle this would be to extend the structural
typing of interfaces. We could say that a generic function Max can
only be instantiated by types that support all the operations used in
the body of the function. So if you write

func Max(a, b T) T {
if a > b {
return a
}
return b
}

then Max can only be used with arguments whose types that support the
< operator (integer, float, string types). In other words the
permitted instantiating types are determined not only by the function
signature, but also by the function body.


> 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.

Right, it can be anything like simple templated code generation.


> 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.

Either you introduce a meta-type system (unlikely) or you require that
the instantiating type of Max be specified whenever it is used. In
C++ syntax:
max := Max<int>

Ian

Ian Lance Taylor

unread,
Nov 30, 2014, 8:15:25 PM11/30/14
to Dave Cheney, Chandru, Go Mailing List
On Sun, Nov 30, 2014 at 4:57 PM, Ian Lance Taylor <ia...@golang.org> wrote:
>
> Right, it can be anything like simple templated code generation.

Sorry, s/can/can't/ .

Ian

Jeff Juozapaitis

unread,
Nov 30, 2014, 9:50:14 PM11/30/14
to Dave Cheney, Viktor Kojouharov, golang-nuts, Chandra Sekar S
Function overloading _is_ important to be able to support generic
functions, but without some notion of inheritance, it would be deeply
flawed.

My pseudo-"proposal" I linked earlier dealt with that, templated functions need to be explicitly created before use. So you'd have

func Max(a,b T) T {
    if a > b {
        return a
    }
    return b
}

Now you use

f := create(Max, int)
bigger := f(1,2) 

Trying to do this with a struct, i.e.

f := create(Max, MyStruct)

Would yield the compile-time error

file:line: cannot create function Max for type MyStruct
    file2:line2: invalid operation a>b (operator > not defined on struct)

These can be disambiguated in the assembly as, just spitballing,

·Max·int
·Max·float32

And so on.

In fact, I'd argue that a templated Max, i.e. f := Max, should yield "undefined: Max" (or perhaps something more specific like "template function Max is not assignable")

If you want to keep it super orthogonal, you could even introduce something like "template func Max(a,b T) T".

Matt Sherman

unread,
Nov 30, 2014, 10:20:22 PM11/30/14
to golan...@googlegroups.com, da...@cheney.net, chand...@gmail.com
That's an intriguing approach.

For that last bit:

max := Max<int>

How to handle it with multiple types in the func? I suppose Max<...argTypes, returnType>.

Also, what about in the case of methods, or in the case of some parameters (or the return type) being concrete and some generic?

Viktor Kojouharov

unread,
Dec 1, 2014, 3:26:31 AM12/1/14
to golan...@googlegroups.com
I just find the discussion very interesting. You have a lot more experience than me in go (a lot more, my first commit in my first piece of go code was in july of 2014), therefore i wouldn't even know about what kinds of damages the addition of function overloading would bring. The only real problem i thought of beforehand was assigning ambiguous functions to variables. And yes, the new syntax would cause problems, but imho it would not be severe, since it wouldn't present any compatibility faults. After all, currently there are no overloaded functions, so all old code will function as is (and of course, I could be very wrong on this assumption). So I really hope you stay active in this thread, as there's much to be learned.

I personally enjoy using go, though I really find the omission of function overloading will hurt in the long run, especially now that code generation has been made easier.

egon

unread,
Dec 1, 2014, 3:46:43 AM12/1/14
to golan...@googlegroups.com, jesper.lou...@gmail.com, da...@cheney.net
On Sunday, 30 November 2014 19:18:05 UTC+2, akwillis wrote:
The problems are:
1. code reuse.

That is not a good problem, but I can see you've added more detailed information.
 
Right now I am editing the type information for the value of a Set struct everytime I use it within a project that uses a different type. Basically I'm using the original like a template. That is no good.

I doubt that there can be a solution that is both fast and templated. The way I would implement a Set<byte> would be significantly different from Set<int>. There would be commonality for some types, but the overhead of running some code generation would be trivial.


2. Set theory. Anywhere I feel the builtin types(array, slice, map) are not flexible enough.

That's a very vague problem, which means it cannot be properly analyzed. I.e. if I can't code a specific real world program that exhibits the problem I really can't understand the problem.
 

3. This issue is common among all my work.

4. Yes. Some class of generics would be useful. The problem is that every time this subject is broached it gets generalized into countless different models. The model I'm most interested about in regard to generic programming is type parameterization. And Yes, this would be the best solution, the only other solution would be to rewrite each package everytime I need to use a different type. Using the silly interface hack works but is very inefficient. 

I doubt that getting both efficency and type parametrization is possible, at least in majority cases. I.e. I can see that working for somewhat similar types, e.g. uint32/int32 but going further than that not really. 

You might be somewhat faster than a interface{} based solution, but not as fast than a solution that takes the type other program specifics into account.

egon

unread,
Dec 1, 2014, 3:54:40 AM12/1/14
to golan...@googlegroups.com, da...@cheney.net, chand...@gmail.com


On Monday, 1 December 2014 05:20:22 UTC+2, Matt Sherman wrote:
That's an intriguing approach.

For that last bit:

max := Max<int>

How to handle it with multiple types in the func? I suppose Max<...argTypes, returnType>.

Also, what about in the case of methods, or in the case of some parameters (or the return type) being concrete and some generic?

Explicit naming of the type parameters:

m := Map~{Key:int, Elem:string}{}
a := math.Min~{T:int}(14, 51)

Nick Craig-Wood

unread,
Dec 1, 2014, 5:35:03 AM12/1/14
to akwillis, golan...@googlegroups.com, jesper.lou...@gmail.com
On 30/11/14 17:18, akwillis wrote:
> 1. code reuse. Right now I am editing the type information for the value
> of a Set struct everytime I use it within a project that uses a
> different type. Basically I'm using the original like a template. That
> is no good.

Gotemplate with go generate solves exactly this problem. It even has a
set type template. Or you can use your own very easily.

https://github.com/ncw/gotemplate

https://github.com/ncw/gotemplate/tree/master/set

Benjamin Measures

unread,
Dec 1, 2014, 5:48:53 AM12/1/14
to golan...@googlegroups.com, da...@cheney.net, chand...@gmail.com
On Monday, 1 December 2014 00:57:51 UTC, Ian Lance Taylor wrote:
I think that one way to handle this would be to extend the structural
typing of interfaces.  We could say that a generic function Max can
only be instantiated by types that support all the operations used in
the body of the function.  So if you write

func Max(a, b T) T {
        if a > b {
                return a
        }
        return b
}

then Max can only be used with arguments whose types that support the
< operator (integer, float, string types).  In other words the
permitted instantiating types are determined not only by the function
signature, but also by the function body.

Don't we already get restrictions on what can be done "by the function body" with interfaces?
func Max(a, b numeric.Interface) numeric.Interface {
        if a.LessThan(b) {
                return b
        }
        return a
}

Isn't then your suggestion more about operator overloading than "generics"?

Theemathas Chirananhavat

unread,
Dec 1, 2014, 8:28:13 AM12/1/14
to golan...@googlegroups.com, da...@cheney.net, chand...@gmail.com
type T1 int64
type T2 float64

//whatever methods here

var x T1 = 1000
var y T2 = 2000.5

var z int8 := Max(x,y).(int8) //whoops

Generics aren't that simple

Jesper Louis Andersen

unread,
Dec 1, 2014, 8:44:20 AM12/1/14
to Ian Lance Taylor, Dave Cheney, Chandru, Go Mailing List

On Mon, Dec 1, 2014 at 1:57 AM, Ian Lance Taylor <ia...@golang.org> wrote:
I think that one way to handle this would be to extend the structural
typing of interfaces.  We could say that a generic function Max can
only be instantiated by types that support all the operations used in
the body of the function.  So if you write

func Max(a, b T) T {
        if a > b {
                return a
        }
        return b
}

This looks very much like type classes in Haskell. However, you may have to nominate the relationship. For instance by declaring a type class Ord:

type class Ord α {
int Cmp(α, α) // Returns either -1, 0, or 1
}

note how this almost looks like an interface, but requires you to specify values for which the type varies. And then in the max function assume we have a varying type α with the property that it is in the Ord type class:

func (Ord α => Max(a, b α) α) {
if Cmp(a, b) < 0 {
return a
}
return b
}

Now, the Max function works for any type α under the additional constraint that α is member of the Ord class. In other words, by implementing an instance of Ord:

func Cmp(a, b int) int {
        if a < b {
                return -1
        } else if a > b {
                return 1
        }
        return 0
}

which can be implicitly instantiated. However, the usual problems tend to apply: you may have to solve some deep chains of type classes. However, on the other hand, it would open up the venue for implementing monads and monoids in Go ;)


--
J.

Matt Sherman

unread,
Dec 1, 2014, 11:07:27 AM12/1/14
to golan...@googlegroups.com
The types package "flattens" the idea of type classes a bit. Instead of a hierarchy of types under type classes, types simple have attributes like Comparable and Ordered: https://godoc.org/golang.org/x/tools/go/types#BasicInfo

Ian Lance Taylor

unread,
Dec 1, 2014, 11:50:30 AM12/1/14
to Matt Sherman, golang-nuts, Dave Cheney, Chandra Sekar S
On Sun, Nov 30, 2014 at 7:20 PM, Matt Sherman <mwsh...@gmail.com> wrote:
>
> That's an intriguing approach.
>
> For that last bit:
>
> max := Max<int>
>
> How to handle it with multiple types in the func? I suppose Max<...argTypes,
> returnType>.

There are indeed many details to consider. This is really just the
first level of detail.


> Also, what about in the case of methods, or in the case of some parameters
> (or the return type) being concrete and some generic?

I tink it would depend on the syntax used to declare a generic method.
Note that the syntax Max<int> can not work for Go, because, e.g.,
Abs<int>(-3) can not be parsed without a symbol table, which is not
acceptable for Go. (Not that I want to get distracted by syntax, I
was just commenting that I think generics can be implemented without
worrying about subtyping.)

Ian

Ian Lance Taylor

unread,
Dec 1, 2014, 11:56:47 AM12/1/14
to Benjamin Measures, golang-nuts, Dave Cheney, Chandra Sekar S
The only operator overloading in my suggestion is the overloading that
is already present in the language. It does not introduce any
additional overloading. Dave was saying that generics requires
subtyping, with specific reference to predeclared types. I'm
suggesting that there is a way to implement generics that does not
require any subtyping.

Your suggestion implies that the language must define interfaces for
all the predeclared types. It also implies that people writing
generic functions must only use methods, and may not use operators.
Both ideas could be adopted but to me they look less than ideal.

Ian

Ian Lance Taylor

unread,
Dec 1, 2014, 11:59:33 AM12/1/14
to Theemathas Chirananhavat, golang-nuts, Dave Cheney, Chandra Sekar S
On Mon, Dec 1, 2014 at 5:28 AM, Theemathas Chirananhavat
<theem...@gmail.com> wrote:
>
> type T1 int64
> type T2 float64
>
> //whatever methods here
>
> var x T1 = 1000
> var y T2 = 2000.5
>
> var z int8 := Max(x,y).(int8) //whoops
>
> Generics aren't that simple

The hypothetical Max function we've been discussing uses the same
generic type for both parameters. Attempting to call it with
arguments of different types must be a compile-time type error. I
don't see that as a conceptual problem. In practice of course it
would be essential to produce a good error message.

Ian

Ian Lance Taylor

unread,
Dec 1, 2014, 12:02:11 PM12/1/14
to Jesper Louis Andersen, Dave Cheney, Chandru, Go Mailing List
On Mon, Dec 1, 2014 at 5:43 AM, Jesper Louis Andersen
<jesper.lou...@gmail.com> wrote:
>
> On Mon, Dec 1, 2014 at 1:57 AM, Ian Lance Taylor <ia...@golang.org> wrote:
>>
>> I think that one way to handle this would be to extend the structural
>> typing of interfaces. We could say that a generic function Max can
>> only be instantiated by types that support all the operations used in
>> the body of the function. So if you write
>>
>> func Max(a, b T) T {
>> if a > b {
>> return a
>> }
>> return b
>> }
>
>
> This looks very much like type classes in Haskell. However, you may have to
> nominate the relationship.

I'm fairly confident that if that is what generics requires, then they
will never be implemented in Go. Go explicitly eschews this kind of
type based programming.

Ian

atd...@gmail.com

unread,
Dec 1, 2014, 12:14:22 PM12/1/14
to golan...@googlegroups.com, theem...@gmail.com, da...@cheney.net, chand...@gmail.com
And even for instance with the same generic interface, I believe such a type assertion is a compile-time error : int8 does not satisfy the interface.

atd...@gmail.com

unread,
Dec 1, 2014, 12:17:27 PM12/1/14
to golan...@googlegroups.com, ia...@golang.org, da...@cheney.net, chand...@gmail.com
I don't think it needs to be that complicated.
See Matt Sherman's post.

Ian

unread,
Dec 1, 2014, 12:26:22 PM12/1/14
to golan...@googlegroups.com, jesper.lou...@gmail.com, da...@cheney.net
I'm not so sure that list of requirements is needed. If we apply some of your questions to Go, for instance, it's easy to conclude that Go is not needed!


1. How many problems does "generics" actually solve?
2. What are those problems?
-- Generics solve problems across types; a quantifiable list of those problems is impossible to build.

3. How common are these problems in programs? (Do 1%, 5%, 10%, 25% of programs need it? What kinds of programs need it?)
-- Who knows? How is it possible to quantify such a number? (Besides extensive architectural analysis?)

4. Is "generics" the best solution to those problems?
-- Who knows? Sometimes they might be, sometimes they won't be. 

5. What will the longer term effect will be on the generics?
-- Again, something that is difficult to quantify.

Generics solve a set of problems; to quote Wikipedia's "Generics In Java article (http://en.wikipedia.org/wiki/Generics_in_Java): 

    They allow "a type or method to operate on objects of various types while providing compile-time type safety."

The implementation of any solution might or might not be better because of generics, a language might be more or less useful because of generics, but they exist in Java and C++ for a reason. That reason generally boils down to "so I don't have to keep writing code that does the same stuff over and over and over". The example that's used elsewhere in this thread is a trivial example, but get to any mildly complex example (web apps contain plenty of such instances), and generics start to look *very* appealing. Let the compiler worry about the differences and let the coder think about the interesting stuff, not implementing the same function over and over with copy-and-paste (or worse, retyping the same thing over and over...) Why should *I* have to rewrite code to solve the same problem for each data type when the compiler is so much better at such mundane and mind-numbing stuff?

It strikes me that Go doesn't have generics not because they're not useful, but because the designers don't like them! Which is basically what they've said in a number of forums and in other threads about generics.

/Ian

Bakul Shah

unread,
Dec 1, 2014, 12:36:31 PM12/1/14
to Ian Lance Taylor, golang-nuts, Matt Sherman, Chandra Sekar S, Dave Cheney

On Dec 1, 2014 8:50 AM, Ian Lance Taylor <ia...@golang.org> wrote:
>
> On Sun, Nov 30, 2014 at 7:20 PM, Matt Sherman <mwsh...@gmail.com> wrote:
> >
> > That's an intriguing approach.
> >
> > For that last bit:
> >
> > max := Max<int>
> >
> > How to handle it with multiple types in the func? I suppose Max<...argTypes,
> > returnType>.

You can just use a type coercion:

max := (func (int) int)(Max)

This is more or less what the compiler would have to do to handle, e.g., Max(5, 6).

> There are indeed many details to consider.  This is really just the
> first level of detail.

Indeed.

Benjamin Measures

unread,
Dec 1, 2014, 12:43:04 PM12/1/14
to golan...@googlegroups.com, jesper.lou...@gmail.com, da...@cheney.net
On Monday, 1 December 2014 17:26:22 UTC, Ian wrote:
It strikes me that Go doesn't have generics not because they're not useful, but because the designers don't like them! Which is basically what they've said in a number of forums and in other threads about generics.

References please.

They've given very good reasons for not /yet/ having generic types in the language:
We haven't yet found a design that gives value proportionate to the complexity, although we continue to think about it.

atd...@gmail.com

unread,
Dec 1, 2014, 12:58:06 PM12/1/14
to golan...@googlegroups.com, jesper.lou...@gmail.com, da...@cheney.net
(Ian) designers don't like them (the solutions in the other languages) == (FAQ) design that gives value not yet found.
I'd guess but can't speak for Ian. :)

Nate Finch

unread,
Dec 1, 2014, 2:05:33 PM12/1/14
to golan...@googlegroups.com
I wish the pro-generics people on this list would respond to the multiple suggestions that they use one of the several existing code generators out there.  This effectively gives you templates in Go just like they are implemented in several other languages, it's just a manual step instead of an automatic step.  There's even the go generate command in 1.4 to make it a more standardized process.  Thus, you can have your set of ints and your set of strings, and define a bunch of generic set theory logic.

Personally, I do not want generics.  I hope they never come to Go.  I've spent almost my entire career writing software in languages with generics, and it inevitably makes the code more complicated and more difficult to understand for very minimal benefits in the real world.
It is loading more messages.
0 new messages