avatar

目录
[译]泛型——通往元编程之路

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

自顶向下全面总结了泛型在各个语言中是如何存在的。

翻译:Hydrogen5


泛型与元编程模型:以Go、Rust、D与Swift等为例

在某些编程领域,通常会编写一个适配多种不同类型的数据结构或算法,例如泛型list或仅接受一个比较函数的排序算法。关于这个问题,各种编程语言几乎已经想到了所有解决方法:从只是让程序员依靠对解决问题有帮助的已有的通用功能 (如C, Go)到甚至可以做到图灵完备的泛型系统(如Rust, C++)。在本文中我将谈谈关于各类语言的泛型系统以及它们分别是如何实现的。首先,我会从C这种没有专门泛型系统的语言的解法开始,接着说明如何逐步向不同方向扩展最终到达其他语言的实现。

我之所以认为泛型是个有趣的角度,原因之一是它们是一般意义上的元编程问题的缩影:编写可以生成其它程序的程序。作为例证,我将说明如何将三种互不相同但是完全通用的元编程方法看作是泛型系统领域中不同方向的衍生:Python等动态语言,Haskell一类的过程宏系统,以及ZigTerra这样的分段编译。

概览

我制作了所有提及到的系统的流图用以概述本文将包含的内容以及所有内容是如何结合起来的:

基本思路

假设我们正在使用一种没有泛型的语言进行编程,并且我们想创建一个适用于任何数据类型的泛型Stack。问题来了,我们编写的所有函数和类型的定义仅适用于有着相同的大小,相同的拷贝方式并且通常有着相同的运行方式的数据。

解决这个问题通常有两个想法,其一是找到一种方法,使所有数据类型在我们的数据结构中以相同的方式运行,其二是对我们的数据结构做多个实现,并进行一些细微调整以正确处理每种数据类型。这两者构成了泛型解决方案的两大基础方向:“装箱”和“单态化”。

装箱是将所有物品放入统一的“盒子”中,以使它们运行一致。通常,这是在堆上分配内容并仅在数据结构中存放指针。我们可以使指向所有不同类型的指针以相同的方式起作用,以使相同的代码可以处理所有数据类型!但是,这样做的代价可能是额外的内存分配,动态分发和缓存失效。在C语言中,这相当于在数据结构中存储void*指针,并且仅将数据在其他对象和void*之间进行转换(如果数据还不在堆上,则在堆上分配)。

单态化是针对要实例化的不同类型的数据复制多份代码的方法。这样,每个实例都可以直接使用其所要处理的数据的方法,而无需任何动态分发。这样可以产生效率最高的代码,但是代价是目标代码大小和编译时间的上升,这是因为仅有微小不同的同一代码被多次编译了。在C语言中,这通常是在宏中定义整个数据结构并为每种要使用它的类型调用它。

总的来说,最后的结论是装箱会带来更短的编译时间,但会降低运行时性能,而单态化将生成最快的代码,但会花费额外的时间来编译和优化所有不同的生成实例。它们在扩展方式上也有所不同:装箱扩展允许在运行时具有更多动态行为,而单态化对于不同实例的差别有着更为灵活的适应。还值得注意的是,在某些较大的程序中,额外生成的代码产生的额外指令容易导致缓存失效,这可能会抵消单态化的性能优势。

这些泛型思路中的每一个都有很多可以扩展的方向,以获得附加的功能与安全性,并且不同的语言将它们发展到了各种有趣的方向。而Rust和C#之类的某些语言甚至同时提供了这两种选择。

装箱

让我们从Go中的基础装箱方法的示例开始:

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 Generics的Wikipedia文章的以下示例:

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还具有类型推断系统,因此您可以编写函数而不标注大部分类型,编译器将推断最可能的类型,这使它看起来很像动态类型语言:

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

推断的类型可以念作“从任意'a类型列表到任意'a类型元素的函数”。返回类型与列表类型必须相同,但可以是任何类型。

接口

