proposal: spec: generic programming facilities
adg opened this issue · 874 comments
This issue proposes that Go should support some form of generic programming.
It has the Go2 label, since for Go1.x the language is more or less done.
Accompanying this issue is a general generics proposal by @ianlancetaylor that includes four specific flawed proposals of generic programming mechanisms for Go.
The intent is not to add generics to Go at this time, but rather to show people what a complete proposal would look like. We hope this will be of help to anyone proposing similar language changes in the future.
CL https://golang.org/cl/22057 mentions this issue.
Let me preemptively remind everybody of our https://golang.org/wiki/NoMeToo policy. The emoji party is above.
There is Summary of Go Generics Discussions, which tries to provide an overview of discussions from different places. It also provides some examples how to solve problems, where you would want to use generics.
There are two "requirements" in the linked proposal that may complicate the implementation and reduce type safety:
- Define generic types based on types that are not known until they are instantiated.
- Do not require an explicit relationship between the definition of a generic type or function and its use. That is, programs should not have to explicitly say type T implements generic G.
These requirements seem to exclude e.g. a system similar to Rust's trait system, where generic types are constrained by trait bounds. Why are these needed?
It becomes tempting to build generics into the standard library at a very low level, as in C++ std::basic_string<char, std::char_traits, std::allocator >. This has its benefits—otherwise nobody would do it—but it has wide-ranging and sometimes surprising effects, as in incomprehensible C++ error messages.
The problem in C++ arises from type checking generated code. There needs to be an additional type check before code generation. The C++ concepts proposal enables this by allowing the author of generic code to specify the requirements of a generic type. That way, compilation can fail type checking before code generation and simple error messages can be printed. The problem with C++ generics (without concepts) is that the generic code is the specification of the generic type. That's what creates the incomprehensible error messages.
Generic code should not be the specification of a generic type.
@tamird It is an essential feature of Go's interface types that you can define a non-interface type T and later define an interface type I such that T implements I. See https://golang.org/doc/faq#implements_interface . It would be inconsistent if Go implemented a form of generics for which a generic type G could only be used with a type T that explicitly said "I can be used to implement G."
I'm not familiar with Rust, but I don't know of any language that requires T to explicitly state that it can be used to implement G. The two requirements you mention do not mean that G can not impose requirements on T, just as I imposes requirements on T. The requirements just mean that G and T can be written independently. That is a highly desirable feature for generics, and I can not imagine abandoning it.
@ianlancetaylor https://doc.rust-lang.org/book/traits.html explains Rust's traits. While I think they're a good model in general, they would be a bad fit for Go as it exists today.
@sbunce I also thought that concepts were the answer, and you can see the idea scattered through the various proposals before the last one. But it is discouraging that concepts were originally planned for what became C++11, and it is now 2016, and they are still controversial and not particularly close to being included in the C++ language.
Would there be value on the academic literature for any guidance on evaluating approaches?
The only paper I've read on the topic is Do developers benefit from generic types? (paywall sorry, you might google your way to a pdf download) which had the following to say
Consequently, a conservative interpretation of the experiment
is that generic types can be considered as a tradeoff
between the positive documentation characteristics and the
negative extensibility characteristics. The exciting part of
the study is that it showed a situation where the use of a
(stronger) static type system had a negative impact on the
development time while at the same time the expected bene-
fit – the reduction of type error fixing time – did not appear.
We think that such tasks could help in future experiments in
identifying the impact of type systems.
I also see #15295 also references Lightweight, flexible object-oriented generics.
If we were going to lean on academia to guide the decision I think it would be better to do an up front literature review, and probably decide early if we would weigh empirical studies differently from ones relying on proofs.
Please see: http://dl.acm.org/citation.cfm?id=2738008 by Barbara Liskov:
The support for generic programming in modern object-oriented programming languages is awkward and lacks desirable expressive power. We introduce an expressive genericity mechanism that adds expressive power and strengthens static checking, while remaining lightweight and simple in common use cases. Like type classes and concepts, the mechanism allows existing types to model type constraints retroactively. For expressive power, we expose models as named constructs that can be defined and selected explicitly to witness constraints; in common uses of genericity, however, types implicitly witness constraints without additional programmer effort.
I think what they did there is pretty cool - I'm sorry if this is the incorrect place to stop but I couldn't find a place to comment in /proposals and I didn't find an appropriate issue here.
It could be interesting to have one or more experimental transpilers - a Go generics source code to Go 1.x.y source code compiler.
I mean - too much talk/arguments-for-my-opinion, and no one is writing source code that try to implement some kind of generics for Go.
Just to get knowledge and experience with Go and generics - to see what works and what doesn't work.
If all Go generics solutions aren't really good, then; No generics for Go.
Can the proposal also include the implications on binary size and memory footprint? I would expect that there will be code duplication for each concrete value type so that compiler optimizations work on them. I hope for a guarantee that there will be no code duplication for concrete pointer types.
I offer a Pugh Decision matrix. My criteria include perspicuity impacts (source complexity, size). I also forced ranked the criteria to determine the weights for the criteria. Your own may vary of course. I used "interfaces" as the default alternative and compared this to "copy/paste" generics, template based generics (I had in mind something like how D language works), and something I called runtime instantiation style generics. I'm sure this is a vast over simplification. Nonetheless, it may spark some ideas on how to evaluate choices... this should be a public link to my Google Sheet, here
Pinging @yizhouzhang and @andrewcmyers so they can voice their opinions about genus like generics in Go. It sounds like it could be a good match :)
The generics design we came up with for Genus has static, modular type checking, does not require predeclaring that types implement some interface, and comes with reasonable performance. I would definitely look at it if you're thinking about generics for Go. It does seem like a good fit from my understanding of Go.
Here is a link to the paper that doesn't require ACM Digital Library access:
http://www.cs.cornell.edu/andru/papers/genus/
The Genus home page is here: http://www.cs.cornell.edu/projects/genus/
We haven't released the compiler publicly yet, but we are planning to do that fairly soon.
Happy to answer any questions people have.
In terms of @mandolyte's decision matrix, Genus scores a 17, tied for #1. I would add some more criteria to score, though. For example, modular type checking is important, as others such as @sbunce observed above, but template-based schemes lack it. The technical report for the Genus paper has a much larger table on page 34, comparing various generics designs.
I just went through the whole Summary of Go Generics document, which was a helpful summary of previous discussions. The generics mechanism in Genus does not, to my mind, suffer from the problems identified for C++, Java, or C#. Genus generics are reified, unlike in Java, so you can find out types at run time. You can also instantiate on primitive types, and you don't get implicit boxing in the places you really don't want it: arrays of T where T is a primitive. The type system is closest to Haskell and Rust -- actually a bit more powerful, but I think also intuitive. Primitive specialization ala C# is not currently supported in Genus but it could be. In most cases, specialization can be determined at link time, so true run-time code generation would not be required.
CL https://golang.org/cl/22163 mentions this issue.
A way to constrain generic types that doesn't require adding new language concepts: https://docs.google.com/document/d/1rX4huWffJ0y1ZjqEpPrDy-kk-m9zWfatgCluGRBQveQ/edit?usp=sharing.
Genus looks really cool and it's clearly an important advancement of the art, but I don't see how it would apply to Go. Does anyone have a sketch of how it would integrate with the Go type system/philosophy?
The issue is the go team is stonewalling attempts. The title clearly states the intentions of the go team. And if that wasn't enough to deter all takers, the features demanded of such a broad domain in the proposals by ian make it clear that if you want generics then they don't want you. It is asinine to even attempt dialog with the go team. To those looking for generics in go, I say fracture the language. Begin a new journey- many will follow. I've already seen some great work done in forks. Organize yourselves, rally around a cause
If anyone wants to try to work up a generics extension to Go based on the Genus design, we are happy to help. We don't know Go well enough to produce a design that harmonizes with the existing language. I think the first step would be a straw-man design proposal with worked-out examples.
@andrewcmyers hoping that @ianlancetaylor will work with you on that. Just having some examples to look at would help a lot.
I've read through the Genus paper. To the extent that I understand it, it seems nice for Java, but doesn't seem like a natural fit for Go.
One key aspect of Go is that when you write a Go program, most of what you write is code. This is different from C++ and Java, where much more of what you write is types. Genus seems to be mostly about types: you write constraints and models, rather than code. Go's type system is very very simple. Genus's type system is far more complex.
The ideas of retroactive modeling, while clearly useful for Java, do not seem to fit Go at all. People already use adapter types to match existing types to interfaces; nothing further should be needed when using generics.
It would be interesting to see these ideas applied to Go, but I'm not optimistic about the result.
I'm not a Go expert, but its type system doesn't seem any simpler than pre-generics Java. The type syntax is a bit lighter-weight in a nice way but the underlying complexity seems about the same.
In Genus, constraints are types but models are code. Models are adapters, but they adapt without adding a layer of actual wrapping. This is very useful when you want to, say, adapt an entire array of objects to a new interface. Retroactive modeling lets you treat the array as an array of objects satisfying the desired interface.
I wouldn't be surprised if it were more complicated than (pre-generics) Java's in a type theoretic sense, even though it's simpler to use in practice.
Relative complexity aside, they're different enough that Genus couldn't map 1:1. No subtyping seems like a big one.
If you're interested:
The briefest summary of the relevant philosophical/design differences I mentioned are contained in the following FAQ entries:
- https://golang.org/doc/faq#implements_interface
- https://golang.org/doc/faq#overloading
- https://golang.org/doc/faq#covariant_types
- https://golang.org/doc/faq#variant_types
Unlike most languages, the Go spec is very short and clear about the relevant properties of the type system start at https://golang.org/ref/spec#Constants and go straight through until the section titled "Blocks" (all of which is less than 11 pages printed).
Unlike Java and C# generics, the Genus generics mechanism is not based on subtyping. On the other hand, it seems to me that Go does have subtyping, but structural subtyping. That is also a good match for the Genus approach, which has a structural flavor rather than relying on predeclared relationships.
I don't believe that Go has structural subtyping.
While two types whose underlying type is identical are therefore identical
can be substituted for one another, https://play.golang.org/p/cT15aQ-PFr
This does not extend to two types who share a common subset of fields,
https://play.golang.org/p/KrC9_BDXuh.
On Thu, Apr 28, 2016 at 1:09 PM, Andrew Myers notifications@github.com
wrote:
Unlike Java and C# generics, the Genus generics mechanism is not based on
subtyping. On the other hand, it seems to me that Go does have subtyping,
but structural subtyping. That is also a good match for the Genus approach,
which has a structural flavor rather than relying on predeclared
relationships.—
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub
#15292 (comment)
Thanks, I was misinterpreting some of the language about when types implement interfaces. Actually, it looks to me as if Go interfaces, with a modest extension, could be used as Genus-style constraints.
That's exactly why I pinged you, genus seems like a much better approach than Java/C# like generics.
There were some ideas with regards to specializing on the interface types; e.g. the package templates approach "proposals" 1 2 are examples of it.
tl;dr; the generic package with interface specialization would look like:
package set
type E interface { Equal(other E) bool }
type Set struct { items []E }
func (s *Set) Add(item E) { ... }
Version 1. with package scoped specialization:
package main
import items set[[E: *Item]]
type Item struct { ... }
func (a *Item) Equal(b *Item) bool { ... }
var xs items.Set
xs.Add(&Item{})
Version 2. the declaration scoped specialization:
package main
import set
type Item struct { ... }
func (a *Item) Equal(b *Item) bool { ... }
var xs set.Set[[E: *Item]]
xs.Add(&Item{})
The package scoped generics will prevent people from significantly abusing the generics system, since the usage is limited to basic algorithms and data-structures. It basically prevents building new language-abstractions and functional-code.
The declaration scoped specialization has more possibilities at the cost making it more prone to abuse and it is more verbose. But, functional code would be possible, e.g:
type E interface{}
func Reduce(zero E, items []E, fn func(a, b E) E) E { ... }
Reduce[[E: int]](0, []int{1,2,3,4}, func(a, b int)int { return a + b } )
// there are probably ways to have some aliases (or similar) to make it less verbose
alias ReduceInt Reduce[[E: int]]
func ReduceInt Reduce[[E: int]]
The interface specialization approach has interesting properties:
- Already existing packages using interfaces would be specializable. e.g. I would be able to call
sort.Sort[[Interface:MyItems]](...)and have the sorting work on the concrete type instead of interface (with potential gains from inlining). - Testing is simplified, I only have to assure that the generic code works with interfaces.
- It's easy to state how it works. i.e. imagine that
[[E: int]]replaces all declarations ofEwithint.
But, there are verbosity issues when working across packages:
type op
import "set"
type E interface{}
func Union(a, b set.Set[[set.E: E]]) set.Set[[set.E: E]] {
result := set.New[[set.E: E]]()
...
}
Of course, the whole thing is simpler to state than to implement. Internally there are probably tons of problems and ways how it could work.
PS, to the grumblers on slow generics progress, I applaud the Go Team for spending more time on issues that have a bigger benefit to the community e.g. compiler/runtime bugs, SSA, GC, http2.
@egonelbre your point that package-level generics will prevent "abuse" is a really important one that I think most people overlook. That plus their relative semantic and syntactic simplicity (only the package and import constructs are affected) make them very attractive for Go.
@andrewcymyers interesting that you think Go interfaces work as Genus-style constraints. I would have thought they still have the problem that you can't express multi-type-parameter constraints with them.
One thing I just realized, however, is that in Go you can write an interface inline. So with the right syntax you could put the interface in scope of all the parameters and capture multi-parameter constraints:
type [V, E] Graph [V interface { Edges() E }, E interface { Endpoints() (V, V) }] ...
I think the bigger problem with interfaces as constraints is that methods are not as pervasive in Go as in Java. Built-in types do not have methods. There is no set of universal methods like those in java.lang.Object. Users don't typically define methods like Equals or HashCode on their types unless they specifically need to, because those methods don't qualify a type for use as map keys, or in any algorithm that needs equality.
(Equality in Go is an interesting story. The language gives your type "==" if it meets certain requirements (see https://golang.org/ref/spec#Logical_operators, search for "comparable"). Any type with "==" can serve as a map key. But if your type doesn't deserve "==", then there is nothing you can write that will make it work as a map key.)
Because methods aren't pervasive, and because there is no easy way to express properties of the built-in types (like what operators they work with), I suggested using code itself as the generic constraint mechanism. See the link in my comment of April 18, above. This proposal has its problems, but one nice feature is that generic numeric code could still use the usual operators, instead of cumbersome method calls.
The other way to go is to add methods to types that lack them. You can do this in the existing language in a much lighter way than in Java:
type Int int
func (i Int) Less(j Int) bool { return i < j }
The Int type "inherits" all the operators and other properties of int. Though you have to cast between the two to use Int and int together, which can be a pain.
Genus models could help here. But they would have to be kept very simple. I think @ianlancetaylor was too narrow in his characterization of Go as writing more code, fewer types. The general principal is that Go abhors complexity. We look at Java and C++ and are determined never to go there. (No offense.)
So one quick idea for a model-like feature would be: have the user write types like Int above, and in generic instantiations allow "int with Int", meaning use type int but treat it like Int. Then there is no overt language construct called model, with its keyword, inheritance semantics, and so on. I don't understand models well enough to know whether this is feasible, but it is more in the spirit of Go.
@jba We certainly agree with the principle of avoiding complexity. "As simple as possible but no simpler." I would probably leave some Genus features out of Go on those grounds, at least at first.
One of the nice things about the Genus approach is that it handles built-in types smoothly. Recall that primitive types in Java don't have methods, and Genus inherits this behavior. Instead, Genus treats primitive types as if they had a fairly large suite of methods for the purpose of satisfying constraints. A hash table requires that its keys can be hashed and compared, but all the primitive types satisfy this constraint. So type instantiations like Map[int, boolean] are perfectly legal with no further fuss. There is no need to distinguish between two flavors of integers (int vs Int) to achieve this. However, if int were not equipped with enough operations for some uses, we would use a model almost exactly like the use of Int above.
Another thing worth mentioning is the idea of "natural models" in Genus. You ordinarily don't have to declare a model to use a generic type: if the type argument satisfies the constraint, a natural model is automatically generated. Our experience is that this is the usual case; declaring explicit, named models is normally not needed. But if a model were needed — for example, if you wanted to hash ints in a nonstandard way — then the syntax is similar to what you suggested: Map[int with fancyHash, boolean]. I would argue that Genus is syntactically light in normal use cases but with power in reserve when needed.
@egonelbre What you're proposing here looks like virtual types, which are supported by Scala. There is an ECOOP'97 paper by Kresten Krab Thorup, "Genericity in Java with virtual types", which explores this direction. We also developed mechanisms for virtual types and virtual classes in our work ("J&: nested intersection for scalable software composition", OOPSLA'06).
Since literal initializations are pervasive in Go, I had to wonder what a function literal would look like. I suspect that the code to handle this largely exists in Go generate, fix, and rename.Maybe it will inspire someone :-)
// the (generic) func type definition
type Sum64 func (X, Y) float64 {
return float64(X) + float64(Y)
}
// instantiate one, positionally
i := 42
var j uint = 86
sum := &Sum64{i, j}
// instantiate one, by named parameter types
sum := &Sum64{ X: int, Y: uint}
// now use it...
result := sum(i, j) // result is 128
Ian's proposal demands too much. We cannot possibly develop all the features at-once, it will exist in an unfinished state for many months.
In the meantime, the unfinished project cannot be called official Go language until done because that will risk fragmenting the ecosystem.
So the question is how to plan this.
Also a huge part of the project would be developing the reference corpus.
developing the actual generic collections, algorithms and other things in such a way we all agree on that they are idiomatic, while using the new go 2.0 features
A possible syntax?
// Module defining generic type
module list(type t)
type node struct {
next *node
data t
}// Module using generic type:
import (
intlist "module/path/to/list" (int)
funclist "module/path/to/list" (func (int) int)
)
l := intlist.New()
l.Insert(5)@md2perpe, syntax is not the hard part of this issue. In fact, it is by far the easiest. Please see the discussion and linked documents above.
@md2perpe We have discussed parametrizing entire packages ("modules") as a way to genericity internally - it does seem to be a way to reduce syntactic overhead. But it has other issues; e.g., it's not clear how one would parametrize it with types that are not package-level. But the idea may still be worth exploring in detail.
I'd like to share a perspective: In a parallel universe all Go function-signatures have always been constrained to mention only interface types, and instead of demand for generics today, there's one for a way to avoid the indirection associated with interface values. Think of how you'd solve that problem (without changing the language). I have some ideas.
@thwd So would the library author continue using interfaces, but without the type switching and type assertions needed today. And would the library user simply pass in concrete types as if the library would use the types as-is... and then would the compiler reconcile the two? And if it couldn't state why? (such as the modulo operator was used in the library, but the user supplied a slice of something.
Am I close? :-)
@mandolyte yes! let's exchange emails as to not pollute this thread. You can reach me at "me at thwd dot me". Anyone else reading this who might be interested; shoot me an email and I'll add you to the thread.
It a great feature for type system and collection library.
A potential syntax:
type Element<T> struct {
prev, next *Element<T>
list *List<T>
value T
}
type List<E> struct {
root Element<E>
len int
}
For interface
type Collection<E> interface {
Size() int
Add(e E) bool
}
super type or type implement:
func contain(l List<parent E>, e E) bool
<V> func (c Collection<child E>)Map(fn func(e E) V) Collection
The above aka in java:
boolean contain(List<? super E>, E e)
<V> Collection Map(Function<? extend E, V> mapFunc);
Just be aware that the cost of interface is unbelievably huge.
@minux I can't say about the performance costs but in relation to code quality. interface{} can't be verified at compile time but generics can. In my opinion this is, in most cases, more important than the performance issues of using interface{}.
There's really no downside to this because the processing required for this doesn't slow the compiler down.
There are (at least) two downsides.
One is increased work for the linker: if the specializations for two types result in the same underlying machine code, we don't want to compile and link two copies of that code.
Another is that parameterized packages are less expressive than parameterized methods. (See the proposals linked from the first comment for detail.)
Is hyper type a good idea?
func getAddFunc (aType type) func(aType, aType) aType {
return func(a, b aType) aType {
return a+b
}
}
Is hyper type a good idea?
What you are describing here is just type parameterization ala C++ (i.e., templates). It doesn't type-check in a modular way because there is no way to know that the type aType has a + operation from the given information. Constrained type parameterization as in CLU, Haskell, Java, Genus is the solution.
@golang101 I have a detailed proposal along those lines. I'll send a CL to add it to the list, but it's unlikely to be adopted.
CL https://golang.org/cl/38731 mentions this issue.
It doesn't type-check in a modular way because there is no way to know that the type
aTypehas a + operation from the given information.
Sure there is. That constraint is implicit in the definition of the function, and constraints of that form can be propagated to all of the (transitive) compile-time callers of getAddFunc.
The constraint isn't part of a Go type — that is, it cannot be encoded in the type system of the run-time portion of the language — but that doesn't mean that it can't be evaluated in a modular fashion.
Added my proposal as 2016-09-compile-time-functions.md.
I do not expect that it will be adopted, but it can at least serve as an interesting reference point.
@bcmills I feel that compile time functions are a powerful idea, apart from any consideration of generics. For example, I wrote a sudoku solver that needs a popcount. To speed that up, I precalculated the popcounts for the various possible values and stored it as Go source. This is something one might do with go:generate. But if there were a compile time function, that lookup table could just as well be calculated at compile time, keeping the machine generated code from having to be committed to the repo. In general, any sort of memoizable mathematical function is a good fit for pre-made lookup tables with compile time functions.
More speculatively, one might also want to, e.g., download a protobuf definition from a canonical source and use that to build types at compile time. But maybe that's too much to be allowed to do at compile time?
I feel like compile time functions are too powerful and too weak at the same time: they are too flexible and can error out in strange ways / slow down compiling the way C++ templates do, but on the other hand they are too static and difficult to adapt to things like first-class functions.
For the second part, I don't see a way you can make something like a "slice of functions that process slices of a particular type and return one element", or in an ad-hoc syntax []func<T>([]T) T, which is very easy to do in essentially every statically typed functional language. What is really needed is values being able to take on parametric types, not some source-code level code generation.
For the second part, I don't see a way you can make something like a "slice of functions that process slices of a particular type and return one element",
If you're talking about a single type parameter, in my proposal that would be written:
const func SliceOfSelectors(T gotype) gotype { return []func([]T)T (type) }If you're talking about mixing type parameters and value parameters, no, my proposal does not allow for that: part of the point of compile-time functions is to be able to operate on unboxed values, and the kind of run-time parametricity I think you're describing pretty much requires boxing of values.
Yup, but in my opinion that kind of thing that requires boxing should be allowed while keeping type-safety, perhaps with special syntax that indicates the "boxedness". A big part of adding "generics" is really to avoid the type-unsafety of interface{} even when the overhead of interface{} is not avoidable. (Perhaps only allow certain parametric type constructs with pointer and interface types that are "already" boxed? Java's Integer etc boxed objects are not completely a bad idea, though slices of value types are tricky)
I just feel like compile-time functions are very C++-like, and would be extremely disappointing for people like me expecting Go2 to have a modern parametric type system grounded in a sound type theory rather than a hack based on manipulating pieces of source code written in a language without generics.
@bcmills
What you propose will not be modular. If module A uses module B, which uses module C, which uses module D, a change to how a type parameter is used in D may need to propagate all the way back to A, even if the implementer of A has no idea that D is in the system. The loose coupling provided by module systems will be weakened, and software will be more brittle. This is one of the problems with C++ templates.
If, on the other hand, type signatures do capture the requirements on type parameters, as in languages like CLU, ML, Haskell, or Genus, a module can be compiled without any access to the internals of modules it depends on.
A big part of adding "generics" is really to avoid the type-unsafety of interface{} even when the overhead of interface{} is not avoidable.
"not avoidable" is relative. Note that the overhead of boxing is point # 3 in Russ's post from 2009 (https://research.swtch.com/generic).
expecting Go2 to have a modern parametric type system grounded in a sound type theory rather than a hack based on manipulating pieces of source code
A good "sound type theory" is descriptive, not prescriptive. My proposal in particular draws from second-order lambda calculus (along the lines of System F), where gotype stands for the kind type and the entire first-order type system is hoisted into the second-order ("compile-time") types.
It's also related to the modal type theory work of Davies, Pfenning, et al at CMU. For some background, I would start with A Modal Analysis of Staged Computation and Modal Types as Staging Specifications for Run-time Code Generation.
It's true that the underlying type theory in my proposal is less formally specified than in the academic literature, but that doesn't mean it isn't there.
If module A uses module B, which uses module C, which uses module D, a change to how a type parameter is used in D may need to propagate all the way back to A, even if the implementwer of A has no idea that D is in the system.
That is already true in Go today: if you look carefully, you'll note that the object files generated by the compiler for a given Go package include information on the portions of the transitive dependencies that affect the exported API.
The loose coupling provided by module systems will be weakened, and software will be more brittle.
I've heard that same argument used to advocate for exporting interface types rather than concrete types in Go APIs, and the reverse turns out to be more common: premature abstraction overconstrains the types and hinders extension of APIs. (For one such example, see #19584.) If you want to rely on this line of argument I think you need to provide some concrete examples.
This is one of the problems with C++ templates.
As I see it, the main problems with C++ templates are (in no particular order):
- Excessive syntactic ambiguity.
a. Ambiguity between type names and value names.
b. Excessively broad support for operator overloading, leading to weakened ability to infer constraints from operator usage. - Over-reliance on overload resolution for metaprogramming (or, equivalently, ad-hoc evolution of metaprogramming support).
a. Especially w.r.t. reference-collapsing rules. - Overly-broad application of the SFINAE principle, leading to very difficult-to-propagate constraints and far too many implicit conditionals in type definitions, leading to very difficult error reporting.
- Overuse of token-pasting and textual inclusion (the C preprocessor) instead of AST substition and higher-order compilation artifacts (which thankfully seems to be at least partly addressed with Modules).
- Lack of good bootstrapping languages for C++ compilers, leading to poor error-reporting in long-lived compiler lineages (e.g. the GCC toolchain).
- The doubling (and sometimes multiplication) of names resulting from mapping sets of operators onto differently-named "concepts" (rather than treating the operators themselves as the fundamental constraints).
I've been coding in C++ off and on for a decade now and I'm happy to discuss the deficiencies of C++ at length, but the fact that program dependencies are transitive has never been remotely near the top of my list of complaints.
On the other hand, needing to update a chain of O(N) dependencies just to add a single method to a type in module A and be able to use it in module D? That's the kind of problem that slows me down on a regular basis. Where parametricity and loose coupling conflict, I'll choose parametricity any day.
Still, I firmly believe that metaprogramming and parametric polymorphism should be separated, and C++'s confusion of them is the root cause of why C++ templates are annoying. Simply put, C++ attempts to implement a type-theory idea using essentially macros on steroids, which is very problematic since programmers like to think of templates as real parametric polymorphism and are hit by unexpected behavior. Compile-time functions are a great idea for metaprogramming and replacing the hack that's go generate, but I don't believe it should be the blessed way of doing generic programming.
"Real" parametric polymorphism helps loose coupling and shouldn't conflict with it. It should also be tightly integrated with the rest of the type system; for example it probably should be integrated into the current interface system, so that many usages of interface types could be rewritten into things like:
func <T io.Reader> ReadAll(in T)
which should avoid interface overhead (like Rust's usage), though in this case it's not very useful.
A better example might be the sort package, where you could have something like
func <T Comparable> Sort(slice []T)
where Comparable is simply a good old interface that types can implement. Sort can then be called on a slice of value types that implement Comparable, without boxing them into interface types.
@bcmills Transitive dependencies unconstrained by the type system are, in my view, at the core of some of your complaints about C++. Transitive dependencies are not so much of a problem if you control modules A, B, C, and D. In general, you are developing module A and may only be weakly aware that module D is down there, and conversely, the developer of D may be unaware of A. If module D now, without making any change to the declarations visible in D, starts using some new operator on a type parameter—or merely uses that type parameter as a type argument to a new module E with its own implicit constraints—those constraints will percolate to all clients, who may not be using type arguments satisfying the constraints. Nothing tells developer D they are blowing it. In effect, you've got a kind of global type inference, with all the difficulties of debugging that that entails.
I believe the approach we took in Genus [PLDI'15] is much better. Type parameters have explicit, but lightweight, constraints (I take your point about supporting operation constraints; CLU showed how to do that right all the way back in 1977). Genus type checking is fully modular. Generic code can either be compiled only once to optimize code space or specialized to particular type arguments for good performance.
If module D now, without making any change to the declarations visible in D, starts using some new operator on a type parameter […] [clients] may not be using type arguments satisfying the constraints. Nothing tells developer D they are blowing it.
Sure, but that's already true for lots of implicit constraints in Go independent of any generic programming mechanism.
For example, a function may receive a parameter of interface type and initially call its methods sequentially. If that function later changes to call those methods concurrently (by spawning additional goroutines), the constraint "must be safe for concurrent use" is not reflected in the type system.
Similarly, the Go type system today does not specify constraints on variable lifetimes: some implementations of io.Writer erroneously assume they can keep a reference to the passed-in slice and read from it later (e.g. by doing the actual write asynchronously in a background goroutine), but that causes data races if the caller of Write attempts to reuse the same backing slice for a subsequent Write.
Or a function using a type-switch might take a different path of a method is added to one of the types in the switch.
Or a function checking for a particular error code might break if the function generating the error changes the way it reports that condition. (For example, see #19647.)
Or a function checking for a particular error type might break if wrappers around the error are added or removed (as happened in the standard net package in Go 1.5).
Or the buffering on a channel exposed in an API may change, introducing deadlocks and/or races.
...and so on.
Go is not unusual in this regard: implicit constraints are ubiquitous in real-world programs.
If you try to capture all of the relevant constraints in explicit annotations, then you end up going in one of two directions.
In one direction, you build a complex, extremely comprehensive system of dependent types and annotations, and the annotations end up recapitulating a substantial portion of the code they annotate. As I hope you can clearly see, that direction is not at all in keeping with the design of the rest of the Go language: Go favors specification simplicity and code conciseness over comprehensive static typing.
In the other direction, the explicit annotations would cover only a subset of the relevant constraints for a given API. Now the annotations provide a false sense of security: the code can still break due to changes in implicit constraints, but the presence of explicit constraints misleads the developer into thinking that any "type-safe" change also maintains compatibility.
It's not obvious to me why that kind of API stability needs to be accomplished through explicit source code annotation: the sort of API stability you're describing can also be achieved (with less redundancy in the code) through source code analysis. For example, you could imagine having the api tool analyze the code and output a much richer set of constraints than can be expressed in the formal type system of the language, and giving the guru tool the ability to query the computed set of constraints for any given API function, method, or parameter.
@bcmills Aren't you making the perfect the enemy of the good? Yes, there are implicit constraints that are hard to capture in a type system. (And good modular design avoids introducing such implicit constraints when feasible.) It would be great to have an all-encompassing analysis that can statically check all the properties you want checked -- and provide clear, non-misleading explanations to programmers about where they are making mistakes. Even with the recent progress on automatic error diagnosis and localization, I'm not holding my breath. For one thing, analysis tools can only analyze the code you give them. Developers do not always have access to all the code that might link with theirs.
So where there are constraints that are easy to capture in a type system, why not give programmers the ability to write them down? We have 40 years of experience programming with statically constrained type parameters. This is a simple, intuitive static annotation that pays off.
Once you start building larger software that layers software modules, you start wanting to write comments explaining such implicit constraints anyway. Assuming there is a good, checkable way to express them, why not then let the compiler in on the joke so it can help you?
I note that some of your examples of other implicit constraints involve error handling. I think our lightweight static checking of exceptions [PLDI 2016] would address these examples.
So where there are constraints that are easy to capture in a type system, why not give programmers the ability to write them down?
[…]
Once you start building larger software that layers software modules, you start wanting to write comments explaining such implicit constraints anyway. Assuming there is a good, checkable way to express them, why not then let the compiler in on the joke so it can help you?
I actually agree completely with this point, and I often use a similar argument in regards to memory management. (If you're going to have to document invariants on aliasing and retention of data anyway, why not enforce those invariants at compile-time?)
But I would take that argument one step further: the converse also holds! If you don't need to write a comment for a constraint (because it is obvious in context to the humans who work with the code), why should you need to write that comment for the compiler? Regardless of my personal preferences, Go's use of garbage-collection and zero-values clearly indicate a bias toward "not requiring programmers to state obvious invariants". It may be the case that Genus-style modeling can express many of the constraints that would be expressed in comments, but how does it fare in terms of eliding the constraints that would also be elided in comments?
It seems to me that Genus-style models are more than just comments anyway: they actually change the semantics of the code in some cases, they don't just constrain it. Now we would have two different mechanisms — interfaces and type-models — for parameterizing behaviors. That would represent a major shift in the Go language: we have discovered some best practices for interfaces over time (such as "define interfaces on the consumer side") and it's not obvious that that experience would translate to such a radically different system, even neglecting Go 1 compatibility.
Furthermore, one of the excellent properties of Go is that its specification can be read (and largely understood) in an afternoon. It isn't obvious to me that a Genus-style system of constraints could be added to the Go language without complicating it substantially — I would be curious to see a concrete proposal for changes to the spec.
Here's an interesting data point for "metaprogramming". It would be nice for certain types in the sync and atomic packages — namely, atomic.Value and sync.Map — to support CompareAndSwap methods, but those only work for types that happen to be comparable. The rest of the atomic.Value and sync.Map APIs remain useful without those methods, so for that use-case we either need something like SFINAE (or other kinds of conditionally-defined APIs) or have to fall back to a more complex hierarchy of types.
I want to drop this creative syntax idea of using aboriginal syllabics.
@bcmills Can you explain more about these three points?
- Ambiguity between type names and value names.
- Excessively broad support for operator overloading
3.Over-reliance on overload resolution for metaprogramming
@mahdix Sure.
- Ambiguity between type names and value names.
This article gives a good introduction. In order to parse a C++ program, you must know which names are types and which are values. When you parse a templated C++ program, you do not have that information available for members of the template parameters.
A similar issue arises in Go for composite literals, but the ambiguity is between values and field names rather than values and types. In this Go code:
const a = someValue
x := T{a: b}is a a literal field name, or is it the constant a being used as a map key or array index?
- Excessively broad support for operator overloading
Argument-dependent lookup is a good place to start. Overloads of operators in C++ can occur as methods on the receiver type or as free functions in any of several namespaces, and the rules for resolving those overloads are quite complex.
There are many ways to avoid that complexity, but the simplest (as Go currently does) is to disallow operator overloading entirely.
- Over-reliance on overload resolution for metaprogramming
The <type_traits> library is a good place to start. Check out the implementation in your friendly neighborhood libc++ to see how overload resolution comes into play.
If Go ever supports metaprogramming (and even that is very doubtful), I would not expect it to involve overload resolution as the fundamental operation for guarding conditional definitions.
@bcmills
As I've never used C++, could you shed some light as to where operator overloading via implementing predefined 'interfaces' stands in terms of complexity. Python and Kotlin are examples of this.
I think that ADL itself is a huge problem with C++ templates that went mostly unmentioned, because they force the compiler to delay resolution of all the names until instantiation time, and can result in very subtle bugs, in part because the "ideal" and "lazy" compilers behave differently here and the standard permits it. The fact that it supports operator overloading is not really the worst part of it by far.
This proposal is based on Templates, a system for macro expansion would not be enough? I'm not talking about go generate or projects like gotemplate. I'm talking about more like this:
macro MacroFoo(stmt ast.Statement) {
....
}Macro could reduce the boilerplate and the use of reflection.
I think that C++ is a good enough example that generics shouldn't be based on templates or macros. Especially considering Go has stuff like anonymous functions that really can't be "instantiated" at compile-time except as an optimization.
@samadadi you can get your point across without saying "what is wrong with you people". Having said that, the argument of complexity has been brought up multiple times already.
Go is not the first language to try to achieve simplicity by omitting support for parametric polymorphism (generics), despite that feature becoming increasingly important over the past 40 years -- in my experience, it's a staple of second-semester programming courses.
The trouble with not having the feature in the language is that programmers end up resorting to workarounds that are even worse. For example, Go programmers often write code templates that are macro-expanded to produce the "real" code for various desired types. But the real programming language is the one you type, not the one the compiler sees. So this strategy effectively means you are using a (no longer standard) language that has all the brittleness and code bloat of C++ templates.
As noted on https://blog.golang.org/toward-go2 we need to provide "experience reports", so that need and design goals can be determined. Could you take a few minutes and document the macro cases you have observed?
Please keep this bug on topic and civil. And again, https://golang.org/wiki/NoMeToo. Please only comment if you have unique and constructive information to add.
@mandolyte It's very easy to find detailed explanations on the web advocating code generation as a (partial) substitute for generics:
https://appliedgo.net/generics/
https://www.calhoun.io/using-code-generation-to-survive-without-generics-in-go/
http://blog.ralch.com/tutorial/golang-code-generation-and-generics/
Clearly there are a lot of people out there taking this approach.
@andrewcmyers , there are some limitations as well as convenience caveats when using code generation BUT .
Generally - if you believe this approach is best/good enough, I think the effort to allow somewhat similar generation from within the go tool chain would be a bless.
- Compiler optimization may be a challenge in this case, but runtime will be consistent, AND code maintenance, user experience (simplicity...) , standard best practices and unified code standards may be kept .
Moreover - all the tool chain will be kept the same, apart from debugging tools (profilers , step debuggers etc) that will see lines of code that were not written by the developer, but that's a little like stepping into ASM code while debugging - only its a readable code :) .
Downside - no precedent (that I know of) to this approach inside the go tool chain .
To sum it up - consider code generation as part of the build process , it shouldnt be too complicated, quite safe, runtime optimized, can keep simplicity and very small change in the language .
IMHO : Its a compromise easily achieved, with a low price .
To be clear, I don't consider macro-style code generation, whether done with gen, cpp, gofmt -r, or other macro/template tools, to be a good solution to the generics problem even if standardized. It has the same problems as C++ templates: code bloat, lack of modular type checking, and difficulty debugging. It gets worse as you start, as is natural, building generic code in terms of other generic code. To my mind, the advantages are limited: it would keep life relatively simple for the Go compiler writers and it does produce efficient code — unless there is instruction cache pressure, a frequent situation in modern software!
No doubt code generation is not a REAL solution even if wrapped up with some in language support to make the look and feel as a "part of the language"
My point was it was VERY cost effective.
Btw, if you look at some of the code generation substitutes, you can easily see how they could have been much more readable, faster, and lack some wrong concepts (e.g. iteration over arrays of pointers vs values) had the language given them better tools for this.
And perhaps that's a better path to resolve for in short term, that would not feel like a patch:
before thinking of the "best generics support that will also be idiomatic to go " (I believe some implementations above would take years to accomplish full integration) , implement some sets of "in language" supported functions that are needed anyhow (like a build in structures deep copy) would make these code generating solution much more usable.
After reading through the generics proposals by @bcmills and @ianlancetaylor, I've made the following observations:
Compile-time Functions and First Class Types
I like the idea of compile-time evaluation, but I don't see the benefit of limiting it to pure functions. This proposal introduces the builtin gotype, but limits its use to const functions and any data types defined within function scope. From the perspective of a library user, instantiation is limited to constructor functions like "New", and leads to function signatures like this one:
const func New(K, V gotype, hashfn Hashfn(K), eqfn Eqfn(K)) func()*Hashmap(K, V, hashfn, eqfn)
The return type here can't be separated into a function type because we are limited to pure functions. Additionally, the signature defines two new "types" in the signature itself (K and V), which means that in order to parse a single parameter, we must parse the whole parameter list. This is fine for a compiler, but I wonder if adds complexity to a package's public API.
Type Parameters in Go
Parameterized types allow for most of the use cases of generic programming, e.g the ability to define generic data structures and operations over different data types. The proposal exhaustively lists enhancements to the type-checker that would be needed to produce better compilation errors, faster compile times, and smaller binaries.
Under the section "Type Checker," the proposal also lists some useful type restrictions to speed up the process, like "Indexable", "Comparable", "Callable", "Composite", etc... What I don't understand is why not allow the user the specify their own type restrictions? The proposal states that
There are no restrictions on how parameterized types may be used in a parameterized function.
However, if the identifiers had more constraints tied to them, wouldn't that have the effect of assisting the compiler? Consider:
HashMap[Anything,Anything] // Compiler must always compare the implementation and usages to make sure this is valid.
vs
HashMap[Comparable,Anything] // Compiler can first filter out instantiations for incomparable types before running an exhaustive check.
Separating type constraints from type parameters and allowing user-defined constraints could also improve readability, making generic packages easier to understand. Interestingly, the flaws listed at the end of the proposal regarding the complexity of type deduction rules could actually be mitigated if those rules are explicitly defined by the user.
I like the idea of compile-time evaluation, but I don't see the benefit of limiting it to pure functions.
The benefit is that it makes separate compilation possible. If a compile-time function can modify global state, then the compiler must either have that state available, or journal the edits to it in such a way that the linker can sequence them at link time. If a compile-time function can modify local state, then we would need some way to track which state is local vs. global. Both add complexity, and it's not obvious that either would provide enough benefit to offset it.
What I don't understand is why not allow the user the specify their own type restrictions?
The type restrictions in that proposal correspond to operations in the syntax of the language. That reduces the surface area of the new features: there is no need to specify additional syntax for constraining types, because all of the syntactic constraints can be inferred from usage.
if the identifiers had more constraints tied to them, wouldn't that have the effect of assisting the compiler?
The language should be designed for its users, not for the compiler-writers.
there is no need to specify additional syntax for constraining types because all of the syntactic constraints can be inferred from usage.
This is the route C++ went down. It requires a global program analysis to identify the relevant usages. Code cannot be reasoned about by programmers in a modular fashion, and error messages are verbose and incomprehensible.
It can be so easy and lightweight to specify the operations needed. See CLU (1977) for an example.
It requires a global program analysis to identify the relevant usages. Code cannot be reasoned about by programmers in a modular fashion,
That's using a particular definition of "modular", which I don't think is as universal as you seem to assume. Under the 2013 proposal, each function or type would have an unambiguous set of constraints inferred bottom-up from imported packages, in exactly the same way that the run-time (and run-time constraints) of non-parametric functions are derived bottom-up from call chains today.
You could presumably query the inferred constraints using guru or a similar tool, and it could answer those queries using local information from the exported package metadata.
and error messages are verbose and incomprehensible.
We have a couple of examples (GCC and MSVC) demonstrating that naively-generated error messages are incomprehensible. I think it's a stretch to assume that error messages for implicit constraints are intrinsically bad.
I think the biggest downside to inferred constraints is that they make it easy to use a type in a way that introduces a constraint without fully understanding it. In the best case, this just means that your users may run into unexpected compile-time failures, but in the worst case, this means you can break the package for consumers by introducing a new constraint inadvertently. Explicitly-specified constraints would avoid this.
I also personally don't feel that explicit constraints are out of line with the existing Go approach, since interfaces are explicit runtime type constraints, although they have limited expressivity.
We have a couple of examples (GCC and MSVC) demonstrating that naively-generated error messages are incomprehensible. I think it's a stretch to assume that error messages for implicit constraints are intrinsically bad.
The list of compilers on which non-local type inference - which is what you propose - results in bad error messages is quite a bit longer than that. It includes SML, OCaml, and GHC, where a lot of effort has already gone into improving their error messages and where there is at least some explicit module structure helping out. You might be able to do better, and if you come up with an algorithm for good error messages with the scheme you propose, you'll have a nice publication. As a starting point toward that algorithm, you might find our POPL 2014 and PLDI 2015 papers on error localization useful. They are more or less the state of the art.
because all of the syntactic constraints can be inferred from usage.
Doesn't that limit the breadth of type-checkable generic programs? For example, note that the type-params proposal doesn't specify an "Iterable" constraint. In the current language, this would correspond either to a slice or channel, but a composite type (say a linked list) wouldn't necessarily satisfy those requirements. Defining an interface like
type Iterable[T] interface {
Next() T
}
helps the linked list case, but now the builtin slice and channel types must to be extended to satisfy this interface.
A constraint that says "I accept the set of all types that are either Iterables, slices, or channels" seems like a win-win-win situation for the user, package author, and compiler implementer. The point I'm trying to make is that constraints are a superset of syntactically valid programs, and some may not make sense from a language perspective, but only from an API perspective.
The language should be designed for its users, not for the compiler-writers.
I agree, but maybe I should have phrased it differently. Improved compiler efficiency could be a side effect of user-defined constraints. The main benefit would be readability, since the user has a better idea of their API behavior than the compiler anyways. The tradeoff here is that generic programs would have to be slightly more explicit about what they accept.
What if instead of
type Iterable[T] interface {
Next() T
}
we separated out the idea of "interfaces" from "constraints". Then we might have
type T generic
type Iterable class {
Next() T
}
where "class" means a Haskell-style typeclass, not a Java-style class.
Having "typeclasses" separate from "interfaces" might help clear up some of the non-orthogonality of the two ideas. Then Sortable (ignoring sort.Interface) might look something like:
type T generic
type Comparable class {
Less(a, b T) bool
}
type Sortable class {
Next() Comparable
}
Here is some feedback to the "Type classes and concepts" section in Genus by @andrewcmyers and its applicability to Go.
This section addresses the limitations of type classes and concepts, stating
first, constraint satisfaction must be uniquely witnessed
I'm not sure I understand this limitation. Wouldn't tying a constraint to separate identifiers prevent it from being unique to a given type? It looks to me that the "where" clause in Genus essentially constructs a type/constraint from a given constraint, but this seems analogous to instantiating a variable from a given type. A constraint in this way resembles a kind.
Here's a dramatic simplification of constraint definitions, adapted to Go:
kind Any interface{} // accepts any type that satisfies interface{}.
type T Any // Declare a type of Any kind. Also binds it to an identifier.
kind Eq T == T // accepts any type for which equality is defined.
So a map declaration would appear as:
type Map[K Eq, V Any] struct {
}
where in Genus, it could look like:
type Map[K, V] where Eq[K], Any[V] struct {
}
and in the existing Type-Params proposal it would look like:
type Map[K,V] struct {
}
I think we can all agree that allowing constraints to leverage the existing type system can both remove overlap between features of the language, and make it easy to understand new ones.
and second, their models define how to adapt a single type, whereas in a language with subtyping, each adapted type in general represents all of its subtypes.
This limitation seems less pertinent to Go since the language already has good conversion rules between named/unnamed types and overlapping interfaces.
The given examples propose models as a solution, which seems to be a useful but not necessary feature for Go. If a library expects a type to implement http.Handler for example, and the user wants different behaviors depending on the context, writing adapters is simple:
type handleFunc func(http.ResponseWriter, *http.Request)
func (f handlerFunc) ServeHTTP(w http.ResponseWriter, r *http.Request) { f(w,r) }
In fact, this is what the standard library does.
first, constraint satisfaction must be uniquely witnessed
I'm not sure I understand this limitation. Wouldn't tying a constraint to separate identifiers prevent >it from being unique to a given type?
The idea is that in Genus you can satisfy the same constraint with the same type in more than one way, unlike in Haskell. For example, if you have a HashSet[T], you can write HashSet[String] to hash strings in the usual way but HashSet[String with CaseInsens] to hash and compare strings with the CaseInsens model, which presumably treats strings in a case-insensitive way. Genus actually distinguishes these two types; this might be overkill for Go. Even if the type system does not keep track of it, it still seems important to be able to override the default operations provided by a type.
kind Any interface{} // accepts any type that satisfies interface{}.
type T Any // Declare a type of Any kind. Also binds it to an identifier.
kind Eq T == T // accepts any type for which equality is defined.
type Map[K Eq, V Any] struct { ...
}
The moral equivalent of this in Genus would be:
constraint Any[T] {}
// Just use Any as if it were a type
constraint Eq[K] {
boolean equals(K);
}
class Map[K, V] where Eq[K] { ... }
In Familia we would merely write:
interface Eq {
boolean equals(This);
}
class Map[K where Eq, V] { ... }
Edit: retracting this in favor a reflect based solution as described in #4146 A generics based solution as I described below grows linearly in the number of compositions. While a reflect based solution will always have a performance handicap it can optimize itself at runtime so that handicap is constant regardless of the number of compositions.
This isn't a proposal but a potential use-case to consider when designing a proposal.
Two things are common in Go code today
- wrapping an interface value to provide additional functionality (wrapping an
http.ResponseWriterfor a framework) - having optional methods that sometimes interface values have (like
Temporary() boolonnet.Error)
These are both good and useful but they don't mix. Once you've wrapped an interface you've lost the ability to access to any methods not defined on the wrapping type. That is, given
type MyError struct {
error
extraContext extraContextType
}
func (m MyError) Error() string {
return fmt.Sprintf("%s: %s", m.extraContext, m.error)
}
If you wrap an error in that struct you hide any additional methods on the original error.
If you don't wrap the error in the struct, you can't provide the extra context.
Let's say that the accepted generic proposal let you define something like the following (arbitrary syntax which I tried to make intentionally ugly so no one will focus on it)
type MyError generic_over[E which_is_a_type_satisfying error] struct {
E
extraContext extraContextType
}
func (m MyError) Error() string {
return fmt.Sprintf("%s: %s", m.extraContext, m.E)
}
By leveraging embedding we could embed any concrete type satisfying the error interface and both wrap it and have access to its other methods. Unfortunately this only gets us part way there.
What we really need here is to take an arbitrary value of the error interface and embed its dynamic type.
This immediately raises two concerns
- the type would have to be created at runtime (likely needed by reflect anyway)
- type creation would have to panic if the error value is nil
If those haven't soured you on the thought, you also need a mechanism to "leap" over the interface to its dynamic type, either by an annotation in the list of generic parameters to say "always instantiate on the dynamic type of interface values" or by some magic function that can only be called during type instantiation to unbox the interface so that its type and value can be correctly spliced in.
Without that you're just instantiating MyError on the error type itself not the dynamic type of the interface.
Let's say that we have a magic unbox function to pull out and (somehow) apply the information:
func wrap(ec extraContext, err error) error {
if err == nil {
return nil
}
return MyError{
E: unbox(err),
extraContext: ec,
}
}
Now let's say that we have a non-nil error, err, whose dynamic type is *net.DNSError. Then this
wrapped := wrap(getExtraContext(), err)
//wrapped 's dynamic type is a MyStruct embedding E=*net.DNSError
_, ok := wrapped.(net.Error)
fmt.Println(ok)
would print true. But if the dynamic type of err had been *os.PathError it would have printed false.
I hope the proposed semantic is clear given the obtuse syntax used in the demonstration.
I also hope there's a better way to solve that problem with less mechanism and ceremony, but I think that the above could work.
@jimmyfrasche If I'm understanding what you want, it's a wrapper-free adaptation mechanism. You want to be able to expand the set of operations a type offers without wrapping it in another object that hides the original. This is a functionality that Genus offers.
@andrewcmyers no.
Struct's in Go allow embedding. If you add a field without a name but with a type to a struct it does two things: It creates a field with the same name as the type and it allows transparent dispatch to any methods of that type. That sounds awfully like inheritance but it's not. If you had a type T that had a method Foo() then the following are equivalent
type S struct {
T
}
and
type S struct {
T T
}
func (s S) Foo() {
s.T.Foo()
}
(when Foo is called its "this" is always of type T).
You can also embed interfaces in structs. This gives the struct all the methods in the interface's contract (though you need to assign some dynamic value to the implicit field or it will cause a panic with the equivalent of a null pointer exception)
Go has interfaces that define a contract in term of a type's methods. A value of any type that satisfies the contract can be boxed in a value of that interface. A value of an interface is a pointer to the internal type manifest (dynamic type) and an pointer to a value of that dynamic type (dynamic value). You can do type assertions on an interface value to (a) get the dynamic value if you assert to its non-interface type or (b) get a new interface value if you assert to a different interface that the dynamic value also satisfies. It's common to use the latter to "feature test" an object to see if it supports optional methods. To reuse an earlier example some errors have a "Temporary() bool" method so you can see if any error is temporary with:
func isTemp(err error) bool {
if t, ok := err.(interface{ Temporary() bool}); ok {
return t.Temporary()
}
return false
}
It's also common to wrap a type in another type to provide extra features. This works well with non-interface types. When you wrap an interface though you also hide the methods you don't know about it and you can't recover them with "feature test" type assertions: the wrapped type only exposes the required methods of the interface even if it has optional methods. Consider:
type A struct {}
func (A) Foo()
func (A) Bar()
type I interface {
Foo()
}
type B struct {
I
}
var i I = B{A{}}
You can't call Bar on i or even know that it exists unless you know that i's dynamic type is a B so you can unwrap it and get at the I field to type assert on that.
This causes real problems, especially dealing with common interfaces like error, or Reader.
If there were a way to lift the dynamic type and value out of an interface (in some safe, controlled manner), you could parameterize a new type with that, set the embedded field to the value, and return a new interface. Then you get a value that satisfies the original interface, has any enhanced functionality you want to add, but the rest of the methods of the original dynamic type are still there to be feature tested.
@jimmyfrasche Indeed. What Genus allows you to do is use one type to satisfy an "interface" contract without boxing it. The value still has its original type and its original operations. Further, the program can specify which operations the type should use to satisfy the contract -- by default, they are the operations the type provides, but the program can supply new ones if the type doesn't have the necessary operations. It can also replace the operations the type would use.
@jimmyfrasche @andrewcmyers For that use-case, see also #4146 (comment).