来自牛津大学（Nobuko Yoshida教授团队）和宾州州立大学（Linhai Song教授团队）的科研人员对带有泛型（generics）的 Go 程序提出了一种新的翻译方法。他们形式化了这种翻译方法，并证明了这种翻译方法的正确性。同时，这些科研人员比较了新方法和其他已有翻译方法（包括Go官方的翻译方法）在翻译速度、生成代码的体积，和代码执行速度上的差别。根据实验结果，这些科研人员对已有泛型翻译的实现提出了一些改进意见。相关论文发表在了OOPSLA’2022（程序语言领域排名前三的顶级会议，CCF的A类会议）。论文：https://songlh.github.io/paper/generic.pdf 工具：https://github.com/sfzhu93/fgg2goGo 编程语言自 2009 年发布以来，其设计和改进的重点一直在于如何帮助开发者简单、安全和高效地开发程序上。根据 Stack Overflow 的调查，Go 在最受欢迎的语言排行榜上排名第五。Go 常用于构建大型系统软件，例如 Docker、Kubernetes 和 gRPC 等。最近的 Go 版本（2022 年 3 月 15 日发布的 Go 1.18）添加了泛型（generics）。泛型可以让 Go 开发者安全快速地重用代码，Go 开发者认为这是 Go 语言此前最关键的缺陷，也是大家期待已久的特性。然而，编译具有泛型的 Go 程序，首先要将它翻译成没有泛型的形式，Go 团队表示，他们还需要做很多工作以确保Go编译器中泛型翻译的良好实现。

背景

在介绍这篇论文之前，先通过一个实例介绍一下 Go 语言中的泛型。许多程序中都会用到求两个变量中的最大值的操作，此时开发者通常定义一个 max 函数来求最大值。Go在 1.18 版本之前不支持泛型，开发者必须为每个要使用求最大值功能的具体类型定义一个单独的函数。如示例 1 所示，开发者为 int 和 float 类型分别定义了 一个单独的max 函数—— max_int()（第1行）和 max_float32()（第9行）。

 

示例1：为每种类型分别编写 max 函数在 Go 1.18 之后，可以通过泛型重写上面程序。重写程序展示如下：
示例2：使用泛型为两种类型编写 max 函数第1-3行定义了名为Gt的接口（interface）。第2行指明了该接口可以代表整数（int）、两种浮点数（float32, float64）和字符串（string）。第 5-11 行定义了一个名为max()的泛型函数。第5行的方括号中的部分（[T Gt]），声明了泛型类型 T 应实现了Gt接口。在此例子中，它要求T类型必须是上述四种类型之一。它随后被用作变量a和b，和函数返回值的类型。这意味着，a、b和返回值的类型必须是同一个类型，且它们都是上述四种类型之一。上述四种类型都支持判断两个操作数的大小，因此第6行的大于号对于这四种类型都适用。这样，就可以只编写一遍max函数却可以令多种不同的支持大于号的数据类型使用max函数。第14、15行分别使max()函数来计算两个int参数和两个float32参数的最大值，并打印计算结果。许多程序语言都支持泛型，但每种语言对于泛型的翻译方法都不尽相同。一般而言，翻译泛型的方法可大致分为两类。第一类被称为单态化（monomorphization）。单态化的思路是为每一个泛型函数的具体参数类型，都生成一个单独的函数实例。例如，示例1可以看作对示例2进行单态化翻译的结果。第二类被称为字典传递（dictionary passing），用这种方法翻译泛型函数时，每一个泛型函数只生成一个实例函数，但是为实例函数添加一个额外的字典参数。与类型相关的操作（如示例2中的比较操作），需要通过查找字典来寻找具体的函数实现。
示例3：使用字典的翻译方式示例3大致展示了使用字典传递法对示例2进行翻译的结果。一个额外的字典参数（dict_of_T Dict）被添加到了max()函数，并将“比较操作”替换成了“通过字典参数查找函数指针，并通过函数指针调用函数进行比较操作（dict_of_T._operator_gt(a, b)）”。

相关工作

