"There are no plans for generics. I said we're going to leave the language; we're done"

[alexander....@gmail.com]

Rob Pike said on Gophercon: "There are no plans for generics. I said we're going to  leave the language; we're done"

Could someone from Go developers say what it meant? I read the internet and everybody tries to guess what it was, maybe Rob could give more detailed answer about the meaning of it?

The first question about generics, do you think they will make the language worse, why there are no plans for them? Faq says "Generics may well be added at some point".

The second is what does "we're going to leave the language; we're done" mean? Is it only about Go 1.x.x or does it mean that Go as a language will not develop in future?

Thanks.

[Rob Pike]

I meant there are no plans for generics. That's not the same as saying
we plan not to do generics. It just means we don't have a plan.

The FAQ is still accurate.

-rob

[DV]

There's a new suggestion for generics on average of once per month on this mailing list. It makes for a good read, there's been lots of ideas thrown around. All have been shot down for one reason or another. 

This is a good rad: http://research.swtch.com/generic

In general, the Go language designers are pretty conservative when it comes to throwing in new features. I'm glad for that, I'm really burned by feature bloat ala C++. 

For now, the approach seems to be:

Is the code you want to "generify" performance critical?

1. If no - reflection might be ok for you, or just box/unbox interface{}'s

2. If yes - write the code as many times as you need to, or use some kind of code generation - feel free to use either external text generators or the std lib's own go/ast and the like. 

I agree it's not ideal, *but* - given that slices/maps/channels are already "generic", the need for "generics" in the language in general is greatly diminished, IMO. So it's a "wart", but a small wart in my book. 

Just my 2 cents...

[Nat Tuck]

Having builtin generic functions/types makes user created generics even more important, because you want to be able to wrap and/or simulate the existing interfaces. Consider something simple like a thread-safe map (where you want to wrap mutations in lock/unlock).

I'm not a fan of the discussion at http://research.swtch.com/generic, because the C++ implementation is really just an optimization of the C# (or Java) model. The compiler generating a specialized version of something for a specific set of template arguments is about as interesting to expose to the user as whether it unrolls a loop.

The only interesting question is whether there's something better than "angle bracket generics". I haven't seen any such proposals.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Kevin Gillette]

Generics almost always seems to come up in the context of writing libraries; application code rarely needs to do things generically. If you really want to write a generic library, and the language is non-generic, just don't write that library.

[Kevin Gillette]

Perhaps it hasn't occurred (or is applicable) to Go generics proposals, but "better" does exist: some languages have generics such that all Lists are Sequences, and thus a List of DerivedType is a also a Sequence of BaseType. The more limited generics that most people are familiar with would not allow the aforementioned equivalence; ironically, it's the limited generics that everybody seems to want.

[DV]

I"m sadly only familiar with "boring angle bracket generics", ala Java/C++/C#, but I'm assuming you're talking about Scala/Haskell? 

For me at least, the "price of admission" to actually learn (and understand) those languages too high, just to reap the benefits of "true" generics. I've started (and abandoned) the "Learn you a Haskell.." tutorial 4 times now. I'm not saying everyone is as dumb as me :-) and maybe implementing some ultra-powerful static type system like Haskell's truly is the way to go, or not go at all, but I personally would be happy-ish with the C++ approach - code generation, via some standard "go pregen" pre-processor type tool. 

I know certain 3rd party projects exist that do this, but none are standard, so none will truly catch on as "the way". Bloated executables is the price to pay, but that's only if you *use* generic code. The same would happen if you wrote the code N times anyway, one per instantiated type, so I don't see the big deal. 

I feel like I'm rambling at this point so I'll stop, but I'm curious as to what your opinion is. 

[Sokolov Yura]

When people says "we want generics" they really says "we want code generation". Generics is a form of with hard rules on definition and wild on application. But may be some thing simpler would be enough?

I don't need full power of generics wild application rules. I just need a comfortable way to paste some field and method definitions into my type.

[Gyepi SAM]

On Fri, May 23, 2014 at 01:23:11PM -0700, DV wrote:
> I know certain 3rd party projects exist that do this, but none are
> standard, so none will truly catch on as "the way". Bloated executables is
> the price to pay, but that's only if you *use* generic code. The same would
> happen if you wrote the code N times anyway, one per instantiated type, so
> I don't see the big deal.

