loading...

Go 2 Draft: Generics

dean profile image Dean Bassett ・7 min read

Go 2 is being drafted.

If you haven't heard, there will be a few major language changes coming to Go 2. The Go team has recently submitted a draft of these changes, and as part of a 3-part series, I've been going through each part, explaining it, and state my opinion on them! This is the second part of the series. Last time I did error values, and this time I will be discussing generics!

Remember that these are just drafts. They will most likely be added to the language, but there is still a chance that it won't. Also, remember that these drafts are not final, of course. The syntax will probably be a bit different from what it is right now.

These may not also be the only changes to the language, but these will probably be the only major changes.

So, Go is getting generics?

Well, maybe... remember that these are only drafts, and may not be implemented in this way, or even at all!

But before we discuss why we would want to have generics, we need to figure out what is wrong with not having them.

Interfaces

So, Go has a unique way of using interfaces. This allows us to not really need generics in many cases, as the values passed in don't need to explicitly implement the interface, they only need to have the required methods!

There are certain things that interfaces can't solve though. Particularly when it comes to channels, slices, maps, and other primitive types.

Why we need generics

Generalized functions like the following cannot be written without generics:

// Returns the keys from a map
func Keys(m map[K]V) []K

// Merges multiple channels into a single channel
func Merge(chans ...<-chan T) <-chan T

Those are just a couple examples. The only type-safe way to implement those would be to write a new function for each type you want it implemented for, which is the opposite of Go's goal of reducing code duplication.

Goals of Generics in Go

So, what does Go want out of generics?

  • Go wants to add a way to "abstract away needless type detail", such as the Keys and Merge functions in the previous section.

  • They do NOT want to target things such as special implementations, like their example of having a general Vector<T> and a special case of Vector<bool> which has bit-packing.

  • They do NOT want turing-complete templates (like C++) or type erasure (like Java), or weird cases that reveal how the generics system works internally. The generics implementation should fit smoothly into the language (looking at Java again with generic array types...).

  • Generic type information should be accessible in both the compile-time AND run-time.

Proposed syntax

Well, types in Go are always declared, and generic types should be no different. While they cannot be declared at the package keyword, they should be prefixed with type.

// A list implementation based on an internal slice.
type List(type T) []T

// A keys function which returns all keys of a map in a type-safe way.
func Keys(type K, V)(m map[K]V) []K

Hey, that's some good progress!

But let's say we want to have a IndexedSet(type T), not everything in Go is comparable (for instance, functions and maps are not currently comparable in Go), and the values must be comparable in order to check if it's already in the Set!

That's where we get contract. Contracts look a lot like functions, but instead of executing code, they specify restrictions on types.

Let's make a contract called Equal for our Set(type T).

contract Equal(t T) {
    t == t // assert that t must be able to use the `==` operator.
}

And now, we can implement our IndexedSet!

// T must satisfy the `Equal` contract. This is shorthand for (type T Equal(T))
type IndexedSet(type T Equal) []T

// Returns the index of x in our IndexedSet, or -1 if
// x is not in the set.
func (s IndexedSet(T)) Find(x T) int {
    for i, v := range s {
        // both `v` and `x` are type T, which satisfies our
        // `Equal` contract
        if v == x {
            return i
        }
    }
    return -1
}

Sweet, so now we can represent a set of values, and access each value by an index!

So we have shown that we can use generics on a data structure so that we can generalize it to work on almost any type. But data structures aren't the only thing that can have generics, remember that we have functions too!

Let's make a Sum function, which sums all of the values inside of a slice of any summable type.

contract Add(t T) {
    t + t
}

// (type T Add) is shorthand for (type T Add(T))
func Sum(type T Add)(x []T) T {
    var total T
    for _, v := range x {
        total += v
    }
    return total
}

Now, we have a function which sums up all of the values in a slice, and returns the result. Let's look at how to call it!

func main() {

        // =================================
        // Running `Sum` with ints
        // =================================

    var w []int
    wSum := Sum(int)(w)


        // =================================
    // Same as above, but with type inference
        // =================================

    var y []complex128
    ySum := Sum(y) // very familiar syntax!


        // =================================
    // Super clear as to how this works
        // =================================

        var foo func([]float32) float32
    foo = Sum(float32)

    var z []float32
    zSum := foo(z)


        // =================================
        // Compile error!
        // `Sum` may not be referenced without
        // defining its generic types.
        // =================================

    bar := Sum
}

