软件开发>杂文>7

共享软件开发的点滴心得

[中文][English][日本語

[机器人制作] [软件开发] [豆知识] [Squeak] [关于]

Scheme & C++ template

溯源

刘新宇

20066

 

“问渠哪得清如许,为有源头活水来”

——朱熹《观书有感》

 

许多今天优秀的作品,来自历史上伟大的创造,尽管这些创造在今天可能不为许多人所知。因此偶尔静下心来,溯源而上,回顾历史,也许能有不少的收获。有趣的是源头有时不只一个,《Discovery》有期讲尼罗河的节目,19世纪曾经有很多英国探险家沿尼罗河逆流而上,进行大规模的征服非洲的探险。他们发现了多条大河不断汇集在一起,最终形成了蕴育出伟大古埃及文明的尼罗河。

 

今天尽管软件界对C++语言有各种评价,使用者仍不免会惊诧于它的博大与深入。如果对C++花一些时间进行逆流而上的“探险”之旅,也是颇为有趣。这样的探险并不惊心动魄,办法就是胡适先生说“开卷有益”,读书——展开——再读书——再展开。具体就是读一本好书,找到书中提到的材料和参考书目(Reference),加以分类整理,再逐一阅读;对每一本书,再发现其中的线索——更多的参考书目和材料。最终,几乎是一定的结果,这张展开的读书网会逐渐收敛、清晰。历史上伟大的作品逐渐展现出来。有时许多作品同时提到某个材料或书,最终的这少数几部作品互相引用,作者们相互影响。它们常常就是伟大的源头,犹如五条欧几里德公设构建出优雅的几何系统一般。

 

C++的探险之旅也是这样有趣,通过书籍、沿着历史溯源,两条大河会喷薄而出,一条是对象理论,另外一条是函数式语言。

C++

^

|

-------------------------

|                       |

OO       Functional Language

 

第一条河很容易看到,宽广、壮阔;第二条不容易找,但是却优雅、有韵味。它是通过模板技术和范型编程引向的另一个世界。这个世外桃源的入口就是STL[1]STL展示了两条线索。1)模板系统的深刻庞大,其背后可能有另一个世界;2STL中有许多优雅的设计,来自Design Pattern[2](如Iterator等)。

 

沿着第二条线索,可以找到GoF的《Design Pattern[2]这部名著,找第一条线索却不容易。引路的著作是Andrei的《Morden C++ Design[3],这部作品一方面用Policy Base DesignDesign PatternGP联系起来,另一方面给出了通向另一个世界的名字:LISP

 

Andrei给出了模板推导时评价说:“这太像LISP[3]”,这句话在《C++ template meta programming[4]中再次被印证,并且Scheme这个线索也出现了[1]。然后《HTDP[5]和《SICP[6]这两部作品终于在这条探险之旅上展现出来。

究竟SchemeC++ Template 有多相似,可以看看下面这个例子,其中左侧是Andrei给出的TypeList实现,右侧是Scheme的表。

// definition of TypeList

template<class T, class U>

struct TypeList{

   typedef T HEAD;

   typedef U TAIL;

};

 

struct NullType;

 

// a type list sample

TypeList<int,

  TypeList<long,

    TypeList<short, NullType>>> myList;

; definition of scheme table

;(cons first, rest)

 

 

 

 

 

 

 