基础装箱方法的另一个限制是箱子里的类型是完全不透明的。这对于像Stack这样的数据结构来说无关紧要,但是诸如排序之类的东西需要一些额外的功能,例如特定类型的比较函数。有多种不同的方式既可以在运行时实现此目标,又可以在编写时就公开它,这在技术上是不同的,您可以使用多种方法来实现同一语言。但是,不同的语言特性大多倾向于以一种特定方式实现,然后语言扩展从所选实现获得了各自的优势。这意味着主要有两种语言家族,分别基于不同的运行时方法:vtable和字典传递。

接口vtable

如果我们想在使用统一的处理所有事物的装箱策略的同时暴露特定类型的函数,我们可以确保有一种统一的方法从对象中找到所需的特定类型的函数。这种方法被称为使用“ vtables”(“虚拟方法表”,但没有人使用全名),其实现方式是,在通用结构中每个对象的偏移量为零时,该指针指向某些布局一致的函数指针表。这些表允许通用代码通过以固定偏移量索引某些指针,从而针对每种类型以相同的方式查找指向特定于类型的函数的指针。

这就是interface在Go中实现类型以及dyn trait在Rust中实现对象的方式。当类型转换为要实现的接口类型时,它将创建一个包装器,该包装器包含一个指向原始对象的指针和一个指向该接口的特定类型的函数的vtable的指针。但是,这需要额外一层指针和额外的布局,这就是为什么Go中的排序使用带有Swap方法的容器接口而不是获取Comparable接口的切片的原因,因为这将需要分配一个新的接口类型的切片并在之上排序,而非原始切片!

面向对象编程

面向对象编程是一种语言特性,可以充分利用vtable的功能。像Java这样的面向对象语言没有包含vtable的单独接口对象,而是在每个对象的开头都有一个vtable指针。类Java语言具有继承系统和接口,完全可以使用这些对象vtables来实现。

除了提供附加功能外,将vtable嵌入每个对象还解决了先前的问题,即需要使用解引用构造新的接口类型。与Go 不同,Java中sorting函数只能在实现Comparable的类型上使用接口。

反射

一旦有了vtable,让编译器还生成带有其他类型信息的表(例如字段名称,类型和位置)就不太困难了。这允许使用相同代码检查一种类型的所有数据。因此可以用来向语言添加“反射”特性,用于实现序列化和任意类型的修饰打印等功能。作为装箱范式的扩展,它具有相同的得失,即它只需要一个代码副本,但是需要大量缓慢的动态分发,这可能会导致序列化性能降低。

依靠具有反射特性实现序列化和其他功能的典型语言包括Java,C#和Go。

动态类型语言

反射非常强大,可以实现许多不同的元编程功能,但是它不能创建新类型或编辑现有值的类型信息。如果我们添加了执行此操作的特性,并且使默认访问和修改语法通过反射实现,那么最终将获得动态类型的语言!Python和Ruby之类的语言通过有效的,功能强大的反射系统进行元编程,获得了难以置信的灵活性,足以做到任何事。

“但是兄啊,动态语言不是这样实现的,它们只是用哈希表实现所有内容!” 你可以说。好吧,哈希表只是好的用于实现可编辑类型信息表的数据结构!而且,这就是某些像CPython这样的解释器的工作方式。如果你看一看像V8这样的高性能JIT是如何实现的,会发现它看起来很像vtables和反射信息!V8的隐藏类(vtable和反射信息)和对象布局与你在Java VM中看到的可能很类似,只是具有在运行时修改对象vtable的功能。这不是巧合,因为从来没有巧合:在Wikipedia上列为V8的创建者的人以前曾参与高性能Java VM的研发

字典传递

除了将vtable与对象关联之外,实现动态接口的另一种方法是将所需函数指针的表传递给需要它们的通用函数。这种方法类似于在调用点上构造Go风格的接口对象,只是该表作为隐藏参数传递,而不是作为现有参数之一打包到包中。

尽管GHC可以通过内联和专用化来进行单态式优化,但Haskell类型类仍使用此方法。OCaml还以一等模块形式使用带有显式参数的字典传递,但是有人建议添加一种机制来实现隐式参数

Swift witness table

