proposal: generic programming facilities #15292

Open
adg opened this Issue Apr 14, 2016 · 45 comments

Projects

None yet
@adg
Contributor
adg commented Apr 14, 2016

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.

@adg adg added Go2 Proposal labels Apr 14, 2016
@gopherbot

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

@gopherbot gopherbot pushed a commit to golang/proposal that referenced this issue Apr 14, 2016
@ianlancetaylor @adg ianlancetaylor + adg design: add "Go should have generics" proposal
This change proposes the notion of generics in Go, and includes four
proposals from years' past that are each flawed in their own ways.
These historical documents are included to show what a complete
generics proposal looks like.

Updates golang/go#15292

Change-Id: Ice1c35af618a043d55ceec54f182d45a4de780e1
Reviewed-on: https://go-review.googlesource.com/22057
Reviewed-by: Ian Lance Taylor <iant@golang.org>
b571c32
@ianlancetaylor ianlancetaylor added this to the Proposal milestone Apr 14, 2016
@bradfitz
Member

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

@egonelbre
Contributor

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
Contributor
tamird commented Apr 14, 2016

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
sbunce commented Apr 14, 2016

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
Contributor

@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
alex commented Apr 14, 2016

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

@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
joho commented Apr 14, 2016

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.

@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
larsth commented Apr 15, 2016

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
Contributor

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
andrewcmyers commented Apr 16, 2016 edited

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
andrewcmyers commented Apr 16, 2016 edited

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
andrewcmyers commented Apr 17, 2016 edited

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.

@mk0x9 mk0x9 pushed a commit to mk0x9/go that referenced this issue Apr 18, 2016
@dsymonds dsymonds doc: link to iant's generics proposal from the FAQ.
Updates #15292.

Change-Id: I229f66c2a41ae0738225f2ba7a574478f5d6d620
Reviewed-on: https://go-review.googlesource.com/22163
Reviewed-by: Andrew Gerrand <adg@golang.org>
3629814
@gopherbot gopherbot pushed a commit that referenced this issue Apr 18, 2016
@dsymonds @adg dsymonds + adg doc: link to iant's generics proposal from the FAQ.
Updates #15292.

Change-Id: I229f66c2a41ae0738225f2ba7a574478f5d6d620
Reviewed-on: https://go-review.googlesource.com/22163
Reviewed-by: Andrew Gerrand <adg@golang.org>
Reviewed-on: https://go-review.googlesource.com/22166
Reviewed-by: David Symonds <dsymonds@golang.org>
6fd563d
@jba
jba commented Apr 18, 2016

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
sprstnd commented Apr 27, 2016

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
Contributor

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:

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
Contributor

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
#15292 (comment)

@andrewcmyers
andrewcmyers commented Apr 28, 2016 edited

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
Contributor

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
jba commented Apr 28, 2016 edited

@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
jba commented Apr 28, 2016

@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
andrewcmyers commented Apr 28, 2016 edited

@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

@shurcooL shurcooL referenced this issue in google/go-github May 14, 2016
Merged

add support for Reactions API #357

@go-li
go-li commented May 26, 2016

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
Member

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

@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
thwd commented Oct 26, 2016

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
thwd commented Oct 28, 2016

@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
leaxoy commented Dec 22, 2016 edited

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
Contributor
mvdan commented Dec 22, 2016

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment