> perhaps they can read the literature of the past 30yrs
40, nearing on 45:
> Milner, R., Morris, L., Newey, M. "A Logic for Computable Functions with reflexive and polymorphic types", Proc. Conference on Proving and Improving Programs, Arc-et-Senans (1975)
The basic tradeoff is monomorphization (code duplication) vs. boxing (in Go speak, interface{}). The problem with saying "well, this is a tradeoff and both sides have downsides, so we won't do anything" is that the tradeoff still exists—it's just something that manually has to be done by the programmer instead of something that the compiler can do. In Go, the monomorphization approach is done with code duplication (either manually or with go generate), while the boxing approach is done with interface{}. Adding generics to the language just automates one or both of the approaches.
The idea that the monomorphization/boxing tradeoff can be dodged by not having generics in the language is a fallacy. In Go, today, you as a programmer already have to decide which side of the tradeoff you want every time you write something that could be generic. It's just that the compiler doesn't help you at all.
> The basic tradeoff is monomorphization (code duplication) vs. boxing (in Go speak, interface{}).
And even that is not the whole story, just because you reify generics does not mean you have to monomorphise everything, Microsoft's C# compiler only monomorphises value types.
Does that mean writing a separate version of an algorithm for each type or types that you want it to handle? Like a sort for ints, a sort for floats, etc., even if the logic is otherwise the same (or almost)?
Not a PL design or theory expert, just interested.
In Haskell (and I believe Scala), one can use pragma hints to specify to the compiler when to specialise, if performance becomes a problem. So I don't see this as an argument against parametric polymorphism.
> The basic tradeoff is monomorphization (code duplication) vs. boxing (in Go speak, interface{}).
There is also the approach taken by Swift, where values of generic type are unboxed in memory, and reified type metadata is passed out of band. There's no mandatory monomorphization.
Really by "boxing" I mean "dictionary passing" (I've also seen the term "intensional type analysis" for it). That encompasses approaches like Java as well as those of Swift.
Hybrid approaches in which the compiler (or JIT!) decides whether to monomorphize or use vtables are also possible.
"Dictionary passing" is a good term for this implementation strategy, I haven't heard it named before. Do you know of any other languages that take a similar approach?
Sure, but it still does basically the same thing of passing around witness tables. Values happen to have a uniform representation, but this seems seems like variation within a cluster of languages that do similar thing rather than something fundamentally new.
The Swift approach shares many of the same characteristics and trade-offs as "true" (aka Java-style) boxing. Of course, it does avoid some downsides of that, but also brings along some additional ones.
I think the main difference is that the Swift approach ends up being more memory-efficient, eg consider Swift's Array<Int> is stored as an array of integer values compared to a Java's ArrayList<Integer> where each element is boxed.
Also the Swift optimizer can clone and specialize generic functions within a module, eliminating the overhead of indirection through reified metadata.
Yes, there's some pitfalls of Java that Swift avoids, like compulsory allocation, but it fundamentally has the same style of indirection (often pointers to stack memory rather than heap, but still pointers), type erasure and pervasive virtual calls, and brings with it even more virtual calls due to needing to go through the value witness table to touch any value (which might be optimised out... or might not, especally with widespread resilience).
The compiler specializing/monomorphizing as an optimisation shows that Swift has a hybrid approach that tries to balance the trade-offs of both (like many other languages, like Haskell, and, with explicit programmer direction, Rust), but the two schemes still fall into the broad categories of monomorphizing vs dictionary passing, not something fundamentally different.
As usual, it lacks discussion about generics in:
Eiffel
Ada
Modula-3
D
MLton
.NET
Rust
Haskell
OCaml
Sather
BETA
CLU
Oh wait, they're pointing out that none of these is even remotely being discussed in the article hinting that they did not, in fact, and much prefer taking down strawmen they built from some sort of daguerreotypes of Java and C++.
> They just weren't ready to make any of the significant tradeoffs other languages have to do in order to support them.
Ah yes, the ever so convenient but never actually clarified "tradeoffs", which only ever happen for generics but oddly enough apparently don't happen for any other feature.
> there's definitely a lot of research in that area.
That there is, would be nice if Go's designers ever bothered actually using it.
Nitpick, but the idea is even older, going back at least to Girard (1971) and Reynolds (1974). :)
I don't know exactly what the problem is for Go. There are tradeoffs, e.g., just with the type system: impredicative, stratified or predicative quantification, implicit subtyping or explicit type instantiation, value restrictions, variance handling for mutable inductive types, Hindley-Milner or bidirectional typechecking, etc. There are more tradeoffs with the implementation. Fortunately, these are all well understood by now.
However, it is also true that many mainstream languages famously got generics wrong. What's most infurating about this situation is that a lot of research just gets ignored. If the question is really "should Go have generics whose design is based on C++ templates and/or Java generics" then the only sane answer is a resounding no.
40, nearing on 45:
> Milner, R., Morris, L., Newey, M. "A Logic for Computable Functions with reflexive and polymorphic types", Proc. Conference on Proving and Improving Programs, Arc-et-Senans (1975)