泛型和元编程的模型：Java, Go, Rust, Swift, D等
zhangxiafll 2020-11-13
在程序设计的时候，我们通常希望使用同样的数据结构或算法，就可以处理许多不同类型的元素，比如通用的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/
