proposal: spec: generic programming facilities

[adg]

This issue proposes that Go should support some form of generic programming. It has the Go2 label, since for Go1.x the language is more or less done.

Accompanying this issue is a general generics proposal by @ianlancetaylor that includes four specific flawed proposals of generic programming mechanisms for Go.

The intent is not to add generics to Go at this time, but rather to show people what a complete proposal would look like. We hope this will be of help to anyone proposing similar language changes in the future.

[gopherbot]

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

[bradfitz]

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

[egonelbre]

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.

[tamird]

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?

[sbunce]

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.

[ianlancetaylor]

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

[alex]

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

[ianlancetaylor]

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

[joho]

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 https://github.com/golang/go/issues/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.

[benjamingr]

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.

[larsth]

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.

[michael-schaller]

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.

[mandolyte]

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

[benjamingr]

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 :)

[andrewcmyers]

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.

[andrewcmyers]

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.

[andrewcmyers]

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.

[gopherbot]

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

[jba]

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.

[jimmyfrasche]

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?

[sprstnd]

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

[andrewcmyers]

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.

[mandolyte]

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

[ianlancetaylor]

I've read through the Genus paper. To the extent that I understand it, it seems nice for Java, but doesn't seem like a natural fit for Go.

One key aspect of Go is that when you write a Go program, most of what you write is code. This is different from C++ and Java, where much more of what you write is types. Genus seems to be mostly about types: you write constraints and models, rather than code. Go's type system is very very simple. Genus's type system is far more complex.

The ideas of retroactive modeling, while clearly useful for Java, do not seem to fit Go at all. People already use adapter types to match existing types to interfaces; nothing further should be needed when using generics.

It would be interesting to see these ideas applied to Go, but I'm not optimistic about the result.

[andrewcmyers]

I'm not a Go expert, but its type system doesn't seem any simpler than pre-generics Java. The type syntax is a bit lighter-weight in a nice way but the underlying complexity seems about the same.

In Genus, constraints are types but models are code. Models are adapters, but they adapt without adding a layer of actual wrapping. This is very useful when you want to, say, adapt an entire array of objects to a new interface. Retroactive modeling lets you treat the array as an array of objects satisfying the desired interface.

[jimmyfrasche]

I wouldn't be surprised if it were more complicated than (pre-generics) Java's in a type theoretic sense, even though it's simpler to use in practice.

Relative complexity aside, they're different enough that Genus couldn't map 1:1. No subtyping seems like a big one.

If you're interested:

The briefest summary of the relevant philosophical/design differences I mentioned are contained in the following FAQ entries:

• https://golang.org/doc/faq#implements_interface
• https://golang.org/doc/faq#overloading
• https://golang.org/doc/faq#covariant_types
• https://golang.org/doc/faq#variant_types

Unlike most languages, the Go spec is very short and clear about the relevant properties of the type system start at https://golang.org/ref/spec#Constants and go straight through until the section titled "Blocks" (all of which is less than 11 pages printed).

[andrewcmyers]

Unlike Java and C# generics, the Genus generics mechanism is not based on subtyping. On the other hand, it seems to me that Go does have subtyping, but structural subtyping. That is also a good match for the Genus approach, which has a structural flavor rather than relying on predeclared relationships.

[davecheney]

I don't believe that Go has structural subtyping.

While two types whose underlying type is identical are therefore identical can be substituted for one another, https://play.golang.org/p/cT15aQ-PFr

This does not extend to two types who share a common subset of fields, https://play.golang.org/p/KrC9_BDXuh.

On Thu, Apr 28, 2016 at 1:09 PM, Andrew Myers notifications@github.com wrote:

Unlike Java and C# generics, the Genus generics mechanism is not based on subtyping. On the other hand, it seems to me that Go does have subtyping, but structural subtyping. That is also a good match for the Genus approach, which has a structural flavor rather than relying on predeclared relationships.

— You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub https://github.com/golang/go/issues/15292#issuecomment-215298127

[andrewcmyers]

Thanks, I was misinterpreting some of the language about when types implement interfaces. Actually, it looks to me as if Go interfaces, with a modest extension, could be used as Genus-style constraints.

[benjamingr]

That's exactly why I pinged you, genus seems like a much better approach than Java/C# like generics.

[egonelbre]

There were some ideas with regards to specializing on the interface types; e.g. the package templates approach "proposals" 1 2 are examples of it.

tl;dr; the generic package with interface specialization would look like:

package set
type E interface { Equal(other E) bool }
type Set struct { items []E }
func (s *Set) Add(item E) { ... }

Version 1. with package scoped specialization:

package main
import items set[[E: *Item]]

type Item struct { ... }
func (a *Item) Equal(b *Item) bool { ... }

var xs items.Set
xs.Add(&Item{})

Version 2. the declaration scoped specialization:

package main
import set

