在C语言中实现类型擦除的泛型函数：一个低调的非提案
2024年9月29日
今年早些时候，我阅读了马丁·乌尔克（Martin Uecker）关于为C语言添加参数化多态性的提案N3212。乍一看，将泛型编程引入基础的C语言似乎有些荒谬，毕竟C++已经有了模板，而现代系统级语言几乎都有某种形式的泛型支持。但这个想法让我思考，或许我们可以做点不同于其他语言的、有意义且实用的事情。C++的模板依赖于单例化，即当你编写一个通用函数或类型时，编译器会为每种使用它的类型生成一个独特的特化版本。大多数系统级语言也遵循C++的这条路，因为单例化允许每个特化版本针对其实例化的特定类型进行单独的编译和优化，而且产生的特化版本无需运行时支持就能处理不同类型的交互。
尽管C语言并非许多人期望的那样“可移植的汇编语言”，但通常一个C函数定义会产生一个对象文件中的一个符号，而且在编译后直接访问函数体是不必要的（尽管对优化有帮助），我们希望能保持这些特性。在系统级语言中实现参数化多态的一个不那么常见的方法，如Swift所采用的，是利用运行时元数据动态处理泛型类型。N3212提案中引入了一个新的 _Type 原始类型，它包含了关于类型大小和其他属性的一些元数据，这样就可以使用 _Var 标记来声明使用该元数据的类型：
void sort(_Type T, size_t N, _Var(T) array[N],
int (*compare)(const _Var(T)*, const _Var(T)*)) {
qsort(array, N, sizeof(_Var(T)), compare);
}
然而，设计一种与语言集成的元数据系统面临挑战，它需要提供足够的信息来支持语言支持的所有可能用法，即使某个接口只需要其中的一部分。传统的qsort函数可能只需要元素的大小，但其他通用函数可能还需要知道类型对调用约定的影响、printf中的格式化标记等。现有的大量C代码使用各种各样的自定义多态接口，所以设计一个单一的元数据机制来平衡提供广泛用途的足够信息和避免过度生成过多对大多数客户端不必要的元数据，是一项艰巨的任务。
因此，我想探索一种可能更简单、更灵活，我认为更能体现C语言主观精神（而非C++的单例化或N3212的设计）的第三种方法。结合类型擦除的泛型和在调用站点收集情境适配元数据的默认参数机制，可能会带来意想不到的表达能力，并能更好地为现有C接口添加类型检查。
免责声明：
坦白说，我的语言设计工作重心不在这里，短期内我不会正式向C工作组提出这个想法。我只是在这里概述一个设计方向的大致框架，而不涉及所有细节。我纯粹是在分享一些想法。如果你选择不再阅读，那也没关系。但如果这激发了你去实现或提议类似的东西，那就太棒了！
你可能会问，为什么花这么多时间考虑为C添加重大新功能？毕竟现在C已经过时了吗？我认为，看到更多不局限于单例化套路的系统语言是有益的。也许这些思考能激励雄心勃勃的系统语言设计师尝试不同的东西。
泛型函数
为了让一个编译后的通用函数能与任何输入类型一起工作，而无需预先定义关于该类型的任何运行时元数据，函数不能依赖具体类型的具体布局。C语言已经有不完整类型的概念，它们类似于预声明的结构体或联合体，可以作为指针的指向类型，但不能直接作为变量或函数参数的类型。作为起点，我们可以规定，泛型类型参数的行为就像不完整类型：
// T可以作为指针的指向类型，可以cv-qualifier等...
void good_generic«T»(const T *a, T *b);
// ...但不能单独作为参数类型
void bad_generic«T»(T a); // 错误，不完整的泛型类型T
在这个世界里，由于不能直接操作不完整类型的值，你可能觉得在泛型函数中做不了太多事情。但通过传递匹配指针参数类型的函数指针，可以创建有用的通用函数：
// 遍历列表，给定访问每个节点的操作和前进到下一个节点的操作
void each_node«Node»(Node *head,
Node *(*next)(Node *),
void (*body)(Node *)) {
for (Node *node = head; node; node = next(node)) {
body(node);
}
}
// 示例用法
struct int_node {
struct int_node *next;
int value;
};
// ...
int main() {
// ...
each_node«struct int_node»(&list[0], next_int_node, print_int_node);
}
这类似于传递一个泛型接口的虚函数表（Swift称为“见证表”），但完全由程序控制，指示虚函数表的内容。
默认参数收集类型元数据
要处理泛型值或数据结构，通常需要更多关于类型的信息。操作未知元素类型的数组或其他数据结构时，一般需要知道元素的大小和可能的对齐方式。如果每次调用站点都需要显式传递大量的元数据，会变得繁琐，而且会削弱泛型的安全性，因为调用者很容易传递错误的元数据。如果泛型函数声明可以指定默认参数，那么可以提供一个机制，自动从调用站点收集相关元数据：
// 减少数组中的值
void reduce«T»(T *out, const T *array, size_t count,
void (*sum)(T *out, const T *element),
size_t element_size = sizeof(T)) {
// ...
}
// 示例用法
int main() {
int values[] = {0, 1, 1, 2, 3, 5, 8, 13};
// 调用站点隐式传递element_size = sizeof(int)
reduce«int»(&sum, values, sizeof(values)/sizeof(int), sum_int);
}