在 Go 语言中，泛型相关的工作始于 Griesemer 等人，他们为 Go 提出了两个形式化表达：Featherweight Generic Go (FGG) 具有泛型，Featherweight Go (FG) 不具有泛型。他们也形式化了一种从 FGG 到 FG 的单态化翻译。这种单态化翻译可以静态地探察程序的调用图，对于每个泛型类型和方法，根据对该类型或方法的使用，生成多个具体的实现。Go 团队非正式地提出了三种翻译方法的提案：一、单态化型板（stencilling）；二、基于调用图的字典传递（call-graph dictionary-passing）；三、基于垃圾回收时内存形状的型板（GC shape stencilling，提案一和二的混合）。同时，Go 团队实现了一个源码到源码的基于单态化方法的翻译原型，这个原型参照了提案一和 Griesemer 等人的工作。当前 Go 1.18 版本的官方编译器中的翻译是一种优化的单态化方法，优化的思路在于，允许垃圾回收时内存形状一样的类型共享实例化的方法。由于多种类型共享实例化方法，每个实例化方法都需要额外的一个字典参数，来区分具体的参数类型和提供必要的方法指针。这些字典参数需要分析整个Go程序的调用关系来构建。尽管有相同内存形状的对象类型有很多种，但目前的官方翻译仅会对指针类型进行这项优化。Go 团队的所有提案（一至三）、Go 1.18 版本编译器中的官方实现、和 Griesemer 等人的提案都有两个核心限制：(一) 无法覆盖一些有用的具有泛型的编程模式（如一些不可单态化的情况）。例如，所有基于单态化的翻译方法都无法处理支持递归定义的泛型类型。示例 4 定义了一个链表，并计算该链表的全排列。在第 9-15 行，为了求解链表的全排列，首先在第 9 行将链表头结点外的剩余部分 tail 递归求解，然后在第 12-13 行，再将当前链表的头节点元素依次插入到 tail 中。permute() 函数中，receiver 参数 this 的类型是一个泛型元素的链表，但它的返回值是一个链表的链表，其中每个链表都是原始链表的一个全排列，每个链表元素的类型是和输入参数的元素相同类型的泛型。单态化的方法无法实例化这样的函数。具体来说，第23行的变量 seq 具有类型 List[int]，但它在第24行的 permute() 方法的返回类型是 List[List[int]]。子序列的 List[List[int]] 同样具有 permute() 方法，这个 permute() 方法的返回值类型是 List[List[List[int]]。单态化的翻译方法会这样无休止地类推下去。尽管程序实际运行过程中可能并不会用到这么多的类型，但典型的单态化算法通常只能保守地对于所有可能的类型生成对应的实例。此处有一个完整的实例。可以看到，现在的 Go 编译器会检查接口是否存在递归定义，并一概排除存在泛型类型递归定义的情况。
示例4：一个不可单态化的 FGG 程序示例：列表上的全排列（二）其他的采用内存管理的语言均使用字典传递的翻译方法。作为一种具有自动内存管理的语言，Go现在已有的泛型翻译方法都是单态化方法。但是，在调研过其他16种静态类型语言之后，作者发现具有内存管理的语言，都采用字典传递的方法进行泛型的翻译。而不具有内存管理的语言，则采用单态化方法进行泛型翻译。

挑战和贡献

作者为Go语言的泛型设计并实现了一种新的基于字典传递的翻译方法，并证明了这种新翻译方法的正确性。跟官方的翻译方法不同，这种新的翻译法通过泛型函数调用处（call site）的局部信息生成所需要的字典。对新方法和已有的翻译方法进行了比较。设计了两组具有泛型的Go程序，一组用来测量各种翻译方法的渐进复杂度，另一组用来描述泛型在真实程序中的使用。通过这两组Go程序，作者系统地比较了每种翻译方法的优缺点。最后发现，一般而言，单态化会带来更好的运行性能，而字典传递会在更短的编译时间内产生更小的可执行程序。还观察到，在有些场景下，新的字典传递翻译方法可以生成运行效率与 Go 1.18 官方翻译器相当的程序。总体而言，论文结果表明，Go 1.18 的官方翻译器有较大的改进空间，以及字典传递和从调用位置生成传递字典的方法对于Go这样的语言是可用的。作者的工作解决了如下的挑战：第一个挑战是如何为Go设计字典传递的翻译方法。Go 独特的结构化子类型（structural subtyping）为翻译方法的设计带来了额外的复杂性。第二个挑战是如何翻译不可单态化的场景（如示例 4 ）。第三个挑战是如何保证翻译的正确性。第四个挑战是如何设计泛型的程序来对不同的翻译方法进行评估。最后一个挑战是如何考察不同翻译方法之间的优缺点。

关于字节跳动App Infrastructure Research Center团队

在App Infrastructure Research Center，我们的使命是加速软件工程与智能技术的融合与互补，推动软件开发的每一个环节的技术进步。为了实现这个目标，我们汇聚来自不同领域和背景的优秀的研究人员和开发工程师，推动解决字节跳动和整个软件工程社区的挑战。

一直以来，App Infrastructure Research Center团队致力于推进智能化在端基础架构的技术进步，十分关注软件工程学术领域的技术与进展，欢迎各前沿学术团队一起探索与讨论！

欢迎联系：yangping.cser@bytedance.com