今年早些时候，我阅读了马丁·乌埃克尔的提案 N3212，该提案提议在 C 语言中添加参数多态性。很容易嘲笑为简单的 C 添加通用编程的想法，因为 C++ 已经有了模板，而几乎每一种现代系统级语言都有某种形式的通用编程支持，但这让我思考，有机会做一些与这些其他语言不同且有意义的事情。C++ 模板依赖于单态化（monomorphization），这意味着当您编写一个泛型函数或类型时，编译器会为您使用它的每个类型生成一个独立的特化。大多数其他类似的系统级语言都以 C++ 为榜样，因为单态化允许每个特化单独生成并与特定类型进行优化，并且生成的特化不需要任何运行时支持来处理不同的类型。然而，单态化也意味着更加复杂的编译和链接模型，在这种模型中，需要在整个编译过程中一致地获取通用定义的源代码（或其某种中间表示）以便根据需要生成新的实例。尽管 C 并不是很多人想要的那种“可移植的汇编语言”，但 C 中的一个函数定义通常会导致目标文件中的一个符号，并且在首次编译后再次访问函数体是不必要的（虽然有助于优化），因此保留这些属性是好的。实现系统级语言中的参数多态性时较少采用的方法是由 Swift 使用并在 N3212 中提出的，即使用运行时元数据来动态处理泛型类型。N3212 提议了一个新的 _Type 原始类型，它携带一些关于类型大小和其他属性的数据，从而使其他值可以用 _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 代码使用各种不同的方法来处理即席（ad-hoc）泛型接口，因此设计规定单一元数据机制的语言将难以实现既能广泛支持各种用途又不因过多不必要的元数据而膨胀代码的目的。因此，我希望探索第三种方法，这种方法的理解和实现可能会更简单、更灵活，我认为这比 C++ 风格的单态化或多态化设计更符合 C 的“精神”。我认为，结合类型擦除泛型以及在调用位置使用默认参数来收集适当的元数据的方法能够提供相当大的表达力，并允许更好地对现有 C 接口进行类型检查。
免责声明
坦白说，我的语言设计职责集中在其他地方，在短期内不会正式向 C 工作组提议这个想法。因此，我在这里只描述这个设计方向的大致轮廓，而不深入细节。我纯粹是出于想法阶段。如果你不想继续读下去，那也无妨。但如果你受到启发并且真正实现或者提议类似的东西，那就太好了！你可能还会问，为什么花费那么多时间去考虑为 C 新增的重大功能？C 现在不是已经是非法了吗？我认为，看到更多的不陷入已有的单态化陷阱中的系统语言一般是有好处的。也许这些思路能够激发一个有雄心的系统语言设计师尝试一些新东西。
泛型函数
为了让单个编译版本的泛型函数适用于任何输入类型而不需预先定义该类型的运行时元数据，该函数不能依赖具体的类型布局。C 已经有 不完整类型，它们非常相似；您可以前置声明一个结构体或联合体，并且前置声明的类型可以作为指针的对象类型，但不能直接作为变量或函数参数的类型。作为起点，我们可以认为泛型类型参数也表现得像不完整类型：
// T can appear as the pointee of a pointer, be cv-qualified, …
void good_generic«T»(const T *a, T *b);
// …but can't appear as a parameter type by itself
void bad_generic«T»(T a); // error; incomplete generic type T
在这个世界里，似乎您将无法在泛型函数中做太多事情，因为您无法直接处理一个不完整类型。然而，通过传递具有相同指针参数类型的函数指针以及指针，您可以创建有用的泛型函数：
// Traverse a list, given operations to visit each node in the list
// and to advance to the next node
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;
};
struct int_node *next_int_node(struct int_node *node) {
return node->next;
}
void print_int_node(struct int_node *node) {
printf("%d\n", node->value);
}
int main() {
struct int_node list[] = {
{ .next = &list[1], .value = 1 },
{ .next = &list[2], .value = 2 },
{ .next = &list[3], .value = 3 },
{ .next = &list[4], .value = 5 },
{ .next = NULL, .value = 8 },
};
each_node«struct int_node»(&list[0], next_int_node, print_int_node);
}
这类似于传递一个泛型接口的虚表（Swift 称之为见证表），但完全由程序控制来表明哪些内容处于虚表内。## 使用默认参数收集类型元数据
要对泛型值或数据结构进行更多操作，您需要更多关于类型的元数据。要在某个未知元素类型的数组或其他数据结构上进行操作，您通常至少需要知道元素的大小和对齐方式。每次调用都需要显式传递大量的元数据会变得麻烦，而且也会破坏泛型的安全性，因为调用者很容易传递“错误”的元数据。如果可以在泛型函数声明中指定默认参数，那么就可以提供一种从调用点自动收集相关元数据的机制：
// Reduce the values in an array
void reduce«T»(T *out, const T *array, size_t count,
void (*sum)(T *out, const T *element),
size_t element_size = sizeof(T)) {
unsigned i;
const T *element;
for (i = 0, element = array;
i < count;
++i, element = (const T*)((const char *)T + element_size)) {
sum(out, element);
}
}
void sum_int(int *out, const int *value) {
out += value;
}
int main() {
int values[] = {0, 1, 1, 2, 3, 5, 8, 13};
int sum = 0;
// call site implicitly passes element_size = sizeof(int)
reduce«int»(&sum, values, sizeof(values)/sizeof(int), sum_int);
printf("%d\n", sum);
}
（需要手动在 reduce 循环中通过指针转换到 char* 再返回来进行指针推进的方式很糟糕，因此应该有一种方法将大小表达式与泛型类型关联起来，以使指针算术工作：）
// Declaring a generic parameter as T[size_expr] expresses that
// sizeof(T) == size_expr
void reduce«T[element_size]»(T *out, const T *array, size_t count,
void (*sum)(T *out, const T *element),
size_t element_size = sizeof(T)) {
unsigned i;
const T *element;
for (i = 0, element = array;
i < count;
// We can use normal pointer arithmetic on a T* if T has a
// size expression
++i, ++element) {
sum(out, element);
}
}
对现有的函数进行泛型改造
有了这两个特性，我们已经有足够的条件来将一些现有常见的 C 函数改造成利用泛型。N3212 使用排序作为动机示例，并演示了一个新的排序接口作为传统 qsort 标准库函数的一种替代方案。但是让我们在不破坏与现有 C 代码兼容性的情况下升级现有的 qsort。qsort 传统的原型看起来像是：
void qsort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *));
其中 base 是数组中第一个元素的指针，nel 是数组中的元素数量，width 是元素的大小，compar 是三元比较函数，用于返回第一个指向的元素是否被认为小于、等于或大于第二个。我们可以将其更改为：
void qsort«T[width]»(T *base, size_t nel, size_t width = sizeof(T),
int (*compar)(const T *, const T *));
由于泛型类型声明本身在运行时没有影响，因此它不应影响 qsort 的调用约定。我们仍然在所有传递指针的地方传递指针。然而，传统上宽（度）参数应默认为 sizeof(T)，但由于它不是 qsort 的最后一个参数，因此按照 C++ 的默认参数规则这是不允许的。不过我们可以放宽这一限制，并允许任何参数在泛型调用点处具有默认值：
int compare_ints(const int *a, const int *b) {
return a - b;
}
int main() {
int array[] = {0, 1, 1, 13, 2, 21, 3, 34, 5, 8};
qsort«int»(array, sizeof(array)/sizeof(int), /*default*/,
compare_ints);
}
为了使现有的 C 代码能够在 qsort 泛型化之后继续调用它，我们可以规定不带泛型参数调用泛型函数会使这些参数回到 void。依赖于泛型参数的默认参数在非泛型调用点不可用，调用者需要手动提供一个参数。除了向后兼容性外，这还有助于使用以无法静态推断的方式存储的运行时元数据来返回泛型代码。（当然，这也是一种很容易逃逸类型安全的方法，尽管 C 中已经有很多这种做法……或许应该有一个更选择性的方法这样做？）## 泛型结构体
用
