longshanks

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  14 Posts :: 0 Stories :: 214 Comments :: 0 Trackbacks

常用链接

留言簿(10)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

GP技术的展望——先有鸿钧后有天

莫华枫


    自从高级语言出现以来,类型始终是语言的核心。几乎所有语言特性都要以类型作为先决条件。类型犹如天地,先于万物而存在。但是,是否还有什么东西比类型更加原始,更加本质,而先于它存在呢?请往下看。:)

泛型和类型

    泛型最简短最直观的描述恐怕应该是:the class of type。尽管这样的描述不算最完备,但也足以说明问题。早在60年代,泛型的概念便已经出现。最初以“参数化类型”的名义存在。70年代末期发展起来的 恐龙级的Ada(我的意思不是说Augusta Ada Byron Lovelace伯爵夫人是恐龙,从画像上看,这位程序员的祖师奶长得相当漂亮:)),尚未拥有oop(Ada83),便已经实现了泛型(Generic)。尽管泛型历史悠久,但真正全面地发展起来,还是在90年代初, 天才的Alexander A. Stepanov创建了stl,促使了“泛型编程”(Generic Programming)的确立。
    出于简便的目的,我套用一个老掉牙的“通用容器”来解释泛型的概念。(就算我敷衍吧:P,毕竟重头戏在后面,具体的请看前面给出的链接)。假设我在编程时需要一个int类型的栈,于是我做了一个类实现这个栈:
    class IntStack {...};
    用的很好。过了两天,我又需要一个栈,但是类型变成了double。于是,我再另写一个:
    class DoubleStack {...};
    不得了,好象是通了马蜂窝,不断地出现了各种类型的栈的需求,有string的,有datetime的,有point的,甚至还有一个Dialog的。每 种类型都得写一个类,而且每次代码几乎一样,只是所涉及的类型不同而已。于是,我就热切地期望出现一种东西,它只是一个代码的框架,实现了stack的所 有功能,只是把类型空着。等哪天我需要了,把新的类型填进去,便得到一个新的stack类。
    这便是泛型。
    但是,仅仅这些,还不足以成就GP的威名。
    我有一个古怪的需求(呵呵,继续敷衍。:)):
    做一个模板,内部有一个vector<>成员:
    template<typename T> A
    {
        ...
        vector<T> m_x;
    };
    可是,如果类型实参是int类型的话,就得用set<>。为了使用的方便,模板名还得是A。于是,我们就得使用下面的技巧:
    template<> A<int>
    {
        ...
        set<T> m_x;
    };
    这叫特化(specialization),相当于告诉编译器如果类型实参是int,用后面那个。否则,用前面的。特化实际上就是根据类型实参由编译器执行模板的选择。换句话说,特化是一种编译期分派技术。
    这里还有另一个更古怪需求:如果类型实参是指针的话,就用list<>。这就得用到另一种特化了:
    template<typename T> A<T*>
    {
        ...
        list<T> m_x;
    }
    这是局部特化(partial specialization),而前面的那种叫做显式特化(explicit specialization),也叫全特化。局部特化则是根据类型实参的特征(或者分类)执行的模板选择。
    最后,还有一个最古怪的需求:如果类型实参拥有形如void func(int a)成员函数的类型,那么就使用deque。这个...,有点难。现有的C++编译器,是无法满足这个要求的。不过希望还是有的,在未来的新版C++09中,我们便可以解决这个问题。

