转载

基于 m4 的 C 代码模板化

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

foo

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

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

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

typedef double * Point;

也可能是:

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

还有可能是:

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

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

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

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 中完成 xy 的距离的计算,然后将结果通过 堆空间 传递给 foo 函数。

更复杂的 foo

现在,继续增加 foo 的需求。之所以要计算两个点之间的距离,肯定是用来比较远近用的。可以让 fooxy 中选出距离点 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_xzd_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_xzd_yz 的四则运算,怎么计算它们的绝对值,怎么对它们进行开方……

即使这些都不是问题,最终我们能够忍受 foo 函数变成了函数指针的乱炖菜,但是它的性能会比 C++ 版本的 foo 函数差许多。因为 C++ 模板代码会被编译器编译为针对特定数据类型的代码,它的 d_xzd_yz 位于栈空间,并且还具有内联函数的优势。C 版本的 foo 函数的境况则非常悲惨,它需要频繁的调用一组外部函数来完成一些非常简单的运算,而且 d_xzd_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_TYPEcompute_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 这个小世界时,它不懂 Pointassert 为何物,于是就开始抱怨。但是此类问题已经属于工程问题了,到目前为止,我们可以发现,借助 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 函数现在是先计算 xz 的距离,结果为 d_xz ,然后计算 yz 在第一维度上的距离,结果为 d_yz_1th ,最后根据 d_xzd_yz_1th 的大小返回相应的点对象。

注:上述代码只是表意,实际上它是错误的。因为 Pointcoordvoid * ,它不能参与类似 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 代码模板。所以上述所有言论,仅为抛砖之见而已。

原文  https://segmentfault.com/a/1190000007670085
正文到此结束
Loading...