Generici

I generici, o più academicamente polimorfismo parametrizzato (Parameterized Polymorphism), si riferiscono all'utilizzo della parametrizzazione dei tipi per realizzare il riutilizzo e la flessibilità del codice. In molti linguaggi di programmazione, il polimorfismo parametrizzato è un concetto importante che consente a funzioni o strutture dati di gestire dati di tipi diversi senza dover scrivere codice separato per ogni tipo. Il Go iniziale non aveva i generici, ma dalla sua nascita, la richiesta più alta dalla comunità per Go è stata l'aggiunta dei generici. Finalmente, nel 2022, Go ha aggiunto il supporto per i generici nella versione 1.18.

Progettazione

Quando Go ha progettato i generici, ha considerato i seguenti piani:

• stenciling: monomorfismo, tipico di C++ e Rust, genera una versione del codice template per ogni tipo utilizzato. Questo ha le migliori prestazioni, senza alcun sovraccarico runtime, le prestazioni equivalgono a una chiamata diretta. Lo svantaggio è che rallenta notevolmente la velocità di compilazione (rispetto al Go stesso) e, poiché genera codice per ogni tipo, causa anche un aumento del volume del file binario compilato.
• dictionaries: genera solo un set di codice e genera un dizionario di tipi durante la compilazione, memorizzato nella sezione dati di sola lettura. Contiene tutte le informazioni sui tipi che verranno utilizzati. Durante la chiamata della funzione, le informazioni sul tipo vengono cercate nel dizionario. Questo metodo non rallenta la velocità di compilazione e non causa aumento del volume, ma crea un enorme sovraccarico runtime, con scarse prestazioni dei generici.

I due metodi sopra rappresentano due estremi. Il piano di implementazione finale scelto da Go è Gcshape stenciling, che è un compromesso. Per i tipi con la stessa forma di memoria (la forma è decisa dall'allocatore di memoria), verrà utilizzato il monomorfismo per generare lo stesso codice. Ad esempio, type Int int e int sono effettivamente lo stesso tipo, quindi condividono lo stesso codice. Ma per i puntatori, anche se tutti i tipi di puntatori hanno la stessa forma di memoria, ad esempio *int e *Person hanno la stessa forma di memoria, non possono condividere lo stesso codice, poiché le operazioni di dereferenziazione hanno layout di memoria del tipo target completamente diversi. Per questo motivo, Go utilizza anche dizionari per ottenere informazioni sui tipi durante il runtime, quindi i generici di Go hanno anche un sovraccarico runtime.

Introduzione

Vediamo prima un esempio semplice:

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

Questa è una funzione molto semplice che somma due numeri interi di tipo int e restituisce il risultato. Se si desidera passare due numeri floating-point di tipo float64 per la somma, ovviamente non è possibile, poiché i tipi non corrispondono. Una soluzione è definire una nuova funzione:

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

Ma sorge un problema: se si sviluppa un pacchetto di strumenti matematici per calcolare la somma di due numeri di tutti i tipi numerici, si dovrebbe scrivere una funzione per ogni tipo? Ovviamente non è possibile. Oppure si può utilizzare il tipo any con la reflection per判断, come segue:

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

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

Ma scrivere così è noioso e le prestazioni sono scarse. Ma la logica della funzione Sum è sempre la stessa, si tratta solo di sommare due numeri. Qui entrano in gioco i generici. Quindi perché sono necessari i generici? I generici servono a risolvere problemi in cui l'esecuzione della logica è indipendente dal tipo. Questo tipo di problemi non si preoccupa di quale tipo viene fornito, basta completare l'operazione corrispondente.

Sintassi

La scrittura dei generici è la seguente:

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

Parametri di tipo: T è un parametro di tipo. Il tipo specifico del parametro dipende da quale tipo viene passato.

Vincoli di tipo: int | float64 costituiscono un vincolo di tipo. Questo vincolo di tipo specifica quali tipi sono consentiti, limitando l'intervallo dei tipi dei parametri di tipo.

Argomenti di tipo: Sum[int](1,2), specifica manualmente il tipo int, int è l'argomento di tipo.

Primo utilizzo, specifica esplicitamente quale tipo utilizzare:

Sum[int](2012, 2022)

Secondo utilizzo, non specifica il tipo, lascia che il compilatore lo inferisca:

Sum(3.1415926, 1.114514)

Questa è una slice generica, con vincolo di tipo int | int32 | int64:

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

Qui non si può omettere l'argomento di tipo durante l'uso:

GenericSlice[int]{1, 2, 3}

Questa è una mappa generica. La chiave deve essere confrontabile, quindi utilizza l'interfaccia comparable. Il vincolo di tipo del valore è V int | string | byte:

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

Utilizzo:

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

Questa è una struttura generica, con vincolo di tipo T int | string:

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

Utilizzo:

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

Questo è un esempio di parametro di slice generica:

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

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

Utilizzo:

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

TIP

Nelle strutture generiche, si consiglia questa scrittura:

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

SayAble è un'interfaccia generica, Person implementa questa interfaccia:

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())
}