I've never understood why people avoid using unpopular software.
For me, it is only sufficient for the software to work and to meet my needs.

One nice solution to the whole issue of generics is to move the code
duplication abstractions out of the target software and into a code generator.

These days, I write more code that writes Go code than I write Go code.
The resulting Go programs are refreshingly simple and fast;
just the sort of mind numbing dull code you'd rather use a computer program to write.

-Gyepi

[Gyepi SAM]

On Fri, May 23, 2014 at 11:30:51PM -0700, Sokolov Yura wrote:
> When people says "we want generics" they really says "we want code generation".

Yup! Been doing this for years now and never had to enter a discussion on
generics (until now).

-Gyepi

[chris dollin]

On 24 May 2014 07:30, Sokolov Yura <funny....@gmail.com> wrote:

When people says "we want generics" they really says "we want code generation".

Ummm ... no.

What they want may be /implemented/ using code generation. It isn't
the code generation that's the requirement.

(Consider SML, which has polymorphic functions not implemented
with "code generation".)

Chris

--
Chris "allusive" Dollin

[Юрий Соколов]

24.05.2014 16:06 пользователь "chris dollin" <ehog....@googlemail.com> написал:

There is only three ways to implement polymorphic functions: code generation, dinamyc dispatch, and interpretation. Both dispatch and interpretation still assumes, that there is more code produced/evaluated then one had wrote.

I think, SML generates code for each parameter combination of polymorphic function, and may be uses interpretation for repl.

[chris dollin]

On 24 May 2014 16:47, Юрий Соколов <funny....@gmail.com> wrote:

24.05.2014 16:06 пользователь "chris dollin" <ehog....@googlemail.com> написал:

> Ummm ... no.

>
> What they want may be /implemented/ using code generation. It isn't
> the code generation that's the requirement.
>
> (Consider SML, which has polymorphic functions not implemented
> with "code generation".)

There is only three ways to implement polymorphic functions: code generation, dinamyc dispatch, and interpretation.

I don't think a typical SML implementation does any of those
things for polymorphic functions. It just has a uniform size for

data values (and an appropriate type system) -- hence large

structures (for a small value of "large") are boxed.

Note that SML's polymorphism is /parametric/ polymorphism,

not OO-style polymorphism.

I think, SML generates code for each parameter combination of polymorphic function,

I don't think so. It doesn't need to.

(An /optimising/ compiler is of course free to make extra code

specialised as appropriate to the program at hand, but that's
a different game of dominoes.)

 

and may be uses interpretation for repl.

I'd expect incremental compilation rather than interpretation.

Certainly the Poplog implementation of SML does that.

[Юрий Соколов]

24.05.2014 20:33 пользователь "chris dollin" <ehog....@googlemail.com> написал:

>
> On 24 May 2014 16:47, Юрий Соколов <funny....@gmail.com> wrote:
>>
>>
>> 24.05.2014 16:06 пользователь "chris dollin" <ehog....@googlemail.com> написал:
>>
>> > Ummm ... no.
>>
>> >
>> > What they want may be /implemented/ using code generation. It isn't
>> > the code generation that's the requirement.
>> >
>> > (Consider SML, which has polymorphic functions not implemented
>> > with "code generation".)
>>
>> There is only three ways to implement polymorphic functions: code generation, dinamyc dispatch, and interpretation.
>
> I don't think a typical SML implementation does any of those
> things for polymorphic functions. It just has a uniform size for
> data values (and an appropriate type system) -- hence large
> structures (for a small value of "large") are boxed.

So that, it ought to use dispatch.

>
> Note that SML's polymorphism is /parametric/ polymorphism,
> not OO-style polymorphism.

Dispatch could like OO-style polimorphism, and could like not. It is still dispatch.

>>
>> I think, SML generates code for each parameter combination of polymorphic function,
>
> I don't think so. It doesn't need to.

If it is true, then it ought to use dispatch, as i said.

Consider: C# specialize templates only for value types, and all reference types uses same generated code with reliance on dispatch+jit. And Java have one code for all template instantiations, relying on dispatch+jit even more.

