proposal: Go 2: generic native types (GNTs) #32863

rcoreilly · 2019-06-30T15:31:27Z

This proposal is to add generic native types (GNTs) to Go: generic versions of each of the native builtin types (e.g., map = generic map, slice = generic slice, number = generic number, float = generic float, signed = generic signed integer, unsigned = generic unsigned integer, etc).

Edit: Can also use generic types to specify container types, e.g., []number is a slice with number elements, map[string]number, etc.

GNTs support a substantial proportion of generic programming functionality, without adding any new syntax to the language: generic code looks identical to regular Go code, except for the use of these generic type names, and a few extra functions that access the type parameters of container objects such as maps and slices (e.g., elem(x) is the type of the elment in a slice or map; key(m) is the type of the key of a map; field(s, fieldName) is the type of the given named field in a struct; return(f) is the type of return value from function, and type(x) is the type of a generic var, e.g., for use in return signature).

The generic struct is the most challenging case, because of its unlimited number of type parameters. The proposed strategy is to adopt the interface concept, but specialized for the struct type, as a struct interface -- see #23796 for discussion of a related proposal, where most of the objections were about "polluting" the existing interface concept with struct-specific functionality -- this problem is avoided by having a special type of interface only for structs, which provides all the benefits from that proposal, as well as supporting the definition of a generic struct type.

Edit: It might be clearer to use prototype instead of struct interface due to the differences between this type and the existing interface -- they do share some properties but also differ significantly.

Here are some examples of some of the main generics use-cases under this proposal:

func Keys(m map) []key(m) {
    s := make([]key(m), len(m))
    idx := 0
    for k := range m {
        s[idx] = k
        idx++
    }
    return s
}

// note: all args in same list (x,y) must be of same concrete type
func Min(x, y number) type(x) {
  if x < y {
     return x
  }
  return y
}

// A struct interface is like an interface, specialized for struct -- any struct
// with the specified field names and types gets the generic methods,
// instantiated for the concrete type
type Vec2 struct interface {
    X, Y number // or float
}

Edit: or prototype version:

// A prototype provides an abstract implementation based on a struct,
// using generically-typed fields, and methods operating on those fields.
// Any concrete struct with the specified field names and types matches the prototype
// (similar to how interfaces are "magically" matched, except based on fields,
// not methods).
// The concrete struct then gets the generic methods from the prototype,
// instantiated for the concrete field types
type Vec2 prototype {
    X, Y number // or float
}

func (v Vec2) Add(u Vec2) Vec2 {
    return Vec2{v.X + u.X, v.Y + u.Y}
}

// Vec2f32 instantiates the generic Vec2 struct interface [prototype] for the float32 type
type Vec2f32 struct {
    X, Y float32
}

func myfunc() {
    v1 := Vec2f32{1,2}
    v2 := Vec2f32{3,4}
    sum := v1.Add(v2) // this is automatically instantiated from prototype
}

package graph

// Edge defines a connection between two nodes, as a struct interface.
// Any type with fields named From and To that are pointers to a 
// concrete struct that implements the Node struct interface will satisfy
// the Edge interface.
type Edge struct interface {
    From, To *Node 
}

// Node defines a node in a graph, which has Edges connecting it to other
// nodes.  Any concrete struct with a slice of structs satisfying the 
// Edge struct interface, named Edges, will satisfy this interface.
type Node struct interface {
    Edges []Edge // concrete slice of a struct interface type..
}

// Unlike the draft proposal, methods can be defined with struct interface args
// just like any interface type can be passed around currently.  A boxing penalty
// is likely but perhaps not inevitable.
func (n *Node) ShortestPathTo(to *Node) []Edge {
    for _, e := range n.Edges {
        if e.To == to {
            return []Edge{e}
        }
        se := e.To.ShortestPathTo(to) // all just std interface virtualization method calls..
        if len(se) > 0 {
            return se // actually would need to sort by path length and return shortest, but whatever..
        }
    }
    return nil
}

In summary, GNTs leverage the "contracts" associated with the existing native types in the language, instead of introducing an entirely new syntax to specify novel such contracts. This makes programming with these types immediately intuitive and natural for any Go programmer, and the code as shown in the above examples inherits the simplicity and elegance of the existing Go syntax, as compared to other generics proposals that require additional type parameters etc.

Edit: The key difference between GNTs and the draft proposal (and other similar approaches using separate type parameters) is that these other approaches split the type information into two separate parts, while GNTs keep the type specification unitary and in one place (where it normally is for non-generic code). For example, in the draft proposal:

