基于 m4 的 C 代码模板化

本文是「在 C 的世界之外」这篇文章的一个大的背景。

foo

假设在一个名曰 foo 的函数的内部需要计算点距：

void foo(void *x, void *y, ...)
{
        ... 略去若干行 ...
        
        /* 此处是计算点距的代码，暂时不知如何写*/
        
        ... 略去若干行 ...
}

foo 所接受的两个参数 x 与 y 分别是指向两个点对象的指针。为了追求通用性， foo 这个函数努力成为一个不依赖具体数据类型的「泛型」函数。也就是说，现在我们并不知道 x 与 y 所指向的点对象究竟有着怎样的数据结构。也许它们的数据结构是：

typedef double * Point;

也可能是：

typedef struct {
        double *coord;
        size_t n;
} Point;

还有可能是：

typedef struct {
        char **coord;
        size_t n;
        void *attachment;
} Point;

没错，点的坐标也可以是字符串数组啊！

总之， foo 所面对的「点」对象，变化万千。这种情况下，如何在 foo 函数中计算 x 与 y 这两个点的距离？

C++ 的观点

如果用 C++，这个问题很容易解决，例如：

template<typename T, typename D>
void foo(T &x, T &y)
{
        ... 略去若干行 ...
        
        D d = compute_distance<T, D>(x, y);
        
        ... 略去若干行 ...
}

我的 C++ 知识还停留在 10 年之前，而且也一直都没怎么用过，不知道这么写是不是正确。在上述代码中， T 表示点的类型， D 表示点的「坐标分量」的类型。这里假设点是一个各向同性空间中的点，也就是说，点的各维坐标分量的数据类型都是 D 。如果不作这一假设，代码似乎没法写。

C 的观点

如果坚持用 C 来写 foo ，该怎么做？只能靠函数指针了。看下面的代码：

void foo(void *x, void *y, void * (*compute_distance)(void *, void *))
{
        ... 略去若干行 ...
        
        void *d = compute_distance(x, y);
        
        ... 略去若干行 ...

        /* 不要忘记释放 d */
        free(d);
}

这样来看，C 也不是那么不堪。只要在 compute_distance 中完成 x 到 y 的距离的计算，然后将结果通过 堆空间 传递给 foo 函数。

更复杂的 foo

现在，继续增加 foo 的需求。之所以要计算两个点之间的距离，肯定是用来比较远近用的。可以让 foo 从 x 与 y 中选出距离点 z 更近的那个点，并将其返回。这一需求，可用 C++ 的代码来描述为：

template<typename T, typename D>
T & foo(T &x, T &y, T &z)
{
        D d_xz = compute_distance<T, D>(x, z);
        D d_yz = compute_distance<T, D>(y, z);
        return d_xz < d_yz ? x : y;
}

如果用 C 来写，写到三目运算符那行代码时，发现没法写了：

void * foo(void *x, void *y, void *z, void * (*compute_distance)(void *, void *))
{
        void *d_xz = compute_distance(x, z);
        void *d_yz = compute_distance(y, z);
        void *ret  = ____没法写了___ ? x : y;
        free(d_yz);
        free(d_xz);
        return ret;
}

怎么比较 d_xz 与 d_yz 呢？我们并不知道它们的类型，甚至都不能确定它们是否能参与 < 运算。C++ 没这个问题，因为在 C++ 中，我们可以对类型为 D 的对象进行 < 运算符重载。

没有办法，只好再向 foo 函数提供一个 C 标准库中的 qsort 风格的函数指针：

void * foo(void *x,
           void *y,
           void *z,
           void * (*compute_distance)(void *, void *),
           int (*cmp)(void *, void *))
{
        void *d_xz = compute_distance(x, z);
        void *d_yz = compute_distance(y, z);
        void *ret = cmp(d_xz, d_yz) < 0 ? x : y;
        free(d_yz);
        free(d_xz);
        return ret;
}

