A proposal for generic in go

[xingtao zhao]

Here is my proposal for generic in go: https://docs.google.com/document/d/1nO7D15c2B3eq2kF62C0yUs_UgpkyPL2zHhMAmlq1l98/edit?usp=sharing

Many parts has not been finished, and just initial thoughts. In the proposal, I want to keep back compatibility. And I try to add the orthogonal feature only and keep the language still simple enough. 

Please add your comments on it. Hope it is useful and could inspire some new features in go 2.0

Thanks!

[Ian Lance Taylor]

Have you read the generics proposals linked from
https://golang.org/issue/15292 ?

Ian

[xingtao zhao]

I read your proposals now. My proposal is very similar to your proposal of type parameter - in fact, they are almost identical. But in my proposal, I am not going that far as in your proposal. I did not include the operators, thus all generic functions can only access the unknown type through interface it satisfied. In my proposal, I am not allowing to access the field of an unknown type. 

Another valuable part my proposal added in the generic struct. I think this is different from the implementation in your proposal. Your proposal convert everything to interface method calls. While in my proposal, we have a special memory layout and padding algorithm, which make access the field of a struct with unknown type very cheap - almost identical to access an element in a slice/array.

And in my proposal, we do not need to change the compiler too much, and do not need to slow down the complier speed a lot.

Anyway, looking forward to any comments for the valuable part in my proposal. Thanks! 

[parais...@gmail.com]

A good compromise would be to only implement "parametric" functions. append and make are" parametric" functions as they know what is their return type at compile time , no matter what type the array/slice argument is . That way people who don't want a generic type are happy as no generic type is introduced, and people who want to write functions like push/pop/map on arrays of any type in a type safe way. 

Go is full of compromises of that sort so it shouldn't be an "all or nothing" debate. 

Aside from the implementation, the most difficult matter is choosing the right syntax, such as

    func XOR<T>(array1 []T,array2 []T)array[]T{

        // implementation

    }

So yes, people would not be able to define their own type of container (set,queues,binary trees,...). But all these containers can be build from array or map structures and methods specific to each data structure could now be written in a "generic" way. 

At the end of the day we all want the same thing, compile time type safety, no more, no less.

[andrew...@gmail.com]

As for me then everything is much more simple if Go language (as the starting point) will  introduce a non-reified generics.

Non reified generics does not requires a complex runtime support (static code which was generated by the compiler will be enough).

Type checking of the type arguments performed at the compile time on the calller side (sender code).

The callee side (receiver code) remains unchanged as it is currently is.

This has some benefits:

1. This is a starting point (but not a no dead end) and point for a later enhancements

2. Does not requires significant changes in the compiler (codegen)

3. Does not requires significant changes in the runtime (engine)

4. Does not requires significant changes in the type system (just to add a few additional fields into the interface type presentation)

5. Does not requires significant changes in the reflection (just to adapt for slightly extended type presentation)

Because they (generic types) will be not reified on the callee side (receiver code) then compiler can generate the same code as it generates currently.

Only callers side will perform generic type checks before assignments of values with generic types and vice versa (to variables, constants, function and methods arguments).

That is.

type Foo<K, V> struct {

}

func (s *Foo) Get(key K) (val V) {

  // Here is generated unchanged code

  // The same as for non generic use

}

func some() {

  foo := Foo<string, int>{}

  // Generated by the compiler

  // _typ := _getRTypeOf(foo)

  // _typ.isGeneric = true

  // _typ.genParams = [2]_GenParam

  // _typ.genParams[0] = &_GenParam{key: "K", val: _getRType(interface{}}

  // _typ.genParams[0] = &_GenParam{key: "V", val: _getRType(interface{}}

  // _typ.genArgs = [2]*_RType{}

  // _typ.genArgs[0] = _getRType(string)

  // _typ.genArgs[1] = _getRType(int)

  // Also compiler statically performs type check bounds of the type arguments to type parameters assignments (if type bounds specified)

  var key interface{}

  key = bool

  // Generated by the compiler (safe guard)

  // _temp0 := key

  // _checkGenericArg(_typ, 0, temp0)

  // _temp1 := foo.Get(key)

  val := foo.Get(_temp0)

}

That is, the compiler always (if it cannot compute the type at compile time and cannot to check them statically) inserts "safe guards" type check before any kimd of an assignments.

The `_checkGenericArg(_typ, index, key)` also performs the checks to type parameter bounds (eg. for Foo<K string, V int>) for a given index of the type parameter and argument.

Callee code does not performs any type checks on incomming parameters.

It always think that incomming parameters has specified type.

That is, if type bounds ommitted then specified type is interface{}

If type bounds specified then specified type is itself

Eg.

type Type1<E> struct {

}

type Type2<E int> struct {

}

func(t *Type1) foo(val E) {

}

func(t *Type2) foo(val E) {

}

