We describe a design for generics in Go inspired by previous work on Featherweight Java by Igarashi, Pierce, and Wadler. Whereas subtyping in Java is nominal, in Go it is structural, and whereas generics in Java are defined via erasure, in Go we use monomorphisation. Although monomorphisation is widely used, we are one of the first to formalise it. Our design also supports a solution to The Expression Problem.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
> it finally took convincing Philip Wadler (of Haskell and Java generics fame) to help. Without that lucky break [...] Go probably still wouldn't have generics.
Small correction, I think:
My understanding is that while Philip Wadler and his colleagues were very helpful, the core Go team was already well on its way to doing generics before Philip Wadler became involved.
From Wadler's "Featherweight Go" paper [1] (the first draft of which seems to have been uploaded to arxiv.org circa May 2020):
Recently, the Go team mooted a design to extend Go with generics [Taylor and Griesemer 2019], and Rob Pike wrote Wadler to ask: Would you be interested in helping us get…
Read the full comment
polymorphism right [...]
and:
It took us several tries over many months to formalise it correctly.
Well before that, doing generics was one of the main focuses in the GopherCon keynotes/announcements in 2017 and 2018 by Russ Cox [2].
The August 2018 generics design [3][4] was very detailed, and my recollection is most people in the Go community at that point believed the core Go team was going to make generics happen, even if the team and community were still iterating on the exact design.
Of course, that design improved over time, including thanks to Wadler and crew, but I think it would be overstating things to say that probably nothing would have happened without Wadler.
[1] https://arxiv.org/pdf/2005.11710v1
[2] https://go.dev/blog/go2draft
[3] https://go.googlesource.com/proposal/+/master/design/go2draf...
[4] https://go.googlesource.com/proposal/+/master/design/go2draf...
> I'm not interested in what "PL (programming language) people" have to say about it. They dislike all generic/parametric polymorphism implementations except their pet language that no one uses.
That's strange. I seem to recall the PL community invented the generics system for Java [0,1]. Actually, I'm pretty sure Philip Wadler had to show them how to work out contravariance correctly. And topically to this thread, Rob Pike asked for his help again designing the generics system for Go [2,3]. A number of mistakes under consideration were curtailed as a result, detailed in that LWN article.
There are countless other examples, so can you elaborate on what you're talking…
Read the full comment
about? Because essentially all meaningful progress on programming languages (yes, including the ones you use) was achieved, or at least fundamentally enabled, by "PL people".
[0] https://homepages.inf.ed.ac.uk/wadler/gj/
[1] https://homepages.inf.ed.ac.uk/wadler/gj/Documents/gj-oopsla...
[2] https://arxiv.org/pdf/2005.11710
[3] https://lwn.net/Articles/824716/
Are we just ignoring when they invited Philip “Featherweight Java” Wadler to help them design Go generics? https://arxiv.org/abs/2005.11710
Or that Robert Griesemer literally is a language PhD, whose thesis was supervised by a little fellow by the name of “Niklaus Wirth”?
https://www.research-collection.ethz.ch/handle/20.500.11850/...
> Most anything in software can easily end up Turing-complete though.
not really, if you actually pay attention when youre designing the type system:
https://arxiv.org/pdf/2005.11710.pdf
Philip Walder, who contributed to the design of Haskell (according to wikipedia, haven't dug deep here) worked with the Go developers on a PL theory underpinning for Go's generics: https://arxiv.org/abs/2005.11710
So, in fact, industry didn't ignore PL theory and research at all.
> I'm not sure what the difference is with regards to pointers.
In C# most objects are 'class' objects, which are implicitly passed by pointer, although some are 'struct' objects passed by value. In Go rather than making the decision once at the type level, the decision to pass by value or pointer is made explicitly every time an object is used.
> I'm not sure that Go really had anything to figure out or invent
If you look at the discussions for Go (which started as early as 2009 [1]) [2] [3] [4] [5] generics seems as big or a bigger project as the other improvements made to the language over the last decade. My impression is there being a broad spectrum of potential…
Read the full comment
trade-offs across compile speed, execution speed, convenience, etc.
The totality of the prior art here is above my pay grade, but I can quote the Haskell people they roped in [4]:
> We believe we are the first to formalise computation of instance sets and determination of whether they are finite. The bookkeeping required to formalise monomorphisation of instances and methods is not trivial ... While the method for monomorphisation described here is specialised to Go, we expect it to be of wider interest, since similar
issues arise for other languages and compilers such as C++, .Net, MLton, or Rust
I think C# occupies a fairly nice design spot also (and takes advantage of its class/struct system to get fast compiles but also performance when needed). But it's not like the C# design couldn't be improved on. As far as I know you still can't write math code that works across 32 and 64 bit floats. And array covariance is implemented in a way that isn't type-safe and relies on run-time checks and exceptions. [6]
[1] https://research.swtch.com/generic
[2] https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX...
[3] https://go.googlesource.com/proposal/+/master/design/go2draf...
[4] https://arxiv.org/pdf/2005.11710.pdf
[5] https://go.googlesource.com/proposal/+/refs/heads/master/des...
[6] https://codeblog.jonskeet.uk/2013/06/22/array-covariance-not...
> Is it a better bet to move on and go full Rust
If you don't like generics you shouldn't use Rust. You can't escape them in Rust. The designers repeated the mistake of C++ and made it a language feature kitchen sink. It's an unholy mess. You'll find yourself constantly fighting the borrow checker. Type signatures are littered with lifetime annotations. The type system is Turing complete because they didn't analyze it before implementing it. Go's generics were formally validated [1]. Rust's compile time is slow, and the 'async' story is sad. Async functions are colored and infect everything.
[1] https://arxiv.org/pdf/2005.11710.pdf
I'm studying programming language semantics and papers like these are quite valuable in understanding type systems of real languages, see also Featherweight Java[0] and Featherweight Go[1]. At first it looks like a lot to take in, but when you start with far simpler type systems like typed arithmetic expressions and simply-typed lambda calculus, you see the same definitions and metatheorems (properties about the type system) appear over and over again (including in this paper). In particular, the pieces you see repeated are:
- the terms and types of the language
- the values (a subset of terms)
- the evaluation relation, telling you how you go from one term to the next
-…
Read the full comment
the typing relation, telling you how you build well-typed terms and what their types are
- Progress states that if you have a well-typed term, it either is a value or it can take one step of evaluation
- Preservation states you that if you have a well-typed term of type T and it takes a step of evaluation, the resulting term still has type T
And we have the slogan, safety = progress + preservation.
I should also note that past a certain level of complexity of type system, you definitely would want to use a theorem prover such as Coq to formally verify and automate easy cases. The proofs themselves are actually quite boring (which is a good thing!).
[0] https://www.cis.upenn.edu/~bcpierce/papers/fj-toplas.pdf
[1] https://arxiv.org/pdf/2005.11710.pdf
Since type erasure was mentioned, it's worth noting that Philip Wadler (of Haskell fame) was involved both in the design of Java generics [0] and of Go generics [1].
(Perhaps I should clarify that I don't have a strong opinion on type erasure.)
[0] https://homepages.inf.ed.ac.uk/wadler/gj/Documents/gj-oopsla...
[1] https://arxiv.org/abs/2005.11710
My understanding from the “Featherweight Go” paper https://arxiv.org/abs/2005.11710 is that generic types will not simply be a synonym for interface{} because the compiler will be able to monomorphize them - they do not require dynamic dispatch like interfaces.
> And Go people's common refusal to look much further, and especially not into academia..
I don't think that's a fair statement, given Phil Wadler's formal work on generics in Go - "Featherweight Go" (https://arxiv.org/abs/2005.11710) - which is acknowledged here: https://blog.golang.org/generics-next-step
If this follows the monomorphic approach described in Featherweight Go [1][2], they will at least avoid problems caused by type erasure and avoid too much runtime overhead.
1. https://arxiv.org/abs/2005.11710
2. https://news.ycombinator.com/item?id=23368453
> Rob was opposing generics from the start.
That's simply not true.
> he was firmly saying no.
I'm sure you cannot find a single instance where he firmly says no to generics.
He wrote in the FAQ that Go might get generics one day and that they are continuing to think about it.
Here he is arguing in favor of generics: https://www.reddit.com/r/golang/comments/jditu9/what_do_gene...
And he was the one who invited Phil Wadler to help with the generics design. From the Featherweight Go paper: "Rob Pike wrote Wadler to ask: Would you be interested in helping us get polymorphism right (and/or figuring out what “right” means) for some future version of Go?" https://arxiv.org/pdf/2005.11710.pdf
> purely for ideological reasons
There are no ideological reasons.
https://github.com/golang/go/commit/dd64f86e0874804d0ec5b713...
"Generics may well come at some point."
https://golang.org/doc/faq#generics
"A language proposal implementing a form of generic types has been accepted for inclusion in the language. If all goes well it will be available in the Go 1.18 release."
One of the language designers explaining the motivation for adding parametric polymorphism to Go:
https://www.youtube.com/watch?v=RIvL2ONhFBI&t=1064s
Explaining the benefits of generics:
https://www.reddit.com/r/golang/comments/jditu9/what_do_gene...
From the Featherweight Go paper: https://arxiv.org/pdf/2005.11710.pdf
"Recently, the Go team mooted a design to extend Go with generics, and Rob Pike wrote Wadler to ask: Would you be interested in helping us get polymorphism right (and/or figuring out what “right” means) for some future version of Go?"
> My understanding from the “Featherweight Go” paper https://arxiv.org/abs/2005.11710 is that generic types will not simply be a synonym for interface{}
The `any` constraint is a synonym for the `interface{}` constraint.
> It's complicated and there was miscommunication but it forms part of the pattern.
It looks like from that thread that the Go team was never on board with certain technical aspects of how dep was implemented. Obviously there are trade offs so it's hard to determine what answer is "right", but opposing a design for technical reasons is still pretty different than pure "not invented here syndrome".
The dep author in that thread says part of the reason he did not make a proposal was he was worried "what negative community consequences (wasted work/goodwill) a misfire proposal might have." But since dep was becoming a de-facto standard, skipping the proposal process was…
Read the full comment
basically doing an end-run against the technical decisions of the Go team (and others in the community not already aboard the dep train).
I have to admit I'm a bit biased here, I use Go and Go modules, followed closely the discussions at the time, and strongly prefer the trade offs made by the (now official) Go package manager over those made by dep. I can understand how people with different priorities (or who dislike Go in general) might feel differently, but I think it's a bit unfair to call rejecting something over real technical trade offs "not invented here" thinking.
> I'm pretty sure there's been several different proposals for generics
I don't know of any? By formal proposal I think they mean complete specification of how it would work with the existing features, not just the start of an idea, because of course you need that to actually add it to the language.
I think few people expected someone external to the Go team would do it, but I think that's more because it's an enormous amount of work that an expert would have to put in for free. In the end I believe even the Go team ended up asking for help from academic specialists to work out the details. [1]
> The second a core language change actually involves a person external to google or the team drop the concept that that could happen I'll withdraw my criticism
They've made almost no changes to the language so far so obviously the evidence is still out on the former case, but for the latter I believe Russ Cox's check/handle proposal [2] and Robert Griesemer's try proposal [3] (both core team members) were rejected after community feedback.
[1] https://arxiv.org/pdf/2005.11710.pdf
[2] https://go.googlesource.com/proposal/+/master/design/go2draf...
[3] https://go.googlesource.com/proposal/+/master/design/32437-t...
Abstract If future net-zero emissions energy systems rely heavily on solar and wind resources, spatial and temporal mismatches between resource availability and electricity demand may challenge system reliability.