泛型 Generic Programming^[1] 通常指允許程序員在強類型程序設計語言中，編寫代碼時使用一些以后才指定的類型，在實例化時作為參數指明這些類型，即類型參數化

首先我們不是科班討論學術，有些概念比較模糊也正常，本文討論的內容意在給大家提供全局的視野看待泛型 Generic, 大致了解主流語言的實現

泛型會提供哪些便利呢？上面的動圖非常經典，比如 min 函數，如果沒有泛型，需要針對 int, float, string 分別寫出不同的特定實現，代碼非常冗余。本文會討論下為什么 go 需要泛型以及 go2 泛型的 proposal^[2]

CPP 模板

#include <iostream>
template <class T>
T max(T a,T b){
  T ret = a > b? a : b;
  std::cout<< a << " and " << b <<" max is " << ret << std::endl;
  return ret;
}
int main(){
  max(1,2);  // 整數
  max(1.2,2.3); // 浮點數
  return 0;
}

上面是 cpp 模板實現的 max 泛型函數，傳入 int, float 都可以工作

$ c++ max.cpp  -o max && ./max
1 and 2 max is 2
1.2 and 2.3 max is 2.3

運行結果如上所示，同樣代碼換成 go 肯定就是錯的，本質是模板在編譯期單態(tài)化，針對每個特定類型生成了特定函數

$ nm max | grep -i max
0000000100000f90 T __Z3maxIdET_S0_S0_
0000000100000ef0 T __Z3maxIiET_S0_S0_
$ c++filt __Z3maxIdET_S0_S0_
double max<double>(double, double)
$ c++filt __Z3maxIiET_S0_S0_
int max<int>(int, int)

通過 nm 查看二進制的符號表，生成了兩個函數，簽名分別是 double max<double>(double, double), int max<int>(int, int)

CPP 模板非常強大，但是也有缺點，比如二進制膨脹的厲害，有可能影響到 cpu icache, 業(yè)務代碼無所謂了。另外 T 沒有其它語言的 constraint 或 bounded, 比如要求 T 必須實現某些方法，然后函數內只能調用這些顯示的約束(C++20 會引入 concepts 實現約束)

C 怎么實現

C 嚴格意義上沒有實現，但在 C11 標準中引入了 _Generic 泛型選擇器，閹割版的實現

#include <stdio.h>
// int類型加法
int addI(int a, int b)
{
    printf("%d + %d = %d\n",a,b, a + b );
    return (a + b);
}
// double類型加法
double addF(double a, double b)
{
    printf("%f + %f = %f\n",a,b, a + b );
    return (a + b);
}
void unsupport(int a,int b)
{
    printf("unsupport type\n");
}
#define ADD(a,b) _Generic((a), \
    int:addI(a,b),\
    double:addF(a,b), \
    default:unsupport(a,b))
int main(void)
{
    ADD(1 , 2);
    ADD(1.1,2.2);
    return 0;
}

上面是實現的 ADD 方法，只是調用的時候看起來是泛型了。 這種實現是有缺點的，c 會做很多隱式轉換，即使你傳入字符串，也會編譯成功，并且取得一個值。并沒有在編譯期確保類型 a, b 一致

同時由于 c 不支持函數名重載，還要人工編寫特定實例的函數 addF, addI, 并且二進制的符號表并沒有 ADD. 類比 cpp 是由編譯器替我們完成

在 C11 以前的標準中，很多代碼都是用 void * 實現，問題在于 void 是沒有類型信息的，需要增加特定的函數指針回調，讓我們來看 redis 例子

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;


typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

上面的代碼來自 redis dict^[3], 字典是泛型的，value 可以是任意類型，只要實現了 dictType 定義的函數指針。內核里面也有大量類似實現，非常通用

Rust 實現

Rust 泛型也同樣編譯期單態(tài)化，運行時沒有開銷

fn printer<T: Display>(t: T) {
    println!("{}", t);
}

這里定義函數 printer, 類型 T 必須實現了 Display trait, 這就是所謂的 constraint 或者 bounded

