Quick question about the generics alternatives that have been considered

[atd...@gmail.com]

Hello,

It' has probably been discussed somewhere but I am curious about what might have been the issues when considering an implementation of generics that would parameterized packages?

The rationale being that usually, packages have a non-mutable interface for the user and are the ompilation unit if I'm not mistaken. So why not just relax the interface exposed by a package and allow for package-wide type specialization?

In terms of pure parametric polymorphism, having packages with a mutable interface in terms of types (via mutation of type aliases for instance) would just be the next iteration. It may require a little bit more from the build tool but the type checking would not have to change I think. The constraints on the parameter would stem implicitly from the code within a package in terms of operations used and interfaces being implemented.

I would expect such "parameterized" packages to be rare, non-pervasive if not for the simple fact that most parameterized package would mostly be able to import other generic packages since they would be defined with abstract types. The compiler may still want to insure that the constraints make sense throughout the dependency tree  of generic imports incrementally but I don't think that that would be a huge problem.

I think that it could be something orthogonal to the design of type constraintd, notably type Lists, that are anyway highly desirable imo but more so to constrain interfaces to a finite set of types ( as a way to have union types, enums, sumtypes or whatnot).

[jake...@gmail.com]

If I understand correctly, this question is specifically addressed by the design draft: https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#why-not-put-type-parameters-on-packages

[atd...@gmail.com]

It does mention it but I fail to see the problem specifically. I am curious about anything that would make it a proposal-killer in terms of design for Go.

Also, the distinction I see is that it would not be the same instantiation of the same package as much as the creation of new packages ( the package names should be parameterized too depending on the input)

As such, packages could be cached and reused for the same input parameters.

 

Having different packages for different kinds seems to be a good separation of concerns to me. Quite the opposite from mixing package boundaries with types, I think it's rather the opposite. (the oppsoite being to allow generic functions spreading across package boundaries)  

Besides, that's exactly what would happen if we had to do it by hand as of today or via code-generation. Hence, we get type specialization trivially. 

 

For instance, if we take the List counter-example, I understand that higher kind polymorphism allow to have only one function definition, albeit parameterized, but it's more complex to write (constraints) and it may allow a pervasive use of  generics that may not be conducive to simple go code.

(Namely, the introduction of the functional patterns such as map/transform/reduce. (which is nothing but an abstraction... nice for people who appreciate it but not necessarily as a generic function imo))

The rest of use-cases for generics could be handled with interfaces and/or the introduction of type-lists, enabling union/sumtypes, essentially augmenting the concept of interface types. 

[Axel Wagner]

The proposal-killers are mentioned - it is awkward for different instantiations of the same package to interact and there is no reason to believe generic usecases will delineate neatly into packages. It sounds like you do not agree that those are proposal-killers. And of course, you are welcome to write down your own design and maybe you even see something they didn't see. But you should be prepared that ultimately, in a "agree to disagree" situation, if the Go team feels it is awkward, their opinion will be what tips the scales.

On Wed, Jan 20, 2021 at 7:09 PM atd...@gmail.com <atd...@gmail.com> wrote:

Also, the distinction I see is that it would not be the same instantiation of the same package as much as the creation of new packages ( the package names should be parameterized too depending on the input)

Just to point out the obvious, that this means you still have to make up a syntax for type-parameters and instantiations. So, this is not a simple matter of importing a regular package.

Having different packages for different kinds seems to be a good separation of concerns to me. Quite the opposite from mixing package boundaries with types, I think it's rather the opposite. (the oppsoite being to allow generic functions spreading across package boundaries)  

Generic functions do not spread across package boundaries. Every generic function and every generic type will still live in a single package.

 

it's more complex to write (constraints)

FTR, the way to express constraints is largely independent on whether you constrain types on a per-function/type or per-package level.

For example, you suggested constraints should be derived implicitly based on the operations used in the package. But you can do that with generic functions too. For example, a previous incarnation of the generics design would have allowed you to specify constraints by writing a function body using all operations you need. In particular, you could've used the function body itself as a contract. So if you take that design and just declare that the contract of a generic function is *implicitly* its function body, you'd get your idea of "constraint-less generics", while operating entirely on a per-function level.

That previous incarnation was abandoned though, because it turns out that implicitly deriving constraints from code is just surprisingly complicated, opens up more questions than it answers and - in my opinion at least - just generally a very bad idea. So, I'm not too optimistic about a new proposal, that tries to go back to that approach.

