泛型和元編程的模型：Java- Go- Rust- Swift- D 等
在程序設計的時候，我們通常希望使用同樣的數據結構或算法，就可以處理許多不同類型的元素，比如通用的 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
endTerra 瘋狂的元編程能力讓它可以做很多事情，比如把特定領域語言的編譯器作爲簡單的函數來實現，或者用少量的代碼在庫中實現 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/
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/hX4NXK-jPCcNvhLUoTaKGw