引言

這是上週我在 Gophercon 2019 大會演講的部落格版本。

本文將討論將泛型新增到 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 方法，該方法返回一個元素。但實際上使用該方法必須返回一個空介面型別，然後我們就失去了靜態型別的所有好處。更微妙的是，將無法定義一個接受兩個具有相同元素型別的不同切片，或者接受一個型別為 A 的對映並返回一個相同型別 A 的切片的泛型函式。Go 是一種靜態型別語言，因為它更容易編寫大型程式；我們不想為了獲得泛型的好處而失去靜態型別的好處。

另一種方法是使用 reflect 包編寫一個通用的 Reverse 函式，但這非常麻煩且執行緩慢，因此很少有人這樣做。這種方法還需要顯式型別斷言，並且沒有靜態型別檢查。

或者，您可以編寫一個程式碼生成器，它接受一個型別併為該型別的切片生成一個 Reverse 函式。市面上有一些程式碼生成器就是這樣做的。但這會給每個需要 Reverse 的包增加一個額外的步驟，它會使構建複雜化，因為所有不同的副本都必須進行編譯，並且修復主原始碼中的 bug 需要重新生成所有例項，其中一些可能完全位於不同的專案中。

所有這些方法都足夠麻煩，以至於我認為大多數需要在 Go 中反轉切片的人只是為他們需要的特定切片型別編寫函式。然後他們需要為該函式編寫測試用例，以確保他們沒有犯像我最初那樣簡單的錯誤。他們還需要定期執行這些測試。

無論我們如何處理，這都意味著大量的額外工作，僅僅是為了一個除了元素型別不同而其他方面完全相同的函式。並不是說它做不到。它顯然可以做到，而且 Go 程式設計師也正在這樣做。只是應該有更好的方法。

對於像 Go 這樣的靜態型別語言，更好的方法就是泛型。我之前寫過，泛型程式設計能夠以通用的形式表示函式和資料結構，並將型別分離出來。這正是我們在這裡想要的。

泛型能為 Go 帶來什麼

我們在 Go 中從泛型中獲得的第一件也是最重要的事情是能夠編寫像 Reverse 這樣的函式，而不必關心切片的元素型別。我們希望將元素型別分離出來。然後，我們可以編寫一次函式，編寫一次測試，將它們放在一個 go-gettable 的包中，並隨時呼叫它們。

更好的是，由於這是一個開源世界，其他人可以編寫一次 Reverse，然後我們可以使用他們的實現。

這時我應該說，“泛型”可以有很多不同的含義。在本文中，我所說的“泛型”就是我剛才描述的。特別是，我不是指 C++ 語言中的模板，它支援比我在這裡寫的內容更多。

我詳細分析了 Reverse，但還有許多其他函式可以通用地編寫，例如

• 查詢切片中的最小/最大元素
• 計算切片的平均值/標準差
• 計算對映的並集/交集
• 查詢節點/邊圖中的最短路徑
• 將轉換函式應用於切片/對映，返回新的切片/對映

這些示例在大多數其他語言中都有。事實上，我是在瀏覽 C++ 標準模板庫時寫下這個列表的。

還有一些示例是 Go 特有的，因為它對併發有強大的支援。

• 帶超時的通道讀取
• 將兩個通道合併為一個通道
• 並行呼叫一系列函式，返回結果切片
• 呼叫一系列函式，使用 Context，返回第一個完成的函式的結果，取消並清理額外的 goroutine

我見過所有這些函式都用不同的型別寫了很多遍。在 Go 中編寫它們並不難。但能夠重用一個高效且經過除錯的、適用於任何值型別的實現將是很棒的。

需要明確的是，這些只是示例。還有許多其他通用函式可以使用泛型更輕鬆、更安全地編寫。

此外，正如我之前寫的，這不僅僅是函式。它也是資料結構。

Go 在語言層面內建了兩個通用的泛型資料結構：切片和對映。切片和對映可以儲存任何資料型別的元素，並且對儲存和檢索的值進行靜態型別檢查。值是按原樣儲存的，而不是作為介面型別。也就是說，當我有一個 []int 時，切片直接儲存 int，而不是轉換為介面型別的 int。

切片和對映是最有用的泛型資料結構，但它們並非唯一。以下是一些其他示例。

• 集合（Sets）
• 自平衡樹，具有高效的插入和按排序順序遍歷
• 多重對映（Multimaps），具有鍵的多個例項
• 併發雜湊對映，支援並行插入和查詢，沒有單一鎖

如果我們能夠編寫泛型型別，我們就可以定義新的資料結構，如這些，它們具有與切片和對映相同的型別檢查優勢：編譯器可以靜態型別檢查它們所包含的值的型別，並且值可以按原樣儲存，而不是作為介面型別。

還應該可以採用前面提到的演算法並將其應用於泛型資料結構。

這些示例都應該與 Reverse 類似：泛型函式和資料結構編寫一次，放在一個包中，並在需要時重用。它們應該像切片和對映一樣工作，即它們不應儲存空介面型別的值，而應儲存特定型別的值，並且這些型別應在編譯時進行檢查。

這就是 Go 透過泛型可以獲得的好處。泛型可以提供強大的構建塊，使我們能夠共享程式碼並更輕鬆地構建程式。

我希望我已經解釋了為什麼值得深入研究這一點。

優點和成本

但是泛型並非來自 糖果山樂園，那個太陽每天都照耀在 檸檬水泉 上的地方。每一次語言更改都有其成本。毫無疑問，將泛型新增到 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 稍微複雜一些，但這種複雜性由函式編寫者承擔，而不是呼叫者。

契約（Contracts）

由於 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 是 string 或 []byte。我們可以使用這個單一的泛型函式來替換 bytes 和 strings 包中的兩個函式。實際上，我們可能不會費心這樣做，但這只是一個有用的簡單示例。

這裡我們需要知道型別引數 T 的行為類似於 string 或 []byte。我們可以對其呼叫 len，可以對其進行索引，並且可以將索引操作的結果與位元組值進行比較。

為了讓它編譯，型別引數 T 本身需要一個型別。它是一個元型別，但由於我們有時需要描述多個相關型別，並且它描述了泛型函式的實現與其呼叫者之間的關係，因此我們實際上稱 T 的型別為契約。在這裡，契約的名稱是 Sequence。它出現在型別引數列表之後。

這是此示例中 Sequence 契約的定義方式。

contract Sequence(T) {
    T string, []byte
}

它非常簡單，因為這是一個簡單的示例：型別引數 T 可以是 string 或 []byte。這裡的 contract 可能是一個新關鍵字，或者是一個在包作用域中識別的特殊識別符號；請參閱設計草案瞭解詳情。

任何記得 我們在 2018 年 Gophercon 上提出的設計 的人會發現，這種編寫契約的方式要簡單得多。我們從早期設計中獲得了大量關於契約過於複雜的反饋，並已盡力將其考慮在內。新的契約寫起來、讀起來和理解起來都簡單得多。

它們允許您指定型別引數的基礎型別，以及/或列出型別引數的方法。它們還允許您描述不同型別引數之間的關係。

帶有方法的契約

這是另一個簡單的示例，一個使用 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 函式（可能也會在標準庫的某個地方）看起來會是這樣。這裡我們只是引用了 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 的槽的指標，或者指向樹中應該放置它的位置的指標。

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 未來版本的方案。