In any case. As I said, my goal isn't really to convince you that your approach won't work - just to explain why I don't think your approach is likely to get accepted.

(Namely, the introduction of the functional patterns such as map/transform/reduce. (which is nothing but an abstraction... nice for people who appreciate it but not necessarily as a generic function imo))

The rest of use-cases for generics could be handled with interfaces and/or the introduction of type-lists, enabling union/sumtypes, essentially augmenting the concept of interface types. 

On Wednesday, January 20, 2021 at 6:21:10 PM UTC+1 jake...@gmail.com wrote:

If I understand correctly, this question is specifically addressed by the design draft: https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#why-not-put-type-parameters-on-packages

On Wednesday, January 20, 2021 at 10:22:19 AM UTC-5 atd...@gmail.com wrote:

Hello,

It' has probably been discussed somewhere but I am curious about what might have been the issues when considering an implementation of generics that would parameterized packages?

The rationale being that usually, packages have a non-mutable interface for the user and are the ompilation unit if I'm not mistaken. So why not just relax the interface exposed by a package and allow for package-wide type specialization?

In terms of pure parametric polymorphism, having packages with a mutable interface in terms of types (via mutation of type aliases for instance) would just be the next iteration. It may require a little bit more from the build tool but the type checking would not have to change I think. The constraints on the parameter would stem implicitly from the code within a package in terms of operations used and interfaces being implemented.

I would expect such "parameterized" packages to be rare, non-pervasive if not for the simple fact that most parameterized package would mostly be able to import other generic packages since they would be defined with abstract types. The compiler may still want to insure that the constraints make sense throughout the dependency tree  of generic imports incrementally but I don't think that that would be a huge problem.

I think that it could be something orthogonal to the design of type constraintd, notably type Lists, that are anyway highly desirable imo but more so to constrain interfaces to a finite set of types ( as a way to have union types, enums, sumtypes or whatnot).

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/7ba98154-ecee-4657-9985-ce21a80c68c2n%40googlegroups.com.

[atd...@gmail.com]

It didn't seem to me like proposal-killers enoguh so much so that they might not have liked some of the design choices they entailed.

The proble with the current running proposal is that it is a generalization fo what the compiler does. It definitely  permits the spread of generic functions across package boundaries since they can be exported. Only that the type inference allows to not have to express the constraints in most cases. This is still a complication.

What I'd like to know is what are the complexities in a package-parametrization. Indeed it would require additional syntax for package import, there would still be a problem with zero-values return. But it could be so much more simple other than that. 

The alternative is doing what the compiler does and dealing with constraint on kinds. Which is a bit more complex.

As far as deriving constraints from code, I think that it's actually completely different at the package level than doing it at a higher granularity ( functions) because a function is not a compilation unit.

It is similar to essentialy replacing a name and building the package.

At the function level, I would presume that  more information about the flow of data would be required.

As a note, I think that with the first iteration of type aliases, people had started experimenting with such parameterization(I think in the image package). Seems a bit more intuitive.

Obviously, the difference is that packages are uniquely identified by their names which is why, the names have to be internally parameterized as well.

I think that dividing the design space for parametricity into simple code parametrization at the package level and type list interfaces on the other hand could be clearer and easier to handle but I'd like to know what are the pain points.

[Axel Wagner]

On Wed, Jan 20, 2021 at 8:42 PM atd...@gmail.com <atd...@gmail.com> wrote:

It didn't seem to me like proposal-killers enoguh so much so that they might not have liked some of the design choices they entailed.

Yes, that's in general what kills proposals.

The proble with the current running proposal is that it is a generalization fo what the compiler does. It definitely  permits the spread of generic functions across package boundaries since they can be exported.

This seems to be a distinction without a difference to me. You can instantiate a parameterized package from other packages as well, so they also "spread out" in that sense.

 

What I'd like to know is what are the complexities in a package-parametrization. Indeed it would require additional syntax for package import, there would still be a problem with zero-values return. But it could be so much more simple other than that.

I don't think it would be simpler. I also don't think it would be significantly more complicated. There are two ways, I think, packages would differ:

1. You'd need to spend more effort on syntax to describe constraints and parameters and instantiations

2. You'd need to make sure that the compiler treats different instantiations as different packages and stores and looks them up in the right place.

