What are Generics?

Generic programming is a style or paradigm of computer programming. Generics allow programmers to write code using types that are specified later, which are then instantiated when the code is used.

Basic Usage of Generics in Golang

Examples

Map Operation

package main

import (
	"fmt"
)

func mapFunc[T any, M any](a []T, f func(T) M) []M {
	n := make([]M, len(a), cap(a))
	for i, e := range a {
		n[i] = f(e)
	}
	return n
}

func main() {
	vi := []int{1, 2, 3, 4, 5, 6}
	vs := mapFunc(vi, func(v int) string {
		return "<" + fmt.Sprint(v * v) + ">"
	})
	fmt.Println(vs)
}

Min Max Functions

package main

import (
	"fmt"
)

type ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr | ~float32 | ~float64 | ~string
}

func max[T ordered](a []T) T {
	m := a[0]
	for _, v := range a {
		if m < v {
			m = v
		}
	}
	return m
}

func min[T ordered](a []T) T {
	m := a[0]
	for _, v := range a {
		if m > v {
			m = v
		}
	}
	return m
}

func main() {
	vi := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	result := max(vi)
	fmt.Println(result)

	vii := []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"}
	result2 := min(vii)
	fmt.Println(result2)
}

Set

// Package sets implements sets of any comparable type.
package sets

// Set is a set of values.
type Set[T comparable] map[T]struct{}

// Make returns a set of some element type.
func Make[T comparable]() Set[T] {
	return make(Set[T])
}

// Add adds v to the set s.
// If v is already in s this has no effect.
func (s Set[T]) Add(v T) {
	s[v] = struct{}{}
}

// Delete removes v from the set s.
// If v is not in s this has no effect.
func (s Set[T]) Delete(v T) {
	delete(s, v)
}

// Contains reports whether v is in s.
func (s Set[T]) Contains(v T) bool {
	_, ok := s[v]
	return ok
}

// Len reports the number of elements in s.
func (s Set[T]) Len() int {
	return len(s)
}

// Iterate invokes f on each element of s.
// It's OK for f to call the Delete method.
func (s Set[T]) Iterate(f func(T)) {
	for v := range s {
		f(v)
	}
}

Trying it Out

Current State of Golang Types and the Significance of Generics

Currently

interface

Drawbacks: Type casting, lack of compile-time constraints.

package main

import "fmt"

func printStr(x interface{}) {
	value, ok := x.(string)
	if !ok {
		fmt.Println("It's not ok for type string")
		return
	}
	fmt.Println("The value is ", value)
}

func main() {
	printStr(123)
}
// It's not ok for type string

Writing Separately for Different Types

Drawbacks: API and code implementation are not clean, large workload, etc.

Examples: sort, math in the current standard library.

Code Generation

Drawbacks: Need to learn third-party code generation tools, go:generate, AST, etc., not universal.

Example:

https://github.com/cheekybits/genny

package gogenerate

import "github.com/cheekybits/genny/generic"

//go:generate genny -in=$GOFILE -out=gen-$GOFILE gen "KeyType=string,int ValueType=string,int"

type KeyType generic.Type
type ValueType generic.Type

type KeyTypeValueTypeMap map[KeyType]ValueType

func NewKeyTypeValueTypeMap() map[KeyType]ValueType {
	return make(map[KeyType]ValueType)
}

Significance of Official Go Generics

  • Generic operations and type constraints
  • Functional programming
  • Simplifying implementation of standard and third-party libraries

………

History of Golang Generics Development

DescriptionTimeAuthor
[Type Functions]2010Ian Lance Taylor
Generalized Types2011Ian Lance Taylor
Generalized Types v22013Ian Lance Taylor
Type Parameters2013Ian Lance Taylor
go:generate2014Rob Pike
First Class Types2015Bryan C.Mills
Contracts2018Ian Lance Taylor, Robert Griesemer
Contracts2019Ian Lance Taylor, Robert Griesemer
Redundancy in Contracts(2019)’s Design2019Ian Lance Taylor, Robert Griesemer
Constrained Type Parameters2020Ian Lance Taylor, Robert Griesemer
Featherweight Go2020Ian Lance Taylor, Robert Griesemer
Merged into master, Go 1.18 released, Standard Library improvements etc.2021 - 2022

Golang Generics Implementation Principles

Loans from other languages

Generics Implementation in Different Languages

boxing VS monomorphization

img

The Dilemma of Generics

https://research.swtch.com/generic

  • Burden on Programmers: e.g., C, increases programmer burden, requires convoluted implementations, but doesn’t increase language complexity.
  • Burden on Compiler: e.g., C++, increases compiler burden, potentially generating a lot of redundant code; duplicate code needs compiler discretion to remove, compiled files might vary largely.
  • Burden on Execution Time: e.g., Java, boxes everything into Objects, performing type erasure. Although this reduces code redundancy and space, boxing/unboxing operations reduce code efficiency.

Go

Keith H. Randal’s three proposals:

Generics implementation - Dictionaries

Compile-time instantiation of dictionaries, where the dictionary contains type information instantiated for type parameters.

Generics implementation - Stenciling

Template generation, generating an independent set of code for each instantiated type.

Generics implementation - GC Shape Stenciling

Hybrid implementation. Types with the same shape share the same code, using dictionaries to distinguish different behaviors of types.

The shape of a type refers to how it appears to the memory allocator/garbage collector, including size, required alignment, and which parts of the type contain pointers.

References

Official Go and Community Resources:

https://go.dev/doc/go1.18

https://go.dev/doc/tutorial/generics

https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md

https://go.dev/blog/generics-proposal

https://go.dev/blog/generics-next-step

https://go.dev/blog/go2draft

https://go.dev/blog/why-generics

https://github.com/golang/proposal/blob/master/design/generics-implementation-dictionaries.md

https://github.com/golang/proposal/blob/master/design/generics-implementation-stenciling.md

https://github.com/golang/proposal/blob/master/design/generics-implementation-gcshape.md

Usage examples, article analysis, etc.:

https://github.com/mattn/go-generics-example

https://colobu.com/2021/08/30/how-is-go-generic-implemented/

https://coolshell.cn/articles/21615.html

https://draveness.me/whys-the-design-go-generics/

https://taoshu.in/go/go-generics-design.html

https://research.swtch.com/generic

https://thume.ca/2019/07/14/a-tour-of-metaprogramming-models-for-generics/