Add generics

[cosmos72]

This is a complex and challenging task.

The idea is to use gomacro as a playground to experiment with Go language extensions, since in many cases it's much easier to add new features to gomacro than to one of the Go compilers.

Generics in Go are a very discussed proposal, and many programmers would like to have them, but their complexity and the miriad of possible variations don't offer a clear solution. Implementing an official but suboptimal solution with warts and issues means that everybody will be stuck with them for a long time due to the need to preserve language compatibility.

Gomacro offers an escape hatch: it's an unofficial Go interpreter, and gives no guarantees analogous to the Go compatibity promise. It merely does a best-effort attempt to implement Go language, and already contains several extensions to it. In the author's opinion, it's a very good environment where to experiment further language extensions.

Combine it with gomacro author's love-hate relationship with C++ templates (love for the power, hate for the syntax) and his dislike for protracted programming discussions with no code to show for them, and you can imagine the outcome.

This issue exists to track progress of the generics implementation in gomacro. Feel free to comment.

[cosmos72]

Implementation started, see branch generics-v1. It currently contains a forked go/parser to recognize the new syntax and a forked go/printer to pretty-print it.

The journey, difficulties, solutions and implementation choices are documented in https://github.com/cosmos72/gomacro/blob/generics-v1/doc/generics.md

[cosmos72]

To avoid spamming the official Go issue on generics beyond the initial announcement, it's probably better to move here the gomacro-specific discussion, including the following technical information posted there:

@mandolyte wrote:

---

@cosmos72 There is a summary of proposals at the link below. Is your blend one of them? https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX4pi-HnNjkMEgyAHX4N4

---

my reply:

---

I have read that document, it summarizes many different approaches to generics by various programming languages.

At the moment I am going toward the "Type specialization" technique used by C++, Rust and others, possibly with a little of "Parameterized template scopes" because Go most general syntax for new types is type ( Foo ...; Bar ...) and I am extending it to template[T1,T2...] type ( Foo ...; Bar ...). Also, I am keeping the door open for "Constrained specialization".

I would like to also implement the "Polymorphic function specialization", i.e. to arrange for the specialization to be automatically inferred by the language at the call site if not specified by the programmer, but I guess it may be somewhat complex to implement. We will see.

The blend I was referring to is between https://github.com/golang/proposal/blob/master/design/15292/2013-10-gen.md and https://github.com/golang/proposal/blob/master/design/15292/2013-12-type-params.md

[cosmos72]

First template functions compiled and executed successfully. See commit c3eb625437cd1a8bea329bbe18e38059b19d9f71

[cosmos72]

Template types added in commit 2aa4c4890e6042e3974cc5d2a95e7f8bf3b0c4f6

Composite literals whose type is a template, as Pair#[int,string] { 7, "foo" }, implemented in commit 60e64e65b3d65a4f411a3edc676f857e9613ade7

[alvaroloes]

@cosmos72 I know it is not official and that you are just doing that to investigate about generics, but it is very motivating seeing something real. Thanks for your work!

[cosmos72]

Thanks for the appreciation :)

I am doing this exactly to have "something real", and not-so-secretly hoping that the experience gained in the process can help moving the stalled situation.

[cosmos72]

Added partial specialization and full specialization of templates.

This makes gomacro templates Turing-complete, although with a syntax even more unreadable than C++ template metaprogramming. See the tests 'turing_completetemplate*' in all_test.go#L1179 for an example of fibonacci numbers computed at compile-time with gomacro templates.

Clearly, if templates are the only mechanism to perform arbitrary (i.e. Turing-complete) computation at compile-time in Go, they will be used for such purpose, despite their syntax (ouch).

In my opinion, the solution is not reducing their power and expressiveness and remove Turing-completeness, but rather introducing a regular Go syntax to execute Go functions at compile-time - provided they satisfy certain restrictions, see for example the proposal https://github.com/golang/proposal/blob/master/design/15292/2016-09-compile-time-functions.md where it talks about "pure functions"

For a more in-depth analysis, see doc/generics.md#turing-completeness

[tooolbox]

@cosmos72 Definitely appreciate the work you're doing on this.

I certainly don't claim to be any kind of expert in this area, with no experience with C++, templates, metaprogramming, or advanced macros. Actually, some of the explanations in your generics doc are very enlightening!

With that said, and with the admission that I haven't yet grokked every paragraph of generics.md, I have a couple of questions:

1. What, in a nutshell, would you say the limitations would be in keeping templates from being Turing-complete?
2. How would the template system interact with interfaces in Go? Could it? Are there any kinds of benefits that could be had by combining the two concepts?
3. Have you given any thought to a syntax for Turing-complete templates which is Go-like? I rather liked your use of const at the end there; any more examples along that line, or any other concepts?

While the lack of generics in Go sometimes forces things to be refreshingly simple, other times it's brutal. It's also maybe worth thinking about the specific use cases where this is really warranted.

[cosmos72]

Thanks for the appreciation :) Here are my (tentative) answers:

1. if you don't want Turing-complete templates, I think the only viable solution is to remove support for partial and full specialization - they are equivalent to if. Clearly, if an alternative implementation of compile-time if is found, for example by some to-be-found clever (ab)use of Go types, Turing-completeness may re-emerge.

   For completeness, I am against this: in my opinion, partial and full template specializations are extremely useful features and worth adding, even after weighting the complexity introduced by them.

   If you're not used to C++ templates, explaining why partial and full template specializations are useful is a bit complicated. The simplest explanation I can give is: they are compile-time equivalent of if, and they allow declaring special cases, or sets of special cases, for templates.

