About
RSS

Bit Focus


编译期数值计算程序设计思路

Posted at 2009-12-02 03:00:11 | Updated at 2018-05-12 05:33:26

阅读这篇文章需要了解基本的 C++ 模板语法规则, 以及模板的泛化, 偏特化, 当然还包括完全特化这些基本概念. 这篇文章将给出基于 C++ 模板的 Metaprogramming 程序设计中需要注意的事项以及渐进式设计思路.

0. 基础

这一段介绍 Metaprogramming 基础, 包括模板模式匹配规则, 使用模板实现循环或分支的基本方法. 对 Metaprogramming 已经有了解的同学可以跳过这一段.

本质上来说, 现代计算机的核心任务是数值计算, 周边任务是 I/O. 现代几个主流的编程语言, 如 C/C++/Java, 它们的语法组织方式与现代计算机的主流体系结构是 "平行" 的, 即, 语句的先后顺序表示它们的逻辑顺序, 而这种顺序与人的一贯思维顺序又是相同的 (在计算机中表达式的计算顺序会与书写顺序稍有不同, 但却很符合人类的思路); 可以说这是什么样的爹生什么样的崽, 什么样的人造什么样的语言和计算机.

然而, 在 C++ 模板世界中, 这个规则被打破了. 从分类上来说, Metaprogramming 更类似于函数式编程, 而不是传统的 C++ 程序设计. 在这个异世界中, 程序员不被允许使用循环或者分支语句, 包括函数返回语句都不允许: 在函数式编程中起码还有函数返回, 而在 Metaprogramming 中, 由于一切函数都没有被调用 (还在编译呢), 因此一切的值都谈不上返回, 它们只是存在于模板符号表中, 一旦编译结束便烟消云散.

当然, 没有循环, 分支这些编程语言中的基本元素, 并不意味着程序员只被允许设计顺序程序. 只不过, 在这里, 一切分流动作都被转化为了另一个语言特性: 模式匹配. (这一点与函数式编程非常相似)

下面一段代码展示了模式匹配的威力:

Code Snippet 0-0

#include <iostream>

template <unsigned I>
struct limit_to_2
{
    static unsigned const R = 2;
};

template <>
struct limit_to_2<1>
{
    static unsigned const R = 1;
};

template <>
struct limit_to_2<0>
{
    static unsigned const R = 0;
};

int main(void)
{
    std::cout << limit_to_2<0>::R << std::endl;
    std::cout << limit_to_2<1>::R << std::endl;
    std::cout << limit_to_2<2>::R << std::endl;
    std::cout << limit_to_2<3>::R << std::endl;
    return 0;
}

模板 limit_to_2 为传入的整数设置了一个上限, 当传入模板的参数为 0 或者 1 时内部定义的 R 值与参数相同, 否则将 R 设置为 2. 这看起来很像是 switch-case 语句, 0 和 1 分别是两个 case, 而未特化的模板则是 default.

但是, 这样做有一些不方便, 如果所设的上限非常高, 那岂不是要为低于限制的情况写很多特化? 所以引入分支是非常必要的. 下面这个例子展示了如何利用模式匹配来实现编译期分支:

Code Snippet 0-1

#include <iostream>

template <bool reach_upboundary, unsigned I> struct limit_branch;

template <unsigned I>
struct limit_to_100
{
    static unsigned const R = limit_branch<100U < I, I>::R;
};

template <unsigned I>
struct limit_branch<true, I>
{
    static unsigned const R = 100U;
};

template <unsigned I>
struct limit_branch<false, I>
{
    static unsigned const R = I;
};

int main(void)
{
    std::cout << limit_to_100<98>::R << std::endl;
    std::cout << limit_to_100<99>::R << std::endl;
    std::cout << limit_to_100<100>::R << std::endl;
    std::cout << limit_to_100<101>::R << std::endl;
    return 0;
}

在程序的开始定义了模板 limit_branch, 但并没有实现它. 它的两个特化实现在后面. 当其中的 bool 参数为真时表示达到上界.

小心使用大于号! 尝试将上面的程序中, limit_to_100 中的定义改为

static unsigned const R = limit_branch*<I >* 100U, I>::R;

