Génériques

Les génériques, ou plus académiquement le polymorphisme paramétré (Parameterized Polymorphism), désignent la réutilisation et la flexibilité du code réalisées par la paramétrisation des types. Dans de nombreux langages de programmation, le polymorphisme paramétré est un concept important qui permet aux fonctions ou aux structures de données de traiter des données de différents types sans avoir à écrire du code séparé pour chaque type. Initialement, Go n'avait pas de génériques, mais depuis sa création, la demande la plus forte de la communauté pour Go était l'ajout des génériques. Finalement, le langage Go a ajouté le support des génériques dans la version 1.18 en 2022.

Conception

Lors de la conception des génériques, le langage Go a considéré les solutions suivantes :

• stenciling : monomorphisation, typique de C++ et Rust, qui génère un modèle de code pour chaque type utilisé. Cette approche offre les meilleures performances, sans aucun coût d'exécution, équivalent à un appel direct. L'inconvénient est qu'elle ralentit considérablement la vitesse de compilation (par rapport à Go lui-même) et gonfle le volume du binaire compilé car du code est généré pour chaque type.

• dictionaries : cette approche ne génère qu'un seul ensemble de code et crée un dictionnaire de types stocké dans le segment de données en lecture seule lors de la compilation. Il stocke toutes les informations de types qui seront utilisées, et lors de l'appel de fonction, les informations de types sont consultées via le dictionnaire. Cette méthode ne ralentit pas la vitesse de compilation et ne gonfle pas le volume, mais entraîne d'énormes coûts d'exécution, les performances des génériques sont médiocres.

Ces deux méthodes représentent deux extrêmes. La solution d'implémentation finalement choisie par le langage Go est Gcshape stenciling, un compromis. Pour les types de même forme mémoire (la forme est déterminée par l'allocateur de mémoire), la monomorphisation est utilisée pour générer le même code. Par exemple, type Int int et int sont en fait le même type, donc ils partagent le même code. Cependant, pour les pointeurs, bien que tous les types de pointeurs aient la même forme mémoire (par exemple *int et *Person ont la même forme mémoire), ils ne peuvent pas partager le même code car les dispositions mémoire des types cibles lors de la déréférencement sont complètement différentes. Pour cette raison, Go utilise également un dictionnaire pour obtenir les informations de types à l'exécution, donc les génériques en Go ont également un coût d'exécution.

Introduction

Commençons par un exemple simple.

func Sum(a, b int) int {
   return a + b
}

C'est une fonction très simple qui additionne deux entiers de type int et retourne le résultat. Si on veut passer deux nombres flottants de type float64 pour les additionner, ce n'est évidemment pas possible car les types ne correspondent pas. Une solution consiste à définir une nouvelle fonction :

func SumFloat64(a, b float64) float64 {
  return a + b
}

Mais alors, si on développe une boîte à outils mathématiques pour calculer la somme de deux nombres de tous les types numériques, faudrait-il écrire une fonction pour chaque type ? Évidemment non. On pourrait utiliser le type any avec la réflexion pour juger, comme suit :

func SumAny(a, b any) (any, error) {
  tA, tB := reflect.ValueOf(a), reflect.ValueOf(b)
  if tA.Kind() != tB.Kind() {
    return nil, errors.New("type non correspondant")
  }

  switch tA.Kind() {
  case reflect.Int:
  case reflect.Int32:
    ...
  }
}

Mais cette écriture est fastidieuse et les performances sont médiocres. La logique de la fonction Sum est toujours la même : additionner deux nombres. C'est là qu'interviennent les génériques. Pourquoi a-t-on besoin de génériques ? Les génériques servent à résoudre les problèmes où la logique d'exécution est indépendante du type. Ce genre de problème ne se soucie pas du type fourni, il suffit d'effectuer l'opération correspondante.

Syntaxe

Les génériques s'écrivent comme suit :

func Sum[T int | float64](a, b T) T {
   return a + b
}

Paramètre de type : T est un paramètre de type. Le type concret du paramètre dépend de ce qui est passé.

Contrainte de type : int | float64 constitue une contrainte de type. Cette contrainte spécifie quels types sont autorisés et limite la portée des types de paramètres.

Argument de type : Sum[int](1,2) spécifie manuellement le type int, int est l'argument de type.

Première utilisation : spécifier explicitement le type à utiliser :

Sum[int](2012, 2022)