There might be corner cases about cyclic imports, but these, I think, are probably analogous to cyclic references in generic functions/types.

The alternative is doing what the compiler does and dealing with constraint on kinds. Which is a bit more complex.

As I said - the language for expressing constraints is completely orthogonal to whether you constrain the types on packages, or functions.

 

As far as deriving constraints from code, I think that it's actually completely different at the package level than doing it at a higher granularity ( functions) because a function is not a compilation unit.

It is similar to essentialy replacing a name and building the package.

At the function level, I would presume that  more information about the flow of data would be required.

I don't really think so. In any case, that is implementation complexity at worst - it is not reflected in complexity for the user. So I don't think it changes anything to how the community would feel about the introduced complexity.

As a note, I think that with the first iteration of type aliases, people had started experimenting with such parameterization(I think in the image package). Seems a bit more intuitive.

Obviously, the difference is that packages are uniquely identified by their names which is why, the names have to be internally parameterized as well.

Not just internally. They have to be parameterized externally as well. A package would want to be able to use two different generic list instantiations in the same function, so the identifier by which they refer to the instantiated package needs to be different for the different instantiations.

I think that dividing the design space for parametricity into simple code parametrization at the package level and type list interfaces on the other hand could be clearer and easier to handle but I'd like to know what are the pain points.

To repeat: You know the pain points. You just don't think they are that painful. Which is fine.

 

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/913e84ad-1ab7-4a9a-aa5a-656d846cc203n%40googlegroups.com.

[Arnaud Delobelle]

Hello

FWIW I had a go at imagining a way to make a variant of your idea
(package-level parametrisation) work. At the time my principal worry
was contracts and I was keen to use interfaces instead to express
parametric constraints:
https://arnodel.github.io/marooned/go/generics/2020/06/06/go-spec2.html

I posted it on golang-nuts a while ago. Here is a link to Ian Lance
Taylor's reply on this list pointing out some shortcomings:
https://groups.google.com/g/golang-nuts/c/Plq8DkScDW8/m/ig5NuDpXBgAJ

Although I don't think my proposal was very good, I also think it was
an attempt to limit the power of generics in the language. I have a
feeling that in order to avoid abuse of generic code you need to make
it less easy to reach, especially less easy to write generic code
(using it should be easy I think!). Restricting to package-level
parametricity means that there is an obvious trade-off in writing
generic code: you have to make a package for it.

Cheers,

Arnaud

> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/913e84ad-1ab7-4a9a-aa5a-656d846cc203n%40googlegroups.com.

[Axel Wagner]

FWIW, personally, I believe if you make it painful to write generics, what will happen is that people will write generic code and complain about how painful it is. I don't think the outcome will be that people will use it less. If someone thinks they need generics and wants to use them, they will.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAJ6cK1Yb%3DkdvXFuubWCW_iRvDckt8PZEhP42fmj97uT-3u4fMA%40mail.gmail.com.

[Ian Lance Taylor]

On Wed, Jan 20, 2021 at 11:42 AM atd...@gmail.com <atd...@gmail.com> wrote:
>
>
> It didn't seem to me like proposal-killers enoguh so much so that they might not have liked some of the design choices they entailed.
>
> The proble with the current running proposal is that it is a generalization fo what the compiler does. It definitely permits the spread of generic functions across package boundaries since they can be exported. Only that the type inference allows to not have to express the constraints in most cases. This is still a complication.
>
> What I'd like to know is what are the complexities in a package-parametrization. Indeed it would require additional syntax for package import, there would still be a problem with zero-values return. But it could be so much more simple other than that.
>
> The alternative is doing what the compiler does and dealing with constraint on kinds. Which is a bit more complex.
>
> As far as deriving constraints from code, I think that it's actually completely different at the package level than doing it at a higher granularity ( functions) because a function is not a compilation unit.
> It is similar to essentialy replacing a name and building the package.
> At the function level, I would presume that more information about the flow of data would be required.
>
> As a note, I think that with the first iteration of type aliases, people had started experimenting with such parameterization(I think in the image package). Seems a bit more intuitive.
> Obviously, the difference is that packages are uniquely identified by their names which is why, the names have to be internally parameterized as well.
>
> I think that dividing the design space for parametricity into simple code parametrization at the package level and type list interfaces on the other hand could be clearer and easier to handle but I'd like to know what are the pain points.

