几段纠结的C++代码，求解脱～

最近接触些函数式编程语言，后来想起来C++好像在某个方面也支持函数式“编程”，于是找资料～ 记忆中好像有过一本书叫做什么来着～呃 哦对了，叫做《C 语言 什么来着～》作者是...谁来着？？
不说这些了，我说到哪里了？哦对了，最近接触了些函数式编程语言，没事自己在C++也捣鼓了一番。这下面的几段代码是捣鼓出来了，可有根像刺一样的刺就像刺在了肉里，纠结，特冒雨上来求解脱：

首先下面是两个类似 D&A的《C++ Template Meta Programing》里面所说的“元函数类”的类，是为接着下来的类做准备的：

// Factorial G
struct G {

private:
    template <typename f, int n>
    struct Meta {

        const static unsigned __int64 Value = n * f::Apply<n - 1>::Value;
    };

    template <typename f>
    struct Meta<f,1> {

        const static unsigned __int64 Value = 1 ;
    };

public:
    template<typename  _f>
    struct Apply {

        struct Type {

            template <int  _n>
            struct Apply {

                typedef Meta<_f,_n> Type;
                const static unsigned __int64 Value = Type::Value;
            };
        };
    };
};

// Fibonacci G
struct G2 {
private:
    template <typename self,int n>
    struct Meta {

        const static unsigned __int64 Value = self::Apply<n -1>::Value +  self::Apply<n -2>::Value;
    };

    template <typename self>
    struct Meta<self,1> {

        const static unsigned __int64 Value = 1;
    };

    template <typename self>
    struct Meta<self,0> {

        const static unsigned __int64 Value = 0;
    };

public:
    template <typename _self>
    struct Apply {

        struct Type {

            template <int _n>
            struct Apply {

                typedef Meta<_self,_n> Type;
                const static unsigned __int64 Value = Type::Value;
            };
        }; 
    };
};

貌似不太花吧；我解释一下里面的 Apply::Type::Apply::Type::Apply::Type::Apply ...
这是因为C++的模板机制不支持类似这样的特性：

 

        template< typename T1,typename T2,typename T3,typename T4 /* ... */ >
        struct TMFunction {
            
        };

        template TMFucntion1 = TMFunction <Type1>;
        auto a = sizeof (TMFucntion1<Type2,Type3,Type4>); 

        template TMFucntion2 = TMFunction <Type1,Type2>;
        auto b = sizeof (TMFucntion2<Type3,Type4>); 

        template TMFucntion3 = TMFunction <Type1><Type2><Type3>;
        auto c = sizeof (TMFucntion3<Type4>); 

        auto d = sizeof (TMFunction <Type1> <Type2> <Type3> <Type4>);

请允许我偷懒用struct 来代替class，在这里用哪一个都能说明问题。

可能有人看出来了，如果把模板当作函数（元函数？），把模板参数作为其函数形参，那么上面这些特性是与 Partial evaluation http://en.wikipedia.org/wiki/Partial_evaluation有关的设定。哦，这与我标头里所提到的代码有关。我绕了个弯，用Apply<>::Type::Apply<>::Type::Apply<>::Type 来模拟<><><>；而且还模拟得似模似样，这多亏了我前面所提到的那本书。呃，好像我是从那里面抄来的～ 请知道的人不要声张。

哦，我记起来我要说什么了，就是像下面的一个 Y Combinator ，它只认识"元函数类"：

template<typename G>
struct Y {

    struct W {

        template <typename F>
        struct Apply {

            typedef typename F::Apply<F>::Type Type;
        };
    };

    struct F {

        template<typename f>
        struct Apply {

            // 下面这两行代码(#1,#2)不能通过编译，因为这时 F::Apply<>::Type 还没有定义，
            // 所以不能递归地用于G::Apply<>::Type 的定义

            /*
            typedef typename W::Apply<f>::Type t;           //#1
            typedef typename G::Apply<t>::Type Type;        //#2
            */

            // 只能以下面的办法来解决
            // 这里 “Type”的定义 并不依赖于 "G::Apply<>::Type"，所以 "G::Apply<>::Type" 使用它不会构成递归定义
            // 但是这使得Y失去了通用性，因为"Type"必须再重复"G::Apply<>::Type" 的定义
    
            /**/
            struct Type {

