Go: Example Types as Contracts

Summary 

The sticking point with adding parametric polymorphism to Go is how to specify which type(s) are allowed to be used as type parameters. Contracts are a good way.  A simpler way is to use example types as detailed below. I believe this would make creating generic functions/datatypes simpler and easier to fathom but with the same benefits as contracts. 

Introduction

I think the 2019 Contracts Draft Design is great. I would be more than happy if it were implemented, but there are some who think the use of contracts could be simplified or avoided and maybe they are right. 

[Personally, I have been using C++ templates for more than 20 years and am happy with having no way to specify constraints on type parameters. (That is C++ (before Concepts) leaves it to the compiler to at some point detect if a specific type does not provide a capability required by a type parameter.) But I concede that even the best C++ compilers produce tedious (but ultimately decipherable) error messages and this is just not acceptable for Go where getting code to build is much much easier than C++ and other languages.  Moreover, as pointed out in the Draft Design, a mechanism such as contracts can make code more resilient by preventing a change to a generic function/type having an unintended change to the type parameter requirements and consequently breaking distant code.]

BTW From now on I will use the term generic as a shorthand for parametric polymorphism.

Go is renowned for making things simple, so my approach was to look at how I (and others) use "generics" in other languages then look at how to make that process as simple as possible. In my experience, generic functions and datatypes are generally created in a vanilla (non-generic) version first, then converted.  In other words rather than starting with a type parameter off the bat, you start with a simple "example" type first, get it working, then convert the example type to a type parameter.

Using Example Types

My proposal is to stick with the example type in Go and just indicate that it can be replaced with other types, as long as they have the same capabilities.  Of course, it's not that simple, but I will address the issues shortly. 

First, a simple example will help.  Let's start with the most obvious generics example – a function to find the minimum value.  Here is the Go code using int. 

func Min(first int, rest ...int) (retval int) {
  retval = first
  for _, v := range rest {
    if v < retval {
      retval = v
    }
  }
  return
}

  

To convert we make one small change to indicate that int is a type parameter.  Thence anywhere int is used it is replaced with the type of the type parameter. 

func Min(type int)(first int, rest ...int) (retval int) {
  retval = first
  for _, v := range rest {

    if v < retval {

      retval = v

    }

  }

  return 

}

  

Now you can use Min() with any integer type like rune or uint64. 

  

The first problem you will probably have already seen is that you may need to use an actual int in the code and not have it take on the generic type.  To do this (and make the code more resilient to changes) you can define a new type. 

type minT int
func Min(type minT)(first minT, rest ...minT) (retval minT) {
  retval = first
  for _, v := range rest {

    if v < retval {

      retval = v

    }

  }

  return 

}

Note that by convention you might be inclined to use a name for the type of T - but something like minT is safer as it is not exported and is less likely to conflict with other uses of generics in the package. 

New Orderable Type 

Now the only reason we use int as the "example type" in the generic Min() function is so we can test the order of values, using the less than operator (<) in this case.  But strings and floating point types also support less than.  We should be able to get a minimum value for those too.  That is why I propose adding a new (non-instantiable) type to the language called orderable.  Now Min() can work with strings too. 

  

func Min(type orderable)(first orderable, rest ...orderable) (retval orderable) {
  retval = first
  for _, v := range rest {

    if v < retval {

      retval = v

    }

  }

  return 

}

Note that you can't declare a variable of type orderable except in a generic function or type that uses an orderable type parameter. 

The compiler knows what types support ordering so this approach will adapt (unlike the 2019 Contracts Draft Desing I believe) to future language changes - for example if an int128 type is added or if ordering (<, >=, etc) is later extended to other types such as some subset of structs. 

We might also want to hide the public name of this new type in the generics package, to avoid polluting the global namespace and possibly introducing conflicts with existing code. In other words the public type would be generics.Orderable to hide the actual type (possibly with a name like __orderable). 

Required Methods 

Another important requirement for a type parameter is that it implements particular method(s).  Here we demonstrate the common example of a function to convert a slice to a slice of strings.  We need to ensure that the function is only called using a slice of a type that implements the String() method. 

type stringer struct {} 
func (stringer) String() string { return "" } 