func Print2(type T1, T2)(s1 []T1, s2 []T2) { ... }

You have to go back and forth between the type args and the regular args to understand what the types of s1 and s2 are -- the information is split across these two places. In contrast, under the GNT proposal:

func Print2(s1 slice, s2 slice) { ... }

the type is fully specified (albeit still generic) in one place.

To use a colorful metaphor, the draft design is like a horcrux that splits key information painfully across multiple places, whereas GNT's preserve the "natural" unity of type specification: you don't have to go searching across multiple hiding locations to find the type :) More scientifically, reducing cognitive load by not having to integrate across these separate pieces of information is a well-established principle: https://en.wikipedia.org/wiki/Split_attention_effect

The major limitation is that generic functionality is limited to these existing native types. You cannot define Min / Max functions that work across all native numbers and on non-native numbers such as big.Int. The bet here is that GNTs solve 80% or more of the use-cases in the cleanest, simplest way -- i.e., the defining feature of Go.

Several of the required keywords are repurposed from existing ones, and thus would have no compatibility impact:

Type kinds: map, chan, interface, struct, struct interface (combination)
Type parameters: type(x), return(f) (with optional 2nd arg specifying which return val if multiple -- could be index or name if named)

These new ones would create potential conflicts:

Type kinds: slice, array, number, unsigned, signed, float, complex, prototype
Type parameters: elem(x), key(x), field(x, fieldName)

See GNTs gist for a full discussion of the proposal -- would be happy to write a design doc according to standard template if requested.

The text was updated successfully, but these errors were encountered:

av86743 · 2019-06-30T16:07:34Z

Also compare with #32862 just prior to this one.

dotaheor · 2019-06-30T17:47:51Z

It is some like this one without the outer gen part.

ianlancetaylor · 2019-06-30T23:17:26Z

One of the goals of generics is to permit people to write type safe containers that are not already provided in the language. A typical example would be a concurrent hash map, such as a type safe version of sync.Map. I don't see how this proposal permits that.

Am I correct in thinking that this is much the same as https://gist.github.com/rcoreilly/bfbee2add03c76ada82810423d81e53d ?

rcoreilly · 2019-07-01T01:15:41Z

@ianlancetaylor Yep I'm submitting an updated, more fully worked-through version of that gist idea here in order to get a complete, considered evaluation of this idea from the entire team, per the proposal process description. Here is my response to that question from the go-nuts email list (you didn't reply to this response so I don't know if it is satisfactory or not?)

you can do any valid map operation on the generic type “map”, so at a minimum it seems like you could just add an appropriate mutex around each of the different operations, using a struct interface:

type SafeMap struct interface {
    mu sync.RWMutex
    m  map
}

func (m *SafeMap) Store(k key(m.m), v elem(m.m)) {
    m.mu.Lock()
    if m.m == nil {
        m.m = make(map[key(m.m)]elem(m.m))
    }
    m.m[k] = v
    m.mu.Unlock()
}
…

any concrete map that shares that struct interface type signature (i.e., the same field names and types) automatically gets the associated methods:

// MySafeMap implements the SafeMap struct interface
type MySafeMap struct {
    mu sync.RWMutex  
    m  map[string]string
}

func MyFunc() {
    m := MySafeMap{}
    m.Store(“mykey”, “myval”) // at this point the compiler knows the concrete type of “m”, can compile Store
}

Robert Engles replied:

That is not sufficient. You can't require the usage of the built-in map, as specialized maps may have a completely different structure (special hash tables when the keys are ints, or more commonly special CAS techniques for highly concurrent lock-free maps).

To which I replied:

That is a good point of clarification about the specific limitation of this proposal: it specifically reifies the existing Go type system and does NOT enable the generic-ification of arbitrary novel types. If you can build a specialized type out of generic versions of existing Go types, then you’re good, but if you need something entirely different, then this won’t do it. The key question is whether having a really simple and tractable “native types” version of generics solves enough problems, while avoiding the challenges of going “fully generic”, to hit that “Go” minimalism sweet spot..

ianlancetaylor · 2019-07-01T01:46:02Z

Thanks, I did see that discussion, and didn't reply further because I thought the point had been made. Sometimes you want a type-safe container that is entirely different. I think that is part of the 80%, not the 20%.

typeless · 2019-07-01T03:51:52Z

I like this proposal. It adds minimal syntax complexities and zero emission of noises for generic code. It does not change much how Go1 code looks.

rcoreilly · 2019-07-01T04:24:18Z