Deuxième utilisation : ne pas spécifier le type et laisser le compilateur l'inférer :

Sum(3.1415926, 1.114514)

Voici une tranche générique avec une contrainte de type int | int32 | int64 :

type GenericSlice[T int | int32 | int64] []T

Ici, on ne peut pas omettre l'argument de type lors de l'utilisation :

GenericSlice[int]{1, 2, 3}

Voici une table de hachage générique. Le type de clé doit être comparable, donc on utilise l'interface comparable. La contrainte de type de valeur est V int | string | byte :

type GenericMap[K comparable, V int | string | byte] map[K]V

Utilisation :

gmap1 := GenericMap[int, string]{1: "hello world"}
gmap2 := make(GenericMap[string, byte], 0)

Voici une structure générique avec une contrainte de type T int | string :

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

Utilisation :

GenericStruct[int]{
   Name: "jack",
   Id:   1024,
}
GenericStruct[string]{
   Name: "Mike",
   Id:   "1024",
}

Voici un exemple de paramètre de tranche générique :

type Company[T int | string, S []T] struct {
   Name  string
   Id    T
   Stuff S
}

// ou comme suit
type Company[T int | string, S []int | []string] struct {
  Name  string
  Id    T
  Stuff S
}

Utilisation :

Company[int, []int]{
   Name:  "lili",
   Id:    1,
   Stuff: []int{1},
}

TIP

Dans une structure générique, cette écriture est recommandée :

type Company[T int | string, S int | string] struct {
  Name  string
  Id    T
  Stuff []S
}

SayAble est une interface générique, Person implémente cette interface.

type SayAble[T int | string] interface {
   Say() T
}

type Person[T int | string] struct {
   msg T
}

func (p Person[T]) Say() T {
   return p.msg
}

func main() {
  var s SayAble[string]
  s = Person[string]{"hello world"}
  fmt.Println(s.Say())
}

Interface générique

Les interfaces génériques peuvent fournir une meilleure capacité de contrainte abstraite. Voici un exemple :

func PrintObj[T fmt.Stringer](s T) {
	fmt.Println(s.String())
}

type Person struct {
	Name string
}

func (p Person) String() string {
	return fmt.Sprintf("Person: %s", p.Name)
}

func main() {
	PrintObj(Person{Name: "Alice"})
}

On peut également utiliser une interface non générique comme paramètre de type générique :

func Write[W io.Writer](w W, bs []byte) (int, error) {
	return w.Write(bs)
}

Assertion de type générique

On peut utiliser les génériques pour effectuer des assertions de type sur le type any. Par exemple, la fonction suivante peut faire une assertion sur tous les types :

func Assert[T any](v any) (bool, T) {
	var av T
	if v == nil {
		return false, av
	}
	av, ok := v.(T)
	return ok, av
}

Ensembles de types

Après la version 1.18, la définition d'interface est devenue un ensemble de types (type set). Les interfaces contenant un ensemble de types sont appelées interfaces générales (General interfaces).

An interface type defines a type set

Les ensembles de types ne peuvent être utilisés que pour les contraintes de type dans les génériques, pas pour les déclarations de type, les conversions de type ou les assertions de type. En tant qu'ensemble, un ensemble de types peut être vide, une union ou une intersection. Nous allons expliquer ces trois situations.

Union

Le type d'interface SignedInt est un ensemble de types. L'union des types d'entiers signés est SignedInt, et inversement, SignedInt est leur sur-ensemble.

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

C'est la même chose pour les types de données de base et pour les autres interfaces génériques :

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

type UnSignedInt interface {
  uint8 | uint16 | uint32 | uint64
}

type Integer interface {
  SignedInt | UnSignedInt
}

Intersection

L'ensemble de types d'une interface non vide est l'intersection des ensembles de types de tous ses éléments. En langage simple : si une interface contient plusieurs ensembles de types non vides, alors cette interface est l'intersection de ces ensembles de types. Exemple :

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

type Integer interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type Number interface {
  SignedInt
  Integer
}

L'intersection dans l'exemple est certainement SignedInt :

func Do[T Number](n T) T {
   return n
}

Do[int](2)
DO[uint](2) // ne peut pas être compilé

Ensemble vide

Un ensemble vide est une intersection vide. Dans l'exemple suivant, Integer est un ensemble de types vide :

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

type UnsignedInt interface {
  uint8 | uint16 | uint | uint32 | uint64
}

type Integer interface {
  SignedInt
  UnsignedInt
}

