(half-baked) Interface constrained generics proposal for Go

go-generics.md

Go generics proposal

This proposes a constraint-based generics system for Go, similar to Swift. Constraints are expressed as interfaces.

• Extend functions and types to support parametric types.
• Extend builtin types so that they (virtually) implement generic interfaces. The advantage of doing this is that generic operations can treat user types and builtin types consistently. Internally the compiler may choose to translate interface calls on builtin types. This would require modelling all builtin types and operations in terms of interfaces. On the upside, there aren't that many as Go is a simple language. eg.
  • []string would implement the Iterable.<K, V> interface via a virtual Iterator() Iterator.<int, string> method.
  • All types that are hashable would implement the Hashable interface.
  • int, float64, string etc. would implement the Addable.<T> interface (among others).
• Controversial: change builtin operators/functions to act on these interfaces. eg. append(s, v...) would become append.<T, S:Appendable.<T>>(S, T...), a + b would become a.Add(b), and so on.
  • All types used in expressions or statements must be declared with appropriate type constraints.
• Type constraints mean that recursive whole-function type-inference is not necessary, at the cost of some typing for the developer.
• The default constraint, if not provided, is Any, analogous to interface{}.
• If a constraint has a single type parameter its type will be inferred from the owning type. eg. T:Addable.<T> can be expressed as T:Addable.

Pro's:

• It is very clear what types will be accepted.
• Should be fast to type check, similar to existing interface checks.
• Use of interfaces for type constraints is consistent with the rest of Go.
• Syntax is familiar to users from other languages, C++, Java, Swift.
• Syntax is, I believe, unambiguous: TypeName.<T0[:Interface], T1[:Interface], ...>. The . disambiguates this from a < b.
• Syntax is also somewhat analogous to type coercion (value.(Interface)), though a bit strained.
• Syntax is consistent across all usages (declaration, invocation).

Con's:

• Declaring generic types can be verbose, though it deliberately restricts type constraints to a single interface.
• Without operator overloading (particularly for range), generic code can be fairly verbose. eg. iter := i.Iterator(); for { k, v, end := iter.Next(); if end { break } } vs. for k, v := range i {}

type Lessable.<T> interface {
  Less(other T) bool
}

type LessableType int

func (l LessableType) Less(other LessableType) bool {
  return l < other
}

type Sizeable interface {
  Size() int
}

// The Addable interface is implemented by builtin types that support the + operator.
type Addable.<T> interface {
  Add(other T) T
}

type Numeric.<T> interface {
  Addable.<T>
  Subtractable.<T>
  Multipliable.<T>
  Divisible.<T>
  // etc.
}

func Add.<T:Addable>(a, b T) T {
  return a.Add(b)
}

func TestAdd(t *testing.T) {
  assert.Equal(t, "ab", Add("a", "b"))
  assert.Equal(t, 3, Add(1, 2))
}

type Iterator.<K, V> interface {
  // Next entry or nils.
  Next() (*K, *V)
}

type Iterable.<K, V> interface {
  Iterator() Iterator.<K, V>
}

type Hashable interface {
  Hash() int
}

// Illustrates composition of parametric interfaces as well as type constraints.
type Map.<K:Hashable, V> interface {
  Sizeable
  Iterable.<K, V>

  Get(K) (V, bool)
  Set(K, V)
  Delete(K)
}

// Invalid: K must be Hashable.
type IntMap.<K> map[K]int

// Valid.
type IntMap.<K:Hashable> map[K]int

intMap := IntMap.<string>{}

type Slice.<E> interface {
  Sizeable
  Iterable.<int, E>
  Hashable

  Get(i int) E
  Set(i int, e E)
  Slice(start, end int) Slice.<E>
  Append(...E) Slice.<E>
}

type IntSlice Slice.<int>

// Okay.
var slice Slice.<int> = []int{}
// Not okay.
var other []int = slice

Example mapping functions:

// Map one slice to another via a function.
func MapSlice.<T, U>(s []T, f func(T) U) []U {
  out := []U{}
  for _, e := range s {
    out = append(out, f(e))
  }
  return out
}

// Map a slice to a map using a keying function.
func MakeMap.<K:Hashable, V>(s []V, f func(V) K) map[K]V {
  out := make(map[K]V{}, len(s))
  for _, v := range s {
    out[f(v)] = v
  }
  return out
}