                template< int n>
                struct Apply {

                    typedef typename W::Apply<f>::Type t;       //temp t
                    typedef typename G::Apply<t>::Type::Apply<n>::Type Type;
                    const static unsigned __int64 Value = Type::Value;
                };
            };
            /**/
        };
    };

    // the result is here 
    typedef typename W::Apply<F>::Type Type;
};

里面的注释就是问题所在，也是纠结所在。若是#1和#2两行代码能起作用，那么在我心目中这个Y 就算合格了。可是我的思路断了，不知如何再绕过去，所以这个Y 只能用于 第二形参是 int 的元函数类，而且必须是没有第三个形参的。OTZ 求解脱!

PS : 关于 Y Combinator,我记得函数是编程里面是位明星，所以这里不做解释了；如有兴趣，可参考这里: http://en.wikipedia.org/wiki/Y_combinator 
     关于 Partial evaluation ，更多的信息可参考 lambda calculus 以及 Higher-order_functions  http://en.wikipedia.org/wiki/First-class_function#Higher-order_functions:_passing_functions_as_arguments

22 个解决方案

#1

模板元编程，脑力过剩者的游戏。
楼主继续吧。我是不准备浪费精力在上面了。

#2

你编程是为了解决问题，不是为了研究语言，解脱个什么劲啊。

#3

 呃 忘记了贴上后面的代码。这是上面那个 Y 和两个 G 的例子:

    typedef Y<G>::Type Factorial;
    typedef Y<G2>::Type Fibonacc;

    std::cout << typeid(Factorial).name() << std::endl;
    std::cout << typeid(Factorial::Apply<10>::Type).name() << std::endl;
    std::cout << Factorial::Apply<20>::Value << std::endl;

    std::cout << typeid(Fibonacc).name() << std::endl;
    std::cout << typeid(Fibonacc::Apply<10>::Type).name() << std::endl;
    std::cout << Fibonacc::Apply<93>::Value << std::endl;

    std::cout << Fibonac(42) << std::endl;

最后面的那个 Fibonac(42) 作为对比是这样定义的：

unsigned int Fibonac(int n)
{
    if(n < 2)
        return n;
    return Fibonac(n - 1) + Fibonac(n - 2);
}

PS: 也许是我老了，也许是我的机器老了，Fibonac(42) 在我的机器上跑了差不多一分钟,我用的是VS 2010; 
    Fibonacc::Apply<93>  是 unsigned __int64 的溢出上限，但是即便是Fibonacc::Apply<100>，编译一样是几秒钟就完成。我真的是老了，求解脱

#4

一楼 二楼  的话有见地。但有时候增长见识也是一种增长解决问题能力的一种办法。

#5

该回复于2012-07-29 10:59:08被版主删除

#6

长路漫漫其修远

#7

引用 3 楼  的回复:

 呃 忘记了贴上后面的代码。这是上面那个 Y 和两个 G 的例子:
C/C++ code

    typedef Y<G>::Type Factorial;
    typedef Y<G2>::Type Fibonacc;

    std::cout << typeid(Factorial).name() << std::endl;
    std::cout << typeid(Factorial::Apply<10>::Type).name() << std::endl;
    std::cout << Factorial::Apply<20>::Value << std::endl;

    std::cout << typeid(Fibonacc).name() << std::endl;
    std::cout << typeid(Fibonacc::Apply<10>::Type).name() << std::endl;
    std::cout << Fibonacc::Apply<93>::Value << std::endl;

    std::cout << Fibonac(42) << std::endl;

要实现支持例子中用法的模板貌似不是很难，我看你在主楼绕了半天，好像是在追求通用性。没学过 lambda calculus 和 Y combinator，wiki page 的解释也聊胜于无。你心目中 Y 的通用用法都是什么样的呢？写点儿伪代码展示一下除了给 Factorial 和 Fibonacci 当外壳的其他用法。
另外，你所有的 Fibonacci 都拼错了，除了注释里的那一个，正确的拼法是  Fibonacci。

#8

个人意见：模版和函数式编程都是语法糖。

#9

引用 7 楼  的回复:

我看你在主楼绕了半天，好像是在追求通用性。没学过 lambda calculus 和 Y combinator，wiki page 的解释也聊胜于无。你心目中 Y 的通用用法都是什么样的呢？写点儿伪代码展示一下除了给 Factorial 和 Fibonacci 当外壳的其他用法。
另外，你所有的 Fibonacci 都拼错了，除了注释里的那一个，正确的拼法是 Fibonacci。

是为了通用性，当然，在此处的通用性也是有限制的，但是这些限制并不是最大的问题。问题是在最前面的指出的那一段代码和注释里面：

            // 下面这两行代码(#1,#2)不能通过编译，因为这时 F::Apply<>::Type 还没有定义，
            // 所以不能递归地用于G::Apply<>::Type 的定义

            /*
            typedef typename W::Apply<f>::Type t;           //#1
            typedef typename G::Apply<t>::Type Type;        //#2
            */

假如上面的两行代码能工作的话，那么这个Y 的实现 就不用和 G 的其他参数绑定（第一个参数 "f" 除外）:

struct G3 {

    template<typename f,typename T1,typename T2,int n>
    struct Meta {

       // 函数体
       /* ... */

       // 递归
       typedef f::Apply<T1,T2>::Type Type;
       // 或者 enum {Value = f::Apply<T1,T2>::Value }
       // 这里没有计算递归终结条件，但这个不是要讨论的重点，重点是递归实现了。
    }; 

    template<_f>
    struct Apply {

       struct Type {

          struct Apply<typename _T1,typename _T2> {      //#Apply

             typedef Meta <_f,_T1,_T2>::Type Type;
          };
       };
    };
}

当前的实现是 G函数的“#Apply” 这一行代码必须要在Y 之中重复写一遍，Y 才能应用于 G ；就相当于Y是定制的。

但如果前面指出的那两行被认为是无效的代码能工作的话，那么就不需要这样的定制:
 typedef typename G::Apply<t>::Type Type;
这里的已经把 G::Apply<t>::Type 提取到Y之中，所以 “#Apply” 这一行代码也就能在 Y 之中运用了：

  typedef Y<G3> func;
  auto value = func::Apply<type1,type2>::Value; // 这里的func::Apply 就是 G3::Apply<>::Type::Apply<>

我这样解释可以么？

"另外，你所有的 Fibonacci 都拼错了，除了注释里的那一个，正确的拼法是 Fibonacci。"
这个问题我也知道，因为注释是用自然语言的，所以“Fibonacci”这个词我没有胡乱做修改。在代码中因为我无法写出两个名字一样的标识符(typedef Y<G2>::Type Fibonacc 以及 unsigned int Fibonac(int n)   )，所以做了修改，希望不要介意

#10

上面代码中
template<typename f,typename T1,typename T2,int n>
    struct Meta { ... };
int n 是手误，在这里是多余的

#11

struct G3 {

    template<typename f,typename T1,typename T2, int n>
    struct Meta {

       enum {Value = n + f::Apply<T1,T2, n - 1>::Value };
    }; 

    template<typename f,typename T1,typename T2>
    struct Meta<0> {

       enum {Value = 0 };
    }; 

    template<_f>
    struct Apply {

       struct Type {

          //#Apply
          template<typename _T1,typename _T2,int _n>
          struct Apply {

             typedef Meta <_f,_T1,_T2,_n>::Type Type;
          };
       };
    };
};

#12

很多东西都是聊以慰藉那些逝去的东西，你一味的追求通用性的模板元编程，并且深陷其中而忘却的一些事情的本质。
就好比鲁迅先生笔下的华老栓，一心执着着给自己的儿子治病，却忘却了那药的作用和由来...
一味的追求程序模板化却忘却的语言本身存在的本和根
Strousstrup曾说过，C++的指导原则之一是不要为不使用的特性付出代价。

#13

引用 12 楼  的回复:

很多东西都是聊以慰藉那些逝去的东西，你一味的追求通用性的模板元编程，并且深陷其中而忘却的一些事情的本质。
就好比鲁迅先生笔下的华老栓，一心执着着给自己的儿子治病，却忘却了那药的作用和由来...
一味的追求程序模板化却忘却的语言本身存在的本和根
Strousstrup曾说过，C++的指导原则之一是不要为不使用的特性付出代价。