impl <A, D> MyTrait<A, D> for YourType where
    A: TraitB + TraitC,
    D: TraitE + TraitF {
    
}

但假如需要滿足多個約束的時候，在 <> 里寫就很不簡潔，需要使用 where^[4] 關鍵字

Rust 很多時候難懂，就是因為疊加了泛型，生命周期，所有權，還有很多的 wrapper, 別說寫了，讀都讀不懂

Java 版本

Java 在 1.5 版本引入了泛型，它的泛型是用類型擦除實現的。Java 的泛型只是在編譯期間用于檢查類型的正確，為了保證與舊版本 JVM 的兼容，類型擦除會刪除泛型的相關信息，導致其在運行時不可用。關于這塊可以參考 大神R大的回答^[5], 早就有類似 cpp 實現，只是涉及兼容上的取舍，不得不這么做

編譯器會插入額外的類型轉換指令，與 C 語言和 C++ 在運行前就已經實現或者生成代碼相比，Java 類型的裝箱和拆箱會降低程序的執(zhí)行效率。非 Java 黨就不寫太多了

Go 為什么需要泛型

官方要在 go1.18 引入泛型，那現在我們是怎么用的呢？很多時候就是 copy 代碼，或者用 interface{} 代替

func Max(a , b Comparable) Comparable

比如常見的 Max 函數，傳入參數 a, b 都實現了 Comparable 接口，然后返回最大值。能工作不？能，但是有問題

1. 丟失了類型信息，原來 cpp/rust 的實現，在函數中操作的都是原始類型，如果用 interface 還需要斷言，這是運行時行為，性能損失很大
2. 表達力不夠，比如 a, b 不能確保是同一個類型，可能一個是 int, 另外一個是 struct. 如果想傳入的是類型組合呢？

再看一個 interface{} 不能當成泛型的例子

func sort(arr []interface{})

這個排序函數如果傳入 sort([]int{1,2,3}) 或是 sort([]float64{1.032, 3.012}) 都會報錯，原因是什么呢？？？

在 go 中 []interface{} 類型是 slice 不是 interface{}, go 中對比接口相等時，是判斷 itab 中 type 和 data 需要都一致。換句話說，不允許類型的協變(沒其它語言背景的不必糾結概念，在 Go2 中也不打算支持協變和逆變)

同時社區(qū)還有其它庫輔助，比如 genny^[6] 和 betterGO^[7], 本質還是上面的動圖

// NOTE: this is how easy it is to define a generic type
type Something generic.Type

// SomethingQueue is a queue of Somethings.
type SomethingQueue struct {
  items []Something
}

func NewSomethingQueue() *SomethingQueue {
  return &SomethingQueue{items: make([]Something, 0)}
}
func (q *SomethingQueue) Push(item Something) {
  q.items = append(q.items, item)
}
func (q *SomethingQueue) Pop() Something {
  item := q.items[0]
  q.items = q.items[1:]
  return item
}

上面定義了一個泛型 type Something generic.Type, 然后用 go generate 生成對應的泛型代碼

cat source.go | genny gen "Something=string"

// StringQueue is a queue of Strings.
type StringQueue struct {
  items []string
}

func NewStringQueue() *StringQueue {
  return &StringQueue{items: make([]string, 0)}
}
func (q *StringQueue) Push(item string) {
  q.items = append(q.items, item)
}
func (q *StringQueue) Pop() string {
  item := q.items[0]
  q.items = q.items[1:]
  return item
}

最后替換相應的類型，生成對應源碼文件，人肉模板騷不騷^^

Go2 泛型

泛型討論了很久，參見 generic programming facilities^[8], Why Generics^[9], Next Step^[10], 以及官方 proposal^[11], 這是最終版，語法上不會再改變。為了運行時性能，go 的實現類似 rust 編譯期單態(tài)化，而且為了兼容 go1 語法也會做一些妥協。如果近期想閱讀源碼的，不如等到明年 go1.18, 因為引入泛型源碼庫變更會很大

1.Multiple type parameters

