Home - Blog - Publications - CV - Scribblings - Photo Album - Funny

July 29, 2019

Are Only Type Parameters Generic Enough for Go 2 Generics?

The Go language appears to be getting slightly closer to supporting generics, with the recent release of a new proposal for generics based on type parameters and contracts.

I generally like the direction this proposal is going, with one significant reservation. I feel that the current proposal both unnecessarily limits how “generic” Go’s generics will be, and risks painting the language into a corner in the long term. This is because the proposal single-mindedly assumes that the only compile-time generic parameters we will ever want are type parameters, which seems like an unnecessary and undesirable restriction. This blog post offers feedback to the current generics draft proposal, exploring this concern and potential solutions.

What Distinguishes Parameters to Generics?

In the current generics proposal, function definitions may be parameterized with a set of optional type parameters, separate from and preceding the function’s regular parameters, as illustrated in the proposal’s simple generic Print example:

func Print(type T)(s []T) {
    for _, v := range s {
        fmt.Println(v)
    }
}

What is actually going on here is that the generic function Print takes one compile-time parameter T (a type) and one run-time parameter s (a slice of type T). A user of this generic binds T to a specific actual type at compile time, which may happen either explicitly or implicity using type inference, to produce a “version” of Print specialized to type T. This specialization of Print to type T is in turn a function taking a run-time parameter s, which the function’s caller will bind to a run-time actual parameter: i.e., a specific slice with elements of type T to be printed.

Of course, as the proposal discusses, such a generic can be compiled multiple ways with different tradeoffs. The compiler could produce a single block of Print code that internally uses polymorphism or reflection mechanisms to operate dynamically on any type that might be passed to it. Alternatively, the compiler might actually instantiate a separate copy of the Print code specialized to each specific type that callers happen to bind T to. The compiler has both options: that’s part of the point.

The restrictions the generics proposal imposes on type parameter lists ensure that the compiler can enumerate all possible bindings of T if it needs to, and thus has the option of choosing either implementation approach. Run-time function parameters clearly do not in general, and should not be expected to, enable the compiler to determine at compile-time (for example) all possible slices that might be passed in as the run-time s parameter. With run-time parameters, compile-time enumeration of all parameter bindings and compile-time specialization based on them is not, in general, an option.

The central crux of this post is simple: what most fundamentally distinguishes the optional “generic” parameter list of a generic function such as that above from its regular parameters is not the fact that T is a type parameter while s is a slice parameter, but the fact that T is a compile-time parameter while s is a run-time parameter.

I that think the current Go 2 Generics proposal unnecessarily “bakes in” an assumption that all compile-time parameters must be type parameters while all run-time parameters must be non-type parameters (e.g., values of specific types such as slices, integers, etc.). This baked-in assumption may appear expedient in keeping the current proposal “as simple as possible” — though any realistic generics proposal including this one is inevitably far from simple — but in doing so this decision may paint the language into a corner and preclude useful and powerful generalizations either now or in the future.

Must All Compile-Time Generic Parameters Be Types?

Suppose for a moment that Go 2 were to follow the C++/Java tradition of using angle brackets instead of parentheses to distinguish the compile-time parameters of generics. I am not actually proposing this syntax, as I agree with the proposal’s preference to avoid the ambiguities arising from overloading either angle brackets or square brackets for this purpose. But merely taking C++-style syntax as a comparison point for now, the above Print generic function might become:

func Print<T>(s []T) {
    for _, v := range s {
        fmt.Println(v)
    }
}

But must all generic parameters be types and only types? It is often useful in practice to be able to write code that can be specialized at compile-time according to non-type parameters such as integers.

The Go language, in fact, already has a built-in generic type that takes a non-type parameter. An array type, specified as [n]t, takes a constant-integer parameter n along with its element-type parameter t. So Go already has a limited precedent for non-type parameters to generic types. Go 2 should should be consistent and compatible with this precedent, and ideally expand on and generalize it. It would be nice if Go 2 generics allowed us, for example, to write generic functions that could be specialized at compile-time to fixed-length arrays of different lengths.

Suppose, for example, that we attached types to compile-time parameters, just like we do with run-time parameters. Again adopting C++-like syntax for now, we could write a generic dot-product function over float32 arrays of any length fixed at compile-time as follows:

func DotProduct<N int>(a, b [N]int) float32 {
    var sum float32
    for i := range a {
        sum += a[i] * b[i]
    }
    return sum
}

Of course it would be nice to make such a function generic over the element type as well instead of fixing it on float32, and that should be possible using the contracts in the current proposal: either by listing all the built-in types supporting the * operator, or by defining a contract with an element-type parameter supporting a method like Mul. But for the moment let’s ignore the contract issues and pretend that all types magically supported the * operator. The above DotProduct example might then become:

func DotProduct<N int, T type>(a, b [N]T) T {
    var sum T
    for i := range a {
        sum += a[i] * b[i]
    }
    return sum
}

Notice that we now have both type and non-type compile-time parameters, each declared in traditional Go “identifier type’ declaration order, with the keyword type doubling as a “meta-type” denoting the type of a type parameter. As a purely stylistic matter, this approach feels more consistent with Go’s existing syntax than the current generics proposal, where a single run-time parameter is declared like (i int) while a single type parameter is declared like (type t).

We could similarly consider whether the type keyword in its “meta-type” role should perhaps become usable in declarations of ordinary run-time parameters and variables as well. Go already has considerable precedent for treating types as runtime objects via its reflection API. In a runtime parameter list, the built-in type type might be either an alias of or otherwise closely related to the existing reflect.Type interface, for example, which already essentially serves this role in run-time usage of types. But this would be a separate and orthogonal discussion to be had, and I have not thought through the potentially nontrivial syntax implications of the type keyword becoming usable anywhere a type name or literal may be used now.

But regardless of how permissive or restrictive Go’s generics prove to be in terms of permitting non-type compile-time parameters, in the interest of keeping future options open if nothing else, it would seem desirable to avoid baking into Go 2’s generics an unchangeable assumption that all compile-time parameters are type parameters and all run-time parameters are non-type parameters. Because both type and non-type parameters certainly make sense as both compile-time and run-time parameters, in all four combinations.

What About Poor Neglected const?

Notice that Go’s built-in array generic restricts its length parameter to be an integer constant, and for good reason: an array’s length must be evaluable at compile time in order for arrays to be embeddable in fixed-length structures without indirection or allocation, and generally in order to serve the role they were designed to fill. The restriction of the array’s length to a compile-time constant is part of the array’s fundamental efficiency contract.

If Go 2 were to allow non-type compile-time parameters to generics, then it would make sense to restrict the values bound to such parameters to be constants, for exactly the same reason. You could instantiate the above DotProduct example with any constant integer N known at compile time, but not with an integer variable or parameter known only at runtime.

Notice that Go already has a keyword whose purpose is to bind a declared identifier to a constant evaluable at compile-time: namely const. You can already use const to assign the result of a complex expression, as in:

const MeaningOfLife int = 2*3*7

But the compiler checks that it can actually evaluate the expression at compile time and complains otherwise. Constants being constants, one would presumably be allowed to use the above MeaningOfLive identifier in instantiating a generic like DotProduct above taking a non-type int parameter, just like one can already use MeaningOfLive in declaring a Go array, while one could not use an ordinary (run-time) integer variable or parameter for either purpose.

The const keyword currently serves only this one rather restricted purpose, but that doesn’t mean that this is the only purpose it can serve. What if we were to use it also in declaring other things whose values must be evaluable and bound to constants at compile time — things like compile-time parameters to generics, for example?

If Go wishes to avoid the ambiguities of C++/Java-style generic syntax for the reasons I understand and respect, then I propose that a more flexible, “generic”, rational, and linguistically-consistent syntax would be to use const instead of type to introduce compile-time parameter lists for generics. For example, the basic Print generic would become:

func Print(const T type)(s []T) {
    for _, v := range s {
        fmt.Println(v)
    }
}

A generic function with two compile-time type parameters and two run-time parameters would look like this:

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

The example DotProduct generic above with two compile-time parameters, one a non-type parameter and the other a type parameter, would now look like this:

func DotProduct(const N int, T type)(a, b [N]T) T { ... }

In general, the (const ...) syntax would declare a parameter list that must be bound to concrete actual parameters at compile-time rather than at run-time, but otherwise looks and works like standard Go parameter list syntax.