Comme les entiers non signés et les entiers signés n'ont certainement pas d'intersection, l'intersection est un ensemble vide. Dans l'exemple suivant, quel que soit le type passé, la compilation échouera :

Do[Integer](1)
Do[Integer](-100)

Interface vide

L'interface vide est différente de l'ensemble vide. L'interface vide est l'ensemble de tous les ensembles de types, c'est-à-dire qu'elle contient tous les types.

func Do[T interface{}](n T) T {
   return n
}

func main() {
   Do[struct{}](struct{}{})
   Do[any]("abc")
}

Cependant, on utilise généralement any comme paramètre de type générique car interface{} n'est pas esthétique.

Type sous-jacent

Lorsqu'on utilise le mot-clé type pour déclarer un nouveau type, même si son type sous-jacent est inclus dans l'ensemble de types, la compilation échouera toujours lors du passage.

type Int interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type TinyInt int8

func Do[T Int](n T) T {
   return n
}

func main() {
   Do[TinyInt](1) // ne peut pas être compilé, même si son type sous-jacent appartient à l'ensemble de types Int
}

Il y a deux solutions. La première consiste à ajouter ce type à l'union de l'ensemble de types, mais cela n'a pas de sens car TinyInt et int8 ont le même type sous-jacent. Donc il y a une deuxième solution :

type Int interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64 | TinyInt
}

Utiliser le symbole ~ pour représenter le type sous-jacent. Si le type sous-jacent d'un type appartient à cet ensemble de types, alors ce type appartient à cet ensemble de types :

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64
}

Après modification, la compilation réussit :

func main() {
   Do[TinyInt](1) // peut être compilé car TinyInt est dans l'ensemble de types Int
}

Points d'attention

Les génériques ne peuvent pas servir de type de base pour un type

L'écriture suivante est erronée. Le paramètre de type générique T ne peut pas servir de type de base :

type GenericType[T int | int32 | int64] T

Bien que l'écriture suivante soit autorisée, elle n'a pas de sens et peut causer des problèmes de débordement numérique, donc elle n'est pas recommandée :

type GenericType[T int | int32 | int64] int

Les types génériques ne peuvent pas utiliser l'assertion de type

Utiliser une assertion de type sur un type générique ne passera pas la compilation. Les génériques servent à résoudre des problèmes indépendants du type. Si un problème nécessite une logique différente selon les types, il ne faut absolument pas utiliser les génériques, mais plutôt interface{} ou any.

func Sum[T int | float64](a, b T) T {
   ints,ok := a.(int) // non autorisé
   switch a.(type) { // non autorisé
   case int:
   case bool:
      ...
   }
   return a + b
}

Les structures anonymes ne supportent pas les génériques

Les structures anonymes ne supportent pas les génériques. Le code suivant ne passera pas la compilation :

testStruct := struct[T int | string] {
   Name string
   Id T
}[int]{
   Name: "jack",
   Id: 1
}

Les fonctions anonymes ne supportent pas les génériques personnalisés

Les deux écritures suivantes ne passeront pas la compilation :

var sum[T int | string] func (a, b T) T
sum := func[T int | string](a,b T) T{
    ...
}

Mais on peut utiliser des types génériques existants, par exemple dans une fermeture :

func Sum[T int | float64](a, b T) T {
  sub := func(c, d T) T {
    return c - d
  }
  return sub(a,b) + a + b
}

Les méthodes génériques ne sont pas supportées

Les méthodes ne peuvent pas avoir de paramètres de type génériques, mais le receiver peut avoir des paramètres de type génériques. Le code suivant ne passera pas la compilation :

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

func (g GenericStruct[T]) name[S int | float64](a S) S {
   return a
}

Les ensembles de types ne peuvent pas servir d'arguments de type

Toute interface avec un ensemble de types ne peut pas servir d'argument de type.

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

func Do[T SignedInt](n T) T {
   return n
}

func main() {
   Do[SignedInt](1) // ne peut pas être compilé
}

Problèmes d'intersection dans les ensembles de types

Pour les types non interface, l'union de types ne peut pas avoir d'intersection. Par exemple, TinyInt et ~int8 ont une intersection :

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // ne peut pas être compilé
}

type TinyInt int8

Mais pour les types interface, les intersections sont autorisées :

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // peut être compilé
}

type TinyInt interface {
  int8
}

Les ensembles de types ne peuvent pas s'unir directement ou indirectement à eux-mêmes

