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.

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.

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.

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

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.

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)

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.

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

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.

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

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

@zerkms run-time checks can be turned off by setting asserting = false (this wouldn't go in the standard library), there's a use pattern for compile-time checks, and anyway a type check just looks at the interface struct (using interface adds more expense than the type check). If interface isn't performing then you'll have to write your own type.

You're saying maximized-performance generic code is a key need. It hasn't been for my use cases, but maybe the standard library could become faster, and maybe others need such a thing.

run-time checks can be turned off by setting asserting = false

then nothing guarantees correctness

You're saying maximized-performance generic code is a key need.

I did not say that. Type safety would be a great deal. Your solution is still interface{}-infected.

but maybe the standard library could become faster, and maybe others need such a thing.

may be, if core dev team is happy to implement whatever I need on demand and quickly.

@pciet

I don’t see the need for an added language feature when just documentation could get us there now.

You say this, yet you have no problem using the generic language features in the form of slices and the make function.

I don’t see the need for an added language feature when just documentation could get us there now.

Then why bother using a statically typed language? You can use a dynamically typed language like Python and rely on documentation to make sure correct data types are sent to your API.

I think one of the advantages of Go is the facilities to enforce some constraints by the compiler to prevent future bugs. Those facilities can be extended (with generics support) to enforce some other constraints to prevent some more bugs in the future.

You say this, yet you have no problem using the generic language features in the form of slices and the make function.

I'm saying the existing features get us to a good balanced point that does have generic programming solutions and there should be strong real reasons to change from the Go 1 type system. Not how a change would improve the language but what problems people are facing now, such as maintaining a lot of run-time type switching for interface{} in the fmt and database standard library packages, that would be fixed.

Then why bother using a statically typed language? You can use a dynamically typed language like Python and rely on documentation to make sure correct data types are sent to your API.

I've heard suggestions to write systems in Python instead of statically-typed languages and organizations do.

Most Go programmer using the standard library use types that can't be completely described without documentation or without looking at the implementation. Types with parametric sub-types or general types with applied constraints only fix a subset of these cases programmatically and would generate a lot of work already done in the standard library.

In the proposal for sum types I suggested a build feature for the interface type switch where an interface use in a function or method has a build error emitted when a possible value assigned to the interface does not match any contained interface type switch case.

A function/method taking an interface could reject some types at build by having no default case and no case for the type. This seems like a reasonable generic programming addition if the feature is feasible to implement.

If Go interfaces could capture the type of the implementer, there could be a form of generics that is completely compatible with current Go syntax - a single parameter form of generics (demonstration).

@dc0d for generic container types I believe that feature adds compile-time type checking without requiring a wrapper type: https://gist.github.com/pciet/36a9dcbe99f6fb71f5fc2d3c455971e5

@pciet You are right. In the provided code, No. 4, sample states that the type is captured for slices and channels (and arrays). But not for maps, because there is only one and only one type parameter: the implementer. And since a map needs two type parameter, wrapper interfaces are needed.

BTW I have to emphasis the demonstrational purpose of that code, as a line of thought. I'm no language designer. This is just a hypothetical way of thinking about the implementation of generics in Go:

• Compatible with current Go
• Simple (single generic type parameter, which feels like this in other OO, referring to current implementer)

Discussion of genericity and all possible use cases in the context of a desire to minimize impacts while maximizing important use cases and flexibility of expression is a very complex analysis. Not sure if any of us will be able to distill it down to short set of principles aka generative essence. I’m trying. Any way, here some of my initial thoughts from my cursory perusal of this thread…

@adg wrote:

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

Afaics, the linked section excerpted as follows fails to state a case of genericity lacking with current interfaces, “There is no way to write a method that takes an interface for the caller supplied type T, for any T, and returns a value of the same type T.”.

There is no way to write an interface with a method that takes an argument of type T, for any T, and returns a value of the same type.

So how else could the code at the call site type check that it has a type T as the result value? For example, the said interface may have a factory method for building type T. This is why we need to parametrise interfaces on type T.

Interfaces are not simply types; they are also values. There is no way to use interface types without using interface values, and interface values aren’t always efficient.

Agreed that since interfaces can’t currently be explicitly parametrised on the type T they operate on, the type T is not accessible to the programmer.

So this what typeclass bounds do at the function definition site taking as input a type T and having a where or requires clause stating the interface(s) that are required for type T. In many circumstances these interface dictionaries can be automatically monomorphised at compile-time so that no dictionary pointer(s) (for the interfaces) are passed into the function at runtime (monomorphisation which I presume the Go compiler applies to interfaces currently?). By ‘values’ in the above quote, I presume he means the input type T and not the dictionary of methods for the interface type implemented by type T.

If we then allow type parameters on data types (e.g. struct), then said type T above can be itself parameterised so we really have a type T<U>. Factories for such types which need to retain knowledge of U are called higher-kinded types (HKT).

Generics permit type-safe polymorphic containers.

C.f. also the issue of heterogeneous containers discussed below. So by polymorphic we mean genericity of the value type of the container (e.g. element type of the collection), yet there’s also the issue of whether we can put more than one value type in the container simultaneously making them heterogeneous.

@tamird wrote:

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

Rust’s trait bounds are essentially typeclass bounds.

@alex wrote:

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.

Why do you think they’re a bad fit? Perhaps you’re thinking of the trait objects which employ runtime dispatch thus are less performant than monomorphism? But those can be considered separately from the typeclass bounds genericity principle (c.f. my discussion of heterogeneous containers/collections below). Afaics, Go’s interfaces are already trait-like bounds and accomplish the goal of typeclasses which is to late bind the dictionaries to the data types at the call site, rather than the anti-pattern of OOP which early binds (even if still at compile-time) dictionaries to data types (at instantiation/construction). Typeclasses can (at least a partial improvement of degrees-of-freedom) solve the Expression Problem which OOP can’t.

@jimmyfrasche wrote:

• https://golang.org/doc/faq#covariant_types

I agree with the above link that typeclasses indeed aren’t subtyping and aren’t expressing any inheritance relationship. And agree with not unnecessarily conflating “genericity” (as a more general concept of reuse or modularity than parametric polymorphism) with inheritance as subclassing does.

However I do also want to point out that inheritance hierarchies (aka subtyping) are inevitable¹ on the assignment to (function inputs) and from (function outputs) if the language supports unions and intersections, because for example a int ν string can accept assignment from an int or a string but neither can accept an assignment from an int ν string. Without unions afaik the only alternative ways to provide statically typed heterogeneous containers/collections are subclassing or existentially bounded polymorphism (aka trait objects in Rust and existential quantification in Haskell). Links above contain discussion about the tradeoffs between existentials and unions. Afaik, the only way to do heterogeneous containers/collections in Go now is to subsume all types to an empty interface{} which is throwing away the typing information and would I presume require casts and runtime type inspection, which sort of² defeats the point of static typing.

The “anti-pattern” to avoid is subclassing aka virtual inheritance (c.f. also “EDIT#2” about the issues with implicit subsumption and equality, etc).

¹ _{Regardless whether they’re matched structurally or nominally because subtyping is due to the Liskov Substitution Principle based on comparative sets and the direction of assignment with function inputs opposite to return values, e.g. a type parameter of a struct or interface can’t reside in both the function inputs and return values unless it invariant instead of co- or contra-variant.}

² _{Absolutism won’t apply because we can’t type check the universe of unbounded non-determinism. IOW, increasing static typing is in tension with algorithmic flexibility. So as I understand it to be, this thread is about choosing an optimum (“sweet spot”) limit to the level of stating typing w.r.t. to the genericity issues.}

@andrewcmyers wrote:

Unlike Java and C# generics, the Genus generics mechanism is not based on subtyping.

It’s the inheritance and subclassing (not structural subtyping) that is the worst anti-pattern you don’t want to copy from Java, Scala, Ceylon, and C++ (unrelated to the problems with C++ templates).

@thwd wrote:

The exponent on the complexity measure of parameterized types is variance. Go's types (excepting interfaces) are invariant and this can and should be kept the rule.

Subtyping with immutability side-steps the complexity of covariance. Immutability also ameliorates some of the problems with subclassing (e.g. Rectangle vs. Square) but not others (e.g. implicit subsumption, equality, etc).

@bxqgit wrote:

Simple syntax and type system are the important pros of Go. If you add generics, language will become an ugly mess like Scala or Haskell.

Note that Scala attempts to merge OOP, subsclassing, FP, generic modules, HKT, and typeclasses (via implicit) all into one PL. Perhaps typeclasses alone might be sufficient.

Haskell is not necessarily obtuse because of typeclass generics, but more likely because it’s enforcing pure functions every where and employing monadic category theory to model controlled imperative effects.

Thus I think it’s not correct to associate the obtuseness and complexity of those PLs with typeclasses in for example Rust. And let’s not blame typeclasses for Rust’s lifetimes+exclusive mutability borrowing abstraction.

Afaics, in the Semantics section of the Type Parameters in Go, the problem encountered by @ianlancetaylor is a conceptualization issue because he’s (afaics) apparently unwittingly reinventing typeclasses:

Can we merge SortableSlice and PSortableSlice to have the best of both worlds? Not quite; there is no way to write a parameterized function that supports either a type with a Less method or a builtin type. The problem is that SortableSlice.Less can not be instantiated for a type without a Less method, and there is no way to only instantiate a method for some types but not others.

The requires Less[T] clause for the typeclass bound (even if implicitly inferred by the compiler) on the Less method for []T is on T not []T. The implementation of the Less[T] typeclass (which contains a method Less method) for each T will either provide an implementation in the function body of the method or assign the < built-in function as the implementation. Yet I believe this requires HKT U[T] if the methods of Sortable[U] need a type parameter U representing the implementing type, e.g. []T. Afair @keean has another way of structuring a sort employing a separate typeclass for the value type T which doesn’t require a HKT.

Note those methods for []T might be implementing a Sortable[U] typeclass, where U is []T.

(Technical aside: it may seem that we could merge SortableSlice and PSortableSlice by having some mechanism to only instantiate a method for some type arguments but not others. However, the result would be to sacrifice compile-time type safety, as using the wrong type would lead to a runtime panic. In Go one can already use interface types and methods and type assertions to select behavior at runtime. There is no need to provide another way to do this using type parameters.)

The selection of the typeclass bound at the call site is resolved at compile-time for a statically known T. If heterogeneous dynamic dispatch is needed then see the options I explained in my prior post.

I hope @keean can find time to come here and help explain typeclasses as he’s more expert and helped me to learn these concepts. I might have some errors in my explanation.

P.S. note for those who already read my prior post, note I edited it extensively about 10 hours after posting it (after some sleep) to hopefully make the points about heterogeneous containers more coherent.

The Cycles section appears to be incorrect. The runtime construction of the S[T]{e} instance of a struct has nothing to do with the selection of the implementation of the generic function called. He’s presumably thinking that the compiler doesn’t know if it’s specializing the implementation of the generic function for the type of the arguments, but all those types are known at compile-time.

Perhaps the Type Checking section specification could be simplified by studying @keean’s concept of a connected graph of distinct types as nodes for a unification algorithm. Any distinct types connected by an edge must have congruent types, with edges created for any types which connect via assignment or otherwise in the source code. If there’s union and intersection (from my prior post), then the direction of assignment has to be taken into account (somehow?). Each distinct unknown type starts off with a least upper bounds (LUB) of Top and a greatest lower bounds (GLB) of Bottom and then constraints can alter these bounds. Connected types have to have compatible bounds. Constraints should all be typeclass bounds.

In Implementation:

For example, it is always possible to implement parameterized functions by generating a new copy of the function for each instantiation, where the new function is created by replacing the type parameters with the type arguments.

I believe the correct technical term is monomorphisation.

This approach would yield the most efficient execution time at the cost of considerable extra compile time and increased code size. It’s likely to be a good choice for parameterized functions that are small enough to inline, but it would be a poor tradeoff in most other cases.

Profiling would tell the programmer which functions can most benefit from monomorphisation. Perhaps the Java Hotspot optimizer does monomorphisation optimization at runtime?

@egonelbre wrote:

There is Summary of Go Generics Discussions, which tries to provide an overview of discussions from different places.

The Overview section seems to imply that Java’s universal use of boxing references for instances in a container is the only axis of design diametrically opposing C++’s monomorphisation of templates. But typeclass bounds (which can also be implemented with C++ templates yet always monomorphised) are applied to functions not to container type parameters. Thus afaics the overview is missing the design axis for typeclasses wherein we can choose whether to monomorphise each typeclass bounded function. With typeclasses we always make programmers faster (less boilerplate) and can get a more refined balance between making compilers/execution faster/slower and code bloat greater/lesser. Per my prior post, perhaps the optimum would be if the choice of functions to monomorphise was profiler driven (automatically or more likely by annotation).

In the Problems : Generic Data Structures section:

Cons

• Generic structures tend to accumulate features from all uses, resulting in increased compile times or code bloat or needing a smarter linker.

For typeclasses this is either not true or less of an issue, because interfaces only need to be implemented for data types which are supplied to functions which use those interfaces. Typeclasses are about late binding of implementation to interface, unlike OOP which binds every data type to it’s methods for the class implementation.

As well, not all the methods need to be put in a single interface. The requires clause (even if implicitly inferred by the compiler) on a typeclass bound for a function declaration can mix-and-match interfaces required.

• Generic structures and the APIs that operate on them tend to be more abstract than purpose-built APIs, which can impose cognitive burden on callers

A counter argument which I think significantly ameliorates this concern is that the cognitive burden of learning an unbounded number of special case re-implementations of the essentially same generic algorithms, is unbounded. Whereas, learning the abstract generic APIs is bounded.

• In-depth optimizations are very non-generic and context specific, hence it’s harder to optimize them in a generic algorithm.

This is not a valid con. The 80/20 rule says don’t add unbounded complexity (e.g. premature optimization) for code which when profiled doesn’t require it. The programmer is free to optimize in 20% of the cases whilst the remaining 80% get handled by the bounded complexity and cognitive load of the generic APIs.

What we’re really getting at here is the regularity of a language and generic APIs help, not hurt that. Those Cons are really not correctly conceptualized.

Alternative solutions:

• use simpler structures instead of complicated structures
  • e.g. use map[int]struct{} instead of Set

Rob Pike (and I also watched him make that point in the video) seems to be missing the point that generic containers aren’t sufficient for making generic functions. We need that T in map[T] so we can pass the generic data type around in functions for inputs, outputs, and for our own struct. Generics only on container type parameters is wholly insufficient for expressing generic APIs and generic APIs are required for bounded complexity and cognitive load and obtaining regularity in a language ecosystem. Also I haven’t seen the increased level of refactoring (thus the reduced composability of modules that can’t be easily refactored) that non-generic code requires, which is what the Expression Problem is about that I mentioned in my first post.

In the Generic Approaches section:

Package templates
This is an approach used by Modula-3, OCaml, SML (so-called “functors”), and Ada. Instead of specifying an individual type for specialization, the whole package is generic. You specialize the package by fixing the type parameters when importing.

I may be mistaken but this seems not quite correct. ML functors (not to be confused with FP functors) can also return an output which remains type parametrised. There would be no way to use the algorithms within other generic functions otherwise, so thus generic modules wouldn’t be able reuse (by importing with concrete types into) other generic modules. This appears to be an attempt to oversimplify and then entirely miss the point of generics, module reuse, etc..

Rather my understanding is that that package (aka module) type parametrisation enables the ability to apply type parameter(s) to a grouping of struct, interface, and func.

More complicated type-system
This is the approach that Haskell and Rust take.
[…]
Cons:

• hard to fit into simpler language (https://groups.google.com/d/msg/golang-nuts/smT_0BhHfBs/MWwGlB-n40kJ)

Quoting @ianlancetaylor in the linked document:

If you believe that, then it's worth pointing out that the core of the
map and slice code in the Go runtime is not generic in the sense of
using type polymorphism. It's generic in the sense that it looks at
type reflection information to see how to move and compare type
values. So we have proof by existence that it is acceptable to write
"generic" code in Go by writing non-polymorphic code that uses type
reflection information efficiently, and then to wrap that code in
compile-time type-safe boilerplate (in the case of maps and slices
this boiler plate is, of course, provided by the compiler).

And that’s what a compiler transpiling from a superset of Go with generics added, would output as Go code. But the wrapping would not be based on some delineation such as package, as that would lack the composability I already mentioned. Point being that there’s no short-cut to a good composable generics type system. Either we do it correctly or don’t do anything, because adding some non-composable hack that isn’t really generics is going to create eventually a clusterfuck inertia of patchwork half-assed genericity and irregularity of corner cases and workarounds making Go ecosystem code unintelligible.

It's also true that most people writing large complex Go programs have
not found a significant need for generics. So far it's been more like
an irritating wart--the need to write three lines of boilerplate for
each type to be sorted--rather than a major barrier to writing useful
code.

Yeah this has been one of the thoughts in my mind as whether going to a full blown typeclass system is justifiable. If all your libraries are based around it, then apparently it could be a beautiful harmony, but if we’re contemplating about the inertia of existing Go hacks for genericity, then perhaps the additional synergy gained is going to be low for a lot of projects?

But if a transpiler from a typeclass syntax emulated the existing manual way Go can model generics (Edit: which I just read that @andrewcmyers states is plausible), this might be less onerous and find useful synergies. For example, I realized that two parameter typeclasses can be emulated with interface implemented on a struct which emulates a tuple, or @jba mentioned an idea for employing inline interface in context. Apparently struct are structurally instead of nominally typed unless given a name with type? Also I confirmed a method of an interface can input another interface so afaics it may be possible to transpile from HKT in your sort example I wrote about in my prior post here. But I need to think this out more when I am not so sleepy.

I think it's fair to say that most of the Go team do not like C++
templates, in which one Turing complete language has been layered over
another Turing complete language such that the two languages have
completely different syntaxes, and programs in both languages are
written in very different ways. C++ templates serve as a cautionary
tale because the complex implementation has pervaded the entire
standard library, causing C++ error messages to become a source of
wonder and amazement. This is not a path that Go will ever follow.

I doubt anyone will disagree! The monomorphisation benefit is orthogonal to the downsides of a Turing complete generics metaprogramming engine.

Btw, the design error of C++ templates appears to me to be the same generative essence of the flaw of generative (as opposed to applicative) ML functors. The Principle of Least Power applies.

@ianlancetaylor wrote:

It is disappointing to see Go becoming more and more complex by adding built-in parameterized types.

Despite the speculation in this issue, I think this is extremely unlikely to happen.

I hope so. I firmly believe that Go should either add a coherent generics system or just accept that it will never have generics.

I think a fork to a transpiler is more likely to happen, partially because I have funding to implement it and am interested to do so. Yet I’m still analyzing the situation.

That would fracture the ecosystem though, but at least then Go can remain pure to its minimalist principles. Thus to avoid fracturing the ecosystem and allow for some other innovations I would like, I would probably not make it a superset and name it Zero instead.

@pciet wrote:

My vote is no to generalized application generics, yes to more built-in generic functions like append and copy that work on multiple base types. Perhaps sort and search could be added for the collection types?

Expanding this inertia is going to perhaps prevent a comprehensive generics feature from ever making it into Go. Those who wanted generics are likely to leave for greener pastures. @andrewcmyers reiterated this:

It is would be disappointing to see Go becoming more and more complex by adding built-in parameterized types. It would be better just to add the language support for programmers to write their own parameterized types.

@shelby3

Afaik, the only way to do heterogeneous containers/collections in Go now is to subsume all types to an empty interface{} which is throwing away the typing information and would I presume require casts and runtime type inspection, which sort of2 defeats the point of static typing.

See the wrapper pattern in comments above for static type checking of interface{} collections in Go.

Point being that there’s no short-cut to a good composable generics type system. Either we do it correctly or don’t do anything, because adding some non-composable hack that isn’t really generics…

Can you explain this more? For the collection types case having an interface defining the necessary generic behavior of contained items seems reasonable to write functions to.

@pciet this code is literally doing the exact thing @shelby3 was describing and considering an antipattern. Quoting you from earlier:

This gives in documentation and testing examples that type wrapper pattern (thanks @pierrre) for compile-time type safety and also has the reflect check for run-time type safety.

You are taking code that lacks type information and, on a type-by-type basis, adding casts and runtime type inspection using reflect. This is exactly what @shelby3 was complaining about. I tend to call this approach "monomorphization-by-hand" and is exactly the sort of tedious chore I think is best punted to a compiler.

This approach has a number of disadvantages:

• Requires type-by-type wrappers, maintained either by hand or a go generate-like tool
• (If done by hand instead of a tool) opportunity to make mistakes in the boilerplate which won't be caught until runtime
• Requires dynamic dispatch instead of static dispatch, which is both slower and uses more memory
• Uses runtime reflection rather than compile-time type assertions, which is also slow
• Not composable: acts entirely on concrete types with no opportunities to use typeclass-like (or even interface-like) bounds on types, unless you handroll another layer of indirection for every non-empty interface you also want to abstract over

Can you explain this more? For the collection types case having an interface defining the necessary generic behavior of contained items seems reasonable to write functions to.

Now everywhere you want to use a bound instead of or in addition to a concrete type, you have to write the same typechecking boilerplate for every interface type too. It just further compounds the (perhaps combinatorial) explosion of static type wrappers you have to write.

There are also ideas that, as far as I know, simply cannot be expressed in Go's type system at all today, such as a bound on a combination of interfaces. Imagine we have:

type Foo interface {
    ...
}

type Bar interface {
    ...
}

How do we express, using a purely static type check, that we want a type that implements both Foo and Bar? As far as I know this isn't possible in Go (short of resorting to runtime checks that may fail, eschewing static type safety).

With a typeclass-based generics system we could express this as:

func baz<T Foo + Bar>(t T) {
    ...
}

@tarcieri

How do we express, using a purely static type check, that we want a type that implements both Foo and Bar?

simply like so:

type T interface {
    Foo
    Bar
}

func baz(t T) { ... }

@sbinet neat, TIL

Personally I consider runtime reflection a mis-feature, but that's just me... I can go into why if anyone is interested.

I think anyone implementing generics of any kind should read Stepanov's "Elements of Programming" several times first. It would avoid a lot of Not Invented Here problems and re-inventing the wheel. After reading that it should be clear why "C++ Concepts" and "Haskell Typeclasses" are the right way to do generics.

I see this issue seems active again
Here's a strawman proposal playground
https://go-li.github.io/test.html
just paste demo programs from here
https://github.com/go-li/demo

Thanks a lot for your evaluation of this single parametered
functions generics.

We maintain the hacked gccgo and
this project would been impossible without you, so we
wanted to contribute back.

Also we look forward to whatever generics you adopt, keep up the great work!

@anlhord where are the implementation details about this? Where can one read about the syntax? What is implemented? What isn't implemented? What are the specifications for this implementations? What are the pros and cons for it?

The playground link contains the worst possible example of this:

package main

import "fmt"

func main() {
	fmt.Println("Hello, playground")
}

That code tells me nothing on how to use it and what can I test.

If you could improve those things, it would help better understand what your proposal is and how it compares to the previous ones / see how the other points raised here apply or not to it.

Hope this helps you understand the problems with your comment.

@joho wrote:

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.

I presume OOP and subclassing (e.g. classes in Java and C++) won’t considered seriously both because Go already has a typeclass-like interface (without the explicit T generic type parameter), Java is cited as what to not copy, and because many have argued they’re an anti-pattern. Upthread I’ve linked to some of that argument. We could go deeper into that analysis if anyone is interested.

I haven’t yet studied newer research such as the Genus system mentioned upthread. I’m wary of “kitchen sink” systems which attempt to mix so many paradigms (e.g. subclassing, multiple inheritance, OOP, trait linearization, implicit, typeclasses, abstract types, etc), due to the complaints about Scala having so many corner cases in practice, although perhaps that will improve with Scala 3 (aka Dotty and the DOT calculus). I’m curious if their comparison table is comparing to experimental Scala 3 or the current version of Scala?

So afaics, what remains are ML functors and Haskell typeclasses in terms of proven genericity systems, which significantly improve extensibility and flexibility as compared to OOP+subsclassing.

I wrote down some of the private discussion @keean and I had about ML functor modules versus typeclasses. The highlights seem to be:

• typeclasses model an algebra (but without checked axioms) and implement each data type for each interface only one way. Thus enabling implicit selection of the implementations by the compiler without annotation at the call site.

• Applicative functors have referential transparency whereas generative functors create a new instance on each instantiation, which means they’re not initialization order invariant.

• ML functors are more powerful/flexible than typeclasses but this comes at the cost of more annotations and potentially more corner case interactions. And according to @keean they require dependent types (for associated types) which is more complex type system. @keean thinks Stepanov’s expression of genericity as an algebra plus typeclasses is sufficiently powerful and flexibility, so that seems to be the sweet spot for state-of-the-art, well proven (in Haskell and now in Rust) genericity. However, the axioms aren’t enforced by typeclasses.

• I've suggested adding unions for heterogeneous containers with typeclasses to extend along another axis of the Expression Problem, although this requires immutability or copying (only for the cases where the heterogeneous extensibility is employed) which is known to have an O(log n) slowdown compared to unrestrained mutable imperativity.

@larsth wrote:

It could be interesting to have one or more experimental transpilers - a Go generics source code to Go 1.x.y source code compiler.

_{P.S. I doubt Go will adopt such a sophisticated typing system, but I’m contemplating a transpiler to existing Go syntax as I mentioned in my prior post (see the edit at the bottom). I want Go’s goroutines (because they’re fundamentally superior to callback-based promises) and it’s portability to both client (GopherJS, Joy, and now the work proceeding on a WASM compile target) and server. And I want a robust generic system along with those very desirable Go features. I’ve tried my best to find another PL ecosystem which meets my desired capabilities and none do. Typeclass generics on Go appears to be what I want.}

@bcmills wrote about his proposal about compile-time functions for genericity:

I've heard that same argument used to advocate for exporting interface types rather than concrete types in Go APIs, and the reverse turns out to be more common: premature abstraction overconstrains the types and hinders extension of APIs. (For one such example, see #19584.) If you want to rely on this line of argument I think you need to provide some concrete examples.

It’s certainly true that type system abstractions necessarily forsake some degrees-of-freedom and sometimes we have bust out of those constraints with “unsafe” (i.e. in violation of the statically checked abstraction), yet that has to be traded off against the benefits of modular decoupling with succinctly annotated invariants.

When designing a system for genericity, we’re likely wanting to increase the regularity and predictability of the ecosystem as one of the principle goals, especially if Go’s core philosophy is taken into consideration (e.g. that average programmers are a priority).

The Principle of Least Power applies. The power/flexibility of the invariants “hidden in” compile-time functions for genericity has to be weighed against their capability to do harm to for example the readability of the source code in the ecosystem (wherein modular decoupling is extremely important because the reader doesn’t have to read a potentially unbounded quantity of code due to implicit transitive dependencies, in order to understand a given module/package!). Implicit resolution of typeclass implementation instances have this problem if their algebra is not adhered to.

Sure, but that's already true for lots of implicit constraints in Go independent of any generic programming mechanism.

For example, a function may receive a parameter of interface type and initially call its methods sequentially. If that function later changes to call those methods concurrently (by spawning additional goroutines), the constraint "must be safe for concurrent use" is not reflected in the type system.

But afaik Go didn’t attempt to design an abstraction to modularize those effects. Rust has such an abstraction (which btw I think is overkill pita/tsuris/limiting for some/most use cases and I argue for an easier single-threaded model abstraction yet unfortunately Go doesn’t support restricting all spawned goroutines to the same thread). And Haskell requires monadic control over effects due to enforcing pure functions for referential transparency.

@alercah wrote:

I think the biggest downside to inferred constraints is that they make it easy to use a type in a way that introduces a constraint without fully understanding it. In the best case, this just means that your users may run into unexpected compile-time failures, but in the worst case, this means you can break the package for consumers by introducing a new constraint inadvertently. Explicitly-specified constraints would avoid this.

Agreed. Being able to surreptitiously break code in other modules because the invariants of the types aren’t explicitly annotated is egregiously insidious.

@andrewcmyers wrote:

To be clear, I don't consider macro-style code generation, whether done with gen, cpp, gofmt -r, or other macro/template tools, to be a good solution to the generics problem even if standardized. It has the same problems as C++ templates: code bloat, lack of modular type checking, and difficulty debugging. It gets worse as you start, as is natural, building generic code in terms of other generic code. To my mind, the advantages are limited: it would keep life relatively simple for the Go compiler writers and it does produce efficient code — unless there is instruction cache pressure, a frequent situation in modern software!

@keean seems to agree with you.

@shelby3 thanks for the comments. Can you next time make the comments / edits directly in the document itself. It's easier to track where things need to be fixed and easier to ensure that all notes get a proper response.

The Overview section seems to imply that Java’s universal use of boxing references for instances ...

Added comment to make it clear, that it's not meant as a comprehensive list. It's mainly there so that people get the gist of different trade-offs. The full list of different approaches is further below.

Generic structures tend to accumulate features from all uses, resulting in increased compile times or code bloat or needing a smarter linker.
For typeclasses this is either not true or less of an issue, because interfaces only need to be implemented for data types which are supplied to functions which use those interfaces. Typeclasses are about late binding of implementation to interface, unlike OOP which binds every data type to it’s methods for the class implementation.

That statement is about what happens to generic data-structures in the long term. In other words a generic data-structure often ends up collecting all different uses -- rather than having multiple smaller implementations for different purposes. Just as an example look at https://www.scala-lang.org/api/2.12.3/scala/collection/immutable/List.html.

It's important to note that, just the "mechanical design" and "as much flexibility" is not sufficient to create a good "generics solution". It also needs good instructions, how things should be used and what to avoid, and consider how people end up using it.

Generic structures and the APIs that operate on them tend to be more abstract than purpose-built APIs ...

A counter argument which I think significantly ameliorates this concern is that the cognitive burden of learning an unbounded number of special case re-implementations of the essentially same generic algorithms, is unbounded...

Added a note about cognitive load of many similar APIs.

The special-case re-implementations aren't unbounded in practice. You will only see a fixed-number of specialization.

This is not a valid con.

You may disagree with some of points, I disagree with quite a few of them to some degree, but I do understand their viewpoint and try to understand the problems people are faced with day-to-day. The goal of the document is to collect different opinions, not to judge "how annoying something is for someone".

However, the document does take a stance on "problems traceable to real-world-problems", because abstract and facilitated problems in forums tend to descend into meaningless chatter without any understanding being built.

What we’re really getting at here is the regularity of a language and generic APIs help, not hurt that.

Sure in practice you might need this style of optimization only for less than 1% of the cases.

Alternative solutions:

Alternative solutions aren't meant as a substitute for generics. But, rather a list of potential solutions for different kinds of problems.

Package templates

I may be mistaken but this seems not quite correct. ML functors (not to be confused with FP functors) can also return an output which remains type parametrised.

Can you provide a clearer wording and if necessary split into two different approaches?

@egonelbre thanks also for responding so I can know on which points I need to clarify my thoughts further.

Can you next time make the comments / edits directly in the document itself.

Apology wish I could comply but I’ve never used the discussion features of Google Doc, don’t have time to learn it, and I also prefer to be able to link to my discussions on Github for future reference.

Just as an example look at https://www.scala-lang.org/api/2.12.3/scala/collection/immutable/List.html.

The design of the Scala collections library was criticized by many people, including one of their former key team members. A comment posted to LtU is representative. Note I added the following to one of my prior posts in this thread to address this:

I’m wary of “kitchen sink” systems which attempt to mix so many paradigms (e.g. subclassing, multiple inheritance, OOP, trait linearization, implicit, typeclasses, abstract types, etc), due to the complaints about Scala having so many corner cases in practice, although perhaps that will improve with Scala 3 (aka Dotty and the DOT calculus).

I don’t think Scala’s collection library would be representative of libraries created for a PL with only typeclasses for polymorphism. Afair, the Scala collections employ the anti-pattern of inheritance, which caused the complex hierarchies, combined with implicit helpers such as CanBuildFrom which exploded the complexity budget. And I think if @keean’s point is adhered to about Stepanov’s Elements of Programming being an algebra, an elegant collections library could be created. It was the first alternative I had seen to a functor (FP) based collections library (i.e. not copying Haskell) also based on math. I want to see this in practice, which is one reason I’m collaborating/discussing with him on design of a new PL. And as of this moment, I’m planning to have that language initially transpile to Go (although I’ve been for years trying to find a way to avoid doing so). So hopefully we’ll be able to experiment soon to see how it works out.

My perception is that the Go community/philosophy would rather wait to see what works in practice and adopt it later once proven, than to rush and pollute the language with failed experiments. Because as you reiterated, all these abstract claims are not so constructive (except to maybe PL design theorists). Also it’s probably implausible to design a coherent generics system by committee.

It also needs good instructions, how things should be used and what to avoid, and consider how people end up using it.

And I think it will help not mixing so many different paradigms available to the programmer in the same language. It's apparently not necessary (@keean and I need to prove that claim). I think we both ascribe to the philosophy that the complexity budget is finite and it’s what you leave out of the PL that is as important as the features included.

However, the document does take a stance on "problems traceable to real-world-problems", because abstract and facilitated problems in forums tend to descend into meaningless chatter without any understanding being built.

Agreed. And it’s also difficult for everyone to follow the abstract points. The devil is in the details and actual results in the wild.

Sure in practice you might need this style of optimization only for less than 1% of the cases.

Go already has interface for genericity, so that can handle the cases where don’t need parametric polymorphism on the type T for the instance of the interface supplied by the call site.

I think read somewhere, maybe it was upthread, the argument that actually the standard library of Go is suffering from inconsistency of optimal use of the most updated idioms. I don’t know if that is true, because I’m not experienced with Go yet. The point I’m making is that the generics paradigm chosen infects all the libraries. So yes as of now you can claim only 1% of the code would need it, because there’s already inertia in idioms that avoid the need for generics.

You may be correct. I have also my skepticism about how much I will use any particular language feature. I think experimentation to find out is the way I will proceed. PL design is an iterative process, then the problem is fighting against the inertia that develops makes it difficult to iterate the process. So I guess Rob Pike is correct in the video where he suggests writing programs that write code for programs (meaning go write generation tools and transpilers) to experiment and test ideas.

When we can show that a particular set of features are superior in practice (and hopefully also popularity of use) to those currently in Go, then we can perhaps see some consensus form around adding them to Go. I encourage others to also create experimental systems that transpile to Go.

Can you provide a clearer wording and if necessary split into two different approaches?

I add my voice to those who would want discourage the attempt to put some overly simplistic templating feature in Go and claim that is generics. IOW, I think a proper functioning generics system that won’t end up being bad inertia is fundamentally incompatible with the desire to have an excessively simplistic design for generics. Afaik, a generics system needs a well thought out and well proven holistic design. Echoing what @larsth wrote, I encourage those with serious proposals to first build a transpiler (or implement in a fork of the gccgo frontend) and then experiment with the proposal so we could all better understand it’s limitations. I was encouraged to read upthread that @ianlancetaylor didn’t think a pollution of bad inertia would be added to Go. As for my specific complaint about the package level parametrisation proposal, my suggestion for who ever is proposing it, please contemplate whether to make a compiler we can all use to play with and then we all can talk about examples of what we like and don’t like about it. Otherwise, we’re talking past each other because maybe I don’t even understand correctly the proposal as described abstractly. I must not understand the proposal, because I don’t understand how the parametrised package can be reused in another package which is also parametrised. IOW, if a package takes parameters, then it needs to instantiate other packages with parameters also. But it seemed the proposal was stating that the only way to instantiate a parametrised package was with a concrete type, not type parameters.

Apology so long-winded. Want to make sure I’m not misunderstood.

@shelby3 ah, I then misunderstood the initial complaint. First I should make clear that the sections in "Generics Approaches" are not concrete proposals. They are approaches or, in other words, bigger design decisions that one might take in a concrete generics approach. However, the groupings are strongly motivated by existing implementations or concrete/informal proposals. Also, I suspect there are at least 5 big ideas still missing from that list.

For the "package templates" approach there are two variations of it (see the linked discussions in document):

1. "interface" based generic packages,
2. explicitly generic packages.

For 1. it doesn't require the generic package to do anything special -- for example the current container/ring would become usable for specialization. Imagine "specialization" here as replacing all instances of the interface in the package with the concrete type (and ignoring circular imports). When that package itself specializes another package, it can use the "interface" as the specialization - it follows that then this use, will be specialized too.

For 2. you can look at them in two ways. One is the recursive concrete specialization at each import -- similar to templating/macroing, at no point there would be a "partially applied package". Of course it can be also seen taken from the functional side, that the generic package is a partial with parameters and then you specialize it.

So, yes, you can use one parameterised package in another.

Echoing what @larsth wrote, I encourage those with serious proposals to first build a transpiler (or implement in a fork of the gccgo frontend) and then experiment with the proposal so we could all better understand it’s limitations.

I know this wasn't explicitly directed at that approach, but it does have 4 different prototypes to test out the idea. Of course, they are not full transpilers, but they are sufficient to test few of the ideas. i.e. I'm not sure whether anyone has implemented the "using parameterised package from another" case.

Parameterised packages sound a lot like ML modules (and ML functors is the parameters can be other packages). There are two ways these can work "applicative" or "generative". An applicative functors is like a value, or a type-alias. A generative functors must be constructed and each instance is different. Another way to think about this, is for a package to be applicative it must be pure (that is no mutable variables at the package level). If there is state at the package level it must be generative as that state needs to be initialised, and it matters which "instance" of a generative package you actually pass as a parameter to other packages which in turn must be generative. For example Ada packages are generative.

The problem with the generative package approach is that it creates lots of boilerplate, where you are instantiating packages with parameters. You can look at Ada generics to see what this looks like.

Type classes avoid this boilerplate by implicitly selecting the typeclass based on the types used in the function only. You can also view type-classes as constrained overloading with multiple dispatch, where the overload resolution almost always occurs statically at compile time, with exceptions for polymorphic recursion and existential types (which are essentially variants you cannot cast out-of, you can only use the interfaces the variant confirms to).

An applicative functors is like a value, or a type-alias. A generative functors must be constructed and each instance is different. Another way to think about this, is for a package to be applicative it must be pure (that is no mutable variables at the package level). If there is state at the package level it must be generative as that state needs to be initialised, and it matters which "instance" of a generative package you actually pass as a parameter to other packages which in turn must be generative. For example Ada packages are generative.

Thank you for the exact terminology, I need to think how to integrate these ideas into the document.

Also, I cannot see a reason why you couldn't have an "automatic type-alias to a generated package" -- in a sense something between "applicative functor" and "generative functor" approach. Obviously, when the package does contain some form of state, it can get complicated to debug and understand.

The problem with the generative package approach is that it creates lots of boilerplate, where you are instantiating packages with parameters. You can look at Ada generics to see what this looks like.

As far as I see, it would create less boilerplate than C++ templates but more than type-classes. Do you have a good real-world program for Ada that demonstrates the problem? (By real-world, I mean code that someone is/was using in production.)

Sure, have a look at my Ada go-board: https://github.com/keean/Go-Board-Ada/blob/master/go.adb

Although this is a fairly loose definition of production, the code is optimised, performs as well as the C++ version, and its open-source, and the algorithm has been refined over several years. You could look at the C++ version too: https://github.com/keean/Go-Board/blob/master/go.cpp

This shows (I think) that Ada generics are a neater solution than C++ templates (but that is not hard), on the other hand it is hard to do the fast access to the data structures in Ada due to the restrictions on returning a reference.

If you want to look at a package generics system for an imperative language, I think Ada is one the best to look at. Its a shame they decided to go multi-paradigm and add all the OO stuff to Ada. Ada is an enhanced Pascal, and Pascal was a small and elegant language. Pascal plus Ada generics would have still been quite a small language, but would have been much better in my opinion. Because the focus of Ada shifted to an OO approach finding good documentation and examples of how to do the same things with generics seem hard to find.

Although I think typeclasses have some advantages, I could live with Ada style generics, there are a couple of issues that hold me back from using Ada more widely, I think it gets values/objects wrong (I think very few languages get this right, 'C' being one of the only ones), it is hard to work with pointers (access variables) and to create safe-pointer abstractions, and it does not provide a way to use packages with runtime-polymorphism (it provides an object model for this, but it adds a whole new paradigm instead of trying to find a way to have runtime-polymorphism using packages).

The solution to runtime-polymorphism is to make packages first-class so instances of package-signatures can be passed as function arguments, this unfortunately requires dependent types (see the work done on Dependent Object Types for Scala to clear up the mess they made with their original type-system).

So I think package generics can work, but it took Ada decades to deal with all the edge cases, so I would look at a production generics system to see what refinements use in production produced. However Ada still falls short because the packages are not first-class, and cannot be used in runtime polymorphism, and this would need to be addressed.

@keean wrote:

Personally I consider runtime reflection a mis-feature, but that's just me... I can go into why if anyone is interested.

Type erasure enables “Theorems for free”, which has practical implications. Writable (and maybe even readable due to transitive relations to imperative code?) runtime reflection makes it’s impossible to guarantee referential transparency in any code and thus certain compiler optimizations aren’t possible and type safe monads aren’t possible. I realize Rust doesn’t even have an immutability feature yet. OTOH, reflection enables other optimizations that wouldn’t be otherwise possible if they couldn’t be statically typed.

I had also stated upthread:

And that’s what a compiler transpiling from a superset of Go with generics added, would output as Go code. But the wrapping would not be based on some delineation such as package, as that would lack the composability I already mentioned. Point being that there’s no short-cut to a good composable generics type system. Either we do it correctly or don’t do anything, because adding some non-composable hack that isn’t really generics is going to create eventually a clusterfuck inertia of patchwork half-assed genericity and irregularity of corner cases and workarounds making Go ecosystem code unintelligible.

@keean wrote:

[…] for a package to be applicative it must be pure (that is no mutable variables at the package level)

And no impure functions may be employed to initialize immutable variables.

@egonelbre wrote:

So, yes, you can use one parameterised package in another.

What I apparently had in mind was “first-class parametrised packages” and the commensurate runtime (aka dynamic) polymorphism that @keean subsequently has mentioned, because I presumed the parametrised packages were proposed in lieu of typeclasses or OOP.

EDIT: but there are two possible meanings for “first-class” modules: modules as first-class values such as in Successor ML and MixML distinguished from modules as first-class values with first-class types as in 1ML, and the necessary tradeoff in module recursion (i.e. mixing) between them.

@keean wrote:

The solution to runtime-polymorphism is to make packages first-class so instances of package-signatures can be passed as function arguments, this unfortunately requires dependent types (see the work done on Dependent Object Types for Scala to clear up the mess they made with their original type-system).

What do you mean by dependent types? (EDIT: I presume now he meant “non-value-dependent” typing, i.e. “functions whose result type depends on the [runtime?] argument[’s type]”) Certainly not dependent on the values of for example int data, such as in Idris. I think you’re referring to dependently typing (i.e. tracking) the type of the values representing instantiated module instances down the call hierarchy so that such polymorphic functions can be monomorphised at compile-time? Does the runtime polymorphism enter due to such monomorphised types being the existential type bound for dynamic types? F-ing Modules demonstrated that “dependent” types aren’t absolutely necessary for modeling ML modules in system F_ω. Have I oversimplified if I presume @rossberg reformulated the typing model to remove all monomorphisation requirements?

The problem with the generative package approach is that it creates lots of boilerplate […]
Type classes avoid this boilerplate by implicitly selecting the typeclass based on the types used in the function only.

Isn’t there also boilerplate with applicative ML functors? There’s no known unification of typeclasses and ML functors (modules) which retains retains the brevity without introducing restrictions that are necessary to prevent (c.f. also) the inherent anti-modularity of the global uniqueness criterion of typeclass implementation instances.

Typeclasses can only implement each type in one way and otherwise requires newtype wrapper boilerplate to overcome the limitation. Here’s another example of multiple ways to implement an algorithm. Afaics, @keean worked around this limitation in his typeclass sort example by overriding implicit selection with an explicitly selected Relation employing wrapping data types to name different relations generically on the value type, but I am doubting whether such tactics are general to all variants of modularity. However a more generalized solution (which can aid in ameliorating the modularity problem of global uniqueness possibly combined with an orphan restriction as improvement to the proposed versioning for orphan resolution by employing a non-default for implementations which could be orphaned) may be to have an extra type parameter implicitly on all typeclass interface, which when not specified defaults to the normal implicit matching, but when specified (or when not specified doesn’t match any other²) then selects the implementation that has the same value in its comma-delimited list of custom values (so this is more generalized, modular matching than naming a specific implement instance). The comma-delimited list is so that an implementation can be differentiated in more than one degree-of-freedom, such as if it has two orthogonal specializations. The desired non-default specialized could be specified either at the function declaration or call site. At the call site, e.g. f<non-default>(…).

So why would we need parametrised modules if we have typeclasses? Afaics only for (← important link to click) substitution because reusing typeclasses for that purposes doesn’t fit well in that for example we want a package module to be able to span multiple files and we want to be able to implicitly open the contents of the module into scope without additional boilerplate. So perhaps going forward with a syntactical-only substitution-only (not first class) package parametrisation is reasonable first step that can address module-level genericity while remaining open to compatibility with and non-overlap of functionality if adding typeclasses later for function-level genericity. However, there’s an issue whether these macros are for example typed or just syntactical (aka “preprocessor”) substitution. If typed, then modules duplicate functionality of typeclasses, which is undesirable both from the standpoint of minimizing the overlapping paradigms/concepts of the PL and potential corner cases due to interactions of the overlap (such as those when attempting to offer both ML functors and typeclasses). Typed modules are more modular because modifications to any encapsulated implementation within the module that doesn’t modify the exported signatures can’t cause consumers of the module to become incompatible (other than the aforementioned anti-modularity problem of typeclass overlapping implementation instances). I’m interested to read @keean’s thoughts on this.

[…] with exceptions for polymorphic recursion and existential types (which are essentially variants you cannot cast out-of, you can only use the interfaces the variant confirms to).

To help other readers. By “polymorphic recursion”, I think refers to higher-ranked types, e.g. parametrised callbacks set at runtime where the compiler can’t monomorphise the body of the callback function because its not known at compile-time. The existential types are as I mentioned before equivalent to Rust’s trait objects, which are one way to attain heterogeneous containers with a later binding in the Expression Problem than class subclassing virtual inheritance, but not as open to extension in the Expression Problem as unions with immutable data structures or copying³ which have an O(log n) performance cost.

¹ _{Which doesn’t requires HKT in the above example, because SET is not requiring the elem type is a type parameter of the generic type of set, i.e. it’s not set<elem>.}

² _{Yet if there existed more than one non-default implementation and no default implementation, then the selection would be ambiguous so the compiler should generate an error. This could be rectified by allowing one implementation to include default on its list of other specializations.}

³ _{Note mutating with immutable data structures doesn’t necessarily require copying the entire data structure, if the data structure is smart enough to isolate history such as singly-linked list.}

Implementing func pick(a CollectionOfT, count uint) []T would be a good example application of generics (from #23717):

// pick returns a slice (len = n) of pseudorandomly chosen elements 
// in unspecified order from c which is an array, slice, or map.
for i, e := range pick(c, n) {

The interface{} approach here is complicated.