[[351974]]

在程序設計的時候，我們通常希望使用同樣的數據結構或算法，就可以處理許多不同類型的元素，比如通用的List或只需要實現compare函數的排序算法。對于這個問題，不同的編程語言已經提出了各種各樣的解決方案：從只是提供對特定目標有用的通用函數(如C，Go)，到功能強大的圖靈完備的通用系統(如Rust，C++)。在本文中，我將帶你領略不同語言中的泛型系統以及它們是如何實現的。我將從C這樣的不具備泛型系統的語言如何解決這個問題開始，然后分別展示其他語言如何在不同的方向上逐漸添加擴展，從而發展出各具特色的泛型系統。

泛型是元編程領域內通用問題的簡單案例：編寫可以生成其他程序的程序。我將描述三種不同的完全通用的元編程方法，看看它們是如何在泛型系統空的不同方向進行擴展：像Python這樣的動態語言，像Template Haskell這樣的過程宏系統，以及像Zig和Terra這樣的階段性編譯。

概述

下圖包含了本文討論的所有語言的泛型系統，用以概述本文主要內容以及它們是如何結合在一起的。

基本想法

假設我們用一種沒有泛型系統的語言進行編程，我們想實現一個通用的堆棧數據結構，它對任何數據類型都有效。困難在于我們寫的每一個函數和類型定義都只對那些大小相同、復制方式相同、行為相同的數據有效。

如何解決這個問題?有兩個基本的想法，一是想辦法讓所有數據類型在我們的數據結構中有同樣的行為方式，二是對我們的數據結構進行多份拷貝，并稍作調整，以特定的方式處理每種數據類型。這兩個想法構成了兩大類解決泛型問題的基礎方法，即"裝箱 "和 "單態化"。

裝箱是指我們把所有的東西都放在統一的 "盒子 "里，使它們的行為方式都一樣。通常是通過在堆上分配內存，只在數據結構中放指針來實現的。我們可以讓不同類型的指針有同樣的行為方式，這樣，同樣的代碼就可以處理所有的數據類型了。然而這種做法可能要付出額外的內存分配、動態查找和緩存丟失的代價。在C語言中，這相當于讓你的數據結構存儲void*指針，也需要將你的數據指針轉換為void*或從void*進行類型轉換(如果數據還沒有在堆上，則在堆上分配)。

單態化是針對我們要處理的不同類型的數據，多次復制代碼。這樣每份代碼都直接使用對應的數據結構和函數，而不需要任何動態查找。這樣運行效率足夠快，但代價是代碼大小和編譯時間的膨脹，因為同樣的代碼只要稍加調整就會被編譯多次。在C語言中，這相當于在一個宏中定義你的整個數據結構，并為在使用該結構的地方調用該宏。

總的來說，裝箱有利于縮短編譯時間，但會損害運行時性能，而單態化會生成的代碼運行期效率高，但需要額外的時間來編譯和優化生成的代碼。當然它們在如何擴展方面這方面也有所不同。裝箱允許在運行時有更多的動態行為，而單態化則可以更靈活地處理通用代碼的不同實例。另外值得注意的是，在一些大型程序中，單態化的性能優勢可能會被額外生成的代碼所帶來的額外指令導致緩存未命中所抵消。

兩個基礎流派中的每一個流派都有很多方向可以擴展，以增加額外的能力或安全性，不同的語言已經將兩者帶入了非常有趣的方向。有些語言如Rust和C#甚至提供了這兩種選擇!

裝箱

讓我們以go語言為例：

type Stack struct { 
  values []interface{} 
} 
 
func (this *Stack) Push(value interface{}) { 
  this.values = append(this.values, value) 
} 
 
func (this *Stack) Pop() interface{} { 
  x := this.values[len(this.values)-1] 
  this.values = this.values[:len(this.values)-1] 
  return x 
} 

使用裝箱的語言示例。C(void*)、Go(interface{})、無泛型的Java(Object)、無泛型的Objective-C(id)

基于類型擦除裝箱的泛型

這里有一些基礎裝箱的問題。