func test() {
  a := []string{"hello", "world"}
  // Slice of string lengths.
  b := MapSlice(a, len)

  c := []*http.Request{}
  // Map of URL to corresponding request.
  d := MakeMap(c, func(r *http.Request) string { return r.URL.String() })
}

People expect parameterized functions to be fast. They do not want a reflection based implementation in all cases. The question is how to support that without excessively slowing down the compiler.

People want to be able to write simple parameterized functions like Sum(v []T) T, a function that returns the sum of the values in the slice v. They are prepared to assume that T is a numeric type. They don’t want to have to write a set of methods simply to implement Sum or the many other similar functions for every numeric type, including their own named numeric types.

// Builtin Addable interface.
type Addable.<T> interface {
  Add(T) T
}

func Sum.<T:Addable>(v []T) T {
  var out T
  for _, e := range v {
    out = out.Add(e)
  }
  return out
}

A type-safe set and a couple of useful operations:

// SetType is the interface for sets.
type SetType.<T:Hashable> interface {
  Iterable.<T, bool>
  Add(T)
  Remove(T)
  Contains(T) bool
}

// Set is a map-based SetType implementation.
//
// Note that map[T]bool already complies with Iterable.<T, bool>,
// so that interface does not have to be implemented.
type Set.<T:Hashable> map[T]bool

// SetOf creates a new Set from the given elements.
//
// eg. ints := SetOf(1, 2, 3, 4) // == Set.<int>{1: true, 2: true, 3: true, 4: true}
func SetOf.<T>(elems ... T) Set.<T> {
  out := Set.<T>{}
  for _, e := range elems {
    out.Add(e)
  }
  return out
}

func (s Set.<T>) Add(v T)           { s[v] = true }
func (s Set.<T>) Unset(v T)         { delete(s, v) }
func (s Set.<T>) Contains(v T) bool { return s[v] }

func Union.<T>(a, b SetType.<T>) SetType.<T> {
  out := Set.<T>{}
  for v := range a {
    out.Set(v)
  }
  for v := range b {
    out.Set(v)
  }
  return out
}

func Intersection.<T>(a, b SetType.<T>) SetType.<T> {
  out := Set.<T>{}
  for v := range a {
    if b.Contains(v) {
      out.Add(v)
    }
  }
  return out
}

Find the index of v1 in s, for any comparable type.

// Equatable types can be compared for equality.
type Equatable.<T> interface {
  Equal(T) bool
}

// Return the index in s of v1, or -1 if not found.
func Find.<T:Equatable>(s []T, v1 T) int {
  for i, v2 := range s {
    if v1.Equal(v2) {
      return i
    }
  }
  return -1
}

A reimplementation of strings.Join() that operates on slices of values that are stringable, not just a slice of strings:

func Join.<T:fmt.Stringer>(a []T, s string) string {
  if len(a) == 0 {
    return ""
  }
  out := a[0].String()
  for _, e := range a[1:] {
    out += s + e.String()
  }
  return out
}

Join a slice of Addable elements with a separator. This will work for builtin types such as bytes, strings, and numeric types, as well as any user type that implements the Addable interface.

func Join.<T:Addable>(a []T, s T) T {
  if len(a) == 0 {
    var out T
    return out
  }
  out := a[0]
  for _, e := range a[1:] {
    out = out.Add(s).Add(e)
  }
  return out
}

An example of a user-type implementing this interface:

type Person struct {
  Name string
  Age int
}

func (p *Person) Add(other *Person) *Person {
  return &Person{
    Name: p.Name + other.Name,
    Age: p.Age + other.Age,
  }
}

A type-safe sort function leveraging the existing stdlib:

type SortableSequence.<T> interface {
  Get(i int) T
  Set(i int, v T)
  Size() int
}

// Sort a collection using the element's natural ordering.
func Sort.<T:Comparable, S:SortableSequence>(s S) {
}

// Sort a collection with a comparison function.
func SortWith.<T, S:SortableSequence>(s S, less func(T, T) bool) {
}

Hash table that fully implements the Map.<K, V> interface:

type HashableEquatable.<T> interface {
  Hashable
  Equatable.<T>
}

type bucket.<K:HashableEquatable, V> struct {
  next *bucket
  key K
  val V
}

// This completely implements the Map.<K, V> interface.
type HashMap.<K:HashableEquatable, V> struct {
  buckets []bucket.<K, V>
  entries int
}

