proposal: Go 2: mini-package: a solution to unify Go builtin and custom generics

[dotaheor]

https://github.com/dotaheor/unify-Go-builtin-and-custom-generics/blob/master/README.md

The proposal introduces a gen code element concept which is much like our familiar func element concept, which makes the proposal very easy to understand.

[rsc]

For what it's worth, I don't understand exactly what the proposal means, nor how to implement it.

[ianlancetaylor]

I don't understand how to write the Min function using this approach: the function that takes two values of any ordered type and returns the smaller value.

[dotaheor]

@rsc This proposal is very rough. There must be many flaws and logic problems in it. Hope it will inspire someone to get a better Go generic design idea.

Basically, this proposal tries to decouple the generic parameter declaration part and the function/type implementation parts, so that main generic body code still keeps looking as Go 1 style and a better readability is got. (I really don't like the cumbersome feeling in the syntax designs of C++/Java/Rust, especially their generic designs.)

I don't have an idea on how to implement it too (if even if you neither, ;D). Maybe it can be implemented in a 3rd-party code generation tool, but I think the experience will be smoother when implementing it as a builtin feature.

@ianlancetaylor The Min generic function can be simply written as

// A gen also acts as a contract at the same time.
gen Min[T type] func {
	export func(x, y T) T {
		if x < y {
			return x
		} else {
			return y
		}
	}
}

Use it:

var n = Min[int32](11, 9)             // n == 9, type of n is int32
var t = Min[string]("hello", "world") // t == "hello", type of t is string
var b = Min[bool](true, false)        // compilation error

// Or, we can bind the generic export to some func declarations.
func MinInt32 = Min[int32]
func MinString = Min[string]
var n1 = MinInt32(11, 9)
var t1 = MinString("hello", "world")

// The code will be simpler by making use of type deduction.
var n2 = Min(11, int32(9))
var t2 = Min("hello", "world")

[fbnz156]

@dotaheor Have you considered looking at code generation for this? See this: https://github.com/ncw/gotemplate

[dotaheor]

@Fabian-F Your project is cool, but it looks it only works well for some data struct use cases. A general generic solution will support more variations.

I ever had a similar idea by using type alias in a package as generic inputs. I planed to use .gg as generic Go file extensions and write a generator program scan all the *.gg files to translate to them as *.go files. But I didn't find a design with a smooth experience, so I gave up it.

[fbnz156]

@dotaheor it's not actually my project.

I actually typed something similar to what you're describing but decided not to suggest it. Generics as you describe them would be too dramatic of a change for Go, and amounts to simple templating.

[dotaheor]

This proposal is really some like C++ template. I don't want to defend C++ template design, but I think C++ template design is not all bad. In fact, many C++ template uses are very readable. The problem of C++ templates is just that it enables people write strange-looking and hard-to-read (and hard-to-debug) code.

This proposal has a distinct characteristic from C++ template design: the exported function/type declaration code parts never entangle with any new added generic element parts. This effectively protects the readability of Go 1 code.

I admit this proposal is some dramatically to change Go, but I think the fact that the newly introduced gen code element concept is much like our familiar func element concept makes the proposal easy to understand.

[fbnz156]

@dotaheor At the end of the day this proposal is still just code templating, which would be much better achieved with a pre-processor (//go:generate) than by modifying the compiler and language spec to effectively achieve the same thing.

I would love generics as much as anyone but there's been no decent suggestions on how to achieve them without complicating Go significantly. This gen keyword proposal is no different.

Perhaps a sensible suggestion would be for an all purpose code preprocessor, which would allow for domain-specific syntax to be added and reduce endless arguing over language changes. This would allow you to create templating using your syntax, generate and substitute typenames.

[dotaheor]

@Fabian-F This proposal is just an idea. It is far to be practicable to be implemented as a formal Go syntax set yet. It is presented here is mainly for inspiration purpose.

Personally, I just think this proposal idea is interesting and is easy to understand. It can be viewed as an attempt to standardize all kinds of code generators, in the familiar function declaration and call manner, to solve some common problems in Go for lacking of custom generics.

[ianlancetaylor]

There are a lot of different ideas here, and I think they need more explanation. How many new keywords does this add? What does on absent do? What is a "builtin generic privilege"? What does it mean for a gen to return an import? How do operator generics work--which operators are permitted? What happens if the arguments to a generic operator have different types? Why the builtin contract comparable? Are there any other builtin contracts?

In the generics design draft contracts serve two purposes: they describe acceptable type arguments and they define permitted operations. It's not really clear whether they serve the same roles in this proposal.

[dotaheor]

There should be two new keywords for sure: gen and export. The on absent is just for description convenience purpose. There should be better alternative ways to do the same job.

For "builtin generic privilege", I mean this current proposal doesn't unify builtin generics and custom generics perfectly. Builtin generics still have some privileges which custom generics can't get.

Please note that this proposal just tries to make the docs of builtin generics look consistent with custom generics. The current builtin generics implementation needn't to be changed.

What does it mean for a gen to return an import?

We can view this as a sub/mini-package is exported as an import, so the result can be assigned to an import identifier, then we can use the import identifier as qualified prefix like the current non-generic imports. When a gen exports hybrid element kinds, such as functions and types, this is a recommended alternative way to let the gen export one result instead.

How do operator generics work--which operators are permitted? What happens if the arguments to a generic operator have different types?

Generally, the types of the arguments should not be different, which is indicated by the example operator gen (the gen itself also acts as a contract).

Maybe the optional inputs and operator generics features mentioned in the proposal are not good ideas.

Why the builtin contract comparable? Are there any other builtin contracts?

I think sometimes named contracts have better readabilities. I tried to list potential useful builtin contracts here: https://gist.github.com/dotaheor/a746923b46d2514ceef49cb47958fd71 (please ignore the assure keyword used there)

In the generics design draft contracts serve two purposes: they describe acceptable type arguments and they define permitted operations. It's not really clear whether they serve the same roles in this proposal.

Yes, this proposal tries to serve the same roles. The difference from the draft is it combines the contract and generic function/type definition syntax in draft as one gen block.

[dotaheor]

@ianlancetaylor In fact, the export keyword is also not very essential. We can comply with the current Go conventions. If a gen only exports one type or func element, then there can only be exactly one type or function which is declared as exported (first letter is upper case) in the gen body. If a gen exports an import, then there can be multiple elements declared as exported.

[dotaheor]

I forgot mentioning that the design in the last comment requires each gen has at most one output. So types and functions hybrid outputs will be prohibited.

BTW, I rewrote the examples in this CL (https://go-review.googlesource.com/c/go/+/187317) with the styles of the proposal in this issue.

Some small changes are added to simplify some simple single output gens.

[dotaheor]

I added a rule in the end of the proposal to make the unification complete reluctantly.

[ianlancetaylor]

I realized that I still don't understand the Min function. How does the Min function know that the type argument supports the < operator? How do we avoid the problem we see in C++ of cascading errors when some invalid type is used?

[dotaheor]

The contracts are created implicitly for the Min example. Yes, this may slow down compiler.

BTW, this proposal doesn't exclude explicit contracts. In fact it also works well with explicit contracts, but the syntax would be some different. In this proposal, Contracts are also defined as gens. For example, if there is a builtin comparable contract (or gen), then the Min generic can be defined with

gen Min[T type] func {
	comparable[T] // This is different to the official draft.
	              // In the draft, the contract appears in
	              // generic function or type prototypes.
	
	// We can continue to apply other contracts here if needed.
	// ...

	export func(x, y T) T {
		if x < y {
			return x
		} else {
			return y
		}
	}
}

(Please note that the newest version of this proposal has discard the export keyword.)

Using the contracts as the way described in the draft is also possible for this proposal, though in my honest opinion, sometimes the relationship between generic types might be very complex so that creating a single contract to describe the relationship is not always flexible.

[dotaheor]

In fact, the Min generic can also be used as a contract in other gen declarations. For example:

gen Max[T type] func {
	Min[T] // The outputs are discarded.

	export func(x, y T) T {
		if x > y {
			return x
		} else {
			return y
		}
	}
}

[ianlancetaylor]

Implicitly created contracts are not contracts. The point of a contract is that it is an explicit declaration of what kinds of type arguments are permitted, and it is an explicit restriction on what kinds of operations are permitted for type parameters. If the contract is implicit, then it depends on the exact body of the function. A small change in the body of the function can implicitly change the contract, causing code far away that calls the function to fail to compile. It's OK for that kind of failure to occur due to an explicit contract change, in which case it's clear that something might fail. It's not OK for it to occur implicitly. See the discussion at https://go.googlesource.com/proposal/+/master/design/go2draft-contracts.md#type-contracts.

[dotaheor]

I see. But sometimes, it is too tedious to define explicit contracts.

[ianlancetaylor]

From my perspective that is like saying that sometimes it is too tedious to define the types of your function arguments and results. There are dynamically typed languages, and there are good reasons for them to exist. But Go is a statically typed language.

[dotaheor]

I think implicitly created ones can also be called contracts. The difference is they are more casual than the ones defined explicitly.

Explicit contracts (or function prototypes) play a pivot role, or a fixed point, to constraint both downstreams (generic or function callers) and the upstream (the definition body). On the other hand, implicit contracts, which are extracted from the definition body, only constraint downstreams.

The advantages of implicit casual contracts are flexible and almost possibility complete. One drawback of implicit casual contracts is that they are often less constrained than intended. The other drawback is the one @ianlancetaylor has mentioned above: the implicit contracts not very formal so that they can be modified casually and easily.

The advantages of explicit formal contracts are great API stability and more user/caller friendly. One disadvantage of explicit contracts (at least for the current draft version) is possibility limited. Another disadvantage is a new set of syntax is needed and sometimes it is tedious to define a contract if the relations between generic types are complex.

I would prefer explicit contracts if the mentioned disadvantages are gone.

[dotaheor]

I just improved my old contract description syntax to get a better readability. The new syntax is here.

The syntax set is not small, but maybe this is inevitable. Readability is more important than simplicity.

[alvaroloes]

The first time I read this proposal I didn't understand it very well and seemed pretty complicated.

After reading the proposal again (the current revision) and understanding it properly, I think it is brilliant! The way the built-in types and user-defined generic types are unified is shockingly elegant.

I have to confess that I haven't dug too deeply into the details, but this way of writing generics is pretty novel and seems to go in the right direction to achieve orthogonality and uniformity in the type system.

It still requires further simplification and refinement, but I'd say this proposal deserves attention.

Thanks for the work!

[ianlancetaylor]

Perhaps I misunderstand, but it seems to me that this new proposal is completely different from the old one. It should probably be in a new issue.

One of the ways that I judge a generics proposal is by the number of new names that it introduces. Currently Go has relatively few names compared to many other programming languages: 25 keywords and 39 predeclared names. One of the most important goals for Go is that it be simple, and a relatively small number of names is one way to judge whether that is succeeding. This new proposal seems to introduce a large number of new names, and in my opinion that is a mark against it.

You say "readability is more important than simplicity." I don't agree. While both are important, simplicity is more important, and moreover simplicity implies readability.

[dotaheor]

The new experimental explicit contract syntax set design is a potential part of this whole generic design. And yes, it can be separated out as a solo contract design proposal. I will do this after several days by improving it more.

The whole design (the gen declaration and the contract part) only introduces two keywords: gen and assure. No built-in names are introduced in the gen declaration design, and currently only one essential built-in contract name, implements, is introduced in the contract syntax design (if type/const properties are not viewed as names). All other constraints may be expressed with built-in contract expressions containing only type/const properties and operators. So I think although the syntax set is not small, it is still simple and intuitive.

[dotaheor]

Indeed. However, the fact that these property names are defined well in Go specification lowers the learning cost.

I also can't make sure whether or not the overall effect by introducing these names is positive or not. I just think the new design is almost possibility complete as implicit contracts, and it makes the definitions of some constraints less ambiguous than implicit contracts.

[ianlancetaylor]

Thanks for the proposal. We're going to continue with our current design draft for generics, which is significantly different from this approach. If that design draft fails, perhaps we can revisit your ideas. You are of course welcome to try implementing this and see how it goes. It is not something that we are going to pursue.

Therefore, this proposal is a likely decline. Leaving open for four weeks for final comments.

-- for @golang/proposal-review

[dotaheor]

OK. Is it ok for me to post (create a new issue for) the contract design part some days later?

[dotaheor]

BTW, the intention of I posted the idea set here and some elsewhere was expecting to get feedback to improve it. Up to now, some surprisingly, no much effective feedback is got, except thinking it is too different.

@bradfitz, @griesemer, @iant, It would be great you can post some different opinions (other than thinking the idea set is too different) here. I will address them to make some adjustments.

[ianlancetaylor]

I feel like I've written quite a few comments on this proposal. Try writing out some real examples, like the ones in the generics design draft, and see how they look. Try working out an implementation strategy. If you genuinely think that your approach is clearly better than the one in the generics design draft--not just different, but clearly better--then show some examples on golang-dev and ask people which they prefer.

[dotaheor]

If you genuinely think that your approach is clearly better than the one in the generics design draft--not just different, but clearly better

No, this is certainly never what I intended to express. I think this is surely a misunderstanding. I do think there are several good points in this proposal, otherwise I would not post it here. But it is hard to say it is clearly better.

The proposal project has some examples: https://github.com/dotaheor/unify-Go-builtin-and-custom-generics/tree/master/examples. Just please note that the new contract design hasn't been used in those examples (I will modify the examples to include the new contract design in several days).

What I forgot mentioning in my previous comments is, I have not any experiences to implement a syntax parser. So I very expected anybody who have such experiences to tell me if this proposal is possible to be implemented. Is there any problems and difficulties in implementing this proposal? In particular some fatal problems make the implementation impossible. This will save much time for who have interests in implementing it.

BTW, if anyone else have interests in implementing this proposal. Just feel free to do it. It is very appreciated if someone can make this proposal a reality or verify that it has fatal problems to do so.

[griesemer]

I have experimented using [ and ] (as you are using here) in the ongoing prototype implementation of the current contract draft; unfortunately they lead to ambiguities that are not easily resolved, at least within the design of the contract proposal.

For instance, when parsing x[T] it's unclear if this is a type x instantiated with type T or whether it is an index expression. We only know at type-checking time what we have. This is not a problem per se. But if we have a type instantiation, the [T] is a (type) parameter list. We expect all parameter lists to behave similar, syntactically, as that "orthogonality" is what makes Go easy to learn and use: "all parameter lists behave the same" so to speak. One of the properties of parameter lists is that they can have a trailing comma, as in min(1,2,) (so the the arguments can be consistently written over multiple lines if so desired). We would expect the same to be the case for a type parameter list. That is, it should be possible to write something like Graph[Node, Edge,], or Tree[Elem,]. But since we can't know whether this is a type instantiation (trailing comma allowed), or an index expression (no trailing comma allowed) at parse time, we either end up with less consistent grammar, have to allow a trailing comma in index expressions (ugly), or, worse, have to report syntax errors during type checking. It can be done, but it's gross.

This is just a simple example of some of the syntactic problems that might arise. It takes time to find them and often requires implementing the parser (or use a parser generator that can detect such problems). So, it is a bit much to ask somebody else to find such problems in your proposal - it pretty much requires somebody to try to implement this. It is hard to just see those problems, and even harder if there is not even a syntax spec.

This is just a tiny example of some of the difficulties that arise with a language change as large as a generics proposal. There are many many more, and many are much harder to resolve.

If you feel like there are significant advantages in your design over the current contracts draft, perhaps you can show those advantages using small examples side by side. That might make it easier to see the good points of this proposal that one might want to consider. Thanks.

[dotaheor]

@griesemer Thanks for the derailed explanations. This is by bar the most well-judged comment.

I really hope these explanations can be posted earlier, at least along with making the proposal review decision.

From your explanations, I can get the following reasons why this proposal is likely declined.

• Generic parameters list with [] make some difficulties for syntax parser.
• Some other more hard to predict difficulties for syntax parser.

About whether not a trailing comma should be allowed in a generic parameter/argument list, I think the answer is this should be consistent with the [8] in [8]byte and [string] in map[string]int. Currently, [8,] and [string,] are both not allowed, so to keep consistency, trailing commas should not be allowed in generic parameter/argument list. For generic parameter lists, this is not a problem, because the last token in a generic parameter list is always a keyword like type and const etc. But for a generic argument list, this might be a small problem if the list is long, for which case, line breaks should not happen after the last token in the generic argument list. However, I think this problem is not very severe. (To avoid this problem, it might be a good idea to limit lengths of generic parameter lists to zero or one and always use gen closures to implement the current generic parameter lists which composes of multiple generic parameters.)

I understand that here the fact that map is a keyword and there is a need to judge whether or not the identifier before a [8]byte is a value or a gen name makes things some different. This really makes some difficulties for the syntax parser. However, as what has been mentioned in the official draft, this is not an obstacle which is impossible to overcome. It needs some code flow order adjustments in the parse and compiler. Whatever, this is really a disadvantage of this proposal. (edit: the gain of making built-in and custom generics consistent is larger.)

I would discuss more if there are other predictable difficulties are found in this proposal. I think it is not a good idea for decline proposal with many ideas just for a single problem or difficulty. I understand your concerns, but I think keeping this issue open (neither declined nor accepted) is better. In fact, I didn't very intend to create this issue a formal proposal. I hope it can show some ideas for inspiration purpose.

In fact, I have maintained this proposal for about three years, improving it from time to time. I really hope Go can own a clean distinct generic system.

BTW, this proposal doesn't exist as a contract proposal. It corresponds to the generic function and type declarations part in the draft. It is just a try to decouple the generic parameter lists from general function and type declarations to remove the cumbersome feeling and to avoid some unnecessary code duplication.

The new explicit contract design mentioned above corresponds to the contract declaration part in draft. Currently, any contract may be presented with a set of constraint expressions, so there is even not the [] problem in it. I think the draft version 1 and version 2 go into two different extreme directions. There are both advantages and disadvantages in them. One is almost possibility complete but will cause some ambiguities sometimes, the other is very formal and readable but is possibility limited. I just want to show a new design combining both the advantages of the two.

I will create a new proposal for the new explicit contract design without the gen declaration part, also for inspiration purpose.

[ianlancetaylor]

I want to make clear that the proposal was marked as "likely decline" for the reasons stated in #32895 (comment), not because of syntactic details with square brackets.

I understand your concerns, but I think keeping this issue open (neither declined nor accepted) is better. In fact, I didn't very intend to create this issue a formal proposal. I hope it can show some ideas for inspiration purpose.

We use the issue tracker as a list of things that the project needs to do. It does not help us to keep an issue open indefinitely with no way to move it forward. You can pursue this project and show ideas and provide inspiration without having an issue in the issue tracker.

[dotaheor]

From my experience, putting all kinds of idea related discussions in one place is good for a community, doing this will unite popularity. And for an individual, this will save much time.

[ianlancetaylor]

For discussions about generics, we already have https://github.com/golang/go/wiki/Go2GenericsFeedback.

[griesemer]

@dotaheor I second @ianlancetaylor comments above.

I brought up the (small) problems using [ ] simply to illustrate how difficult it often is to tease out problems of a design by simply reading a description of it, even if one has experience in the field. We (or somebody else) can't possibly do that work for you in general, but that is what you were effectively asking for when you wrote: "So I very expected anybody who have such experiences to tell me if this proposal is possible to be implemented. Is there any problems and difficulties in implementing this proposal?"

In some cases, people will jump in and help out with the investigation, but that is usually the case when the proposal is compelling enough that people decide to spend that time.

[dotaheor]

For discussions about generics, we already have https://github.com/golang/go/wiki/Go2GenericsFeedback.

There is almost not any discussions. How many people will check that page from time to time?

@griesemer
Ian's comment on why explicit contracts is needed and you last comment are the only two effective inputs since this proposal is posted. But unfortunately, the likely-decline decision is made at the same time (or before) the two comments are posted. No proposals are perfect at the beginning. A proposal needs inputs from others to be adjusted constantly. I haven't made the adjustments yet, then you made the likely-decline decision, which makes it looks you made the decision firstly then found a reason to defend the decision. This might not be truth, but it really gave me the feeling.

[griesemer]

@dotaheor I appreciate your frustration. The fact that nobody else has provided substantial feedback may indicate a lack of interest for this proposal, or a lack of time and resources to engage with it. For us it is not compelling enough to engage with it in more detail than we already have - we can't possibly help you figure out all the fine points; we simply don't have the time for that. We have to take all this at face value and conclude that the proposal is not compelling enough at this point.

If you feel strongly about your proposal, it would be great if you could show us how it is solving problems better than our current contracts proposal, ideally with small examples that shows the differences side by side. That is also what @ianlancetaylor suggested earlier. Thanks.

[dotaheor]

The examples are here: https://github.com/dotaheor/unify-Go-builtin-and-custom-generics/tree/master/examples, I have mentioned them several times.
They are the corresponding examples to the ones in draft 2.

[dotaheor]

Just be aware that the contracts used the examples have not been changed to the new design yet.

[dotaheor]

I updated both the contract and gen declaration design:

• https://github.com/dotaheor/unify-Go-builtin-and-custom-generics/blob/master/contracts.md
• https://github.com/dotaheor/unify-Go-builtin-and-custom-generics/blob/master/README.md

All examples are also updated.

[ianlancetaylor]

I haven't made the adjustments yet, then you made the likely-decline decision, which makes it looks you made the decision firstly then found a reason to defend the decision.

Again, please read what we wrote in #32895 (comment) . The reasons given there have nothing to do with any adjustments to the proposal.

[ianlancetaylor]

@griesemer said "it would be great if you could show us how it is solving problems better than our current contracts proposal, ideally with small examples that shows the differences side by side. That is also what @ianlancetaylor suggested earlier."

You've shown us the examples, but that is the less important part of what he asked for. Show us how this proposal solves problems better than the current design draft. And ideally do it here rather than pointing us to lengthy separate documents.

I also want to echo one of @griesemer 's points: we have limited time and resources. From my point of view we've put a lot of time into examining and commenting on this proposal. As the author of the proposal it is your job to persuade people that your approach is a good idea. It is not our job to help you improve your proposal. We already have a design draft that we've put years of work into. If you want to convince us to put a lot of time into your proposal, you need to show us why it is better.

[dotaheor]

Show us how this proposal solves problems better than the current design draft.

Hi, @ianlancetaylor, I think I have listed the good points in the document. The most obvious good point is the proposal makes the looking of custom generic and built-in generic consistent.

Another also obvious good points of this proposal is it removes the cumbersome feeling of generic function and type declarations.

The good points are listed at the beginning of the document. I re-list them here for convenience:

1. supports const generic parameters (the draft only supports types now).
2. consistent looking of builtin and custom generics.
3. the main part of the declaration syntax of generic types and functions is totally Go 1 compatible.
4. uses generics is much like calling functions, so it is easy to understand.
5. avoid the cumbersome feeling of generic function and type declarations.

[dotaheor]

Show us how this proposal solves problems better than the current design draft. And ideally do it here rather than pointing us to lengthy separate documents.

Do you mean I need to post some examples here?

[ianlancetaylor]

Thanks. What do you mean by "makes the looking of custom generic and built-in generic consistent"?

I'm not sure I agree about the "cumbersome feeling." It seems like where the design draft uses type parameters you use a new keyword and a new notion of mini-packages. I don't see why either approach is less cumbersome.

[dotaheor]

OK, maybe I misunderstood something.

Anyway, this might the last comment I made in this thread.
I will not work this proposal any more.
Working on it really affects the progresses of my other tasks.

I just intended to present some ideas here and hope some of them may have a positive impact in Go generic design process. You don't need to review it. I'm sorry if the reviewing have spent you much time.
If would be great if the title of this issue is allowed to be changed to ideas: Go 2: mini-package: a solution to unify Go builtin and custom generic. You can close it, but I just think leaving it open is also not bad.

Here, I just post a (draft-2) example by adopting this proposal for comparison.

// declaration
gen Map[S type][Element type] func {
	assure S.kind == []int.Kind && S.element == Element

	// The only exported element acts as the output of this gen.
	func Map(s S, f func(Element) Element) S {
		r := make(S, len(s))
		for i, v := range s {
			r[i] = f(v)
		}
		return r
	}
}

// use it:

type MySlice []int

func DoubleMySlice(s MySlice) MySlice {
	v := Map(MySlice, int, s, func(e int) int { return 2 * e })
	// or: v := Map[MySlice][int](s, func(e int) int { return 2 * e })
	// Here v has type MySlice, not type []int.
	return v
}

Update: add the implementation part.

[bradfitz]

You can close it, but I just think leaving it open is also not bad.

Closing it doesn't delete any information. We only leave issues open when there's something actionable to do.

For just brainstorming what generics might look like, another forum is probably best.

Per the comment above (#32895 (comment)) saying this is a likely decline, we're going to close this, as it doesn't look like there's been a change in consensus.