// Print prints the elements of any slice.
// Print has a type parameter T and has a single (non-type)
// parameter s which is a slice of that type parameter.
func Print[T any](s []T) {
 ......
}

類型參數列表，放到中括號里 [], 其中 T 是類型，any 關鍵字是表示可以傳入任意類型。居然不是業(yè)界通用的尖括號 <> 感覺非常丑... 其中 any 其實就是 interface{} 空接口，寫起來相對方便，而且語意上表達更準確一些

// Print2 has two type parameters and two non-type parameters.
func Print2[T1, T2 any](s1 []T1, s2 []T2) { ... }

// Print2Same has one type parameter and two non-type parameters.
func Print2Same[T any](s1 []T, s2 []T) { ... }

在 Print2 中可以傳入相同或不同的類型，比如 Print2[int, int] 者 Print2[int, string] 都是允許的

但是 Print2Same 的參數 s1, s2 類別必然要相同，編譯期保證。這也就是上面提到 go1 時 interface{} 模擬泛型的問題

2.Constraint

func Stringify[T any](s []T) (ret []string) {
 for _, v := range s {
  ret = append(ret, v.String()) // INVALID
 }
 return ret
}

這個例子是不會編譯成功的，因為 T 是任意類型，并沒有實現 String() 方法。也就是說，泛型函數只允許調用 constraint 約束里顯示指定的方法 這樣的好處是，對于大型項目的構建，不會因為隱式的改動，而改變兼容性

相比于 rust where 語句，go 中增加了類型參數列表和接口的組合，做為約束

package constraints

// Ordered is a type constraint that matches any ordered type.
// An ordered type is one that supports the <, <=, >, and >= operators.
type Ordered interface {
 type int, int8, int16, int32, int64,
  uint, uint8, uint16, uint32, uint64, uintptr,
  float32, float64,
  string
}

上面是約束的定義，關鍵字 type 后面跟上允許的類型列表，不知道為啥就是丑。其它語言用到哪個類型，編譯期單態(tài)就好了，go 需要人工枚舉所有可能...

// Smallest returns the smallest element in a slice.
// It panics if the slice is empty.
func Smallest[T constraints.Ordered](s []T) T {
 r := s[0] // panics if slice is empty
 for _, v := range s[1:] {
  if v < r {
   r = v
  }
 }
 return r
}

3.泛型類型

上面提到的都是 Generic Func, 另一個使用場景是泛型類型 Generic Type

// Vector is a name for a slice of any element type.
type Vector[T any] []T

上面標準的泛型容器定義，類似其它語言的 Vector

// Push adds a value to the end of a vector.
func (v *Vector[T]) Push(x T) { *v = append(*v, x) }

同樣，泛型類型還可以定義方法

// List is a linked list of values of type T.
type ListNode[T] {xxx}
type List[T] struct {
    head *ListNode[T]
    tail *ListNode[T]
    size int
}


// This type is INVALID.
type P[T1, T2 any] struct {
 F *P[T2, T1] // INVALID; must be [T1, T2]
}

上面是定義的 struct 語法，比較相似。但如果泛型類型，有指向自己的指針，那么注意參數順序也要一樣，P[T1, T2 any] 這樣寫的，那么指針也要 *[T1, T2]. 官方說防止類型實例化的遞歸

4.Comparable types in constraints

Go 不允許重載操作符，這樣好處多多。但同時代表著大于，小于這些只適用于基本類型。但也有例外 ==, != 可以比較 struct, array, interface. 官方在標準庫預定義了約束 comparable 用于比較

// Index returns the index of x in s, or -1 if not found.
func Index[T comparable](s []T, x T) int {
 for i, v := range s {
  // v and x are type T, which has the comparable
  // constraint, so we can use == here.
  if v == x {
   return i
  }
 }
 return -1
}

上面的例子很清晰明了，T 實現了比較接口，就可以用 ==

// ComparableHasher is a type constraint that matches all
// comparable types with a Hash method.
type ComparableHasher interface {
 comparable
 Hash() uintptr
}