这时大于号被当作右尖括号, 编译器会吐出一个尴尬的模板编译错误.

Metaprogramming 中循环的秘诀在于递归, 而不是将循环拆分成分支和跳转. 下面来展示一个典型的循环:

Code Snippet 0-2

#include <iostream>

template <bool reach_upboundary, unsigned I> struct limit_branch;

template <unsigned I>
struct limit_to_100
{
    static unsigned const R = limit_branch<100U < I, I>::R;
};

template <unsigned I>
struct limit_branch<true, I>
{
    static unsigned const R = 100U;
};

template <unsigned I>
struct limit_branch<false, I>
{
    static unsigned const R = I;
};

template <unsigned I>
struct loop_print
{
    static inline void print()
    {
        loop_print<I - 1>::print();
        std::cout << limit_to_100<I>::R << std::endl;
    }
};

template <>
struct loop_print<0>
{
    static inline void print()
    {
        std::cout << 0 << std::endl;
    }
};

int main(void)
{
    loop_print<120>::print();
    return 0;
}

在这段程序中, loop_print 将递归调用另一模板实例 print 函数, 直到参数匹配 0, 这时模板特化中的函数之输出, 退出递归.

这里出现了一个问题: 如果不设置退出条件, 编译器会死循环吗? 当然, 聪明的编译器会设置一个递归深度阈值, 当模板递归太深时直接认为发生了模板实例化发生错误, 这一点比运行时程序默默无闻地死循环要好一些. (对应地, 也会出现本来不该死的情况就死了. 停机问题不可解, 谁知道呢~)

说到死循环, 忘记特化退出条件的情形应该是很少的. 但是, C++ 中的隐患也是出名的多 (继续诅咒标准委员会吧), 在模板方面很不可思议的一点是, 条件短路失灵了! 如下程序:

Code Snippet 0-3

#include <iostream>

template <int I>
struct inf
{
    static bool const R = I < 100 && inf<I + 1>::R;
};

int main(void)
{
    inf<120>::R;
    return 0;
}

看起来人畜无害, 因为传入的参数会使得表达式 I < 100 不成立, 那么按理来说后面的条件不会再被计算. 然而这段程序会让大多数编译器出错. 另外, 三目运算符也不靠谱:

Code Snippet 0-4

#include <iostream>

template <int I>
struct inf
{
    static bool const R = I < 100 ? inf<I + 1>::R : false;
};

int main(void)
{
    inf<120>::R;
    return 0;
}

要跳出这个困境只能添加额外的分流模板来解决, 如

Code Snippet 0-5

#include <iostream>

template <int I>
struct inf
{
    template <bool Cond, int II> struct branch;

    static bool const R = branch<I < 100, I>::R;

    template <int II>
    struct branch<true, II>
    {
        static bool const R = inf<II + 1>::R;
    };

    template <int II>
    struct branch<false, II>
    {
        static bool const R = false;
    };
};

int main(void)
{
    inf<120>::R;
    return 0;
}

甚至不可以去掉 branch 的参数 II, 因为内部模板特化不允许引用外部模板参数!

1. 渐进设计

假设现在要设计一个程序, 在编译期计算前 N 个素数之和. 为了完成这个任务, 先列出一份清单:

template <int N>
struct is_prime
{
    static bool const YES /* 是的, 参数是一个素数 */ ;
};
template <int N>
struct the_Nth_prime
{
    static int const P /* 第 N 个素数的值 */;
};
template <int N>
struct sum_first_Nth_primes
{
    static int const S /* 前 N 个素数之和 */;
};

如此, 大业可图矣.

2. 筛子

作为优雅的程序员可不能给 is_prime 构造很多个偏特化来暴力枚举素数, 而是使用筛法来完成素数判断工作, 而 is_prime 只是一个壳而已.

要准确而完备地找出素数, 还是必须使用传统的暴力试除法: 给定整数 N, 从第 1 个素数 2 开始, 将每个素数作为被除数进行试除, 如果除得余数为 0 则判定 N 不是素数, 如果除到大于或等于某个值的素数仍然除不尽, 那么这个数就是素数. 现在的问题是, 那个 "某个值" 选取多少呢? 为了不让程序复杂到 "好吧我们再来实现编译时求近似平方根" 这种问题, 可以考虑将它简单地定为 N 的一半.