Concept和类型

    concept是GP发展必然结果。正如前面所提到的需求,我们有时候会需要编译器能够鉴识出类型的某些特征,比如拥有特定的成员等等,然后执行某种操作。下面是一个最常用的例子:
    swap()是一个非常有用的函数模板,它可以交换两个对象的内容,这是swap手法的基础。swap()的基本定义差不多是这样:
    template<typename T> swap(T& lhs, T& rhs) {
        T tmp(lhs);
        lhs=rhs;
        rhs=tmp;
    }
    但是,如果需要交换的对象是容器之类的大型对象,那么这个swap()的性能会很差。因为它执行了三次复制,这往往是O(n)的。标准容器都提供了一个 swap成员函数,通过交换容器内指向数据缓冲的指针,获得O(1)的性能。因此,swap()成员是首选使用的。但是,这就需要程序员识别对象是否存在 swap成员,然后加以调用。如果swap()函数能够自动识别对象是否存在swap成员,那么就可以方便很多。如果有swap成员,就调用成员,否则, 就是用上述通过中间变量交换的版本。
    这就需要用到concept技术了:
    template<Swappable T> void swap(T& lhs, T& rhs) {
        lhs.swap(rhs);
    }
    这里,Swappable是一个concept:
    concept Swappable<typename T> {
        void T::swap(T&);
    }
    于是,如果遇到拥有swap成员函数的对象,正好符合Swappable concept,编译器可以使用第二个版本,在O(1)复杂度内完成交换。否则,便使用前一个版本:
    vector a, b;
    ... //初始化a和b
    swap(a,b); //使用后一个版本
    int c=10, d=23;
    swap(c, d); //使用前一个版本
    这里的swap()也是运用了特化,所不同的是在concept的指导下进行的。这样的特化有时也被称作concept based overload。
    从上面的例子中可以看到,原先的特化,无论是全特化,还是局部特化,要么特化一个类型,要么特化一个大类(如指针)的类型。但无法做到更加精细。比如,我 希望一个模板能够针对所有的整数(int,long,short,char等)进行特化,这在原先是无法做到的。但拥有了concept之后,我们便可以 定义一个代表所有整数的concept,然后使用这个整数concept执行特化。换句话说,concept使得特化更加精细了,整个泛型系统从原来“离 散”的变成了“连续”的。
    不过上面那个concept特化的模板看起来实在不算好看,头上那一坨template...实在有碍观瞻。既然是concept based overload,那么何不直接使用重载的形式,而不必再带上累赘的template<...>:
    void fun(anytype a){...} //#1,anytype是伪造的关键字,表示所有类型。这东西最好少用。
    void fun(Integers a){...} //#2,Integers是concept,表示所有整型类型
    void fun(Floats a){...} //#3,Floats是concept,表示所有浮点类型
    void fun(long a){...} //#4
    void fun(int a){...} //#5
    void fun(double a){...} //#6
    ...
    int x=1;
    long y=10;
    short z=7;
    string s="aaa";
    float t=23.4;
    fun(x); //选择#5
    fun(y); //选择#4
    fun(z); //选择#2
    fun(s); //选择#1
    fun(t); //选择#3
    这种形式在语义上与原来的模板形式几乎一样。注意,是几乎。如下的情形是重载形式无法做到的:
    template<Integers T> T swap(T lhs, T rhs) {
        T temp(lhs);
        ...
    }
    这里,模板做到了两件事:其一,模板萃取出类型T,在函数体中,可以使用T执行一些操作,比如上述代码中的临时对象temp的构造。这个问题容易解决,因为萃取类型T还有其他的方法,一个typeof()操作符便可实现:
    Integers swap(Integers lhs, Integers rhs) {
        typeof(lhs) temp(lhs);
        ...
    }
    其二,模板保证了lhs,rhs和返回值都是同一类型。这个问题,可以通过施加在函数上的concept约束解决:
    Integers swap(Integers lhs, Integers rhs)
        requires SameType<lhs, rhs>
            && SameType<lhs, retval> {  //retval是杜撰的关键字,用以表示返回值
        typeof(lhs) temp(lhs);
        ...
    }
    相比之下,重载形式比较繁琐。总体而言,尽管重载形式冗长一些,但含义更加明确,更加直观。并且在concept的接口功能作用下,对参数类型一致的要求 通常并不多见(一般在基本类型,如整型等,的运算处理中较多见。因为这些操作要求类型有特定的长度,以免溢出。其他类型,特别是用户定义类型,通常由于封 装的作用,不会对类型的内部特性有过多要求,否则就不应使用泛型算法)。如果可以改变语法的话,那么就能用诸如@代替typeof,==代替 SameType的方法减少代码量:
    Integers swap(Integers lhs, Integers rhs)
        requires @lhs == @rhs && @lhs == @retval {
        @lhs temp(lhs);
        ...
    }
   