• 根據語言的不同，我們經常需要在每次讀寫數據結構的時候，進行類型轉換。
• 很難阻止使用者將不同類型的元素放入數據結構中，這可能會導致運行時異常。

解決方法是在類型系統中增加泛型功能，同時在運行時仍然和以前一樣完全使用基本裝箱方法。這種方法通常被稱為類型擦除，因為類型系統中的類型都被 "擦除 "了，都變成了同一類型(比如Object)。

Java和Objective-C一開始都是使用基礎裝箱，后來又增加了基于類型擦除的泛型功能，為了兼容，甚至使用了和以前完全一樣的集合類型，但可以選擇泛型參數。請看下面的例子，其來自維基百科上關于Java泛型的文章。

List v = new ArrayList(); 
v.add("test"); // A String that cannot be cast to an Integer 
Integer i = (Integer)v.get(0); // Run time error 
 
List<String> v = new ArrayList<String>(); 
v.add("test"); 
Integer i = v.get(0); // (type error) compilation-time error 

具有統一表達方式的推斷裝箱泛型

OCaml將這個想法更進一步，采用統一的表示方式，沒有需要額外裝箱分配的基元類型(就像Java中int需要變成Integer才能進入ArrayList一樣)，因為所有的對象要么已經被裝箱，要么用一個指針大小的整數表示，所以一切都是一個機器字。然而當垃圾收集器查看存儲在通用結構中的數據時，它需要區分指針和整數，所以用1位(指針不會有這1位)來標記整數，只留下31位或63位的范圍。

OCaml還有一個類型推理系統，所以你可以寫一個函數，如果你不注釋它，編譯器會推斷出最通用的類型，這可能導致函數看起來像動態類型語言。

let first (head :: tail) = head(* inferred type: 'a list -> 'a *) 

推斷類型會推斷出 "從類型為'a'的元素列表到類型為'a'的元素的函數"。該代碼確認了這樣的關系：返回類型與列表類型相同，但可以是任何類型。

接口

基礎裝箱方法的另一個限制是，裝箱類型是完全不透明的。這對于堆棧這樣的數據結構來說是沒有問題的，但是像通用排序函數這樣的功能需要一些額外的函數，比如特定類型的比較函數。有很多不同的方式可以在運行時實現并在語言中導出該功能，你可以在同一種語言中使用多種方式。然而不同的語言大多數采用某種特定方式實現，然后語言擴展則充分利用所選實現的優勢。這意味著基于著不同的運行時方法，主要有兩個選擇：vtables和字典傳遞。

接口vtables

如果我們想暴露類型特化的函數，同時又要堅持裝箱策略，那么我們只要確保有統一的方法可以從對象中找到給定類型的函數就可以了。這種方法叫做 "vtables"(由 "虛擬方法表 "縮寫而來)，它的實現方式是，在通用結構中的每個對象的偏移量為0的地方，都有一個指向函數指針表的指針。這些表通過在固定的偏移量處索引某些指針，讓通用代碼以同樣的方式為每個類型查找特定類型的函數指針。

譯者注，圖示如下：

這就是Go中接口類型的實現方式，以及Rust中dyn trait對象的實現方式。當你把一個類型轉換為一個接口類型時，它會創建一個包裝器，這個包裝器包含一個指向原始對象的指針和一個指向該接口特定類型函數的vtable的指針。然而這需要額外的指針和內存，這也是為什么Go中的排序需要切片實現Sort.Interface接口，而非切片元素實現Comparable接口。

譯者注：

Go 語言對slice進行排序，需要在slice(切片)上實現Sort.Interface接口，如下所示：

type Interface interface { 
    Len() int    // Len 為集合內元素的總數 
    Less(i, j int) bool　//如果index為i的元素小于index為j的元素，則返回true，否則返回false 
    Swap(i, j int)  // Swap 交換索引為 i 和 j 的元素 
} 

使用方式：

package main 
  
import ( 
    "fmt" 
    "sort" 
) 
  
//定義interface{},并實現sort.Interface接口的三個方法 
type IntSlice []int 
  
func (c IntSlice) Len() int { 
    return len(c) 
} 
func (c IntSlice) Swap(i, j int) { 
    c[i], c[j] = c[j], c[i] 
} 
func (c IntSlice) Less(i, j int) bool { 
    return c[i] < c[j] 
} 
func main() { 
    a := IntSlice{1, 3, 5, 7, 2} 
    b := []float64{1.1, 2.3, 5.3, 3.4} 
    c := []int{1, 3, 5, 4, 2} 
    fmt.Println(sort.IsSorted(a)) //false 
    if !sort.IsSorted(a) { 
        sort.Sort(a)  
    } 
    if !sort.Float64sAreSorted(b) { 
        sort.Float64s(b) 
    } 
    if !sort.IntsAreSorted(c) { 
        sort.Ints(c) 
    } 
    fmt.Println(a)//[1 2 3 5 7] 
    fmt.Println(b)//[1.1 2.3 3.4 5.3] 
    fmt.Println(c)// [1 2 3 4 5] 
} 

對于Java來說，對數組排序需要在數組/集合元素上實現Comparable 接口，代碼如下：

class Simpson implements Comparable<Simpson> { 
    String name; 
 
    Simpson(String name) { 
        this.name = name; 
    } 
 
    @Override 
    public int compareTo(Simpson simpson) { 
        return this.name.compareTo(simpson.name); 
    } 
} 
 
public class SimpsonSorting { 
 
     public static void main(String... sortingWithList) { 
        List<SimpsonCharacter> simpsons = new ArrayList<>(); 
        simpsons.add(new SimpsonCharacter("Homer ")); 
        simpsons.add(new SimpsonCharacter("Marge ")); 
        simpsons.add(new SimpsonCharacter("Bart ")); 
        simpsons.add(new SimpsonCharacter("Lisa ")); 
 
        Collections.sort(simpsons); 
        simpsons.stream().map(s -> s.name).forEach(System.out::print); 
 
        Collections.reverse(simpsons); 
        simpsons.stream().forEach(System.out::print); 
    } 
 
} 

面向對象編程

面向對象編程語言很好地利用了vtables的力量。像Java這樣的面向對象語言沒有獨立的包含vtables的接口對象，而是在每個對象的開頭有一個vtable指針。類似Java的語言有繼承和接口系統，完全可以用這些對象vtables來實現。

除了提供額外的功能外，在每個對象中嵌入vtables還解決了之前需要構造新類型的問題。與Go不同的是，在Java中，排序函數可以使用該類型上的Comparable接口。

反射

一旦你有了vtables，就可以讓編譯器也生成其他類型信息，如字段名、類型和位置，這些都不困難。這樣就可以用同樣的代碼訪問一個類型中的所有數據，而這些代碼可以檢查其他任何類型中的數據。就可以添加 "反射 "功能，它可以用來實現任意類型的序列化等功能。作為裝箱范式的擴展，它有同樣的問題，即它只需要一份代碼，但需要大量動態查找，這可能會導致序列化性能很低。

具有反射功能的語言以及將其用于序列化的例子包括Java、C#和Go。

動態類型語言

反射是非常強大的，可以完成很多不同的元編程任務，但有一點它不能做，那就是創建新的類型或編輯現有字段的類型信息。如果我們增加了這樣的能力，并通過反射來實現，最終就會得到動態類型語言。在Python和Ruby這樣的語言中，其超強的反射系統會帶來驚人的元編程能力，并且使用其元編程能力的代碼無處不在。

"但是Tristan，動態語言不是這樣工作的，他們只是用哈希表來實現一切!"有人可能會這么說。好吧，哈希表只是一個用于實現可編輯的類型信息表的數據結構。而且，這只是某些像CPython這樣的解釋器的工作方式。如果你看一眼像V8這樣的高性能JIT是如何實現的，它的做法就類似vtables和反射信息! V8的隱藏類(vtables和反射信息)和對象布局與你在Java虛擬機中看到的類似，只是對象能夠在運行時改為新vtable。

字典傳遞

除了將vtables與對象關聯起來，實現動態接口的另一種方式是將所需的函數指針表傳遞給需要它們的通用函數。這種方法在某種程度上類似于在調用時構造Go式的接口對象，只是將函數指針表作為一個隱藏的參數傳遞，而不是作為現有的參數之一打包在一起。