>
> (An /optimising/ compiler is of course free to make extra code
> specialised as appropriate to the program at hand, but that's
> a different game of dominoes.)
>  

Making extra code is a single way to avoid dispatch.

>>
>> and may be uses interpretation for repl.
>
> I'd expect incremental compilation rather than interpretation.
> Certainly the Poplog implementation of SML does that.

I was not sure and said "may be".

Go has a dispatch with interfaces, and it is really good for "bussiness code". But when performance is needed, then code generation is only way.

And, of cause type safety suffers a bit with interfaces - second need for generics/code generation(/may be polimorhics).

[Jesper Louis Andersen]

On Sat, May 24, 2014 at 6:33 PM, chris dollin <ehog....@googlemail.com> wrote:

I don't think a typical SML implementation does any of those
things for polymorphic functions. It just has a uniform size for

data values (and an appropriate type system) -- hence large

structures (for a small value of "large") are boxed.

This depends on the SML implementation. Note that a polymorphic type in SML can be "passed along" but there is no way you can do anything to it. So there is no need for a dynamic dispatch. This means you don't have to worry about a lot of things and you can use a boxed representation where you store something of pointer-size. Usual tagging schemes works here to pack (63-bit) integers into the pointer slot as well.

MLton (mlton.org) uses expansion of the polymorphic code into monomorphic code. It can do so because it is whole program compiling and thus knows each type used in the program.

Personally, I think the complexity of "generics" and their addition to Go stems from its choice of structural subtyping. Once you pick subtyping, you are stuck with a number of nasty type-level choices where none of them looks satisfying.

--
J.

[Jesper Louis Andersen]

On Sat, May 24, 2014 at 6:57 PM, Юрий Соколов <funny....@gmail.com> wrote:

So that, it ought to use dispatch.

It doesn't have to for polymorphic values. SML does need a dispatch for some implementations of functors however, but that is a different game altogether. The key is that a polymorphic value has no "methods" so to speak which can manipulate it. Thus you can pick a generic representation like a pointer (i.e., a box) and use that all over the place.

In a functor, you do need to know what structure you applied to it and there you have the distinction between dispatching or generation to a greater extent. Again, SML compilers pick different strategies. MLton expands functors through defunctorization, so it generates code. Again, it can do so because it is a whole program compiler[0]

[0] The price of which is that a self-compile of it own 150k+ lines of code takes a couple of gigabytes and around 1.5 minutes on a fast machine.

--
J.

[Юрий Соколов]

And still,  it is just implementation details. Semantically, polimorphics are still code generation: instead of writting function instance for each argument combination, you wrote rule to evaluator how to deal with those different arguments.

Every call to virtual method could ve considered as code generation. In fact, there is at least one language, which implements virtual call with "select" statement.

24.05.2014 20:33 пользователь "chris dollin" <ehog....@googlemail.com> написал:

[Юрий Соколов]

24.05.2014 21:04 пользователь "Jesper Louis Andersen" <jesper.lou...@gmail.com> написал:

>
>
> On Sat, May 24, 2014 at 6:57 PM, Юрий Соколов <funny....@gmail.com> wrote:
>>
>> So that, it ought to use dispatch.
>
>
> It doesn't have to for polymorphic values. SML does need a dispatch for some implementations of functors however, but that is a different game altogether. The key is that a polymorphic value has no "methods" so to speak which can manipulate it. Thus you can pick a generic representation like a pointer (i.e., a box) and use that all over the place.

"Dispatch" doesn't mean "methods". Even "dynamic dispatch" doesn't mean "methods" nor "virtual methods". "Dispatch" is chosing implementation depending on actual arguments. "Methods" is just one form to declare "dispatching".

"Methods" doesn't mean "dynamic dispatch". Even "virtual methods" doesn't mean "dynamic dispatch" (in presence of whole program analyser).

>
> In a functor, you do need to know what structure you applied to it and there you have the distinction between dispatching or generation to a greater extent. Again, SML compilers pick different strategies. MLton expands functors through defunctorization, so it generates code. Again, it can do so because it is a whole program compiler[0]
>

I said same thing: there is only two ways to IMPLEMENT polymorphic code: either (dynamic) dispatch or code generation (static dispatch), or both combined. Semantically this ways are same.

[chris dollin]