@ianlancetaylor Have you considered that, as long as said container is composed out of existing container elements, GNTs would handle that case? How many containers would not have a map or slice as the underlying storage?

Also, it would be possible to adopt this proposal on its own minimalist merits, and postpone a more "generic" generic solution, after real-world experience with how far this can go. It seems likely that anything that is "fully generic" is going to incur a significant syntactic penalty in terms of type specifiers and contracts, so perhaps it would be better to put that off until we can see to what extent it is really that valuable in real-world cases?

And @typeless thanks for the support!

ianlancetaylor · 2019-07-01T07:02:46Z

The maps provided by the language don't permit you to specify a hash or equality function, so they are limited in how they handle keys.

You can't implement a proper concurrent hashmap on the basis of maps or slices; you need a more complex data structure.

I find these to be serious difficulties with this approach. Of course others may not agree.

rcoreilly · 2019-07-01T16:01:43Z

Not to belabor the point but if these features were deemed not important enough to include in the language itself then perhaps that indicates their status relative to the 80 / 20 tradeoff?

Could we use some Go corpus stats to decide these kinds of questions - how frequently are those features actually used?

mikeschinkel · 2019-07-01T20:29:51Z

@ianlancetaylor

The maps provided by the language don't permit you to specify a hash or equality function, so they are limited in how they handle keys.
You can't implement a proper concurrent hashmap on the basis of maps or slices; you need a more complex data structure.

Is it not possible to consider a solution for the subset of the problem? Seems that is the approach the try() proposal chose?

ianlancetaylor · 2019-07-01T21:05:13Z

@rcoreilly The language has a limited set of generic types. The generics problem is that Go provides no way for people to write generic code other than using that limited set. Any 80/20 tradeoff here, if there is one, doesn't have anything to do with what Go already provides. It has to do with a tradeoff among concepts that Go does not provide. I am suggesting that the ability to write compile-time-type-safe containers is part of the 80% that needs to be provided by any solution to the generics problem. The fact that Go does not provide such containers doesn't tell us anything about whether compile-time-type-safe containers are in the 80% or 20% of what Go does not provide.

Could we use some Go corpus stats to decide these kinds of questions - how frequently are those features actually used?

I don't think I understand this question. Since Go does not provide these features, they are never used.

ianlancetaylor · 2019-07-01T21:07:54Z

@mikeschinkel We can consider steps that solve a subset of the problem, as long as there is a clear path forward to addressing more of the problem as we gain experience. The try proposal, for example, is careful to explain that we can add additional arguments to the try builtin function to add additional functionality, such as wrapping errors, if that seems desirable.

mikeschinkel · 2019-07-01T23:54:11Z

@ianlancetaylor Not in reply to your reply. but as an additional comment.

However, since this is off-topic of this proposal I am hiding it in a details section.

Click to read

I think everyone in the Go team understands that generics are a very hard problem to solve without recreating the complexity of generics in Java et.al. And I for one very much do not want Go to become so complex that its code is hard to reason about in order to add generics.

One thing Go has done that is relatively unique in the realm of serious programming languages is provide builtin functions with features that a Go programmer cannot develop on their own, e.g. append(), make(), etc. Earlier in my career I would have thought that to be a negative but now I think one of the strengths of the language is that it can offer special case solutions so that its language does not have to become too complex.

As such, it is my hope that the Go team will address most of the need for generics with builtin functions to handle the 80+% of use-cases. Here is my list of proposed new builtins:

A func that returns a slice of property values given a map or slice of structs, e.g. props(myMap,Id) and props(mySlice,Id) where Id is a property of the struct that myMap and mySlice contain.
A func that converts a map of structs to a slice, or a slice of structs to a map; e.g. convert(myMap) and/or convert(mySlice,myKeyExpression) where myKeyExpression is either a property name, or an expression that assumes property names that are not qualified, e.g. fmt.Sprintf("%s:%s", id, FullName()) where both id is a property and FullName() is a method of the struct that myStruct is a type of.
A func that filters a map or a slice, e.g. filter(mySlice,myFilterExpression) where myFilterExpression is equivalent to myKeyExpression above but that returns bool but if false eliminates the element from the returned slice.
A func that iterates a map or a slice, e.g. mySlice, err = iterate(mySlice,myIterateExpression) where myIterateExpression could be Validate() and returns an error or nil and if != nil short-circuits the internal loop and return with the error as 2nd return value.
A func that unwraps an interface{} containing a map or slice to a map or slice containing the same type contained in the interface{}s, or a map or slice of interface{}s containing identical types to a map or slice of that type, e.g. unwrap(myInterfaceOfMap), unwrap(myInterfaceOfSlice), unwrap(mySliceOfInterface) and/or unwrap(myMapOfInterface).
A func that wraps an a map or slice into a map of interface{} values containing the types, e.g. wrap(myMap) and/or wrap(mySlice).