I believe this approach is compatible with the semantics and syntax of contracts in the current Go 2 generics proposal. The new contract construct effectively declares additional meta-types more restrictive than type. For example, after declaring the proposal’s equal contract defining types with an Equal method, the example generic Index function becomes:

// Index returns the index of e in s, or -1.
func Index(const T equal)(s []T, e T) int { ... }

Notice that equal is used here instead of type as a more-restrictive meta-type denoting any particular type evaluable at compile-time that has an Equal method according to the contract. The current proposal’s syntax, (type T equal), is conceptually redundant in that both the type keyword before T and the equal identifier after T both effectively declare T as a type parameter, the latter by virtue of equal having been declared via a contract. The (const T equal) syntax, in contrast, is non-redundant in that the const keyword declares this to be a compile-time constant parameter list, while the equal alone declares T to be a type parameter (and not an int or string or…) restricted to some particular type satisfying the equal contract.

Assuming we declared a multype contract, either of built-in types supporting the * operator or of arbitrary types supporting a Mul method, we could then properly “fix” the above DotProduct example as follows:

func DotProduct(const N int, T multype)(a, b [N]T) T { ... }

Example Ways Generics Over Non-Types are Useful

There are many ways in which generics over non-type compile-time constant values are likely to be useful. I will briefly cover two classes of such uses here: first, generics over arrays, and second, allowing compile-time configuration and specialization of packages and algorithms for which efficiency matters.

Making [Generics Over] Arrays Useful

Without support for non-type parameters to generics, it will presumably be possible to define functions or types that are generic over (say) all arrays of a particular size over a parameterized type T, but not over all arrays, leaving a major gap in the language, both conceptually and pragmatically in terms of code efficiency.

There are many common uses of arrays for which their compile-time fixed length is important for efficiency, particularly for arrays of small fixed lengths. In image processing, for example, manipulation of RGB 3-tuples or RGBA 4-tuples (with an alpha channel) is extremely common, pervasive, and performance-critical. In 2D and 3D modeling, rendering, gaming, etc., manipulation of 2-, 3-, or 4-element vectors and corresponding 2×2, 3×3, and 4×4 transformation matrices are fundamental and performance-critical. Using arrays instead of slices in short-vector code like this allows the compiler to unroll loops and eliminate range checks effectively.

Currently, developers who care about getting these efficiency benefits must write manually-specialized versions of all the tuple, vector, or matrix manipulation functions they need, once for each relevant combination of tuple/vector/matrix dimensions and element types. The current Go generics proposal will presumably allow semi-generic functions to range over different element types but not different dimensions. It would be nice if vector/matrix operations could be generic over both element types and dimensions.

Example: image processing and RGB versus RGBA tuples

For example, an image processing library that wishes to process both RGB and RGBA tuples leveraging the maximum efficiency of arrays will have to provide two sets of generic pixel-manipulation functions, one for RGB 3-tuples and the other for RGBA 4-tuples, even though each of these can be semi-generic over different numeric types. With support for generics over non-type parameters, the image processing library could provide just one set of generic pixel-manipulation functions, which clients can use — and which the Go compiler can specialize efficiently for — both RGB 3-tuple arrays and RGBA 4-tuple arrays at compile time, depending on the needs of a particular client of the library.

Example: vector and matrix operations in 2D/3D applications

Similarly, a 2D or 3D library (or even the Go standard library) must currently take and process variable-length slices as arguments in order to handle vectors and matrices of different sizes, or else provide a separate set of code specialized to each of the performance-critical common cases: e.g., 2D vectors and 2×2 matrices, 3D vectors and 3×3 matrices, and 4D vectors and 4×4 perspective and orthographic projection matrices. The current Go generics proposal will allow semi-generic functions parameterized with a numeric type (e.g., float32 versus float64) but will still require manually-coded versions for each common-case dimension. Suppporting non-type parameters to generics (or even just constant int parameters alone) would fill this gap and allow libraries to include generic functions specializable at compile time to the particular vector/matrix dimension(s) needed by the application, without either giving up the efficiency benefits of arrays or duplicating large amounts of manually-specialized code.

Example: vector and matrix generics over both slice and array representations