反思

如果 foo 继续复杂下去，C 版本的 foo 函数也许会变成函数指针大本营。譬如，怎么进行 d_xz 与 d_yz 的四则运算，怎么计算它们的绝对值，怎么对它们进行开方……

即使这些都不是问题，最终我们能够忍受 foo 函数变成了函数指针的乱炖菜，但是它的性能会比 C++ 版本的 foo 函数差许多。因为 C++ 模板代码会被编译器编译为针对特定数据类型的代码，它的 d_xz 与 d_yz 位于栈空间，并且还具有内联函数的优势。C 版本的 foo 函数的境况则非常悲惨，它需要频繁的调用一组外部函数来完成一些非常简单的运算，而且 d_xz 与 d_yz 需要堆空间的分配与释放操作。也许 C 标准库中的 qsort 就是这样败给 C++ STL 中的 sort 函数的。

C 不适合这种细微的抽象，特别是那些可能需要用于 CPU 密集的数值运算的程序的函数不适合这样细微的抽象。像数组、链表、树、图这些基本的数据结构，可以用 void * 表示所存储的数据，但是这些数据结构本身不需要去做依赖于数据类型的运算，所以可以对它们进行抽象。如果是写针对于人类日常活动的一些程序，譬如写 GUI 库，写一些桌面软件——文本编辑器、阅读器、文件管理器之类，怎么抽象都没大有关系。不过，要写 GNU Science Library 这样的库，就不能去抽象了。GSL 库几乎为每一种基本的数据类型都提供了一套代码。

C 的用武之地是写面向特定需求的代码。如果需求变了，代码再重新写一遍……这样说，似乎很落伍，但是目前做前端的不是在重写过去的桌面程序代码么？做手机 APP 的，不是在重写过去的那些桌面程序代码么？代码重写，增加就业岗位，拯救颓废的世界经济……有什么不好？

m4

单靠 C 是难以挣脱地心引力的。在犹豫是否投靠 C++ 之时，我想起了曾经玩了一段时间的 m4。

m4 说，你可以像下面这样写 foo 函数：

void * foo(void *x, void *y, void *z)
{
        DISTANCE_TYPE d_xz, d_yz;
        compute_distance_T(x, z, d_xz);
        compute_distance_T(y, z, d_yz);
        return less_than_T(d_xz, d_yz) ? x : y;
}

代码中的 DISTANCE_TYPE 、 compute_distance_T 以及 less_than_T 皆为宏。它们可以是 C 的宏，也可以是 m4 的宏。如果它们是 C 的宏，那么 foo 的定义需要放在头文件中供其他模块使用，这样最终的结果就类似于未经编译器优化的 C++ 模板代码的最终结果。如果它们是 m4 的宏，那么 foo 的定义就可以放在 foo.c 文件中了，这样最终的结果就类似于经过编译器 -O2 级别及其以上的 C++ 模板代码的最终结果。由于 m4 宏语言是图灵完备的，它的功能要比 C 的宏强大了几个数量级。无独有偶，C++ 的模板语言也是图灵完备的。

为了让故事继续下去，我们不妨去构造一个 foo 模块以供其他模块调用。foo 模块的头文件名曰 foo.h，其内容如下：

#ifndef FOO_H
#define FOO_H

void * foo(void *x, void *y, void *z);

#endif

foo 模块的实现代码即上述的 foo 函数，现在将其保存于一份名曰 foo.c_T 的文件之中：

#include "foo.h"

void * foo(void *x, void *y, void *z)
{
        DISTANCE_TYPE d_xz, d_yz;
        compute_distance_T(x, z, d_xz);
        compute_distance_T(y, z, d_yz);
        return less_than_T(d_xz, d_yz) ? x : y;
}

然后再制作一个调用 foo 模块的 main.c：

#include <stdio.h>
#include <stdlib.h>
#include "foo.h"