Interfacce Generiche

Le interfacce generiche possono fornire migliori capacità di astrazione e vincolo. Ecco un esempio:

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"})
}

È anche possibile utilizzare un'interfaccia non generica come parametro di tipo generico:

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

Type Assertion Generica

Possiamo utilizzare i generici per eseguire type assertion sul tipo any. Ad esempio, la funzione seguente può asserire tutti i tipi:

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

Insiemi di Tipi

Dopo la versione 1.18, la definizione di interfaccia è diventata un type set (insieme di tipi). Le interfacce contenenti insiemi di tipi sono chiamate General interfaces, ovvero interfacce generiche.

An interface type defines a type set

Gli insiemi di tipi possono essere utilizzati solo come vincoli di tipo nei generici, non possono essere utilizzati per dichiarazioni di tipo, conversioni di tipo o type assertion. Un insieme di tipi è un insieme e avrà insiemi vuoti, unioni e intersezioni. Di seguito verranno spiegati questi tre casi.

Unione

Il tipo di interfaccia SignedInt è un insieme di tipi. L'unione dei tipi di numeri interi con segno è SignedInt. Viceversa, SignedInt è il loro superset:

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

Lo stesso vale per gli altri tipi di interfacce generiche:

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

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

type Integer interface {
  SignedInt | UnSignedInt
}

Intersezione

L'insieme di tipi di un'interfaccia non vuota è l'intersezione degli insiemi di tipi di tutti i suoi elementi. Tradotto in linguaggio umano: se un'interfaccia contiene più insiemi di tipi non vuoti, allora quell'interfaccia è l'intersezione di questi insiemi di tipi. Ecco un esempio:

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'intersezione nell'esempio è sicuramente SignedInt:

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

Do[int](2)
DO[uint](2) // Non può passare la compilazione

Insieme Vuoto

L'insieme vuoto significa che non c'è intersezione. Ecco un esempio, Integer nell'esempio seguente è un insieme di tipi vuoto:

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

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

type Integer interface {
  SignedInt
  UnsignedInt
}

Poiché i numeri interi senza segno e i numeri interi con segno non hanno sicuramente intersezione, l'intersezione è un insieme vuoto. Nell'esempio seguente, indipendentemente da quale tipo viene passato, non può passare la compilazione:

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

Interfaccia Vuota

L'interfaccia vuota non è la stessa dell'insieme vuoto. L'interfaccia vuota è l'insieme di tutti gli insiemi di tipi, ovvero contiene tutti i tipi:

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

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

Tuttavia, generalmente utilizziamo any come parametro di tipo generico, poiché interface{} non è esteticamente gradevole.

Tipo Sottostante

Quando si dichiara un nuovo tipo utilizzando la parola chiave type, anche se il suo tipo sottostante è incluso nell'insieme di tipi, non potrà passare la compilazione quando viene passato:

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) // Non può passare la compilazione, anche se il suo tipo sottostante appartiene all'intervallo dell'insieme di tipi Int
}

Ci sono due soluzioni. La prima è aggiungere il tipo all'insieme di tipi, ma questo non ha senso, poiché TinyInt e int8 hanno lo stesso tipo sottostante. Quindi c'è una seconda soluzione:

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

Utilizzando il simbolo ~ per indicare il tipo sottostante. Se il tipo sottostante di un tipo appartiene a quell'insieme di tipi, allora quel tipo appartiene a quell'insieme di tipi:

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

Dopo la modifica, può passare la compilazione:

func main() {
   Do[TinyInt](1) // Può passare la compilazione, poiché TinyInt è nell'insieme di tipi Int
}

Punti di Attenzione

I generici non possono essere utilizzati come tipo di base per un tipo

La seguente scrittura è errata. Il parametro di tipo generico T non può essere utilizzato come tipo di base:

type GenericType[T int | int32 | int64] T

Anche se la scrittura seguente è consentita, non ha senso e potrebbe causare problemi di overflow numerico, quindi non è consigliata:

type GenericType[T int | int32 | int64] int

I tipi generici non possono utilizzare type assertion

Utilizzare type assertion su tipi generici non passerà la compilazione. I generici devono risolvere problemi indipendenti dal tipo. Se un problema richiede logica diversa in base a tipi diversi, allora non si dovrebbero assolutamente utilizzare i generici. Si dovrebbe utilizzare interface{} o any:

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

Le strutture anonime non supportano i generici

Le strutture anonime non supportano i generici. Il codice seguente non passerà la compilazione:

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

Le funzioni anonime non supportano generici personalizzati

Le seguenti due scritture non passeranno la compilazione:

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

Ma è possibile utilizzare tipi generici esistenti, ad esempio nelle closure:

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

Non supporta metodi generici

I metodi non possono avere parametri di tipo generici, ma il receiver può avere parametri di tipo generici. Il codice seguente non passerà la compilazione:

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

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

Gli insiemi di tipi non possono essere utilizzati come argomenti di tipo