Through appropriate use of the “either-or” type disjunction mechanism already in the Go generics proposal, it should even be possible to build generic libraries compatible with either slices or [pointers to] arrays, not just one or the other. For example, the Go standard library or other libraries could include generic vector operations taking either runtime-dimensioned slices or compile-time-dimensioned vectors:

contract Numeric(T) {
    T float32, float64, int, int32, ...
}

contract Vector(const N int, E Numeric, V type) {
    V []E, *[N]E    // a slice of E or a pointer to an array of E
}

func (r V) Add(const N, E, V Vector)(a, b V) V {
    for i := range r {
        r[i] = a[i] + b[i]
    }
    return r
}

func DotProduct(const N, E, V Vector)(a, b V) E {
    var sum E
    for i := range r {
        sum += a[i] * b[i]
    }
    return sum
}

This capability would get even more useful and powerful considering generics for matrix operations using either slices or multidimensional arrays to represent matrices. In the latter case, the compilar can not only specialize these generics to both the types and dimensions needed by applications, but also enforce appropriate dimension invariants on arrays at compile-time.

A generic function for matrix transposition could, when applied to matrices represented as 2-dimensional arrays, ensure at compile-time that the matrix is square:

contract Transposable(const n int, E Numeric, M type)  {
    M [][]E, *[n][n]E
}

func (r Mr) Transpose(const n, E, M Transposable)(a M) M {
    for i := range r {
        for j := range r {
            r[i][j] = a[j][i]
        }
    }
    return r
}

Similarly, a generic function for matrix multiplication could work with not only different element types but also with either slices or [pointers to] arrays, and in the latter case the compiler can check at compile time the correct dimension correspondences via type unification, and specialize the code to the specific types and dimensions an application actually uses:

contract Multable(const n, m, p int, E Numeric, Ma, Mb, Mr type) {
    Ma [][]E, *[n][m]E
    Mb [][]E, *[m][p]E
    Mr [][]E, *[n][p]E
}

func (r Mr) MatMult(const n,m,p,E,Ma,Mb,Mr Multable)(a Ma, b Mb) Mr {
    for i := range r {
        for j := range r[i] {
            var sum E
            for k := range a[i] {
                sum += a[i][k] * b[k][j]
            }
            r[i][j] = sum
        }
    }
    return r
}

If we add run-time checks to the above code for proper dimension correspondence, then a specializing compiler will automatically compile those checks out to nothing whenever MatMult is used with the array representation, simply as a result of ordinary constant propagation.

These slice-and-array generics examples all have the subtlety of depending on the Go compiler to do something sensible with the const int parameters that aren’t needed when the above generic functions are used with slices. Type unification will not find anything to bind n to when Transpose is called with a slice, for example. This should be OK, however, if the compiler an avoid complaining about unconstrained generic parameters until/unless something in the generated code actually tries to use an unconstrained generic parameter.

Compile-time Configuration and Specialization of Library Code

Beyond arrays and code that depends on them, supporting non-type compile-time parameters to generics would enable library modules to be made configurable at compile time in many ways to support both general and specialized use-cases efficiently.

Compile-time configurable big integers