I think Axel has expressed the pain points pretty well.

You've got a List package that lets you manage linked lists of some
type. So you write

import listint "list[int]"

and then you can write lst := listint.New(); lst.Push(1). Or
something like that.

Now you want a list of lists of int. How do you write that?

import listint "list[int]"
import listlistint "list[listint.List]"

?

That is not how imports work in Go. Now import has changed from
"import a package" to "instantiate an imported package". Those are
pretty different operations.

Also look at https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#list-transform
and think about how to implement that using generic packages.

More generally, there just isn't any clear reason to believe that
generic types and functions naturally map to package boundaries. It's
easy to think up cases where I would want an unexported generic
function. If only packages can be generic, then I have to create a
new internal package just to represent that function. That seems
tedious.

You have asked a couple of times for "proposal-killers". I'm not sure
that there are proposal-killers for attaching generics to packages. I
think it could probably be made to work. In 2017 Robert Griesemer and
I spent about six months working up a generic proposal based on
packages. But in the end we stopped pursuing that approach, because
there were too many difficulties and awkwardnesses.

Ian

[atd...@gmail.com]

I have been asking because the List of List example seemed a bit contrieved to me. I have seen maps of linked lists or slice of slices for math stuff but rarely lists of lists.(probably because of the time complexity)

But yes, composing the parametrization is probably not something that should be possible. Would have to have  package List[int] fully created beforehand via code generation. No recursive instantiation.

I think I understand the worry more clearly. Paramaeterized packages make the definition of Higher Kinded operations more difficult. The Transform function which operates on Lists would be one example.

This could also be a feature to have some things more difficult to do. I have no idea on this, I think it would require data on the kind of code that is needed the most in the wild.

Not sure that the most powerful generics facilities are required. I think that the current set of constraints of what is expressible via current Go code is also why it is successful. Namely the small set of identifiable, common idioms.

If Higher Kinded type of functions are easily created, one could fear that there wiould be more code styles within the Go ecosystem.

But anyway, it needs data across codebases to see what is required. (I know that scientific code, ML code will be wildly different for instance)

But yes, I guess would tend to agree with Arnaud.

Thanks for the answers! :)

[Axel Wagner]

Personally, I feel that "let's reduce utility while keeping complexity constant" is a questionable approach, if you feel that generics don't provide enough value to justify their complexity. I feel that *if* we introduce generics, we should make sure they actually pay for their cost. I'd much rather have no generics at all, than a bad and useless implementation of them.

--

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/92868a82-63f0-48a2-bc40-e3ce5e06a111n%40googlegroups.com.

[atd...@gmail.com]

It's not about bad or useless, the same way Go is not useless because of its current set of constraints.

It's about implementing which you can derive the most value of(also in terms of simplicity, code-sharing etc.)

Meta-programming is all-encompassing but it's problematic. Give someone a hammer and everything looks like nails.

[Ian Lance Taylor]

On Wed, Jan 20, 2021 at 1:19 PM atd...@gmail.com <atd...@gmail.com> wrote:
>
> I have been asking because the List of List example seemed a bit contrieved to me. I have seen maps of linked lists or slice of slices for math stuff but rarely lists of lists.(probably because of the time complexity)

We will have to disagree on that. A list of lists of int is no more
contrived than a type like [][]byte, which is a type that appears at
least 50 times in the Go standard library.

Ian

[atd...@gmail.com]

Oh, I know it does, as mentioned above. Typically to emulate matrices.

My point was that it is still different from a linked list of linked lists.If not time complexity, data locality etc. May be useful for some type of very large graph datastructures, I wouldn,'t know since I haven't encountered this use case yet.

If many other people have felt the need for list of lists then I would be enlightened.

Also, just pointing out that having higher-order functions easily created at compile time for generic code is nice but we also have interfaces which could alleviate part of the issue.

In the end, I am sure you have more data points than I have, my questions have been mostly answered, I'll leave the rest in your care.

Cheers,

[Axel Wagner]

FTR, the same argument that applies to `List(List(int))` also applies to `Set(Set(int))` and `Map(Key1, Map(Key2, Val))`, neither of which suffers from algorithmic complexity issues and both of which I have used in the past in real code.

--

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/d51f545b-59af-41dd-bf38-b4a7afe65714n%40googlegroups.com.

[atd...@gmail.com]