Generated as the following (that's easy)

func(t *Type1) foo(val interface{}) {

}

func(t *Type2) foo(val int) {

}

[andrew...@gmail.com]

Overhead at runtime will be not very big;

1. Generate each time an instance of specific generic type with arguments

2. Perform generic specific type checks before any kind of an assignements

1. The first overhead can be reduced (eleminated) by the static code generation of specified generic types with storing them in special place

Eg.

foo := Foo<string, int>{}

Since this code is static (which means that at runtime the arguments (string and int) remains unchanged then this type (Foo<string, int>) can be canonicalized (I can also say "hashed" but canonicalized is more precisely). pre-generated by the compiler and stored (to avoid re-creating it each time at runtime) for further use.

2. The second overhead can be reduced (eleminated) by the static code generation when compiler can compute types (used in assignments).

Since specific generic type is know at compile time then generic type checks (the same as regular, non generic) can be performed at compile time

[Micky]

It's never going to happen! To quote the powers-to-be, "The language is done".
Good luck!

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

[Rodrigo Kochenburger]

Micky, I'm not sure where you're quoting from but they never said it's never gonna happen.

From the FAQ: "Generics may well be added at some point." and "This remains an open issue".

https://golang.org/doc/faq#generics

[xingtao zhao]

That was my original thought. While later I realized that we still need some parameter check in the callee code to satisfy the interface matching (the generic version of each function in my proposal). And we need special assembler function for dynamic interface cast.

[andrew...@gmail.com]

>> While later I realized that we still need some parameter check in the callee code to satisfy the interface matching (the generic version of each function in my proposal).

A am sorry but your judgements is not correct.

Here is a proofs:

1. It is redundant to perform check of the correctness of the assignments after when assignement already made.

Eg.

val i int

i = 0

// It is redundant to perform check the correctness of the assignments of `i` after when assignement of `i` already made.

2. Fucntion is a callable piece of code which CAN have initial variables (function parameters) which SHOULD be assigned (via function arguments) before function invocation.

Of course, these parameters can be explicit and implicit.

Eg. receiver of the method is an implicit parameter but it still a parameter (function variable which would be assigned before function invocation implicitly by the compiler, or by the reflection construction).

That is, this code is equilvalent.

var i int

i = 0

// other code, `i` already assigned

func foo(i int) {

  // other code, `i` already assigned

}

3. Also you should to know that in a generic type system (type sytem with the generic types) each type is potentialy a generic type.

Here is a proof.

Each type in a generic type system looks like a function.

Type can have a [0..~] number of parameters which are declared by the type declaration and whose parameters can be assigned by the type arguments. If arguments omitted then parameters assigned to default values (types).

The same as the funtions.

// Declare type with 2 parameters, K and V

type Type<K, V> {}

// Declare type with 2 bounded parameters, K and V

type Type1<K string, V int> {}

// Instantiate new type with a specified arguments (the same as the function invocation)

// For simplicity we can imagine the following auto generated code

// if *__staticType1021 == nill {

//   *__staticType1021 = __createGenericType(__getType(Type1), __getType(string), __getType(bool))

//  That is, call to __createGenericType(*t RType, args... *RType)

// }

// foo := __newobject(*__staticType1021)

foo := Type1<string, bool>()

Another story when we use generic type on the callee side.

func (t *Type1) foo(key K) V {

  // Here compiler always assume that the type of `t` is a generic type `Type1` with a correctly assigned type arguments.

  // Assigned arguments does not need to re-check 

  // ___type0 := __getTypeOf(t)

  // Here is enough (since type are generic) rely only on that the each type argument bound to the type parameter

  ...

}

[Henry]

I think we should carefully consider whether generics is worthy enough to be added into the language. It is easy to add a feature, but nearly impossible to remove one without breaking the backward compatibility promise.

One thing for sure is that we are in the middle of a paradigm shift. I am seeing more and more codes blending OOP with elements of functional programming. Some OOP purists go as far as avoiding getter/setter and use DTO to allow data editing, which to me it looks like a separation of data and function in procedural programming. Whatever the latest trend is, we shouldn't let Go become another C++ by blindly following trends. Everything must be thought of carefully.

I was one of the generics supporters for Go in this forum, but now I am not so sure.

[andrew...@gmail.com]

>> I was one of the generics supporters for Go in this forum, but now I am not so sure.

But why?

Generic types is the same types as and the regular types.

Difference only in that the regular types does not have a parameters but generic types are always have at least one parameter.

This is why they are called generic (universal) types.

The same as you don't worry about that the function can have a parameters why you should worry about that the type can have a parameters?

When for types allowed to have parameters then this get a some benefits:

1. Generice types can be "configured" by some requirements (by their parameters)

2. Generice types can have a restrictions (eg. each parameter can have its own upper type bounds)

3. Generic types are universal types

Eg. Trivial example

type KeyValuePair<K, V> struct {

  key K

  val V

}

You can use this type everywhere since it is universal type.

Below is not the same type (because in generic type system K != V, but here interface{} == interface{}):

type KeyValuePair struct {

  key interface{}

  val interface{}

}

Because power of the generic types in that the they are variative:

- Covariant

- Contrvariant

- Invariant

And they, of course, can have a parameters.

[Henry]

I am not saying that generics is bad, but I am questioning whether generics is necessary.

[Micky]

I guess that's for diplomatic reasons. If you watch talks of core
contributors then I believe you'll know what I mean :)

[andrew...@gmail.com]

>> I am not saying that generics is bad, but I am questioning whether generics is necessary.

Please, do not panic.

If you worry about the following things:

- Generated code will grow when used generics

- Generated code will be more complex when used generics

- Execution performance will slow down when used generics

- Memory consumption will grow when used generics

I can say you.

- Generated code will NOT grow when used generics

- Generated code will NOT more complex when used generics

- Execution performance will NOT slow down when used generics

- Memory consumption will NOT grow when used generics

They are so arranged that they are universal for all uses cases and does not require a significant changes in the following things:

- Compilers

- Runtimes

- Reflections

Most of the type checks will be performed at the compile time only because the Go language is statically typed language.

Most of the type instances (instances of the generic types which will be created at runtime) will be stored for the further reuse (they will be not created again and again but they will retrieved from the hidden static variables, so called lazy getters).

Only when used reflection then they (newly created type instances) can get some overhead but just a little bit more then with non-generic types.

Generic types is not evil, nor complex.

They are still the same types but only with the parameters (this is single kind of complexity which for me is not complexity at all) and they are variative (but this is not a complexity this is just a rules).

[Ian Davis]

 

On Tue, Jun 21, 2016, at 01:45 PM, andrew...@gmail.com wrote:

>> I am not saying that generics is bad, but I am questioning whether generics is necessary.

 

Please, do not panic.

If you worry about the following things:

- Generated code will grow when used generics

- Generated code will be more complex when used generics

- Execution performance will slow down when used generics

- Memory consumption will grow when used generics

 

I don't believe most people in this mailing list are worried about those things. They are worried about things like code complexity, readability and increase in cognitive load to decipher chains of type definitions.

 

Ian

[andrew...@gmail.com]

>> increase in cognitive load to decipher chains of type definitions.

Sorry, but who are members of this mail lists?

This is a first time when I hear about such loads such as the `cognitive load`.

Also I am possible here a single person who does not know anything about the `cognitive load to decipher chains of type definitions`.

I am mostly business man and a programmer just for my own requirements.

I love to implements parsers, code generators, some effective algorithms for solving some problem at the most effective time.

Also my work includes a diagnose the failures and locate them.

And I want to apologize for my illiteracy (thick-headed), but I do not really was expecting that all members of this mail list worry mostly about the ` increase in cognitive load to decipher chains of type definitions` and don't worry about other things.

I am sorry.

[Ian Davis]

What I mean is that most people who have followed the past generics discussions already know it's possible to implement them with efficient memory use and performance. So they don't need to worry much about that.

 

What stops them being added to the language is: can they be implemented without making Go a much more complex language than it is now.  In my opinion complex or large languages result in code that is much harder and expensive to maintain over the long term.

 

Ian

 

[Henry]

You still haven't provided any argument why generics is indispensable.

The reason why I am no longer sure about my position in this issue is because -while I agree that generics is useful- I don't think that generics is essential. In fact, all of C++ features are useful and implemented in a very efficient manner, but take a look what happened when you slab that many features together. If you can do away with less, I think you should go for less. The trouble is deprecating language features is a lot harder than deprecating APIs in the standard library, while programming fads come and go.

[andrew...@gmail.com]

>> What I mean is that most people who have followed the past generics discussions already know it's possible to implement them with efficient memory use and performance. So they don't need to worry much about that. 

Thank you for explanation.

>> can they be implemented without making Go a much more complex language than it is now

What is a measure of the syntax complexity in the Go language.

What this means and how they should be measured such a relative criteria?

- Much more complex

- More complex

- Slightly more complex

- Little bit more complex

Also how you personally measure these cognitive loads?

1.Sample (pattern)

type KeyValuePair interafce {

  key interface{}

  val  interface{}

}

2.Sample (pattern)

type KeyValuePair<K, V> interafce {

  key K

  val  V

}

What about that a value of the #2 sample is more complex than #1 sample on the 146%?

With permissible error of no more than 5%.

I think that possible we should to start a discussion about that problem (complexity measurement of the Go language perception).

I'm not kidding.

[Egon]

On Tuesday, 21 June 2016 17:18:04 UTC+3, andrew...@gmail.com wrote:

>> increase in cognitive load to decipher chains of type definitions.

Sorry, but who are members of this mail lists?

This is a first time when I hear about such loads such as the `cognitive load`.

https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX4pi-HnNjkMEgyAHX4N4

Also I am possible here a single person who does not know anything about the `cognitive load to decipher chains of type definitions`.

See http://www.boost.org/, although it is at the very far end of the spectrum (for example Dijkstra algorithm). Or, examples in "Modern C++ Design Generic Programming".

Or if I take the trivial example and write some facilitated code (I know that concurrent map API wouldn't look like that):

package conc

type Map<K,V> struct {

  Entries []Entry<K,V>

}

type Entry<K, V> struct {

  Key K

  Value V

}

package main

func PrintItems<T>(m conc.Map<Person, T>, format func(T)string) {

  var entry conc.Entry<Person, T>

  for m.Next(&entry) {

    fmt.Println(entry.Key.Name, format(entry.Value))

  }

}

func main() {

  m := conc.NewMap<Person, string>()

  PrintItems<string>(m, func(x string) string { return x })

}

And I'm not doing anything complicated, yet. This approach doesn't properly isolate the generic parts and you get code that is completely mixed with it.

I am mostly business man and a programmer just for my own requirements.

I love to implements parsers, code generators, some effective algorithms for solving some problem at the most effective time.

Also my work includes a diagnose the failures and locate them.

And I want to apologize for my illiteracy (thick-headed), but I do not really was expecting that all members of this mail list worry mostly about the ` increase in cognitive load to decipher chains of type definitions` and don't worry about other things.

I am sorry.

https://github.com/golang/proposal/blob/master/design/15292-generics.md

Here are some official proposals that were unfit:

* https://github.com/golang/proposal/blob/master/design/15292/2010-06-type-functions.md

* https://github.com/golang/proposal/blob/master/design/15292/2011-03-gen.md

* https://github.com/golang/proposal/blob/master/design/15292/2013-10-gen.md

* https://github.com/golang/proposal/blob/master/design/15292/2013-12-type-params.md

+ Egon

[xingtao zhao]

For example:

type Int int

func (i Int) Add(j Int) Int { return i + j }

type Number<T Number<T>> interface {

    Add(j T) T
}

If we want Int satisfy the interface Number<Int>, we have to create two versions of function Int.Add, one for concrete type Int, one with generic type T

And if we want to support:

var i Int

var v interface{} = i

var n Number<Int> = v.(Number<Int>)

We will have to create a stub for Int.Add in itable of Number, and dynamically adapt the parameter types at runtime.

[Axel Wagner]

The issue is, that a "KeyValuePair<K, V>" (no matter if you implemented it via generics or like you mention via interfaces) is a fundamentally useless type and generics encourage people to add useless types. A "KeyValuePair<K, V>" is a "struct { Key K, Value V }", plain and simple. It's not an interface and it's not a generic type, it's simply a struct.

I agree, that generics are useful, but they seem to be mainly useful for people who write "frameworks", not so much for people who write "applications" and so far, go is pretty much a language for the latter. Whenever people try to justify generics, they do it from a "I want to write a framework" POV - and whenever I miss generics, I do because I'm currently writing a framework of some kind.

Generics empower abstractions, but most programmers are very bad at building abstractions, so if you make it easy to build abstractions, you will end up with a lot of bad abstractions (have a look at java). So, to a certain degree, the value of go is, to *not* make building abstractions overly simple. That leads to abstractions being used only where they are essential and being left out where they are superfluous. This is where reduced cognitive overhead comes into play - limiting the levels of abstractions that people need to deal with to the bare essentials. Java is bloated and hard to use, not because the language is bad, but because it has a history of programmers building bad abstractions into it which gets stacked on top of each other. So, yes, if you compare a bad abstraction using interfaces with a bad abstraction using generics, generics will, in general, compare very well. But you just shouldn't build the bad abstraction in the first place.

The second concern with complexity is the spec. The exact behavior and semantics of generics need to be spec'ed and useful generics need a lot specification. For example, the current rules for type inference can be understood completely just by looking at a single expression and it's type and it's correspondingly simple to implement and spec. Generics usually need more powerful type inference methods to not be cumbersome, which will take up a lot of space in the spec. As humans, just like computers, have very little memory, the time it takes to understand the spec will grow superlinear with the length of it, due to frequent cache misses, so a long spec will significantly increase the time needed to learn the language. In the same vein, to understand a language, you need to know about interactions between it's different concepts, not just the concepts itself, so the needed space and time complexity to learn a language also grows quadratic in the number of concepts in the language (in general). All of that contributes to why people are wary of adding new concepts to go - the costs in terms of understanding and learning the language are huge and they grow very much superlinear in the number of concepts added, so each added concept must be carefully examined (I know go for years and I still learn new things about interactions between different concepts all the time).

I sometimes miss generics, yes, but I also believe adding them will make the language significantly harder to learn and will significantly worsen the quality of go code in the wild, so it would likely eliminate the reasons I like go currently (which is that go code is usually of exceptionally high quality, uniform and easy to understand).

--

[xingtao zhao]

I totally agree that I always want generics mainly when I am writing a framework. But I do not agree with you on that "go is pretty much a language for writing applications". I don't think go is powerful enough that we do no need any framework. I don't think we can always develop applications from the scratch. And I do think it is a big help for go if we have a lot of frameworks/libraries right on your hand. I do think it is a waste of engineer time to develop all the tools from scratch. Currently there are many frameworks/libraries have to use a lot of reflections just because generic is missing. This both makes the framework/library hard to use, slower, and less safe (a lot of runtime type checking which should/could be done at compiling time).

Think about how many people were asking: For the following types, how can I convert []Fool to []Barer, and via verse?

type Barer interface { Bar() }

type Foo struct{ ... }

func (f *Foo) Bar() { ... }

func Process([]Barer) { ... }

We have to tell them write a helper function to convert it. While in fact, if we have generic, and declare Process as:

func Process<T Barer>([]T) { ... } 

we do not need this kind of conversions at all. Interface is perfect for abstraction of the direct layer, while it is not good enough for abstractions inside of slice, map, chan, and structure, especially for slices which are used a lot in go code. I think this is a very big requirement by the users who is writing "applications" as well.

[Axel Wagner]

On Tue, Jun 21, 2016 at 9:38 PM, xingtao zhao <zhaox...@gmail.com> wrote:

I totally agree that I always want generics mainly when I am writing a framework. But I do not agree with you on that "go is pretty much a language for writing applications". I don't think go is powerful enough that we do no need any framework. I don't think we can always develop applications from the scratch.

I agree. But I don't think that "reuse" implies "framework", lest "requires generic". For example, you can write very easily reusable components based on net/http. Much, much more so, than what we probably would have with generics. For reuse you need to build abstractions, but the limited way in which we can abstract in go requires you to think hard about *good* ones.

 

And I do think it is a big help for go if we have a lot of frameworks/libraries right on your hand. I do think it is a waste of engineer time to develop all the tools from scratch. Currently there are many frameworks/libraries have to use a lot of reflections just because generic is missing.

No, they don't have to, they want to, because thinking about good abstractions is hard and reflection is the only way go gives you to write bad and ultimately useless abstractions.

 

This both makes the framework/library hard to use, slower, and less safe (a lot of runtime type checking which should/could be done at compiling time).

I disagree that safety for it's own sake is a useful goal. I consider type safety like I consider memory safety: You definitely want the vast majority of your code to be memory safe, but sometimes you have to use unsafe in limited cases and that's fine and it doesn't compromise the safety of the program as a whole. If the unsafe amount of code is small enough, it's easily verified by hand. The same goes for type-safety. It is fine to lose some type-safety in limited amounts of code, as long as you are careful, review it and make the limitations simple to understand.

A good example are the encoding packages - that's a decent place to use reflection, even though it limits your static type safety. But there is limited API surface that you need to understand, usually just two functions or so. It's easy to still write safe programs that way.

 

Think about how many people were asking: For the following types, how can I convert []Fool to []Barer, and via verse?

type Barer interface { Bar() }

type Foo struct{ ... }

func (f *Foo) Bar() { ... }

func Process([]Barer) { ... }

We have to tell them write a helper function to convert it.

No, we don't. We have to write a loop. We might opt to write a helper if we need to do that very often. But, honestly, we almost never do.

 

While in fact, if we have generic, and declare Process as:

func Process<T Barer>([]T) { ... } 

we do not need this kind of conversions at all. Interface is perfect for abstraction of the direct layer, while it is not good enough for abstractions inside of slice, map, chan, and structure, especially for slices which are used a lot in go code. I think this is a very big requirement by the users who is writing "applications" as well.

I disagree. You are, again, writing frameworks. A perfectly understandable and readable loop that turns a []Foo into a []Barer is four lines of code. A helper function is six. You probably need to do that on average at most .1 times per application that you write. I don't consider .6 lines of code per application saved a significant saving that could serve as an argument here.

And you are also misrepresenting, what would happen. Because realistically (look at existing languages with generics) the signature of that function would more be something like

func Map<Iterable<T>, O>(in T, f func(T) O) Iterable<O>

Just to save .6 lines of code per application.

[Alex Bligh]

On 21 Jun 2016, at 19:55, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:

> The issue is, that a "KeyValuePair<K, V>" (no matter if you implemented it via generics or like you mention via interfaces) is a fundamentally useless type and generics encourage people to add useless types. A "KeyValuePair<K, V>" is a "struct { Key K, Value V }", plain and simple. It's not an interface and it's not a generic type, it's simply a struct.
>
> I agree, that generics are useful, but they seem to be mainly useful for people who write "frameworks", not so much for people who write "applications" and so far, go is pretty much a language for the latter. Whenever people try to justify generics, they do it from a "I want to write a framework" POV - and whenever I miss generics, I do because I'm currently writing a framework of some kind.

Not sure that's fair.

For background, I'd quite like generics and liked Ian's last proposal quite a bit, but I also appreciate the cleanliness of go.

An recent example, in an real life application, where generics would have been useful is as follows.

I had a cache type thing built around a red-black tree, or more precisely two red black trees. The items were structs, and I needed one RB tree to be ordered by time of insertion (then key, for uniqueness), and one by key. One red-black tree dealt with expiries, and one with finding the item. In the absence of generics, I needed to embed the struct in a 'ByTime' and 'ByItem' struct, each of which implement a different 'LessThan' method. And everything that accessed the trees had a bunch of ugly casting from an interface{} to the relevant type. This does not make for readable code in any form. A RB tree that was implemented as a generic (and perhaps took a 'LessThan' function as a lambda) would have been far far cleaner in *my* code.

So saying it's all about being useful for people who write "frameworks" is unfair. It would actually have made the application code (i.e. the library user) far easier to read.

Of course it's possible to generate foolish uses (I would however note in passing that even with KeyValuePair things might not be as simple as you think, as it would (presumably) require comparability of K type items); however, it's also possible to perform stupidity with existing go syntax. The question is whether generics encourage it.

--
Alex Bligh

[ad...@gardener.com]

On Tuesday, June 21, 2016 at 2:56:01 PM UTC-4, Axel Wagner wrote:

The issue is, that a "KeyValuePair<K, V>" (no matter if you implemented it via generics or like you mention via interfaces) is a fundamentally useless type and generics encourage people to add useless types. A "KeyValuePair<K, V>" is a "struct { Key K, Value V }", plain and simple. It's not an interface and it's not a generic type, it's simply a struct.

I agree, that generics are useful, but they seem to be mainly useful for people who write "frameworks", not so much for people who write "applications" and so far, go is pretty much a language for the latter. Whenever people try to justify generics, they do it from a "I want to write a framework" POV - and whenever I miss generics, I do because I'm currently writing a framework of some kind.

generics would greatly reduce the work required to reproduce or possibly eliminate all work when building container types.

 

Generics empower abstractions, but most programmers are very bad at building abstractions, so if you make it easy to build abstractions, you will end up with a lot of bad abstractions (have a look at java). So, to a certain degree, the value of go is, to *not* make building abstractions overly simple. That leads to abstractions being used only where they are essential and being left out where they are superfluous. This is where reduced cognitive overhead comes into play - limiting the levels of abstractions that people need to deal with to the bare essentials. Java is bloated and hard to use, not because the language is bad, but because it has a history of programmers building bad abstractions into it which gets stacked on top of each other. So, yes, if you compare a bad abstraction using interfaces with a bad abstraction using generics, generics will, in general, compare very well. But you just shouldn't build the bad abstraction in the first place.

 

this is true with almost every feature of the language, so its absurd to even use this as an argument. generics would greatly reduced computational complexity.
 

The second concern with complexity is the spec. The exact behavior and semantics of generics need to be spec'ed and useful generics need a lot specification. For example, the current rules for type inference can be understood completely just by looking at a single expression and it's type and it's correspondingly simple to implement and spec. Generics usually need more powerful type inference methods to not be cumbersome, which will take up a lot of space in the spec. As humans, just like computers, have very little memory, the time it takes to understand the spec will grow superlinear with the length of it, due to frequent cache misses, so a long spec will significantly increase the time needed to learn the language. In the same vein, to understand a language, you need to know about interactions between it's different concepts, not just the concepts itself, so the needed space and time complexity to learn a language also grows quadratic in the number of concepts in the language (in general). All of that contributes to why people are wary of adding new concepts to go - the costs in terms of understanding and learning the language are huge and they grow very much superlinear in the number of concepts added, so each added concept must be carefully examined (I know go for years and I still learn new things about interactions between different concepts all the time).

this comment is more mumbo-jumbo
 

I sometimes miss generics, yes, but I also believe adding them will make the language significantly harder to learn and will significantly worsen the quality of go code in the wild, so it would likely eliminate the reasons I like go currently (which is that go code is usually of exceptionally high quality, uniform and easy to understand).

another absurd comment. generics would greater benefits and reduce the complexity of code.

[Marcus Yip]

On Tuesday, June 21, 2016 at 2:56:01 PM UTC-4, Axel Wagner wrote: The issue is, that a "KeyValuePair" (no matter if you implemented it via generics or like you mention via interfaces) i

[ad...@gardener.com]

generics would greatly improve code reuse for many algorithms- this one fact alone trumps all opposition. In fact, go's builtin container types have generics-like functionality already. Imagine arrays, slices, maps without this functionality- exactly, enough said. the arguments against generics are mind-numbing.

with that said, the best approach for those seeking generics in go is to produce preprocessers chained with the existing go tools, and wrapping that chain in a new toolset. this approach would reduce the effort needed to produce and maintain this new toolset. Most of the useful generic-like functionality is easily produced at compile time. I doubt there would be any benefit pushing generics into the language proper.

I'd also like to think generics could be introduced very similar to the how unsafe is designed- as a compiler feature.

[Matt Ho]

I think I have to agree with most of the posters here about generics.  In theory, I miss them.  However, in practice, I find that there are usually only a few times during the course of a project where I wish I had generics.  And then after writing a few lines of code to do what the generic would have done, I find I stop missing them.  

M

[andrew...@gmail.com]

>> The issue is, that a "KeyValuePair<K, V>" (no matter if you implemented it via generics or like you mention via interfaces) is a fundamentally useless type and generics encourage people to add useless types. A "KeyValuePair<K, V>" is a "struct { Key K, Value V }", plain and simple. It's not an interface and it's not a generic type, it's simply a struct.

I not agree with you only because with generics this pattern is always type safe.

Eg.

type Foo<K, V> struct {

  key K
  val V
}

func accepInt(i int) {
}

func some() string {
  foo := &Foo<string, int>()
  // some code

  // Compile error: `key` is not `int`
  acceptInt(foo.key)

  // Compile error: `key` (int) cannot be compared with `string`
  if foo.key == foo.val {
  }

  // Compile error: `key` is not `string`
  return foo.val
}

func baz(foo Foo<K, V>) bool {
  // Compile error: `key` (K) cannot be compared with `V`  
  return foo.key == foo.val
}

[Axel Wagner]

I don't know what you are doing, here, but…

func some() string {

    foo := struct{ Key string, Value int }{}

    // some code

    // compie error: Can't use foo.Key (type string) as int

    acceptInt(foo.Key)

    // compile error: mismatched types string and int

    if foo.Key == foo.Value {

    }

    // compile error: Can't use foo.Value (type int) as string

    return foo.Value

}

perfectly type safe.

[andrew...@gmail.com]

>> perfectly type safe.

Perfectly type safe but not perfectly reusable.

What If we slightly complicate the task?

Now is my code and I want to see on your code exampe (perfectly type safe but and perfectly reusable)

type Foo<K, V> interface {
  Get(key K) V
  Set(key K, val V)
}

func foo() (int, Foo<string, int>) {
  foo := &Foo<string, int>{}
  // ...
  foos := []Foo<K,V>{}
  // ...
  k := "London"
  // ...
  return 55, foo2(foos, 55, k)
}

// This code is type safe and reusable
foo2<K, V> (foos []Foo<K,V>, i int, key K) (V, Foo<K,V>) {
  foo := foos[i]
  return foo.Get(key), foo
}

[Axel Wagner]

And my point is and was: It doesn't *need* to be both type safe *and* reusable, unless you are focusing your energy on writing frameworks or treating type safety as a goal solely for it's own sake. It's perfectly fine to write small stuff yourself (for example like this) with explicit types and it's perfectly fine to locally not have strict compiler checks if you are doing something complicated that needs to be reusable. If you focus on application writers, instead of the authors of the frameworks they might use, you'll recognize that either choice just isn't that bad.

--

[andrew...@gmail.com]

Sorry for typo and possible spam but correct example here:

type Foo<K, V> interface {
  Get(key K) V
  Set(key K, val V)
}

func foo() (int, Foo<string, int>) {

  // Typo: foo := &Foo<string, int>{}
  foo := &fooStruct<string, int>{}
  

[Egon]

As a general suggestion:

Do not use fabricated examples, use concrete real-world examples.

Fabricated examples make harder to examine the practical side of generics -- i.e. how would you solve a particular problem with/without generics. The fabricated examples can suggest a problem where there is none, alternatively they can trivialize the actual problem without solving it in the first place. And by concrete real-world examples, I really mean code that someone would pay you to write.

Talking about reusability of faciliated code is nonsense, because that code isn't usable in the first place.

[andrew...@gmail.com]

>> And my point is and was: It doesn't *need* to be both type safe *and* reusable, unless you are focusing your energy on writing frameworks or treating type safety as a goal solely for it's own sake.

It does NEED to be BOTH type safe and reusable.

1. Type safety prevent the programmers to make errors.

2. Reusabilty prevent the programmers to implement the same functionality again and again and again and again and again and again...

Code reuse, also called software reuse, is the use of existing software, or software knowledge, to build new software, following the reusability principles.

Reusability

In computer science and software engineering, reusability is the use of existing assets in some form within the software product development process. 

Candidate design features for software reuse include:

• Adaptable
• Brief: small size
• Consistency
• Correctness
• Extensibility
• Fast
• Flexible
• Generic
• Localization of volatile (changeable) design assumptions (David Parnas)
• Modularity
• Orthogonality
• Parameterization
• Simple: low complexity
• Stability under changing requirements

P.S.

We continue the discussion about the dangers of `to be both type safe *and* reusable`?

Me and most of us MUST focusing our energy on writing high quailty and reusable software.

If someone doesn't agree I will not retort.

Want write software only for himself? Not a problem, your energy are your energy.

[Axel Wagner]

You are not bringing anything new to the table here, except the attempt to insult my intelligence, apparently.

There are huge software projects out there written in languages that are less type safe than go and the vast majority of code written is not reusable. Both also aren't absolutes. There is no binary "type safe or not type safe" and no "reusable or not reusable". There are only more or less expressive type systems and there are only pieces of code that are easier or harder to reuse. Every language finds their own tradeoff for them and every programmer must find their own preferences for the tradeoffs they require. go is explicitly designed as an engineering language and the defining characteristic of engineering is the acknowledgment of tradeoffs. So, without acknowledging that this needs to be a tradeoff, there really is not much point in talking about how to improve go. If someone prefers the extreme, might I suggest agda instead of go? I don't know of a more type safe language out there.

On Wed, Jun 22, 2016 at 10:11 AM, <andrew...@gmail.com> wrote:

We continue the discussion about the dangers of `to be both type safe *and* reusable`?

That is not what I was saying. I was talking about the dangers of generics for producing clear and readable code. That is not an issue with being both, it's an issue with generics. "It needs to be both" just isn't a very good argument in favor of them.

 

Me and most of us MUST focusing our energy on writing high quailty and reusable software.

Instead, we seem to focus your energy on debating whether we need to add generics to go or not. There are people out there writing high quality and reusable software *right now*, both in go and not in go. Coincidentally, that's what I'm going to do now too.

 

Want write software only for himself? Not a problem, your energy are your energy.

I get paid to write and maintain large software in large teams, in many languages falling into very different spots on the scale of type safety and re-usability and my opinions are informed by that. You shouldn't presume that people disagree with you because they know less.

[andrew...@gmail.com]

>> You are not bringing anything new to the table here, except the attempt to insult my intelligence, apparently.

I do not have any claims to anyone personally.

I only defend my own point of view.

P.S.

Also I don't love to see or use some (not my own) code which written like a mess.

If I cannot understand some code then this does not means that this code is bad.

But if I know that a some code has been written carelessly and can be written more diligently then it gives me a negative reaction on that work (if there was no reason to write it carelessly).

That is, write code once and and use it everywhere.

Or more precisely, write (high quality and reusable) code once and and use it everywhere (and give the possibility to use it to everyone).

The generics programming are very good suit for that.

In the simplest definition, generic programming is a style of computer programming in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. 

The term generic programming describes a programming paradigm whereby fundamental requirements on types are abstracted from across concrete examples of algorithms and data structures and formalised as concepts, with generic functions implemented in terms of these concepts, typically using language genericity mechanisms as described above.

P.S.

I am sorry but here we discuss mostly about the advantages and disadvantages of the generic programming (of course, in Go language).

Here we do not discuss: How to coding in Go language without generic programming.

I think that it should be different topic with appropriate title.

[Egon]

Are there any points missing in the summary? 

This thread was a about a specific proposal, but as usual with threads they diverge from the original topic.

 

Here we do not discuss: How to coding in Go language without generic programming.

I think that it should be different topic with appropriate title.

The version without generics is necessary to compare how well a particular generics approach improves the current language and code.

[Andrew Mezoni]

>> The version without generics is necessary to compare how well a particular generics approach improves the current language and code.

I am sorry but this is obviously that any useful feature (in the context of solving problems) improves the current language and code.

Another question: how new (version of the) language will look cosmetically with this newly added feature.

I found that the second question here more important then the first.

It is obviously correct that the code with a generics (in appropriate place) would be more useful then other code.

But here I undestand one interesting thing which states: Some obviously useful feature can significantly spoil the overall picture of language.

For me this is very strange only because even a C language also has been improved after when it initially was introduced.

In the years following the publication of K&R C, several features were added to the language, supported by compilers from AT&T and some other vendors. These included:

• void functions (i.e., functions with no return value)
• functions returning struct or union types (rather than pointers)
• assignment for struct data types
• enumerated types

C99 introduced several new features, including inline functions, several new data types (including long long int and a complex type to represent complex numbers), variable-length arrays and flexible array members, improved support for IEEE 754 floating point, support for variadic macros (macros of variable arity), and support for one-line comments beginning with //

The C11 standard adds numerous new features to C and the library, including type generic macros, anonymous structures, improved Unicode support, atomic operations, multi-threading, and bounds-checked functions. 

P.S.

I guess I should think that this is very bad, because my first acquaintance with the language began with the ZX-Spetrum and continued with the Borland Turbo C.

Indeed, the C language is now looks much worse cosmetically than before. 

But should I regret it?

Maybe...

[Viktor Kojouharov]

https://golang.org/pkg/math/ and https://golang.org/pkg/container/ are just two stdlib packages that would greatly benefit from some kind of generics. I'm pretty sure there are more packages in the stdlib that would be greatly improved. And that's just the standard library. 

[Viktor Kojouharov]

On Tuesday, June 21, 2016 at 9:56:01 PM UTC+3, Axel Wagner wrote:

The issue is, that a "KeyValuePair<K, V>" (no matter if you implemented it via generics or like you mention via interfaces) is a fundamentally useless type and generics encourage people to add useless types. A "KeyValuePair<K, V>" is a "struct { Key K, Value V }", plain and simple. It's not an interface and it's not a generic type, it's simply a struct.

And yet the 'K' and 'V' within the struct are generic types. A struct is never simple. That's its whole point.

 

I agree, that generics are useful, but they seem to be mainly useful for people who write "frameworks", not so much for people who write "applications" and so far, go is pretty much a language for the latter. Whenever people try to justify generics, they do it from a "I want to write a framework" POV - and whenever I miss generics, I do because I'm currently writing a framework of some kind.

A lot of these 'applications' that you think are the language's main target are built on top of libraries, including stdlib, written by that same language. And these same libraries can benefit from having generics, once again, including stdlib.

 

Generics empower abstractions, but most programmers are very bad at building abstractions, so if you make it easy to build abstractions, you will end up with a lot of bad abstractions (have a look at java). So, to a certain degree, the value of go is, to *not* make building abstractions overly simple. That leads to abstractions being used only where they are essential and being left out where they are superfluous. This is where reduced cognitive overhead comes into play - limiting the levels of abstractions that people need to deal with to the bare essentials. Java is bloated and hard to use, not because the language is bad, but because it has a history of programmers building bad abstractions into it which gets stacked on top of each other. So, yes, if you compare a bad abstraction using interfaces with a bad abstraction using generics, generics will, in general, compare very well. But you just shouldn't build the bad abstraction in the first place.

I've found this type of thinking quite poisonous. The "lets bereave ourselves of something universally lauded as useful, because it _might_ be used in the wrong manner by some people" mentality is just wrong and prevents any kind of useful evolution under any context. 

 

The second concern with complexity is the spec. The exact behavior and semantics of generics need to be spec'ed and useful generics need a lot specification. For example, the current rules for type inference can be understood completely just by looking at a single expression and it's type and it's correspondingly simple to implement and spec. Generics usually need more powerful type inference methods to not be cumbersome, which will take up a lot of space in the spec. As humans, just like computers, have very little memory, the time it takes to understand the spec will grow superlinear with the length of it, due to frequent cache misses, so a long spec will significantly increase the time needed to learn the language. In the same vein, to understand a language, you need to know about interactions between it's different concepts, not just the concepts itself, so the needed space and time complexity to learn a language also grows quadratic in the number of concepts in the language (in general). All of that contributes to why people are wary of adding new concepts to go - the costs in terms of understanding and learning the language are huge and they grow very much superlinear in the number of concepts added, so each added concept must be carefully examined (I know go for years and I still learn new things about interactions between different concepts all the time).

And yet this hasn't stopped people from successfully learning and utilizing languages that have generics are part of their specifications. The fact still remains that unlike a lot of other proposed languages additions that are immediately dropped, generics are still open for discussion by the language developers themselves. 

I sometimes miss generics, yes, but I also believe adding them will make the language significantly harder to learn and will significantly worsen the quality of go code in the wild, so it would likely eliminate the reasons I like go currently (which is that go code is usually of exceptionally high quality, uniform and easy to understand).

I'm sorry, but that's just fearmongering. Unless you have some kind of magic crystal ball, there's now way you'd know how the quality of go code will change. You don't even know what the implementation will look like ...

[Egon]

On Wednesday, 22 June 2016 15:32:53 UTC+3, Andrew Mezoni wrote:

>> The version without generics is necessary to compare how well a particular generics approach improves the current language and code.

I am sorry but this is obviously that any useful feature (in the context of solving problems) improves the current language and code.

Yes.. Of course, this presupposes that the particular generics approach is useful.

How would you demonstrate that one generics approach is more useful than another?

Another question: how new (version of the) language will look cosmetically with this newly added feature.

I found that the second question here more important then the first.

It is obviously correct that the code with a generics (in appropriate place) would be more useful then other code.

Which generics approach?

Which places need that kind of generics?

Should the language solve all generics related problems or only some?

Are there better solutions to those problems than generics?

Would some meta-programming approach negate the need for generics?

Also, is "useful in some particular case" the best metric to decide whether something should be included in the language?

e.g. #define max(a,b) ((a) < (b) ? (b) : (a))

But here I undestand one interesting thing which states: Some obviously useful feature can significantly spoil the overall picture of language.

For me this is very strange only because even a C language also has been improved after when it initially was introduced. 

Have you also looked at the proposals that were rejected? If someone made the proposal, it must have been useful to someone.

In the years following the publication of K&R C, several features were added to the language, supported by compilers from AT&T and some other vendors. These included:

• void functions (i.e., functions with no return value)
• functions returning struct or union types (rather than pointers)
• assignment for struct data types
• enumerated types

Were there any competing proposal for those same feature sets? Why were the others rejected whereas these particular ones accepted?

Also, what if, instead functions just allowing returning struct/unions, it would have also allowed to return multiple parameters? Would that have resulted better or worse C code?

[Sean Russell]

On Tuesday, June 21, 2016 at 10:29:37 AM UTC-4, Henry wrote:
> You still haven't provided any argument why generics is indispensable.

That can't be the litmus for language feature inclusion; if it was, Go would resemble ASM.

In my personal experience, something North of 50% of my non-trivial applications could have been more simple with some form of generics allowing me to reduce code duplication. In particular, any application dealing with demarshaling of data from a large set of similar functions (e.g. web calls) are good examples. Have 30 functions to make the same web calls and perform the same demarshaling calls -- especially where the web call may be more complex, as in a SOAP call -- does not make the code cleaner, easier to cognitively parse, or more safe. Indeed, in almost every such case, generics reduce code duplication and make the code safer from bugs, and easier to maintain.

Indispensable? That's subjective, and very few language features satisfy that requirement. For me, the strongest argument against it is that if the core Go team can't think of a way to implement it cleanly and efficiently, then I trust it's a hard problem. I'm sure they've looked at it; it must be the single most commonly requested, hashed-over, and proposal-backed feature.

--- SER

[Andrew Mezoni]

>> The fact still remains that unlike a lot of other proposed languages additions that are immediately dropped, generics are still open for discussion by the language developers themselves. 

I think that the problerm only in the Go developers brcause them even does try to implement them experimentally.

That is so called "hidden" implementation when the runtime engine supports the feature but compiler does not.

That is, available for testing only through the reflection but without grammar specification on that how to declare and use time at compile time.

As for me, they should have them (support of the generic types) in the runtime engine and in the reflection for the testing purpose but does not introduce them until they not decide that them are ready for real use.

[Axel Wagner]

On Wed, Jun 22, 2016 at 2:55 PM, Viktor Kojouharov <vkojo...@gmail.com> wrote:

And yet the 'K' and 'V' within the struct are generic types. A struct is never simple. That's its whole point.

I don't know what you mean by that. A struct is very simple, it's flat data.

 

A lot of these 'applications' that you think are the language's main target are built on top of libraries, including stdlib, written by that same language. And these same libraries can benefit from having generics, once again, including stdlib.

I agree. But I also think they can suffer from them. And I don't find it at all obvious which effect will dominate. From my experience with other languages, the overall effect will probably be negative, because the number of places where they help is very small, whereas the number of places where they hurt and are still being used (judging, again, from other languages) is very large.

 

I've found this type of thinking quite poisonous. The "lets bereave ourselves of something universally lauded as useful, because it _might_ be used in the wrong manner by some people" mentality is just wrong and prevents any kind of useful evolution under any context. 

Again, I am judging here from my experiences with other languages that do have generics and I am also taking into account the arguments brought forth by people proposing them for go. There is strong evidence that the correct phrasing is "will", not "might".

And yet this hasn't stopped people from successfully learning and utilizing languages that have generics are part of their specifications.

Yes, but I haven't claimed impossibility, but hardship. Let's look at it from this way: If generics are as indispensable as claimed here, why are people still using go then? For years the adoption of go has grown, not dropped, especially for large-scale applications and despite a lack of generics which is painted as a necessity. That just doesn't make any sense. I'm claiming that the reason go is still being used is *because* it's lack of generics (and other features), rather than despite of it. It's because it's a comparatively simple and easily understandable language.

 

The fact still remains that unlike a lot of other proposed languages additions that are immediately dropped, generics are still open for discussion by the language developers themselves. 

Yes. And I would treat proposals by the go team very differently from the random repeated proposals to golang-nuts by people I have never heard of. Because they've come up with the language as I like it and I trust them to not add a proposal that goes contrary to it's spirit.

 

I'm sorry, but that's just fearmongering. Unless you have some kind of magic crystal ball, there's now way you'd know how the quality of go code will change.  You don't even know what the implementation will look like ...

As mentioned above, I'm working from my experience with languages that currently have them and from examples people have put forward to justify their need. As most if not all "wild" proposals so far have argued from a standpoint of existing implementations and tried to apply existing implementations to go, I consider that very fair.

[Thomas Bushnell, BSG]

Really? How would you implement math.Max with generics? 

Thomas

--

[Michael Jones]

The wonderful history of symbolic algebra at IBM (Scratchpad, Scratchpad II) resulted in a third system, Axiom, that has always seemed to me a bright lesson in types. It boldly goes into the topic with rigor, using category theory to decide what relationships make sense and what the nature of a tensor cross product of types truly is. 

A key part of that is the notion of more general and more specific types. This makes it possible to define a function that needs arguments supporting a less than order relationship so it could be applied to integer and real arguments, but not to complex numbers. This is just the mechanism that makes a generic Max() easy to create. Imagine a definition like:

func {T type, where a,b ∈T allows a<b} Max(a, b T) T {

if a < b {

    return b

}

return a

}

This is a nice way to answer the riddle and it is just what Axiom supports (but expresses differently).

http://axiom-developer.org/axiom-website/bookvol2.pdf

Michael Jones

michae...@gmail.com

[Thomas Bushnell, BSG]

But Michael, that implementation isn't right for floats! Check out the actual source for math.Max.

[Michael Jones]

Yes, for floats with NANs and the like, you must specialize. My replacement for the standard library sort (3x to 10x faster in the common case) had to have more macro generators than expected just to handle the "uncomparables" in float32 and float64.

You are right about that issue.

P.S. By the way, Hi! Good to hear from you.

[Thomas Bushnell, BSG]

This is why I like this example. Generics induce people to write the wrong thing instead of thinking about the right thing. When you start thinking of the right thing, you often discover better solutions.

I think the sort package's way of doing sorting and binary search are so clearly better than almost any generic implementation I've seen, that I think generics are a bad idea for this reason alone.

Thomas

[Henry]

Having completed an earlier project, my colleagues and I sat down to review the team performance and what we could do better next. My colleague proposed an intriguing idea and we decided to randomly pick two components of our past projects that could be implemented independently from the rest of the projects and were easy to test. We rewrote the components from using OO (object oriented) to using PP (procedural). I was surprised with the result. The number of lines was reduced by about 30%. We were able to see things that were hidden behind the complex interaction of objects before, and simplified the codes considerably. Performance was improved by about 5%. This was no surprise because I always knew that OO has a bit of an overhead and the code simplification also helps. Maintainability is a bit subjective, but my colleagues and I think that the PP codes are easier to read and simpler to understand. The main obstacle in OO is with understanding the model employed. In our case, we has components that were outsourced to some offshore developers before, and we often had to rely on external documentation to understand the model they use. What was intuitive to them was not very intuitive to us. With PP, my other colleague who was not involved with rewriting the codes thinks that our PP codes can be understood by reading the source codes alone. However, the main selling point to me is the reduction in loc. For every 1000 lines of OO codes, we can save about 300 lines of codes with PP.

This experience makes me question many things and wonder whether the advances in programming for the past 40 years are really improvements over earlier methodologies. Everything I was taught of in college now seems questionable. Some people may argue that -in my case- it is probably a case of bad OO design and that if they get it right, OO should yield substantial benefits, especially when it comes to maintainability. The key phrase here is 'if they get it right'. OO allows abstraction, including over-abstraction, that is limited only by imagination. How do you know when you reach the right design?  

Returning to the topic, instead of arguing about hypothetical uses of generics, we should test it in real projects and see whether the benefit of generics outweighs its cost. There are other languages that support generics and may be used to test this. I personally have doubts over the necessity of generics. I think if they get it right, generics should be beneficial. The key here again is 'if they get it right'.  The room for potential abuse of generics which leads to incorrect design probably outweighs its benefits. 

[Egon]

On Thursday, 23 June 2016 06:41:07 UTC+3, Thomas Bushnell, BSG wrote:

This is why I like this example. Generics induce people to write the wrong thing instead of thinking about the right thing. When you start thinking of the right thing, you often discover better solutions.

It's also a great example why real-world examples are better for discussion.

 

I think the sort package's way of doing sorting and binary search are so clearly better than almost any generic implementation I've seen, that I think generics are a bad idea for this reason alone.

To me the major issues with C++/Java/C# generics is that they are too fine-grained. Often they are declaration scoped with meaningless type parameter names "T", "K".

The most promising generics idea I've seen is packages with interface specialization. 1. it's harder to abuse, 2. you end up building packages as usual with interfaces, 3. minimal change to the language. However it has some drawbacks - it doesn't solve all the generics problems - only data structures and algorithms part. The generic "sort" package, with that approach, wouldn't look any different.

[Egon]

On Thursday, 23 June 2016 07:59:16 UTC+3, Henry wrote:

Having completed an earlier project, my colleagues and I sat down to review the team performance and what we could do better next. My colleague proposed an intriguing idea and we decided to randomly pick two components of our past projects that could be implemented independently from the rest of the projects and were easy to test. We rewrote the components from using OO (object oriented) to using PP (procedural). I was surprised with the result. The number of lines was reduced by about 30%. We were able to see things that were hidden behind the complex interaction of objects before, and simplified the codes considerably. Performance was improved by about 5%. This was no surprise because I always knew that OO has a bit of an overhead and the code simplification also helps. Maintainability is a bit subjective, but my colleagues and I think that the PP codes are easier to read and simpler to understand. The main obstacle in OO is with understanding the model employed. In our case, we has components that were outsourced to some offshore developers before, and we often had to rely on external documentation to understand the model they use. What was intuitive to them was not very intuitive to us. With PP, my other colleague who was not involved with rewriting the codes thinks that our PP codes can be understood by reading the source codes alone. However, the main selling point to me is the reduction in loc. For every 1000 lines of OO codes, we can save about 300 lines of codes with PP.

This experience makes me question many things and wonder whether the advances in programming for the past 40 years are really improvements over earlier methodologies. Everything I was taught of in college now seems questionable. Some people may argue that -in my case- it is probably a case of bad OO design and that if they get it right, OO should yield substantial benefits, especially when it comes to maintainability. The key phrase here is 'if they get it right'. OO allows abstraction, including over-abstraction, that is limited only by imagination. How do you know when you reach the right design? 

I've seen similar reduction or increase in readability, in multiple ways, i.e. going from PP <-> OO; OO <-> PP, PP <-> FP, FP <-> LP, of course the reverse as well etc. I've even gotten into a habit of prototyping critical parts in multiple languages.

I suspect the major contributor in rewrites isn't the new paradigm, but rather the paradigm shift itself. You notice new ways of compressing/cleaning the code, but at the same time you can retain ideas from the previous iteration. The new paradigm/language gives you new constraints and at the same time relaxes some -- resulting in easier creative thinking. In essence you combine the "good design from OO" and "good design from PP". Obviously, some of these translations will be lossy and make code larger -- so you will hit a limit eventually.

When you talk about OO, it's useful to mention what language you were using, as there is no gold-standard what OO is. Even in a particular language you could write it in multitude of ways. I've noticed, that the major contributors to complexity in OO, are inheritance and displaced methods (e.g. multiple objects interact and the method describing interaction is put into one of those objects). Both cause fragmented artifacts - in one case the inherited type is scattered around several places, in the other case the interaction code is scattered between objects. With PP you tend to use your instincts more (rather than some principles), and end up putting related pieces together. However it doesn't mean you cannot fragment the code in PP (http://number-none.com/blow/john_carmack_on_inlined_code.html).

Now, sure, you might not agree about how big issue inheritance/methods are in OO. What I'm trying to get here is that there are deeper properties than the paradigm, language or a feature that causes problems.

It's the same with generics approaches -- there are underlying forces that cause these bad-designs, and one of the questions is, how to minimize the bad-design while still keeping the benefits.

[Mandolyte]

Earlier someone asked about real world examples. The obvious standard library was mentioned. It only took me a few seconds to remember Jan Mercl's interval package. A quick look suggests that the current 1200+ lines of code would be reduced to about 250.

If this sort of code is written very often, the "prove it to me" argument against generics will be less effective.

So, how about some more examples?

[Egon]

On Wednesday, 29 June 2016 01:51:58 UTC+3, Mandolyte wrote:

Earlier someone asked about real world examples. The obvious standard library was mentioned. It only took me a few seconds to remember Jan Mercl's interval package. A quick look suggests that the current 1200+ lines of code would be reduced to about 250.

I'm not sure what application would require that full extent of the interval package. Currently the only thing I see importing it was https://godoc.org/github.com/cznic/wm, but it only used only one func from it... so the whole package could be replaced with ~10 lines.

So the problem is that I don't know a real-world use-case for that package -- hence I cannot judge it's API design and quality. Sure the interval package might be necessary, but is there a simpler design? Is the genericness of that package even warranted?  How would it affect user code by making it generic. Are there alternate designs? Should it implement a tree instead?

[Egon]

Just to be clear what I consider a great example for analyzing generics:

1. a package containing something non-trivial and generic

   alternatively, multiple packages that could have benfitted from that generic design

2. 3+ real-world packages/applications use that package

   By real-world here I mean it wasn't written for learning or fun, but rather solving a concrete problem.

3. the package is specialized with at least 4 different types

   ~4 types is where manual management of specializations becomes too verbose

4. the package is implemented "in the best way"

   e.g. linked list would be a bad example, because it's usually a bad solution in the first place

5. the package using it, is written "in the best way"

   e.g. code using a custom implementation of map without a good reason is a bad example

Reasoning for those points, 1. is just the baseline implementation and ensures that the specializations can use a non-trivial amount of code; 2. ensures that package 1. is actually valuable in practice; 3. ensures that the package would benefit from generics; 4./5. are mainly for discussion and whether the right problem was solved, maybe 1. can be significantly simplified or is unnecessary.

PS: I'm not saying there isn't value in smaller examples, but when all listed conditions are met, then it's easier to analyse what trade-offs can be made and how those will affect code using it.

+ Egon

[Sean Russell]

On Wednesday, June 29, 2016 at 2:31:59 AM UTC-4, Egon wrote:

Just to be clear what I consider a great example for analyzing generics:

2. 3+ real-world packages/applications use that package

   By real-world here I mean it wasn't written for learning or fun, but rather solving a concrete problem.

How about one (a single) production application with 106 types, all sharing three common functions identical except for the type categories they operate over?  1411 LOC that could not only be reduced to around 300 (interesting that my numbers are similar to the one @Mandolyte came up with from 'interval') -- although, I'll state again that saving LOC isn't the killer feature of this request; it's the fact that a bug fix or other change has to be made in 25 different places.

 

4. the package is implemented "in the best way"

   e.g. linked list would be a bad example, because it's usually a bad solution in the first place

My example, detailed in another thread, is deserializing XML content from a legacy SOAP application, and normalizing and simplifying the data structures.  The 106 types, 25 functions, and 1411 LOC is just for the SOAP & deserializing.  There's a whole other chunk of code dealing with the conversion from type to type that I used introspection for (that was a mistake!) rather than deal with several more thousand lines of duplicate code.

My case is extremely error prone and difficult to maintain safely.  I'm afraid to touch the code.  There's enough customization on a couple types that templating wouldn't be much help.  I'd love suggestions of a better way to implement than copy/paste.  I can't even use introspection

The criteria you lay out assumes a public library; bespoke, single-purpose applications should also be able to be used as valid examples.

--- SER

[Egon]

On Wednesday, 29 June 2016 14:45:09 UTC+3, Sean Russell wrote:

On Wednesday, June 29, 2016 at 2:31:59 AM UTC-4, Egon wrote:

Just to be clear what I consider a great example for analyzing generics:

2. 3+ real-world packages/applications use that package

   By real-world here I mean it wasn't written for learning or fun, but rather solving a concrete problem.

How about one (a single) production application with 106 types, all sharing three common functions identical except for the type categories they operate over?

Hence, the either-or in packages and applications. The reason for multiple packages/applications is to ensure that it isn't an isolated problem affecting very few applications. Of course, it still is a good example... although not great. Also it gives more weight to that particular problem compared to other generic issues.

 

1411 LOC that could not only be reduced to around 300 (interesting that my numbers are similar to the one @Mandolyte came up with from 'interval') -- although, I'll state again that saving LOC isn't the killer feature of this request; it's the fact that a bug fix or other change has to be made in 25 different places.

 

4. the package is implemented "in the best way"

   e.g. linked list would be a bad example, because it's usually a bad solution in the first place

My example, detailed in another thread, is deserializing XML content from a legacy SOAP application, and normalizing and simplifying the data structures.

Could you link to it? I'm unable to find it...

 

The 106 types, 25 functions, and 1411 LOC is just for the SOAP & deserializing.  There's a whole other chunk of code dealing with the conversion from type to type that I used introspection for (that was a mistake!) rather than deal with several more thousand lines of duplicate code.

My case is extremely error prone and difficult to maintain safely.  I'm afraid to touch the code.  There's enough customization on a couple types that templating wouldn't be much help.  I'd love suggestions of a better way to implement than copy/paste.  I can't even use introspection

The criteria you lay out assumes a public library; bespoke, single-purpose applications should also be able to be used as valid examples.

As said, it's just criteria for a great example -- maybe "perfect example" would be a better name :). Obviously there is room for examples that fill only some or only fill partially those conditions.

[Øyvind Teig]

The suggestions of generics discussed here and in the referenced documentation, will it be possible to compile the "Go-with-generics" language into some idiomatic Go and compile it with the standard compiler? (I guess what idiomatic means is the real question here..). Or would it break idiomatic Go?

If it won't break it, wouldn't it be better to add some of this instead of leaving some of these important matters out? (I have read a guy mention concurrency and Haskell; the language is so flexible that it may be added any way. And it has. So there is no standard way for it)

Also, would it be possible to add generics around channels to (limit their functionality I assume (like not legal to address both sides of a channel in the same goroutine (I know it's sometimes nice)))? 

And make formal analysis (like transformation from Go-with-generics to CSPm) easier?

[charr...@gmail.com]

On Wednesday, June 29, 2016 at 3:42:51 PM UTC+2, Øyvind Teig wrote:

The suggestions of generics discussed here and in the referenced documentation, will it be possible to compile the "Go-with-generics" language into some idiomatic Go and compile it with the standard compiler? (I guess what idiomatic means is the real question here..). Or would it break idiomatic Go?

it can be done with using unsafe

 

[Øyvind Teig]

torsdag 30. juni 2016 18.04.13 UTC+2 skrev charr...@gmail.com følgende:

On Wednesday, June 29, 2016 at 3:42:51 PM UTC+2, Øyvind Teig wrote:

The suggestions of generics discussed here and in the referenced documentation, will it be possible to compile the "Go-with-generics" language into some idiomatic Go and compile it with the standard compiler? (I guess what idiomatic means is the real question here..). Or would it break idiomatic Go?

it can be done with using unsafe

?? 

[Andrew Mezoni]

>> it can be done with using unsafe

This is the only available method (and very suitable).

The same method used throughout in the Go language the runtime.

It's very easy to do that.

Problem only to find appropriate syntax for the current Go grammar for to be look as idiomatic Go.

I still not found that but I am still looking (this even is a bigger problem than "how to implement them?").

[Øyvind Teig]

I assume the scope of the discussion about introducing generics is not how Go-generics might hypothetically be transformed to idiomatic Go. I find no reference to "unsafe" in neither of these (already mentioned here):

• "Proposal: Go should have generics" by Ian Lance Taylor https://github.com/golang/proposal/blob/master/design/15292-generics.md 
  
• "proposal: generic programming facilities" by Andrew Gerrand https://github.com/golang/go/issues/15292 
  

Neither do I find any mention of "reflect", which I assume might be relevant.

From this I infer that adding generics to Go is a rather large affair. It also looks like that in the pages above.

More interesting, I don't see formal modeling verification mentioned in any of the generics-documents above, neither in this recent thread:

• "formal verification in Go? someday perhaps?" at https://groups.google.com/forum/#!topic/golang-nuts/MVITBF3TcOE
  

I know that Rob Pike was involved with formal verification since long ("Bell Labs and CSP Threads", by Russ Cox, see https://swtch.com/~rsc/thread/) and that this background was colouring much of how Go ended up. Has generics been discussed along this line: that Go-generics might be more/less suitable for formal verification?

Øyvind

[Egon]

On Friday, 1 July 2016 10:32:20 UTC+3, Øyvind Teig wrote:

I assume the scope of the discussion about introducing generics is not how Go-generics might hypothetically be transformed to idiomatic Go. I find no reference to "unsafe" in neither of these (already mentioned here):

• "Proposal: Go should have generics" by Ian Lance Taylor https://github.com/golang/proposal/blob/master/design/15292-generics.md 
  
• "proposal: generic programming facilities" by Andrew Gerrand https://github.com/golang/go/issues/15292 
  

Neither do I find any mention of "reflect", which I assume might be relevant.

From this I infer that adding generics to Go is a rather large affair. It also looks like that in the pages above.

More interesting, I don't see formal modeling verification mentioned in any of the generics-documents above, neither in this recent thread:

• "formal verification in Go? someday perhaps?" at https://groups.google.com/forum/#!topic/golang-nuts/MVITBF3TcOE
  

I know that Rob Pike was involved with formal verification since long ("Bell Labs and CSP Threads", by Russ Cox, see https://swtch.com/~rsc/thread/) and that this background was colouring much of how Go ended up. Has generics been discussed along this line: that Go-generics might be more/less suitable for formal verification?

I haven't seen such discussion. I can't even recall even seeing anywhere such formal verification system (one that is based on generics and isn't dependently typed). It's an interesting thought, but I cannot even imagine how to bind together generics and (non-trivial) formal verification. And then ... a formal verficiation implementation that doesn't slow down compilation.

[charr...@gmail.com]

On Wednesday, June 15, 2016 at 3:04:05 AM UTC+2, xingtao zhao wrote:

Here is my proposal for generic in go: https://docs.google.com/document/d/1nO7D15c2B3eq2kF62C0yUs_UgpkyPL2zHhMAmlq1l98/edit?usp=sharing

Many parts has not been finished, and just initial thoughts. In the proposal, I want to keep back compatibility. And I try to add the orthogonal feature only and keep the language still simple enough. 

Please add your comments on it. Hope it is useful and could inspire some new features in go 2.0

the parametrized struct got me interested, how to best handle the embedding the arbitrary type.

Especially passing said struct to a generic function.

type S<T> struct {

I1  int

C1  char

T1  T

I2  int

Ts1 [2]T

Is1 [10]int

Ts2 [53]T

C2  char

T2  T

Ts3 [2]T

Tp1 *T

I3  int

}


Now imagine that T=int8
For the reason, the following concrete struct satisfies the template:

type ActualS struct {

I1  int

C1  char

T1  int8

I2  int

Ts1 [2]int8

Is1 [10]int

Ts2 [53]int8

C2  char

T2  int8

Ts3 [2]int8

Tp1 *T

I3  int

}

Now, the concrete struct is passed to the algorithm that accepts S<T>.

func IllegalAlgo<T>(x S<T>) {
  x.T1 = x.T2  
}

 I think this should not be allowed, because variable x could have different sizes based on sizeof(T).

But passing the arbitrary large struct S via pointer could work:

func OKAlgo<T>(x *S<T>) {
  x.T1 = x.T2  
}

Now.
Obvious mode of operation would be that the procedure or algorithm would perform the multiplications by sizeof(T) to access fields.
In my opinion, would be best to move the generic-sized objects to the end (or require them to be placed at the end). This way said algorithm could operate on almost the whole object without need for arithmetic.

type S<T> struct {

I1  int

C1  char

I2  int

Is1 [10]int

C2  char

Tp1 *T

I3  int

//////////
T1  T

Ts1 [2]T

Ts2 [53]T

T2  T

Ts3 [2]T

}


 

Thanks!

[Andrew Mezoni]

>> Now imagine that T=int8

Generic struct always has the same size only because it uses pointers.

type S<T>  struct {

  elem T

  arr []T

}

Is the same as the following struct.

type S<T>  struct {

  elem unsafe.Pointer

  arr []unsafe.Pointer

}

This is because it is designed to be universal.

You may ask: Why use "unsafe.Pointer" instead of the "interface{}?".

My answer is that the "unsafe.Pointer" has less size ().

Size of the "unsafe.Pointer" is a size of "uintptr".

And size of the "interface{}" is a size of the following struct:

struct emptyInterface {

  typ *rtype

  data unsafe.Pointer

}

This means, if the "emptyInterface" (a.k.a "inteface{}") is universal structure, and "inteface{}" uses "unsafe.Pointer" for "data" field then why other universal (parametrized) type (eg. generic struct) should use other approach?

If the information about the type arguments must be strored directly into the "rtype" structure then why duplicate them in each field?

The "duplicate them" means use "interface{}" instead of the "unsafe.Pointer".

Moreover, it is easier to work with the "unsafe.Pointer" than with the "interface{}".

The "interface{}" in Go language means a "boxed" value.

This is convenient, but it adds overhead in comparison with the "unsafe.Pointer".

[charr...@gmail.com]

On Friday, July 1, 2016 at 1:53:46 PM UTC+2, Andrew Mezoni wrote:

>> Now imagine that T=int8

Generic struct always has the same size only because it uses pointers.

type S<T>  struct {

  elem *T

  arr []T

}

I believe you've made a mistake here, elem needs to be *T , not T

[Andrew Mezoni]

>> I believe you've made a mistake here, elem needs to be *T , not T

This was just an abstract example.

I just wanted to say that if someone want to try implement a transpiller of the "Go.next" to the "Go" then the better way to represent the data of the different types (which are specified by the type arguments) in parametrized types is to use "unsafe.Pointer's".

Eg

type slice struct {

	array unsafe.Pointer
	len   int
	cap   int
}

type sliceType struct {
	rtype
	elem  *rtype
}

// arrayAt returns the i-th element of p, a C-array whose elements are

// eltSize wide (in bytes).
func arrayAt(p unsafe.Pointer, i int, eltSize uintptr) unsafe.Pointer {
	return unsafe.Pointer(uintptr(p) + uintptr(i)*eltSize)
}

This means that "unsafe.Pointer's" used everywhere for represent data of any kind.

That's all I want to say.

[Axel Wagner]

How does the compiler know sizeof(T)? If it's passed as an argument or saved together with the struct or something in that regard, you end up with the "java approach", if you have the compiler specializes the function per size, you end up with the "C++ approach" (also, in either case, there is no need for the "only pointers are allowed" kludge), from

http://research.swtch.com/generic

The most basic rule, for everyone arguing in favor of generics, is, that they need to decide which tradeoff they make and how they justify it. That blog post should be step 1 for everyone wanting to propose generics.

[Andrew Mezoni]

>> The generic dilemma is this: do you want slow programmers, slow compilers and bloated binaries, or slow execution times?

(The Java approach.) Box everything implicitly. 
This slows execution. 

I just want to add some clarification.

This does not slows a whole execution.

All that works fast will remain the same fast.

Of course, new (generic) code will be slightly slower by the following reasons.

1. Information about the types will be obtained not at the compile time but at the runtime (this requires a some time to access this information).

2. Type checking will be performed not at compile time but at the runtime (this also requires a some time to comparsion).

This is true but...

1. Information about the types can obtained at the compile time very fast

2. Requirements of performing the type checking at the runtime will not occur so often

Generic programming divides the code (which uses generic types) on the two different kinds:

- Generic code

- Parametrized code

Parametrized code used even in C language and, of course, it used currently on Go language.

Eg.

func set(slice []string, int i, val string) {
  slice[i] = val
}

func Set(list List<string>, int i, val string) {
  list.Set(i val)

}

This is identical (in purpose) parametrized source code.

Everything (both of them) are computed by the compiler and everything compiled into very effective and very fast binary code without the requirements to perform some additional work at the runtime (such as the type checking).

In contarst, this is a generic code (information about types is not known at the compile time).

func (r *List) Set(i int, val E) {
  r.slice[i] = val
}

Compiler, in this generic code, does not know what type of value will have a variable `val E` at runtime.

Here arrives is a reasonable question: "Should compiler perform type checking before performing such assignment?".

My answer is: ". No. In such case compiler should not perform type checking at runtime All required type checks already was performed previously."

Here is a proof:

type List<E> struct {
  slice []E
}

This means that the compiler is the guarantor of that the for some instance of the type `List<E>` the field `slice []E` with some type assigned to `E` of `List` will have the same type assigned to `E`.

Here is a proof:

list := &List<string>{}

// or

list := NewList<string>()

// where `NewList` is

func NewList<E>() *List<E> {
  i := &List<E>{}
  i.slice = make([]E, 5)
  return i
}

In both cases the compiler ensures that the every member of the generic type, which has the type `E`, will be assigned only to the specified type argument (in our case, `string`).

Now look again on our questionable code which possible can be slow.

func (r *List) Set(i int, val E) {
  r.slice[i] = val
}


What we (and compiler) know about it?
- The receiver (r *List) has some unknown type
- The parameter (val E) has some unknown type but we know that this type is the same as `E` in `List<E>`
- The field (List<E>.slice []E) of the receiver has some unknown type but we know that this type is the same as `E` in `List<E>`

Should compiler perform some (possible slow) type checking at runtime to compare the type `E` with type `E`?
What does this means?

This means that this generic code also can fast as it possible.

P.S.
The slow code mostly goes in the instantiation process but all the benefits from the use of new types cost to put up with it (and this is not very slow, and do not forget that arrays and maps in Go also has the "generics code" but it hidden from programmers).

Finally.

Question: "Does this code (with two parametrized types) requires the runtime type checks?"

var slice []int{}
var list List<int>{}
var v1 int

v1 = slice[1]
v1 = list.Get(1) // List<E> with the argument `E` set to `int` always returns the `int`

No. But will be executed sligtly slower than this code:

v1 = funcWhichAlwaysReturnsOnlyInt(1)

But why?
This is because generic function always returns the pointers that need to dereference:

v1 = list.Get(1)

// Compiled to

_temp0 := list.Get(1) // unsafe.Pointer, compiler know that it points to `int`
v1 = *(*int)(_temp0)

[Egon]

On Friday, 1 July 2016 21:34:10 UTC+3, Andrew Mezoni wrote:

>> The generic dilemma is this: do you want slow programmers, slow compilers and bloated binaries, or slow execution times?

(The Java approach.) Box everything implicitly. 
This slows execution. 

I just want to add some clarification.

This does not slows a whole execution.

All that works fast will remain the same fast.

Of course, new (generic) code will be slightly slower by the following reasons.

1. Information about the types will be obtained not at the compile time but at the runtime (this requires a some time to access this information).

Go has to run in environments where runtime code-generation / modification is not allowed. (https://docs.google.com/document/pub?id=1IXHI5Jr9k4zDdmUhcZImH59bOUK0G325J1FY6hdelcM)

[Andrew Mezoni]

>> Go has to run in environments where runtime code-generation / modification is not allowed.

Where you find that I wrote about that?

The generic code (not a parametrized code) executed in the same manner as the reflection works.

But with a single and very big differnce.

The reflection is slow because it designed to be "for all occasions".

The generic code are:

- Analysed by the compiler

- Optimised by the compiler

- Unnecessary code eliminated by the compiler (maximally reduced some procedures  to minimal overhead)

This is a main reason why the compiled generic code (not a parametrized code) in the most cases not a much more slower than a non-generic code (but not always).

P.S.

Seriously, where you found that I wrote something about the requirements of the "runtime code-generation / modification" in my examples?

Yes, my English is terrible but I never did not mention these notions.

[Egon]

On Friday, 1 July 2016 21:59:19 UTC+3, Andrew Mezoni wrote:

>> Go has to run in environments where runtime code-generation / modification is not allowed. 

Where you find that I wrote about that?

Yeah, sorry, my mistake:

1. Information about the types will be obtained not at the compile time but at the runtime

I assumed that meant that you build up some type-information and use that at runtime to optimize specific pieces of code.

[Axel Wagner]

On Fri, Jul 1, 2016 at 8:34 PM, Andrew Mezoni <andrew...@gmail.com> wrote:

>> The generic dilemma is this: do you want slow programmers, slow compilers and bloated binaries, or slow execution times?

(The Java approach.) Box everything implicitly. 
This slows execution. 

I just want to add some clarification.

This does not slows a whole execution.

All that works fast will remain the same fast.

Of course, new (generic) code will be slightly slower by the following reasons.

1. Information about the types will be obtained not at the compile time but at the runtime (this requires a some time to access this information).

2. Type checking will be performed not at compile time but at the runtime (this also requires a some time to comparsion).

This is true but...

1. Information about the types can obtained at the compile time very fast

No, it can't, unless you go the C++ way. That is the point. When a package declares a function taking a generic Type T, the compiler can not know anything about T. Because a parameter will be declared in a different package, so in a different compilation unit. The only way to make this work, is to instantiate a function per type or type size or something like that and that is the C++ way.

 

2. Requirements of performing the type checking at the runtime will not occur so often

One of the most cited reasons for generics is iterators and generic datastructurs. No, it's not going to "not occur so often". People are talking about replacing the most central pieces of their code with generics, otherwise they aren't particularly useful. That's the most fundamental dilemma about generics: For them to actually be useful, you need to replace often used code by a single generic implementation. It doesn't make sense to have generics and *not* call into generic code all the time.

I don't know what argument you are trying to make. I don't think you are making the one you think you are making.

func (r *List) Set(i int, val E) {

  r.slice[i] = val

}

How does the compiler know the address of r.slice[i], to put E into? Or the size of E, to copy it there? This is a very simple question, don't sidestep it. Try to answer it and you will realize, that you are either going the C++ way, or the Java way.

For non-generic code, the compiler knows the size of E, because it knows it's type, basta. So r.slice[i] is simply r.slice.ptr + sizeof(E) * i. If it doesn't know the size at compile time, as it can't, a priori, if E is generic and can be any time, it will need to replace sizeof(E) by something appropriate. And you then either let the compiler put in the size when it sees a call to Set and generates a function with the appropriate size (so it specializes the current code for concrete types once per size, the C++ way), or it needs to create a generic implementation of Set, which takes the size of E as a parameter, this is boxing, the java way.

You have to choose one and you need to give an argument why your choice is the correct one. That is the point of Russ' post, that there *is* no obviously right choice here.

P.S.
The slow code mostly goes in the instantiation process but all the benefits from the use of new types cost to put up with it (and this is not very slow, and do not forget that arrays and maps in Go also has the "generics code" but it hidden from programmers).

No. You are wrong. The only generic code in regards to slices and maps is the make function. The types itself *are not generic*. There is no []T type, there is only a []int, a []string and a []Foobar. At every point in your program where you use a slice, the type of the element type is *known at compile time*. The concrete type and everything. make/append is generic on the surface. Go chooses the C++ way here. But it also limits the different use-cases, so the increase in compile size is at most linear in the number of types used.

 

Finally.

Question: "Does this code (with two parametrized types) requires the runtime type checks?"

var slice []int{}
var list List<int>{}
var v1 int

v1 = slice[1]
v1 = list.Get(1) // List<E> with the argument `E` set to `int` always returns the `int`

No. But will be executed sligtly slower than this code:

v1 = funcWhichAlwaysReturnsOnlyInt(1)

But why?
This is because generic function always returns the pointers that need to dereference:

How does the generic function know the size of the return value? It needs to make sure, there is enough space allocated to return a pointer to. As list.Get is generic, it doesn't know it is going to return an int in a call, so how does it know how much to allocate?

You can not side-step the issue. A generic function *needs to know the size of the type parameter from somewhere*. And, to reiterate, you either do that by instantiating it per type and then make it a compile-time constant (C++ way), or you pass the size (java way) and thus incur a runtime cost, because you can't use specialized instructions and constant folding and in the end using a constant will always be faster.

[Axel Wagner]

You are still not making a clear decision about the generics dilemma here.

On Fri, Jul 1, 2016 at 8:59 PM, Andrew Mezoni <andrew...@gmail.com> wrote:

>> Go has to run in environments where runtime code-generation / modification is not allowed.

Where you find that I wrote about that?

The generic code (not a parametrized code) executed in the same manner as the reflection works.

That is the java way. You basically take a separate size argument.

 

But with a single and very big differnce.

The reflection is slow because it designed to be "for all occasions".

The generic code are:

- Analysed by the compiler

- Optimised by the compiler

- Unnecessary code eliminated by the compiler (maximally reduced some procedures  to minimal overhead)

This is the C++ way. You have a specialization per type.

This is a main reason why the compiled generic code (not a parametrized code) in the most cases not a much more slower than a non-generic code (but not always).

You either are choosing the java way, which slows down execution, or the C++ way, which slows down compilation (or you try, like you currently are, to walk around it by claiming you are doing some kind of mix, which would be fine, but it wouldn't eliminate those disadvantages, the parts you are doing the java way are slow to execute and the parts you are doing the c++ way are slow to compile).

 

P.S.

Seriously, where you found that I wrote something about the requirements of the "runtime code-generation / modification" in my examples?

Yes, my English is terrible but I never did not mention these notions.

[Axel Wagner]

Perhaps a better question is: Given a generic function

func Get(l List<E>, i int) E {

    …

}

var a List<int>{ 1,2,3}

var b List<string>{"1", "2", "3"}

var c List<float64>{1.0, 2.0, 3.0}

fmt.Println(Get(a, 0), Get(b, 1), Get(c, 2))

// Should print "1 2 3.0"

implement the code, a compiler would generate for this, in C (or, if you prefer, the current, real, go. But C is probably better). This is the best way to illustrate, how you envision it to work. Only then can we actually talk about what you are proposing here.

[charr...@gmail.com]

How does the compiler know sizeof(T)?

interesting question. About obtaining sizeof(T). The sizeof(T) is known from the call site calling the generic function, in particular from the type of variable that's passed to the generic function. What If generic function calls another generic function (possibly in different "module"? Now the T in callee is equal to T in caller, so sizeof is same, no need to do anything. (remember i use single parametric so there is no T1, T2 etc...)

After obtaining sizeof(T), it needs to be passed to the function. I'm no call convention expert so In my experiment I've did the stupid simplest thing to make it work,  Before a call to a generic function, I emitted  runtime setter to store it, then in function i get it from runtime. there is race, sure but can be swept under the rug by putting it to thread specific place, maybe G(goroutine) .
 

If it's passed as an argument or saved together with the struct or something in that regard, you end up with the "java approach", if you have the compiler specializes the function per size, you end up with the "C++ approach" (also, in either case, there is no need for the "only pointers are allowed" kludge), from

If go goes the Java way but does it somehow differently. Something clever but very practical. I believe this is possible.

Perhaps modify Golang's 2.0 calling convention, that EVERY function must get upon compilation one extra invisible-to programmer argument that is pointer that
when said function is generic, points to sizeof(T) storage place .
If you're calling to non-generic function it's just NULL, and it seems like a waste? but does it slow it down everything so much??

 

[Ian Lance Taylor]

On Fri, Jul 1, 2016 at 12:51 PM, <charr...@gmail.com> wrote:
>
> Perhaps modify Golang's 2.0 calling convention, that EVERY function must get
> upon compilation one extra invisible-to programmer argument that is pointer
> that
> when said function is generic, points to sizeof(T) storage place .
> If you're calling to non-generic function it's just NULL, and it seems like
> a waste? but does it slow it down everything so much??

A single function can have multiple arguments with different generic types.

If you need an extra parameter, I think you need to pass it normally,
not using some special mechanism.

Also you need to figure out how to make this work for methods when a
value of the type is stored in an interface.

Ian

[Andrew Mezoni]

>> How does the generic function know the size of the return value?

All your judgement are not correct only because you ask not a correct questions.

They return pointers to appropriate values.

Or you really think that the `map` also returns a value instead of pointer?

How it (map) can know the size of the return value

The `map` in Go language also generic type.

Caller (parametrized code):

var m map[Foo]Baz

...

v := m[Foo{}]

Callee (generice code):

// mapaccess1 returns a pointer to h[key].  Never returns nil, instead
// it will return a reference to the zero object for the value type if
// the key is not in the map.
// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {

Returned value will be obtained in parametrized code (where m is map[Foo]Baz) from the pointer because both (caller and  callee which is instance of the map[Foo]Baz) operates with the values of the same types.

The `map` does not know the types and its sizes. It only know that it instantiated (by the type argements) at the runtime "to be ready to work for these types".

This approach is called "generices programming" and it used in Go language in the following types:

- Channels

- Slices

- Maps

P.S.

// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.

This note not for the programmers. This not for the developers.
This is because programmers always gets a value from the dereferenced pointers but developers can call this function directly.

[Axel Wagner]

On Fri, Jul 1, 2016 at 9:51 PM, <charr...@gmail.com> wrote:

How does the compiler know sizeof(T)?

interesting question. About obtaining sizeof(T). The sizeof(T) is known from the call site calling the generic function, in particular from the type of variable that's passed to the generic function.

When the compiler is compiling the generic function, it doesn't know anything about the call-sites. Because they could be in a different compilation unit.

Unless you are suggesting, that the compiler compiles it into a generic version, which is then put into the object file and instantiated to a concrete version at link time. In that case the answer is "I am favoring the C++ way". Which is fine. But you need to justify why that is the way you are favoring.

 

After obtaining sizeof(T), it needs to be passed to the function. I'm no call convention expert so In my experiment I've did the stupid simplest thing to make it work,  Before a call to a generic function, I emitted  runtime setter to store it, then in function i get it from runtime. there is race, sure but can be swept under the rug by putting it to thread specific place, maybe G(goroutine) .

This scheme, in it's essence ends up being the "box everything" java version (not the least because of what ian is saying about interfaces). i.e. the only thing you may be gaining by this scheme over the java way, is that the compiler can do an unboxing optimization at the "root" of the call-stack (after inlining and everything). Java does that too. You are talking about the Java path. And that's okay, but you need to justify why you think the Java path is the correct one.

 

If it's passed as an argument or saved together with the struct or something in that regard, you end up with the "java approach", if you have the compiler specializes the function per size, you end up with the "C++ approach" (also, in either case, there is no need for the "only pointers are allowed" kludge), from

If go goes the Java way but does it somehow differently. Something clever but very practical. I believe this is possible.

Perhaps modify Golang's 2.0 calling convention, that EVERY function must get upon compilation one extra invisible-to programmer argument that is pointer that
when said function is generic, points to sizeof(T) storage place .
If you're calling to non-generic function it's just NULL, and it seems like a waste? but does it slow it down everything so much??

As explained above, you are re-phrasing the Java way. Whether the box is attached to the data or "passed as a parameter", at the end it'll be the same size and will have the same disadvantages, like cache locality, additional indirections and the need to do arithmetic, instead of folding constants.

[Andrew Mezoni]

Can I ask the question out of turn?

Ok. I ask.

What wrong in Java way?

What wrong in C# way?

Of course, they have a boxing/unboxing concepts.

Does this means that boxing/unboxing is very, very, very slow operations and should not be used even in Java or in C#?

But they used. They used at least in generics programming in the languages.

Does this means that generics programming in these languages are very, very, very slow?

Does this means that generics programming in other languages are very, very, very fast?

Generics programming are always compromise between the performance and universality.

Where universality always means an usability.

C++ way is out of the scope.

@Ian Lance Taylor

Add an additional reserved field into the potential generic types and this will allows to starts some experiments with implementing transpilers from the "Go.next" to the "Go".

Eg.

type structType struct {

rtype

fields []structField

reserv unsafe.Pointer // place for the extra info about generic/parametrized type

}

type interfaceType struct {

rtype

methods []imethod // sorted by hash

reserv unsafe.Pointer // place for the extra info about generic/parametrized type

}

[Axel Wagner]

On Fri, Jul 1, 2016 at 10:00 PM, Andrew Mezoni <andrew...@gmail.com> wrote:

>> How does the generic function know the size of the return value?

All your judgement are not correct only because you ask not a correct questions.

I am not asking the questions you want me to ask, but that doesn't make it the wrong question. And it doesn't mean, a proposal for generics doesn't need to be able to answer them.

 

They return pointers to appropriate values. 

Or you really think that the `map` also returns a value instead of pointer?

Yes, it does. It returns essentially a struct, which then contains pointers, to memory with well-known at compile time sizes. That there is an indirection in the struct doesn't mean that a function doesn't need to know the size of the memory it is allocating for a bucket. A function doesn't return a map[S]T, it returns a map[int]string and thus it knows that every bucket of that map must contain a word for the int and two words for the string.

 

How it (map) can know the size of the return value

The `map` in Go language also generic type.

No, it's not. Again, there is no map[S]T. It's a fabrication. Every map has a concrete, specific, compile-time known type. Every function that uses a map knows the exact type of both key and value, so there is no problem here.

If you are proposing to generalize map, what you are really proposing, is the C++ way, because that's essentially what go is doing (just that the compiler knows very well what the concrete behaviors of the type are and that it can inline some parts that are appropriate and use generic versions in other places, where it isn't. It can't do that for actual generic types).

 

I'll repeat the question: Your proposal needs to be able to compile this (or equivalent) code to C (or assembler, or go, or something specific enough that we can talk about what it is actually doing):

func Get(l List<E>, i int) E {

    …

}

var a List<int64>{ 1, 2, 3 }

var b List<string>{ "1", "2", "3" }

var c List<float64>{ 1.0, 2.0, 3.0 }

fmt.Println(Get(a, 0), Get(b, 1), Get(c, 2))

as it needs to be able to compile this (or something equivalent) to something specific, make us understand what you are proposing, by providing what this compiles to. For example, write a go program, which accurately reflects, what this is supposed to do, which is a) valid with the current semantics of go, e.g. runs on the playground) and b) prints "1 2 3.0". You may change the generic input, but it needs to maintain the invariant that it only contains one implementation of the Get function.

It doesn't make sense to continue a discussion where you are continuing to handwave your way around the questions. The good thing about this last specific question is, that a valid proposal of how to handle generics must be able to answer it, while at the same time, it is impossible to handwave your way around it.

[Axel Wagner]

On Fri, Jul 1, 2016 at 10:23 PM, Andrew Mezoni <andrew...@gmail.com> wrote:

Can I ask the question out of turn?

Ok. I ask.

What wrong in Java way?

What wrong in C# way?

Nothing inherently. It just takes a performance penalty and it needs to be justified that this performance penalty is worth it. That is the only thing I am saying. The post by Russ doesn't say that any tradeoff is *wrong*. It just says that a tradeoff must be made, explicitly and that there, so far, seem to be no inherently correct way to make it. Unless you figure out a way around the trilemma, you *must* justify why your choice of the three is the correct one.

 

Of course, they have a boxing/unboxing concepts. 

Does this means that boxing/unboxing is very, very, very slow operations and should not be used even in Java or in C#?

But they used. They used at least in generics programming in the languages.

Yes. And go has as one explicit design goal not to do them ("control over memory layout"). This can be revised, of course, but you need to justify why that cost is worth it.

 

Does this means that generics programming in these languages are very, very, very slow?

No, just slower than in other languages (like C++ or rust) and that it is not clear that this performance hit is obviously worth it.

 

Does this means that generics programming in other languages are very, very, very fast?

Also no, generics programming is somewhat slow most of the time. But faster, yes.

 

Generics programming are always compromise between the performance and universality. 

Where universality always means an usability. 

*Exactly*. That is *precisely my point*. There is a tradeoff to be made but that tradeoff *needs to be justified*. You need to make an argument for which of the three you choose; slow programmers, slow compilers or slow programs. Currently go chooses the former, because it was deemed good enough like it is and the productivity hit of slow compilers wasn't deemed acceptable (and when you see all the outrage about compile speeds since 1.4, the community seems to agree) and the hit on performance was deemed to high a cost. It is possible to change that choice, but the change needs justification and a simple "I don't like slow programmers" isn't a particularly good argument.

 

C++ way is out of the scope.

Why do you think that? You seem to both "slow compilers" and "slow programmers" (otherwise we wouldn't have this argument) to be out of the question. But where does that judgement come from? How do you justify this particular choice in the Trilemma? 

[Andrew Mezoni]

>> That there is an indirection in the struct doesn't mean that a function doesn't need to know the size of the memory it is allocating for a bucket.

Your judgement are now incorrect.

Obtaining the size of the of the type is not so hard at runtime.

It always known from `rtype`

This is how map allocates buckets.

It creates an array of the type `t.bucket`.

Where `t` is `mapType` and  the `bucket` is a field in this type which specifies the the better type of storing buckets.

if h.buckets == nil {
	h.buckets = newarray(t.bucket, 1)
}

How new array know the size?

This is easiest question in the world.

Answer is: From a given type.

// implementation of make builtin for slices
func newarray(typ *_type, n uintptr) unsafe.Pointer {
	flags := uint32(0)
	if typ.kind&kindNoPointers != 0 {
		flags |= flagNoScan
	}
	if int(n) < 0 || (typ.size > 0 && n > _MaxMem/uintptr(typ.size)) {
		panic("runtime: allocation size out of range")
	}
	return mallocgc(uintptr(typ.size)*n, typ, flags)
}

Look how passed the `key` into the `map` method `get` (mapaccess).

It passed as the unsafe.Pointer.

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {

P.S.

The `map` is very well oprimized in Go language (it has more than one method for different groups of types).
But this does not means that the code generated for use "a single method for every groups of types" approach would be much more slower.

[Axel Wagner]

You are still avoiding answering the one simple question that would explain perfectly well, without any room for misunderstanding, what you are proposing. I would also like to point out again that I am not arguing in favor or against the C++ or the Java way. I am simply trying to get you to answer the question which of the two you are proposing.

--

[Andrew Mezoni]

>>  I would also like to point out again that I am not arguing in favor or against the C++ or the Java way. I am simply trying to get you to answer the question which of the two you are proposing.

Neither one nor the other.

Only the "Go way".

And I am did not propose.

I am only try bring understanding that Go already partially ready for that.

[Mandolyte]

IMHO, regarding the trilemma, I want slow compilers. This option means no penalty unless you actually use the generic feature. Want fast compiles, then don't use generics. I've never been convinced about the code bloat issue that gets tagged with slow compiles. I think the code bloat issue should also be tagged with slow programmers since we have to use the copy/paste method. That's both code bloat and slow programmers and is hard to maintain to boot.

By the way, I at appreciate the civil and earnest tone of this thread, passion and politeness can go to together.

[Chad]

What's generic programming?

 An implementation of overloading for datastructures and function/methods.

The compiler is left in charge of going through the code and specifying which types should actually be used.

Go restricts the overloading of function/methods.

So we are left with the specification of new datastructures.

To be fair, unless in very specific cases, datastructures specifically created to be safe for concurrent use are not too useful.

The reason being that their content is not deterministic. It is tied to the scheduler.

Write-only datastructures are probably the only interesting case that is interesting.

I mean, for instance, concurrent writes to a map while no reads occurs.

The only interesting case otherwise would be the concurrent reading/writing of an append only datastructure, but that would probably be a very specific tuning for speed.

So the only very interesting datastructures that would be remaining are datastructures that are fast to read from concurrently (maps are quite fast in Go)

Or fast to write to concurrently.

I wonder which kind of datastructures people may want to write.

But I have the impression that what people truly want is being able to overload functions. That's complicated. Multiple dispatch may be slow, perhaps unresolvable.. there are issues on that side. Besides introducing unwarranted implicitness.

The appeal of generics is probably a false appeal.

On Wednesday, June 15, 2016 at 3:04:05 AM UTC+2, xingtao zhao wrote:

Here is my proposal for generic in go: https://docs.google.com/document/d/1nO7D15c2B3eq2kF62C0yUs_UgpkyPL2zHhMAmlq1l98/edit?usp=sharing

Many parts has not been finished, and just initial thoughts. In the proposal, I want to keep back compatibility. And I try to add the orthogonal feature only and keep the language still simple enough. 

Please add your comments on it. Hope it is useful and could inspire some new features in go 2.0

Thanks!

[Mandolyte]

On Saturday, July 2, 2016 at 9:12:54 AM UTC-4, Chad wrote:

The appeal of generics is probably a false appeal.

Then, if you accept the trilemma described at http://research.swtch.com/generic, that puts you in favor of "slow programmers"... just kidding. I went back to read all the comments from that blog post and found that it could have been written yesterday. Not much has changed since 2009. One commenter Rivorus is very eloquent, favoring generics and points convincingly to the Boost Graph Library as why they are necessary. Others not so much. Pretty much like every thread on this topic when it comes up.

But I think the key is that Go's target of server side development rarely needs generics (think of Docker, Kubernetics, web server, etc.). However, just last April, Ian Lance Taylor stated forcefully "Go should support some form of generic programming. Generic programming enables the representation of algorithms and data structures in a generic form, with concrete elements of the code (such as types) factored out. It means the ability to express algorithms with minimal assumptions about data structures, and vice-versa." at https://github.com/golang/proposal/blob/master/design/15292-generics.md. 

This leads me to conclude that there are whole areas of software development that Go could impact significantly if it introduced generics. I think someone already pointed this out earlier in the thread, that this area is one of Libraries, Frameworks. This is an area of some controversy in the Go community. See, for instance, Doug Cheney's blog post at http://dave.cheney.net/2014/10/26/go-frameworks-and-ludditry.

But I'm with Ian on this point. Go needs it, but I'm content to wait for it to be done well.

[Dave Cheney]

Lol, Doug Cheney.

[Chad]

Hehe, perhaps. But I am not sure that it makes people much slower if that assertion is even true.

The thing being that, what is more important for an application algorithm? The data or the datastructure ?

I would tend to think that the data is more important. The choice of datastructure is often about computation speed.

For most application side algorithms/protocols etc, we already have most of the building blocks we need.

[Henry]

Doug Cheney is the generic version of Dave Cheney. ;)