On 24 May 2014 17:57, Юрий Соколов <funny....@gmail.com> wrote:

24.05.2014 20:33 пользователь "chris dollin" <ehog....@googlemail.com> написал:

>
> On 24 May 2014 16:47, Юрий Соколов <funny....@gmail.com> wrote:
>> 24.05.2014 16:06 пользователь "chris dollin" <ehog....@googlemail.com> написал:
>>

>> There is only three ways to implement polymorphic functions: code generation, dinamyc dispatch, and interpretation.
>
> I don't think a typical SML implementation does any of those
> things for polymorphic functions. It just has a uniform size for
> data values (and an appropriate type system) -- hence large
> structures (for a small value of "large") are boxed.

So that, it ought to use dispatch.

I don't understand. Why "ought" it to use dispatch? It can just

a function call -- call the polymorphic function's body. Job done.

(Optimisation might make something more complex desirable,

or not.)

>
> Note that SML's polymorphism is /parametric/ polymorphism,
> not OO-style polymorphism.

Dispatch could like OO-style polimorphism, and could like not. It is still dispatch.

What, in your terms, does "dispatch" mean then?

[chris dollin]

On 24 May 2014 18:04, Юрий Соколов <funny....@gmail.com> wrote:

And still,  it is just implementation details. Semantically, polimorphics are still code generation:

I think that's a particulary odd way to describe ML-style polymorphism

for functions. There's no notion of "code generation" at the semantic level.

instead of writting function instance for each argument combination, you wrote rule to evaluator how to deal with those different arguments.

Well ... no. Take the case of a map function

    let map f [] = []
        | h:t = f x : map f t

(my ML is very rusty, forgive any syntax clunkers)

This works as-is for functions of any type X->Y and lists of type [X]

and produces a list of type [Y]. Nobody has to worry about
argument combinators or dispatch. of course the type-checker

has to do some fancy footwork to work out and check the types,

but that's not how the code is /executed/.

[chris dollin]

On 24 May 2014 18:24, Юрий Соколов <funny....@gmail.com> wrote:

 

"Dispatch" is chosing implementation depending on actual arguments.

Excellent. Then ML-style functional polymorphism implementations
need not dispatch, or strictly, need only do a generic dispatch
(chose the only function available), because the code of the function
can be independant of the types of the arguments.

(An implementation can choose another way to do things, but that there
are implementations that do dispatch doesn't make ones that don't

go away.)

Chris

--
Chris "allusive" Dollin

[chris dollin]

On 24 May 2014 18:40, chris dollin <ehog....@googlemail.com> wrote:

need not dispatch, or strictly, need only do a generic dispatch

Degenerate (not "generic", pah)

Chris
 

--
Chris "allusive" Dollin

[Kevin Gillette]

On Friday, May 23, 2014 2:23:11 PM UTC-6, DV wrote:

I"m sadly only familiar with "boring angle bracket generics", ala Java/C++/C#, but I'm assuming you're talking about Scala/Haskell? 

Dart is an example of a more "conventional" language that has the previously described form of generics; they call them "covariant" generics, though after reading the wikipedia page I'm not sure that's the right term for what they're actually achieving. 

[David Symonds]

On 25 May 2014 14:34, Kevin Gillette <extempor...@gmail.com> wrote:

> Dart is an example of a more "conventional" language that has the previously
> described form of generics; they call them "covariant" generics, though
> after reading the wikipedia page I'm not sure that's the right term for what
> they're actually achieving.