type Item struct { ... }
func (a *Item) Equal(b *Item) bool { ... }

var xs set.Set[[E: *Item]]
xs.Add(&Item{})

The package scoped generics will prevent people from significantly abusing the generics system, since the usage is limited to basic algorithms and data-structures. It basically prevents building new language-abstractions and functional-code.

The declaration scoped specialization has more possibilities at the cost making it more prone to abuse and it is more verbose. But, functional code would be possible, e.g:

type E interface{}
func Reduce(zero E, items []E, fn func(a, b E) E) E { ... }

Reduce[[E: int]](0, []int{1,2,3,4}, func(a, b int)int { return a + b } )
// there are probably ways to have some aliases (or similar) to make it less verbose
alias ReduceInt Reduce[[E: int]]
func ReduceInt Reduce[[E: int]]

The interface specialization approach has interesting properties:

• Already existing packages using interfaces would be specializable. e.g. I would be able to call sort.Sort[[Interface:MyItems]](...) and have the sorting work on the concrete type instead of interface (with potential gains from inlining).
• Testing is simplified, I only have to assure that the generic code works with interfaces.
• It's easy to state how it works. i.e. imagine that [[E: int]] replaces all declarations of E with int.

But, there are verbosity issues when working across packages:

type op
import "set"

type E interface{}
func Union(a, b set.Set[[set.E: E]]) set.Set[[set.E: E]] {
    result := set.New[[set.E: E]]()
    ...
}

Of course, the whole thing is simpler to state than to implement. Internally there are probably tons of problems and ways how it could work.

PS, to the grumblers on slow generics progress, I applaud the Go Team for spending more time on issues that have a bigger benefit to the community e.g. compiler/runtime bugs, SSA, GC, http2.

[jba]

@egonelbre your point that package-level generics will prevent "abuse" is a really important one that I think most people overlook. That plus their relative semantic and syntactic simplicity (only the package and import constructs are affected) make them very attractive for Go.

[jba]

@andrewcymyers interesting that you think Go interfaces work as Genus-style constraints. I would have thought they still have the problem that you can't express multi-type-parameter constraints with them.

One thing I just realized, however, is that in Go you can write an interface inline. So with the right syntax you could put the interface in scope of all the parameters and capture multi-parameter constraints:

type [V, E] Graph [V interface { Edges() E }, E interface { Endpoints() (V, V) }] ...

I think the bigger problem with interfaces as constraints is that methods are not as pervasive in Go as in Java. Built-in types do not have methods. There is no set of universal methods like those in java.lang.Object. Users don't typically define methods like Equals or HashCode on their types unless they specifically need to, because those methods don't qualify a type for use as map keys, or in any algorithm that needs equality.