I am assuming that the compiler could see all the above and be able to optimize it hence why there would be no need to qualify properties or methods.

OTOH, for the unwrap() method that works with interfaces the Go compiler might not know what types it will contain so I would propose having the compiler recognize an Unwrap() methods as a special interface for any type that needs to be unwrapped thus allowing the unwrapping code to be precompiled. If an interface{} was attempted to be unwrapped and its contained types did not implement the Unwrapper interface then it should throw a panic().

Of course the names I chose are open for bikeshedding, but the functionality is really what I wanted to present. There maybe be one of two more that I have forgotten, but this is all I've got at the moment.

The above would probably eliminate at least 80-90% of my needs for generics and it would probably reduce the number of lines of code in my codebases by 1/3 to 1/2 current size.

rcoreilly · 2019-07-02T14:48:20Z

@ianlancetaylor Haven't people written non-type-safe interface{} based versions of containers that they really need? That is what I'm suggesting could be analyzed to determine the prevalence of demand for containers outside the standard. Also, it would be important to see how many of those weren't backed by a standard slice or map in a way that would be amenable to this approach. Or easily handled using a struct interface as in the Graph example, which also handles linked lists and all manner of tree-like structures. I've got very limited internet here in Yellowstone now so can't easily look up examples but I'm sure there are lots of them that I've seen..

Also, in terms of a pathway to full generic types, it occurs to me that this overall approach could be extended as in Michal Straba's generics proposal to use the keyword type for a fully generic item (while using the type(x) function to access the actual type, instead of defining an extra type parameter, to eliminate need for additional syntax) -- this would then forgo the benefits of having a known "contract", but would be available for "extreme" cases. But I'm struggling to see how you would compute a hash function on a fully generic type? Probably you'd want to make specialized versions for number, string keys? Seems like it would still be a lot better to not include this at the start, to see if it is really worth "going there".

ianlancetaylor · 2019-07-03T01:17:11Z

I see, sure, that is worth asking. It's not a great comparison since interfaces generally require boxing values, so there is a real cost to building containers based on interfaces. So people avoid doing that. But it's worth asking. For example, can this proposal be used to build a compile-time-type-safe version of sync.Map?

rcoreilly · 2019-07-03T14:56:42Z

Yep definitely can do a compile-time-type-safe version of sync.Map -- when the struct interface is instantiated by a concrete struct it should have everything it needs to compile all the methods.

ianlancetaylor · 2019-07-04T01:17:29Z

I don't understand how that works. And looking back at your SafeMap example, I don't understand how that works either. I can sort of see how struct interface defines an generic interface that other types can implement, and I can sort of see how MySafeMap implements SafeMap. But that's not what I want. I want SafeMap to be the complete implementation, written in terms of a generic type parameter. I don't want to have to write MySafeMap, which has specific key and element types. See the "containers" example in https://go.googlesource.com/proposal/+/master/design/go2draft-contracts.md .

rcoreilly · 2019-07-04T05:36:46Z

It is just a different way of achieving the same end result. Either you add new syntax to specify type parameters (following the paradigm used in C++ and other languages), or you name a concrete instantiation of a struct interface type (which seems like a more Go way to do it, following the interface paradigm). In both cases, you are specifying the same information.

In other words, the move here is to adopt the idea that an abstract interface is much like a generic type specification, and concrete types that implement the interface are what you actually want to use in any given case. By using the struct form of the interface, we can specify concrete types for the generically-typed fields, but otherwise it should work much like an existing interface.

A drawback is that you need to come up with relevant names for the concrete instantiations (probably something better than MySafeMap) -- that type name effectively replaces the generic type and the type parameters in the standard approach.

But the advantage is that you can further customize the concrete type, just like something that implements an interface can also do various other things -- i.e., the polymorphism / mix-and-match model instead of just a "type-parameterized instantiation of a canonical generic type". Also, this approach can naturally support multiple different generic fields, which would start to get awkward for the type parameter approach. Furthermore, it is very clear exactly when and where the generic type is being instantiated with concrete type args -- this could simplify a lot of the issues with duplicate code generation etc.

For many cases involving generic number or float types, e.g., the Vec2 example, it would be natural for the package to provide default named instantiations (Vec2f32, Vec2f64) so it functions much like existing code generation techniques.