I know but in the case of map, it's a built-in. We have easily higher order functions for that that can be defined.

Where there is a problem is defining higher order functions for generic user-defined containers... I think that it is going a bit too far in the parametrization. It may happen and be somewhat useful, but I don't think that the design should be optimized for it unless pervasive.

I leave the Set datastructure out because the implementations may vary too much and I do not have any data points on this. But the question is, are people more likely to use maps of sets or sets of sets...?

[Jesper Louis Andersen]

On Wed, Jan 20, 2021 at 4:22 PM atd...@gmail.com <atd...@gmail.com> wrote:

It' has probably been discussed somewhere but I am curious about what might have been the issues when considering an implementation of generics that would parameterized packages?

You can take a look at Standard ML / Ocaml "functors" if you want to see an exploration of what it entails as a consequence. It's a completely different approach, and often you'd find you need to improve the module/package system of the language in order to make it feel fluid for a programmer. For Go, it would require quite some language extension before it would be viable (or rather, that is my hunch). One particular important point is that you tend to end up with a "stratification" of sorts. The module system becomes a language of its own, on top of a core language and they don't mix. The stratification isn't required though, as shown by Andreas Rossberg in his 1ML paper. In Go terms, you remove structs, and a struct is a package containing a "var" section. Now, parameterization of packages becomes parametrization of interfaces/structs as a result. What Rossberg shows is that you can create a language out of this idea, and said language "works" insofar it's possible to give it a sensible semantics.

Note: for this to work, you really want packages to be nestable inside packages. And you also want to decouple packages entirely from the file system, by which time you have a language entirely different from Go.

[atd...@gmail.com]

Looking briefly, seems interesting but slightly different. It seems that the intent described in the paper is to endorse full blown functions as a replacement to import statements.

It is useful insofar that it could rationalize the use of build constraints in Go. But it is too expressive in that it may obscure which packages are actually imported amongst other things.

For instance, it allows to branch and decide on different implementations for hashmaps depending on a size parameter. This is a bit different from what I had in mind as I think that generic packages should be encapsulated and 

would simply expose a simple interface to some of their internal state (mostlly allowing to replace type names).

The consequences would be a bit different Ibelieve.

That is another example where I think, too much power is granted to the programmer, in the sake of generalization. Now, the evaluation of import constraints may slow down the build of large programs arbitrarily,

and, as you mentioned, it requires package to be virtualized (because their definition/instantiation is not static anymore) which I don't think is desirable.

The advantage of doing things a bit more simply is that we could decide to save parameterized packages to files via code generation if required. The constraints are static.

(I really appreciate everyday that Go is not "over-engineered")

[atd...@gmail.com]

Just coming back to this quickly, although it is unlikely to change anything at this stage, but, re. a transform function, instead of using parametric polymorphism, I think it is possible to do it with interface arguments and to a greater extent, type lists interface arguments if we have access to these in the future..

It would require to have the transform function in its own package. I don't expect it to be a big problem as I do not think that a transform function require full-parametricity: to transofrm a list of U elements into anoter list of V elements,

I would tend to think that U and V need to be known in advance. A purely generic transformation seems a bit of a red herring to me.

So, not so sure that it would be a counter argument to package parametrization.

However, the only example I may conceive to be a bit annoying is providing a "seemingly" single generic Max function, If for instance, we want the math package to be a regular package that also expose a few generic functions.

I would tend to think that this is where it would be difficult to bind the type of the argument with the type of the return value with only type lists.

With a package parametrization, we would have to introduce a math/generic package and have something like:

 import  (

     mint math/generic [type T= int]

     mfloat math/generic [type T=float]

If we have code that requires Max on ints and floats within a same package, that would make people have to use 2 different max functions, (just like we do these days anyway)

mint.Max(2,3)

mfloat.Max(2.0,3.0)

No opinion on this. I don't think it would bother me but...

Am I missing something?

[atd...@gmail.com]

Forget about it. Does not work. Can't avoid having to constrain types. An algorithm for value types would not be so easily usable with pointer types, at the very least because of nil checks.

And, although it might not be a problem, if we ever have type list interfaces, or even simple multi-parametered packages, there will be a need to split packages into a combination of subpackages based on arities etc.

Otherwise, we could have two func(int) defined by different packages (package List[T= int, U= float] and package List[T=int, U= string]

Probably solvable but anyway...