Genéricos

Los genéricos, o más académicamente llamados polimorfismo parametrizado (Parameterized Polymorphism), se refieren a la reutilización y flexibilidad del código mediante la parametrización de tipos. En muchos lenguajes de programación, el polimorfismo parametrizado es un concepto importante que permite a las funciones o estructuras de datos manejar diferentes tipos de datos sin necesidad de escribir código separado para cada tipo. El Go original no tenía genéricos, pero desde su nacimiento, la solicitud más común de la comunidad sobre Go fue la adición de genéricos. Finalmente, Go añadió soporte para genéricos en la versión 1.18 en 2022.

Diseño

Cuando Go diseñó los genéricos, consideró las siguientes opciones:

• stenciling: monomorfización, típico en C++ y Rust, genera una plantilla de código para cada tipo utilizado. Esto tiene el mejor rendimiento, sin costo en tiempo de ejecución, igual que una llamada directa. La desventaja es que ralentiza significativamente la velocidad de compilación (en comparación con Go mismo) y, como genera código para cada tipo, también infla el tamaño del binario compilado.

• dictionaries: solo genera un conjunto de código y crea un diccionario de tipos en tiempo de compilación almacenado en el segmento de datos de solo lectura. Almacena toda la información de tipos que se utilizará, y al llamar a la función, consulta la información de tipos según el diccionario. Este método no ralentiza la velocidad de compilación ni causa inflación de tamaño, pero genera un gran costo en tiempo de ejecución, el rendimiento de los genéricos es muy pobre.

Los dos métodos anteriores representan dos extremos. La implementación final elegida por Go es Gcshape stenciling, un compromiso. Para tipos con la misma forma de memoria (la forma la decide el asignador de memoria), se usa monomorfización y se genera el mismo código. Por ejemplo, type Int int e int son esencialmente el mismo tipo, por lo que comparten el mismo código. Sin embargo, para los punteros, aunque todos los tipos de punteros tienen la misma forma de memoria (por ejemplo, *int, *Person), no pueden compartir el mismo código porque las operaciones de desreferenciación tienen diseños de memoria de tipo objetivo completamente diferentes. Por esta razón, Go también usa diccionarios para obtener información de tipos en tiempo de ejecución, por lo que los genéricos de Go también tienen un costo en tiempo de ejecución.

Introducción

Veamos un ejemplo simple:

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

Esta es una función muy simple que suma dos enteros de tipo int y devuelve el resultado. Si se quisiera pasar dos números de punto flotante de tipo float64 para sumar, claramente no funcionaría porque los tipos no coinciden. Una solución sería definir una nueva función:

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

Entonces surge la pregunta: si se desarrolla un paquete de herramientas matemáticas para calcular la suma de dos números de todos los tipos numéricos, ¿se debe escribir una función para cada tipo? Claramente no es factible. O se podría usar el tipo any con reflexión para determinar el tipo:

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

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

Pero esto es engorroso y de bajo rendimiento. Sin embargo, la lógica de la función Sum es exactamente la misma, solo suma dos números. Aquí es donde se necesitan los genéricos. ¿Por qué se necesitan los genéricos? Los genéricos existen para resolver problemas donde la lógica de ejecución es independiente del tipo. Este tipo de problemas no se preocupa por qué tipo se proporciona, solo necesita completar la operación correspondiente.

Sintaxis

Los genéricos se escriben así:

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

Parámetro de tipo: T es un parámetro de tipo, el tipo específico depende de lo que se pase.

Restricción de tipo: int | float64 constituye una restricción de tipo, que especifica qué tipos están permitidos y limita el rango de tipos del parámetro de tipo.

Argumento de tipo: Sum[int](1,2), se especifica manualmente el tipo int, int es el argumento de tipo.

Primer uso, especificar explícitamente qué tipo usar:

Sum[int](2012, 2022)

Segundo uso, no especificar el tipo y dejar que el compilador lo infiera:

Sum(3.1415926, 1.114514)

Este es un slice genérico con restricción de tipo int | int32 | int64:

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

Aquí no se puede omitir el argumento de tipo:

GenericSlice[int]{1, 2, 3}

Este es un mapa hash genérico, el tipo de clave debe ser comparable, por lo que se usa la interfaz comparable, la restricción de tipo de valor es V int | string | byte:

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

Uso:

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

Esta es una estructura genérica con restricción de tipo T int | string:

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

Uso:

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

Este es un ejemplo de parámetro de slice genérico:

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

// también se puede escribir así
type Company[T int | string, S []int | []string] struct {
  Name  string
  Id    T
  Stuff S
}

Uso:

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

TIP

En estructuras genéricas, se recomienda más esta escritura:

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

