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--
}
}
很簡單，但即使對於像這樣的簡單函式，你還是會想要撰寫幾個測試案例。事實上，當我這麼做時，我發現了一個錯誤。我確定許多讀者已經發現它了。
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。
現在讓我們反轉字串的片段。
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 方法，用來傳回元素。但是，要在實務上使用這個方法，它必須傳回一個空介面類型，然後我們便會失去靜態型別所帶來的好處。更巧妙的是，會沒有辦法定義一個接受兩個具有相同元素類型的不同切片做為參數的泛型函數，或是接受一個元素類型做為參數並傳回相同元素類型切片的泛型函數。Go 是一種靜態型別語言，原因在於這使得撰寫大型程式更容易；我們不希望為了獲得泛型的優點而失去靜態型別的優點。
另一種方法是使用 reflect 套件撰寫一個泛型 Reverse 函數，但是那樣撰寫起來很困難，執行起來也很慢，所以很少有人會這麼做。這種方法還需要明確的類型斷言，而且沒有靜態類型檢查。
或者，你可以撰寫一個接收類型並為該類型所切出來的切片產生 Reverse 函數的程式碼產生器。有幾個程式碼產生器可以做到這件事。但是，這會替需要 Reverse 的每個套件增加一個步驟，因為所有不同的複本都必須編譯，而且在主程式原始碼修正錯誤時，需要重新產生所有實例，其中某些實例可能完全在不同的專案中。
所有這些方法都夠難用，以致於我想大多數在 Go 中反轉切片的人，會直接為他們需要的特定切片類型撰寫函數。接下來他們需要為函數撰寫測試案例，以確保他們沒有犯一開始我犯過的那種簡單錯誤。而且他們需要定期執行那些測試。
然而，我們以何種方式執行這些操作，都表示對於一個函數而言，除了元素類型之外，外觀完全相同，這需要做很多額外的工作。這不是說這做不到。很明顯可以做到，而 Go 程式設計師也在這麼做。只不過應該有更好的方法。
對於像 Go 這樣的靜態型別語言來說，更好的方法就是泛型。先前我寫到泛型程式設計能夠以泛型形式表示函數和資料結構，而類別則不會受到影響。這正是我們這裡想要的。
泛型能夠帶給 Go 的東西
我們對 Go 中泛型的第一個也是最重要的想要的功能，就是在撰寫類似於 Reverse 的函數時，不用考慮切片的元素類型。我們要將元素類型分解出來。然後我們就可以寫一次函數，撰寫一次測試，將它們放入 go-gettable 套件中，並在我們需要時呼叫它們。
更棒的是，由於這是開放原始碼世界，其他人可以寫一次 Reverse，然後我們就可以使用他們的實作。
在這裡我應該說明「泛型」可以有很多不同的意思。在本文中，「泛型」的意思是我剛才描述的內容。特別是，我並不表示類似於 C++ 語言中發現的範本，它支援的內容比我這裡寫的還要多。
我詳細說明了 Reverse，但還有許多其他函數我們可以用泛型的形式撰寫，例如：
- 在切片中尋找最小/最大的元素
- 尋找切片的平均數/標準偏差
- 計算字典的聯集/交集
- 在節點/邊緣圖形中尋找最短路徑
- 對切片/字典套用轉換函數，傳回新的切片/字典
這些範例可以在大部分其他語言中找到。事實上，我透過一瞥 C++ 標準範本函式庫寫下了這份清單。
還有一些特別適用於 Go 的範例，因為 Go 強力支援並行處理。
- 在指定逾時時從通道讀取資料
- 將兩個通道合併成一個通道
- 平行呼叫一個函數清單，傳回結果切片
- 呼叫函數清單（使用 Context），傳回最先完成函數的結果，取消並清除其他 goroutine
我已經多次看到用不同類型撰寫的所有這些函數。它們很容易用 Go 撰寫。但是，能夠重複使用高效且經過除錯的實作（適用於任何值類型）會是一件很棒的事情。
講得更清楚，這些只是範例而已。還有更多一般通用的函數，使用泛型可以更輕鬆、更安全地撰寫這些函數。
而且，正如我之前寫的，這不只是函數。這也是資料結構。
Go 具有兩種內建於語言的一般通用泛型資料結構：切片和字典。切片和字典可以儲存任何資料類型的值，並針對儲存和檢索的值進行靜態類型檢查。這些值會儲存為它們本身，而不是介面類型。也就是說，當我有一個 []int 時，切片直接儲存 int，而不是轉換為介面類型的 int。
切片和字典是最有用的泛型資料結構，但它們並非唯一。以下是一些其他範例。
- 集合
- 自我平衡的樹狀結構，以排序順序進行有效插入和遍歷
- 具有多個關鍵個體的多重地圖
- 並行雜湊地圖，支援同時插入與查詢各種鎖定
如果我們可以撰寫一般類型，我們就可以定義新的資料結構，就像這些，這些一般的類型檢查優點與區塊和地圖一樣：編譯器可以靜態型態檢查他們所保存之值的類型，這些值可以儲存為他們自己，而不是介面類型。
應用演算法，就像前面提到的，並將其應用於一般資料結構也應該是可行的。
這些範例都應該和 Reverse 一樣：通用的函式與資料結構只撰寫一次，在套件中，並在需要的時候重複使用這些範例應可以像區塊和地圖一樣，不會儲存空介面類型的值，而應該儲存明確的類型，且這些類型應在編譯時檢查。
所以，這正是 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，並已成為我們稱之為類型參數的東西。它現在不是區段參數類型的一部分，而是一個獨立的、額外的類型參數。
要在具有類型參數的函數中呼叫函數，您通常會傳遞類型參數，它就像其他任何參數，只是類型不同。
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 是一種靜態類型語言，因此我們必須討論類型參數的類型。這個元類型會告訴編譯器呼叫泛函時允許傳遞哪種類型的類型參數，以及泛函可以使用類型參數的值來執行哪些類型的運算。
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 可以是 字串 或 []byte。我們可以使用此單一泛函來取代 bytes 和 strings 套件中的兩個函數。在實務上，我們可能不這麼做，但這是一個實用的簡單範例。
這裡我們需要知道類型參數 T 就像 字串 或 []byte。我們可以在它上面呼叫 len，我們可以對它進行索引，我們可以將索引操作的結果與位元組值比較。
要讓它編譯，類型參數 T 本身需要一個類型。它是一個元類型，但由於我們有時需要描述多個相關類型，而且由於它描述了泛函的實作與呼叫者之間的關係，所以我們實際上稱呼 T 的類型為合約。這裡，合約被命名為 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 {
...
}
這裡我們正在描述一個圖形，由節點和邊緣建構而成。我們沒有要求圖形的特定資料結構。相反地，我們表示 Node 型別必須具備 Edges 方法，傳回連接到 Node 的邊緣清單。而 Edge 型別則必須具備 Nodes 方法，傳回 Edge 連接的兩個 Nodes。
我略過了實作，但這顯示傳回 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 函式（也可能在標準函式庫中的某個地方）看起來會像這樣。在此，我們只是參照在契約封裝中定義的 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 商店
部落格索引