因为现在是在验证整数 N 是否是素数, 那么, 正如数学归纳法一样, 可以认为对于小于 N 的整数, is_prime<N> 都已经实现了, 并且已经统计出小于 N 的素数中有 PrimeNo 个数是素数, 当然, the_Nth_prime<PN>::P 对于所有 PN <= PrimeNo 也都实现了. 为筛的过程画个简易流程图:

PrimeNo = 1:
    N / 2 < the_Nth_prime<PN>::P ?
        => NO:  N is a prime! END loop
        => YES: N % the_Nth_prime<PN>::P reminds 0 ?
            => YES: N is NOT a prime!
            => NO:  PrimeNo += 1, continue loop

为了完成筛过程, 需要两个参数: PrimeNoN

template <int PrimeNo, int N>
struct prime_verify
{
    static bool const BINGO /* 是素数 */;
};

而流程图中的两个分支语句需要实现为两个分流模板, 分流模板需要与筛子模板相同的参数以完成递归, 那么可以考虑这样设计判断除法是否有余数的分流模板:

template <bool NoReminder, int PrimeNo, int N>
struct verify_branch_no_rem;

它的两个偏特化的实现为

Code Snippet 0-6

template <int PrimeNo, int N>
struct verify_branch_no_rem<false, PrimeNo, N>
{
    /* 继续向上递归 */
    static bool const R = prime_verify<PrimeNo + 1, N>::BINGO;
};

template <int PrimeNo, int N>
struct verify_branch_no_rem<true, PrimeNo, N>
{
    /* 整除了! 不是素数 */
    static bool const R = false;
};

另一分流模板, 验证是否到达上界, 可以这么干:

Code Snippet 0-7

template <bool Reached, int PrimeNo, int N>
struct verify_branch_reach_upbdr;

template <int PrimeNo, int N>
struct verify_branch_reach_upbdr<false, PrimeNo, N>
{
    static bool const R = /* 调用 verify_branch_no_rem 分流 */
        verify_branch_no_rem<0 == N % the_Nth_prime<PrimeNo>::P,
                             PrimeNo, N>::R;
};

template <int PrimeNo, int N>
struct verify_branch_reach_upbdr<true, PrimeNo, N>
{
    /* 达到上界! 是素数 */
    static bool const R = true;
};

实现 `prime_verify`:

template <int PrimeNo, int N>
struct prime_verify
{
    static bool const BINGO = /* 调用 verify_branch_reach_upbdr 分流 */
        verify_branch_reach_upbdr<N / 2 < the_Nth_prime<PrimeNo>::P,
                                  PrimeNo, N>::R;
};

最外面的壳 is_prime 的实现很简单:

template <int N>
struct is_prime
{
    /* 从第 1 个素数开始验证 */
    static bool const YES = prime_verify<1, N>::BINGO;
};

当然, 别忘了偏特化, 为最小的几个数进行偏特化当然是必要的了:

Code Snippet 0-8

template <>
struct is_prime<1>
{
    static bool const YES = false;
};

template <>
struct is_prime<2>
{
    static bool const YES = true;
};

3. 嗅探第 N 个素数

仍然用递推方法, 假定现在前 (N - 1) 个素数都计算出了 (即, 模板 the_Nth_prime 在参数介于 1 到 (N - 1) 闭区间内的所有特化都已经实例化了), 那么计算第 N 个素数, 则可以从 (the_Nth_prime<N - 1>::P + 1) 开始递推. 搜索下一素数的流程图如下

Num = the_Nth_prime<N - 1>::P + 1:
    is_prime<Num>::YES ?
        => YES: return Num
        => No : Num += 1, continue loop

很明显, 至少还需要一个分流模板来进行递归. 此外, `the_Nth_prime` 本身也只作为一个壳, 它的参数太少了, 难以进行递归操作. 设计如下:

Code Snippet 0-9

template <bool UntilNowItMayBeAPrime, int Num>
struct seek_next_branch;

