Press "Enter" to skip to content

Golang: A New Generics Implementation Proposal

0

A few days ago, a new proposal draft for generics implementation in Golang was submitted.

What are “Generics” and what Needs do they Solve?

It is a long time that the language has been lacking the ability of defining functions and other entities that are not based on concrete types but on generic, parametrized types. Thus, for example, the functions for finding minimum and maximum – math.Min() and math.Max() – are only defined in the standard library for float64, and not for any other type. Even if one would like to create their own Min-Max package, with functions like mymath.Min() or mymath.Max() for various types, they would not be able to do so. No current structure in the language allows code like this:

...
	
var vi, ui int
var vi8, ui8 int8
	
vi = min(102, ui)
vi8 = min(ui8, 3)
...	

In the first assignment, the function Min() is used with int arguments (at least the right one; the type of the left one, which is a literal, allows the language a bit flexibility). The function’s result is also assigned to a variable of type int. On the second assignment, a function with the very same name is called, but this time, it should accept int8 arguments and return an int8 result.

But How could we even try to achieve that?
On the one hand, the language requires clear, concrete argument types as part of the function definition. That means that a single function is restricted to a single type per argument. For example, the following can only handle arguments of type int and will always return a result of that type:

func Min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

On the other hand, the language does not allow function overloading. That means, one cannot write several functions named Min(), in the same namespace, which only differ by their argument type. So, trying something like this is completely irrelevant:


func Min(a, b int) int { ... }
func Min(a, b int8) int8 { ... }

This leaves us with only two options. Either writing a set of almost-identical functions, which share the very same logic and only differ by their types and names – say, something like this:

func minInt(a, b int) int { if a < b { return a }; return b }
func minInt8(a, b int8) int8 { if a < b { return a }; return b }
func minInt16(a, b int16) int16 { if a < b { return a }; return b }
...

which is not the prettiest, clearest, safest and most elegant code ever seen; or, trying to use the language’s current wildcard, interface{}. This other option will require an ugly code in its body to convert the argument to its real type, which might be any of the numerical ones.  Worse than that, its caller must also convert the result to the original type. It is so ridiculous, that it is not a real option.

What we really want is an elegant way to have “one ring to rule them all”; something like –

func min(a, b «SOMETYPE, which is any numeric type») «that very same SOMETYPE» { 
    if a < b { 
        return a 
    } 
    return b 
}

which will then allow us any call of the form –

vi = min(102, ui)
vi8 = min(ui8, 3)
vi16 = min(ui16, 0)
...

Simple.
Clear.
Elegant.
Impossible.

When working with more complex types, that are being accessed using functions rather than operators, the language does provide some sort of flexibility. In those cases, using interfaces does allow functions to work in a polymorphic fashion. For example, a function f1() might define its argument to be of type Averager, where Averager is defined as an interface that requires the definition of a function named Average(). This way, the function can safely call Average() on it, without knowing its actual type, and the appropriateAverage() function will be called. This is the standard implementation of polymorphism in Go.

The “lowest common denominator” of the types is the already-mentioned type interface{}, that defines no functions at all. It can therefore be replaced by any other type, but for the very same reason, it is much less useful.

How Does it Works?

The new proposal formalizes the idea presented above about using that “SOMETYPE“. The type parameter(s) appear in square brackets, between the function name and its parenthesis. For example, it will be possible to write a function like that:


// Stringify accepts a slice of any type that 
// implements the Stringer interface:
func Stringify[T Stringer](s1, s2 []T) (ret []string) {
  ...
}

This function, Stringify(), accepts one type-parameter, T; however, not any type is allowed as a T replacer. Only types that implement the Stringer interface might fit in. Then, it gets two arguments, s1 and s2, that must be of the same chosen type for T.  The type that follows the type-argument – e.g., Stringer, in that example – is the constraint on T. If no constraint is to be applied, a new keyword, any, is provided.

It is also possible to define complex types in a parametric form. For example:


// Vector is a name for a slice of any element type.
type Vector[T any] []T
...
var vi Vector[int] 
var vf Vector[float64]

