在某些编程领域，通常希望编写一种数据结构或算法来处理不同类型的元素。 例如，仅需要比较功能的泛型列表或排序算法。 提供了多种语言来解决此问题的各种方法：从简单地向程序员指出适当的通用函数（C，Go）到如此强大的通用系统，使它们成为图灵完整的（
Rust ，
C ++ ）。 在本文中，我将讨论来自不同语言的通用系统及其实现。 我将首先使用没有这种系统的语言（例如C）解决问题，然后说明逐步扩展扩展如何导致其他语言的系统。
我发现泛型是一个有趣的选择，因为它们是一般元编程任务的一个简单特殊情况：编写可以生成其他程序类的程序。 作为证明，我将展示如何在通用系统空间中将三种不同且完全通用的元编程方法视为多向扩展：动态语言（如Python），过程宏系统（如
Template Haskel）和分阶段编译（如
Zig和
Terra） 。
复习
我绘制了本文中描述的所有系统的框图，以便您可以介绍其内容以及这些系统如何互连：
主要思想
假设我们正在使用不具有通用系统的语言编写代码，并且我们想要创建一个通用堆栈数据结构的数据结构，该结构可以处理任何类型的数据。 问题在于，每个函数和类型定义仅适用于相同大小并以一种方式复制的数据，并且通常类似地工作。
解决此问题的方法有两种：要么确保所有数据类型在我们的结构中均以相同的方式起作用，要么对数据结构进行许多复制，并进行少量更改以使每种数据类型都能正常使用。 这些想法构成了具有泛型的两大类解决方案的基础：装箱和单态化。
包装意味着将所有内容连续放入统一的“盒子”中，它们的工作方式相同。 通常这样做是这样的：将数据放在堆中，并将指向它的指针放在数据结构中。 您可以指向所有将以相同方式工作的类型的指针，因此相同的代码将可用于任何类型的数据！ 但是，这导致内存消耗增加，动态搜索和高速缓存未命中。 在C语言中，这意味着您的数据结构存储
void*指针，并且仅将数据缓存到
void*或从其中缓存数据（如果数据不在堆中，则会将其放置在其中）。
单一化意味着针对我们要存储的不同类型的数据重复复制代码。 然后，每个代码实例都可以直接使用其使用的大小和数据方法，而无需动态搜索。 使用这种方法，代码可以以最快的速度运行，但是它的大小和编译时间会增加，这是因为我们重复了相同的代码，但做了很小的改动。 在C语言中，这对应于将
整个数据结构定义为macro ，随后是对每种数据类型的调用。
通常，在编译时，代码的编译速度更快，但是在执行过程中其性能可能会下降，而在单态化过程中，我们会生成快速代码，但是编译和优化代码的所有实例都需要更多时间。 另一个区别是，打包扩展使您可以使可执行代码更具动态性，而单态化则使您可以灵活地分隔通用代码的不同实例。 还值得注意的是，在某些大型程序中，由于生成的代码中附加指令的高速缓存中的未命中，可以抵消单态化的好处。
如果需要更多功能或更高的安全性，上述每种使用泛型的方案都可以朝不同的方向扩展，并且各种语言的作者都提出了非常有趣的解决方案。 例如，两种方法都可以在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从通常的包装开始，后来为了兼容起见，使用了类型混搭的通用语言工具，后来获得了使用与以前相同的集合类型，但具有通用类型的可选参数的语言工具。 考虑一下Wikipedia文章中有关
Java泛型的示例：
List v = new ArrayList(); v.add("test");
具有统一性能的派生打包泛型
OCaml进一步发展了统一视图的概念。 没有原始类型需要额外的包装放置（因为
int必须转换为
Integer才能进入Java中的
ArrayList ），因为所有内容都已经被包装或由指针大小的整数值表示，即所有内容都适合一个机器字。 但是，当垃圾回收器查看通用结构中存储的数据时，需要将指针与数字区分开，因此数字用一位标记，放置在正确对齐的指针没有一位的位置，只剩下31或63位的范围。
OCaml还具有类型推断系统，因此您可以编写一个函数，如果不添加注释，则编译器将输出最合适的泛型类型，因此这些函数看起来就像是一种动态类型化的语言：
let first (head :: tail) = head (* inferred type: 'a list -> 'a *)
给定的类型可以称为“从类型
'a到类型
'a的元素列表中的一个函数”。 这意味着返回类型将与列表类型相同，并且可以是任何类型。
介面
常规包装的另一个限制是包装类型是
完全不透明的。 对于像栈这样的数据结构来说，这不是问题，但是诸如对通用函数进行排序之类的工具需要附加的功能，例如特定于类型的比较功能。 有许多方法可以在运行时中实现并反映语言，从技术上讲，这是不同的方向，您可以
使用几种类似的方法来
实现相同的语言 。 但是，不同语言的功能会影响其实现，只有扩展才能增强所选实现的优势。 这意味着有两种基于不同运行时方法的语言家族：虚拟方法表（vtables）和字典传输。
接口方法表
如果我们要提供特定于类型的功能，并且为了统一处理所有内容而遵循打包策略，那么只要有一个统一的方法就可以找到我们需要从对象中获取的相似功能就足够了。 这种方法被称为“虚拟方法表”（vtable，虚拟方法表），尽管没有人使用全名。 它的实现方式如下：在每个通用结构对象的零偏移处，有一个指向具有一致电路的功能指针表的指针。 在这些表中，通用代码通过以固定偏移量索引特定指针来查找指向特定类型函数的指针。
这是在Rust中的Go和
dyn trait对象中实现
interface类型的方式。 当将类型转换为要实现的接口类型时，将为该接口创建一个包装，该包装包含一个指向源对象的指针和一个指向特定于类型的函数的vtable的指针。 但这需要对指针的间接寻址和其他方案的附加级别。 因此，在Go中排序使用
带有Swap方法的容器接口 ，并且不采用Comparable接口的分片，因为这将需要在内存中放置一个全新的接口类型分片，而不是原始分片！
面向对象编程
OOP是一种语言属性，可以充分利用虚拟类型表的功能。 像Java这样的OOP语言，没有使用vtables分隔单独的接口对象，而是在每个对象的开头插入了一个指向虚拟类型表的指针。 类似Java的语言具有继承系统和接口，可以使用这些虚拟类型对象表完全实现它们。
除了提供其他功能之外，将vtable嵌入每个对象还解决了需要使用间接寻址（间接）构造新接口类型的问题。 与Go不同，在Java中
，sort函数可以将
Comparable接口应用于其实现的类型。
倒影
如果您有虚拟类型的表，那么强制编译器生成其他类型信息的表将很困难，例如，字段名称，类型和位置。 这将允许使用可以查看任何其他类型的所有数据的代码访问该类型的所有数据。 此行为可用于在语言中添加“反射”，从而允许序列化和任意类型的美观显示。 反射作为打包范例的扩展，有一个缺点：为此，仅一个代码副本就足够了，但是您需要执行许多动态搜索，这会降低序列化的速度。
使用反射进行序列化和其他功能的语言：Java，C＃和Go。
动态类型语言
反射是一个非常强大的工具，可让您解决许多不同的元编程任务。 但是，它不允许您创建新类型或编辑有关现有值类型的信息。 如果我们添加此功能，并且默认情况下使数据访问和修改语法使用反射，那么我们将获得动态类型的语言！ 由于用于解决任何问题的有效，功能强大的反射系统，使用Python和Ruby等语言进行元编程的非凡灵活性已经出现。
您可以说：“但是动态语言不能那样工作，它们只是使用哈希表实现一切！” 哈希表只是用于创建具有类型信息的可编辑表的良好数据结构。 另外，某些解释器（例如CPython）也以这种方式工作。 在V8这样的高性能JIT中，
有很多虚拟类型表和反射信息。 在V8中，隐藏类（vtable和反射信息）和对象的结构类似于Java VM中的内容，并具有在运行时用新的虚拟类型表替换对象的功能。 这不是巧合，因为没有巧合：
V8的
创建者曾经
在高性能Java VM上工作 。
字典传输
实现动态接口的另一种方法是将具有所需函数指针的表传输到需要它们的通用函数。 这有点类似于在调用位置构造Go形接口对象，仅在我们这种情况下，表是作为隐藏参数传递的，而不是作为现有参数之一打包成束的。
尽管GHC允许您使用内联和特殊化执行某种类型的单态化，但是该方法
在Haskell的类型类中使用。 OCaml使用字典传递和
一流参数的形式的显式参数，但是已经有人提议
增加使参数隐式的能力 。
Swift中的见证表
Swift的作者使用了一个有趣的解决方案：传输字典，以及将数据放在类型大小上以及如何将它们移动，复制和释放到表中，使您能够为所有类型的统一工作提供所有必要的信息，而无需打包它们。 因此，Swift可以实现泛型，
而不会以所有实体
的统一表示形式将其泛化并放置在内存中 ！ 是的，您必须为动态搜索付费，这是使用打包的整个系列的典型特征，但是它可以节省用于放置在内存中的资源，内存的使用和缓存不一致。 使用标
为@inlinable的函数，Swift编译器还可以在模块内部或模块之间进行特殊化（单态化）和内联泛型，从而避免上述费用。 可能使用对代码大小的影响的启发式评估。
它还说明了Swift如何
实现ABI稳定性 ，同时仍然允许您在结构中添加和重新分配字段，尽管作者提供了
@frozen属性来拒绝动态搜索以提高性能。
内涵类型分析
还有另一种实现打包类型的接口的方法。 我们按照vtable指针的示例，将类型标识符添加到对象的特定部分，然后为每个接口方法生成函数，这些接口方法对于实现该方法的所有类型都具有较大的
switch表达式，并将其传递给正确的特定于类型的方法。
我没有警告不要使用使用这种方法的语言，但是C ++编译器和Java虚拟机的行为类似，当使用基于配置文件的优化时，它们会发现调用泛型的某个位置主要适用于某些类型的对象。 编译器和VM使用对每个普通类型的检查替换调用位置，然后使用常规动态调度将这些类型静态调度为后备。 因此，分支预测算法可以预测代码将继续执行哪个分支，并将继续使用静态调用来分派指令。
单一化
这是包装的替代方法。 使用单态化，我们需要找到一种方法来为我们要使用的每种类型生成代码的多个版本。 编译器具有代码需要经历的几个表示阶段，并且从理论上讲，可以复制到任何这些阶段。
源代码生成
单一化的最简单方法是在第一个演示阶段进行复制：复制源代码！ 这样，编译器甚至不必支持泛型，并且有时这是由C和Go语言的用户完成的，而C和Go语言的编译器没有这种支持。
在C语言中，您可以使用预处理器，并通过使用不同的
#define重复插入来定义宏或标头中的数据结构。 Go拥有像
genny这样的脚本，可以轻松生成代码。
复制源代码的缺点是，根据语言的不同，可能有必要处理众多问题和极端情况，而且，编译器会分析多次并检查类型几乎相同的代码。 同样，根据语言和工具的不同，这些方法的泛型可能很难编写和使用，好像在C宏内部，每行以反斜杠结尾，并且所有函数的类型和名称都必须手动粘贴到其标识符中以避免冲突。
D中的字符串混合
但是，代码生成有其优点，例如可以使用成熟的编程语言生成代码以及使用用户熟悉的视图。
某些以不同方式实现泛型的语言还使您可以为泛型系统中未考虑的更一般的元编程情况（例如，序列化）生成代码。 最容易理解的示例是
D中的字符串混合 ，它允许使用语言的所有功能在编译中间以字符串值的形式编译D代码。
Rust程序宏
一个类似的示例，仅在编译器的一个阶段进行了表示。
Rust过程宏将令牌流用作输入和输出，从而提供了将这些流转换为字符串（反之亦然）的实用程序。 这种方法的优点是令牌流可以存储源代码中的位置信息。 由用户编写的代码，可以将宏作为令牌直接从输入插入到周末。 如果此代码在macOS的输出中导致编译错误，则编译器将显示一条消息，并准确指向代码损坏部分的文件，行和列。 但是，如果宏生成了损坏的代码，则错误消息将指示宏调用。 例如，如果您使用一个
宏来将函数包装在记录调用中，并在实现包装的函数时出错，则错误消息将直接指向文件中的错误，而不是宏所生成的代码。
语法树宏
某些语言甚至走得更远，并提供了用于在宏中使用和创建不同类型的抽象语法树的工具（抽象语法树，AST）。 示例包括
Template Haskell ，
Nim宏 ，
OCaml PPX和几乎所有
Lisp 。
AST宏的缺点是您不想强迫用户学习大量的函数来构建AST类型以及基本语言。 在Lisp语言家族中，可以借助AST的语法和结构之间的极大简化和最大对应来解决此问题，但是，创建结构并不总是那么容易。
因此，在我提到的所有语言中，以一种或另一种形式都有一个“ quote”原语，您在其中提供了该语言的一段代码，并返回了语法树。 这些原语可以使用字符串插值的相似性来合并语法树的值。 这是有关模板Haskell的示例：
, , , . . , PPX OCaml
/ , . Rust ,
parsing quotation , , . Rust
, , !
模式
— . ++ 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} };
, , . , , .
D , , : , , . D;
if (
! ):
C++20 «» , , .
D , (compile time function evaluation)
static if , , , , - runtime-. , , , ++ , .
, « ». , 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 .
Terra , . Terra — Lua, - , Lua API , quoting splicing:
function MakeStack(T) local struct Stack { items : &T;
Terra
- (domain specific) ,
Java Go . Terra runtime , .
Rust
, . , , ++, . , , , , . , . Rust, — Swift Haskell.
Rust « » (trait bounds).
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] };
, . Rust . Rust 2018 ,
v: &impl SomeTrait ,
v: &dyn SomeTrait . GHC Swift Haskell , .
— , . , (placeholders) -, , .
memcpy , ! , . . JIT, , .
, , , , , , ! , , , . , , .