(define my-list

  (cons 'Mars

    (cons 'Venus

      (cons 'Earth empty))))

如果不是计算机专业的话,毕竟能够有机会接触Scheme的人不多,至少没有比接触C++的多。所以这里就试图利用C++template programmingScheme略做对比。既能普及一下scheme的皮毛,又能揭示C++ template函数式语言的一面,给那些希望探索这个世界的探险者抛砖引玉。更大的设想,是希望C++这部分功能能够极大地被发掘出来,使这个古老而又崭新的语言焕发生机,在新的领域一展身手。

 

前缀运算

 

“泠泠七弦上,静听松风寒。古调虽自爱,今人多不弹。”

——刘长卿《听弹琴》

 

从小学数学课起,中缀运算就是大多数人接触到的唯一运算方式,比如1+1, 3×7……。因为说明运算动作的符号(+号、×号),总在两个数字之间,因此有了中缀运算这个名称。中缀运算大量出现在日常生活中,所以人们习惯它。但是它有没有麻烦呢?

 

小学数学的“先乘除,后加减”曾经让不少孩子吃过苦头,比如:

1+2*3=1+6=7

而孩子们总是习惯:1+2*3=>3*3=>9

而很多C++程序员会被运算优先级折磨,连Bjarne Stroustrup也说,如果你犹豫,就加上括号[7]

 

Scheme使用前缀运算,如(+ 1 1)=2, (* 3 7)=21。看起来很不习惯,然而它却可以解决运算优先级的问题。比如:

12×3==>(+ 1 (*2 3))=(+ 1 6) = 7,反之孩子们习惯的错误计算写成前缀表达是:

(* (+ 1 2) 3))=(* 3 3) = 9他们是截然不同的两个表达式。

 

现在看看C++ template怎么驱动编译器进行运算,实现上面的前缀运算。首先模板参数除了可以是类型外,还可以是整数,于是加法和乘法可以这样表示:

 

template<int x, int y>

struct Add{

   static const int value=x+y;

};

 

template<int x, int y>

struct Multiply{

   static const int value=x*y;

};

 

然后可以测试一下,看看这个前缀运算怎么使用。

 

int main(int argc, char* argv[]){

   std::cout<<Add<1, 1>::value<<"\n";

   std::cout<<Add<1, Multiply<2, 3>::value >::value<<"\n";

}

程序会输出27,都是没有歧义的正确结果。

 

函数与常量

 

有了前缀运算,计算简单的小学算术就差不多了,但是要想计算更复杂的内容,还需要函数的帮助。这里的函数,不是C++的函数,也不是所谓的模板函数这么简单。由于所有运算都是编译器在编译期完成的,而不是在运行期完成的。所以需要一个编译器能看懂的函数。假设需要进行华氏温度和摄氏温度的转换。首先查物理手册,得知华氏温标的定义是:在一个大气压下水的凝固点是32华氏度,而沸点为212华氏度;同时摄氏温标规定,水的凝固点为0摄氏度,沸点为100摄氏度。所以换算公式为:

C = (F-32)*100 / (212-32)

C++template定义为:

 

template<int F>

struct Fah2Cel{

   //C = (F-32)*100/(312-32);

   static const int value =

      Division<

        Multiply<Sub<F, 32>::value, 100>::value,

        Sub<312, 32>::value

           >::value;

};

其中前缀减法和除法的定义和前面类似,这里略去。使用方法和测试结果如下:

int main(int argc, char* argv[]){

   std::cout<<"32F = " <<Fah2Cel<32>::value <<"C\n";

   std::cout<<"212F = "<<Fah2Cel<212>::value<<"C\n";

   std::cout<<"80F = " <<Fah2Cel<80>::value <<"C\n";

}

输出:

32F = 0C

212F = 64C

80F = 17C

 

上面的表达式看起来有些不直观,如果写成Scheme前缀表达式是:

(define (Fahrenheit->Celsius f)  (/(* (- f 32) 100 ) (- 312 32))

 

观察前面的计算过程,其中一个显著的特点是没有涉及任何中间变量。不管是简单的前缀运算还是稍微复杂的函数,都如同一台高级计算器(Calculator),但是类似SchemeC++ template编译期计算允许用户定义常量,首先是简单常量,其定义方法和C++的常量一样,如一个大气压为76mm汞柱

 

const int P = 76;

 

函数除了可以操作简单数字,还可以操作复杂结构,比如下面定义笛卡儿平面上的点和计算两点的内积:

template<int x, int y>

struct Pos{

   static const int x=x;

   static const int y=y;

};

 

template<class P1, class P2>

struct Product{

   static const int value =

      Add<

        Sub<P1::x, P2::x>::value * Sub<P1::x, P2::x>::value,

        Sub<P1::y, P2::y>::value * Sub<P1::y, P2::y>::value

      >::value;

};

这样下面语句输出25

std::cout<<Product<Pos<1, 1>, Pos<4, 5> >::value<<"\n";

 

条件分支和逻辑运算

 

C++语言本身有if-else语句,然而在编译器模板推导时却派不上用场,所以C++ template采用模板偏特化的方法实现条件分支,最著名的例子就是编译期Assert[3]。这里给出另外的一些例子,首先看if-else类型的条件控制如何实现,程序输入一个数字,判断是偶数还是奇数,如果是偶数则输出”Even”否则输出”Odd”

template<int n> struct IsEven{

   static const bool value = !(n%2);

};

 

template<bool flag> struct EvenOdd;

 

template<> struct EvenOdd<true>{

   static void Print(){ std::cout<<"Even\n"; }

};

 

template<> struct EvenOdd<false>{

   static void Print(){ std::cout<<"Odd\n"; }

};

 

首先IsEven将数字n根据奇偶性质转换成布尔型的true或者false。然后EvenOdd根据bool值分别进入2个分支(本质是两个偏特化)。每个偏特化输出各自的结果。使用方法如下:

 

int main(int argc, char* argv[]){

   EvenOdd< IsEven<3>::value >::Print();

   EvenOdd< IsEven<4>::value >::Print();

}

 

下面再看看多分支,假设某商店为了促销,规定如下:购物满100元享受8折,购物满500元享受7折,购物满1000元除7折外还加送50元礼品(相当于减掉了50元)。那么下面用C++ template模板推导来实现此多分支程序。

 

template<int n> struct Discount{

   template<bool b1, bool b2, bool b3> struct Branch{

      static const int value = n;

   };

 

   template<> struct Branch< true, false, false >{

      static const int value = n*8/10;

   };

 

   template<> struct Branch< false, true, false>{

      static const int value = n*7/10;

   };

 

   template<> struct Branch< false, false, true>{

      static const int value = n*7/10 - 50;

   };

 

   static const int value = Branch<

      (n>=100 && n<500),

      (n>=500 && n<1000),

      (n>1000)

      >::value;

};

 

这里略做解释,首先实现的方式不止这一个,仍然可以仿照上面if-else的方法定义一个从购物金额到打折方法的映射,但是由于分支多于一个,不能像奇偶数问题那样映射成truefalse,如果映射成0,1,2..的话,可读性会略有降低。上面的实现用到了一个C++特性,就是可以定义内部类(包括内部类模板),所以可以把Branch放在Disount内部。Branch有一个通用版本和3个偏特化版本,分别对应题目要求的4条分支。控制进入哪一个特化版本(分支)的方式是使用3个逻辑表达式开关。调用和测试代码如下:

 

int main(int argc, char* argv[]){

   std::cout<<"20   pay: " <<Discount<20>::value<<"\n";

   std::cout<<"498  pay: " <<Discount<498>::value<<"\n";

   std::cout<<"580  pay: " <<Discount<580>::value<<"\n";

   std::cout<<"1001 pay: " <<Discount<1001>::value<<"\n";

}

程序输出:

20   pay: 20

498  pay: 398

580  pay: 406

1001 pay: 650

同时可以看到,C++ template在编译期推导中,条件判断是一个难点,原因就是必须用模板偏特化来实现条件选择。如果用Scheme实现上述程序的话,代码就会简单很多,如下:

(define (Discount n)

  (cond

    [(< n 100) n]

    [(< n 500) (* n 0.8)]

    [(< n 1000) (* n 0.7)]

[else (- (* n 0.7) 50)]))

Scheme程序测试和输出为:

> (Discount 20)

20

> (Discount 498)

398.4

> (Discount 580)

406

> (Discount 1001)

650.7

 

递归——真正复杂的程序

 

到目前为止的所有处理的数据本身和程序都比较简单,这些远远还不能体现函数式语言的强大。程序处理的数据首先可以复杂很多。Andrei[3]中给除了类型列表,并且用模板推导的功能操纵这个列表,包括添加,删除,查找等等。这里要在Andrei的基础上揭示C++模板不但可以处理类型列表,还可以操作数值列表,并且最后会给出表的排序算法!所有这一切都围绕着一个核心——递归

 

首先,表的定义就是一个递归定义。软件界著名的递归例子之一就是开源软件的名字GNU了,GNU=GNU is Not Unix。这是一个无限递归的例子。然而计算机只能处理有限的内容,所以表的定义如下:

struct Empty;

 

template<int n, class T>

struct List{

   static const int First = n;

   typedef T Rest;

};

这里Empty的定义很重要,它是消除无限递归的出口,由于比较抽象,下面给一些简单的例子:

typedef List<1, Empty> List1;

typedef List<7, List<14, List<5, List<9, Empty>>>> Randoms;

typedef List<2,

List<3,

List<5,

List<7,

List<11, Empty>>>>> PrimeNumbers;

 

 

所以递归表的含义就是:一个表由两部分组成,第一部分是一个元素,第二部分是一个递归表。这个定义的一部分用自身定义,因而称之为递归定义。如果仅仅是这个定义,那么这个表可以无限构造下去。因此加入了一个Empty作为递归出口,因此上述递归表的最后一个元素是一个Empty,以方便计算机处理。

 

除了数据可以递归,函数本身也可以递归,递归函数在处理中调用自身,从而完成运算,下面是阶乘的递归实现:

 

template<int n> struct Factorial;

 

template<> struct Factorial<0>{

   static const int value = 1;

};

 

template<int n> struct Factorial{

   static const int value = n*Factorial<n-1>::value;

};

 

这个实现的数学含义是,n!=n*(n-1)!,并且定义出口为:0!=1。这段程序的测试结果为:

int main(int argc, char* argv[]){

   std::cout<<"5!="<<Factorial<5>::value;

}

程序输出5!=120

 

有了递归表和递归函数,就可以展示C++ template酷似Scheme的一面——强大的编译期递归处理能力。先看一个例子,累加:

 

template<class NList> struct Sum;

 

template<> struct Sum<Empty>{

   static const int value = 0;

};

 

template<class NList> struct Sum{

   static const int value = NList::First + Sum<NList::Rest>::value;

};

 

int main(int argc, char* argv[]){

   std::cout<<Sum<PrimeNumbers>::value;

}

程序输出为前5个素数的和——28

这个程序的原理是首先定义一个函数Sum,它接受一个递归数字表。第二部分是针对递归出口的处理,如果用户输入的这个表是个空表,那么结果——也就是表中各个元素的和——必然是0。然后第三部分针对一般情况处理,取出表中的第一个元素First,用它加上剩下的表的累加结果,就是最终结果。那么剩下表的累加结果有谁处理呢?由于递归的原理,仍然有Sum处理,程序一级一级递归下去知道遇到表中的最后一个元素——Empty

 

递归的强大功能几乎可以处理和数列有关的所有运算,下面这个程序可以将商品价格表中所有低于20元价格的找出来:

template<class NList> struct Pick;

 

template<> struct Pick<Empty>{

   typedef Empty Result;

};

 

template<int n, class T> struct Pick<List<n, T> >{

   template<bool x> struct Branch;

   template<> struct Branch<true>{

      typedef List<n, typename Pick<T>::Result> Result;

   };

 

   template<> struct Branch<false>{

      typedef typename Pick<T>::Result Result;

   };

 

   typedef typename Branch<(n<20)>::Result Result;

};

 

Sum不同,这里用了另外的偏特化方法,明确说明对于List<n,T>这种情形的处理方式。如果递归表当前的数值比20小,那么就把它取出来并且和剩下部分的挑选的结果组成最终表格(Branch的第一个分支)。反之,就仅仅针对剩下的部分进行一次挑选即可。

 

为了验证上面程序的输出,需要一个打印程序,能够将递归表中的元素全部打印出来,这个函数如下:

template<class NList> struct Print;

 

template<int n, class T> struct Print<List<n, T> >{

   static void print(){

      std::cout<<n<<",";

      Print<T>::print();

   }

};

 

template<> struct Print<Empty>{

   static void print(){ std::cout<<"\n"; }

};

有了这些工具,就可以测试Pick功能了:

int main(int argc, char* argv[]){

   typedef List<100, List<15, List<24, List<5, List<1, Empty>>>>> Prices;

   Print< Pick<Prices>::Result >::print();

}

程序输出:

15,5,1,完全符合题目的要求。

最后我们挑战本篇文章的最难题目——排序。该函数声明如下,它接受一个含有数字的表,输出为排好顺序的表:

template<class NList> struct Sort;

 

和许多习惯了过程化语言的程序员习惯不同,由于不能定义任何编译期变量,所以“冒泡法”没有了用武之地。所以思路是采用玩扑克牌时抓牌的手段——任何时候,手里的牌已经按顺序理好了,然后抓一张新牌,把这张牌插入到手里已有的牌中……

 

最简单的情况就是手里没有牌的情况,实现如下:

template<> struct Sort<Empty>{

   typedef Empty Result;

};

 

此后,考虑最复杂的情况,玩家手里有牌,并且已经通过Sort排好序,现在要做的就是通过Insert函数把新抓来的牌插进去,用代码描述就是:

template<class NList> struct Sort{

   typedef typename Insert<

      NList::First,

      typename Sort<typename NList::Rest>::Result

   >::Result Result;

};

 

解决一个问题又带来了一个新的问题——如何实现InsertInsert应该接受一个数字,和一个已排序好的序列,输出为一个新的序列,声明如下:

emplate<int n, class NList> struct Insert;

 

仍然先从最简单的情况下手,假设手里一张牌都没有,那么插入操作完成后,得到一个一张牌的序列,用代码表示就是:

template<int n> struct Insert<n, Empty>{

   typedef List<n, Empty> Result;

};

 

然后再考虑通常的情况,把新抓来的牌和手里的第一张牌比较,如果小的话,那么这张新牌就放在剩下的牌前面,否则就对剩下的牌进行一次Insert。因此代码是这样:

template<int n, class NList> struct Insert{

   template<bool x> struct Branch;

   template<> struct Branch<true>{

      typedef List<n, NList> Result;

   };

   template<> struct Branch<false>{

      typedef List<

        NList::First,

        typename Insert<n, typename NList::Rest>::Result

      > Result;

   };

   typedef typename Branch<(n<NList::First)>::Result Result;

};

这样SortInsert互相作用,排序算法就得以实现了,为了测试算法的正确与否,仍然需要前面定义的Print,测试代码和结果如下:

int main(int argc, char* argv[]){

   typedef List<100, List<15, List<24, List<5, List<1, Empty>>>>> Prices;

   Print< Sort<Prices>::Result >::print();

}

程序输出:

1,5,15,24,100,已经正确排序了。至此C++ template编译期编程的概念可以浮出水面了。利用编译期编程,不仅可以进行排序,还可以进行线性查找,删除,添加,求最大值等诸多功能。而这些功能不会耗费任何运行时资源——堆栈,进程空间……所有这些计算都是编译器完成的。最重要的是,用户可以在同一种语言中既享受面向对象编程的乐趣,又享受函数化编程的优美,不用切换环境和工具——这是多么有趣的事情。而提供这样强大功能的语言,目前世界上只有一个——就是C++。(Opps,没有接触过CLOS,这句话可能值得商榷。)

 

结论

 

看到排序算法的实现,会产生C++ templateScheme一样无所不能的误解。然而C++编译期环境和编译器毕竟不是Scheme,整篇文章,有一个问题一直避开不谈——目前的C++ template推导,可以操作的东西只有两个:类型和整型量(bool算做整型量)。而要完成生活中真正的计算,必须对浮点数加以支持,另外,如果要和用户真正的互动,支持自然语言的字符串也不可或缺。这些都是C++编译器编程无法处理的。

 

通过对C++的溯源,这个探险之旅带来的不仅仅是惊奇和有趣,它更会带来启发,希望更多的人能进一步发掘编译期编程的世界,并且和普通编程结合起来,这后面一定有更有趣的世界。

 

参考书目:

[1] Nicolai M. Josuttis. C++ Standard Library, The: A Tutorial and Reference. Addison Wesley 1st Edition August 06, 1999

[2] Erich Gamma, etc. Design pattern: Elements of Reusable Object-Oriented Software. Addison-Wesley.

[3] Andrei Alexandrescu, Modern C++ Design: Generic Programming and Design Pattern Applied. Addison Wesley, Feb. 2001

[4] David Abrahams, Aleksey Gurtovoy. C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond. Addison Wesley Professional. December 10, 2004

[5] Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi. How to Design Programs, An Introduction to Computing and Programming. The MIT Press, 2001

[6] Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and Interpretation of Computer Programs. second edition. The MIT Press.

[7] Stroustrup, Bjarne. 1997. The C++ Programming Language, 3rd ed. Reading, MA: Addison-Wesley 


 
[1] 感谢好朋友史苏的推荐,这是他在开发一个RFC822 lexer/parser时的发现


[English][上一篇][下一篇][目录][主页][联系我们: liuxinyu95@gmail.com]

ċ
fp.h
(7k)
Xinyu LIU,
Apr 9, 2012, 1:48 AM
ċ
sort.h
(4k)
Xinyu LIU,
Apr 9, 2012, 1:48 AM
Comments