CL https://golang.org/cl/22057 mentions this issue.

Let me preemptively remind everybody of our https://golang.org/wiki/NoMeToo policy. The emoji party is above.

There is Summary of Go Generics Discussions, which tries to provide an overview of discussions from different places. It also provides some examples how to solve problems, where you would want to use generics.

There are two "requirements" in the linked proposal that may complicate the implementation and reduce type safety:

• Define generic types based on types that are not known until they are instantiated.
• Do not require an explicit relationship between the definition of a generic type or function and its use. That is, programs should not have to explicitly say type T implements generic G.

These requirements seem to exclude e.g. a system similar to Rust's trait system, where generic types are constrained by trait bounds. Why are these needed?

It becomes tempting to build generics into the standard library at a very low level, as in C++ std::basic_string<char, std::char_traits, std::allocator >. This has its benefits—otherwise nobody would do it—but it has wide-ranging and sometimes surprising effects, as in incomprehensible C++ error messages.

The problem in C++ arises from type checking generated code. There needs to be an additional type check before code generation. The C++ concepts proposal enables this by allowing the author of generic code to specify the requirements of a generic type. That way, compilation can fail type checking before code generation and simple error messages can be printed. The problem with C++ generics (without concepts) is that the generic code is the specification of the generic type. That's what creates the incomprehensible error messages.

Generic code should not be the specification of a generic type.

@tamird It is an essential feature of Go's interface types that you can define a non-interface type T and later define an interface type I such that T implements I. See https://golang.org/doc/faq#implements_interface . It would be inconsistent if Go implemented a form of generics for which a generic type G could only be used with a type T that explicitly said "I can be used to implement G."

I'm not familiar with Rust, but I don't know of any language that requires T to explicitly state that it can be used to implement G. The two requirements you mention do not mean that G can not impose requirements on T, just as I imposes requirements on T. The requirements just mean that G and T can be written independently. That is a highly desirable feature for generics, and I can not imagine abandoning it.

@ianlancetaylor https://doc.rust-lang.org/book/traits.html explains Rust's traits. While I think they're a good model in general, they would be a bad fit for Go as it exists today.

@sbunce I also thought that concepts were the answer, and you can see the idea scattered through the various proposals before the last one. But it is discouraging that concepts were originally planned for what became C++11, and it is now 2016, and they are still controversial and not particularly close to being included in the C++ language.

Would there be value on the academic literature for any guidance on evaluating approaches?

The only paper I've read on the topic is Do developers benefit from generic types? (paywall sorry, you might google your way to a pdf download) which had the following to say

Consequently, a conservative interpretation of the experiment
is that generic types can be considered as a tradeoff
between the positive documentation characteristics and the
negative extensibility characteristics. The exciting part of
the study is that it showed a situation where the use of a
(stronger) static type system had a negative impact on the
development time while at the same time the expected bene-
fit – the reduction of type error fixing time – did not appear.
We think that such tasks could help in future experiments in
identifying the impact of type systems.

I also see #15295 also references Lightweight, flexible object-oriented generics.

If we were going to lean on academia to guide the decision I think it would be better to do an up front literature review, and probably decide early if we would weigh empirical studies differently from ones relying on proofs.

Please see: http://dl.acm.org/citation.cfm?id=2738008 by Barbara Liskov:

The support for generic programming in modern object-oriented programming languages is awkward and lacks desirable expressive power. We introduce an expressive genericity mechanism that adds expressive power and strengthens static checking, while remaining lightweight and simple in common use cases. Like type classes and concepts, the mechanism allows existing types to model type constraints retroactively. For expressive power, we expose models as named constructs that can be defined and selected explicitly to witness constraints; in common uses of genericity, however, types implicitly witness constraints without additional programmer effort.

I think what they did there is pretty cool - I'm sorry if this is the incorrect place to stop but I couldn't find a place to comment in /proposals and I didn't find an appropriate issue here.

It could be interesting to have one or more experimental transpilers - a Go generics source code to Go 1.x.y source code compiler.
I mean - too much talk/arguments-for-my-opinion, and no one is writing source code that try to implement some kind of generics for Go.

Just to get knowledge and experience with Go and generics - to see what works and what doesn't work.
If all Go generics solutions aren't really good, then; No generics for Go.

Can the proposal also include the implications on binary size and memory footprint? I would expect that there will be code duplication for each concrete value type so that compiler optimizations work on them. I hope for a guarantee that there will be no code duplication for concrete pointer types.