So anyway, yes this is definitely not the standard type-parameterized generics syntax, and this is also why I think it is likely to be the most "Go-like" of any of the existing proposals, most of which follow in that general type-parameter mold..

lootch · 2019-07-04T06:51:48Z

On 7/4/19, rcoreilly ***@***.***> wrote: It is just a different way of achieving the same end result. Either you add new syntax to specify type parameters (following the paradigm used in C++ and other languages), or you name a concrete instantiation of a `struct interface` type (which seems like a more Go way to do it, following the `interface` paradigm). In both cases, you are specifying the same information.

Any chance you could explain by example? Lucio.

ianlancetaylor · 2019-07-04T12:44:33Z

When I say that I believe that any generics implementation must be able to support compile-time-type-safe containers, I mean that people must be able to write the code for a container once, and be able to instantiate that code many times for many different types. I think the ability to do that is a requirement for any generics proposal in Go.

rcoreilly · 2019-07-06T18:32:27Z

@typeless I'm not familiar with those GCC extensions so I'll have to look those up -- good prior art it seems! Regarding the unexported (lowercase) fields, there would have to be a rule that says that the unexported fields of a struct interface are exported to the struct that instantiates it (across package boundaries). Furthermore, the use of unexported fields (e.g., f.s in example code) in any methods in either the struct interface or the instantiating struct would be legal because these are all local to the current package. Anyone importing a package with the instantiating struct would not be able to refer to the unexported fields, as expected with the current rules.

Then it is just a question of design preference whether to use unexported or exported field names, as it is currently.

rcoreilly · 2019-07-06T18:41:35Z

Looks like typeof became decltype in C++11 -- relevant arguments about its utility: https://en.wikipedia.org/wiki/Decltype

rcoreilly · 2019-07-28T14:18:14Z

Perhaps it would be clearer to use a different keyword such as prototype instead of struct interface, given the differences between how the proposed struct interface works compared to the existing interface. An interface is an abstracted API defined strictly in terms of methods, and the struct interface is not really that -- you don't match or redefine its methods.

prototype captures more of the core idea of something that is an abstracted implementation, where the fields need to be concretized to make fully implemented type.

It is also cleaner to have a single keyword instead of a sequence of two.

rcoreilly · 2019-07-29T00:58:45Z

Just saw the updated contracts proposal: https://go.googlesource.com/proposal/+/master/design/go2draft-contracts.md -- given that contracts can now only specify existing types, wouldn't it be simpler to just introduce sensible generic type categories in the first place, and do away with the need for the contract syntax and the type parameters! :) How many times will people specify random combinations of number types? Or generic functions that operate on string and number types? This seems like a lot of extra parentheses and syntax, for potentially rarely needed extra degrees of freedom..

alanfo · 2019-07-29T16:51:58Z

given that contracts can now only specify existing types, wouldn't it be simpler to just introduce sensible generic type categories in the first place, and do away with the need for the contract syntax and the type parameters! :)

Well, last September shortly after the first draft design for generics had been published, I wrote an alternative proposal which did use what I thought at the time were sensible 'type groups'. However, it later became clear that, with the integer groups, there were problems with the smaller types not being able to deal with untyped literals outside their range and, in later proposals, I came up with the idea of being able to exclude such types from those which would otherwise have satisfied the contract.

When I look at the latest draft design, I think listing the types which can satisfy the contract is much simpler and more flexible (even if a trifle long-winded) than having predefined type groups though a standard contracts package can, of course, include the contracts which are most likely to be used in practice.

ianlancetaylor · 2019-07-29T17:40:14Z

This seems like a lot of extra parentheses and syntax, for potentially rarely needed extra degrees of freedom..

Note that the only extra syntax for contracts is the ability to write an identifier after the list of type parameters. The extra parentheses are still there to list the type parameters.

In exchange we get the ability to, for example, write a function that operators on either a []byte or string, which I believe is not available in this proposal. We also have the possibility of writing generic functions that operate on generic containers, though I admit that I don't know whether that will really work out in practice.

rcoreilly · 2019-07-30T14:49:40Z

@alanfo I remember some of that discussion which certainly inspired this current proposal. Within the context of the draft design, the ability to list types explicitly and also use predefined contracts that delineate the standard kinds of categories seems reasonable and is certainly more flexible than only having predefined categories.

However, in the context of the present proposal, there is a much bigger potential benefit available by using generic type names (signed, unsigned, integer, number, etc), which is retaining the current Go1 syntax entirely, and avoiding extra type parameters. Using lists of types and / or having the ability to define arbitrary new categories would probably be an excessive complexification here. I'm not sure the language itself should be expected to prevent numerical overflow if you use too small of a type for the job..