SayAble es una interfaz genérica, Person implementa esta interfaz:

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

Interfaz Genérica

Las interfaces genéricas pueden proporcionar mejor capacidad de restricción de abstracción. Aquí hay un ejemplo:

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

También se puede usar una interfaz no genérica como parámetro de tipo genérico:

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

Afirmación de Tipo Genérico

Se pueden usar genéricos para hacer afirmaciones de tipo sobre el tipo any. Por ejemplo, la siguiente función puede afirmar todos los tipos:

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

Conjuntos de Tipos

Después de la versión 1.18, la definición de interfaz cambió a conjunto de tipos (type set). Las interfaces que contienen conjuntos de tipos se denominan General interfaces o interfaces genéricas.

An interface type defines a type set

Los conjuntos de tipos solo se pueden usar para restricciones de tipo en genéricos, no se pueden usar para declaraciones de tipo, conversiones de tipo o afirmaciones de tipo. Como conjunto, un conjunto de tipos tiene conjunto vacío, unión e intersección. A continuación se explicarán estas tres situaciones.

Unión

El tipo de interfaz SignedInt es un conjunto de tipos. La unión de tipos de enteros con signo es SignedInt, y a la inversa, SignedInt es su superconjunto:

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

Lo mismo aplica para otros tipos de datos básicos y otras interfaces genéricas:

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

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

type Integer interface {
  SignedInt | UnSignedInt
}

Intersección

El conjunto de tipos de una interfaz no vacía es la intersección de los conjuntos de tipos de todos sus elementos. En otras palabras: si una interfaz contiene múltiples conjuntos de tipos no vacíos, entonces esa interfaz es la intersección de esos conjuntos de tipos. Ejemplo:

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
}

La intersección en el ejemplo es claramente SignedInt:

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

Do[int](2)
DO[uint](2) // no puede compilar

Conjunto Vacío

El conjunto vacío es cuando no hay intersección. En el siguiente ejemplo, Integer es un conjunto de tipos vacío:

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

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

type Integer interface {
  SignedInt
  UnsignedInt
}

Como los enteros sin signo y con signo definitivamente no tienen intersección, la intersección es un conjunto vacío. En el siguiente ejemplo, no importa qué tipo se pase, no podrá compilar:

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

Interfaz Vacía

La interfaz vacía es diferente del conjunto vacío. La interfaz vacía es el conjunto de todos los conjuntos de tipos, es decir, contiene todos los tipos:

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

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

Sin embargo, generalmente usamos any como parámetro de tipo genérico porque interface{} no se ve bien.

Tipo Subyacente

Cuando se declara un nuevo tipo con la palabra clave type, incluso si su tipo subyacente está incluido en el conjunto de tipos, aún no podrá compilar al pasarlo:

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) // no puede compilar, incluso si su tipo subyacente está dentro del conjunto de tipos Int
}

Hay dos soluciones. La primera es agregar ese tipo al conjunto de tipos, pero esto no tiene sentido porque TinyInt e int8 tienen el mismo tipo subyacente. Por lo tanto, existe la segunda solución:

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

Usar el símbolo ~ para indicar el tipo subyacente. Si el tipo subyacente de un tipo pertenece a ese conjunto de tipos, entonces ese tipo pertenece a ese conjunto de tipos:

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

Después de modificar, podrá compilar:

func main() {
   Do[TinyInt](1) // puede compilar porque TinyInt está dentro del conjunto de tipos Int
}

Puntos a Tener en Cuenta

Los genéricos no pueden ser un tipo básico de un tipo

La siguiente escritura es incorrecta, el parámetro de tipo genérico T no puede ser un tipo básico:

type GenericType[T int | int32 | int64] T

Aunque la siguiente escritura es permitida, no tiene sentido y puede causar problemas de desbordamiento numérico, por lo que no se recomienda:

type GenericType[T int | int32 | int64] int

Los tipos genéricos no pueden usar afirmación de tipo

Usar afirmación de tipo en tipos genéricos no podrá compilar. Los genéricos resuelven problemas independientes del tipo. Si un problema requiere lógica diferente según diferentes tipos, entonces no se deben usar genéricos, se debe usar interface{} o any:

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

Las estructuras anónimas no admiten genéricos

Las estructuras anónimas no admiten genéricos, el siguiente código no podrá compilar:

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

Las funciones anónimas no admiten genéricos personalizados

Las siguientes dos escrituras no podrán compilar:

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

Pero se pueden usar tipos genéricos existentes, por ejemplo, en closures:

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

No se admiten métodos genéricos

Los métodos no pueden tener parámetros de tipo genérico, pero el receiver puede tener parámetros de tipo genérico. El siguiente código no podrá compilar:

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

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