想必woomevan有些误解。
在这里并非是执意追求通用性的模板元编程，更不用说是深陷其中了。仅仅是因为这一阵在接触函数式编程方面的应用，想起了C++的模板元编程其实也是接近于函数式编程，所以又回头考察。毕竟以前对FPL不了解，所以对C++模板的理解与应用都是没有深入。

我确实是看到了FPL的一些优点，所以想看看对C++的模板元编程能达到什么样的理解程度。如果有可能，我认为在C++之中使用自带的模板元编程会比引入一个新的FPL进行混合编程应用更加方便。

实在不行，放弃又有何不可。从一些实现以及自己的学习过程中，我也发现了不少类似这样的限制。有的能利用一些技巧绕过去，而有些特性的实现则太困难。除非有相当的价值，否则谁会绕着弯子而不走直路。

学习与讨论，旨在同求进步。谢谢woomevan给出你的看法

#14

看得头都晕了

#15

语法糖，无处不在

#16

引用 9 楼  的回复:

引用 7 楼  的回复:

我看你在主楼绕了半天，好像是在追求通用性。没学过 lambda calculus 和 Y combinator，wiki page 的解释也聊胜于无。你心目中 Y 的通用用法都是什么样的呢？写点儿伪代码展示一下除了给 Factorial 和 Fibonacci 当外壳的其他用法。
另外，你所有的 Fibonacci 都拼错了，除了注释里的那一个，正确的拼法是 F……

我想知道的不是这些。你说这些时已经把我捆绑在你的实现上了，我想知道你要解决的问题本身。就好像 c++ 标准只描述虚函数的行为，而不谈虚函数表和虚表指针一样，因为后者为实现细节，不属于问题本身。我想知道这个 Y combinator 需要支持的行为，以及你预期的使用方法和应该产生的效果；有可能我根本搞不出解决方案，或搞来搞去和你的类似，但这并不影响分析一个问题的正确流程是先了解问题本身，然后在讨论具体解法。

#17

引用 16 楼  的回复:

我想知道的不是这些。你说这些时已经把我捆绑在你的实现上了，我想知道你要解决的问题本身。就好像 c++ 标准只描述虚函数的行为，而不谈虚函数表和虚表指针一样，因为后者为实现细节，不属于问题本身。我想知道这个 Y combinator 需要支持的行为，以及你预期的使用方法和应该产生的效果；有可能我根本搞不出解决方案，或搞来搞去和你的类似，但这并不影响分析一个问题的正确流程是先了解问题本身，然后在讨论具体解法。

对于模板元函数 G<f,arg1,arg2,arg3,...> ，Y 能应用于G而不受限于其除以外的其它参数arg1,arg2,arg3,...的个数或者形式(模板参数类型，比如不管arg1 是typename 还是又是一个template，这里我用参数的形式来表达这个意思)。亦即是说，Y 的实现是应用于模板元函数上，但是它对于G 的限制仅限于G的第一个参数，就和通常的应用于函数式编程语言里的 Y Combinator 一样。 
（这里G的形式可以是我给出的元函数类，或者别的形式，但是 Y 的实现可以不必为此负责，只要其中一种形式能实现Y，那么其它的G形式的Y也可以实现，所以我用元函数类来举例子）

PS:
模板元函数能否像通常的函数（并非仅是C中的函数）那样使用起来时意义简洁明了，我更倾向于将模板元编程理解成函数式编程，因为模板元函数更像无状态的纯函数。而我认为 Y 的实现是否“简洁”是检验这一门语言是否易于使用的一个参考点。

#18

引用 17 楼  的回复:

对于模板元函数 G<f,arg1,arg2,arg3,...> ，Y 能应用于G而不受限于其除以外的其它参数arg1,arg2,arg3,...的个数或者形式(模板参数类型，比如不管arg1 是typename 还是又是一个template，这里我用参数的形式来表达这个意思)。亦即是说，Y 的实现是应用于模板元函数上，但是它对于G 的限制仅限于G的第一个参数，就和通常的应用于函数式编程语言里的 Y Combinator 一样。 
（这里G的形式可以是我给出的元函数类，或者别的形式，但是 Y 的实现可以不必为此负责，只要其中一种形式能实现Y，那么其它的G形式的Y也可以实现，所以我用元函数类来举例子）