func Stringify(type stringer)(s []stringer) (retval []string) { 
    for _, v := range s { 
        retval = append(retval, v.String()) 
    }
    return 
}

  

Here stringer is the "example type" for the generic Stringify() function.  One ugliness is that we have to implement a dummy String() method on the stringer type, but it doesn't really do much and the compiler would not need to generate any code for this function since it is never called.

New Any Type 

The above stringer type is based on an empty struct on the assumption that this can represent any type in Go.  However, now that I think about it, this may preclude using Stringify() with a slice of some types.  Maybe we also need to add a type to the language that can stand in for any type. 

type stringer generics.Any 
func (stringer) String() (retval string) { }

New Comparable Type 

Comparing types for equality is a little complicated in Go.  Even the 2019 Contracts Draft Design proposes a special predefined contract called "comparable" (which, I assume, is intended to be handled specially by the compiler).  Similarly, in my proposal we have a new Go type called generics.Comparable that includes all types that can be compared. (A cursory explanation is that slice, map, function types are non-comparable plus any array/struct/interface types that contain such non-comparable type(s).) 

Here is an example to demonstrate using the example from the 2019 Contracts Draft Design:

type indexT generics.Comparable 

func Index(type indexT)(s []indexT, x indexT) int { 
    for i, v := range s { 
        if v == x { 
            return i 
        } 
    } 
    return -1 
}

Types using Type Parameters 

I have unintentionally concentrated on generic functions above.  Just for completeness I present a generic type as well – the ubiquitous pair.

type pairT1 generics.Any 

type pairT2 generics.Any 

type pair(type pairT1, pairT2) struct { 
    first  pairT1
    second pairT2
}

This also demonstrates how to have more than one type parameter using the same example type. That is, T1 and T2 use the same example type but can be instantiated with different actual types.

Mutually Referencing Type Parameters 

  

Of course, a function or type can have multiple type parameters, which can refer to each other. Again using an example from the 2019 Draft Design.

type node generics.Any

func (node) Edges() (edges []edge) { return } 

type edge generics.Any 
func (edge) Nodes() (from, to node) { return } 

type Graph(type node, edge) struct { ... } 
func New(type node, edge)(nodes []node) *Graph(node, edge) { ... } 
func (g *Graph(node, edge)) ShortestPath(from, to node) []edge { ... }   

Further Constraints 

In my proposal certain types when used as a type parameter can stand in for any type that has the same capabilities. So int can stand in for all integer types. However, we may need further restrictions on allowed types for a type parameter such as only integers of at least 16 bits.  In this case perhaps int16 could mean any integer of 16 bits or more and uint could mean any unsigned integer, etc.

If this does not work well perhaps allow a new generic type to be defined from a set of existing types.  This is similar to specifying a list of types in a contract in the 2019 Contracts Draft Design.

package generics

type UInt16 {uint16, uint32, uint64}  // maybe uint128 later
type SInt16 {int16, int32, int64}
type Int16 {int16, int32, int64, uint16, uint32, uint64}

type Int16 {UInt16, SInt16}

Embedding

As in the 2019 Draft Design example types can "embed" other types using the existing type embedding mechanism.

type printStringer struct{stringer} // embed stringer type from above

func (printStringer) Print() {}

  

Alternatively you can just extend the existing type by adding a method.

type printStringer stringer

func (printStringer) Print() {}

Conclusion

I actually wrote a draft of this proposal late last year after hearing Rob Pike's talk at the Sydney Go Meetup (October 2018?) about the 2018 Draft Designs for Go 2.  Unfortunately, I never found the time to complete it, and was hoping that someone else would put forward a similar proposal.  (The most similar proposal I have seen is Matt Sherman's [https://clipperhouse.com/go-generics-typeclasses/].) 

Now that I have reviewed and polished this proposal I think it's rather similar to the 2019 Contracts Draft Design but replaces the contracts with something more familiar and easier to grasp. The new contracts syntax is an improvement on the 2018 Contracts Draft Design but is still confusing - a contract with methods looks much like an interface but must also include the receiver type for each method which looks out of place.

This proposal makes it easy to write functions and datatypes in a non-generic version and convert them to generic ones. Please post a comment below if I have missed something.