Concept、类型和对象

    事情还可以有更加夸张的发展。前面对泛型进行了特化,能不能对类型也来一番“特化”呢?当然可以:
    void fun(int a);
    void fun(int a:a==0); //对于类型int而言,a==0便是“特化”了
    更完整的,也可以有“局部特化”:
    void fun(int a); //#1
    void fun(int a:a==0); //#2
    void fun(int a:a>200); //#3
    void fun(int a:a<20&&a>10); //#4
    void fun(int a:(a>70&&a<90)||(a<-10)); //#5
    ...
    int a=0, b=15, c=250, d=-50;
    fun(80); //使用#5
    fun(50); //使用#1
    fun(a); //使用#2
    fun(b); //使用#4
    fun(c); //使用#3
    fun(d); //使用#5
    实际上,这无非是在参数声明之后加上一组约束条件,用以表明该版本函数的选择条件。没有约束的函数版本在没有任何约束条件匹配的情况下被选择。对于使用立 即数或者静态对象的调用而言,函数的选择在编译期执行,编译器根据条件直接调用匹配的版本。对于变量作为实参的调用而言,则需要展开,编译器将自动生成如 下代码:
    //首先将函数重新命名,赋予唯一的名称
    void fun_1(int a); //#1
    void fun_2(int a); //#2
    void fun_3(int a); //#3
    void fun_4(int a); //#4
    void fun_5(int a); //#5
    //然后构造分派函数
    void fun_d(int a) {
        if(a==0)
            fun_2(a);
        else if(a>200)
            fun_3(a);
        ...
        else
            fun_1(a);
    }
    在某些情况下,可能需要对一个对象的成员做出约束,此时便可以采用这种形式:
    struct A
    {
        float x;
    };
    ...
    void fun(A a:a.x>39.7);
    ...
    这种施加在类型上的所谓“特化”实际上只是一种语法糖,只是由编译器自动生成了分派函数而已。这个机制在Haskell等语言中早已存在,并且在使用上带 来很大的灵活性。如果没有这种机制,那么一旦需要增加函数分派条件,那么必须手工修改分派函数。如果这些函数,包括分派函数,是第三方提供的代码,那么修 改将是很麻烦的事。而一旦拥有了这种机制,那么只需添加一个相应的函数重载即可。
    当concept-类型重载和类型-对象重载混合在一起时,便体现更大的作用:
    void fun(anytype a);
    void fun(Integers a);
    void fun(Floats a);
    void fun(long a);
    void fun(int a);
    void fun(double a);
    void fun(double a:a==0.8);
    void fun(short a:a<10);
    void fun(string a:a=="abc");
    ...
    concept-类型-对象重载体系遵循一个原则:优先选择匹配的函数中最特化的。这实际上是类型重载规则的扩展。大的来说,所有类型比所属的 concept更加特化,所有对象约束比所属的类型更加特化。对于concept而言,如果concept A refine自concept B,那么A比B更加特化。同样,如果一个类型的约束强于另一个,那么前一个就比后一个更加特化,比如a==20比a>10更加特化。综合起来,可以 有这样一个抽象的规则:两个约束(concept,或者施加在对象上的约束)A和B,作用在类型或者对象上分别产生集合,如果A产生的集合是B产生的集合 的真子集,那么便认为A比B更加特化。
    根据这些规则,实际上可以对一个函数的重载构造出一个“特化树”:

    越接近树的根部,越泛化,越接近叶子,越特化。调用时使用的实参便在这棵“特化树”上搜索,找到最匹配的函数版本。
    concept-类型-对象体系将泛型、类型和对象统一在一个系统中,使得函数的重载(特化)具有更简单的形式和规则。并且,这个体系同样可以很好地在类模板上使用,简化模板的定义和使用。