這種方式雖然被Haskell類型類使用，但GHC(GHC是Haskell編譯器)通過內聯和特殊化，也可以做單態化優化。字典傳遞這種方式也被OCaml使用，其以一等模塊的形式提供一個顯式參數傳遞字典，但也有建議增加隱式參數的機制。

Swift Witness Tables

Swift的泛型實現更加有趣，通過使用字典傳遞，同時把類型的大小以及如何移動、復制和釋放它們放到函數指針表中，該表可以提供所有所需的信息，以統一的方式處理任何類型，而不需要裝箱。這樣一來，Swift就可以在沒有單態化的情況下實現泛型，也不需要把所有的類型都使用統一的表達。雖然仍然存在所有動態查找成本，然而也節省了分配內存、內存和緩存不連貫的成本。Swift編譯器能夠在模塊內和跨模塊使用注解為@inlinable的函數進行單態化處理(monomorphize)和內聯泛型，以避免這些成本，其使用啟發式算法來估算代碼會膨脹多少。

此功能還解釋了Swift為何以允許在結構體中添加和重新排列字段的方式實現ABI穩定性，盡管它們出于性能原因提供@frozen屬性以選擇退出動態查找。

內涵類型分析

還有一種為裝箱類型實現接口的方法是在對象的固定部分添加類型ID，就像vtable指針會訪問的位置，然后為每個接口方法生成函數，在所有實現該接口方法的類型上有一個大的switch語句，并派發到正確的特定類型方法。

我不知道有什么語言使用這種技術，但是C++編譯器和Java虛擬機在使用profile-guided優化來了解某個通用調用點主要作用于某些類型的對象時，會做類似的事情。他們會對每個通用類型檢查以代替調用點，然后對該通用類型進行靜態調度，通常的動態調度作為后備情況。這樣分支預測器就可以預測出將采取的通用情況分支，并通過靜態調用繼續調度指令。

單態化

另一種泛型的實現方法是單態化。在這種方式中，需要找到某種方法來為每種類型輸出多個版本的代碼。編譯器在編譯時，代碼會經過多個表達階段，理論上我們可以在其中任何一個階段進行復制。

生成源代碼

單態化最簡單的方法就是在源代碼層面就進行復制。這樣編譯器甚至不需要支持泛型，C和Go等(編譯器不支持泛型)語言的用戶有時會這樣做。

在C語言中，你可以使用預處理程序，在宏或頭文件中定義你的數據結構，并多次包含#defines。在Go中，有像genny這樣的腳本，可以簡化代碼生成的過程。

這樣做的缺點是，復制源代碼會有很多弊端和邊緣情況需要注意，對基本相同的代碼進行多次解析和類型檢查也給編譯器帶來很多額外的工作。其次根據語言和工具的不同，這種泛型方法寫起來和用起來都會很丑，比如說如果你在C語言宏里面寫一個宏，每一行都要以反斜杠結尾，而且所有的類型和函數名都需要手動連接上標識符以避免碰撞。

D string mixins

不過代碼生成確實有一些好處，那就是你可以使用全能的編程語言來生成代碼，而且它使用的是用戶已經熟悉的方法。

一些以其他方式實現泛型功能的語言也包含了一種干凈的代碼生成方式，以解決其泛型系統沒有涵蓋的更一般的元編程用例。最明顯的例子是D 語言的string mixin，它可以在編譯中間使用D的所有功能將D代碼生成為字符串。

Rust 過程宏

還有一個類似的例子是Rust的過程宏，它將token流作為輸入，輸出token流，同時提供程序將token流轉換為字符串或者從字符串轉換為token流。這種方法的優點是token流可以保存源代碼位置信息。使用宏就可以直接將用戶寫的代碼以token的形式從輸入粘貼到輸出，如果用戶的代碼在宏輸出中引起編譯器錯誤，編譯器輸出的錯誤信息將正確地指向用戶代碼所在的文件、行和列，但如果宏生成了錯誤，那么錯誤信息將指向宏調用。例如如果在日志調用中使用了一個封裝函數的宏，而在封裝函數的實現中出錯，編譯器的錯誤將直接指向錯誤所在的你的代碼，而非指向宏。