Swift做了一个有趣的实现,即通过使用字典传递并将类型的大小以及它们移动,复制和释放方式记录到表中,它们可以以统一的方式提供处理任何类型所需的所有信息,而无需将它们装箱。这样,Swift可以实现泛型而无需单态化,也无需将所有内容分配为统一的表示形式!它们仍然有所有装箱相关实现的动态分发开销,但是防止了分配,记录和缓存失效。Swift编译器还能够在一个模块内以及跨模块内通过@inlinable 标注的函数进行特殊化(单态化)和内联泛型来避免这些开销(如果需要),并使用启发式算法来估算代码会膨胀多少。

此功能还说明了Swift如何在允许在结构体中添加和重新排列字段的同时实现ABI稳定性,尽管出于性能原因,它们提供了 @frozen 属性以选择关闭动态分发。

内涵类型分析

为装箱类型实现接口的另一种方法是在对象的特定部分中添加类型ID,例如vtable指针所指的内存,然后为每个接口方法生成函数,这些函数实际上对switch语句实现的所有类型都有重要声明该接口方法,并分派到正确的特定于类型的方法。

我不知道使用这种技术的任何语言,但是C ++编译器和Java VM在使用配置文件引导的优化来了解某个通用调用站点主要作用于某些类型的对象时,会做类似的事情。他们将通过检查每种常见类型来替换呼叫站点,然后对该普通类型进行静态调度,并以通常的动态调度作为后备情况。这样,分支预测器可以预测将采用普通情况分支,并继续通过静态调用分派指令。

单态化

现在,装箱的另一种方法是单态化。在单态化方法中,我们需要找到一种方法来为要使用的每种类型输出代码的多个版本。编译器具有表示代码的多个阶段,表示在编译时会经过这些阶段,并且理论上我们可以在其中任何阶段进行复制。

生成源代码

单态化的最简单方法是在表示形式的第一个阶段进行复制:源代码!这样,编译器甚至不必在其中提供泛型支持,这就是使用C和Go等语言的用户所使用的,这些编译器有些不支持泛型。

在C语言中,您可以使用预处理器,并在宏或头文件中定义数据结构,该宏或头文件中包含多中不同的#define。在Go中,有诸如genny之类的脚本可以简化代码生成过程。

这样做的缺点是,根据语言的不同,复制源代码可能会有很多缺陷和边缘情况,并且还会给编译器许多额外的工作去进行多次解析和类型检查,这些操作基本上是相同的代码。再说一次,取决于语言和工具,这样的泛型可能很难编写和使用,例如,如果在C宏中编一些东西,则每行必须以反斜杠结尾,并且所有类型和函数名称都必须将类型名称手动链接到它们的标识符上,以避免冲突。

D语言字符串拼接

但是,代码生成确实有好处,那就是可以使用功能强大的编程语言来生成代码,并且还可以使用用户已经知道的表示形式。

一些以其他方式实现泛型的语言还包括一种干净的代码生成方式,以解决其泛型系统未涵盖的更通用的元编程用例,例如序列化。最清楚的例子是D的字符串拼接,它可以在编译中间过程中将D代码视作字符串生成来使用D的全部功能。

Rust过程宏

一个类似的例子,但仅在编译期的一个步骤中表示,即Rust的过程宏,它将标记流作为输入,输出标记流,同时提供工具来将标记流与字符串进行相互转换。这种方法的优点是标记流可以保留源代码中的位置信息。宏可以将用户从输入写入的代码直接粘贴为输出,作为标记,然后,如果用户的代码在宏输出中产生一个编译错误,则编译器打印的错误消息将正确指向用户特定文件行与列的代码,但是如果宏生成了错误的代码,则错误消息将指向宏调用。例如,如果您使用在记录调用中包装函数的宏 并且在执行包装函数时出错,编译错误将直接指向文件中的错误,而不是宏生成的代码中。

语法树宏

某些语言的确采取了进一步的措施,并提供了在使用该语言编写的宏中使用和产生抽象语法树(AST)类型的功能。比如Template HaskellNim宏OCaml PPX和几乎所有Lisp

AST宏的一个问题是您不希望用户学习大量用于构造AST类型以及基本语言的函数。Lisp家族的解决方法是使语法和AST结构非常简单并具有非常直接的对应关系,但是构造这些结构仍然很繁琐。因此,我提到的所有语言都具有某种形式的“ quote”原语,通过在其中提供该语言的代码片段来返回语法树。这些引用原语还具有一种以类似于字符串插值的方式拼接语法树值的方法。这是Template Haskell的示例:

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 |]