类模板

    C++的类模板特化形式并不惹人喜爱:
    template<typename T> A{...}; //基础模板
    template<> A<int>{...}; //显式特化(全特化)
    template<typename T> A<T*>{...}; //局部特化
    在C++09中,可以直接用concept定义模板的类型形参:
    template<Integers T> A{...};
    实质上,这种形式本身就是一种局部特化,因而原本那种累赘局部特化形式可以废除,代之以concept风格的形式:
    template<Pointer T> A{...}; //Pointer表示此处采用指针特化模板
    同样,如果推广到全特化,形式也就进一步简单了:
    template<int> A{...}; //这个形式有些突兀,这里只打算表达这个意思,应该有更“和谐”的形式
    如果模板参数是对象,则使用现有的定义形式:
    template<int a> A{...};
    更进一步,可以引入对象的约束:
    template<int a:a>10> A{...};
    此外,C++中在模板特化之前需要有基础模板。但实际上这是多余的,D语言已经取消了这个限制,这对于简化模板的使用有着莫大的帮助。

从本质上讲...

    从本质上讲,我们可以把所有类型看作一个集合T={ti},而concept则是施加在类型集合上的约束。通过concept这个约束,我们便可以获得类 型集合T的一个子集C。理论上,所有concept所对应的类型子集Cj构成了类型集合的幂集{Cj}。在{Cj}中,有两类类型子集是很特殊的。一组是 T本 身,即所有类型。存在一个concept不对T施加任何约束,便得到了C0=T。第二类则是另一个极端,存在一组concept,施加在T上之后所得的类 型子集仅包含一个类型:Ci={ti}。由于这组concept与类型存在一一对应的关系,那么我们便可以用这组concept来指代类型。也就是把类型 作为特殊的concept处理。如此,concept便同类型统一在一个体系中。这种处理可以使我们获得极大的好处。
    这组特殊的concept仍旧使用对应的类型名作为称谓,仍旧称之为“类型”,但其本质上还是concept。任何一个类型,一旦创建,也就创建了相应的特殊concept。如果在模板特化中使用一个类型的时候,实际上就是在使用相对应的那个特殊concept:
    void func(typeA a); //尽管使用了类型名typeA,但实际上这里所指的是typeA所对应的那个特殊concept。
    在这个concept体系的作用下,函数模板的特化和重载整个地统一起来(concept based overload)。
    至于作用在类型上的那种“特化”,也是同样的道理。对于一个类型T而言,它所有的对象构成一个集合O。如果存在一组约束作用于O,那么每 一个约束对应着O的一个子集。理论上,我们可以构造出一组约束,使得他们同O的每一个子集一一对应。同样,这些子集中有两类子集比较特殊。一类是所有对象 的集合。另一类便是只有一个对象的子集。于是,我们可以使用这组特殊对象子集所对应的约束指代相应的对象。也就是将对象看作特殊的约束。如此,类型和对象 也被统一在一个系统中了。
    进而,类型在逻辑上被作为特殊concept处理,对象则被作为特殊的类型处理。于是,这三者便可以统一在一个体系下,一同参与特化。

总结

    尽管形式不能代表本质,但形式的变化往往会带来很多有益的进步。更重要的是,很多本质上的变化总会伴随着形式上的改变。通过将concept、类型和对象 在逻辑上整合到统一的体系之中,便可以促使模板、特化、函数重载等机制在形式上达成统一。从而能够简化这些功能的使用。这也是当前重视语言(工具)易用性 的潮流的一个必然诉求。这个形式上的统一并非语法糖之类的表面变化。而是完全依赖于concept这个新型的类型描述(泛型)系统的确立和发展。 concept的出现,弥补了以往泛型的不足,找回了泛型系统缺失的环节,弥补了泛型同类型之间的裂痕。在此作用下,便可以构建起concept-类型- 对象的抽象体系,用统一的系统囊括这三个原本分立的概念。在这个新的三位一体的系统下,使得模板的特化和重载拥有了相同的形式,进而获得更直观的语义,和 更好的易用性。