Qualsiasi interfaccia con un insieme di tipi non può essere utilizzata come argomento di tipo:

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

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

func main() {
   Do[SignedInt](1) // Non può passare la compilazione
}

Problemi di intersezione negli insiemi di tipi

Per i tipi non di interfaccia, non ci possono essere intersezioni nell'unione di tipi. Ad esempio, TinyInt e ~int8 nell'esempio seguente hanno un'intersezione:

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // Non può passare la compilazione
}

type TinyInt int8

Ma per i tipi di interfaccia, è consentito avere intersezioni:

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // Può passare la compilazione
}

type TinyInt interface {
  int8
}

Gli insiemi di tipi non possono essere uniti direttamente o indirettamente a se stessi

Nell'esempio seguente, Floats si unisce direttamente a se stesso, e Double si unisce a Floats, quindi si unisce indirettamente a se stesso:

type Floats interface {  // Il codice non può passare la compilazione
   Floats | Double
}

type Double interface {
   Floats
}

L'interfaccia comparable non può essere unita agli insiemi di tipi

Allo stesso modo, non può essere unita ai vincoli di tipo, quindi viene基本上 utilizzata separatamente:

func Do[T comparable | Integer](n T) T { // Non può passare la compilazione
   return n
}

type Number interface { // Non può passare la compilazione
  Integer | comparable
}

type Comparable interface { // Può passare la compilazione ma non ha senso
  comparable
}

I method set non possono essere uniti agli insiemi di tipi

Qualsiasi interfaccia contenente metodi non può essere unita a un insieme di tipi:

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

Ma possono fare intersezioni, anche se questo non ha alcun senso:

type I interface {
    int
    fmt.Stringer
}

Utilizzo

Le strutture dati sono lo scenario di utilizzo più comune dei generici. Di seguito vengono mostrati due strutture dati per dimostrare come utilizzare i generici.

Coda

Di seguito viene implementata una semplice coda utilizzando i generici. Prima si dichiara il tipo di coda. Il tipo degli elementi nella coda può essere arbitrario, quindi il vincolo di tipo è any:

type Queue[T any] []T

Ci sono solo quattro metodi: Pop, Peek, Push, Size. Il codice è il seguente:

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)
}

Nei metodi Pop e Peek, si può vedere che il valore di ritorno è _ T. Questo è l'uso di valori di ritorno nominati, ma utilizza il trattino basso _ per indicare che è anonimo. Questo non è superfluo, ma per indicare il valore zero generico. Poiché sono stati utilizzati i generici, quando la coda è vuota, è necessario restituire un valore zero, ma poiché il tipo è sconosciuto, non è possibile restituire un tipo specifico. Utilizzando il metodo sopra, è possibile restituire un valore zero generico. È anche possibile dichiarare una variabile generica per risolvere il problema del valore zero. Per una variabile generica, il suo valore predefinito è il valore zero di quel tipo:

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
}

Heap

Nell'esempio della coda sopra, poiché non ci sono requisiti per gli elementi, il vincolo di tipo è any. Ma l'heap è diverso. L'heap è una struttura dati speciale che può判断 il valore massimo o minimo in O(1), quindi ha un requisito per gli elementi: devono essere tipi ordinabili. Ma i tipi ordinabili built-in sono solo numeri e stringhe, quindi durante l'inizializzazione dell'heap, è necessario passare un comparatore personalizzato. Il comparatore viene fornito dal chiamante e anche il comparatore deve utilizzare i generici:

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

Di seguito è riportata una semplice implementazione di un heap binario. Prima si dichiara la struttura generica, utilizzando ancora any come vincolo, in modo da poter memorizzare qualsiasi tipo:

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

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

Implementazione di alcuni metodi:

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
}

L'utilizzo è il seguente:

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())
}

Output:

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

Con il supporto dei generici, anche i tipi non ordinabili possono utilizzare l'heap dopo aver passato un comparatore. Questo è sicuramente più elegante e conveniente rispetto all'utilizzo di interface{} per conversioni e assertion di tipo.

Pool di Oggetti

Il pool di oggetti originale può utilizzare solo il tipo any, e ogni volta che si estrae è necessario eseguire un type assertion. Dopo una semplice modifica con i generici, è possibile risparmiare questo lavoro:

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)
	}
}

Riepilogo

Una delle grandi caratteristiche di Go è la velocità di compilazione molto rapida. La compilazione è veloce perché il compilatore fa poche ottimizzazioni durante la fase di compilazione. L'aggiunta dei generici causerà un aumento del carico di lavoro del compilatore e una maggiore complessità, il che porterà inevitabilmente a un rallentamento della velocità di compilazione. In effetti, quando Go 1.18 ha introdotto i generici, ha effettivamente rallentato la compilazione. Il team Go voleva aggiungere i generici senza rallentare troppo la compilazione e rendere l'uso degli sviluppatori agevole. Se il compilatore è a disagio (il più a disagio è ovviamente senza generici), gli sviluppatori sono a disagio. I generici attuali sono il prodotto del compromesso tra questi due aspetti.