語法樹宏

有些語言確實更進一步，提供了在宏中消費和產生抽象語法樹(AST)類型的功能。這方面的例子包括模板Haskell、Nim macros、OCaml PPX和幾乎所有的Lisps。

AST宏的問題是，你不希望用戶學習一堆構造AST類型的函數。Lisp系列語言解決了這個問題，其語法和AST有非常直接的對應關系，但構造過程仍然會很繁瑣。因此，我提到的所有語言都有某種形式的 "引用 "原語，你在語言中提供一個代碼片段，它就會返回語法樹。這些引用原語也提供方法來拼接語法樹的值，就像字符串拼接一樣。下面是模板Haskell中的一個例子。

-- using AST construction functions 
genFn :: Name -> Q Exp 
genFn f = do 
  x <- newName "x" 
  lamE [varP x] (appE (varE f) (varE x)) 
 
-- using quotation with $() for splicing 
genFn' :: Name -> Q Exp 
genFn' f = [| \x -> $(varE f) x |] 

在語法樹級別而不是token級別做過程宏的一個缺點是，語法樹類型經常會隨著新的語言特性增加而改變，而token類型可以保持兼容。例如OCaml的PPX系統需要特殊的基礎設施來遷移解析樹到宏所使用的語言版本中去。而Rust的相關庫則增加了解析和引用實用程序，因此你可以用類似過程宏的風格來編寫語法樹宏。Rust甚至有一個實驗性的庫，通過這種方式提供反射功能。

模板

下一種泛型的實現方式，是把生成代碼推進到編譯的下一階段。在C++和D中使用的模板使用這種方式，你可以在類型和函數上指定 "模板參數"，當你實例化一個具有特定類型的模板時，該類型會被替換到函數中，然后對函數進行類型檢查，以確保組合是有效的。

template <class T> T myMax(T a, T b) { 
  return (a>b?a:b); 
} 
 
template <class T> struct Pair { 
  T values[2]; 
}; 
 
int main() { 
  myMax(5, 6); 
  Pair<int> p { {5,6} }; 
  // This would give us a compile error inside myMax 
  // about Pair being an invalid operand to `>`: 
  // myMax(p, p); 
} 

模板系統的問題是，如果你在你的庫中包含一個模板函數，而用戶用錯誤的類型實例化它，其編譯錯誤難以理解。這與動態類型語言中的庫在處理用戶傳遞錯誤類型時可能發生的情況非常相似。D語言有一個有趣的解決方法，也與動態語言中流行的做法類似：只需使用幫助函數來檢查類型是否有效，如果失敗的話，錯誤信息會指向幫助函數! 下面是D語言中的例子。

// We're going to use the isNumeric function in std.traits 
import std.traits; 
 
// The `if` is optional (without it you'll get an error inside like C++) 
// The `if` is also included in docs and participates in overloading! 
T myMax(T)(T a, T b) if(isNumeric!T) { 
    return (a>b?a:b); 
} 
 
struct Pair(T) { 
  T[2] values; 
} 
 
void main() { 
  myMax(5, 6); 
  Pair!int p = {[5,6]}; 
  // This would give a compile error saying that `(Pair!int, Pair!int)` 
  // doesn't match the available instance `myMax(T a, T b) if(isNumeric!T)`: 
  // myMax(p, p); 
} 

C++20有一個叫做 "概念(concepts) "的功能，除了設計上更像定義接口和類型約束外，它的作用是一樣的。

編譯期函數

D的模板有很多擴展，允許你使用編譯期函數評估和靜態if等功能，可以使模板的行為就像函數一樣，在編譯時接受一組參數，并返回一個非通用的運行時函數。這使得D模板成為功能齊全的元編程系統，據我了解，現代C++模板也有類似的功能，但實現機制不夠干凈。

還有一些語言把 "泛型只是編譯期函數 "的概念更進一步的運行，比如Zig。