// h := hashmap.New.<int, string>()
func New.<K:HashableEquatable, V>() *HashMap.<K, V> {
  return &HashMap{buckets: make([]bucket.<K, V>, 16)}
}

func (h *HashMap.<K, V>) Get(key K) (val V, found bool) {
  h := key.Hash() % len(h.buckets)
  for b := h.buckets[h]; b != nil; b = b.next {
    if key.Equal(b.key) {
      return b.val, true
    }
  }
  return
}

func (h *HashMap.<K, V>) Set(key K, val V) {
  // ...
}

func (h *HashMap.<K, V>) Delete(key K) {
  // ...
}

func (h *HashMap.<K, V>) Size() int {
  // ...
}

// Implements the Iterator.<K, V> interface.
type iterator.<K:HashableEquatable, V> struct {
  bucket *bucket.<K, V>
}

func (i *iterator.<K, V>)  Next() (K, V, bool) {
  if i.bucket == nil {
    // TODO: Find a better way to express empty values in generics.
    var k K
    var v V
    return k, v, false
  }
  k, v := i.bucket.key, i.bucket.val
  i.bucket = i.bucket.next
  return k, v, true
}

// Implements the Iterable.<K, V> interface.
func (h *HashMap.<K, V>) Iterator() Iterator.<K, V> {
  // Type parameters are inferred from struct field values.
  return &iterator{h.buckets[0]}
}

func test() {
  h := New.<int, string>()
  // h[1] = "hello"
  h.Insert(1, "hello")
  // v, ok := h[1]
  v, ok := h.Get(1)
}

An actor system:

type Actor.<Message, Result> interface {
  Receive(Message) Result
  Stop()
}

// Message and corresponding response sent to an actor.
type envelope.<Message, Result> struct {
  stop bool
  message Message
  result chan Result
}

// Mailbox for an actor.
type Mailbox.<Message, Result> struct {
  env chan envelope.<Message, Result>
}

// Tell sends a message to the actor but does not wait for a response.
func (m *Mailbox.<Message, Result>) Tell(message Message) {
  go func() {
    m.env <- envelope{message: message, result: make(chan Result, 1)}
  }()
}

// Ask synchronously sends a message to the actor, waits for a response, and returns it.
func (m *Mailbox.<Message, Result>) Ask(message Message) Result {
  result := make(chan Result)
  m.env <- envelope{message: message, result: result}
  return <-result
}

// Stop the actor.
func (m *Mailbox.<Message, Result>) Stop() {
  m.env <- envelope{stop: true}
}

type MailboxFunc.<Message> func(Message)

func (m MailboxFunc.<Message>) Deliver(message Message) {
  m(message)
}

// Start an actor and return its mailbox.
func Start.<Message, Result>(actor Actor.<Message, Result>) Mailbox.<Message, Result> {
  mbox := Mailbox{make(chan envelope.<Message, Result>)}
  // Start actor main loop.
  go func() {
    for env := range mbox.env {
      if env.stop {
        actor.Stop()
        break
      }
      env.result <- actor.Receive(Message)
    }
  }()
  return mbox
}

type Hello struct {
  Who string
}

type HelloActor struct {}

func (h *HelloActor) Receive(hello *Hello) string {
  return fmt.Sprint("hello", hello.Who)
}


mbox := Start(&HelloActor{})
greeting := mbox.Ask(&Hello{"Bob"})
fmt.Println(greeting)

In the final call to Start() the type inferencer kicks in and parametric types do not have to be specified.

Here is some pseudocode for the inferencer:

# Final map of parametric type to inferred concrete type.
inferred_type_parameters = {}

for iface_method in Actor.methods
  impl_method = HelloActor.methods[method.name]
  if not impl_method:
    error("HelloActor does not have method %s", iface_method)

  if len(impl_method.args) != len(iface_method.args)
    error("HelloActor.%s does not have the same number of arguments", impl_method)

  for arg in iface_method.args
    if arg.type.is_parameteric_type
      if arg.type.name not in inferred_type_parameters
        inferred_type_parameters[arg.type.name] = impl_method.args[arg.index].type.name
      else if inferred_type_parameters[arg.type.name] != impl_method.args[arg.index].type.name
        error("HelloActor.%s argument %i should be of type %s to conform to Actor", impl_method, arg.index, arg.type)