rcoreilly · 2019-07-30T15:06:50Z

@ianlancetaylor you should be able to write a lot of common functions that operate on slices of any type using the generic slice type: e.g., Reverse, Insert, Delete, etc. string could presumably be treated as a special read-only []byte slice in this case, and the compiler could catch any attempt to use non-read-only slice operations on generic code instantiated with the string type.

It should also be possible to extend the proposal to include generic types of the form []number or []integer, etc, which would allow more control over the element type. In which case, you could write generic code with explicit type conversions of the elements as needed to do just about anything, in methods that would accept any such type, including []byte and string (subject to the read-only constraints above).

I haven't looked into the guts of bytes vs. strings packages to evaluate this more concretely, but probably many of those methods could be written generically under this proposal. Presumably there are still a number of cases that must be specialized for string to deal with its read-only nature (and availability of the + operator), and that would be the case for any generics proposal.

alanfo · 2019-07-30T16:11:53Z

@rcoreilly

I'm not sure the language itself should be expected to prevent numerical overflow if you use too small of a type for the job.

The problem with using the smaller integer types was not so much that they might overflow but that (to take an example from the current design draft) they wouldn't compile at all:

func Add1024(type T integer)(s []T) {
	for i, v := range s {
		s[i] = v + 1024 // INVALID: 1024 not permitted by int8/uint8
	}
}

Nonetheless, unanticipated overflow is a problem with something like a generic sum function and, unless some new integer type(s) are to be introduced which panic on overflow, it might be better for such a function to always return (u)int64 rather than the element type of the slice which is being accumulated.

rcoreilly · 2019-07-30T17:00:35Z

Is it a problem if that code would not compile when you try to instantiate it with [u]int8? Seems like that would be a good thing -- you'd know at compile time that it doesn't make sense to instantiate that generic function with that type (compiling only happens when you instantiate with a specific type). Yep it does seem like a Sum function should return a (u)int64 to avoid overflow.

ianlancetaylor · 2019-07-30T17:21:29Z

One important question is: what does that compilation failure look like?

One of the major problems with C++ templates is the long nested compilation errors that result from using a template incorrectly. That is not something we want in Go.

rcoreilly · 2019-08-01T03:11:29Z

The compiler should know that it is dealing with a concrete instantiation of a generic type, so I would think that it could provide a suitably specific error message.

Also, I would guess that the majority of generic code would use the prototype (struct interface) approach, in which case there is a clear specific point at which the generic type is instantiated into a concrete one, so all error messages etc would be localized there, and clearly traceable to that point in the code.

rcoreilly · 2019-09-18T04:32:30Z

Just checking back in on this -- has this ever been discussed among the core team? Is it DOA or might there still be a chance? I still think it represents an opportunity to do something truly Go-level innovative, simple, and elegant (with commensurate limits), but if a more conventional, general-purpose approach is favored, then that probably makes sense too. Anyway, would be great to hear any more specific comments if available.

ianlancetaylor · 2019-10-11T20:34:53Z

I just re-read this issue, and I have to say that I do not find it to be simple.

Adding new categories like number, signed, unsigned, float means adding a new set of names and concepts that every Go programmer must learn. You suggest that this is simpler than listing types in a contract. I don't agree. Listing types in a contract, as suggested in the current generics design draft, adds only one new concept to the language: the ability to list types. In practice, people will then rely on the standard library for things like contracts.SignedInteger. I would prefer to put new concepts in the standard library than in the language proper.

That said, defining new compile-time-type-safe data structures remains my major concern. As far as I can tell, the idea here is that a struct interface automatically adds methods to types that follow a certain pattern, but only in the case where a certain package is imported. Nothing else in Go works like that. It seems to mean that a change in one package can silently break a distant package, as it can cause methods to be added to, or removed from, an existing type. That does not seem simple and it does not seem to me to be particularly Go-like.

An 80% solution should introduce a minimum of new concepts to the language. For that matter, the same is true for a 100% solution. I don't see that this proposal meets that goal.

rcoreilly · 2019-10-11T21:26:12Z