typedef struct {
        size_t n;
        double *coord;
} Point;

int main(void)
{
        double a = {1.0, 2.0, 3.0};
        double b = {2.0, 1.0, 3.0};
        double c = {4.0, 5.0, 3.0};
        Point *x = malloc(sizeof(Point));
        Point *y = malloc(sizeof(Point));
        Point *z = malloc(sizeof(Point));
        x->n = 3; y->n = 3; z->n = 3;
        x->coord = a; y->coord = b; z->coord = c;
        if (x == foo(x, y, z)) printf("I am x!/n");
        else printf("I am y!/n");
        free(z);
        free(y);
        free(x);
        return 0;
}

各个模块的代码均已准备就绪，但是尚无法编译，因为 foo.c_T 目前仅仅是一个模板。若基于它产生一份符合 main.c 需求的 foo.c，我们需要根据 main.c 的需要去定义一组 m4 宏。

然后在 foo.h 与 foo.c_T 的同一目录下创建 foo_env.m4 文件，内容如下：

divert(-1)
define(`DISTANCE_TYPE', `double')
define(`compute_distance_T', 
`do {
        size_t n = ((Point *)($1))->n;
        assert(n == ((Point *)($2))->n);
        $3 = 0.0;
        for (size_t i = 0; i < n; i++) {
                double d = ((Point *)($2))->coord[i] - ((Point *)($1))->coord[i];
                $3 += d * d;
        }
} while (0)')
define(`less_than_T', `($1 < $2)')
divert(0)dnl

然后，假设 Bash 的工作目录是上述三份文件所在的目录，执行以下命令：

$ echo "include(/`foo_env.m4')dnl" > _t_foo.m4  # 「/'」 是对「`」符号的转义
$ cat foo.c_T >> _t_foo.m4
$ m4 _t_foo.m4 > foo.c
$ ls
foo.c  foo.c_T  foo_env.m4  foo.h  main.c  _t_foo.m4

现在有了一份 foo.c，其中提供了可供其他模块调用的 foo 模板函数的一个实例，即：

void * foo(void *x, void *y, void *z)
{
        double d_xz, d_yz;
        do {
                size_t n = ((Point *)(x))->n;
                assert(n == ((Point *)(z))->n);
                d_xz = 0.0;
                for (size_t i = 0; i < n; i++) {
                        double d = ((Point *)(z))->coord[i] - ((Point *)(x))->coord[i];
                        d_xz += d * d;
                }
        } while (0);
        do {
                size_t n = ((Point *)(y))->n;
                assert(n == ((Point *)(z))->n);
                d_yz = 0.0;
                for (size_t i = 0; i < n; i++) {
                        double d = ((Point *)(z))->coord[i] - ((Point *)(y))->coord[i];
                        d_yz += d * d;
                }
        } while (0);
        return (d_xz < d_yz) ? x : y;
}

但是，在 main.c 中，我们还是无法去调用这个 foo 函数的实例，因为 foo.c 文件中出现了 Point 类型与 C 标准库提供的断言宏 assert ，当 C 编译器进入 foo.c 这个小世界时，它不懂 Point 与 assert 为何物，于是就开始抱怨。但是此类问题已经属于工程问题了，到目前为止，我们可以发现，借助 m4 的力量，让 C 代码变成模板代码并非多么困难的事。

工程

下面开始解决「工程」问题，即如何生成可在 main.c 中使用的 foo 函数模板的实例。首先需要将 Point 数据结构的定义从 main.c 中分离出来，存放于 point.h 文件，并去掉具体的坐标分量类型，然后将 foo.h 中的 foo 函数的声明也移植到 point.h 文件：

#ifndef POINT_H
#define POINT_H
#include <stdio.h>

typedef struct {
        size_t n;
        void *coord;
} Point;

Point * foo(Point *x, Point *y, Point *z);

#endif

现在 foo.h 没用了，可将其删除。也就是说， foo 函数应当属于 Point 模块，因为它所涉及的运算的主体是 Point 对象。

同样的道理，应当将 foo.c_T 更名为 point.c_T，然后将其内容修改为：

Point_T_REQUIRES
#include "point.h"

Point * foo(Point *x, Point *y, Point *z)
{
        DISTANCE_TYPE d_xz, d_yz;
        compute_distance_T(x, z, d_xz);
        compute_distance_T(y, z, d_yz);
        return less_than_T(d_xz, d_yz) ? x : y;
}

main.c 的内容变为：

#include <stdio.h>
#include <stdlib.h>
#include "point.h"

int main(void)
{
        double a[] = {1.0, 2.0, 3.0};
        double b[] = {2.0, 1.0, 3.0};
        double c[] = {4.0, 5.0, 3.0};
        Point *x = malloc(sizeof(Point));
        Point *y = malloc(sizeof(Point));
        Point *z = malloc(sizeof(Point));
        x->n = 3; y->n = 3; z->n = 3;
        x->coord = a; y->coord = b; z->coord = c;
        if (x == foo(x, y, z)) printf("I am x!/n");
        else printf("I am y!/n");
        free(z);
        free(y);
        free(x);
        return 0;
}

将 foo_env.m4 更名为 point_env.m4，其内容变为：

divert(-1)
define(`Point_T_REQUIRES', `#include <assert.h>')
define(`DISTANCE_TYPE', `double')
define(`compute_distance_T', 
`do {
        size_t n = ((Point *)($1))->n;
        assert(n == ((Point *)($2))->n);
        $3 = 0.0;
        for (size_t i = 0; i < n; i++) {
                double d = ((double *)($2->coord))[i] - ((double *)($1->coord))[i];
                $3 += d * d;
        }
} while (0)')
define(`less_than_T', `($1 < $2)')
divert(0)dnl

然后在 Bash 中执行以下命令：

$ ls 
main.c  point.c_T  point_env.m4  point.h
$ echo "include(/`point_env.m4')dnl" > _t_point.m4
$ cat point.c_T >> _t_point.m4
$ m4 _t_point.m4 > point.c
$ gcc -std=c11 -pedantic -Werror point.c main.c -o test
$ ./test
I am x!

让 foo 更 foo

现在，我希望在 foo 函数中执行以下运算：

Point * foo(Point *x, Point *y, Point *z)
{
        DISTANCE_TYPE d_xz, d_yz_1th;
        compute_distance_T(x, z, d_xz);
        compute_distance_T(y->coord[0], z->coord[0], d_yz_1th);
        return less_than_T(d_xz, d_yz_1th) ? x : y;
}

也就是说， foo 函数现在是先计算 x 到 z 的距离，结果为 d_xz ，然后计算 y 与 z 在第一维度上的距离，结果为 d_yz_1th ，最后根据 d_xz 与 d_yz_1th 的大小返回相应的点对象。

注：上述代码只是表意，实际上它是错误的。因为 Point 的 coord 是 void * ，它不能参与类似 y->coord[0] 这样的下标运算。

不去争论 foo 这样做是否科学，现实中有些问题的确需要做类似的运算，这里仅仅是为了让问题简单一些而做了许多简化。

之前 point_env.m4 中的 compute_distance_T 现在无法满足需求了。因为 compute_distance_T 只考虑了两个 n 维点的运算，未考虑两个点退化为 1 个维度上的坐标分量的情况。如果不想修改 compute_distance_T 的定义，那么就只能将 y->coord[0] 与 z->coord[0] 封装为两个 1 维的 Point 对象，然后再送给 compute_distance_T ，但是这样做，就丢失了用宏抽象抽象这些运算的本意——为了尽量提高代码的计算性能，结果半途而废。

我们需要给 compute_distance_T 的一个「特化」的机会。可将 foo 函数的代码修改为：

Point * foo(Point *x, Point *y, Point *z)
{
        DISTANCE_TYPE d_xz, d_yz_ith;
        compute_distance_T(x, z, d_xz);
        compute_distance_T(y, z, d_yz_1th, 0);
        return less_than_T(d_xz, d_yz_1th) ? x : y;
}

现在， compute_distance_T 变成了接受 4 个参数的宏，第 4 个参数表示计算两个点在指定维度上的距离。如果不向它提供第 4 个参数，那么它计算的便是两个点的距离。基于这一思路，可将 point_env.m4 中的 compute_distance_T 的定义修改为：

define(`compute_distance_T', 
`do {
ifelse(`4`, ,
`dnl
        size_t n = ((Point *)($1))->n;
        assert(n == ((Point *)($2))->n);
        $3 = 0.0;
        for (size_t i = 0; i < n; i++) {
                double d = ((double *)($2->coord))[i] - ((double *)($1->coord))[i];
                $3 += d * d;
        }dnl
',
`dnl
        size_t n = ((Point *)($1))->n;
        assert(n == ((Point *)($2))->n);
        $3 = ((double *)($2->coord))[$4] - ((double *)($1->coord))[$4];
        $3 *= $3;dnl
'
} while (0)')

这个新的 compute_distance_T ，能够将：

compute_distance_T(x, z, d_xz);
compute_distance_T(y, z, d_yz_1th, 0);

展开为：

do {
        size_t n = ((Point *)(x))->n;
        assert(n == ((Point *)(z))->n);
        d_xz = 0.0;
        for (size_t i = 0; i < n; i++) {
                double d = ((double *)(z->coord))[i] - ((double *)(x->coord))[i];
                d_xz += d * d;
        }
} while (0);
do {
        size_t n = ((Point *)(y))->n;
        assert(n == ((Point *)(z))->n);
        d_yz_1th = ((double *)(z->coord))[0] - ((double *)(y->coord))[0];
        d_yz_1th *= d_yz_1th;
} while (0);

这正是我们所期望的。

这个更 foo 的 foo，展示了基于 m4 的 C 模板代码有着很大的弹性，这些要归功于 m4 的变参宏与条件宏。point.c_T 中的代码所具备的这种的弹性，在 C++ 的世界里可通过函数的重载与函数内联来实现。

讨论

本文所用的 m4 宏，只是 m4 宏的用法之冰山一角。即便如此，它在 C 世界这一番拳打脚踢，也足以表明其力量之所在。理论上，既然 m4 宏是一种图灵完备的编程语言，那么 C++ 模板所能做到的事，基于 m4 的 C 代码模板也能够做到。至于如何去做，这要归结为工程问题。至于实际上做此事的复杂程度，现在觉得难以分出高下。

身为宏编程语言，m4 有其固有的缺陷。用宏语言编写的复杂程序一旦在运行时出现问题，就很难准确定位问题所在，因为错误是在宏展开的结果中发现的，发现错误的时候，很难快速确定它是哪个宏的展开结果。然而，当 C++ 模板代码出错时，编译器也会给出一堆不知所云的错误信息。即使 C++ 标准如大家所希望的那样，引入了 Concept，从而可以在模板代码中检测模板参数是否合乎要求，m4 依然有应对之法，因为 m4 可以检测某个宏是否被定义……

也许基于 m4 的 C 代码模板能够体现的一个优势是，我们不需要去修改语言，也不需要去修改语言的编译器，只需要在语言之外，利用一些常用的工具，便能够很大程度上写出兼顾抽象与执行效率的代码。上文除了用了 m4 之外，也用了很基本的 Bash 命令。在实际的工程中，我们可以继续用 Bash 脚本去实现 C 代码模板实例的生成过程的自动化。

现在，我也不会真的尝试在实际的项目中去尝试基于 m4 的 C 代码模板。所以上述所有言论，仅为抛砖之见而已。