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 c3eb625

[cosmos72]

Template types added in commit 2aa4c48

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

[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_complete_template_*' 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.