fn Stack(comptime T: type) type { 
    return struct { 
        items: []T, 
        len: usize, 
 
        const Self = @This(); 
        pub fn push(self: Self, item: T) { 
            // ... 
        } 
    }; 
} 

Zig在編譯時和運行時都使用同一種語言，函數根據是否標記為comptime的參數進行區分。還有一種語言，在元級(meta level)使用單獨的但類似的語言，叫Terra。Terra是Lua的一種方言，它允許你構建類似C語言的低級函數，然后使用Lua API以及引用和拼接原語言在元級來操作它們。

function MakeStack(T) 
    local struct Stack { 
        items : &T; -- &T is a pointer to T 
        len : int; 
    } 
    terra Stack:push(item : T) 
        -- ... 
    end 
    return Stack 
end 

Terra瘋狂的元編程能力讓它可以做很多事情，比如把特定領域語言的編譯器作為簡單的函數來實現，或者用少量的代碼在庫中實現Java和Go的接口和對象系統。然后它可以將生成的運行時代碼保存為無依賴的對象文件。

Rust 泛型

下一種類型的單態化泛型，是在類型檢查之后，把代碼生成的過程再推進一步。上文提到用C++可以像動態類型語言中的獲取泛型庫函數內的錯誤類型，這是因為模板參數中基本只有一種類型。所以這就意味著我們可以通過在我們的元級中增加類型系統來解決這個問題，并靜態檢查它們是否支持你使用的操作。這就是泛型在Rust中的工作方式，在語言層面來說也是Swift和Haskell中泛型的工作方式。

在Rust中，你需要在你的類型參數上聲明 "trait bounds"，其中trait就像其他語言中的接口一樣，聲明了類型提供的一系列函數。Rust編譯器會檢查你的泛型函數的主體是否能與任trait bounds的類型一起工作，也不允許你使用trait bounds沒有聲明的函數。這樣Rust中泛型函數在實例化時，就永遠不會在庫函數得到編譯器錯誤。編譯器也只需要對每個泛型函數進行一次類型檢查。

fn my_max<T: PartialOrd>(a: T, b: T) -> T { 
    if a > b { a } else { b } 
} 
 
struct Pair<T> { 
    values: [T; 2], 
} 
 
fn main() { 
    my_max(5,6); 
    let p: Pair<i32> = Pair { values: [5,6] }; 
    // Would give a compile error saying that 
    // PartialOrd is not implemented for Pair<i32>: 
    // my_max(p,p); 
} 

在語言層面上，以裝箱方式實現的泛型所需要的類型系統和這個十分類似，這也是為什么Rust可以使用同一個類型系統來支持這兩種泛型的原因! Rust 2018甚至增加了統一的語法，其中v: &impl SomeTrait參數會被單態化，但v: &dyn SomeTrait參數會使用裝箱。這一方式也讓Swift的編譯器和Haskell的GHC等編譯器即使默認使用裝箱來實現泛型，也可以單態化作為優化手段。

機器碼單態化

單態化泛型的下一步是在編譯器后端中進一步推進。就像我們可以復制帶有泛型類型占位符的源代碼模板一樣，我們可以生成帶有特定類型占位符的機器代碼。然后我們就可以像鏈接器的一樣工作，通過memcpy和一些補丁，很快就可以把這些模板標記出來! 其缺點是每個單態化的副本不能被優化器特別優化，然而因為沒有重復優化，所以編譯速度可以快很多。我們甚至可以把代碼stamper做成一個小小的JIT，被包含在二進制文件中，并在運行時把單態化的副本標記出來，以避免二進制文件的膨脹。

其實我并不知道有哪種語言的泛型是這樣工作的，這只是我在寫作本文時的一個想法，作為這個分類法的自然延伸，這也正是我希望從中得到的東西! 我希望這篇文章能讓你更清楚地了解不同語言中的泛型系統，以及如何對他們分類，并促進你的思考，也許我們可能會發現新的酷炫的編程語言的方向。

原文地址：

https://thume.ca/2019/07/14/a-tour-of-metaprogramming-models-for-generics/

本文轉載自微信公眾號「高可用架構」，可以通過以下二維碼關注。轉載本文請聯系高可用架構公眾號。