Now that we've covered what they are pretty sure they want, let's talk about some stuff they aren't sure about.

Open Questions

So there are some issues about generics that the Go team is still unsure about.

1. Implied Constraints

// Maps must have the `==` operator defined on their keys.
// Then the question begs, should the following function compile properly?
// Or should we be required to make a contract for K?
func Keys(type K, V)(m map[K]V) []K

// alternatively...

contract Equal(t T) {
    t == t
}

// Now, we apply the Equal contract to K
func Keys(type K, V Equal(K))(m map[K]V) []K

2. Dual Implementation

Since a generic type's real type is available at compile time and run time, there is an issue when we want to have a generic method on a type. The issue is kinda hard to explain, so let's use an example:

// A set of values
type Set(type T Equal) ...

// Calls the function `f` on each value in Set(T),
// and then returns the results as a Set(U)
func (s Set(T)) Apply(type U)(f func(T) U) Set(U)

This is extremely useful, but it has consequences...

Consider that Set(int).Apply(int) evaluates to a separate function from Set(int).Apply(string).

What would the following code print?

func main() {
    v := reflect.ValueOf(Set(int){})

    fmt.Println(v.NumMethod())
}

Since Set(int).Apply(int) and Set(int).Apply(string) are separate, then v.NumMethod() would have to be, well, equivalent to the number of defined types (theoretically infinite).

On the other hand, the Apply method can still be written as a top-level function, but because of the restriction, it can't be a method on Set(T).

func Apply(type T, U Equal(T))(s Set(T), f func(T) U) Set(U)

3. Contract Bodies

Essentially, they want to know if contract bodies should be allowed to have any code, or if they should be restricted to a subset of go code.

For instance, should we allow the following?

contract C(t T) {
    if t == t {
        for i := 0; i < t; i++ {
            t = t + t
            t = t * t
        }
    }
}

(Side-note: the code in a contract never gets executed)

When really, the contract would be much more readable in the the following form:

contract C(t T) {
    t == t       // T is comparable
    0 < t        // T is relational to integers
    t = t + t    // T is assignable and has a + operator
    t = t * t    // T is assignable and has a * operator
}

My opinions

Semantics

I love the semantics. I really love the idea of f(int) evaluating to a function which uses an int as its generic type. It looks like a function call that returns another function, which is really nice.

Syntax

While the semantics behind f(int) is really nice, it comes with a huge drawback.

So. Many. Parentheses.

The current function declaration syntax would now be something similar to the following:

func (Receiver) FuncName(Generic Type List)(Argument List) (Return Value List)

Contracts

I don't like contracts. I feel like they could have done a better job, and I have already submitted feedback to their wiki about it. I got a response, which is cool. Might need to adjust my feedback though because

Overall

I really like Generics. Personally, I don't think Go really needs them, but I would like them. My only issue is that I feel like Go is settling a lot, which really isn't good.

Straight from the generics draft overview:

Polymorphism in Go must fit smoothly into the surrounding language, without awkward special cases and without exposing implementation details.

If that's what you want, then why do we have to deal with that awkward special case with not having generic functions with receivers?

From the contracts draft:

Why not use interfaces instead of contracts?
The interface method syntax is familiar. Writing contract bodies with x + x is ordinary Go syntax, but it is stylized, repetitive, and looks weird.

It is unclear how to represent operators using interface methods. We considered syntaxes like +(T, T) T, but that is confusing and repetitive. Also, a minor point, but ==(T, T) bool does not correspond to the == operator, which returns an untyped boolean value, not bool. We also considered writing simply + or ==. That seems to work but unfortunately the semicolon insertion rules require writing a semicolon after each operator at the end of a line. Using contracts that look like functions gives us a familiar syntax at the cost of some repetition. These are not fatal problems, but they are difficulties.

TL;DR: They couldn't figure out a good syntax to define operators for interfaces... is that really a good reason?

In the end, I feel like they settled quite a bit in order to get this proposal out, which just doesn't seem like Go. Not that this is a terrible proposal, or that I'd be sad to have this in the language, but I feel like it can be made a lot better.

Posted on by:

dean profile

Dean Bassett

@dean

Computer science major at Michigan Technological University, class of 2020 👀