It is funny to observe that here, as in many other syntactic issues, Go seems to deliberately diverse from the common form of C++ and its cousins. The angle brackets, <T> – the undoubted traditional “trademark” of templates or generic – was dropped in favor of the square brackets. The proposal does explain the reason for that, though (hint: constraint on Golang’s compilation rules). Not only by form, but also by concept, Go is very different than those languages, even if the draft is accepted. Other compiled languages, like C++, Java or Rust, offer extremely powerful generic/template tools, that are made to take a major part in common design and development. Go, at least according to that draft, is still way behind them; its generics are meant to be a mere minor solution for few edge cases.

The main drawback of compiled languages is the need to prepare the binary product for each platform in advance. On the other hand, the advantages of such languages is their ability to produce much more efficient products, both in footprint and performance. One of the key ingredients for that is using those generics’ abilities during compile-time resolution to improve the run-time. Go does not plan to go that path; so –
Will that purpose actually make Golang more efficient?
The answer is – it probably will, but in a quite limited fashion.
What are, then, the advantages of that proposal over the current situation?


The Draft’s Main Benefits

While the support in generics in this proposal is very limited related to other languages, it will still offer developers with several important advantages.

Moving Errors from Run-Time to Compile-Time

Finding errors and bugs during compilation-time allows a much faster progress in code development, than when the same bugs are only found during run-time. And run-time, of course, is not necessarily any run; it is not necessarily first run; in fact, it might just as well firstly occur on one of the client’s runs. In principle, careful crafting of interfaces might dramatically reduce that risk. However, many Go functions are written using general interfaces as arguments, where only within the function their dynamic types are tested and they are being converted to the appropriate concrete static types. Using generics might change the coding style and make it more accurate in the first place.

Polymorphism without Functions

As demonstrated at the beginning of the post, arguments of interface types are only good for accessing through polymorphic function or methods. If a function should accept non-concretely-typed arguments and access them not by functions but by operators, this is a whole different story. The current Go syntax can only allow that by converting to various acceptable static types within the function. This approach is

    1. cumbersome,
    2. violates OCP – the Open/Closed Principle,
    3. results in performance penalty, and
    4. moves the error from compile-time to run-time.

The other option, as demonstrated with the min()/max() functions, will be to write many look-alike functions, one per concrete type. In principle, writing those two functions using generics should solve all of those issues.

Enforcing Constraints between Two or More Polymorphic Arguments

A Go function can accept an argument of some interface type Some. Similarly, a function might accept two or more arguments of that interface type. For example, like that:

func f1(a Some) { ... }
func f2(a, b Some) { ... }

In this case, f1() will accept for a anything that implements the interface Some. If Sometimes and Somewhere both implement Some, then either of them will work fine. The same is true for a and b in f2(). Of course, it is also possible that one of them will be of type Sometimes and the other of type Somewheref2() does not enforce them to have the same concrete type.
And can not enforce it.
Sometimes it really doesn’t matter. But there are always other cases somewhere.

Using the new proposed generics syntax, it is possible to define f3(), that accepts two arguments of the same type that implements Some:

func f3[T Some](a, b T) { ... }

Calling f3() with two Sometimes arguments will work, as well as calling it with two Somewhere ones. However, trying to call it with one Sometimes argument and one Somewhere argument will break the compilation. In a similar way, it is possible to define not only type-identical arguments, but any other type-based relation. For example, an argument of type T and another argument that is []T, etc.

Directly Using Generic Types

A standard Go function that gets a polymorphic type through an interface-type argument cannot directly use the actual type of that argument. For example, it cannot create a local variable of that type. Using the generics proposal, this can be done easily and elegantly.

Define Complex Structures using Type-Parameters

As demonstrated at the beginning of the post, the new proposal allows not only defining generic functions but also generic types. For example, a struct that holds two slices of some numeric types (either of the same T for both, or of two possibly-different types, T and S). Using that generic types, it is easy to create concrete types that define the specific type(s) of the slice(s), and use them like any other struct.

Improve Performance and Footprint by Direct Access to Internal Elements

