Go 部落格
為什麼要泛型？
引言
本文是我在上週 Gophercon 2019 大會上演講的部落格版本。
本文旨在探討將泛型新增到 Go 語言的意義，以及我認為我們應該這樣做的原因。我還會提及關於在 Go 中新增泛型的一種可能設計方案的最新進展。
Go 於 2009 年 11 月 10 日釋出。不到 24 小時後，我們看到了關於泛型的第一個評論。(該評論也提到了異常，我們在 2010 年初以 panic 和 recover 的形式將其新增到了語言中。)
在三年的 Go 語言調查中，缺乏泛型一直被列為語言中需要解決的前三大問題之一。
為什麼要泛型？
但新增泛型意味著什麼？我們為什麼想要它？
引用 Jazayeri 等人的話來說：泛型程式設計使得函式和資料結構能夠以泛型形式表示，並將型別引數化。
這是什麼意思？
舉個簡單的例子，假設我們想反轉一個切片中的元素。這並非許多程式都需要的操作，但也並非完全不常見。
假設這是一個 int 型別的切片。
func ReverseInts(s []int) {
first := 0
last := len(s)
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}
相當簡單，但即使對於這樣一個簡單的函式，你也會想寫幾個測試用例。實際上，當我寫的時候，我發現了一個 bug。我相信很多讀者已經發現了。
func ReverseInts(s []int) {
first := 0
last := len(s) - 1
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}
當我們設定變數 last 時，需要減去 1。
現在我們來反轉一個 string 型別的切片。
func ReverseStrings(s []string) {
first := 0
last := len(s) - 1
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}
如果你比較 ReverseInts 和 ReverseStrings，你會發現這兩個函式完全相同，除了引數的型別不同。我相信沒有讀者會對此感到驚訝。
對於一些 Go 新手來說，令人驚訝的是目前無法編寫一個適用於任何型別切片的簡單 Reverse 函式。
大多數其他語言都允許你編寫此類函式。
在像 Python 或 JavaScript 這樣的動態型別語言中，你可以簡單地編寫函式，無需指定元素型別。這在 Go 中行不通，因為 Go 是靜態型別語言，要求你寫出切片的精確型別和切片元素的型別。
大多數其他靜態型別語言，如 C++、Java、Rust 或 Swift，都支援泛型來解決正是這類問題。
當今 Go 中的泛型程式設計
那麼，人們如何在 Go 中編寫這類程式碼呢？
在 Go 中，你可以透過使用介面型別，並在你想傳入的切片型別上定義方法，來編寫一個適用於不同切片型別的函式。標準庫的 sort.Sort 函式就是這樣工作的。
換句話說，Go 中的介面型別是一種泛型程式設計形式。它們允許我們捕獲不同型別的共同之處，並將其表達為方法。然後我們可以編寫使用這些介面型別的函式，這些函式將適用於任何實現了這些方法的型別。
但這種方法未能達到我們期望的效果。使用介面時，你必須自己編寫方法。僅僅為了反轉一個切片，就不得不定義一個帶有幾個方法的命名型別，這很笨拙。而且你為每種切片型別編寫的方法都是完全相同的，所以從某種意義上說，我們只是移動和精簡了重複程式碼，並沒有消除它。儘管介面是一種泛型形式，但它們並未提供我們期望從泛型獲得的一切。
另一種利用介面實現泛型的方式，可以避免自己編寫方法，那就是讓語言為某些型別的型別定義方法。這是語言目前不支援的，但例如，語言可以定義每種切片型別都有一個返回元素的 Index 方法。但要在實踐中使用該方法，它必須返回空介面型別，這樣我們就會失去靜態型別的所有好處。更微妙的是，將無法定義一個泛型函式，該函式接受兩個具有相同元素型別的不同切片，或者接受一種元素型別的 map 並返回相同元素型別的切片。Go 是一種靜態型別語言，因為這使得編寫大型程式更容易；我們不希望為了獲得泛型的好處而失去靜態型別的好處。
另一種方法是使用 reflect 包編寫一個泛型的 Reverse 函式，但這非常笨拙且執行緩慢，以至於很少有人這樣做。這種方法還需要顯式的型別斷言，並且沒有靜態型別檢查。
或者，你可以編寫一個程式碼生成器，它接受一個型別併為該型別的切片生成一個 Reverse 函式。市面上有好幾個這樣的程式碼生成器。但這會給需要 Reverse 的每個包增加一個額外的步驟，使構建複雜化，因為所有不同的副本都必須編譯，並且修復主源中的 bug 需要重新生成所有例項，其中一些例項可能完全位於不同的專案中。
所有這些方法都足夠笨拙，以至於我認為大多數需要在 Go 中反轉切片的人只是為他們需要的特定切片型別編寫函式。然後他們需要為該函式編寫測試用例，以確保沒有犯像我最初犯的簡單錯誤。而且他們需要定期執行這些測試。
無論我們怎麼做，僅僅為了一個除了元素型別外看起來完全相同的函式，這意味著大量額外的工作。這並非說它做不到。顯然它可以做到，而且 Go 程式設計師正在這樣做。只是應該有更好的方法。
對於像 Go 這樣的靜態型別語言，更好的方法就是泛型。我前面寫過，泛型程式設計使得函式和資料結構能夠以泛型形式表示，並將型別引數化。這正是我們在這裡想要的。
泛型能為 Go 帶來什麼
在 Go 中，我們期望從泛型獲得的首要且最重要的事情是能夠編寫像 Reverse 這樣的函式，而無需關心切片的元素型別。我們希望將該元素型別引數化。然後我們可以只寫一次函式，只寫一次測試，將其放入一個可透過 go get 獲取的包中，並在需要時隨時呼叫。
更好的是，既然這是一個開源世界，其他人可以編寫一次 Reverse，而我們可以使用他們的實現。
此時我應該說明的是，“泛型”可以意味著許多不同的事物。在本文中，我所說的“泛型”就是我剛剛描述的。特別地，我指的不是 C++ 語言中的模板，C++ 模板支援的內容遠超我在此所述。
我詳細解釋了 Reverse 函式，但還有許多其他我們可以泛型地編寫的函式，例如：
- 查詢切片中的最小/最大元素
- 計算切片的平均值/標準差
- 計算 map 的並集/交集
- 查詢節點/邊圖中的最短路徑
- 對切片/map 應用轉換函式，返回新的切片/map
這些例子在大多數其他語言中都有。實際上，我是透過瀏覽 C++ 標準模板庫來寫下這個列表的。
還有一些例子是 Go 特有的，因為它對併發有強大的支援。
- 帶超時的 channel 讀取
- 將兩個 channel 合併成一個 channel
- 並行呼叫一系列函式，返回結果切片
- 使用 Context 呼叫一系列函式，返回第一個完成函式的결과，並取消和清理多餘的 goroutine
我見過所有這些函式被用不同的型別重複編寫多次。在 Go 中編寫它們並不難。但如果能夠複用一個適用於任何值型別的高效且已除錯的實現，那就太好了。
需要說明的是，這些只是例子。還有許多更通用的函式可以使用泛型更輕鬆、更安全地編寫。
此外，正如我前面寫到的，不只是函式。還有資料結構。
Go 語言內建了兩種通用的泛型資料結構：切片（slices）和 map。切片和 map 可以容納任何資料型別的值，並對儲存和檢索的值進行靜態型別檢查。值以其本身的形式儲存，而不是以介面型別儲存。也就是說，當我有一個 []int 時，切片直接儲存 int 值，而不是轉換為介面型別的 int 值。
切片和 map 是最有用的泛型資料結構，但它們並非唯一。這裡還有一些其他例子。
- 集合
- 自平衡樹，支援高效插入和按排序順序遍歷
- 多重 map（Multimap），一個鍵可以對應多個值例項
- 併發雜湊 map，支援並行插入和查詢且無需單一鎖
如果我們能編寫泛型型別，我們就可以定義新的資料結構，就像這些例子一樣，它們擁有與切片和 map 相同的型別檢查優勢：編譯器可以靜態檢查它們所持有值的型別，並且這些值可以以其本身的形式儲存，而不是以介面型別儲存。
也應該可以將前面提到的演算法應用於泛型資料結構。
所有這些例子都應該像 Reverse 一樣：作為泛型函式和資料結構，它們只需編寫一次，放在一個包中，並在需要時重複使用。它們應該像切片和 map 那樣工作，不應儲存空介面型別的值，而應儲存特定型別的值，並且這些型別應在編譯時進行檢查。
這就是 Go 可以從泛型中獲得的。泛型可以提供強大的構建塊，使我們能夠共享程式碼並更輕鬆地構建程式。
我希望我已經解釋了為什麼這值得深入研究。
好處與成本
但泛型並非來自糖果山（Big Rock Candy Mountain），那個每天陽光照耀在檸檬水泉水之上的土地。任何語言的改變都有代價。毫無疑問，將泛型新增到 Go 會使語言變得更復雜。與任何語言改變一樣，我們需要討論如何最大化收益並最小化成本。
在 Go 語言中，我們的目標是透過獨立、正交且可以自由組合的語言特性來降低複雜性。我們透過簡化單個特性來降低複雜性，並透過允許它們自由組合來最大化這些特性的益處。我們希望在泛型方面也能做到這一點。
為了使這一點更具體，我將列出我們應該遵循的一些準則。
最小化新概念
我們應該儘量少地向語言中新增新概念。這意味著最少的新語法和最少的新關鍵字及其他名稱。
複雜性應落在泛型程式碼的編寫者身上，而非使用者
應儘可能地將複雜性交給編寫泛型包的程式設計師。我們不希望包的使用者不得不擔心泛型。這意味著呼叫泛型函式應該以自然的方式進行，並且使用泛型包時出現的任何錯誤都應該以易於理解和修復的方式報告。除錯泛型程式碼的呼叫也應該很容易。
編寫者和使用者可以獨立工作
同樣，我們應該使泛型程式碼的編寫者和使用者能夠輕鬆地將各自的關注點分開，以便他們可以獨立開發程式碼。他們不應該像不同包中的普通函式編寫者和呼叫者那樣互相擔心對方在做什麼。這聽起來很顯而易見，但這並非適用於所有其他程式語言中的泛型。
短構建時間，快執行時間
當然，我們希望儘可能地保持 Go 目前提供的短構建時間和快執行時間。泛型往往會在快速構建和快速執行之間引入權衡。我們希望儘可能兼得。
保持 Go 的清晰度和簡潔性
最重要的是，Go 目前是一門簡單的語言。Go 程式通常清晰易懂。我們長期探索此領域的一個主要部分是試圖理解如何在保持這種清晰度和簡潔性的同時新增泛型。我們需要找到能很好地融入現有語言的機制，而不是將其變成完全不同的東西。
這些準則應適用於 Go 中的任何泛型實現。這是我今天想留給大家的最重要的資訊：泛型能為語言帶來顯著益處，但只有在 Go 語言依然像 Go 的前提下，泛型才值得去實現。
設計草案
幸運的是，我認為這是可以做到的。為了結束本文，我將從討論我們為什麼想要泛型及其要求，轉向簡要討論我們認為如何將它們新增到語言中的設計方案。
2022 年 1 月補充說明：此部落格文章寫於 2019 年，其中描述的泛型版本並非最終採用的版本。有關最新資訊，請參閱語言規範中關於型別引數的描述和泛型設計文件。
在今年的 Gophercon 大會上，Robert Griesemer 和我釋出了一份關於如何在 Go 中新增泛型的設計草案。請查閱草案瞭解全部細節。我將在此處介紹一些主要內容。
這是該設計中的泛型 Reverse 函式。
func Reverse (type Element) (s []Element) {
first := 0
last := len(s) - 1
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}
你會注意到函式體完全相同。只有簽名發生了變化。
切片的元素型別已被引數化。它現在命名為 Element，併成為了我們所說的型別引數。它不再是切片引數型別的一部分，而是一個獨立的、額外的型別引數。
要呼叫帶型別引數的函式，在一般情況下，你需要傳遞一個型別實參（type argument），它就像任何其他實參一樣，只不過它是一個型別。
func ReverseAndPrint(s []int) {
Reverse(int)(s)
fmt.Println(s)
}
這就是本例中在 Reverse 之後看到的 (int)。
幸運的是，在大多數情況下，包括本例，編譯器可以根據常規實參的型別推斷出型別實參，你根本不需要提及型別實參。
呼叫泛型函式看起來就像呼叫任何其他函式一樣。
func ReverseAndPrint(s []int) {
Reverse(s)
fmt.Println(s)
}
換句話說，儘管泛型 Reverse 函式比 ReverseInts 和 ReverseStrings 略微複雜，但這種複雜性落在了函式的編寫者身上，而不是呼叫者身上。
契約
由於 Go 是一種靜態型別語言，我們必須討論型別引數的型別。這種元型別（meta-type）告訴編譯器在呼叫泛型函式時允許使用哪些型別的實參，以及泛型函式可以用該型別引數的值執行哪些操作。
Reverse 函式可以處理任何型別的切片。它對 Element 型別的值唯一的操作是賦值，這在 Go 中適用於任何型別。對於這類非常常見的泛型函式，我們無需對型別引數進行特殊說明。
我們快速看一下另一個函式。
func IndexByte (type T Sequence) (s T, b byte) int {
for i := 0; i < len(s); i++ {
if s[i] == b {
return i
}
}
return -1
}
目前，標準庫中的 bytes 包和 strings 包都有一個 IndexByte 函式。這個函式返回序列 s 中 b 的索引，其中 s 可以是 string 或 []byte。我們可以使用這個單一的泛型函式來替代 bytes 和 strings 包中的這兩個函式。實際上我們可能不會去這樣做，但這一個有用的簡單例子。
這裡我們需要知道型別引數 T 的行為類似於 string 或 []byte。我們可以對它呼叫 len，可以對其進行索引，並且可以將索引操作的結果與位元組值進行比較。
為了讓它能夠編譯，型別引數 T 本身需要一個型別。它是一個元型別，但因為有時我們需要描述多個相關型別，並且它描述了泛型函式的實現與其呼叫者之間的關係，所以我們實際上將 T 的型別稱為契約（contract）。在這裡，該契約被命名為 Sequence。它出現在型別引數列表之後。
這就是本例中 Sequence 契約的定義方式。
contract Sequence(T) {
T string, []byte
}
這非常簡單，因為這是一個簡單的例子：型別引數 T 可以是 string 或 []byte。這裡的 contract 可能是一個新關鍵字，或者是在包範圍內識別的特殊識別符號；詳情請參閱設計草案。
任何記得我們在 Gophercon 2018 大會上提出的設計的人都會看到，這種編寫契約的方式要簡單得多。我們收到了很多關於早期設計的反饋，認為契約過於複雜，我們已努力將這些反饋考慮在內。新的契約更易於編寫、閱讀和理解。
它們允許你指定型別引數的基礎型別，和/或列出型別引數的方法。它們還允許你描述不同型別引數之間的關係。
帶方法的契約
這是另一個簡單的例子，一個函式使用 String 方法返回 s 中所有元素的字串表示形式的 []string 切片。
func ToStrings (type E Stringer) (s []E) []string {
r := make([]string, len(s))
for i, v := range s {
r[i] = v.String()
}
return r
}
這相當直接：遍歷切片，對每個元素呼叫 String 方法，並返回一個包含結果字串的切片。
這個函式要求元素型別實現 String 方法。Stringer 契約確保了這一點。
contract Stringer(T) {
T String() string
}
該契約簡單地表示 T 必須實現 String 方法。
你可能會注意到這個契約看起來像 fmt.Stringer 介面，因此值得指出的是，ToStrings 函式的引數不是 fmt.Stringer 的切片。它是一個某種元素型別的切片，其中該元素型別實現了 fmt.Stringer。元素型別切片和 fmt.Stringer 切片在記憶體表示上通常是不同的，並且 Go 不支援它們之間的直接轉換。因此，即使 fmt.Stringer 存在，這樣做也是值得的。
帶多個型別的契約
這是帶多個型別引數的契約示例。
type Graph (type Node, Edge G) struct { ... }
contract G(Node, Edge) {
Node Edges() []Edge
Edge Nodes() (from Node, to Node)
}
func New (type Node, Edge G) (nodes []Node) *Graph(Node, Edge) {
...
}
func (g *Graph(Node, Edge)) ShortestPath(from, to Node) []Edge {
...
}
這裡我們描述了一個由節點（nodes）和邊（edges）構成的圖。我們不要求圖使用特定的資料結構。相反，我們說 Node 型別必須有一個 Edges 方法，返回連線到該 Node 的邊列表。而 Edge 型別必須有一個 Nodes 方法，返回該 Edge 連線的兩個 Node。
我跳過了實現部分，但這展示了一個返回 Graph 的 New 函式的簽名，以及 Graph 上一個 ShortestPath 方法的簽名。
這裡重要的啟示是，契約不僅僅關乎單一型別。它可以描述兩個或更多型別之間的關係。
有序型別
關於 Go 的一個出人意料的常見抱怨是它沒有 Min 函式。或者，就此而言，也沒有 Max 函式。這是因為一個有用的 Min 函式應該適用於任何有序型別，這意味著它必須是泛型的。
雖然自己寫 Min 函式相當簡單，但任何有用的泛型實現都應該允許我們將其新增到標準庫。使用我們的設計方案，它看起來是這樣的。
func Min (type T Ordered) (a, b T) T {
if a < b {
return a
}
return b
}
Ordered 契約表明型別 T 必須是一個有序型別，這意味著它支援小於、大於等運算子。
contract Ordered(T) {
T int, int8, int16, int32, int64,
uint, uint8, uint16, uint32, uint64, uintptr,
float32, float64,
string
}
Ordered 契約僅僅是語言定義的所有有序型別的列表。此契約接受列表中的任何型別，或其基礎型別為其中之一的任何命名型別。基本上，就是任何你可以與小於運算子一起使用的型別。
事實證明，僅僅列舉支援小於運算子的型別比發明適用於所有運算子的新符號要容易得多。畢竟，在 Go 中，只有內建型別支援運算子。
同樣的方法可用於任何運算子，或者更廣泛地說，用於編寫任何旨在與內建型別一起使用的泛型函式的契約。它允許泛型函式的編寫者清晰地指定函式預期使用的型別集合。它讓泛型函式的呼叫者清晰地看到該函式是否適用於正在使用的型別。
實際上，這個契約很可能會進入標準庫，因此真正的 Min 函式（很可能也將在標準庫的某個地方）會是這樣的。這裡我們只是引用 contracts 包中定義的 Ordered 契約。
func Min (type T contracts.Ordered) (a, b T) T {
if a < b {
return a
}
return b
}
泛型資料結構
最後，我們來看一個簡單的泛型資料結構，二叉樹。在這個例子中，樹有一個比較函式，所以對元素型別沒有要求。
type Tree (type E) struct {
root *node(E)
compare func(E, E) int
}
type node (type E) struct {
val E
left, right *node(E)
}
這是建立新二叉樹的方法。比較函式被傳遞給 New 函式。
func New (type E) (cmp func(E, E) int) *Tree(E) {
return &Tree(E){compare: cmp}
}
一個未匯出的方法返回一個指標，指向持有 v 的位置，或指向 v 在樹中應放置的位置。
func (t *Tree(E)) find(v E) **node(E) {
pn := &t.root
for *pn != nil {
switch cmp := t.compare(v, (*pn).val); {
case cmp < 0:
pn = &(*pn).left
case cmp > 0:
pn = &(*pn).right
default:
return pn
}
}
return pn
}
這裡的細節並不重要，特別是我還沒有測試這段程式碼。我只是想展示編寫一個簡單的泛型資料結構看起來是什麼樣子。
這是測試樹是否包含某個值的程式碼。
func (t *Tree(E)) Contains(v E) bool {
return *t.find(e) != nil
}
這是插入新值的程式碼。
func (t *Tree(E)) Insert(v E) bool {
pn := t.find(v)
if *pn != nil {
return false
}
*pn = &node(E){val: v}
return true
}
請注意，型別 node 帶有一個型別實參 E。這就是編寫泛型資料結構的樣子。正如你所見，它看起來像是編寫普通的 Go 程式碼，只不過這裡那裡散佈著一些型別實參。
使用這棵樹非常簡單。
var intTree = tree.New(func(a, b int) int { return a - b })
func InsertAndCheck(v int) {
intTree.Insert(v)
if !intTree.Contains(v) {
log.Fatalf("%d not found after insertion", v)
}
}
這正是應有的樣子。編寫泛型資料結構稍微困難一些，因為你通常必須顯式地寫出支援型別的型別實參，但在儘可能的情況下，使用泛型資料結構與使用普通的非泛型資料結構沒有區別。
下一步
我們正在進行實際的實現，以便能夠對這個設計進行實驗。在實踐中嘗試設計非常重要，以確保我們能夠編寫我們想編寫的程式。進展不如我們希望的快，但隨著這些實現的可用，我們將釋出更多細節。
Robert Griesemer 已經編寫了一個初步的 CL，修改了 go/types 包。這使得我們可以測試使用泛型和契約的程式碼是否可以進行型別檢查。目前還不完整，但它主要適用於單個包，我們會繼續努力完善它。
我們希望人們使用這個和未來的實現來嘗試編寫和使用泛型程式碼，看看會發生什麼。我們想確保人們能夠編寫他們需要的程式碼，並能按預期使用它。當然，一開始並非所有事情都會順利，並且隨著我們探索這個領域，我們可能需要改變一些東西。此外，需要說明的是，我們更感興趣的是關於語義的反饋，而不是語法細節。
我想感謝所有對早期設計提出意見的人，以及所有討論 Go 中泛型可能是什麼樣子的人。我們閱讀了所有的評論，並非常感謝大家為此付出的努力。沒有這些努力，我們不可能取得今天的進展。
我們的目標是達成一個設計方案，使編寫我今天討論的泛型程式碼成為可能，同時不使語言變得過於複雜或不再像 Go。我們希望這個設計是邁向這個目標的一步，並且隨著我們從自身和大家的經驗中學習哪些可行、哪些不可行，我們期望繼續對其進行調整。如果確實達到了這個目標，那麼我們將有一個可以為未來的 Go 版本提出的方案。
下一篇文章：實驗、簡化、釋出
上一篇文章：宣佈新的 Go 商店上線
部落格索引