I offer a Pugh Decision matrix. My criteria include perspicuity impacts (source complexity, size). I also forced ranked the criteria to determine the weights for the criteria. Your own may vary of course. I used "interfaces" as the default alternative and compared this to "copy/paste" generics, template based generics (I had in mind something like how D language works), and something I called runtime instantiation style generics. I'm sure this is a vast over simplification. Nonetheless, it may spark some ideas on how to evaluate choices... this should be a public link to my Google Sheet, here

Pinging @yizhouzhang and @andrewcmyers so they can voice their opinions about genus like generics in Go. It sounds like it could be a good match :)

The generics design we came up with for Genus has static, modular type checking, does not require predeclaring that types implement some interface, and comes with reasonable performance. I would definitely look at it if you're thinking about generics for Go. It does seem like a good fit from my understanding of Go.

Here is a link to the paper that doesn't require ACM Digital Library access:
http://www.cs.cornell.edu/andru/papers/genus/

The Genus home page is here: http://www.cs.cornell.edu/projects/genus/

We haven't released the compiler publicly yet, but we are planning to do that fairly soon.

Happy to answer any questions people have.

In terms of @mandolyte's decision matrix, Genus scores a 17, tied for #1. I would add some more criteria to score, though. For example, modular type checking is important, as others such as @sbunce observed above, but template-based schemes lack it. The technical report for the Genus paper has a much larger table on page 34, comparing various generics designs.

I just went through the whole Summary of Go Generics document, which was a helpful summary of previous discussions. The generics mechanism in Genus does not, to my mind, suffer from the problems identified for C++, Java, or C#. Genus generics are reified, unlike in Java, so you can find out types at run time. You can also instantiate on primitive types, and you don't get implicit boxing in the places you really don't want it: arrays of T where T is a primitive. The type system is closest to Haskell and Rust -- actually a bit more powerful, but I think also intuitive. Primitive specialization ala C# is not currently supported in Genus but it could be. In most cases, specialization can be determined at link time, so true run-time code generation would not be required.

CL https://golang.org/cl/22163 mentions this issue.

A way to constrain generic types that doesn't require adding new language concepts: https://docs.google.com/document/d/1rX4huWffJ0y1ZjqEpPrDy-kk-m9zWfatgCluGRBQveQ/edit?usp=sharing.

Genus looks really cool and it's clearly an important advancement of the art, but I don't see how it would apply to Go. Does anyone have a sketch of how it would integrate with the Go type system/philosophy?

The issue is the go team is stonewalling attempts. The title clearly states the intentions of the go team. And if that wasn't enough to deter all takers, the features demanded of such a broad domain in the proposals by ian make it clear that if you want generics then they don't want you. It is asinine to even attempt dialog with the go team. To those looking for generics in go, I say fracture the language. Begin a new journey- many will follow. I've already seen some great work done in forks. Organize yourselves, rally around a cause

If anyone wants to try to work up a generics extension to Go based on the Genus design, we are happy to help. We don't know Go well enough to produce a design that harmonizes with the existing language. I think the first step would be a straw-man design proposal with worked-out examples.

@andrewcmyers hoping that @ianlancetaylor will work with you on that. Just having some examples to look at would help a lot.

Go's core team has shown in the past that it is willing to say "no". That generics took so long to deliberate over is in my books a good thing.

I think that, too.

But my experience told me too often the opposite. Initial designs of generics tend to be extended over time arguably complicating the language, e.g. Rust/Swift.
I wish the go team the best to hold on their ideals to leave the language as simple as possible.

Rust is not overcomplicated. It is as complicated as it needs to be for the things it needs to do. Not everything can be easy.

@iio7

I therefore propose that the pro-generics camp provide real examples of problems they have faced that was such a big issue that it justifies adding generics to Go.

If all we're presented are these small theoretical examples of sorting lists, etc., then clearly this is nothing but hype that needs to go away.

I thought the newest design draft document had fairly good examples. Of course they're going to be small since it's a design draft. As far as sorting lists or the rest of the draft document examples being "toys" goes, I'm really not sure what you expect? It's a language feature that's under active development, nobody's got a massive case study to give you yet.

But, off the top of my head, these are some of the things I'm looking forwards to:

• type-safe containers. Mentioned in the draft too but this is really something I'm personally looking forward to and figure will have a big positive impact on code and API quality. "Type safe containers" sounds anticlimactic, but it's the poster child for generics and for a good reason. Sure, sync.Map, sync.Pool, caches, repository types etc etc work just "fine" if you spray interface{} all over the place, but that's not really much of a solution. Throws compile-time type safety out the window and I can't imagine all those conversions are free (although definitely not going to be your biggest performance worry either). These are probably one of the biggest offenders when it comes to being forced to resort to interface{}; any type that you want to be able to either hold or retrieve / save generic types is currently either going to be hand-rolled boilerplate for each "instantiation", compile time type unsafe with reflect and/or interface{}, or a go generate template hack. This covers everything from database drivers to sync.Map to loggers to parsers to what have you. As said, this is what I'm personally really looking forward to since it has wide-reaching implications and is pretty much what generics are all about
• also, better tooling for channels. Generics allow for, well, generic packages that provide things like eg. fan-out, fan-in, broadcast, whatever. Channel patterns that are even slightly more complex than unidirectional point-to-point take a lot of boilerplate nowadays. Channels and goroutines practically beg for a flow-based / reactive programming model
• less use for reflect, meaning compile time type safety and less of this:

		case int, int8, int16, int32, int64:
			// todo: unroll these instead of reflect...
			oe.AddInt64(k, reflect.ValueOf(v).Int())
		case uint, uint8, uint16, uint32, uint64:
			oe.AddUint64(k, reflect.ValueOf(v).Uint())

• map / filter / reduce that work with all slice types + other functional patterns, although I have a sneaking suspicion you're not necessarily a fan. Personally I find them incredibly handy, and iterating with for (even with range) feels extremely clunky when doing actual list processing

It's honestly not all that hard to come up with good use cases for generics. It's a tool like any other; of course it can be abused to produce terrible code, but with that rationale we might as well just go back to BASIC. In general I'm not a fan of the slippery slope argument. There's absolutely no proof that generics (which plenty of other languages implemented without bursting into flames and keeling over into the ocean) are going to somehow be detrimental to the language in and of themselves, and this idea that now the gates are open and the screaming hordes will overrun the Go dev team with demands for obscure features is a bit ridiculous. While I'm not a fan of Java or C++, but the problems with those languages aren't due to generics. Doubt anybody wants to see Go become the next C++, but being as simple as possible doesn't mean no new language features ever – it's a balancing act, and the newest generics draft is actually fairly nice and simple.

Hi, I am a newbie in Go (but I wrote considerable amount of C). My understanding to this language is very limited, but I love the simplicity and disciplined principle of this language. I recall one of Go creators said it is desired in this language to have one way and only just one way to achieve a thing. I show up here asking if anyone can tell me why we choose not to use Interface to address the issue where we find troublesome if we do not have generics.

I googled about why Go needs generics, the first thing show up in the results is a blog post from Ian Lance Taylor. His illustrating example was that it seems difficult to write a general "reverse" function that could handle different types:

func ReverseInts(s []int) {
    first := 0
    last := len(s) - 1
    for first < last {
        s[first], s[last] = s[last], s[first]
        first++
        last--
    }
}

func ReverseStrings(s []string) {
    first := 0
    last := len(s) - 1
    for first < last {
        s[first], s[last] = s[last], s[first]
        first++
        last--
    }
}

I pondered upon this and wrote a Go Interface solution:

package main
 
/* define an interface being able to perform "reverse" */
 
type array interface {
        at(idx int) interface{}
        swap(i, j int)
        length() int
}
 
func array_reverse(a array) {
        mid := a.length() / 2
        for idx := 0; idx < mid; idx++ {
                a.swap(idx, a.length() - idx - 1)
        }
}
 
/* an example struct that implements array type */
 
type Cat struct {
        age int
        name string
}
 
type Cats []Cat
 
func (cats Cats) length() int {
        return len(cats)
}
 
func (cats Cats) swap(i, j int) {
        cats[i], cats[j] = cats[j], cats[i]
}
 
func (cats Cats) at(idx int) interface{} {
        return cats[idx]
}

func main() {
        var cats Cats
        cats = []Cat{{3, "Leo"}, {2, "Ketty"}, {10, "Tom"}}
        array_reverse(array(cats))
}

Admittedly, using interface we need to implement a few functions (maybe we can reduce the set of interface methods required here if using reflection, but for this example, I find it easier to understand and keep the code as it is) for every new type of object in order for them to be passed into reverse() function.

However, the overhead for a new container implementation to add those common interface is not that bad? Especially considering that to introduce generics would potentially add another way to bloat the code and greatly make the language and its tool chains more complex.

As newbie as I am, please remind me here if you think there is reason generics will be a better choice than my example interface implementation above (or there are other cases I have not considered yet?). I will be very thankful to hear because I believe there maybe points I miss.