Any access to data through an interface is done indirectly: the interface never holds the data itself, but rather a pointer to the actual data. Thus, for example, an int8 that is being held through an interface, consumes much more than a single byte of memory, and any access to its value requires a “double access”: first, to the address of the interface, and then, using the pointer it holds, to the address of the data itself. This might not be a critical consideration when dealing with a few such issues here and there. But when this is the case, for example, in a very large slice, the consumed memory and the run time might dramatically increase. Add to this a garbage collector that updates all the addresses all the time – and this becomes a real issue. Using generics according to that proposal will eliminate all that overhead.

What the Proposal Might Improve, Under Some Implementations?

The current draft suggests the syntax for generics in Go. It does not define its specific implementation. Unlike in languages like C++, where the top goal is to always produce the most efficient binary product, Golang is led by several competing goals.

Thus, for example, function templates in C++ are separately compiled for each of their instantiations. Assume that we have a C++ function template named makePairs() that accepts two vectors vt, vs of various generic types T and S and returns a vector of pairs, such that the i-th pair is composed of the i-th element in vt and the i-th element in vs. If that function is being called – at least once – with two vectors of ints, the compiler will instantiate a specific function for that.  If in some other place(s) that function is being called with two vectors of doubles, then the compiler will produce an additional instance of it, for two vectors of doubles. If yet another piece of code calls makePairs() with vt as int and vs as double, a third instance will be created. At compilation/linkage time, each call will be linked to the appropriate instance, which is exactly tailored for those arguments. Since no run-time checks of the actual type is required, and the compiler can optimize each instance separately in the best way, it will usually achieve the best performance (also involved here are code bloat effects, function inlining and other optimizations). But this comes with a cost: anyone that ever compiled a significant C++ project knows that its extremely efficient product is the result of very long compilation time. Template instantiation is a part of this trade-off.

In Go, not only the efficiency of the final binary is important, but also the efficiency of the compiling process itself. When those two compete, Go’s compiler will settle it by some compromise between them. For that reason, although the draft does not specifically define the implementation for generics, it assumes that it will take a different path than multiple instantiations.

What this Proposal does not Allow?

Generic Functions on Top of Generic Types

In addition to minimizing the run-time and footprint of binary product and minimizing the time of the compilation process, Go also strives for minimizing the language itself, that is: keeping its syntax as simple as possible. Go keeps this principle even when it comes with the cost of less elegant code or avoiding sophisticated abilities. Its philosophy is that it is better to keep the syntax as simple as possible even if it requires many more lines of code for achieving a task that could have been coded by fewer lines of complex syntax. This is one of the main reasons that Go is considered as having a relatively short learning curve. In fact, this approach is the main reason for not having generics yet.

In C++, for example, it is possible to have a class template that accepts some generic type T, and add to it a member function template (or “generic method”, if we translate it to Go’s terms) that accepts some other generic type S. Thus, the concrete member-function (“method”) depends on both T and S. This elegantly allows a wide range of use-cases. But the large flexibility of templates – like this combination of class template and function template – makes C++’s templates extremely non-trivial for newcomers.

Go, on the other hand, loyal to its principle, forbids such complex generic structures. The current draft allows only a “one-dimensional” “genericness”:
either a generic function that accepts only concrete types,
or a function that works on a generic type, without any additional type parameters.
This approach might result in a bit cumbersome code (e.g., creating a new generic type for the sole purpose of sending it to a given function), but it keeps the syntax simpler.

Specialization

Another ability that this proposal does not allow is defining different versions of generic code for specific types – which is known as Specialization. This approach makes sense in the context of a language that does not allow even a simple, basic function overloading: any function call must map to a specific function that is defined solely by its name. However, eliminating specialization highly narrows the usage and elegance of generics.

Recall the example at the beginning of the post – the functions math.Min() and math.Max(). Currently, they are only defined on float64. It will be tempting, then, to rewrite them as generic functions, so that they would work for any two numeric arguments of the same type. For example, something like that:


// Assume that constraints.Ordered includes 
// all the types on which "less then" operator works 
func Min[T constraints.Ordered](x, y T) T { 
  if x < y { 
    return x 
  }
  return y 
}

Simple, elegant, works on every type that the concepts of minimum applies for. The obvious solution!
Alas, it won’t work as expected!
The exiting functions for minimum and maximum calculation, that work on two float64 arguments, must consider special cases that are irrelevant for integer types. For example, what happens in the case of infinity, NaN, or when comparing +0.0 with -0.0. Since writing a special case of a generic function is not allowed, it would not be possible to solve that elegantly. One way to solve that might be by writing several functions with different names – e.g. a generic MinInt() for all integer types and other functions for non-integer types. Another approach might be writing a single generic Min(), which internally checks the actual type of its arguments and applies different calculations as appropriate. Not the most efficient and elegant design. In addition, such solutions are not polymorphic by design (not Open/Close) and results in performance penalty and cumbersome code.

Implicit Interface – Duck Typing

One existing approach to generic code assumes that there is no formal restrictions on the types that the generic code (function or type) might accept. The interface of a given generic type T is not explicitly defined, but implicitly inferred from the logic (which is also called Duck-Typing – a term taken from the Python world). That is, whenever the generic code is called, the compiler tries to read it using the provided arguments and their types. If the code compiles for that specific type – e.g., int64 or MyAwesomeCar – it is Okay. The generic code only becomes meaningful after each specific call. Moreover:
It is impossible to know a-priory whether calling a piece of generic code for a given type is legal or not, without going over the whole logic of the generic entity.

This approach allows some freedom for creative, multi-dimensional use of such code, but it is very poor from software engineering point of view. In order to know whether it is legal to call some function with a MyAwesomeCar argument, one must first try it and see if compilation passes; struggling with the possible compilation errors to understand the problems and how to solve them might be very difficult by its own. And if one already know that MyAwesomeCar does work with the generic function, it might have some hard time knowing what changes are fine and what might break the code.

This is why the proposed draft requires any generic code to explicitly define the interface required from the types it accepts. The draft refer to that definition as the Constraints on the generic type. The definition might be done in one of two ways. The first is “open”: the code defines an interface that defines what functions must be defined for any acceptable type. Any type will do, as long as it implements the interface. The other way, which is provided for supporting non-functions generic operations (e.g. the operator <, as in the Min() example), is “closed”: the interface defines the constraints using a final set of allowed types.

Meta-Programming

According to the draft, a piece of generic code can only serve as a boiler plate for some Go code, allowing the replacement of one or more generic types by concrete ones. It is deliberately not advanced enough to allow defining logic using the generics’ syntax itself. That is, no meta-programming – i.e., logic that is written using generics syntax and actually “runs” during compilation – is allowed. This, of course, makes lots of sense according to the Go’s principles of fast compilation and syntactic simplicity.

Additional Complexities

The world of generic programming is wide, rich and complex, and allows – in different languages – many additional abilities:

  • Defining the allowed types and their interrelations in various ways;
  • Defining generic arguments that are value-arguments rather than type-arguments;
  • Variadic entities that are not limited to a fixed number of generic arguments;
  • Using generic entities within other generic entities;

These are only a few of the additional tools that generic code allows in languages like C++, Java or Rust. The proposed draft, loyal to Go’s philosophy, deliberately avoids such directions and leaves the generics a rather simple, basic tool. Moreover, the proposal was written under the clear, explicit assumption that relatively very little generic code will actually be written. It suggests that only few, rare libraries will be written in generic terms. Most Go programmers, according to this prediction, will only have to deal with calling such generic code.

 


 

Summary

The lack of generics in Golang is a controversial issue that is being discussed for a long time. This is not the first attempt to add such a mechanism to the language, but so far, none of the attempts succeeded. The current proposal tries to overcome the problems and suggest a simple, basic mechanism. Should the community accept it and it becomes part of the language, it will be easier to inspect the actual usage of it. By learning the actual solutions and obstacles that a wide community of programmers finds in this solution, it will be easier, later on, to reconsider relevant changes towards a deeper generics support.