Los conjuntos de tipos no pueden usarse como argumentos de tipo

Cualquier interfaz con conjunto de tipos no puede usarse como argumento de tipo:

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

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

func main() {
   Do[SignedInt](1) // no puede compilar
}

Problema de intersección en conjuntos de tipos

Para tipos no interfaz, la unión de tipos no puede tener intersección. Por ejemplo, TinyInt y ~int8 tienen intersección:

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // no puede compilar
}

type TinyInt int8

Pero para tipos de interfaz, se permite tener intersección:

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

type TinyInt interface {
  int8
}

Los conjuntos de tipos no pueden unirse directa o indirectamente consigo mismos

En el siguiente ejemplo, Floats se une directamente consigo mismo, y Double se une con Floats, por lo que indirectamente se une consigo mismo:

type Floats interface {  // el código no puede compilar
   Floats | Double
}

type Double interface {
   Floats
}

La interfaz comparable no puede unirse a conjuntos de tipos

Tampoco se puede unir a restricciones de tipo, por lo que generalmente se usa por separado:

func Do[T comparable | Integer](n T) T { // no puede compilar
   return n
}

type Number interface { // no puede compilar
  Integer | comparable
}

type Comparable interface { // puede compilar pero no tiene sentido
  comparable
}

Los conjuntos de métodos no pueden unirse a conjuntos de tipos

Cualquier interfaz que contenga métodos no puede unirse a un conjunto de tipos:

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

Pero pueden hacer intersección, aunque esto no tiene sentido:

type I interface {
    int
    fmt.Stringer
}

Uso

Las estructuras de datos son el escenario de uso más común de los genéricos. A continuación se muestra cómo usar genéricos con dos estructuras de datos.

Cola

A continuación se implementa una cola simple con genéricos. Primero se declara el tipo de cola, el tipo de elemento en la cola puede ser cualquiera, por lo que la restricción de tipo es any:

type Queue[T any] []T

Solo hay cuatro métodos: Pop, Peek, Push, Size. El código es el siguiente:

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

En los métodos Pop y Peek, se puede ver que el valor de retorno es _ T. Esta es una forma de usar valores de retorno con nombre, pero se usa el guion bajo _ para indicar que es anónimo. Esto no es redundante, sino para representar el valor cero genérico. Debido a que se usan genéricos, cuando la cola está vacía, se debe devolver un valor cero, pero como el tipo es desconocido, no es posible devolver un tipo específico. Usando la forma anterior se puede devolver el valor cero genérico. También se puede resolver el problema del valor cero declarando una variable genérica. Para una variable genérica, su valor predeterminado es el valor cero de ese 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

En el ejemplo de la cola anterior, como no hay requisitos para los elementos, la restricción de tipo es any. Pero el heap es diferente. El heap es una estructura de datos especial que puede determinar el valor máximo o mínimo en tiempo O(1), por lo que tiene un requisito para los elementos: deben ser tipos ordenables. Pero los tipos ordenables incorporados solo son números y cadenas, por lo que al inicializar el heap, se debe pasar un comparador personalizado. El comparador lo proporciona el llamador y también debe usar genéricos:

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

A continuación se muestra una implementación simple de un heap binario. Primero se declara la estructura genérica, aún usando any como restricción para poder almacenar cualquier tipo:

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

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

Implementación de varios métodos:

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 {
    // mayor o igual
    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
    }

    // menor o igual
    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
}

Uso:

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

Salida:

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

Con el apoyo de los genéricos, los tipos que originalmente no se podían ordenar también pueden usar heap pasando un comparador. Esto es definitivamente más elegante y conveniente que usar interface{} para conversión y afirmación de tipos.

Pool de Objetos

El pool de objetos original solo podía usar el tipo any, y cada vez que se obtenía un objeto se debía hacer una afirmación de tipo. Con una simple modificación usando genéricos, se puede evitar este trabajo:

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

Resumen

Una de las características de Go es su velocidad de compilación muy rápida. La compilación es rápida porque se hacen pocas optimizaciones en tiempo de compilación. La adición de genéricos aumenta la carga de trabajo del compilador y lo hace más complejo, lo que inevitablemente ralentiza la velocidad de compilación. De hecho, cuando Go 1.18 lanzó los genéricos, efectivamente ralentizó la compilación. El equipo de Go quería agregar genéricos sin ralentizar demasiado la compilación, y que los desarrolladores los usaran cómodamente. Si el compilador sufre, los desarrolladores están contentos; si el compilador está relajado (lo más relajado sería no tener genéricos), los desarrolladores sufren. Los genéricos actuales son el producto de este compromiso.