Simple is all relative I guess. The definition I was using is that no new syntax is added, and the resulting code looks exactly like current Go code. I think people would find the generic code to be highly readable and "simple" to understand, per the examples above. There have been a number of objections to the draft design about the new syntax with all the extra parens etc being a major barrier. E.g., Dave Cheney's blog: https://dave.cheney.net/tag/generics I personally find C++ template code nearly unreadable because of all the extra parameters, and there is solid cognitive science research that says that people have a very limited ability to process multiple things at the same time, so adding additional type parameters just pushes the cognitive limits in a serious way (regardless if you use parens or <> or whatever). I really think this is a big issue and is the single most important advantage to this design.

Per some discussion above, the proposal is that struct interface (or prototype) only adds methods for types that directly include the package that defines the prototype. This prevents any silent indirect damage. I don't think it is too difficult to understand this principle, even if it is not currently true of other Go code.

As for the objection about adding the new type categories, that is certainly valid. something has to be added to get the new functionality. I personally don't think that these would be difficult to understand, and given that these type categories are likely to be widely used under any proposal, people will end up having to learn these new categories one way or another. So in some ways just biting the bullet and adding simple, short, clear keywords to the language itself might be better than putting it off into a longer package name like contracts.SignedInteger. That is a lot to type and read compared to signed. Also, it is not like these categories are ever going to change -- there are just a few obvious such categories given the properties of numbers and the Go type system, so enshrining them in the language doesn't seem particularly risky in that respect.

Anyway, lots of judgment calls and again reasonable people will differ. But overall my feeling is that this represents the kind of simplicity argument that has driven Go decisions in the past, and has made the language so special -- the number one consideration has been to keep the code clean and easy to read and understand, and I see this as a way to achieve that goal in the realm of generics, whereas the draft proposal will introduce a lot of extra cognitive load, and is overall very similar to the way things have been done in other languages. Here's a chance to do something different!

ianlancetaylor · 2019-10-11T23:01:24Z

Adding struct interface is new syntax.

When you point out that there are no type arguments at the call site, that leads me to wonder how for

func AddTo(s []number, a number) {
    for i := range s {
        s[i] += a
    }
}

we can express the fact that a must have the same type as the elements of s. That is, when a function has different arguments of type number, sometimes those have to be the same type, sometimes they don't. How do we express that?

rcoreilly · 2019-10-12T06:05:38Z

For many cases, there is a convenient solution:

// note: all args in same list (x,y) must be of same concrete type
func Min(x, y number) type(x) {
  if x < y {
     return x
  }
  return y
}

If you don't want to enforce that constraint, then use separate type specifiers:x number, y number. This doesn't work for your example, but there are two potential solutions.

You could use the type(x) expression to specify the slice type:

func AddTo(s []type(a), a number) {
    for i := range s {
        s[i] += a
    }
}

This is more readable I think than requiring explicit type args for everything, even though it is just a bit more complex and more indirect in terms of mental load than just writing number.

Thus, as a "pragmatic" special case, we could simply state that any container element type that matches that of another non-container type, implies the same concrete type. This would likely be correct for the vast majority of uses -- how often would you want to not have that be the case?

Anyway, there is certainly room for debate about option 2 but hopefully option 1 is reasonably satisfactory in any case.

rcoreilly · 2019-10-12T06:08:02Z

and would you call prototype new syntax, or just another new generic type name? I kinda like prototype better than struct interface at this point, given that the behavior is sufficiently different from interface, and it is also shorter to type.

ianlancetaylor · 2019-10-15T23:49:44Z

If prototype is a new keyword then it is new syntax by definition.