Discussion

markdown guide
 

To be honest I do not see semantic difference between interfaces and generics. The only difference is that generics have always been resolved in compile time, interfaces in run-time.
I'd prefer to extend semantics of standard interfaces that allows to use built-in types as interfaced object and add something like static modificator to interfaces that will say to compiler to resolve/convert functions and stucts in compile time.
I always have supposed that issue of generics in Go is that it makes compilation complicated and broke main feature of Go, very fast compilation.

 

Looking back at this, I realize that I didn't really respond to this properly.

  1. There really aren't many "modifiers" in Go. This is because Go really wants the simplest type system possible. The current type system is extremely straightforward.

  2. Interfaces are resolved at compiletime as well as runtime. For instance, you cannot assign a struct to an interface type if the struct does not implement the interface.

    If you want to assert that a struct implements an interface, you can put var _ = InterfaceType(StructType{}) as a package level variable. I personally don't like this practice but it gets the job done.

  3. Generics in Go will compile quickly, it is one of their main goals. They believe that generics really won't be used much anyway, because there are very few problems that they really solve. There are also very few features in Go generics because Go's type system is so simple. All of these things together show that compile times in Go should still be extremely short, even with generic types.

 

Hi... I'm not sure that I told something special about Go generics proposal... Actually I agree with Rob that usefulness of generics is overestimated. Including generics/templates in C++ standard have just opened Pandora's box. Look at implementation of the simpliest template std::vector in GCC (man std::vector). It didn't look simple at all. For most of nowadays' programmers it looks at it as at dark evil magics. After all of that C++ cannot be considered as simple programming language.
About 'static resolution' of golang's interfaces... You are right. Sure, they are no fully run-time resolved. I just tried to simplify the way to explain my idea. It looks like it was not reach the goal.
Golang compilation is quickly now. But look at std::vector implementation one more time. You should notice how many additional conceptions will be added to make it really generics (batch of traits, additional types and adoption objects). I'm far enough to think that guys from Standard committee of C++ didn't try to simplify all of it. But we have what we have now. So...
Anyway the time is the best judge and teacher. Let's look what it will be turned to...

C++ is just a bad implementation of Generics in my opinion. Everyone uses it as an example of a mistake. So I'll fully agree with you on that front.

Also, I agree with Rob too. There really aren't many problems that Generics solve, but there are a few things that they solve that are extremely useful. The nice thing about Go's implementation is it's not meant to be some big complicated system. But yes - we'll see how they turn out.

To be honest I cannot agree that generics in C++ is a bad implementation. I suppose it's just a real price you should pay for this "real generics". Sure, you can move the implementation from STDLIB/STL to under hood of compilator, but it changes nothing. In the same way you can never look at the implementation of STL and consider them as well-done. Most C++ programmers does it in this way.

 

Look at the examples I have provided. There is no generalized, type-safe way to implement them without generics

 

Yikes, the syntax is uglier than I had feared.

Parens for everything. Everything looks like a function call.

I guess if you take an ugly language and glob on more features, it can only get uglier.

IMO they should redesign the whole syntax to something more traditional. I’ve heard the argument that they designed the syntax so the compiler would be fast - I’ve always thought that was nonsense. Plenty of compilers with a more traditional syntax are just as fast or faster than Go.

I like the ideas of Go a lot. It’s a shame it has to be so hard to read...

 

I think that the idea is that it should look like a function call. So calling something like Sum(int) would be a "function call" that returns a func ([]int) int

I agree that it's a lot of parentheses in the definition, but hopefully type inference is good enough that the parentheses aren't needed much at the call site, if at all.

 

Looks to me that. No. Like some java crap that distracts what language should do, instead doing it. They should not keep it just simple but micro service simple; rather than including monolith concepts. Maybe looking even more to python direction than Java.

 

Can they please use <> for types just like Java or C++? These paranthesis are not readable!

 

The idea behind their parentheses are that it should act like a function - calling Max(int32) returns a func(int32, int32) int32. To call this function, one could do Max(int32)(x, y), or with type inference, Max(x, y) will work fine.

Then to declare a function that takes type parameters, it should ideally look similar to calling it: func Max(type T)(i1, i2 T) T.

That is the justification for all of the parentheses. I'm not sure if I entirely agree with it, but I'm not against it.