Dans l'exemple suivant, Floats s'unit directement à lui-même, et Double s'unit à Floats, donc s'unit indirectement à lui-même :

type Floats interface {  // le code ne peut pas être compilé
   Floats | Double
}

type Double interface {
   Floats
}

L'interface comparable ne peut pas être unie à un ensemble de types

De même, elle ne peut pas être unie aux contraintes de types, donc elle est généralement utilisée seule.

func Do[T comparable | Integer](n T) T { // ne peut pas être compilé
   return n
}

type Number interface { // ne peut pas être compilé
  Integer | comparable
}

type Comparable interface { // peut être compilé mais n'a pas de sens
  comparable
}

Les ensembles de méthodes ne peuvent pas être unis à un ensemble de types

Toute interface contenant des méthodes ne peut pas être unie à un ensemble de types :

type I interface {
    int | fmt.Stringer // cannot use fmt.Stringer in union (fmt.Stringer contains methods)
}

Mais elles peuvent faire une intersection, bien que cela n'ait aucun sens :

type I interface {
    int
    fmt.Stringer
}

Utilisation

Les structures de données sont le cas d'utilisation le plus courant des génériques. Nous allons montrer comment utiliser les génériques avec deux structures de données.

File d'attente (Queue)

Implémentons une file d'attente simple avec des génériques. D'abord, déclarons le type de file d'attente. Le type des éléments dans la file peut être arbitraire, donc la contrainte de type est any :

type Queue[T any] []T

Il y a seulement quatre méthodes : Pop, Peek, Push, Size. Voici le code :

type Queue[T any] []T

func (q *Queue[T]) Push(e T) {
  *q = append(*q, e)
}

func (q *Queue[T]) Pop(e T) (_ T) {
  if q.Size() > 0 {
    res := q.Peek()
    *q = (*q)[1:]
    return res
  }
  return
}

func (q *Queue[T]) Peek() (_ T) {
  if q.Size() > 0 {
    return (*q)[0]
  }
  return
}

func (q *Queue[T]) Size() int {
  return len(*q)
}

Dans les méthodes Pop et Peek, on peut voir que la valeur de retour est _ T. C'est l'utilisation de valeurs de retour nommées, mais avec un tiret bas _ pour indiquer qu'elles sont anonymes. Ce n'est pas redondant, c'est pour représenter la valeur zéro générique. Comme on utilise des génériques, lorsque la file est vide, il faut retourner une valeur zéro, mais comme le type est inconnu, il est impossible de retourner un type concret. La méthode ci-dessus permet de retourner la valeur zéro générique. On peut également déclarer une variable générique pour résoudre le problème de la valeur zéro. Pour une variable générique, la valeur par défaut est la valeur zéro de ce type :

func (q *Queue[T]) Pop(e T) T {
    var res T
  if q.Size() > 0 {
    res = q.Peek()
    *q = (*q)[1:]
    return res
  }
  return res
}

Tas (Heap)

Dans l'exemple de la file d'attente ci-dessus, comme il n'y a aucune exigence sur les éléments, la contrainte de type est any. Mais le tas est différent. Le tas est une structure de données spéciale qui peut déterminer la valeur maximale ou minimale en temps O(1), donc il a une exigence sur les éléments : ils doivent être triables. Mais les types triables intégrés sont seulement les nombres et les chaînes. Donc, lors de l'initialisation du tas, il faut passer un comparateur personnalisé. Le comparateur est fourni par l'appelant et doit également utiliser des génériques :

type Comparator[T any] func(a, b T) int

Voici une implémentation simple d'un tas binaire. D'abord, déclarons la structure générique, toujours avec une contrainte any pour pouvoir stocker n'importe quel type :

type Comparator[T any] func(a, b T) int

type BinaryHeap[T any] struct {
  s []T
  c Comparator[T]
}

Implémentation de quelques méthodes :

func (heap *BinaryHeap[T]) Peek() (_ T) {
  if heap.Size() > 0 {
    return heap.s[0]
  }
  return
}

func (heap *BinaryHeap[T]) Pop() (_ T) {
  size := heap.Size()
  if size > 0 {
    res := heap.s[0]
    heap.s[0], heap.s[size-1] = heap.s[size-1], heap.s[0]
    heap.s = heap.s[:size-1]
    heap.down(0)
    return res
  }
  return
}