在语法树级别而不是标记级别上执行过程宏的一个缺点是,语法树类型通常会随着新语言功能的添加而发生变化,而标记类型却可以保持兼容。例如,OCaml的PPX系统需要特殊的基础结构才能将解析树与宏所使用的语言版本之间进行迁移。而Rust具有添加解析引用工具的库,因此可以以类似于语法树宏的样式编写过程宏。Rust甚至有一个实验库试图复制反射提供的接口

模板

下一类泛型只是在编译期进一步推动代码生成。C ++和D中的模板是一种实现泛型的方法,您可以在类型和函数上指定“模板参数”,并在实例化具有特定类型的模板时,将该类型替换为函数,然后该函数为type做检查以确保该组合有效。

c++
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中的相同示例,请注意if签名中的和通常更好的语法(!是提供模板参数的方式):

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具有称为concept的特性,除了设计更像定义接口和类型约束之外,其功能相同。

编译期函数

D的模板具有许多扩展,这些扩展使用户可以使用诸如编译期函数求值与static if之类的功能,并使用户基本上可以使模板的行为类似于提供编译期参数列表并返回特化的运行时函数的函数。这使D模板成为功能齐全的元编程系统,据我了解,现代C ++模板具有相似的功能,但机制较不简洁。

有些语言采用“泛型只是编译期函数”的概念,并进一步使用它,例如Zig:

Code
fn Stack(comptime T: type) type {
return struct {
items: []T,
len: usize,

const Self = @This();
pub fn push(self: Self, item: T) {
// ...
}
};
}

Zig在编译期和运行时使用相同的代码来完成此任务,并根据标记的参数comptime分解函数。在元级别上还有另一种独立但相似的语言Terra。Terra是Lua的一种方言,它允许用户内联构造较低级的类似于C的函数,然后使用Lua API以及引用和拼接原语在元级别上对其进行操作:

Code
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疯狂的元编程能力使其可以执行一些操作,例如将DSL的优化编译器实现为简单函数,或者使用少量代码在库中实现JavaGo的接口和对象系统。然后,它可以将生成的运行时级代码保存为无依赖关系的目标文件。

Rust泛型

当然,下一类单态泛型在经过类型检查之后,会将代码生成进一步移到编译器中。我提到过,用C ++可以获取的库内部错误的类型就像动态类型的语言得到的错误,这当然是因为模板参数中基本上只有一种类型的类型,就像动态语言。因此,这意味着我们可以通过以下方式解决问题:将类型系统添加到我们的元级别,并通过静态检查它们是否支持用户使用的操作来获得多种类型的类型。这就是泛型在Rust中的工作方式,在语言级别上这也是Swift和Haskell中的工作方式。

在Rust中,您需要在类型参数上声明“trait约束”,其中traits类似于其他语言中的接口,并声明该类型提供的一组功能。Rust编译器将检查泛型函数的主体是否适用于符合trait约束的任何类型,并且不允许用户使用trait约束未声明的类型的功能。这样,Rust中泛型函数的用户在实例化库函数时就永远不会遇到编译错误。编译器也只需对每个泛型函数做一次类型检查。

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和一些补丁(例如链接程序的工作原理)将这些模板快速清除掉!不利之处是优化器无法对每个单态副本进行特别优化,但是由于缺少重复优化,因此编译速度会更快。我们甚至可以将代码结构制作成一个很小的JIT,将其包含在二进制文件中,并在运行时将单态化的副本打印出来,以免二进制文件膨胀。

实际上,我不知道任何一种这样运作的语言,这只是我作分类后自然扩展而来的一个想法,这正是我希望从本文中获得的东西!我希望本文能使您对不同语言的泛型系统有一个更清晰的了解,以及将它们组合成一个一致的类别,并促使您考虑一下概念中的方向,我们可能会从中找到新颖的编程语言。

End.


第一次做这种翻译工作,还挺累的,翻到一半还来了面试电话。

但是的确了解了些新的东西,关于单态,关于模板,关于元编程。

元编程真是有趣的东西。