2. Gomacro already supports template interfaces :) And yes, they are useful. Consider for example something like

   template[T] type Sortable interface {
   Less(T) bool
   }

   or

   template[T] type Iterator interface {
   Get() T
   Prev() bool
   Next() bool
   }

   which cannot be conveniently expressed by Go 1.x - one has to resort to interface{} or to more convoluted interfaces in order to avoid indicating T

3. Go-like syntax for Turing-complete templates: I thought a little about it, and there are even too many solutions. One may for example implement template constants, as:

   template[N] const Fibonacci = Fibonacci#[N-1] + Fibonacci#[N-2]
   template[] for[2] const Fibonacci = 1
   template[] for[1] const Fibonacci = 1
   const Fib20 = Fibonacci#[20]

   but they are still not very readable. There is an ongoing discussion on compile-time function execution, see https://github.com/golang/proposal/blob/master/design/15292/2016-09-compile-time-functions.md - among the proposals listed there, the one I prefer is to simply put const before an expression to indicate that it should be executed at compile time. I like it because it allows to write the code only once (with normal Go syntax), and execute it either at compile-time or run-time. Example:

   func Fibonacci(N int) int {
   if N <= 2 {
   return 1
   }
   return Fibonacci(N-1) + Fibonacci(N-2)
   }
   var Fib20 = const Fibonacci(20) // evaluate at compile time
   var Fib21 = Fibonacci(21) // evaluate at run time (at program start)

   Another option is to implement Lisp-like macros (Gomacro already has them, though not documented yet), which are basically functions with the additional mark "execute me at compile time".

[komuw]

@cosmos72 Hello, what are your thoughts on the Go2 generics draft: https://go.googlesource.com/proposal/+/master/design/go2draft-contracts.md ?

I would be interested to read what you think, assuming you have published your thoughts somewhere.

[cosmos72]

I read it quickly, and I would need a more thorough study to comment.

It will probably take a while, because I am currently preparing my presentation for Golab 2018 conference

[cosmos72]

Update: I read more in detail https://go.googlesource.com/proposal/+/master/design/go2draft-contracts.md and here are my comments:

• the generic idea (pun intended) makes sense. In a way, it is a "minimal" proposal since it omits partial and full template specialization - it stays away from Turing completeness.
• I do not like the syntax. The proposed syntax to declare generics type Vector(type Element) []Element and to use them var v Vector(int) is almost identical to how functions and closures are declared and called. I am afraid it will be very difficult to visually distinguish a generic from a function, both for programmers and for the parser. I'd like a prominent marker with an ASCII character not yet used by Go, for example: type Vector#(type Element) []Element and var v Vector#(int) or even better, replace #() with either #[] or #<>
• contracts are too clever. I agree with https://utcc.utoronto.ca/~cks/space/blog/programming/Go2ContractsTooClever - Chris explained the problem much more clearly than I could.

[cosmos72]

An alternative implementation, named "generics v2" is in progress.

It follows more closely https://github.com/golang/proposal/blob/master/design/15292/2013-12-type-params.md and does not have partial or full specializations - thus avoiding Turing completeness at compile time.

I am currently adding contracts to it - a much lighter version than https://go.googlesource.com/proposal/+/master/design/go2draft-contracts.md. In my "generics v2" contracts are just interfaces, with the small extension that receiver type can also be specified, if one wants. I also reused the syntax Foo#[A,B] from "generics v1" to specify generic parameters.

Example:

type Eq#[T] interface {
  func (T) Equal(T) bool
}

As you can see, Eq#[T] is an interface for types that can be compared with themselves: the receiver and (only) argument of method Equal both have type T. Go 1.x interfaces cannot express such relation, because they cannot mention the receiver. One could attempt to write

type Eq2 interface {
  Equal(Eq2) bool
}

but it has a different meaning: if a type T implements Eq2, then it can be compared - by calling its method Equal - with any other type than also implements Eq2, not just with itself. That's not what programmers usually want.

Contracts can be added to template types and functions with the following syntax:

func Uniq#[T: Eq](slice []T) []T {
   // ...
}

The Uniq function is expected to remove duplicates from its slice argument. It can be used only with types T that satisfy the contract Eq i.e. implement the interface Eq#[T] i.e. which have a method func (T) Equal(T) bool

[cosmos72]

The alternative implementation of generics "v2" - now named "contracts are interfaces", or CTI in brief, is now enabled by default. See https://github.com/cosmos72/gomacro#generics and https://github.com/cosmos72/gomacro/blob/master/doc/generics-cti.md for details

[cosmos72]

Update: generics have been approved in Go. Gomacro should be updated to support them

[elamre]

Did you ever continue to look into this issue? Would be nice to have

[cosmos72]

Well, it's now a matter of revamping the experimental implementation already present in gomacro, modify the experimental syntax to conform to official Go generics, and implement the missing parts of the semantics.

I even have an idea on how to import at runtime third-party packages that expose generics in their public API - it's a hack, but it should work in most cases.

Currently, the only missing thing is my time and dedication (should I say inspiration?): it's going to be quite a difficult task...

[kaarrot]

+1 for having official generics in gomacro. I've seen some packages errored on import in go macro due to dependency on generics. I imagine this list will keep growing. Is there anything to help moving this forward? Thanks.