@t-k- that's pretty much how the current stdlib does sorting. But generics would make it statically typed meaning no empty interfaces. Also with polymorphism you can create data structures which would be more difficult or impractical to use with just interfaces.

Two points to consider:

1. Type safety:
   Imagine the cats array get returned from array_reverse but there is an additional method in Cats[] which isn't available in the interface array.
   So you are required to cast array back to cats in order to execute the missing method.
   Of course, you can extend your array interface to support cats, but this isn't how it usually works.
   Library writer and app writer are different persons and the library writer can't know all possible methods of a concrete type implementing the interface. Moreover, his goal is to write his interface very minimalistic in order to cover most if not all the possible cases.

2. Performance
   Dealing with interfaces requires boxing whereas with generics, boxing can be optimized out, but it doesn't have to.

@TotallyGamerJet Thank you for your reply. I am really new into Go, could you elaborate more?

1. what is "no empty interface", for the reverse() interface to work, you need to have a super set of methods to implement it.
2. Do you have an easy to understand data structure in your mind right now that would be easier to write with polymorphism, in your view?

@sighoya Yes I can see your second point, I remember C++ template is also efficient for similar reason? However, as most of the people against Generics, simplicity is also a thing.

As for your first point, I am not sure if I understand it. Can I just use cats as Cats type for whatever next steps where Cats methods are required? array interface just need those methods for reverse(), if you want other functionalities irrelevant to array, just pass the original cats to other functions, and write whatever is needed to do, isn't that the point of interface?

To your first point, I am a little unclear, why array interface wants something to support cats?

Afaict, your array interface wants to support any concrete (non interface) type implementing sort functionality. The concrete type itself can provide more than these methods.

Imagine there is a function

f(array Array) Array {doSomething(array); return array}

What is, if I call f with the cats array and want to execute a method of cats, which doesn't exists in the Array interface, on the returned value of f?
It just doesn't compile because the compiler doesn't know if cats get returned from f:?

type Array interface
{
method1(...){...}
}

type cats struct
{
method1(...){...}
method2(...){...}
}

f(cats).method2() //doesn't compile

Without generics, you are forced to cast, with generics you know that cats get returned because the type parameter is instantiated to cats:

f[T:Array](array T) T {doSomething(array); return array;}
f(cats).method2(...); ==> //works as `f` gets specialized to `f:Cats=>Cats`

A better example is the List interface List[T]. With generics you know that after adding an element to a List the element type doesn't change. Without generics, you don't know that, so you need a cast back for any type != interface{}, List to List[int]

@t-k- what I mean is that your implementation can't handle built-in types such as int and string without creating an extra type. And most of the methods implementing the array interface are nearly identical which doesn't really solve the problem of duplication it just moves it.

The simplest data structure I can think of is a Stack. Which would store a slice of some Type and can return the static type when pop is called. And would take the type in when pushed. So it would be impossible to push an int onto a Stack of strings. This is impossible if the stack is made up of interfaces

@sighoya Thank you for putting a more concrete example here. I really appreciate. But if you want to call method2 on Cats type, in many cases I think there are instance of Cats type already somewhere just like what is in my example code above, in these cases you just use cats as defined in the scope, no need to cast types.

To your List[T] example, similarly, I also do not want to use the return value from say, List push(), to do things later on that are irrelevant to List.

@TotallyGamerJet I agree it wouldn't be suitable for built-in types (without a wrapper), but we can add code for built-in types later (by core team maybe?) if we find some manipulation in foo library (pretend it is reverse() but we do not have it in early language versions) is getting really popular and useful, this way, 1) it does not break compatibility of old code and 2) no need to add generics such that every function designer will ponder between options.

Your second point is interesting to me, I never think about this (I have not wrote much generic code for quite some time):

The simplest data structure I can think of is a Stack. Which would store a slice of some Type and can return the static type when pop is called. And would take the type in when pushed. So it would be impossible to push an int onto a Stack of strings. This is impossible if the stack is made up of interfaces

But I imagine we can still design a Stack that is able to be pushed an arbitrary variable sized objects (say it is called varLenItem), with a push function like:

func (s Stack) push(obj varLenItem) {
...
}

You will need to have a size() interface method implemented on varLenItem though. And maybe Stack needs to record all the boundaries or it needs to append delimiters between varLenItem.

This is getting a little tricky since normally you want a linked list to store strings, but just assume you want such a Stack, I think you still can do it with interface. I will try it myself and get back to you in this thread.