func AddTo(s []type(a), a number) {

The scoping here troubles me. Currently other than at package scope Go names are always scoped so that references must follow the definition. That changes here.

rcoreilly · 2019-10-16T06:05:22Z

I forgot about the elem() expression, which allows it to be written in the right order and with the proper semantics that the type is really coming from the container:

func AddTo(s []number, a elem(s)) {

In fact, it would probably be much more likely for this kind of code to appear as a method on a type rather than a standalone function like that.

type NumSlice []number

func (s *NumSlice) AddTo(a elem(s)) {

This would presumably be a fairly familiar pattern so seeing that elem(s) would become expected and easily processed. Likewise for key(m) etc.

As to whether the backward-order version should still be allowed, even if not encouraged, it is probably the case that the parser's multiple passes would be able to handle the forward reference within that same argument scope, so that would have to be a judgment / design call.

rcoreilly · 2019-10-16T06:11:14Z

and when I was referring to new syntax above, I was talking about something that would change the parse tree in a fundamental way, like adding a whole new set of type parameters to functions, as compared to just adding a new keyword that can be plugged in where e.g., previously you would have had float64 and now you have number -- that seems like a qualitatively different type of new syntax. I guess prototype is a bit more than number but it still looks mostly just like struct from the parsing perspective.

rcoreilly · 2019-11-13T00:39:30Z

I'm adding this to the overall intro, to highlight the key difference between this proposal and the draft proposal and other standard approaches to generics using separate type arguments: The draft proposal et al split the type information into two separate parts, while this proposal keeps the type specification unitary and in one place (where it normally is for non-generic code). For example, in the draft proposal:

func Print2(type T1, T2)(s1 []T1, s2 []T2) { ... }

You have to go back and forth between the type args and the regular args to understand what the types of s1 and s2 are -- the information is split across these two places. In contrast, under the GNT proposal:

func Print2(s1 slice, s2 slice) { ... }

the type is fully specified (albeit still generic) in one place.

To use a colorful metaphor, the draft design is like a horcrux that splits key information painfully across multiple places, whereas GNT's preserve the "natural" unity of type specification: you don't have to go searching across multiple hiding locations to find the type :)

rcoreilly · 2019-11-13T00:54:12Z

link added to first issue description (intro): https://en.wikipedia.org/wiki/Split_attention_effect

rcoreilly · 2020-06-17T22:33:37Z

Closing this in favor of the much simpler #39669 which is essentially a syntactic variant of the current draft proposal.

gopherbot added this to the Proposal milestone Jun 30, 2019

gopherbot added the Proposal label Jun 30, 2019

ianlancetaylor added v2 A language change or incompatible library change LanguageChange labels Jun 30, 2019

This comment has been minimized.

Sign in to view

ianlancetaylor added the generics Issue is related to generics label Oct 29, 2019

rcoreilly mentioned this issue Jun 3, 2020

proposal: spec: generic programming facilities #15292

Closed

rcoreilly mentioned this issue Jun 17, 2020

proposal: Go 2: generic types (GT) #39669

Closed

rcoreilly closed this as completed Jun 17, 2020

golang locked and limited conversation to collaborators Jun 17, 2021

gopherbot added the FrozenDueToAge label Jun 17, 2021

proposal: Go 2: generic native types (GNTs) #32863

proposal: Go 2: generic native types (GNTs) #32863

Comments

rcoreilly commented Jun 30, 2019 • edited

av86743 commented Jun 30, 2019

dotaheor commented Jun 30, 2019

ianlancetaylor commented Jun 30, 2019

rcoreilly commented Jul 1, 2019 • edited

ianlancetaylor commented Jul 1, 2019

typeless commented Jul 1, 2019

rcoreilly commented Jul 1, 2019

ianlancetaylor commented Jul 1, 2019

rcoreilly commented Jul 1, 2019

This comment has been minimized.

mikeschinkel commented Jul 1, 2019 • edited

This comment has been minimized.

ianlancetaylor commented Jul 1, 2019

ianlancetaylor commented Jul 1, 2019

This comment has been minimized.

This comment has been minimized.

This comment has been minimized.

mikeschinkel commented Jul 1, 2019

This comment has been minimized.

rcoreilly commented Jul 2, 2019

ianlancetaylor commented Jul 3, 2019

rcoreilly commented Jul 3, 2019

ianlancetaylor commented Jul 4, 2019

rcoreilly commented Jul 4, 2019

lootch commented Jul 4, 2019 via email

ianlancetaylor commented Jul 4, 2019

rcoreilly commented Jul 6, 2019

rcoreilly commented Jul 6, 2019

rcoreilly commented Jul 28, 2019

rcoreilly commented Jul 29, 2019

alanfo commented Jul 29, 2019

ianlancetaylor commented Jul 29, 2019

rcoreilly commented Jul 30, 2019

rcoreilly commented Jul 30, 2019

alanfo commented Jul 30, 2019

rcoreilly commented Jul 30, 2019

ianlancetaylor commented Jul 30, 2019

rcoreilly commented Aug 1, 2019

rcoreilly commented Sep 18, 2019

ianlancetaylor commented Oct 11, 2019

rcoreilly commented Oct 11, 2019

ianlancetaylor commented Oct 11, 2019

rcoreilly commented Oct 12, 2019

rcoreilly commented Oct 12, 2019

ianlancetaylor commented Oct 15, 2019

rcoreilly commented Oct 16, 2019

rcoreilly commented Oct 16, 2019

rcoreilly commented Nov 13, 2019

rcoreilly commented Nov 13, 2019

rcoreilly commented Jun 17, 2020

rcoreilly commented Jun 30, 2019 •

edited

rcoreilly commented Jul 1, 2019 •

edited

mikeschinkel commented Jul 1, 2019 •

edited