(Equality in Go is an interesting story. The language gives your type "==" if it meets certain requirements (see https://golang.org/ref/spec#Logical_operators, search for "comparable"). Any type with "==" can serve as a map key. But if your type doesn't deserve "==", then there is nothing you can write that will make it work as a map key.)

Because methods aren't pervasive, and because there is no easy way to express properties of the built-in types (like what operators they work with), I suggested using code itself as the generic constraint mechanism. See the link in my comment of April 18, above. This proposal has its problems, but one nice feature is that generic numeric code could still use the usual operators, instead of cumbersome method calls.

The other way to go is to add methods to types that lack them. You can do this in the existing language in a much lighter way than in Java:

type Int int func (i Int) Less(j Int) bool { return i < j }

The Int type "inherits" all the operators and other properties of int. Though you have to cast between the two to use Int and int together, which can be a pain.

Genus models could help here. But they would have to be kept very simple. I think @ianlancetaylor was too narrow in his characterization of Go as writing more code, fewer types. The general principal is that Go abhors complexity. We look at Java and C++ and are determined never to go there. (No offense.)

So one quick idea for a model-like feature would be: have the user write types like Int above, and in generic instantiations allow "int with Int", meaning use type int but treat it like Int. Then there is no overt language construct called model, with its keyword, inheritance semantics, and so on. I don't understand models well enough to know whether this is feasible, but it is more in the spirit of Go.

[andrewcmyers]

@jba We certainly agree with the principle of avoiding complexity. "As simple as possible but no simpler." I would probably leave some Genus features out of Go on those grounds, at least at first.

One of the nice things about the Genus approach is that it handles built-in types smoothly. Recall that primitive types in Java don't have methods, and Genus inherits this behavior. Instead, Genus treats primitive types as if they had a fairly large suite of methods for the purpose of satisfying constraints. A hash table requires that its keys can be hashed and compared, but all the primitive types satisfy this constraint. So type instantiations like Map[int, boolean] are perfectly legal with no further fuss. There is no need to distinguish between two flavors of integers (int vs Int) to achieve this. However, if int were not equipped with enough operations for some uses, we would use a model almost exactly like the use of Int above.

Another thing worth mentioning is the idea of "natural models" in Genus. You ordinarily don't have to declare a model to use a generic type: if the type argument satisfies the constraint, a natural model is automatically generated. Our experience is that this is the usual case; declaring explicit, named models is normally not needed. But if a model were needed — for example, if you wanted to hash ints in a nonstandard way — then the syntax is similar to what you suggested: Map[int with fancyHash, boolean]. I would argue that Genus is syntactically light in normal use cases but with power in reserve when needed.

[andrewcmyers]

@egonelbre What you're proposing here looks like virtual types, which are supported by Scala. There is an ECOOP'97 paper by Kresten Krab Thorup, "Genericity in Java with virtual types", which explores this direction. We also developed mechanisms for virtual types and virtual classes in our work ("J&: nested intersection for scalable software composition", OOPSLA'06).

[mandolyte]

Since literal initializations are pervasive in Go, I had to wonder what a function literal would look like. I suspect that the code to handle this largely exists in Go generate, fix, and rename.Maybe it will inspire someone :-)

// the (generic) func type definition type Sum64 func (X, Y) float64 { return float64(X) + float64(Y) }

// instantiate one, positionally i := 42 var j uint = 86 sum := &Sum64{i, j}

// instantiate one, by named parameter types sum := &Sum64{ X: int, Y: uint}

// now use it... result := sum(i, j) // result is 128

[go-li]

Ian's proposal demands too much. We cannot possibly develop all the features at-once, it will exist in an unfinished state for many months.

In the meantime, the unfinished project cannot be called official Go language until done because that will risk fragmenting the ecosystem.

So the question is how to plan this.

Also a huge part of the project would be developing the reference corpus. developing the actual generic collections, algorithms and other things in such a way we all agree on that they are idiomatic, while using the new go 2.0 features

[md2perpe]

A possible syntax?

// Module defining generic type
module list(type t)

type node struct {
    next *node
    data t
}

// Module using generic type:
import (
    intlist "module/path/to/list" (int)
    funclist "module/path/to/list" (func (int) int)
)

l := intlist.New()
l.Insert(5)

[bradfitz]

@md2perpe, syntax is not the hard part of this issue. In fact, it is by far the easiest. Please see the discussion and linked documents above.

[griesemer]

@md2perpe We have discussed parametrizing entire packages ("modules") as a way to genericity internally - it does seem to be a way to reduce syntactic overhead. But it has other issues; e.g., it's not clear how one would parametrize it with types that are not package-level. But the idea may still be worth exploring in detail.

[thwd]

I'd like to share a perspective: In a parallel universe all Go function-signatures have always been constrained to mention only interface types, and instead of demand for generics today, there's one for a way to avoid the indirection associated with interface values. Think of how you'd solve that problem (without changing the language). I have some ideas.

[mandolyte]

@thwd So would the library author continue using interfaces, but without the type switching and type assertions needed today. And would the library user simply pass in concrete types as if the library would use the types as-is... and then would the compiler reconcile the two? And if it couldn't state why? (such as the modulo operator was used in the library, but the user supplied a slice of something.

Am I close? :-)

[thwd]

@mandolyte yes! let's exchange emails as to not pollute this thread. You can reach me at "me at thwd dot me". Anyone else reading this who might be interested; shoot me an email and I'll add you to the thread.

[leaxoy]

It a great feature for type system and collection library. A potential syntax:

type Element<T> struct {
    prev, next *Element<T>
    list *List<T>
    value T
}
type List<E> struct {
    root Element<E>
    len int
}

For interface

type Collection<E> interface {
    Size() int
    Add(e E) bool
}

super type or type implement:

func contain(l List<parent E>, e E) bool
<V> func (c Collection<child E>)Map(fn func(e E) V) Collection

The above aka in java:

boolean contain(List<? super E>, E e)
<V> Collection Map(Function<? extend E, V> mapFunc);

[mvdan]

@leaxoy as said before, the syntax is not the hard part here. See discussion above.

[dongweigogo]

Just be aware that the cost of interface is unbelievably huge.

[minux]

Please elaborate why do you think the cost of interface is "unbelievably" large. It shouldn't be worse than C++'s non-specialized virtual calls.

[txgruppi]

@minux I can't say about the performance costs but in relation to code quality. interface{} can't be verified at compile time but generics can. In my opinion this is, in most cases, more important than the performance issues of using interface{}.

[bcmills]

@xoviat

There's really no downside to this because the processing required for this doesn't slow the compiler down.

There are (at least) two downsides.

One is increased work for the linker: if the specializations for two types result in the same underlying machine code, we don't want to compile and link two copies of that code.

Another is that parameterized packages are less expressive than parameterized methods. (See the proposals linked from the first comment for detail.)

[go101]

Is hyper type a good idea?

func getAddFunc (aType type) func(aType, aType) aType {
    return func(a, b aType) aType {
        return a+b
    }
}