posted on 2008-07-26 19:44 longshanks 阅读(1902) 评论(10)  编辑 收藏 引用

Feedback

# re: GP技术的展望——先有鸿钧后有天 2008-07-26 21:25 oldrev
这样的话程序中会不会出现无数只为约束函数参数而没其他作用的 concepts,重走 C#/Java 中 interface 的老路?  回复  更多评论
  

# re: GP技术的展望——先有鸿钧后有天 2008-07-26 22:28 clear
c++0x 的concept不需要显式声明的,比如那个Swapable,任何一个类型,只要有一个满足其条件的swap成员函数,就自动成为这个concept的一个特例存在
所以不会像java里面那样对所有的类都implement一堆的interface  回复  更多评论
  

# re: GP技术的展望——先有鸿钧后有天 2008-07-26 22:33 Kevin Lynx
longshanks终于又发文了。学习。  回复  更多评论
  

# re: GP技术的展望——先有鸿钧后有天 2008-07-26 22:36 空明流转
其实语法糖很重要。。。。  回复  更多评论
  

# re: GP技术的展望——先有鸿钧后有天 [未登录] 2008-07-26 23:06 foxtail
博大精深的C++ 呵呵  回复  更多评论
  

# re: GP技术的展望——先有鸿钧后有天 2008-07-27 00:40 bneliao
gp要一桶浆糊了  回复  更多评论
  

# re: GP技术的展望——先有鸿钧后有天 2008-07-27 06:54 longshanks
to oldrev兄:
我不太理解“只为约束函数参数而没其他作用的 concepts”这个概念,能否给个例子。这个问题我这么想:concept以及runtime concept同oop的interface的差异我以前的blog和toplanguage讨论中都谈论过。本质上,interface是“用一个类型来表征一组类型”,逻辑上就不那么和谐。而concept则是用一个独立的,专门用于描述一组类型的概念实现这个功能。interface的弊端,比如侵入的接口、造成类型耦合等等,在concept中不会存在。运用concept,我们可以消除这部分问题。至于其他的interface问题,可能来自于需求和设计,通常也无法全部通过这种技术手段消除。
当然就像clear兄所说,concept可以auto(需要在定义concept指定auto),这也消除了不少麻烦。只是auto需要谨慎,只有那些含有公共语义约定的concept,比如swappable、copyable等等,以及形式(成员)非常特殊,不可能有其他语义的类型与之混淆的情况下,才可以使用,否则容易引起混乱。  回复  更多评论
  

# re: GP技术的展望——先有鸿钧后有天 2008-07-27 10:07 oldrev
@longshanks

在大多数地方 concept 的用途和 interface 是差不多的,定义一个 Copyable 的 concept 和定义一个 ICopyable 是一样的麻烦,虽然 concept 是非侵入的。
  回复  更多评论
  

# re: GP技术的展望——先有鸿钧后有天 2008-07-27 11:10 longshanks
@oldrev
这个就没办法了。这些接口都是需求设计驱使的,只是不同的手段实现而已。这方面的问题由于没有广泛的应用,还不太清楚,需要实践检验。
concept相比interface的直接好处在于两点:1、不需要在接口实现类型产生前定义concept,任何时候都可以,这样可以减少设计上的压力。这是非侵入的好处。2、concept驱动下的模板在runtime和compiletime是相同的,也就是同一个模板可以同时用于runtime和static,而不需要另搞一套。
间接的好处是会对语言整个模型产生根本性的影响,从而消除语言某些方面的复杂性和缺陷。这个我打算在下一篇blog里探讨。  回复  更多评论
  

# re: GP技术的展望——先有鸿钧后有天 2008-07-28 15:18 oldrev
@longshanks
期待ing....  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理