"Covariance" refers to how related types X and Y cause composite types
X' and Y' to be related by virtue of their composition being based on
X and Y. The usual case is if X is a subtype of Y then List<X> is
considered a subtype of List<Y>; the "List" composite type "varies"
with its parametrised type. (There are other more complex cases, but
that doesn't really matter here.)

The issue here is how the parametrisation is tracked in the
implementation, since generated code may need to know how to deal with
the X in List<X>.

The rough approach one could imagine for a Go version of this is
similar to interfaces (which track a (type,value) pair): track both
types (i.e. List and X), plus the value.

A common solution elsewhere is "don't track it at runtime, but check
it at compile time", also known as "type erasure", which Java does.

Dart takes this solution one step further, which is "don't track it at
compile time", which works because it has a dynamic type system. This
has the unusual aspect that "don't track" is effectively elevated into
the language spec, rather than just being an implementation detail.

In this sense, Dart has "covariance" of such parametrised types, in
that List<X> can be used as a subtype (or rather, a compatible type)
of List<Y>, even if X and Y are unrelated.

[Jesper Louis Andersen]

On Sat, May 24, 2014 at 7:24 PM, Юрий Соколов <funny....@gmail.com> wrote:

I said same thing: there is only two ways to IMPLEMENT polymorphic code: either (dynamic) dispatch or code generation (static dispatch), or both combined. Semantically this ways are same.

Indeed. And in a language like SML the parametric[0] polymorphism is such that you can often avoid a dispatch at all, because what you want statically holds. The SML function

fun len [] = 0

   | len (_ :: xs) = 1 + len xs

has type 'a list -> int for any type 'a. Since it doesn't scrutinize the contents of the list, there is no reason to dispatch on the content. You just know that whatever you stuck into the list can fit into a pointer, and you are good to go. The Go equivalent is something along the lines of

count := 0

for e := l.Front(); e != nil; e = e.Next() {

count++

}

This ought to work with any kind of list content because we don't use the element for anything but its structure. If we do something along the lines of count = count + e.Value, then the type of the content becomes important, and likewise in SML. If we write

fun len [] = 0

| len (x :: xs) = x + (len xs)

then the type is inferred to be int list -> int and the function isn't polymorphic anymore. No need for a dispatch here either.

The TL;DR is: Beware of the word polymorphism. It means different things in different contexts. To an OO programmer it is way different compared to an SML programmer.

[0] Note we a talking parametric polymorphism. A way to see those are that they are implicitly generated template instances for a very limited setting, whereas C++ templates are an explicit parametric polymorphism construction that allows for more but then can't automatically be figured out.

--
J.

[Jesper Louis Andersen]

On Sun, May 25, 2014 at 9:50 AM, David Symonds <dsym...@golang.org> wrote:

In this sense, Dart has "covariance" of such parametrised types, in
that List<X> can be used as a subtype (or rather, a compatible type)
of List<Y>, even if X and Y are unrelated.

Do note that this choice makes the type system unsound. I.e., there are programs which will type check that are not well-formed. Indeed, it is caught at runtime, but this will imply a considerable cost in execution speed which then has to be plugged by employing 10 JIT compiler writers for 3 years and counting :)

--
J.

[Kevin Gillette]

Right, and I agree with your stated explanation of covariance. I've just heard dart talks in which X is a subtype of Y and List is a subtype (or implementer) of something like Iterable, so List<X> is a subtype of all of the following: List<Y>, Iterable<X>, and Iterable<Y>. I recall hearing _that_ being referred to in the talk(s) as the property that makes it "covariant," though I could have been misremembering/mishearing or they could have misspoke.

At any rate, that specific form of generics goes beyond the typical crop of language generics capabilities. At the same time, that form is much less applicable to Go; we could have had direct language support for a special "iterator" interface such that it could be used in for-range statements, and it would not have been particularly difficult (the design and implementation seem straightforward); but it, and the Uniform access principle as a whole, were consciously excluded from the language, and there are idioms for streaming from unending data sources (use callback iterators or channels, and/or batching) and processing finite variable-length data (deal with it as a slice, and avoid the overhead of repeated function calls).

The kinds of generics that Go would actually benefit I suspect is more than none but less than what mainstream generic languages have. If we had "full featured" generics, we'd lose a lot of orthogonality (or gain a lot of incomprehensible magic). Even covariance would only really make sense in terms of interfaces and the concrete types that implement them.

[Kevin Gillette]

Dart's entire type system is essentially optional; they do regularly (and seemingly proudly) admit that their type system is unsound; Go sacrificed theoretical "coolness" for readability, and Dart traded theoretical soundness for convenience. I didn't intend to indicate that Dart's approach was in any way applicable to Go or in any strong, statically typed context -- rather, I was just using it as an example of where generics, in the general, language-agnostic sense, can end up.

[Sokolov Yura]

воскресенье, 25 мая 2014 г., 12:36:36 UTC+4 пользователь Jesper Louis Andersen написал:

On Sat, May 24, 2014 at 7:24 PM, Юрий Соколов <funny....@gmail.com> wrote:

I said same thing: there is only two ways to IMPLEMENT polymorphic code: either (dynamic) dispatch or code generation (static dispatch), or both combined. Semantically this ways are same.

Indeed. And in a language like SML the parametric[0] polymorphism is such that you can often avoid a dispatch at all, because what you want statically holds. The SML function

fun len [] = 0

   | len (_ :: xs) = 1 + len xs

what about

    fun sum [] = 0
        | sum (x :: xs) = x + sum xs

??????? I could hardly imagine this function works without runtime dispatch or/and code generation.
Or may be SML doesn't allow instantiation of this function for both list of integer and list of float?
Then it is... ah... "limited polymorphism"

Any way: yes, there is third option to implement "limited polymorphic functions" without dispatch and code generation: "onesized autoboxed polymorphic values".
In fact, Go has "tagged onesized autoboxed polymorphic values" - interfaces. And you can make the very same "polymorphic functions" on `interface{}`.
But it lack compile time type checking on them.

Maybe introducing of "parametrized types" with usages of interfaces as "onesized values" and compile time type check will satisfy half of generic's askers.
But other half asks for performance, and "onesized autoboxed polymorphic values" could not satisfy this need (simply because autoboxing pushes on GC).
So that, code generation is needed to implement "parametrized types" fast.

With need of code generation, "templates" and "parametrized types with polymorphic functions" has one big disadvantage: they need to instantiate code based on a call site - based on actual passed arguments. And I think this is most scary thing for Go language designers.

My suggestion: do not provide "call time parametrization", just give "declaration time code generation" in term of parametrized mixins/macroses.
More over, it looks like most of custom generics for Go already go this way. And this is really good way.

I will be just happy, if i could just paste some fields and methods to a new type (parametrized with types and/or names). I don't need anything more for Go.
Something like:

     import "rbtree"

     type MyItem struct {
         Key  int
         Value string
         rbtree.Fields(MyItem)
     }

     func (item *MyItem) Compare(other *MyItem) { ... }

     rbtree.Methods(MyItem)

 

[Sokolov Yura]

This ought to work with any kind of list content because we don't use the element for anything but its structure. If we do something along the lines of count = count + e.Value, then the type of the content becomes important, and likewise in SML. If we write

fun len [] = 0

| len (x :: xs) = x + (len xs)

then the type is inferred to be int list -> int and the function isn't polymorphic anymore. No need for a dispatch here either.

Oh, sorry, I've missed this.

So that, "polymorphism" is very limited in SML? SML lacks any "polymorphism" on non-parametrized types, so that, it doesn't need dispatch on non-parametrized types, so that, in presence of "onesized polymorphic values" it could implement "polymorphic" functions on parametrized types without code generation and dispatch.

But that is not the case for Go, cause a) it has values with different sizes, b) it has polymorphism even on simple values (constants could have a different concrete type).

[Kevin Gillette]

On Sunday, May 25, 2014 1:45:48 PM UTC-6, Sokolov Yura wrote:

    fun sum [] = 0
        | sum (x :: xs) = x + sum xs

??????? I could hardly imagine this function works without runtime dispatch or/and code generation.
Or may be SML doesn't allow instantiation of this function for both list of integer and list of float?
Then it is... ah... "limited polymorphism"

I'm pretty sure at least the GHC compiler uses code-generation at compile time to make that work. It's also not very much code in this example, and a lot of specializations can be generated for a small amount of binary. This example also only has one type; the problems with code generation occur when you have combinatorial type explosion, and need to generate an implementation for every possible combination of types (particularly when later used with runtime dispatch).

[m...@carlmjohnson.net]

On Saturday, May 24, 2014 1:24:35 PM UTC-4, Sokolov Yura wrote:

I said same thing: there is only two ways to IMPLEMENT polymorphic code: either (dynamic) dispatch or code generation (static dispatch), or both combined. Semantically this ways are same.

I'm curious: map[string]MyType — is the best way to describe how Go implements this internally dynamic dispatch or code generation or both? 

[Kevin Gillette]

iirc, the compiler generates hash functions for each underlying key type (though it may be that there's a general purpose hasher being used), and the runtime can use type information (key size, value size) to do map operations.