in many cases I think there are instance of Cats type already somewhere

In your codebase, yes, but probably not in the codebase of the library writer. It is impossible to know all concrete types a library user may provide.

To your List[T] example, similarly, I also do not want to use the return value from say, List push(),

Well okay, that works in case the returned type stays the same with the argument type.

But what about a method taking two lists and returns a list containing the elements of both lists joined into tuples?:

zip(list1 List, list2 List) List {return List(tuple(list1[0],list2[0]),tuple(list1[1],list2[1]),...)}

How to access the elements in the tuples out of the returned list safely?

How to access the elements in the tuples out of the returned list safely?

@sighoya then you just split the zip function (into something like make_tuples() and cat_typles())? because that is a signal the zip() function has some useful thing in its body? Also, with generics, how can you really avoid the problem?

then you just split the zip function (into something like make_tuples() and cat_typles())?

But then you have to write the zip function for every List type: zip_Cat, zip_Dog, zip_CatDog

Also, with generics, how can you really avoid the problem?

zip[S,T](list1 List[S], list2 List[T]) List[Tuple[S,T]] {return List[Tuple[S,T]](tuple(list1[0],list2[0]),tuple(list1[1],list2[1]),...)}

Extracting any element out of the actual list is of type Tuple[S,T], retrieve the first element out of the Tuple is of type S, the latter of type T.

@sighoya So your point is how to make general functions like zip_Any() rather than how to obtain some intermediate results in its body. I see. So if all we want is to concatenate both T and S into a List, it goes back to the question whether we can do it in an "interface way" (e.g., by having ListElement interface for List cat() function)? My guess is yes.

If casting things to ListElement makes it unsafe, then you are picking up the wrong type of instance? I think we can still cast a thing to ListElement for the purpose of pushing it into a List, at the same time using its original type (defined previously somewhere) for other things irrelevant to List operations. Even if the previous object of origin type is lost, we can use reflection to test whether it is of type S or T when we pop an item from the List in your example.

@TotallyGamerJet Hi here is my naive and inefficient way to implement a variable length stack using interface:

package main

type VarLenItem interface {
	Bytes() []byte
}

type Stack struct {
	continousSpace []byte
	delimitersPtrs []int
}

func (s *Stack) Push(item VarLenItem) {
	for _, b := range item.Bytes() {
		s.continousSpace = append(s.continousSpace, b)
	}
	s.delimitersPtrs = append(s.delimitersPtrs, len(s.continousSpace))
}

/* here is an example implementation for string */

type strVarLenItem struct {
	content string
}

func (str strVarLenItem) Bytes() []byte {
	return []byte(str.content)
}

func main() {
	a := "foo"
	b := "barbaz"

	var stack Stack
	var item strVarLenItem = strVarLenItem{a}
	stack.Push(item)
	item = strVarLenItem{b}
	stack.Push(item)
}

Similarly, you can have an intVarLenItem for int to be pushed to such stack.

As you can see I am really new in Go, I am sure there are better ways to append byte stream, but my point it is possible to implement it in an easy-to-understand interface as long as we get the abstraction layer right. And the bonus of using interface is we can know what methods exactly a container wants from us in order to perform its operations, this helps a new data type implementation programmer to get a sense how efficient it is for "my type of data" to be manipulated by a datastructure container.

Keep Simple Keep Go No Generic

The real world is very well! There are no generics and not need it (Generics are not required in the real world).

Some things that use generics may look simple, but keep some coding can be done as well (Generics look good but are not required).

Something that would be a game-changer for Go instrumentation area would be to have a generic-based alternative to reflect.MakeFunc() so that we could generate functions according to a function type at compilation time instead of using run-time reflection based on the function type descriptor. 99% of the time, we know what is the target function type, but we use reflect.MakeFunc() as a glue/bridge between generic instrumentation features with the instrumented function. Code-generation could do the job to avoid MakeFunc in the cases we know the target function types, but I'd rather avoid the complexity of maintaining such code-generation tool.

I can try to provide some concrete examples if necessary.

A specific proposal for adding generic programming facilities to Go has been accepted: #43651. Therefore, I am going to close this issue.

Thanks for all the discussion, thoughts, and suggestions over the years.

This is a general issue about adding generics to Go. It also has more than 800 comments already. Specific details like how the reflect package should change for a specific generics proposal should not be handled here, they should be handled as part of the specific proposal or as separate issues on their own. Thanks.

That said, the accepted generics proposal does not require any changes to the reflect package. See https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#reflection.