PS:
模板元函数能否像通常的函数（并非仅是C中的函数）那样使用起来时意义简洁明了，我更倾向于将模板元编程理解成函数式编程，因为模板元函数更像无状态的纯函数。而我认为 Y 的实现是否“简洁”是检验这一门语言是否易于使用的一个参考点。

看不明白你说什么，我没学过函数式编程语言，也不知道 Y Combinator 是什么。你就不能写两行伪代码，秀一下这个 Y 和 G 到底用起来是什么样子的？就是再高深的理论，也不妨碍举几个例子吧。你陈述中一直在说模板元函数，可是代码里从头到尾都是类模板。我是真搞晕了。

#19

引用 18 楼  的回复:

看不明白你说什么，我没学过函数式编程语言，也不知道 Y Combinator 是什么。你就不能写两行伪代码，秀一下这个 Y 和 G 到底用起来是什么样子的？就是再高深的理论，也不妨碍举几个例子吧。你陈述中一直在说模板元函数，可是代码里从头到尾都是类模板。我是真搞晕了。

Y Combinator,简单的说它有这样的特性：
对于任意函数 G（当然，是至少有一个参数的函数）：
Y(G) = G(Y(G))

这就是 Y 的全部。
我想我能给出的解释比不上 wikipedia 上的来得更详细；起先我给出链接了。G 在这里只是我给出的原函数类的形式，是普通的元函数类。例子，就是我给出的代码。Y Combinator 本来就是一种符号运算用的组合子，取再多的例子也是类似这样的，没有本质上的区别。

你心目中的模板元函数可能和我理解的不一样。

#20

引用 19 楼  的回复:

Y Combinator,简单的说它有这样的特性：
对于任意函数 G（当然，是至少有一个参数的函数）：
Y(G) = G(Y(G))

这就是 Y 的全部。
我想我能给出的解释比不上 wikipedia 上的来得更详细；起先我给出链接了。G 在这里只是我给出的原函数类的形式，是普通的元函数类。例子，就是我给出的代码。Y Combinator 本来就是一种符号运算用的组合子，取再多的例子也是类似这样的，没有本质上的区别。

你心目中的模板元函数可能和我理解的不一样。

我大概看明白了，但是也没想出方法。不过，我倒是想问一下，这个 Y combinator 和 G 本身比起来有什么优势呢？我看 wiki 的例子，和你的例子，好像 Y(G) 能做的事，G 本身都能做，因此 Y 的能力来源于 G，如果 Y 不能带来额外的利益的话，为什么好要用它呢？
比如，运行时程序和模板元编程都能够完成类似功能的话，模板元编程能够带来在编译期完成运算的好处，所以比运行时有优势。但这个 Y combinator 貌似没有这种优势，你的 G 是在编译期完成计算的，所以 Y 也是，如果 G 不能，Y 也不能。想看一个例子，Y(G) 能干，而 G 干不了的。

#21

引用 20 楼  的回复:

我大概看明白了，但是也没想出方法。不过，我倒是想问一下，这个 Y combinator 和 G 本身比起来有什么优势呢？我看 wiki 的例子，和你的例子，好像 Y(G) 能做的事，G 本身都能做，因此 Y 的能力来源于 G，如果 Y 不能带来额外的利益的话，为什么好要用它呢？
比如，运行时程序和模板元编程都能够完成类似功能的话，模板元编程能够带来在编译期完成运算的好处，所以比运行时有优势。但这个 Y combinator 貌似没有这种优势，你的 G 是在编译期完成计算的，所以 Y 也是，如果 G 不能，Y 也不能。想看一个例子，Y(G) 能干，而 G 干不了的。

再深入下去就和我的初衷离地远了。
要详细讨论 Y combinator 的话，那话题蛮多的。你所说的没有错，但有一种情形你可能没有想到过：
 当 G 不能自指的时候，怎么让 G 实现递归调用自身？
Y 的主要工作就是帮助这样的G实现自指递归的。当然在C++模板元编程中，模板元函数使能够引用自身进行递归的，所以 Y 在这里显得多余。

但是，怎么说呢，Y 也是一种思想，我仅仅是试图用 C++ TMP 来完成 它的 Y combinator，就像画画一样。也许画不出来，也许能画个轮廓，但无论结果如何，都能帮助我提高画画的技巧。

#22

引用 8 楼  的回复:

个人意见：模版和函数式编程都是语法糖。

糖还是可以适当吃以下的