template <int Num>
struct seek_next_branch<true, Num>
{
    /* 找到了. */
    static int const N = Num;
};

template <int Num>
struct seek_next_branch<false, Num>
{
    /* 继续嗅探 */
    static int const N = seek_next_prime<Num + 1>::N;
};

template <int Num>
struct seek_next_prime
{
    /* 分流 */
    static int const N = seek_next_branch<is_prime<Num>::YES, Num>::N;
};

那么最后把这些东西揉在一起, 就完成了任务:

Code Snippet 0-10

template <int N>
struct the_Nth_prime
{
    static int const P = seek_next_prime<the_Nth_prime<N - 1>::P + 1>::N;
};

template <>
struct the_Nth_prime<1>
{
    /* 记得要偏特化这个 */
    static int const P = 2;
};

template <int N>
struct sum_first_Nth_primes
{
    static int const S = the_Nth_prime<N>::P
                         + sum_first_Nth_primes<N - 1>::S;
};

template <>
struct sum_first_Nth_primes<1> /* 偏特化 */
{
    static int const S = the_Nth_prime<1>::P;
};

4. 一个完整的实例

Code Snippet 0-11

#include <iostream>

template <int N> struct the_Nth_prime;

template <bool Reached, int PrimeNo, int N> struct verify_branch_reach_upbdr;

template <bool NoReminder, int PrimeNo, int N> struct verify_branch_no_rem;

template <int PrimeNo, int N>
struct prime_verify
{
    static bool const BINGO =
        verify_branch_reach_upbdr<N / 2 < the_Nth_prime<PrimeNo>::P,
                                  PrimeNo, N>::R;
};

template <int N>
struct is_prime
{
    static bool const YES = prime_verify<1, N>::BINGO;
};

template <>
struct is_prime<1>
{
    static bool const YES = false;
};

template <>
struct is_prime<2>
{
    static bool const YES = true;
};

template <bool UntilNowItMayBeAPrime, int Num> struct seek_next_branch;

template <int Num>
struct seek_next_prime
{
    static int const N = seek_next_branch<is_prime<Num>::YES, Num>::N;
};

template <int N>
struct the_Nth_prime
{
    static int const P = seek_next_prime<the_Nth_prime<N - 1>::P + 1>::N;
};

template <>
struct the_Nth_prime<1>
{
    static int const P = 2;
};

template <int N>
struct sum_first_Nth_primes
{
    static int const S = the_Nth_prime<N>::P + sum_first_Nth_primes<N - 1>::S;
};

template <>
struct sum_first_Nth_primes<1>
{
    static int const S = the_Nth_prime<1>::P;
};

/* branch implementation */
template <int Num>
struct seek_next_branch<true, Num>
{
    static int const N = Num;
};

template <int Num>
struct seek_next_branch<false, Num>
{
    static int const N = seek_next_prime<Num + 1>::N;
};

template <int PrimeNo, int N>
struct verify_branch_reach_upbdr<true, PrimeNo, N>
{
    static bool const R = true;
};

template <int PrimeNo, int N>
struct verify_branch_reach_upbdr<false, PrimeNo, N>
{
    static bool const R =
        verify_branch_no_rem<0 == N % the_Nth_prime<PrimeNo>::P,
                             PrimeNo, N>::R;
};

template <int PrimeNo, int N>
struct verify_branch_no_rem<false, PrimeNo, N>
{
    static bool const R = prime_verify<PrimeNo + 1, N>::BINGO;
};

template <int PrimeNo, int N>
struct verify_branch_no_rem<true, PrimeNo, N>
{
    static bool const R = false;
};

/* loop print */
template <int Prime, int SumOfThePrimes>
struct printz
{
private: printz();
};

template <int N>
struct loop_print
{
    loop_print<N - 1> _1;
    printz<the_Nth_prime<N>::P, sum_first_Nth_primes<N>::S> _2;
};

template <>
struct loop_print<0> {};

int main(void)
{
    loop_print<10> _;
    return 0;
}

选一个报错能力强的编译器编译它, 然后会看到...

Post tags:   Template  Metaprogramming  C++

Leave a comment:




Creative Commons License Your comment will be licensed under
CC-NC-ND 3.0


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site