func (heap *BinaryHeap[T]) Push(e T) {
  heap.s = append(heap.s, e)
  heap.up(heap.Size() - 1)
}

func (heap *BinaryHeap[T]) up(i int) {
  if heap.Size() == 0 || i < 0 || i >= heap.Size() {
    return
  }
  for parentIndex := i>>1 - 1; parentIndex >= 0; parentIndex = i>>1 - 1 {
    // greater than or equal to
    if heap.compare(heap.s[i], heap.s[parentIndex]) >= 0 {
      break
    }
    heap.s[i], heap.s[parentIndex] = heap.s[parentIndex], heap.s[i]
    i = parentIndex
  }
}

func (heap *BinaryHeap[T]) down(i int) {
  if heap.Size() == 0 || i < 0 || i >= heap.Size() {
    return
  }
  size := heap.Size()
  for lsonIndex := i<<1 + 1; lsonIndex < size; lsonIndex = i<<1 + 1 {
    rsonIndex := lsonIndex + 1

    if rsonIndex < size && heap.compare(heap.s[rsonIndex], heap.s[lsonIndex]) < 0 {
      lsonIndex = rsonIndex
    }

    // less than or equal to
    if heap.compare(heap.s[i], heap.s[lsonIndex]) <= 0 {
      break
    }
    heap.s[i], heap.s[lsonIndex] = heap.s[lsonIndex], heap.s[i]
    i = lsonIndex
  }
}

func (heap *BinaryHeap[T]) Size() int {
  return len(heap.s)
}

func NewHeap[T any](n int, c Comparator[T]) BinaryHeap[T] {
	var heap BinaryHeap[T]
	heap.s = make([]T, 0, n)
	heap.Comparator = c
	return heap
}

Utilisation :

type Person struct {
  Age  int
  Name string
}

func main() {
  heap := NewHeap[Person](10, func(a, b Person) int {
    return cmp.Compare(a.Age, b.Age)
  })
  heap.Push(Person{Age: 10, Name: "John"})
  heap.Push(Person{Age: 18, Name: "mike"})
  heap.Push(Person{Age: 9, Name: "lili"})
  heap.Push(Person{Age: 32, Name: "miki"})
  fmt.Println(heap.Peek())
  fmt.Println(heap.Pop())
  fmt.Println(heap.Peek())
}

Sortie :

{9 lili}
{9 lili}
{10 John}

Avec les génériques, des types qui n'étaient pas triables peuvent maintenant utiliser le tas en passant un comparateur. C'est certainement plus élégant et pratique que d'utiliser interface{} pour les conversions et assertions de type.

Pool d'objets

La version originale du pool d'objets ne pouvait utiliser que le type any, et il fallait effectuer une assertion de type à chaque récupération. Avec une simple modification utilisant les génériques, on peut éviter ce travail :

package main

import (
	"bytes"
	"fmt"
	"sync"
)

func NewPool[T any](newFn func() T) *Pool[T] {
	return &Pool[T]{
		pool: &sync.Pool{
			New: func() interface{} {
				return newFn()
			},
		},
	}
}

type Pool[T any] struct {
	pool *sync.Pool
}

func (p *Pool[T]) Put(v T) {
	p.pool.Put(v)
}

func (p *Pool[T]) Get() T {
	var v T
	get := p.pool.Get()
	if get != nil {
		v, _ = get.(T)
	}
	return v
}

func main() {
	bufferPool := NewPool(func() *bytes.Buffer {
		return bytes.NewBuffer(nil)
	})

	for range 100 {
		buffer := bufferPool.Get()
		buffer.WriteString("Hello, World!")
		fmt.Println(buffer.String())
		buffer.Reset()
		bufferPool.Put(buffer)
	}
}

Résumé

L'une des grandes caractéristiques de Go est sa vitesse de compilation très rapide. La compilation est rapide car peu d'optimisations sont effectuées pendant la compilation. L'ajout des génériques augmente la charge de travail du compilateur et le rend plus complexe, ce qui ralentit inévitablement la vitesse de compilation. En fait, lorsque Go 1.18 a introduit les génériques, la compilation était effectivement plus lente. L'équipe Go voulait ajouter les génériques sans trop ralentir la compilation, et que les développeurs puissent les utiliser facilement. Si le compilateur est à l'aise (le plus à l'aise serait de ne pas avoir de génériques du tout), les développeurs ne le sont pas. Les génériques actuels sont le résultat d'un compromis entre ces deux aspects.