Consider the Go standard library’s `big.Int’ facility for arbitrary-precision integer arithmetic, for example. While general and highly useful, a fairly common case it does not address is the need for integers slightly larger than the natively-supported 64-bit size but still small and fixed-length for efficiency. For example, there have been calls for 128-bit integers in Go, and the Ethereum virtual machine uses 256-bit integers pervasively.

A developer who needs 128- or 256-bit signed or unsigned integers in particular, and cares about performance, must currently choose between using bit.Int and giving up the performance advantages of code specialized to 2-word or 4-word integers and signed or unsigned arithmetic specifically, or writing a manually-specialized arithmetic package that may not benefit from the architecture-specific underlying optimizations that big.Int does without a lot of additional effort and code maintenance.

With non-type compile-time parameters to generics, the math/big package could support a variation of big.Int compile-time configurable at compile time and specializable to a particular bit width and/or signedness configuration. For example:

type GenericInt(const bits int, signed Signedness) struct { ... }

type Signedness int
const (
    SignBit Signedness = iota, // default: separate sign bit
    Unsigned,                  // no sign bit, unsigned values only
    TwosComplement,            // topmost integer bit is sign bit
)

Configuring GenericInt with bits == 0 would allow its length to vary at runtime as in big.Int, and setting signed == SignBit would similarly configure it to keep a sign bit stored separately from the significant integer bits as in big.Int. Thus, the configuration GenericInt(0, SignBit) would be equivalent to the current big.Int. The internal implementation of GenericInt would of course have a variety of internal tests and dependencies on the bits and signed, but a specializing compiler would generally resolve and optimize away these tests at compile time.

If Go 2 could allow generic and non-generic forms of the same identifier without getting confused, then GenericInt could effectively replace big.Int, with the non-parameterized Int just representing the default configuration of the generic Int:

type Int(const Bits int, signed Signedness) struct { ... }

type Int Int(0, SignBit)

Specialization might have storage and garbage collection efficiency benefits, which may be significant. With implementation care, for example, configurations of GenericInt for a fixed number of bits and Unsigned or TwosComplement mode could internally use a fixed-length array with no space overhead. For example, an Int(128, Unsigned) or an Int(128, TwosComplement) would always take exactly 128 bits of storage and never cause allocations.

Compile-time configurable big integers might also be an element of a clean solution to the problem of providing constant-time big integers for cryptography. Go 2 might, for example, reasonably guarantee guarantee that operations on a big.Int configured with all parameters fixed at compile-time contain no control-flow that depends on data at runtime. Alternatively, since expensive operations such as modular exponentiation can often be done more efficiently when constant-time operation is not required (e.g., for verifying rather than creating digital signatures), constant-time operation might be a separate compile-time parameter to big.Int.

To be clear, this is not a specific proposal at the moment that big.Int should be generalized in this particular (or any) way. This is merely an example of how types like big.Int could potentially be made configurable and specializable at compile time if Go 2 generics support non-type generic parameters. The following examples should be taken in similar spirit.

Compile-time configurable big floats

The same principles apply naturally to big.Float, where other natural configuration options such as mantissa precision and rounding mode may naturally apply in addition to signedness.

While Go natively supports only 32-bit and 64-bit IEEE floating point, compile-time configuration parameters to a generic big.Float could provide reasonably-efficient, compile-time specialized implementations of the other binary floating-point formats standardized by IEEE 754-2008, such as 16-bit, 128-bit, and 256-bit floating-point numbers.

Many applications typically use only one floating-point rounding mode, and a great deal of internal control-flow complexity in big.Float is dedicated to testing the rounding mode and handling all of the cases. Another large part of the internal complexity is dedicated to handling sign bits and zeros in all combinations. An application that, for example, needs arbitrary- or fixed-precision floating-point numbers that are always positive and processed with only one rounding mode, for example, could configure a generic big.Float for positive-only operation with only that rounding mode, obtaining a much more efficient compile-time-specialized version with a tiny fraction of the runtime conditionals and branches that the general big.Float contains.

While the hardware branch prediction units of modern processors of course already mitigate some of the costs of these numerous internal branches by “learning” which direction a branch typically follows, appropriately-specialized versions of code such as big.Float would place much less pressure on hardware branch prediction — leaving that branch prediction cache space for effective use by the code calling big.Float — at a cost, of course, of code size in applications that use multiple configurations of big.Float.

Compile-time configuration structures

From a software engineering perspective, introducing compile-time configuration options to generics in an incremental, backward-compatible way would be facilitated if Go 2 were also enhanced to support const structs. Go already supports struct value literals, which are effectively constant structs anyway; the addition would merely to be to allow struct literals to to be used in const declarations and generic parameter lists.

In this way, compile-time-configurable generics could simply take an extensible Config structure as their one compile-time parameter. Such a compile-time Config struct for big.Float might look something like this:

type FloatConfig struct {
    MaxPrec int,      // Mantissa precision in bits, 0 for variable
    Nonzero bool,     // Zero values disallowed
    Unsigned bool,    // Negative values disallowed
    Mode RoundngMode, // Fixed rounding mode, Any for variable
    _ struct{},       // Ensure extensibility with future parameters
}

type Float(const config FloatConfig) struct { ... }
type Float Float(FloatConfig{}) // default configuration

There are a wide variety of circumstances in which such compile-time configurability and specialization may be useful. More algorithmic choices and optimizations are often available when the data being processed is known to have certain properties; compile-time configuration parameters to generics may be used to signal to libraries in an extensible way that the data has such properties and that relevant optimizations may be activated.

For example, many graph algorithms and optimizations work only when the graph is known to be undirected (two-way edges), or when all edge weights are known to be positive, or when the graph is known to be directed acyclic, or a tree, or fast mixing. Generic graph algorithm libraries could use declarative compile-time parameters via Config structures to specialize their general algorithms to special cases such as these. Matrix and linear algebra operations can often be optimized considerably if the matrix is known to be upper- or lower-triangular or to have other properties the client might declare to enable specialization. As mentioned above, cryptographic algorithms and arithmetic can often be optimized in situations where the data being operated on is known to be non-sensitive so that arithmetic need not be constant-time.

Are These Like C++ const Parameters?

No. C++ allows programmers to attach the const keyword to individual parameters (and even to individual pointer-indirection levels within a parameter) in order to declare the contents of a run-time parameter to be read-only. Experience has shown that that use of const leads to insane complexity, and still never quite gets you what you actually want, due to the complex interactions with pointer indirections and mutable types.

The use of the const keyword proposed here applies to entire parameter lists, not to individual parameters or components of parameters or types, and it declares all the parameters to be completely evaluated and bound to constants at compile time as part of generic instantiation. We’re not using const here to try and tweak run-time parameters to be (unreliably) read-only, as in C++. Instead we’re using const to declare that the entire parameter list is to be evaluated and bound to constant actuals at compile-time and, at least conceptually if perhaps not always in implementation, to disappear entirely at runtime through generic instantiation.

Are We Metaprogramming Yet?

I respect and agree with the current Go 2 Generics proposal’s desire to avoid the complexity of the kinds of metaprogramming that C++ templates support, not to mention the risk of a source program accidentally or deliberately making the compiler run forever or diverge. It might be claimed that allowing non-type parameters to generics constitutes support for metaprogramming, compromising that philosophy.

To such a claim, however, I would argue that Go already includes some (albeit extremely restricted) support for metaprogramming, such as the const declaration’s ability to evaluate an expression (i.e., run a program!) at compile time. And the current generics proposal already inherently adds the still-limited “metaprogramming” functionality of “calling” parameterized “functions” (generics) at compile time to produce multiple specializations or instantiations of the same code. The important question is not so much whether we’re doing metaprogramming: we are anyway, inevitably. The question is what the right model and set of constraints is.

Given the fact that the Go language already has considerable machinery for dealing with compile-time constants of a variety of types, I don’t see any reason to believe that supporting non-type compile-type parameters to generics will somehow launch Go on an inevitable slide toward the template insanity of C++. The rules for declaring and invoking generics in Go can and should ensure that the compiler can decide not just in finite time, but quickly, whether a proposed generic instantiation is legally evaluable at compile time. A lot of the machinery to do so (e.g., constants) is already there.

Conclusion

Allowing the compile-time parameter lists of generics to include non-type constant parameters as well as type parameters could substantially increase the power of the generics mechanism. Non-type compile-time parameters to generics could enable users to obtain a lot of the desirable combination of code efficiency and conciseness that programmers often want from macro (or hygenic macro) facilities, for example. A clean syntactic distinction between compile-time (const ...) and run-time (...) parameter lists will enable programmers to maintain a clear understanding of what will be evaluated at compile-time versus run-time and avoid performance surprises, regardless of whether those parameters happen to be types or non-types.

Even if it is decided that Go 2 should initially support only type parameters to generics, however, considerations of “future-proofing” and maintaining maximum flexibility alone still seem to favor the adoption of a syntax and semantics that does not “bake in” forever an unchangeable assumption that compile-time parameters are always types while run-time parameters are always non-types. Adopting a syntax like (const T1, T2 type) for compile-time parameters instead of (type T1, T2) keeps the syntax focused on what’s fundamentally important, namely that the parameters to generics are bound to constants at compile time. This approach also maintains greater linguistic consistency with existing declaration styles, and avoids painting the language into an evolutionary corner it may not escape, even if generics initially support only type parameters.

Updated 6-August-2019 with the section on example uses.



Bryan Ford