// ImpossibleConstraint is a type constraint that no type can satisfy,
// because slice types are not comparable.
type ImpossibleConstraint interface {
 comparable
 type []int
}

用 interface 實現約束，上面的例子是 hasher 接口，下面的接口是永遠不能實現的，很好理解，類型 []int 是不能比較的

5.類型推導 type inference

類型推導很重要，可以省略很多無用代碼，編譯器自動識別類型

func Map[F, T any](s []F, f func(F) T) []T { ... }

這是一個 Map 算子函數的簽名，f 匿名函數，將 []F 轉換成 []T 類型 slice

 var s []int
 f := func(i int) int64 { return int64(i) }
 var r []int64
 // Specify both type arguments explicitly.
 r = Map[int, int64](s, f)
 // Specify just the first type argument, for F,
 // and let T be inferred.
 r = Map[int](s, f)
 // Don't specify any type arguments, and let both be inferred.
 r = Map(s, f)

最理想只需要調用 r=Map(s, f) 就可以，否則還要寫 r = Map[int, int64](s, f), 能推導的就不要讓人寫

除了上面的，再舉個例子比如 T1, T2 是兩個類型參數，那么 []map[int]bool 可以和以下類型統(tǒng)一 unified 起來

• []map[int]bool 這個就是類型自身，很好理解
• T1 當然可以匹配
• []T1 T1 匹配到 map[int]bool
• []map[T1]T2 這里 T1 是 int, T2 是 bool

上面只是幾種可能，但同時不能匹配到 int, struct{}, []map[T1]string 這也是顯而易見的。雖然 go2 不支持協變，但是基于類型推導還是比 go1 方便的多

6.type lists 組合

// StringableSignedInteger is a type constraint that matches any
// type that is both 1) defined as a signed integer type;
// 2) has a String method.
type StringableSignedInteger interface {
 type int, int8, int16, int32, int64
 String() string
}

約束還可以將 類型列表 與普通的接口函數組合起來。上面的 StringableSignedInteger 要求約束，必須是 type list 里的任一類型，同時實現了 String() string 函數

問題是 int 這些都沒有 string 方法，所以上面約束其實是 impossible 的，只是舉例子說明如何使用

7.未實現部份

官方還列舉了很多 omissions^[12] 未實現的點

比如不支持：特化，元編程(cpp 玩爛了)，curry 柯立化等等，泛型分享內容大致這些，感興趣直接看官網好了

泛型代價

引入泛型不是沒有代價的，都是取舍，好在 go 語言誕生才十年，沒有很重的歷史包袱

• Slow Compiler: 這是 c++/rust 泛型
• Slow Performance: 這是 java/scala 泛型
• Slow Programmer: 這是 go1

但 go 真的需要泛型嘛？雖然 go 定位是系統(tǒng)語言，用的最多還是偏業(yè)務層，中間件以下還是 c/c++ 的舞臺，哪怕 go 己經有了殺手級應用 docker/k8s

吸引大公司選擇 go 的原因，就是簡單，快速上手，goroutine 用戶態(tài)高并發(fā)。如果 GA 后，會不會導致代碼庫里泛型使用泛濫呢？可以預見，go1.18 出來后，大家要刷新對 go 的認識了，同時對于新手學習區(qū)線也不再簡單

支持泛型也會讓 go 很好的處理數據，要是再搞個分代 GC, 是不是可以造大數據的輪子了^^

小結

引用曹大^[13]的一句話：敏捷大師們其實非常雙標，他們給出的方法論也不一定靠譜，反正成功了就是大師方法得當，失敗了就是我們執(zhí)行不力沒有學到精髓。正著說反著說都有道理。

再看看現在的 Go 社區(qū)，buzzwords 也很多，如果一個特性大師不想做，那就是 less is more. 如果一個特性大師想做，那就是 orthogonal, 非?？陀^

寫文章不容易，如果對大家有所幫助和啟發(fā)，請大家?guī)兔c擊在看，點贊，分享 三連

關于 泛型 大家有什么看法，歡迎留言一起討論，大牛多留言 ^_^

參考資料