longshanks

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

常用链接

留言簿(5)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

2008年9月18日 #

三只小猪
莫华枫

    小时候听说过三只小猪的故事,隐约记得故事是讲三只小猪用不同方法造房子,对抗老狼。这些天做软件,遇到一个无比简单的问题,但在三种不同的语言中,却有着截然不同的解法。

    最近,冷不丁地接到公司下派的一个紧急任务,做手持POS和PC程序之间交换数据的程序。各种各样的麻烦中,有一个小得不起眼的问题,POS机中数据的字 节序和PC相反。这可不算是什么啊。没错,是在太简单了。尽管如此,还是引发了一场争论。做POS程序的,希望PC程序做转换。做PC程序的,希望POS 程序做转换。(谁都想少做点,对吧;))。最终,作为和事佬的我,为了维护和谐的氛围,揽下了这件事。当然,到底在那里做,还是要决定的。最终选择在PC 上,毕竟PC上调试起来容易。(天煞的,这个POS机没有debug,也没有模拟器,显示屏还没我手机的大,做起来着实费事)。
    其实,我的本意是想在POS上做这个转换。因为POS用的是C(一个不知什么年代的gcc),可以直接操作字节。基本的代码看起来差不多应该是这样:
        unsigned long InvData(unsigned long val, int n) {
            unsigned long t=val, res=0;
            for(; n >0; n--)
            {
                res = res << 8;
                res |= (unsigned char)t;
                t = t >> 8;
            }
            return res;
        }
    n是数据类型的字节长度。这里使用了最长的无符号整数类型。这是核心转换函数,各种类型的转换函数都可以从中派生:
        long InvDataLong(long val) {
            return (long)InvData((unsigned long)val, sizeof(val));
        }
        short InvDataShort(short val) {
            return (short)InvData((unsigned short)val, sizeof(val));
        }
        ...
    最后,有一个比较特殊的地方,float。float的编码不同于整型,如果直接用(unsigned long)强制类型转换,只会把float数值的整数部分赋予参数,得不到正确的结果。正确的做法,应当是把float占用的四个字节直接映射成一个 unsigned long:
        float InvDataFloat(float val) {
            float val=InvData(*(unsigned long*)(&val), sizeof(val));
            return *(float*)(&val);
        }
    通过将float变量的地址强制转换成unsigned long*类型,然后再dereference成unsigned long类型。当然还有其他办法,比如memcpy,这里就不多说了。至于double类型,为了简化问题,这里将其忽略。如果有64位的整型,那么 double可以采用类似的解法。否则,就必须写专门的处理函数。
    当然,最终我还是使用C#写这个转换。相比之下,C#的转换代码显得更具现代风味。基本算法还是一样:
        public static ulong DataInv(ulong val, int n)
        {
            ulong v1_ = val, v2_ = 0;

            for (; n > 0; n--)
            {
                v2_ <<= 8;
                v2_ |= (byte)v1_;
                v1_ >>= 8;
            }

            return v2_;
        }
    对于习惯于C/C++的同学们注意了,long/ulong在C#中不是4字节,而是8字节。也就是C/C++中的longlong。以这个函数为基础,其它整数类型的字节序转换也就有了:
        public static ulong DataInv(ulong val)
        {
            return DataInv(val, sizeof(ulong));
        }

        public static uint DataInv(uint val)
        {
            return (uint)DataInv((ulong)val, sizeof(uint));
        }

        public static int DataInv(int val)
        {
            return (int)DataInv((uint)val);
        }
        ...
    然而,面对float,出现了麻烦。在C#中,没有指针,无法象C那样将float展开成ulong。(unsafe代码可以执行这类操作,但这不是C#嫡亲的特性,并且是违背C#设计理念的。这里不做考虑)。C#提供了另一种风格的操作:
        public static float DataInv(float val)
        {
            float res_ = 0;

            byte[] buf_ = BitConverter.GetBytes(val);
            byte t = 0;

            t = buf_[0];
            buf_[0] = buf_[3];
            buf_[3] = t;

            t = buf_[1];
            buf_[1] = buf_[2];
            buf_[2] = t;

            res_ = BitConverter.ToSingle(buf_, 0);

            return res_;
        }
    这个做法尽管有些累赘,但道理上很简单:把float变量转换成一个字节流,然后把相应的位置对调,就获得了字节反序的float。相比C的float转 换,C#明显不够简练。原因很简单,C#根本不是用来干这个的。C是一种非常底层的语言,它的内存模型是完全直观的,与硬件系统相对应的。因而,对于这种 与机器相关的操作,当然也显得游刃有余。而C#定位于高层开发的高级语言,底层的内存模型是被屏蔽的,程序员无需知道和关心。
    不过,C#的代码却拥有它的优势。只需看一眼这些函数的使用代码,便不言自明了:
        //C代码
        int x=234;
        float y=789.89;
        short z=332;
        x=InvDataInt(x);
        y=InvDataFloat(y);
        z=InvDataShort(z);

        //C#代码
        int x=234;
        float y=789.89;
        short z=332;
        x=DataInv(x);
        y=DataInv(y);
        z=DataInv(z);
    在C代码中,对于不同的类型,需要使用不同命名的函数。而在C#代码中,则只需使用DataInv这样一个函数名。至于届时选用那个版本的函数,编译器会 根据实际的类型自动匹配。C#运用函数重载这个特性,使得调用代码可以采用统一的形式。即便是数据的类型有所变化,也无需对调用代码做任何修改。(这在我 的开发过程中的得到了验证,传输数据的成员类型曾经发生变化,我也只是修改了数据结构的定义,便将问题搞定)。这一点,在C中是无法做到的。
    归结起来,C由于侧重于底层,在数据转换方便的灵活性,使得转换代码的构建更加容易。而C#则得益于函数重载,在转换代码使用方面,有独到的优势。
    迄今为止,三只小猪中,还只有两只出现。下面就要第三只出场了。
    作为C++的粉丝,我会自然而然地想到使用C++来实现这个转换功能。于是便有了如下的代码:
       unsigned long InvData(unsigned long val, int n) {
            unsigned long t=val, res=0;
            for(; n >0; n--)
            {
                res = res << 8;
                res |= (unsigned char)t;
                t = t >> 8;
            }
        }
        long InvData(long val) {
            return (long)InvData((unsigned long)val, sizeof(val));
        }
        short InvData(short val) {
            return (short)InvData((unsigned short)val, sizeof(val));
        }
        ...
        float InvData(float val) {
            float val=InvData(*(unsigned long*)(&val), sizeof(val));
            return *(float*)(&val);
        }
    这些代码就好象是C和C#代码的杂交后代。既有C的底层操作,也有C#的函数重载,兼有两者的优点。
    不过,还能做得更好:
        template<typename T>
        T InvData(T val) {
            T t=val, res=0;
            int n=sizeof(T);
            for(; n >0; n--)
            {
                res = res << 8;
                res |= (unsigned char)t;
                t = t >> 8;
            }
            return (T)res;
        }
    这样,就把所有的整型都一网打尽了,仅用一个函数模板,便完成了原先诸多函数所做的工作。而float版本的函数则保持不变,作为InvData()的一个重载。按照C++的函数模板-重载规则,float版的函数重载将被优先使用。

    好了,三只小猪的故事讲完了。前两只小猪各有优点,也各有缺点。而第三只小猪则杂合和前两者的优点,并且具有更大的进步。尽管第三只小猪存在各种各样的缺陷,但毕竟它的众多特性为我们带来了很多效率和方便,这些还是应当值得肯定的。

附:第三只小猪的其他手段:
1、强制转换成字符串数组
template<typename T>
T InvData1(T v) {
    unsigned char* pVal1=(unsigned char*)(&v)
        , *pVal2=pVal1+sizeof(T)-1, t;
    while(pVal2-pVal1>1)
    {
        t=*pVal2;
        *pVal2=*pVal1;
        *pVal1=t;
        pVal1++;
        pVal2--;
    }
    return v;
}
2、使用标准库,blog上有人留言建议的
template<typename T>
T InvData(T v) {
    unsigned char* pVal=(unsigned char*)(&v);
    size_t n=sizeof(T);
    std::reverse(pVal, pVal+n, pVal);
}
3、使用traits
template<size_t n> struct SameSizeInt;
template<> struct SameSizeInt<1> { typedef unsigned char Type; };
template<> struct SameSizeInt<2> { typedef unsigned short Type; };
template<> struct SameSizeInt<4> { typedef unsigned long Type; };
template<> struct SameSizeInt<8> { typedef unsigned longlong Type; };

template<typename T>
T InvData(T v) {
    size_t n=sizeof(T);
    typedef SameSizeInt<sizeof(T)>::Type NewT;
    NewT v1=*(NewT*)(&v), v2=0;
    for(; n >0; n--)
    {
        v2= v2<< 8;
        v2|= (unsigned char)v1;
        v1 = v1 >> 8;
    }
    return *(T*)(&v2);
}

甚至可以使用tmp去掉其中的循环。在C++中,这类任务的实现方法,完全看程序员的想象力了。:)
posted @ 2008-09-18 19:25 longshanks 阅读(1591) | 评论 (3)编辑 收藏

2008年8月2日 #

GP技术的展望——C--
莫华枫

    C++的复杂是公认的,尽管我认为在人类的聪明智慧之下,这点复杂压根儿算不上什么。不过我得承认,对于一般的应用而言,C++对程序员产生的压力还是不 小的。毕竟现在有更多更合适的选择。仅仅承认复杂,这没有什么意义。我不时地产生一个念头:有什么办法既保留C++的优点,而消除它的缺点和复杂。我知道 D语言在做这样的事情。但是,D更多地是在就事论事地消除C++的缺陷,而没有在根本上消除缺陷和复杂性。
    一般而言,一样东西复杂了,基本上都是因为东西太多。很显然,C++的语言特性在众多语言中是数一数二的。于是,我便想到或许把C++变成“C--”,可以治好C++的复杂之病。在探讨这个问题之前,让我们先从C出发,看看C++为何如此复杂。

C和C++

    尽管存在这样那样的不足,比如non-lalr的语法、隐式的指针类型转换等,但C语言的设计哲学却是足够经典的。C语言有一个非正式的分类,认为它既非汇编这样的低级语言,也非Pascal那样的高级语言, 而应该算作中级语言,介于其他两类语言之间。这种分类恰如其分地点出了C语言的特点和理念:以高级语言语法形式承载了低级语言的编程模型。低级语言的特点 是可以直接地描述硬件系统的结构。C则继承了这个特点。C语言直观地反映了硬件的逻辑构造,比如数组是内存块,可以等价于指针。在C语言中,我们可以几乎 直接看到硬件的构造,并且加以操作。这些特性对于底层开发至关重要。
    然而,C的这种直观简洁的模型过于底层和琐碎,不利于应用在那些构造复杂、变化多样的应用中。针对C的这些弱点,Bjarne Stroustrup决心利用OOP技术对C语言进行改造,从而促使了C++的诞生。C++全面(几乎100%)地兼容C,试图以此在不损失C语言的直观 和简洁的情况下,同时具备更强的软件工程特性,使其具备开发大型复杂系统的优势。这个目标“几乎”达到了,但是代价颇为可观。
    在经历了80、90年代的辉煌之后,C++的应用领域开始退步。一方面,在底层应用方面,C++的很多特性被认为是多余的。如果不使用这些特性,那么 C++则同C没有什么差别。相反这些特性的使用,对开发团队的整体能力提出了更高的要求。因而,在最底层,很多人放弃了C++而回归了C,因为那些高级特 性并未带来很多帮助,反而产生了很多负担。另一方面,在高层开发中,业务逻辑和界面也无需那么多底层的特性和苛刻的性能要求,更多简单方便、上手容易的语 言相比C++更加适合。C++的应用被压缩在中间层,随着业界系统级开发的不断专业化,C++的使用规模也会越来越小。(当然,它所开发的应用往往都是关 键性的,并且是没有选择余地的)。实际上,C++在这个层面也并非完美的工具。目前无法取代是因为没有相同级别的替代品。D或许是个强有力的竞争者,但一 方面出于历史遗留代码的规模和应用惯性,另一方面D也并未完全解决C++面临的复杂性问题,D也很难在可见的将来取代C++。
    实际上,C++的这种尴尬地位有着更深层次的原因。C++的本意是在保留C的底层特性基础上,增加更好的软件工程特性。但是,C++事实上并未真正意义上 地保留C的底层特性。回顾一下C的设计理念——直观而简洁地反映底层硬件的特性。C++通过兼容C获得了这种能力。但是这里有个问题,如果我要获得C的这 种简单直观性,就必须放弃C++中的很多高级特性。这里最明显的一个例子便是pod(plain old data)。
    在C中压根没有pod的概念,因为所有的对象都是pod。但是,C++中有了pod。因为C++的对象可能不是一个pod,那么我们便无法象在C当中那样 获得直观简洁的内存模型。对于pod,我们可以通过对象的基地址和数据成员的偏移量获得数据成员的地址,或者反过来。但在非pod对象中,却无法这么做。 因为C++的标准并未对非pod对象的内存布局作出定义,因而对于不同的编译器,对象布局是不同的。而在C中,仅仅会因为底层硬件系统的差异而影响对象布 局。
    这个问题通常并不显而易见。但在很多情况下为我们制造了不小的障碍。比如,对象的序列化:我们试图将一个对象以二进制流的形式保存在磁盘中、数据库中,或 者在网上传输,如果是pod,则直接将对象从基地址开始,按对象的大小复制出来,或传输,或存储,非常方便。但如果是非pod,由于对象的不同部分可能存 在于不同的地方,因而无法直接复制,只能通过手工加入序列化操作代码,侵入式地读取对象数据。(这个问题不仅仅存在于C++,其他语言,如java、C# 等都存在。只是它们没有很强烈的性能要求,可以使用诸如reflect等手段加以处理)。同样的问题也存在于诸如hash值的计算等方面。这对很多开发工 作造成不小的影响,不仅仅在底层,也包括很多高层的应用。
    究其原因,C++仅仅试图通过机械地将C的底层特性和OOP等高层特性混合在一起,意图达到两方兼顾的目的。但是,事与愿违,OOP的 引入实际上使得C的编程模型和其他更高级的抽象模型无法兼容。在使用C++的过程中,要么只使用C的特性,而无法获得代码抽象和安全性方面的好处,要么放 弃C的直观简洁,而获得高层次的抽象能力。反而,由于C和OOP编程模型之间的矛盾,大大增加了语言的复杂性和缺陷数。

舍弃

    但是,我们可以看到在C++中,并非所有的高级特性都与C的底层特性相冲突。很多使用C而不喜欢C++的人都表示过他们原意接受OB,也就是仅仅使用封装 。对于RAII,基本上也持肯定的态度。或许也会接受继承,但也表露出对这种技术带来的复杂性的担心。动多态是明显受到排斥的技术。显然这是因为动多态破坏了C的编程模型,使得很多本来简单的问题复杂化。不是它不好,或者没用,是它打破了太多的东西。
    因而,我们设想一下,如果我们去除动多态特性,那么是否会消除这类问题呢?我们一步步看。
    动多态的一个基本支撑技术是虚函数。在使用虚函数的情况下,类的每一次继承都会产生一个虚函数表(vtable),其中存放的是指向虚函数的指针。这些虚函数表必须存放在对象体中,也就是和对象的数据存放在一起(至少要关联在一起)。因而,对象在内存里并不是以连续的方式存放,而被分割成不同的部分,甚至身首异处(详见《Inside C++ Object Model》)。这便造成了前面所说的非pod麻烦。一旦放弃虚函数和vtable,对象的内存布局中,便不会有东西将对象分割开。所有的对象的数据存储都是连续的,因而都是pod。在这一点上,通过去除vtable,使得语言回归了C的直观和简单。
    动多态的内容当然不仅仅是一个虚函数,另一个重要的基石是继承。当然,我们并不打算放弃继承,因为它并不直接破坏C的直观性和简洁性。不同于虚函数,继承 不是完全为了动多态而生的。继承最初的用途在于代码复用。当它被赋予了多态含义后,才会成为动多态的基础。以下的代码可以有两种不同的解读:
    class B : public A {};
    从代码复用的角度来看,B继承自A,表示我打算让B复用A的所有代码,并且增加其他功能。而从多态的角度来看,B是一个A的扩展,B和A之间存在is-a的 关系。(B是一个A)。两者是站在不同层面看待同一个问题。代码复用,代表了编码的观点,而多态,则代表了业务逻辑的观点。但是,两者并非实质上的一回 事。在很多情况下,基类往往作为继承类的某种代表,或者接口,这在编码角度来看并没有对等的理解。而这种接口作用,则是动多态的基础。动多态通过不同的类 继承自同一个基类,使它们拥有共同的接口,从而可以使用统一的形式加以操作。作为一个极端,interface(或者说抽象基类),仅仅拥有接口函数(即vtable)而不包含任何数据成员。这是纯粹的接口。
    然而,这里存在一个缺陷。一个接口所代表的是一组类,它将成为这一组类同外界交互的共同界面。但是,使用基类、或者抽象基类作为接口,实质上是在使用一个 类型来代表一组类型。打个比方,一群人凑在一起出去旅游,我们称他们这群人为“旅行团”。我们知道旅行团不是一个人,而是一个不同于“人”的概念。动多态 里的接口相当于把一个旅行团当作一个人来看待。尽管这只是逻辑上的,或许一个旅行团的很多行为和一个人颇为相似。但是根本上而言,两者毕竟不是相同层次的 概念。这样的处理方法往往会带来了很多弊端。
    为了使继承被赋予的这重作用发挥作用,还需要一项非常关键的处理:类型转换。请看以下代码:
    void func(A* a);
    B b;
    func(&b);
    最后这行代码施行了动多态,如果B override了A的虚函数的话。很显然,如果严格地从强类型角度而言,&b是不应当作为func的实参,因为两者类型不匹配。但是如果拒绝接 受&b作为实参,那么动多态将无法进行下去。因此,我们放宽了类型转换的限制:允许继承类对象的引用或指针隐式地转换成基类的引用或指针。这样, 形如func(&b);便可以顺理成章地成为合法的代码。
    然而,这也是有代价的:
    B ba[5];
    func(ba);
    后面这行函数调用实际上是一个极其危险的错误。假设在func()中,将形参a作为一个类型A的数组对待,那么当我们使用ba作为实参调用func()的 时候,会将ba作为A的 数组处理。我们知道,数组内部元素是紧挨着的,第二个元素的位置是第一个元素的基址加上元素的尺寸,以此类推。如果传递进来的对象数组是B类型的,而被作 为A类型处理,那么两者的元素位置将可能不同步。尽管B继承自A,但是B的尺寸很有可能大于A,那么从第二个元素起,a[1]的地址并非ba[1]的地 址。于是,当我们以a[1]访问ba时,实际上很可能在ba[0]的内部某个位置读取,而func()的代码还以为是在操作ba[1]。这便是C++中的 一个重要的陷阱——对象切割。这种错误相当隐蔽,危险性极大。
    由于C++试图保留C的编程模型,因而保留了指针-数组的等价性。这种等价性体现了数组的本质。这在C中是一项利器,并无任何问题。但在C++中,由于存 在了继承,以及继承类的隐式类型转换,使得这种原本滋补的特性成为了一剂毒药。换句话说,C++所引入的动多态破坏了C的直观性。

舍弃之后

    从上面的分析来看,动多态同C的编程模型是不相容的。因而如果希望得到C的直观性,并且消除C++的缺陷,必须放弃动多态这个特性。现在来看看放弃之后将会怎样。
    一旦放弃了动多态,也就放弃了虚函数和vtable。此时,所有的对象都是pod了。那么首当其冲的好处,就是可以进行非侵入的序列化、hash计算等等 操作。由于对象肯定是连续分布的,可以直接地将对象取出进行编码、存储、计算和传输,而无需了解对象内部的数据结构和含义。另外一个重要的问题也会得到解 决,这就是ABI。在C中统一的ABI很自然地存在于语言中。我们可以很容易地用link将两个不同编译器编译的模块连接起来,而不会发生问题。但 是,C++中做不到,除非不再使用类而使用纯C。目前C++还没有统一的ABI,即便标准委员会有意建立这样的规范,实现起来也绝非易事。但是,如果放弃 动多态之后,对象的布局便回归到C的形态,从而使得ABI不再成为一个问题。
    另一方面,随着动多态的取消,那么继承的作用被仅仅局限于代码复用,不再具有构造接口的作用。我们前面已经看到,继承类向基类的隐式转换,是为了使基类能 够顺利地成为继承类的接口。既然放弃了动多态,那么也就无需基类再承担接口的任务。那么由继承类向基类的隐式类型转换也可以被禁止:
    void func(A* a);
    B b;
    func(&b);  //编译错误,类型不匹配
    进而对象切割也不会发生:
    B ba[5];
    func(ba); //编译错误,类型不匹配
    尽管根据数组-指针的等价性,ba可以被隐式地转换为B*,但是B*不再能够隐式地转换为A*,从而避免了对象的切割。
    问题是,如此简单地将动多态放弃掉,就如同将水和孩子一起泼掉那样,实际上放弃了动多态带来的好处。实际上并非如此。我们放弃动多态这个特性,但并不打算放弃它所具有的功能,而是用另一种技术加以替代。这便是runtime concept(这里这里)。
    不同于以类型为基础的interface,concept是独立于类型的系统。concept生来便是为了描述一组类型,因而是接口最理想的实现手段。当concept runtime化之后,便具有了与动多态相同的功能(很多方面还有所超越)。
    runtime concept同样需要类似vtable的函数分派表,但由于它不是类型,这些分派表无需存放在对象内部,可以独立放置(可以同RTTI信息放在一起), 并且只需一份。正是基于这个特性,方才保证了所有对象依然是pod,依然能够保证对象布局的直观性。
    同样,runtime concept承担了接口的任务,但不象动多态那样依赖于继承和相应的隐式类型转换。(通过自动或手动的concept_map)。因而,我们依旧可以禁止基于继承关系的隐式类型转换,从而防止对象切割的情况。
    一旦使用concept作为多态的实现手段,反倒促使原本动多态的一些麻烦得到消除。在动多态中,必须指定virtual函数。如此,在一个类中会存在两 种不同形态的函数,实现动多态的虚函数,和无此功能的普通函数。准确地维护这样两种函数,颇有些难度。而且,函数是虚还是不虚,牵涉到系统的设计,必须在 最初构建时确定,否则以后很难修改。但在放弃动多态,使用concept的情况下,只要一个继承类中,使用相同的签名覆盖基类中的函数,便实现了多态。当 进行concept_map,即将接口与类绑定时,只会考虑继承类的函数,而忽略基类中被覆盖的函数。于是,只需简单的覆盖,便实现了多态的控制。对于是 否多态一个函数,即是否改变基类函数的行为,完全由继承类控制,在创建基类时不必为此伤神。其结果就是,我们无需在系统设计的最初一刻就操心多态的问题, 而只需根据实现的需要随时实现。

其他

    存在大量隐式转换也是C++常受人诟病的一个方面,(特别是那些Pascal系的程序员)。隐式转换的目的是带来方便,使得编码更加简洁,减少冗余。同时也使得一些技巧得以施行。但是,隐式转换的副作用也颇为可观。比如:
    void fun(short a);
    long a=1248;
    fun(a); //顶多一个警告
    这种转换存在两面性:一方面,它可能是合理的,因为尽管a类型long大于short,但很可能存放着short可容纳的数值;但另一方面,a的确存在short无法容纳的可能性,这便会造成一个非常隐蔽的bug。
    C/C++对此的策略是把问题扔给程序员处理,如果有bug那是程序员的问题。这也算得上合情合理,毕竟有所得必有所失,也符合C/C++的一贯理念。但 终究不是最理想的方式。但是如果象Pascal那样将类型管得很死,那么语言又会失去灵活性,使得开发的复杂性增加。
    如果试图禁止隐式类型转换,那么为了维持函数使用代码的简洁性,函数必须对所有的类型执行重载。这大大增加了函数实现的负担,并且重复的代码严重违背了DRY原则。
    现在或许存在一些途径,使得在维持绝对强类型的情况下获得所希望的灵活性。钥匙可能依然在concept手上。考虑如下的代码:
    void fun(Integers a);
    long a=1248;
    fun(a);
    longlong b=7243218743012;
    fun(b);
    此处,fun()是一个函数,它的形参是一个concept,代表了所有的整型。这样,这个函数便可以接受任何一种整型(或者具有整型行为的类型)。我们 相信,在一般的应用下,任何整数都有完全相同的行为。因此,我们便可以很方便地使用Integers这个接口执行对整数的操作,而无需关心到底是什么样的 整数。
    如此,我们便可以在禁止隐式类型转换,不使用函数重载的情况下,完成这种函数的编写。同时可以得到更好的类型安全性。

    强制类型转换是非常重要的特性,特别是在底层开发时。但也是双刃剑,往往引来很隐蔽的错误。强制类型转换很多情况下是无理的,通常都是软件的设计问题造成的。但终究还是有一些情况,需要它来处理。
    设想这样一个场景:两个一模一样的类型,但它们分属不同的函数。(这种情形尽管不多见,但还是存在的。这往往是混乱设计的结果。当然也有合理的情况,比如 来自两个不同库的类型)。我现在需要写一个函数,能够同时使用这两个类型。比较安全一些的,可以用函数重载。但是两个重载的函数代码是一样的,典型的冗余 代码。当然也可以针对其中一个结构编写代码,然后在使用时,对另一个结构的实例执行强制类型转换。但是,强制类型转换毕竟不是件好事。因此,我们也可以构 造一个concept,让它描述这两个类型。然后在编写函数时使用这个concept,当这两个类型都与concept绑定后,便可以直接使用这两个类 型,而没有类型安全和代码冗余的问题。
    (顺便提一下,这种方式也可以运用在类型不同的情况下。比如两个类型不完全相同,但是基本要素都一样。那么就可以使用concept_map的适配功能, 将两个类型统一在一个concept下。这种方式相比oop的Adapter模式,更加简洁。adapter本身是一个container,它所实现的接 口函数,都必须一一转发到内部的对象,编写起来相当繁琐。但在concept_map中,对于那些符合concept描述的函数无需另行处 理,concept会自动匹配,只需对那些不符合要求的函数执行适配。)

    前面说过,指针数组的等价性体现了一种直观的编程模型。但是,指针和数组毕竟还是存在很多差别,比如指针仅仅表达了一组对象在内存中的位置,但并未携带对象数量的信息。因而,当数组退化成指针时,便已经失去了数组的身份:
    void func(int* x);
    int a[20];
    func(a);
    这里,在函数func中已经无法将a作为数组处理,因为无法知道变成int*后的a有多大来避免越界。甚至我们无法把a作为多个对象构成的内存块看待,因为我们不知道大小。因此,只有显式地给出数组大小,才能使用:
    void func(int* x, long size);
    但是,在concept的作用下,数组和指针得以依然保持它们的等价性的情况下,解决数组退化问题。考虑这样两个函数:
    void func1(Pointer x);
    void func2(Container x);
    其中,Pointer是代表指针的concept,而Container则是代表容器的concept。必须注意的是,Pointer是严格意义上的指 针,也就是说无法在Pointer上执行迭代操作。Pointer只能作为指针使用,只具备dereference的能力(很像java的“指针”,不是 吗?concept在没有放弃C的底层特性的情况下也做到了。)。而Container则是专门用来表达容器的concept,其基本的特性便是迭代。在 func1中,无法对形参x执行迭代,仅仅将其作为指向一个对象的指针处理,保证其安全性。而对于需要进行迭代操作的func2而言,x则是可以遍历的。 于是,对于同一个数组a,两个函数分别从不同的角度对其进行处理:
    int a[20];
    func1(a); //a直接作为指针处理,但不能迭代
    func2(a); //a作为容器处理,可以迭代,并且其尺寸信息也一同传入
    此处实际上是利用了concept对类型特性的描述作用,将具有两重性的数组类型(数组a即代表了数组这个容器,也代表了数组的起始地址)以不同特征加以 表达,以满足不同应用的需求。数组仍然可以退化成指针,C的直观模型得到保留,在很多特殊的场合发挥作用。但在其他应用场景,可以更加安全地使用数组。
   

总结

    综上所述,C++未能真正延续C的直观简洁,主要是由于动多态的一些基础设施破坏了C的编程模型。因而,我们可以通过放弃动多态,及其相关的一些技术,代 之以更加“和谐”的runtime concept,使得C++在基本保留C的编程模型的同时,获得了相比原来更好的软件工程特性。至此,这种改变后的C++(如果还能称为C++的话)拥有 如下的主干特性:
    1、SP,来自于C。
    2、完全pod化。
    3、OB。保留了封装和RAII。尽管也保留了继承,但其作用仅限于代码复用,禁止基于继承的隐式类型转换。
    4、GP,包括static和runtime concept。这是抽象高级特性的核心和基石。
    这样的语言特性实质上比现有的C++更加简洁,但是其能力更加强大。也比C++更易于贴近C的编程模型,以便适应底层的开发。我不能说这样的变化是否会产生一个更好的语言,但是我相信这些特性有助于构造更加均衡统一的语言。
posted @ 2008-08-02 20:57 longshanks 阅读(2705) | 评论 (14)编辑 收藏

2008年7月26日 #

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 @ 2008-07-26 19:44 longshanks 阅读(1759) | 评论 (10)编辑 收藏

2008年2月26日 #

     摘要: C++的营养 莫华枫     上一篇《C++的营养——RAII》中介绍了RAII,以及如何在C#中实现。这次介绍另一个重要的基础技术——swap手法。 swap手法     swap手法不应当是C++独有的技术,很多语言都可以实现,并且从中得到好处。只是C++存在的一些缺陷迫使大牛们发掘,并开始重视这种有用的手法。这 个原...  阅读全文
posted @ 2008-02-26 15:16 longshanks 阅读(3487) | 评论 (3)编辑 收藏

2008年2月16日 #

     摘要: C++的营养 莫华枫     动物都会摄取食物,吸收其中的营养,用于自身生长和活动。然而,并非食物中所有的物质都能为动物所吸收。那些无法消化的物质,通过消化道的另一头(某些动 物消化道只有一头)排出体外。不过,一种动物无法消化的排泄物,是另一种动物(生物)的食物,后者可以从中摄取所需的营养。    一门编程语言,对于程序...  阅读全文
posted @ 2008-02-16 08:19 longshanks 阅读(1779) | 评论 (2)编辑 收藏

2008年2月14日 #

瓦格纳的排场

    这个春节过的实在无趣。走完亲戚,招待完亲戚,逛街买好东西,就没多少时间了。看书的兴致也没了。想写点什么,总是没法集中精力。实在腻味了,把以前下载的瓦格纳的歌剧《尼伯龙根指环》拿出来看看。自从下载,没怎么好好看过,这回算是补上了。
    瓦格纳的“指环”系列可以算是歌剧里的极品,总共四出:莱茵黄金、女武神、齐格佛雷德和众神的黄昏。分成四个晚上连演,总共加起来大约15个小时。不说别 的,里面的角色众多,光神就有8个,人有7个,女武神9个,尼伯龙根矮人2个,还有三个仙女、2个巨人,和一只小鸟(在后台的女高音)。情节错综复杂,音 乐更是宏大。资料上说,这部歌剧中有200多个动机组合、交织在一起。不过,这还不能表现出瓦格纳在音响上近乎变态的追求。指环系列要求一个超过100人 庞大的乐团,并且引入了几种新的乐器,包括 Wagner tuba, bass trumpet和contrabass trombone。其中, Wagner tuba还是他为这部歌剧专门发明的。最夸张的是,瓦格纳为了获得如此庞大的乐队同演员声音之间的平衡,专门建造了一座歌剧院,也就是著名的拜罗伊特节日剧院(Bayreuth Festspielhaus)。这在音乐史上是绝无仅有的。正是由于这种骇人的排场,造就了歌剧史上的巅峰之作。
    这倒让我联想到C++。说实在的,C++的使用,有时也同瓦格纳谱写的歌剧那样,非常复杂、庞大,需要大量的投入,和前期准备。有时,为了一些应用,而去构造一些的基础设施(就像
拜罗伊特节日剧院)。这种庞大导致了应用面的狭窄,但是却能够获得极品般的东西。这种东西当然不会是到处都有,但却是强大的、伟大的,以及关键性的。
    当然,排场仅仅是表面的东西,真正吸引人的,还是瓦格纳的音乐。歌剧在瓦格纳手里,不再是一系列的咏叹调。瓦格纳是在用音乐讲故事。音乐是歌剧的一部分, 歌唱是音乐的一部分,布景、灯光和舞台效果都是不可分割的一分子。所有这些是一个整体,除了个别出彩的乐段(基本上只有“飞驰的女武神”这一段,曾被用在 电影“现代启示录”中),很少单独演奏。它们戏剧性太强了,脱离了歌剧,就仅仅是一堆音符而已。
    这一点上,C++也是如此,语言、库、惯用法等等,都是整体,一旦相互脱离,便无法发挥应有的作用。所以孤立地运用C++某一方面的特性,往往会误入歧途,只有综合运用各种手段,才能真正地用好C++。
    瓦格纳庞大复杂和莫扎特的简洁优雅形成了鲜明的对比。但是我们不能说莫扎特比瓦格纳更好,或者反过来。他们的音乐都是最伟大的杰作,一个人可以毫无冲突地 同时成为他们俩人的粉丝(就像我:))。我们总能从中获得想像、思考、思想和伦理,两者都具备无法替代的营养。认真地学习和吸收,才是正道。
    编程语言的学习和使用,又何尝不是如此呢?

注:严格地说,瓦格纳的这些作品并不是歌剧,有一个正式的名称:music drama,直接翻译是“音乐戏剧”,是歌剧的扩展。但是为了方便,还是广义上地将其称作歌剧。
posted @ 2008-02-14 11:25 longshanks 阅读(1076) | 评论 (1)编辑 收藏

2008年1月25日 #

当GPL遇上MP

莫华枫

    GPL,也就是General Purpose Language,是我们使用的最多的一类语言。传统上,GPL的语法,或者特性,是固态的。然而,程序员都是聪明人(即便算不上“最聪明”,也算得上 “很聪明”吧:)),往往不愿受到语法的束缚,试图按自己的心意“改造”语言。实际上,即便是早期的语言,也提供了一些工具,供聪明人们玩弄语法。我看的第一本C语言的书里,就有这么一个例子,展示出这种“邪恶”的手段:
      #define procedure void
      #define begin {
      #define end }
    然后:
      procedure fun(int x)
      begin
          ...
      end
    实际上,它的意思是:
      void fun(int x)
      {
          ...
      }
    这可以看作是对初学C语言的Pascal程序员的安慰。这种蹩脚的戏法可以算作元编程的一种,在一种语言里创造了另一个语法。不过,实在有些无聊。然而,在实际开发中,我们或多或少地会需要一些超出语法范围的机制。有时为了完善语言,弥补一些缺憾;有时为了增强一些功能;有时为了获得一些方便。更新潮的,是试图在一种GPL里构建Domain Specific Language,或者说“子语言”,以获得某个特性领域上更直观、更简洁的编程方式。这些对语言的扩展需求的实现,依赖于被称为Meta- Programming(MP)的技术。
    另一方面,随着语言功能和特性的不断增加,越来越多的人开始抱怨语言太复杂。一方面:“难道我们会需要那些一辈子也用不到几回的语言机制,来增加语言的复杂性和学习使用者的负担吗?”。另一方面:“有备无患,一个语言机制要到迫在眉睫的时候才去考虑吗?”。但MP技术则将这对矛盾消弭于无形。一种语言,可以简洁到只需最基本的一些特性。而其他特定的语言功能需求,可以通过MP加以扩展。如果不需要某种特性,那么只要不加载相应的MP代码即可,而无需为那些机制而烦恼。
    MP最诱人的地方,莫过于我们可以通过编写一个代码库便使得语言具备以往没有的特性。
    然而,全面的MP能力往往带来巨大的副作用,以至于我们无法知道到底是好处更多,还是副作用更多。语言的随意扩展往往带来某些危险,比如语法的冲突和不兼容,对基础语言的干扰,关键字的泛滥等等。换句话说,MP是孙悟空,本领高强。但没有紧箍咒,是管不住他的。
    那么,紧箍咒是什么呢?这就是这里打算探讨的主题。本文打算通过观察两种已存在的MP技术,分析它们的特点与缺陷,从中找出解决问题的(可能)途径。

AST宏

    首先,先来看一下宏,这种远古时代遗留下来的技术。以及它的后裔,ast宏。
    关于传统的宏的MP功能,上面的代码已经简单地展示了。但是,这种功能是极其有限的。宏是通过文本替换的形式,把语言中的一些符号、操作符、关键字等等替换成另一种形式。而对于复杂的语法构造的创建无能为力。问题的另一面,宏带来了很多副作用。由于宏的基础是文本替换,所以几乎不受语法和语义的约束。而且,宏的调试困难,通常也不受命名空间的约束。它带来的麻烦,往往多于带来的好处。
    ast宏作为传统宏的后继者,做了改进,使得宏可以在ast(Abstract Syntax Tree)结构上执行语法的匹配。(这里需要感谢TopLanguage上的Olerev兄,他用简洁而又清晰的文字,对我进行了ast宏的初级培训:))。这样,便可以创造新的语法:
      syntax(x, "<->", y, ";")
      {
          std::swap(x, y);
      }
    当遇到代码:
      x <-> y;
    的时候,编译器用std::swap(x,y);加以替换。实际上,这是将一种语法结构映射到另一个语法结构上。而ast宏则是这种映射的执行者。
    但是,ast宏并未消除宏本身的那些缺陷。如果x或者y本身不符合swap的要求(类型相同,并且能复制构造和赋值,或者拥有swap成员函数),那么 ast宏调用的时候无法对此作出检验。宏通常以预编译器处理,ast宏则将其推迟到语法分析之时。但是此时依然无法得到x或y的语义特征,无法直接在调用点给出错误信息。
    同时,ast宏还是无法处理二义性的语法构造。如果一个ast宏所定义的语法构造与主语言,或者其他ast宏的相同,则会引发混乱。但是,如果简单粗暴地将这种“重定义”作为非法处理,那么会大大缩小ast宏(以及MP)的应用范围。实际上,这种语法构造的重定义有其现实意义,可以看作一种语法构造的“重载”,或者函数(操作符)重载的一种扩展。
    解决的方法并不复杂,就是为ast宏加上约束。实际上,类似的情形在C++98的模板上也存在,而C++则试图通过为模板添加concept约束加以解决。这种约束有两个作用:其一,在第一时间对ast宏的使用进行正确性检验,而无需等到代码展开之后;其二,用以区分同一个语法构造的不同版本。
    于是,对于上述例子可以这样施加约束(这些代码只能表达一个意思,还无法看作真正意义上的MP语法):
      syntax(x, "<->", y, ";")
           where x,y is object of concept (has_swap_mem or (CopyConstructable and Assignable))
                && typeof(x)==typeof(y)
      {
          std::swap(x,y);
      }
    如此,除非x,y都是对象,并且符合所指定的concept,否则编译器会当即加以拒绝,而且直截了当。
    不过,如此变化之后,ast宏将不会再是宏了。因为这种约束是语义上的,必须等到语义分析阶段,方能检验。这就超出了宏的领地了。不过既然ast宏可以从预处理阶段推迟到语法分析阶段,那么再推迟一下也没关系。再说,我们关注的是这种功能,带约束的ast宏到底是不是宏,也无关紧要。

TMP

    下面,我们回过头,再来看看另一种MP技术——TMP(参考David Abrahams, Aleksey Gurtovoy所著的《C++ Template Metaprogramming》)。对于TMP存在颇多争议,支持者认为它提供了更多的功能和灵活性;反对者认为TMP过于tricky,难于运用和调试。不管怎么样,TMP的出现向我们展示了一种可能性,即在GPL中安全地进行MP编程的可能性。由于TMP所运用的都是C++本身的语言机制,而这些机制都是相容的。所以,TMP所构建的 MP体系不会同GPL和其他子语言的语法机制相冲突。
    实际上,TMP依赖于C++的模板及其特化机制所构建的编译期计算体系,以及操作符的重载和模板化。下面的代码摘自boost::spirit的文档:
      group = '(' >> expr >> ')';

      expr1 = integer | group;

      expr2 = expr1 >> *(('*' >> expr1) | ('/' >> expr1));

   expr = expr2 >> *(('+' >> expr2) | ('-' >> expr2));

    这里表达了一组EBNF(语法着实古怪,这咱待会儿再说):>>代表了标准EBNF的“followed by”,*代表了标准EBNF的*(从右边移到左边),括号还是括号,|依旧表示Union。通过对这些操作符的重载,赋予了它们新的语义(即EBNF的相关语义)。然后配合模板的类型推导、特化等等机制,变戏法般地构造出一个语法解析器,而且是编译时完成的。

    尽管在spirit中,>>、*、|等操作符被挪作他用,但是我们依然可以在这些代码的前后左右插入诸如:cin>> *ptrX;的代码,而不会引发任何问题。这是因为>>等操作符是按照不同的类型重载的,对于不同类型的对象的调用,会调用不同版本的操作符重载,互不干扰,老少无欺。

    但是,TMP存在两个问题。其一,错误处理不足。如果我不小心把第二行代码错写成:expr1 = i | group;,而i是一个int类型的变量,那么编译器往往会给出一些稀奇古怪的错误。无非就是说类型不匹配之类的,但是很晦涩。这方面也是TMP受人诟病的一个主要原因。好在C++0x中的concept可以对模板作出约束,并且在调用点直接给出错误提示。随着这些技术的引入,这方面问题将会得到缓解。

    其二,受到C++语法体系的约束,MP无法自由地按我们习惯的形式定义语法构造。前面说过了,spirit的EBNF语法与标准EBNF有不小的差异,这对于spirit的使用造成了不便。同样,如果试图运用TMP在C++中构造更高级的DSL应用,诸如一种用于记账的帐务处理语言,将会遇到更大的限制。实际上TMP下的DSL也很少有令人满意的。

    所以说,TMP在使用上的安全性来源于操作符复用(或重载)的特性。但是,操作符本身的语法特性是固定的,这使得依赖于操作符(泛化或非泛化)重载的TMP不可能成为真正意义上的MP手段。

    那么,对于TMP而言,我们感兴趣的是它的安全性和相容性。而对其不满的,则是语法构造的灵活性。本着“去其糟粕,取其精华”的宗旨,我们可以对TMP做一番改进,以获得更完整的MP技术。TMP的核心自然是模板(类模板和函数/操作符模板),在concept的帮助下,模板可以获得最好的安全性和相容性。以此为基础,如果我们将模板扩展到语法构造上,那么便可以在保留TMP的安全性和相容性的情况下,获得更大的语法灵活性。也就是说,我们需要增加一种模板——语法模板

      template<typename T>
      syntax synSwap=x "<->" y ";"
         require SameType<decltype(x), T> && SameType<decltype(y), T>
                && (has_swap_mem<T> || (CopyConstructable<T> and Assignable<T>)
      {
          std::swap(x, y);
      }

    这里我杜撰了关键字syntax,并且允许为语法构造命名,便于使用。而语法构造描述,则是等号后面的部分。require沿用自C++0x的concept提案。稍作了些改造,允许concept之间的||。

用户定义的语法

    如果比较带约束的ast宏和语法模板,会发现极其相似。实际上,两者殊途同归,展示了几乎完全相同的东西。ast宏和TMP分别位于同一个问题的两端,当它们的缺陷得到弥补时,便会相互靠拢,最终归结到一种形式上。 

    现在,通过结合两种方案的特色,我们便可以得到一个最终的MP构造,既安全,又灵活:

      syntax synSwap=x "<->" y ";";

      where

          (x,y is object)

          && SameType<x, y>

          && (has_swap_mem<x> || (CopyConstructable<x> and Assignable<x>))

      {

          std::swap(x, y);

      }

    我去掉了template关键字,在约束(where)的作用下,template和类型参数列表都已经没有必要了。同时,也允许直接将对象放入 concept:Assignable<x>,这相当于:Assignable<decltype<x>>。

    “is ...”是特别的约束,用来描述那些超越concept范畴的特性。“...”可以是关键字“object”,表明相应的标识符是对象;也可以是关键字 “type”,表明相应的标识符是类型;或者是关键字“concept”,指定相应的标识符是concept等等。操作符的重载所涉及的参数只会是对象,只需对其类型做出约束,因此concept便足够使用。但语法构造的定义则广大的多,它不仅仅会涉及对象,更可能涉及其它类型的语法要素。实际上,语法构造所面对的参数是“标识符”。那么一个标识符上可能具备的各种特性,都应当作为约束的内容。这里大致归纳出以下几点需要约束的特性:

  1. 分类。对象、类型、concept、函数等等。is ...;
  2. 来源。来自哪个namespace。from ...;
  3. 尺寸。类型大小。sizeof(x)>20;
  4. 从属。指定一个语法构造是否从属于其他语法构造(其他语法构造的一部分)。如果是从属语法构造,那么将不能单独出现在独立的语句中。更进一步,可以强行指定一个语法构造从属于某个语法构造,不允许在其他语法构造中使用。belong_to ...;
  5. 类型及对象间的关系。诸如继承、子对象、子类型、true typedef、别名、成员等等。
  6. ...

    也可以认为,语法构造的约束是concept的自然延伸。concept对类型做出约束,而语法构造的约束的对象,则是标识符。

    为了强化语法构造的创建能力,应当允许在语法构造的定义中使用BNF,或其他类似的语法描述语言。

    在语法构造约束的支援下,便可以化解一些子语言同宿主语言之间的语法冲突。比如,我们创建了一种类似spirit的EBNF子语言,可以按照标准的EBNF形式编写语法,构造一个语法解析器:

      syntax repeat1=p '+'

      where

          p is object of type(Parser)

      {...}

    这样便定义了一个后缀形式的+操作符,但仅仅作用于类型Parser的对象上。对于如下的代码:

      letter + number

    使用主语言的+(加),还是使用EBNF的+(重复,至少一次),取决于letter和number的特征(这里是类型):

      int letter, number;

      letter + number; //使用主语言的+,表示letter加number

      Parser letter, number;

      letter + number; //使用EBNF的+,表示一串letter后面跟一个number

    如此,便使得用户定义的语法不会同主语言的相同语法发生冲突。

    但是,语法构造的约束并不能完全消除所有的语法冲突。其中一种情况便是常量的使用。比如:

      'x' + 'y'

    它在宿主语言中,会被识别为两个字符的相加。但在BNF子语言中,则会是若干个字符'x'之后紧跟一个‘y'。由于没有类型、对象等代码实体的参与,编译器无法分辨使用哪种语言的语法规则来处理。解决的方法是使得常量类型化。这种做法在C++等语言中已经运用多年。通常采用为常量加前后缀:

      'x'b_ + 'y'b_

    以此代表BNF子语言的常量。常量的语法定义可以是:

      syntax bnf_const="'" letter "'" "b_";

      where

          is const of ... //...可以是某种类型

      {...}

    通过is const of约束,将所定义的常量与某个类型绑定。而通过类型,编译器便可以推断出应当使用那种语法对其处理。

    然而,尽管带约束的语法构造定义可以在很大程度上消除语法冲突和歧义,但不可能消除所有的语法矛盾。另一方面,结构相似,但语义完全不同的语法构造混合在一起,即便不引发矛盾,也会对使用者造成难以预计的混乱。因此,在实际环境下,需要通过某种“语法围栏”严格限定某种用户定义语法的作用范围。最直接的形式,就是通过namespace实现。namespace在隔离和协调命名冲突中起到很好的作用,可以进一步将其运用到MP中。由于namespace一经打开,其作用范围不会超出最内层的代码块作用域:

      {

          using namespace XXX;

          ...

      } //XXX的作用范围不会超出这个范围

    运用这个特性,可以很自然地将蕴藏在一个namespace中的用户定义语法构造限制在一个确定的范围内。

    但是,仅此不够。毕竟语法不同于命名,不仅会存在冲突,还会存在(合法的)混淆,而且往往是非常危险的。为此,需要允许在using namespace的时候进一步指定语法的排他性。比如:

      {

          using namespace XXX exclusive;

          ...

      }

    如果namespace中的用户定义语法与外部语法(宿主语言,或外围引用的namespace)重叠(冲突或混淆),外部语法将被屏蔽。更进一步,可以允许不同级别的排他:排斥重叠和完全屏蔽。前者只屏蔽重叠的语法,这种级别通常用于扩展性的用户语法构造(扩展主语言,需要同主语言协同工作。而且语法重叠较少);而后者则将外部语法统统屏蔽,只保留所打开的namespace中的语法(子语言在代码块中是唯一语言),这种级别用于相对独立的功能性子语言(可以独立工作的子语言,通常会与主语言和其他子语言间存在较大的语法重叠,比如上述BNF子语言等等)。

    为提供更多的灵活性,可以在完全屏蔽的情况下,通过特定语句引入某种不会引发冲突的外部语法。比如:

      {

          using namespace XXX exclusive full;

          using host_lang::syntax(...); //引入主语言的某个语法,...代表语法名称

          ...

      }

    通常情况下,子语言不会完全独立运作,需要同宿主语言或其他子语言交互,也就是数据交换。主语言代码可能需要将数据对象传递给子语言,处理完成后再取回。由于编译器依赖于标识符的特性(主要是类型)来选择语法构造。所以,一种子语言必须使用其内部定义的类型和对象。为了能够交换数据,必须能够把主语言的对象包装成子语言的内部类型。通过在子语言的namespace中进行true typedef,可以将主语言类型定义成一个新的(真)类型,在进入子语言作用域的时候,做显式的类型转换。另外,为了方便数据转换,还可以采用两种方法:将主语言类型map到一个子语言类型(相当于给予“双重国籍”),进入子语言的语法范围时,相应的对象在类型上具有两重性,可以被自动识别成所需的类型,但必须在确保不发生语法混淆的情况下使用;另一种稳妥些的方法,可以允许执行一种typedef,介于alias和true typedef之间,它定义了一个新类型,但可以隐式地同原来的类型相互转换。数据交换的问题较复杂,很多问题尚未理清,有待进一步考察。

总结

    作为MP手段,ast宏拥有灵活性,而TMP则具备安全性,将两者各自的优点相结合,使我们可以获得更加灵活和安全的语法构造定义手段。通过在用户定义的语法构造上施加全面的约束,可以很好地规避语法冲突和歧义。

    但是,需要说明的是,这里所考察的仅仅局限在用户定义语法构造的冲突和歧义的消除上。GPL/MP要真正达到实用阶段,还需要面对更多问题。比如,由于存在用户定义的语法构造,语法分析阶段所面对的语法不是固态的,需要随时随地接受新语法,甚至重叠的语法(存在多个候选语法,不同的候选语法又会产生不同的下级语法),这就使语法分析大大复杂;语法模式匹配被推迟到语义分析阶段,此前将无法对某些语法错误作出检验;一个语法构造的语义需要通过宿主语言定义,如何衔接定义代码和周边的环境和状态;如何为用户定义的语法构造设置出错信息;由于某些语法构造的二义性,如何判别语法错误属于哪个语法构造;...。此外还有一些更本质性的问题,诸如语法构造的重载和二义性是否会更容易诱使使用者产生更多的错误等等,牵涉到错综复杂的问题,需要更多的分析和试验。

    另外,作为MP的重要组成部分,编译期计算能力也至关重要。TMP运用了C++模板特化,D语言通过更易于理解的static_if等机制,都试图获得编译期的计算能力,这些机制在完整的MP中需要进一步扩展,而并非仅仅局限在与类型相关的计算上。其他一些与此相关的特性,包括反射(编译期和运行期)、类型traits等,也应作为MP必不可少的特性。

posted @ 2008-01-25 15:09 longshanks 阅读(1185) | 评论 (4)编辑 收藏

2008年1月6日 #


GP技术的展望——道生一,一生二

by  莫华枫



    长期以来,我们始终把GP(泛型编程)作为一种辅助技术,用于简化代码结构、提高开发效率。从某种程度上来讲,这种观念是对的。因为迄今为止,GP技术还只是一种编译期技术。只能在编译期发挥作用,一旦软件完成编译,成为可执行代码,便失去了利用GP的机会。对于现在的多数应用而言,运行时的多态能力显得尤为重要。而现有的GP无法在这个层面发挥作用,以至于我这个“GP迷”也不得不灰溜溜地声称“用OOP构建系统,用GP优化代码”。

    然而,不久前,在TopLanguage group上的一次讨论,促使我们注意到runtime GP这个概念。从中,我们看到了希望——使GP runtime化的希望——使得GP有望在运行时发挥其巨大的威力,进一步为软件的设计与开发带来更高的效率和更灵活的结构。
    在这个新的系列文章中,我试图运用runtime GP实现一些简单,但典型的案例,来检测runtime GP的能力和限制,同时也可以进一步探讨和展示这种技术的特性。

运行时多态

    现在的应用侧重于交互式的运作形式,要求软件在用户输入下作出响应。为了在这种情况下,软件的整体结构的优化,大量使用组件技术,使得软件成为“可组装” 的系统。而接口-实现分离的结构形式很好地实现了这个目标。多态在此中起到了关键性的作用。其中,以OOP为代表的“动多态”(也称为 “subtyping多态”),构建起在运行时可调控的可组装系统。GP作为“静多态”,运用泛化的类型体系,大大简化这种系统的构建,消除重复劳动。另外还有一种鲜为人知的多态形式,被《C++ Template》的作者David Vandevoorde和Nicolai M. Josuttis称为runtime unbound多态。而原来的“动多态”,即OOP多态,被细化为runtime bound多态;“静多态”,也就是模板,则被称为static unbound多态。
    不过这种称谓容易引起误解,主要就是unbound这个词上。在这里unbound和bound是指在编写代码时,一个symbol是否同一个具体的类型 bound。从这点来看,由于GP代码在编写之时,面向的是泛型,不是具体的类型,那么GP是unbound的。因为现有的GP是编译期的技术,所以是 static的。OOP的动多态则必须针对一个具体的类型编写代码,所以是bound的。但因为动多态可以在运行时确定真正的类型,所以是runtime 的。至于runtime unbound,以往只出现在动态语言中,比如SmallTalk、Python、Ruby,一种形象地称谓是“duck-typing”多态。关于多态的更完整的分类和介绍可以看这里
    通过动态语言机制实现的runtime unbound,存在的性能和类型安全问题。但当我们将GP中的concept技术推广到runtime时会发现,rungime unbound可以拥有同OOP动多态相当的效率和类型安全性,但却具有更大的灵活性和更丰富的特性。关于这方面,我已经写过一篇文章 ,大致描述了一种实现runtime concept的途径(本文的附录里,我也给出了这种runtime concept实现的改进)。

Runtime Concept

    Runtime concept的实现并不会很复杂,基本上可以沿用OOP中的“虚表”技术,并且可以更加简单。真正复杂的部分是如何在语言层面表达出这种runtime GP,而不对已有的static GP和其他语言特性造成干扰。在这里,我首先建立一个基本的方案,然后通过一些案例对其进行检验,在发现问题后再做调整。
    考虑到runtime concept本身也是concept,那么沿用static concept的定义形式是不会有问题的:
      concept myconcept<T> {
          T& copy(T& lhs, T const& rhs);
          void T::fun();
          ...
      }
    具体的concept定义和使用规则,可以参考C++0x的concept提案这篇文章 ,以及这篇文章
    另一方面,我们可以通过concept_map将符合一个concept的类型绑定到该concept之上:
      concept_map myconcept<MyType> {}
    相关内容也可参考上述文件。
    有了concept之后,我们便可以用它们约束一个模板:
      template<myconcept T>void myfun(T const& val); //函数模板
      template<myconcept T>class X  //类模板
      {
           ...
      };
    到此为止,runtime concept同static concept还是同一个事物。它们真正的分离在于使用。对于static concept应用,我们使用一个具体的类型在实例化(特化)一个模板:
      X<MyType> x1;  //实例化一个类模板
      MyType obj1;
      myfun(obj1);  //编译器推导obj1对象的类型实例化函数模板
      myfun<MyType>(obj1);  //函数模板的显式实例化
    现在,我们将允许一种非常规的做法,以使runtime concept成为可能:允许使用concept实例化一个模板,或定义一个对象
      X<myconcept> x2;
      myconcept* obj2=new myconcept<MyType>;
      myfun(obj2);  //此处,编译器将会生成runtime版本的myfun
    这里的含义非常明确:对于x2,接受任何符合myconcept的类型的对象。obj2是一个“动态对象”(这里将runtime concept引入的那种不知道真实类型,但符合某个concept的对象称为“动态对象”。而类型明确已知的对象成为“静态对象”),符合myconcept要求。至于实际的类型,随便,只要符合myconcept就行。
    这种情形非常类似于传统动多态的interface。但是,它们有着根本的差异。interface是一个具体的类型,并且要求类型通过继承这种形式实现这个接口。而concept则不是一种类型,而是一种“泛型”——具备某种特征的类型的抽象(或集合),不需要在类型创建时立刻与接口绑定。与 concept的绑定(concept_map)可以发生在任何时候。于是,runtime concept实际上成为了一种非侵入的接口。相比interface这种侵入型的接口,更加灵活便捷。
    通过这样一种做法,我们便可以获得一种能够在运行时工作的GP系统。
    在此基础上,为了便于后续案例展开,进一步引入一些有用的特性:
  1. 一个concept的assosiate type被视为一个concept。一个concept的指针/引用(concept_id*/concept_id&,含义是指向一个符合concept_id的动态对象,其实际类型未知),都被视作concept。一个类模板用concept实例化后,逻辑上也是一个concept。
  2. 动态对象的创建。如果需要在栈上创建动态对象,那么可以使用语法:concept_id<type_id> obj_id; 这里concept_id是concept名,type_id是具体的类型名,obj_id是对象名称。这样,便在栈上创建了一个符合concept_id的动态对象,其实际类型是type_id
    如果需要在堆上创建动态对象,那么可以用语法:concept_id* obj_id=new concept_id<type_id>; 这实际上可以看作“concept指针/引用”。
  3. concept推导(编译期)。对于表达式concept_id obj_id=Exp,其中Exp是一个表达式,如果表达式Exp的类型是具体的类型,那么obj_id代表了一个静态对象,其类型为Exp的类型。如果表达式Exp的类型是concept,那么obj_id是一个动态对象,其类型为Exp所代表的concept。
    那么如何确定Exp是具体类型还是concept?可以使用这么一个规则:如果Exp中涉及的对象,比如函数的实参、表达式的操作数等等,只要有一个是动态对象(类型是concept),那么Exp的类型就是concept;反之,如果所有涉及的对象都是静态对象(类型为具体的类型),那么Exp的类型为相应的具体类型。同样的规则适用于concept*或concept&。
  4. concept转换。类似在类的继承结构上执行转换。refined concept可以隐式地转换成base concept,反过来必须显式地进行,并且通过concept_cast操作符执行。兄弟concept之间也必须通过concept_cast转换。
  5. 基于concept的重载,也可以在runtime时执行,实现泛化的dynamic-dispatch操作。

    下面,就开始第一个案例。

案例:升级的坦克

    假设我们做一个游戏,主题是开坦克打仗。按游戏的惯例,消灭敌人可以得到积分,积分到一定数量,便可以升级。为了简便起见,我们只考虑对主炮升级。第一级的主炮是90mm的;第二级的主炮升级到120mm。主炮分两种,一种只能发射穿甲弹,另一种只能发射高爆弹。因此,坦克也分为两种:能打穿甲弹的和能打高爆弹的。
    为了使代码容易开发和维护,我们考虑采用模块化的方式:开发一个坦克的框架,然后通过更换不同的主炮,实现不同种类的坦克和升级:
      //一些基本的concept定义
      //炮弹头concept
      concept Warheads<typename T> {
          double explode(TargetType tt); //炮弹爆炸,返回杀伤率。不同弹头,对不同类型目标杀伤率不一样。
      }
      //炮弹concept,我们关心的当然是弹头,所以用Warheads定义一个associate type
      concept Rounds<typename T> {
          Warheads WH;
          ...
      }
      //主炮concept
      concept Cannons<typename T> {
          Rounds R;
          void T::load(R& r); //装填炮弹,load之后炮弹会存放在炮膛里,不能再load,除非把炮弹打出去
          R::WH T::fire();   //开炮,返回弹头。发射后炮膛变空,可以再load
      }
      //类型和模板定义
      //坦克类模板
      template<Cannons C>
      class Tank
      {
          ...
      public:
          void load(typenam C::R& r) {
              m_cannon.load(r);
          }
          typename C::R::WH fire() {
              return m_cannon.fire();
          }
      private:
          C m_cannon;
      };
      //主炮类模板
      template<Rounds Rd>
      class Cannon
      {
      public:
          typedef Rd R;
          void load(R& r) {...}
          typename R::WH fire() {...}
      }
      template<Rounds Rd> concept_map Cannons<Cannon<Rd>>{}
      //炮弹类模板
      template<Warheads W>
      class Round
      {
      public:
          typedef W WH;
          static const int caliber=W::caliber;
          W shoot() {...}
          ...
      };
      template<Warhead W> concept_map<Round<W>>{}
      //弹头类模板,通过traits把各类弹头的不同行为弹头的代码框架分离,使类型“可组装”
      concept WH_Traits<T> {
          return T::exploed(int, TargetType, double, Material);
      }
      template<WH_Traits wht, int c>
      class Warhead
      {
      public:
          const static int caliber=c;
          double explode(TargetType tt) {
              return wht::exploed(c, tt, ...);
          }
          ...
      };
      template<WH_Traits WHT, int c> concept_map<Warhead<WHT, c>>{}
      //弹头traits
      struct KE_WHTraits
      {
          static double exploed(int caliber, TargetType tt, double weight, Material m) {...}
      };
      concept_map<KE_WHTraits>{}
      struct HE_WHTraits
      {
          static double exploed(int caliber, TargetType tt, double weight, Material m) {...}
      };
      concept_map<HE_WHTraits>{}
      //定义各类弹头
      typedef Warhead<KE_WHTraits, 90> WH_KE_90;
      typedef Warhead<KE_WHTraits, 120> WH_KE_120;
      typedef Warhead<HE_WHTraits, 90> WH_HE_90;
      typedef Warhead<HE_WHTraits, 120> WH_HE_120;
      //定义各类炮弹
      typedef Round<WH_KE_90> Round_KE_90;
      typedef Round<WH_KE_120> Round_KE_120;
      typedef Round<WH_HE_90> Round_HE_90;
      typedef Round<WH_HE_120> Round_HE_120;
      //定义各类主炮
      typedef Cannon<Round_KE_90> Cannon_KE_90;
      typedef Cannon<Round_KE_120> Cannon_KE_120;
      typedef Cannon<Round_HE_90> Cannon_HE_90;
      typedef Cannon<Round_HE_120> Cannon_HE_120;
      //定义各类坦克
      typedef Tank<Cannon_KE_90> Tank_KE_90;
      typedef Tank<Cannon_KE_120> Tank_KE_120;
      typedef Tank<Cannon_HE_90> Tank_HE_90;
      typedef Tank<Cannon_HE_120> Tank_HE_120;
    于是,当我们开始游戏时,就可以按照玩家的级别创建坦克对象,并且射击:
      //第一级玩家,驾驶发射90mm高爆炮弹的坦克
      Tank_HE_90 myTank;
      Round_HE_90 r1;
      myTank.load(r1);
      myTank.fire();
      //第二级玩家,驾驶发射120mm穿甲弹的坦克
      Tank_KE_120 yourTank;
      Round_KE_120 r2;
      yourTank.load(r2);
      yourTank.fire();
      //如果这样,危险,炮弹不匹配,小心炸膛
      myTank.load(r2); //error
    到目前为止,这些代码仅仅展示了静态的GP。concept在这里也只是起到了类型参数约束的作用。但是,在这些代码中,我们可以明显地看到,在运用GP 的参数化类型特性之后,可以很容易地进行组件化。对于一组具备类似行为和结构特征的类型,我们可以通过模板的类型参数,将差异部分抽取出来,独立成所谓的 “traits”或者“policy”。并且通过traits或policy的组合构成不同的产品。在某些复杂的情况下,traits和policy还可以进一步通过traits或policy实现组件化。
    接下来,很自然地应当展开runtime GP的运用了。
    一个游戏者是可以升级的,为了使得这种升级变得更加灵活,我们会很自然地使用Composite模式。现在,我们可以在Runtime concept的支援下实现GP版的Composite模式:
      //坦克的concept
      concept tanks<T> {
          typename Round;
          void T::load(Round&);
          Round::WH T::fire();
      }
      concept_map tanks<Tank_KE_90>{}
      concept_map tanks<Tank_HE_90>{}
      concept_map tanks<Tank_KE_120>{}
      concept_map tanks<Tank_HE_120>{}
      //坦克构造函数模板
      template<tanks T>
      T* CreateTank(WHType type, int level) { //WHType是一个枚举表明炮弹种类
          switch(level)
          {
          case 1:
              if(type==wht_KE)
                  return new tanks<Tank_KE_90>;
              else
                  return new tanks<Tank_HE_90>;
          case 2:
              if(type==wht_KE)
                  return new tanks<Tank_KE_120>;
              else
                  return new tanks<Tank_HE_120>;
          default:
              throw error("no such tank.");
          }
      }
      //玩家类
      class player
      {
      public:
          void update() {
m_pTank=CreateTank(m_tankType, ++m_level);
          }
          ...
      private:
          int m_level;
          WHType m_tankType;
tanks* m_pTank;
      };
    在类player中,使用了一个concept,而不是一个类型,来定义一个对象。根据前面提到的concept推导规则,m_pTank指向一个动态对象,还是静态对象,取决于为它赋值的表达式类型是concept还是具体类型。在update()函数中,可以看到,m_pTank通过表达式CreateTank(m_tankType, ++m_level)赋值。那么这个函数的返回类型,将决定m_pTank的类型。CreateTank()是一个模板,返回类型是模板参数,并且是符合concept tanks的类型。关键在于代码中的return new tanks<...>语句。前文已经说过,这种形式是使用<...>中的类型创建一个符合tanks的动态对象。所以,CreateTank()返回的是动态对象。那么,m_pTank也将指向一个动态对象。在运行时,当玩家达到一定条件,便可以升级。update()成员函数将根据玩家的级别重新创建相应的坦克对象,赋值到m_pTank中。
    这里,实际上是利用tanks这个concept描述,充当类型的公有接口。它所具有的特性同动多态的抽象基类是非常相似的。但是所不同的是,如同我在代码中展现的那样,concept作为接口,可以在任何时候定义,同类型绑定。而无需象抽象基类那样,必须在类型定义之前定义。于是,这种非侵入式的接口相比抽象基类拥有更加灵活自由的特性。
    然而,事情还没有完。在进一步深化坦克案例后,我们还将发现runtime GP拥有更加有趣和重要的特性。
    坦克开炮为的是攻击目标。对目标的毁伤情况直接关系到玩家的生存和得分。所以,我们必须对射击后,目标的损毁情况进行计算。于是编写了这样一组函数:
      double LethalityEvaluate(Target& t, double hitRate, WH_KE_90& wh) {...}
      double LethalityEvaluate(Target& t, double hitRate, WH_HE_90& wh) {...}
      double LethalityEvaluate(Target& t, double hitRate, WH_KE_120& wh) {...}
      double LethalityEvaluate(Target& t, double hitRate, WH_HE_120& wh) {...}
    Target是目标;hitRate是命中率,根据坦克和目标的位置、射击参数综合计算获得(如果想要更真实,可以加上风向、风力、气温、湿度、海拔等等因素);wh就是发射出来的炮弹了。函数返回杀伤率。如此,我们便可以在射击之后进行评估了:
      double l=LethalityEvaluate(house, hr, myTank.fire());
     现在,游戏需要进行一些扩展,增加一个升级,允许坦克升级到第三级。到了第三极,主炮的口径就升到头了,但可以升级功能,可以发射穿甲弹和高爆弹。这样,我们就需要一个“两用”的主炮类。但是,实际上并不需要直接做这么一个类,只需要用“两用”的弹药来实例化Cannon模板:
      concept Warheads120<T> : Warheads<T> { //120mm炮弹头concept
          double LethalityEvaluate(Target& t, double hitRate, T& wh);
      }
      concept Rounds120<T> : Rounds<T> {}
      concept_map Warheads120<WH_KE_120> {}  //120mm的穿甲弹属于Warheads120
      concept_map Warheads120<WH_HE_120> {}  //120mm的高爆弹属于Warheads120
      template<WH120 WH> concept_map Rounds120<Round<WH>> {} //所有弹头是Warheads120的炮弹都是属于Rounds120
      typedef Canon<Rounds120> Cannon120; //用Rounds120实例化Cannon模板,得到“两用”主炮
    一堆炫目的concept和concept_map之后,得到Rounds120,就是所谓的“两用”弹药。作为一个concept,它同两种类型map 在一起,实际上就成了这两个类型的接口。当我们使用Rounds120实例化Cannon<>模板时,也就创建了一个“两用的主炮”(使用 Rounds120弹药的主炮)。如果用这个Cannon120实例化Tank模板,那么就可以得到第三级坦克(装上Cannon120主炮的坦克就是第三级):
      typedef Tank<Cannon120> TankL3;
    于是,我们可以使用不同的120mm弹药装填主炮,并且发射相应的炮弹:
      TankL3 tank_l3;
      Round_KE_120 ke_round;  //创建一枚穿甲弹
      Round_HE_120 he_round;  //创建一枚高爆弹
      tank_l3.load(ke_round);  //装填穿甲弹
      tank_l3.fire();               //发射穿甲弹
      tank_l3.load(he_round);  //装填高爆弹
      tank_l3.fire();               //发射高爆弹
    现在,我们把注意力从消灭敌人,转移到TankL3::load()的参数类型和TankL3::fire()的返回类型上。在一级和二级坦克(类型 Tank_KE_90等)上,load()成员的参数类型是Round_KE_90等具体的类型;而fire()的返回类型亦是如此。但TankL3是用 Cannon120实例化的,而Cannon120是用Rounds120这个concept实例化的。根据Tank<>模板的定义, load()成员的参数类型实际上是模板参数上的一个associate type。而这个associate type实际上就是Rounds120。这意味着load()实例化后的签名是:void load(Rounds120& r)(这里暂且允许concept作为类型参数使用)。只要符合Rounds120的类型都可以作为实参传递给load()成员。同样,fire()成员的返回类型来自于Round120上的associate type,也是个concept。因此,fire()实例化后的签名是:Warheads120 fire()。
    接下来值得注意的是fire()成员。它返回类型是一个concept,那么返回的将是一个动态对象。在运行时,它可能返回WH_KE_120的实例,也可能返回WH_HE_120的实例,取决于运行时load()函数所装填的炮弹类型。当我们采用LethalityEvaluate()函数对该炮弹的杀伤情况进行评估将会出现比较微妙的情况:
      double x=LethalityEvaluate(hisTank, hr, tank_l3.fire());
    这时候,编译器应当选择哪个LethalityEvaluate()?由于tank_l3.fire()返回的是一个动态对象,具体的类型编译时不知道。实际上,在正宗的静态语言中,这样的调用根本无法通过编译。当然,编译器可以通过runtime reflect获得类型信息,然后在LethalityEvaluate()的重载中匹配正确的函数。然而,这种动态语言做法会造成性能上的问题,为静态语言所不屑。
    但是,在这里,在runtime concept的作用下,我们可以使这种调用成为静态的、合法的,并且是高效的。请注意我在concept Warhead120的定义中加入了一个associate function:double LethalityEvaluate(Target& t, double hitRate, T& wh);。runtime concept会很忠实地将concept定义中的associate function构造到一个函数指针表(我称之为ctable)中。(详细情况请看本文附录和这篇文章的附录)。因此,与tank_l3.fire()返回的动态对象实际类型对应的LethalityEvaluate()函数版本的指针正老老实实地躺在相应的ctable里。所以,我们可以直接从动态对象上获得指向ctable的指针,并且找出相应的LethalityEvaluate()函数指针,然后直接调用即可。比如:
      tank_l3.load(ke_round);
      double x=LethalityEvaluate(hisTank, hr, tank_l3.fire());
    在这些代码的背后,ke_round通过load()装填入主炮后,便摇身变成了一个动态对象。编译器会为它附加上指向ctable的指针,然后在调用 fire()的时候返回指向这个动态对象的引用。此时,编译器发现这个动态对象所对应的Warhead120 concept上已经定义了一个名为LethalityEvaluate()的associate function,并且签名与当前调用相符。于是,便可以直接找到ctable中LethalityEvaluate()对应的那个函数指针,无所顾忌的调用。由于一个concept的associate function肯定是同实际类型匹配的函数版本。比如,对于WH_HE_120而言,它的associate function LethalityEvaluate()是版本:double LethalityEvaluate(Target& t, double hitRate, WH_HE_120& wh) {...}。其他版本的LethalityEvaluate()都无法满足concept Warhead120施加在类型WH_HE_120上的约束。
    这个特性就使得runtime concept作为接口,相比动多态的抽象接口,具有更大的灵活性。抽象接口只表达了类的成员,以及类本身的行为,无法表达类型同其他类型的互动关系,或者说类型间的交互。而concept同时描述了成员函数和相关的自由函数(包括操作符),使得类型间的关系也可以通过接口直接获得,无需再通过 reflect等间接的动态手段。
    这一点在处理内置类型(如int、float)、预置类型(某些库中的类型)、第三方类型等不易或无法修改的类型有至关重要的作用。在OOP下,我们无法输出一个“整数”,或许是short、或许是long,甚至是unsinged longlong。为此,我们要么把它们转换成一个“最基础类型”(C/C++的void*,或C#的Object*),然后运用rtti信息进行类型转换,再做处理;要么使用variant这种类型包装(就像COM中的那样),然后为他们全面定义一套计算库。但runtime concept不仅仅允许输出“整数”这样一个动态对象,而且还将相关的各种操作附在动态对象之上,使之无需借助rtti或者辅助类型也可进行各类处理,就如同处理具体类型的对象那样。
    但是,在这里我仅仅考察了针对一个类型的concept(暂且称之为一元concept),还未涉及两个和两个以上类型的concept(暂且称为多元 concept,或n-元concept)。在实际开发中,多数操作都会涉及多个对象,比如两个数相加、一种类型转换成另一种。此时,我们将会面对多元的 concept。但是多元的runtime concept的特性还不清楚,还需要进一步研究分析。

总结

    本文初步展示了在引入runtime concept之后,GP的动态化特性。归纳起来有以下几点:
  1. static GP和runtime GP之间在形式上完全统一,两者可以看作同一种抽象机制的不同表现。因此,我们在构造类型、函数等代码实体的时候,并不需要考虑它们将来需要作为static使用,还是runtime使用。static和runtime的控制完全取决于这些代码实体的使用方式。这就很好地减少了软件项目早期设计,以及库设计的前瞻性方面压力。
  2. runtime concept作为非侵入式的接口,可以非常灵活地使用。我们无需在代码编写的一开始就精确地定义好接口,可以先直接编写功能类型,逐步构建软件结构。需要时再定义接口(concept),并可以在任何时候与类型绑定。接口的定制可以成为一个逐步推进的过程,早期的接口设计不足产生的不良影响相应地弱化了。
  3. runtime concept相比动多态的抽象接口更加自由。concept可以对类型的成员函数、自由函数、类型特征等等方面的特性作出描述。在runtime化之后,相关自由函数成为了接口的一部分。更进一步规约了类型在整体软件的代码环境中的行为特征。同时,也为动态对象的访问提供更多的信息和手段。
  4. concept不仅实现类型描述,还可以进一步描述类型之间的关系。这大大完善了抽象体系。特别在runtime情况下,这种更宽泛的类型描述能力可以起到两个作用:其一,进一步约束了动态对象的行为;其二,为外界操作和使用类型提供更多的信息,消除或减少了类型匹配方面的抽象惩罚。这个方面的更多特性尚不清楚,还需要更进一步地深入研究。
    综上所述,我们可以看到runtime GP在不损失性能的情况下,具备相比动多态更灵活、更丰富的手段。从根本上而言,以concept为核心的GP提供了更基础的抽象体系(关于这方面探讨,请看我的这篇文章中关于concept对类型划分的作用部分)。或者说,concept的类型描述和约束作用体现了类型抽象的本质,而在此基础上进一步衍生出static和runtime两种具体的使用方式。这也就是所谓:道生一,一生二。:)

附录

Runtime Concept实现方案二

    我在这篇文章附录里,给出了一种实现runtime concept的可能方案。这里,我进一步对这个方案做了一些改进,使其更加精简、高效。
    假设我们有一个concept:
    concept Shape<T>
    {
        void T::load(xml);
        void T::draw(device);
        void move(T&);
    }
    另外,还有一个代表圆的concept:
    concept Cycles<T> :
        CopyConstructable<T>,
        Assignable<T>,
        Swappable<T>,
        Shape<T>
    {
        T::T(double, double, double);
        double T::getX();
        double T::getY();
        double T::getR();
        void T::setX(double);
        void T::setY(double);
        void T::setR(double);
    }
    现在有类型Cycle:
    class Cycle
    {
    public:
        Cycle(double x, double y, double r);
        Cycle(Cycle const& c);
        Cycle& operator=(Cycle const& c);
        void swap(Cycle const& c);
        void load(xml init);
        void draw(device dev);
        double getX();
        double getY();
        double getR();
        void setX(double x);
        void setY(double y);
        void setR(double r);
    private:
        ...
    };
    我们将类型Cycle map到concept Cycles上:
      concept_map Cycles<Cycle>{}
    当我们创建对象时,将会得到如下图的结构:

runtime concept-2

    concept表(concept list)不再同对象放在一起,而是同一个类型的类型信息放在一起。一同放置的还有ctable。ctable中每个对应的concept项都有一个指向 concept表的指针(也可以指向类型信息头),用以找到concept list,执行concept cast。动态对象,或动态对象的引用/指针上只需附加一个指向相应的concept的指针即可。相比前一个方案,内存利用率更高。

posted @ 2008-01-06 17:17 longshanks 阅读(2699) | 评论 (7)编辑 收藏

2007年12月17日 #

被误解的C++——汉尼拔

by 莫华枫

    公元前216年8月2日,意大利东部平原,一个叫做坎尼的地方,两支大军摆开阵势,准备决一死战。一方是由保罗斯和瓦罗两位执政官率领的罗马人,另一方则是伟大的军事天才汉尼拔*巴卡率领的迦太基军队及其同盟。罗马人超过8万,而迦太基仅有4万余人。然而到了傍晚,罗马人被彻底击败,7万人被杀,仅有少数得以逃脱。这就是著名的坎尼会战。经此一役,(外加先前进行的特利比亚和特拉西梅诺湖会战),罗马人元气大伤,成年公民损失达五分之一。部分城邦背叛罗马,西西里也发生起义。罗马已经到了摇摇欲坠的地步。

    汉尼拔的这些胜利,完全得益于先前的一次异乎寻常的远征。公元前218年,汉尼拔率领军队,从新迦太基城(西班牙)出发,翻越比利牛斯山,进入南高卢地域。在他面前有两条路可走,翻越阿尔俾斯山,或者沿海岸进入意大利。但是,当时罗马人已在沿海地区部署了两支部队,准备拦截汉尼拔。而且,罗马人的海军优势,使得他们可以在任何时候将一支部队登陆在他的背后。而翻越阿尔俾斯山,则是一条及其艰险的道路,更何况是在冬天。

    汉尼拔选择了阿尔俾斯山。他甩开了罗马人,从小圣贝纳德和日内瓦山之间越过阿尔俾斯山,进入意大利境内。此时,罗马人便失去了战略纵深,一把尖刀已经深深地插入他们的腹内...

 

    C++的发展史上,也有着如同汉尼拔翻越阿尔俾斯山远征。一切还得从C with Class时代说起。

    Bjarne曾经反复强调,他创建C++为的是将Simular的抽象能力同C的性能结合起来。于是,在C语言的基础上,诞生了一种拥有类、继承、重载等等面向对象机制的语言。在这个阶段,C++提供了两个方面的抽象能力。一种是数据抽象,也就是将数据所要表达的含义通过类型以及依附于类型上的成员表述。另一种则是多态,一种最原始的多态(重载)。

    数据抽象,通过被称为“抽象数据类型(ADT)”的技术实现。ADT的一种方案,就是类。类所提供的封装性将一个数据实体的外在特征,或者说语义的表述形式,同具体的实现,比如数据存储形式,分离。这样所增加的中间层将数据的使用者同数据的实现者隔离,使得他们使用共同的约定语义工作,不再相互了解彼此的细节,从而使得两者得以解耦。

    多态则是更加基础更加重要的一种特性。多态使得我们得以用同一种符号实现某种确定的语义。多态的精髓在于:以一种形式表达一种语义。在此之前,我们往往被迫使用不同的符号来代表同一种抽象语义,为的是适应强类型系统所施加的约束。比如:

//代码#1
int add_int(int lhs, int rhs);
float add_float(float lhs, float rhs);

    很显然,这两个函数表达的语义分别是“把两个int类型值加在一起”和“把两个float类型值加在一起”。这两个语义抽象起来都表达了一个意思:加。

    我们在做算术题的时候是不会管被计算的数字是整数还是实数。同样,如果能够在编程的时候,不考虑算术操作对象的类型,只需关心谁和谁进行什么操作,那么会方便得多。当C++引入重载后,这种愿望便得以实现:

//代码#2
int add(int lhs, int rhs);
float add(float lhs, float rhs);

    重载使得我们只需关心“加”这个语义,至于什么类型和什么类型相加,则由编译器根据操作数的类型自动解析。

    从某种意义上说,重载是被长期忽视,但却极为重要的一个语言特性。在多数介绍OOP的书籍中,重载往往被作为OOP的附属品,放在一些不起眼的地方。它的多态本质也被动多态的人造光环所设遮蔽。然而,重载的重要作用却在实践中潜移默化地体现出来。重载差不多可以看作语言迈入现代抽象体系的第一步。它的实际效用甚至要超过被广为关注的OOP,而不会像OOP那样在获得抽象的同时,伴随着不小的副作用。

     随着虚函数的引入,C++开始具备了颇具争议的动多态技术。虚函数是一种依附于类(OOP的类型基础)的多态技术。其技术基础是后期绑定(late-binding)。当一个类D继承自类B时,它有两种方法覆盖(override)B上的某个函数:

//代码#3
class B
{
public:
    void fun1();
    virtual void fun2();
};

class D:public B
{
public:
    void fun1();
    void fun2();
};

    当继承类D中声明了同基类B中成员函数相同函数名、相同签名的成员函数,那么基类的成员函数将被覆盖。对于基类的非虚成员函数,继承类会直接将其遮蔽。对于类型D的使用者,fun1代表了D中所赋予的语义。而类型D的实例,可以隐式地转换成类型B的引用b,此时调用b的fun1,则执行的是类B的fun1 定义,而非类D的fun1,尽管此时b实际指向一个D的实例。

    但是,如果继承类覆盖了基类的虚函数,那么将得到相反的结果:当调用引用b的fun2,实际上却是调用了D的fun2定义。这表明,覆盖一个虚函数,将会在继承类和基类之间的所有层次上执行覆盖。这种彻底的、全方位的覆盖行为,使得我们可以在继承类上修饰或扩展基类的功能或行为。这便是OOP扩展机制的基础。而这种技术被称为动多态,意思是基类引用所表达的语义并非取决于基类本身,而是来源于它所指向的实际对象,因此它是“多态”的。因为一个引用所指向的对象可以在运行时变换,所以它是“动”的。

    随着动多态而来的一个“副产品”,却事实上成为了OOP的核心和支柱。虚函数的“动多态”特性将我们引向一个极端的情况:一个都是虚函数的类。更重要的,这个类上的虚函数都没有实现,每个虚函数都未曾指向一个实实在在的函数体。当然,这样的类是无法直接使用的。有趣的是,这种被称为“抽象基类”的类,迫使我们继承它,并“替它”实现那些没有实现的虚函数。这样,对于一个抽象基类的引用,多态地拥有了继承类的行为。而反过来,抽象基类实际上起到了强迫继承类实现某些特定功能的作用。因此,抽象基类扮演了接口的角色。接口具有两重作用:一、约束继承类(实现者)迫使其实现预定的成员函数(功能和行为);二、描述了继承类必定拥有的成员函数(功能和行为)。这两种作用促使接口成为了OOP设计体系的支柱。

    C++在这方面的进步,使其成为一个真正意义上具备现代抽象能力的语言。然而,这种进步并非“翻越阿尔俾斯山”。充其量也只能算作“翻越比利牛斯山”。对于C++而言,真正艰苦的远征才刚开始,那令人生畏的“阿尔俾斯山”仍在遥远的前方。

    同汉尼拔一样,当C++一脚迈入“现代抽象语言俱乐部”后,便面临两种选择。或者在原有基础上修修补补,成为一种OOP语言;或者继续前进,翻越那座险峻的山峰。C++的汉尼拔——Bjarne Stroustrup——选择了后者。

    从D&E的描述中我们可以看到,在C++的原始设计中就已经考虑“类型参数”的问题。但直到90年代初,才真正意义上地实现了模板。然而,模板只是第一步。诸如Ada等语言中都有类似的机制(泛型,generic),但并未对当时的编程技术产生根本性的影响。

    关键性的成果来源于Alex Stepanov的贡献。Stepanov在后来被称为stl的算法-容器库上所做的努力,使得一种新兴的编程技术——泛型编程(Generic Programming,GP)——进入了人们的视野。stl的产生对C++的模板机制产生了极其重要的影响,促使了模板特化的诞生。模板特化表面上是模板的辅助特性,但是实际上它却是比“类型参数”更加本质的机能。

    假设我们有一组函数执行比较两个对象大小的操作:

//代码#4
int compare(int lhs, int rhs);
int compare(float lhs, float rhs);
int compare(string lhs, string rhs);

    重载使得我们可以仅用compare一个函数名执行不同类型的比较操作。但是这些函数具有一样的实现代码。模板的引入,使得我们可以消除这种重复代码:

//代码#5
template<typename T> int compare(T lhs, T rhs) {
    if(lhs==rhs)
        return 0;
    if(lhs>rhs)
        return 1;
    if(lhs<rhs)
        return -1;
}

    这样一个模板可以应用于任何类型,不但用一个符号表达了一个语义,而且用一个实现代替了诸多重复代码。这便是GP的基本作用。

    接下来的变化,可以算作真正意义上的“登山”了。

    如果有两个指针,分别指向两个相同类型的对象。此时如果我们采用上述compare函数模板,那么将无法得到所需的结果。因为此时比较的是两个指针的值,而不是所指向的对象本身。为了应付这种特殊情况,我们需要对compare做“特别处理”:

//代码#6
template<typename T> int compare(T* lhs, T* rhs) {
    if(*lhs==*rhs)
        return 0;
    if(*lhs>*rhs)
        return 1;
    if(*lhs<*rhs)
        return -1;
}

    这个“特殊版本”的compare,对于任何类型的指针作出响应。如果调用时的实参是一个指针,那么这个“指针版”的compare将会得到优先匹配。如果我们将compare改成下面的实现,那么就会出现非常有趣的行为:

//代码#7
template<typename T>
struct comp_impl
{
    int operator()(T lhs, T rhs) {
        if(lhs==rhs)
            return 0;
        if(lhs>rhs)
            return 1;
        if(lhs<rhs)
            return -1;
    }
};
template<typename T>
struct comp_impl<T*>
{
    int operator()(T* lhs, T* rhs) {
        comp_impl<T>()(*lhs, *rhs);
    }
};
template<typename T> int compare(T* lhs, T* rhs) {
    comp_impl<T>()(*lhs, *rhs);
}

    当我们将指针的指针作为实参,调用compare时,神奇的事情发生了:

//代码#8
double **x, **y;
compare(x, y);

    compare居然成功地剥离了两个指针,并且正确地比较了两个对象的值。这个戏法充分利用了类模板的局部特化和特化解析规则。根据规则,越是特化的模板,越是优先匹配。T*版的comp_impl比T版的更加“特化”,会得到优先匹配。那么当一个指针的指针实例化comp_impl,则会匹配T*版的 comp_impl,因为指针的指针,也是指针。T*版通过局部特化机制,剥离掉一级指针,然后用所得的类型实例化comp_impl。指针的指针剥离掉一级指针,那么还是一个指针,又会匹配T*版。T*版又会剥离掉一级指针,剩下的就是真正可以比较的类型——double。此时,double已无法与 T*版本匹配,只能匹配基础模板,执行真正的比较操作。

    这种奇妙的手法是蕴含在模板特化中一些更加本质的机制的结果。这种意外获得的“模板衍生产品”可以算作一种编译时计算的能力,后来被一些“好事者”发展成独立的“模板元编程”(Template Meta Programming,TMP)。

    尽管TMP新奇而又奥妙,但终究只是一种辅助技术,用来弥补C++的一些缺陷、做一些扩展,“捡个漏”什么的。不过它为我们带来了两点重要的启示:一、我们有可能通过语言本身的一些机制,进行元编程;二、元编程在一定程度上可以同通用语言一起使用。这些启示对编程语言的发展有很好的指导意义。

    模板及特化规则是C++ GP的核心所在。这些语言特性的强大能力并非凭空而来。实际上有一只“幕后大手”在冥冥之中操纵着一切。

    假设有一个类型系统,包含n个类型:t1,...,tn,那么这些类型构成了一个集合T={t1,...,tn}。在当我们运用重载技术时,实际上构造了一组类型的tuple到函数实现的映射:<ti1,ti2,ti3,...> ->fj()。编译器在重载解析的时候,就是按照这组映射寻找匹配的函数版本。当我们编写了形如代码#5的模板,那么就相当于构建了映射:<T, T,...> ->f0()。

    而代码#6,以及代码#7中的T*版模板,实际上是构造了一个<Tp>->fp()的映射。这里Tp是T的一个子集:Tp={t'|t'=ti*, ti∈T}。换句话说,特化使泛型体系细化了。利用模板特化技术,我们已经能够(笨拙地)分辨浮点数、整数、内置类型、内置数组、类、枚举等等类型。具备为类型划分的能力,也就是构造不同的类型子集的能力。

    现在,我们便可以构造一个“泛型体系”:G={T} U T U Tp U Ta U Ti U Tf U Tc ...。其中,Tp是所有指针类型,Ta是数组,Ti是整数,Tf是浮点数,Tc是类等等。但是如果我们按照泛化程度,把G中的元素排列开:{T, Tp, Ta, Ti,...,t1,...,tn}。我们会发现这中间存在一些“断层”。这些断层位于T和Tp等之间,以及Tp等与ti等之间等等。这表明在C++98/03中,抽象体系不够完整,存在缺陷。

    所以,到目前为止,C++还没有真正翻越阿尔俾斯山里那座最险峻的山峰。这正是C++0x正在努力做的,而且胜利在望。

    在C++0x中,大牛们引入了first-class的concept支持。concept目前还没有正式的法定描述(以及合理的中文翻译)。通俗地讲,concept描述了一个类型的(接口)特征。说具体的,一个concept描述了类型必须具备的公共成员函数,必须具备的施加在该类型上的自由函数(和操作符),以及必须具备的其他特征(通过间接手段)。下面是一个典型的concept:

concept has_equal<T>
{
    bool T::equal(T const& v);
};

    这个concept告诉我们它所描述的类型必须有一个equal成员,以另一个同类型的对象为参数。当我们将这个concept施加在一个函数模板上,并作为对类型参数的约束,那么就表明了这个模板对类型参数的要求:

template<has_equal T>bool is_equal(T& lhs, T const& rhs) {
    return lhs.equal(rhs);
}

    如果实参对象的类型没有equal成员,那么is_equal将会拒绝编译通过:这不是我要的!

    concept是可以组合的,正式的术语叫做“refine”。我们可以通过refine进一步构造出约束更强的concept:

concept my_concept<T> : has_equal<T>, DefaultConstructable<T>, Swappable<T> {}

    refine获得的concept将会“继承”那些“基concept”的所有约束。作为更细致的组合手段,concept还可以通过!操作符“去掉”某些内涵的concept约束:

concept my_concept1<T> : has_equal<T>, !DefaultConstructable<T> {}

    这个concept要求类型具备equal成员,但不能有默认构造函数。

    通过这些手段,concept可以“无限细分”类型集合T。理论上,我们可以制造一连串只相差一个函数或者只相差一个参数的concept。

    一个concept实际上就是构成类型集合T的划分的约束:Tx={ti| Cx(ti)==true, ti∈T}。其中Cx就是concept所构造的约束。不同的concept有着不同范围的约束。这样,理论上我们可以运用concept枚举出类型集合 T的所有子集。而这些子集则正好填补了上述G中的那些断层。换句话说,concept细化了类型划分的粒度,或者说泛型的粒度。使得“离散”的泛型系统变成“连续”的。

    当我们运用concept约束一个函数模板的类型参数时,相当于用concept所描述的类型子集构建一个映射:<Tx1,Tx2,...>->fx()。凡是符合tuple <Tx1,Tx2,...>的类型组合,对应fx()。所以,从这个角度而言,函数模板的特化(包括concept)可以看作函数重载的一种扩展。在concept的促进下,我们便可以把函数模板特化和函数重载统一在一个体系下处理,使用共同的规则解析。

    在目前阶段,C++差不多已经登上了“抽象阿尔俾斯山”的顶峰。但是就如同汉尼拔进入意大利后,还需要面对强盛的罗马共和国,与之作战那样。C++的面前还需要进一步将优势化作胜利。要做的事还很多,其中最重要的,当属构建Runtime GP。目前C++的GP是编译时机制。对于运行时决断的任务,还需要求助于OOP的动多态。但是C++领域的大牛们已经着手在Runtime GP和Runtime Concept等方面展开努力。这方面的最新成果可以看这里这里这里。相信经过若干年的努力后,GP将会完全的成熟,成为真正主流的编程技术。

 

    坎尼会战之后,汉尼拔已经拥有了绝对的优势。罗马人已经战败,他同罗马城之间已经没有任何强大的敌对力量,罗马人也已经闻风丧胆,几无斗志。但是,汉尼拔却犯下了或许令他一生后悔的错误。他放过了罗马城,转而攻击罗马的南部城邦和同盟。他低估了罗马人的意志,以及罗马同盟的牢固程度。罗马人很快结束了最初的混乱,任命了新的执政官,采用了坚壁清野、以柔克刚的新战略。随着时间的推移,汉尼拔和他的军队限于孤立无援的境地,被迫为了生存而作战。尽管迫降并占领了几个罗马城市,但是终究无法再次获得给予罗马人致命一击的机会。

    汉尼拔的战略错误实际上在从新迦太基城出发之前已经注定。因为汉尼拔对罗马人的远征的根本目的并非击溃并占领罗马,而是通过打击罗马,削弱他们的势力,瓦解他们的联盟。以达到寻求签订和平协议的目的。然而这种有限战略却使导致了他的最终失败。

 

    不幸的是,C++或多或少地有着同汉尼拔一样的战略错误。C++最初的目的基本上仅仅局限于“更好的C”。并且全面兼容C。这在当时似乎很合理,因为C可以算作最成功的“底层高级语言”,拥有很高的性能和灵活性。但是,C的设计并未考虑将来会有一个叫做“C++”的语言来对其进行扩展。结果很多优点对于C而言是优点,但却成了C++的负担。比如,C大量使用操作符表达语法结构,对于C而言显得非常简洁,但对于C++,则使其被迫大规模复用操作符,为其后出现的很多语法缺陷埋下了伏笔。这一点上,Ada做得相对成熟些。它从Pascal那里继承了主要语法,但不考虑兼容。这使得Ada更加完整,易于发展。新语言就是新语言,过分的兼容是镣铐,不是优势。而且,合理地继承语法,同样可以吸引众多开发者。从经验来看,程序员对于语法变化的承受能力还是很强的。他们更多地关心语言的功能和易用性。

    另一方面,C++最初并未把目标定在“创建一种高度抽象,又确保性能的语言”。纵观C++的发展,各种抽象机制并非在完整的规划或路线图的指导下加入语言。所有高级特性都是以“添油战术”零打碎敲地加入语言。从某种程度上来看,C++更像是一种实验性语言,而非工业语言。C++的强大功能和优点是长期积累获得的,而它的诸多缺陷也是长期添加特性的结果。

    汉尼拔和C++给予我们一个很好的教训。对于一个试图在1、20年后依然健康成长的语言,那么就必须在最初便拥有明确的目标和技术发展规划。对于以往的语言特性应当择优而取,不能照单全收。并且在技术上拥有足够的前瞻性。我们知道,技术前瞻性是很难做到的,毕竟技术发展太快。如果做不到,那就得有足够的魄力对过去的东西加以取舍。所谓“舍小就大,弃子争先”。

    总体而言,C++在抽象机制的发展方面,还算是成功的。尽管伴随着不少技术缺陷,但是C++的抽象能力在各种语言中可称得上出类拔萃。而且C++还在发展,它未来将会发展成什么形态,不得而知。但是,无论C++是继续修修补补,还是根本性地变革,它的抽象能力都会不折不扣地保留,并且不断完善和增强。

 

    坎尼会战之后,汉尼拔又打过几次小规模的胜仗。但经过长期的作战,也得不到迦太基的支援,汉尼拔的力量越来越弱,只能在意大利半岛上勉强生存。罗马很快恢复了元气,改革了军事体系和作战方式,重新掌握了战略主动权。更重要的是,罗马也有了自己的“汉尼拔”——(征服非洲的)普布利乌斯·科尔内利乌斯·西庇阿(大西庇阿)。西庇阿被派往北非大陆,直接攻击迦太基人的老巢。汉尼拔被召回,在扎马与西庇阿摆开阵势,展开一场决战。最终,西庇阿运用从汉尼拔那里学到的战术击溃了迦太基人,为罗马人赢得了第二次布匿战争的胜利。

    此后,汉尼拔在罗马人的通缉之下,流亡于地中海沿岸,试图寻求东山再起的机会。但最终未能如愿,被迫于公元前183年自尽,享年64岁。有趣的是,他的老对手,小他12岁的西庇阿也于同年去世。一个伟大的传奇就此结束。

posted @ 2007-12-17 11:28 longshanks 阅读(2044) | 评论 (11)编辑 收藏

2007年12月6日 #

    本文来源于TopLanguage Group 上的一次讨论(这里这里这里 )。pongba提出:C++的抽象机制并不完善,原因是为了性能而做的折中,未来随着计算能力的提高到一定程度,人们就能够忽略更好的抽象所带来的负面效应。就此诸老大各自提出高见,受益良多啊。经过讨论,我基本上理解了pongba的想法。但我觉得等待计算机的性能提高太消极了。我相信随着编程技术的发展,这种最优抽象造成的性能损失将会越来越小。这种途径将会更快地让人们接受最优抽象形式。

     在“C++ Template”一书中,将多态总结为三种主要类型:runtime bound、static unbound和runtime unbound。其中runtime bound就是我们通常所说的动多态,OOP的核心支柱(广义上OOP还包括Object Base(OB,仅指类型封装等OO的基本特性),但有时也会将OB和OOP分开,OOP单指以OO为基础的动多态。这里使用狭义的OOP含义); static unbound就是静多态,通过模板实现。而runtime unbound则是一种不常见的形式。早年的SmallTalk具有这种形式,现在的ruby也引入这种机制。
     在主流的(静态)语言中,我们会面临两种类型的多态需求:对于编译期可以确定类型的,使用静多态,比如实例化一个容器;对于运行期方能确定类型的,则使用 动多态。而runtime unbound也可以用于运行期类型决断。于是,便有了两种运行期多态。这两种多态的特性和他们的差异,是本文的核心。实际上,相比动多态, runtime unbound多态为我们提供了更本质的运行时多态手段,我们可以从中获得更大的收益。但是鉴于一些技术上的困难,runtime unbound多态无法进入主流世界。不过,由于新的编程技术的出现,使得这种更好的运行时多态形式可以同动多态一比高下。

动多态   

    废话少说,让我们从一个老掉牙的案例开始吧:编写一个绘图程序,图形包括矩形、椭圆、三角形、多边形等等。图形从脚本(比如xml)中读出,创建后保存在一个容器中备查。通过遍历容器执行图形绘制。
    就这么个题目,很简单,也很熟悉,解释OOP的动多态最常用的案例。下面我们就从动多态实现开始。
    首先定义一个抽象基类,也就是接口:

    class IShape

    {

        virtual void load(xml init)=0;

        virtual void draw(monitor m)=0;

        ...

    };

    然后定义各种图形类,并从这个接口上继承:

    class Rectangle: public IShape

    {

        void load(xml init) {...}

        void draw(monitor m) {...}

        ...

    };

    class Ellipse: public IShape

    {

        void load(xml init) {...}

        void draw(monitor m) {...}

        ...

    };

    ...

 

    void DrawShapes(monitor m, vector<IShape*> const& g)

    {

        vector<IShape*>::const_iterator b(g.begin()), e(g.end());

        for(; b!=e; ++b)

        {

            (*b)->draw(m);

        }

    }

    ...

    现在可以使用这些图形类了:

    vector<IShape*> vg;

    vg.push_back(new Rectangle);

    vg.push_back(new Ellipse);

    ...

    DrawShapes(crt, vg);

    通过接口IShape,我们可以把不同的图形类统一到一种类型下。但是,通过虚函数的override,由图形类实现IShape上的虚函数。这可以算老 生常谈了。动多态的核心就是利用override和late bound的组合,使得一个基类可以在类型归一化的情况下,拥有继承类的语义。OOP设计模式大量运用这种技术,实现很多需要灵活扩展的系统。

Runtime Unbound

    Runtime Unbound多态混合了静多态和动多态的特征,即既有类型泛化,又是运行时决断的。一个最典型的例子就是ruby的函数:
    class x
       def fun(car)
            car.aboard
        end
    end
    这个案例非常明确地展示出了Runtime Unbound多态的特点。car参数没有类型,这里也不需要关心类型,只要求car对象有一个aboard方法即可。由于ruby是动态语言,能够运行时检测对象的特征,并动态调用对象上的方法。
    在Runtime Unbound的思想指导下,我们利用一种伪造的“动态C++”,把上面的绘图例子重新编写:

    class Rectangle

    {

        void load(xml init) {...}

        void draw(monitor dev) {...}

        ...

    };

    class Ellipse

    {

        void load(xml init) {...}

        void draw(monitor dev) {...}

        ...

    };

    ...

    void DrawShapes(monitor dev, vector<anything> const& g)

    {

        vector<IShape>::const_iterator b(g.begin()), e(g.end());

        for(; b!=e; ++b)

        {

            (*b).draw(dev);

        }

    }

    ...

    vector<anything> vg;

    vg.push_back(Rectangle(...));

    vg.push_back(Ellipse(...));

    ...

    DrawShapes(crt, vg);

    图形类不再从抽象接口IShape继承,而用关键字anything实例化vector<>模板。这个虚构的anything关键字所起的作 用就是使得vector能够接受不同类型的对象。当DrawShapes()函数接收到存放图形对象的容器后,遍历每一个对象,并且调用对象上的draw ()函数,而不管其类型。
    从这段代码中,我们可以看出Runtime Unbound多态带来的好处。所有图形类不再需要归一化成一个类型(抽象接口)。每个类只需按照约定,实现load、draw等成员函数即可。也就是 说,这些图形类解耦合了。一旦类型解耦,便赋予我们很大的自由度。最典型的情况就是,我们需要使用一个其他人开发的图形类,并且无法修改其实现。此时,如 果使用动多态,就很麻烦。因为尽管这些图形类都拥有load、draw等函数,但毕竟不是继承自IShape,无法直接插入容器。必须编写一个继承自 IShape的适配器,作为外来图形类的包装,转发对其的访问。表面上,我们只是减少一个接口的定义,但Runtime Unbound多态带来的解耦有着非凡的意义。因为类耦合始终是OOP设计中的一个令人头痛的问题。在后面,我们还将看到建立在Runtime Unbound多态基础上的更大的进步。
    然而,尽管Runtime Unbound多态具有这些优点,但因为建立在动态语言之上,其自身存在的一些缺陷使得这项技术无法广泛使用,并进入主流。
    Runtime Unbound多态面临的第一个问题就是类型安全。确切的讲是静态类型安全。
    本质上,Runtime Unbound多态(动态语言)并非没有类型安全。当动态语言试图访问一个未知类型对象的成员时,会通过一些特殊机制或特殊接口获得类型信息,并在其中寻 找所需的对象成员。如果没有找到,便会抛出异常。但是,传统上,我们希望语言能够在编译期得到类型安全保证,而不要在运行时才发现问题。也就是说, Runtime Unbound多态只能提供运行时类型安全,而无法得到静态类型安全。
    第二个问题是性能。Runtime Unbound需要在运行时搜寻类型的接口,并执行调用。执行这类寻找和调用的方法有两种:反射和动态链接。
    反射机制可以向程序提供类型的信息。通过这些信息,Runtime Unbound可以了解是否存在所需的接口函数。反射通常也提供了接口函数调用的服务,允许将参数打包,并通过函数名调用。这种机制性能很差,基本上无法用于稍许密集些的操作。
    动态链接则是在访问对象前在对象的成员函数表上查询并获得相应函数的地址,填充到调用方的调用表中,调用方通过调用表执行间接调用。这种机制相对快一些,但由于需要查询成员函数表,复杂度基本上都在O(n)左右,无法与动多态的O(1)调用相比。
    这些问题的解决,依赖于一种新兴的技术,即concept。concept不仅很消除了类型安全的问题,更主要的是它大幅缩小了两种Runtime多态的性能差距,有望使Runtime Unbound成为主流的技术。

concept

    随着C++0x逐渐浮出水面,concept作为此次标准更新的核心部分,已经在C++社群中引起关注。随着时间的推移,concept的潜在作用也在不断被发掘出来。
    concept主要用来描述一个类型的接口和特征。通俗地讲,concept描述了一组具备了共同接口的类型。在引入concept后,C++可以对模板参数进行约束:
    concept assignable<T> {
        T& operator=(T const&);
    }
    template<assignable T> void copy(T& a, T const& b) {
        a=b;
    }
    这表示类型T必须有operator=的重载。如果一个类型X没有对operator=进行重载,那么当调用copy时,便会引发编译错误。这使得类型参数可以在函数使用之前便能得到检验,而无需等到对象被使用时。
    另一方面,concept参与到特化中后,使得操作分派更加方便:
    concept assignable<T> {
        T& operator=(T const&);
    }
    concept copyable<T> {
        T& T::copy(T const&);
    }
    template<assignable T> void copy(T& a, T const& b) {    //#1
        a=b;
    }
    template<copyable T> void copy(T& a, T const& b) {    //#2
        a.copy(b);
    }
    X x1,x2; //X支持operator=操作符
    Y y1,y2; //Y拥有copy成员函数
    copy(x1, x2);    //使用#1
    copy(y1, y2);    //使用#2
    在静多态中,concept很好地提供了类型约束。既然同样是Unbound,那么concept是否同样可以被用于Runtime Unbound?应当说可以,但不是现有的concept。在Runtime Unbound多态中,需要运行时的concept。
    依旧使用绘图案例做一个演示。假设这里使用的"C++"已经支持concept,并且也支持了运行时的concept:

    class Rectangle

    {

        void load(xml init) {...}

        void draw(monitor dev) {...}

        ...

    };

    class Ellipse

    {

        void load(xml init) {...}

        void draw(monitor dev) {...}

        ...

    };

    ...

    concept Shape<T> {

        void T::load(xml init);

        void T::draw(monitor dev);

    }

    ...

    void DrawShapes(monitor dev, vector<Shape> const& g)

    {

        vector<IShape>::const_iterator b(g.begin()), e(g.end());

        for(; b!=e; ++b)

        {

            (*b).draw(dev);

        }

    }

    ...

    vector<Shape> vg;

    vg.push_back(Rectangle(...));

    vg.push_back(Ellipse(...));

    vg.push_back(string("xxx"));    //错误,不符合Shape concept

    ...

    DrawShapes(crt, vg);

    乍看起来没什么特别的,但是请注意vector<Shape>。这里使用一个concept,而不是一个具体的类型,实例化一个模板。这里的意思是说,这个容器接受的是所有符合Shape concept的对象,类型不同也没关系。当push进vg的对象不符合Shape,便会发生编译错误。

     但是,最关键的东西不在这里。注意到DrawShapes函数了吗?由于vector<Shape>中的元素类型可能完全不同。语句 (*b).draw(dev);的语义在静态语言中是非法的,因为我们根本无法在编译时具体确定(*b)的类型,从而链接正确的draw成员。而在这里, 由于我们引入了Runtime Unbound,对于对象的访问链接发生在运行时。因此,我们便可以把不同类型的对象存放在一个容器中。

    concept在这里起到了类型检验的作用,不符合相应concept的对象是无法放入这个容器的,从而在此后对对象的使用的时候,也不会发生类型失配的 问题。这也就在动态的机制下确保了类型安全。动多态确保类型安全依靠静态类型。也就是所有类型都从一个抽象接口上继承,从而将类型归一化,以获得建立在静 态类型系统之上的类型安全。而concept的类型安全保证来源于对类型特征的描述,是一种非侵入的接口约束,灵活性大大高于类型归一化的动多态。

    如果我们引入这样一个规则:如果用类型创建实例(对象),那么所创建的对象是静态链接的,也就是编译时链接;而用concept创建一个对象,那么所创建的对象是动态链接的,也就是运行时链接。

    在这条规则的作用下,下面这段简单的代码将会产生非常奇妙的效果:

    class nShape

    {

    public:

        nShape(Shape g, int n) : m_graph(g), m_n(n) {}

        void setShape(Shape g) {

            m_graph=g;

        }

    private:

        Shape    m_graph;

        int        m_n;

    };

    在规则的作用下,m_graph是一个动态对象,它的类型只有在运行时才能明确。但是无论什么类型,必须满足Shape concept。而m_n的类型是确定的,所以是一个静态对象

    这和传统的模板有区别吗?模板也可以用不同的类型参数定义成员数据。请看如下代码:

    Rectangle r;

    Ellipse e;
     nShape(r, 10);

     nShape.setShape(e);   //对于传统模板而言,这个操作是非法的,因为e和r不是同一种类型

    动态对象的特点在于,我们可以在对象创建后,用一个不同类型的动态对象代替原来的,只需要这些对象符合相应的concept。这在静态的模板上是做不到的。

    现在回过头来看一下用concept实例化模板的情形。我们知道,用一个类型实例化一个模板,得到的是一个类,或者说类型。而用一个concept实例化 一个模板,得到的又是什么呢?还是一个concept。那么vector<Shape>是一个concept,因而它的实例是动态的对象。当 然,实际上没有必要把vector<Shape>的实例整个地当成动态对象,它只是具有动态对象的行为特征。在实现上,vector< Shape>可以按照普通模板展开,而其内部由concept模板实参定义的对象作为动态对象处理即可。一个由concept实例化的模板的对象作为语义上的动态对象
    下面的代码则引出了另一个重要的特性:
    vector<float> vFloat;    //静态对象的容器,内部存放的都是静态对象,属于同一类型float
    vector<Shape> vShape; //动态对象的容器,内部存放动态对象,都符合Shape
    同一个类模板,当使用类型实例化,执行static unbound多态使用concept实例化,执行runtime unbound多态。两者的形式相同。也就是说static多态同runtime多态以相同的形式表达。 由于concept的加入,两种完全不同的多态被统一在同一个模型和形式下。实际上,static和runtime unbound多态可以看作同一个抽象体系的两个分支,分别处理不同情况的应用。而形式上的统一,则更加接近抽象体系的本质。同时,也使得两种 unbound多态的差异被后台化,使用者无需额外的工作,便可以同时获得动态和静态的抽象能力。同时,两种多态所展示的逻辑上的对称性,也暗示了两者在 本质上的联系。这里统一的形式,便是这种对称性的结果。
    对于模板函数,则会表现出更加有趣的特性(这个函数模板有些特别,不需要template关键字和类型参数列表,这是我伪造的。但由于concept的使用,它本质上还是一个模板):
    void draw(Shape g);
    这个函数接受一个符合Shape的参数。如果我们用一个静态对象调用这个函数:
    Rectangle r;
    draw(r);
    那么,就执行static unbound,实例化成一个完完整整的函数,同传统的函数模板一样。
    如果用一个动态对象调用这个函数:
    Shape g=Cycle();
    draw(g);
    g=Rectangle();
    draw(g);
    那么,就执行runtime unbound,生成一个等待运行时链接的函数。上面的两次调用,分别进行了两次运行时链接,以匹配不同的动态对象。
    这样,我们可以通过函数调用时的参数对象,来控制使用不同的多态形式。更复杂的情况就是用一个函数的返回值调用另一个函数,这样构成的调用链依然符合上述的调用控制原则。
    下面,我们将看到Runtime Unbound多态的一个精彩表演:
    //假设,我们已经定义了Rectangle、Cycle、Square、Ellipse、Trangle五个类,
    // 分别map到Rectangles、Cycles、Squares、Ellipses、Trangles五个concept上,
    // 这些concept都refine(可以不正确地理解为继承吧)自Shape。
    void draw(monitor dev, Rectangles r); //#3
    void draw(monitor dev, Cycles c);       //#4
    void draw(monitor dev, Squares s);    //#5
    void draw(monitor dev, Ellipses e);    //#6
    void draw(monitor dev, Trangles t);    //#7
    //此处定义一个Shape的动态对象
    Shape g=CreateShapeByUserInput();    //这个函数根据用户输入创建图形对象,所以图形对象的类型只能到运行时从能确定。
    draw(crt, g);
    好了,现在该调用哪个版本的draw?根据用户的输入来。换句话说,调用哪个版本的draw,取决于CreateShapeByUserInput()函数的返回结果,也就是用户输入的结果。如果CreateShapeByUserInput() 返回Rectangle的动态对象,那么执行#3;如果返回的是Trangle对象,那么执行#7。这是一种动态分派的操作。在运行时concept的作 用下,实现起来非常容易。对draw的调用最终会被转换成一个concept需求表,来自draw函数,每一项对应一个函数版本,并且指明了所对应的 concept。动态对象上也有一个concept表,每一项存放了这个对象所符合的concept。用这两个表相互匹配,可以找到g对象的 concept最匹配的那个draw版本,然后调用。
    这实际上是将重载决断放到运行时进行,而concept在其中起到了匹配参数的作用。
    这样的做法同利用rtti信息执行类型分派调用类似:
    void draw_impl(monitor dev, Rectangle& r);
    void draw_impl(monitor dev, Cycle& c);
    void draw_impl(monitor dev, Square& s);
    void draw_impl(monitor dev, Ellipse& e);
    void draw_impl(monitor dev, Trangle& t);
    void draw_impl(monitor dev, Shape& g) {
        if(typeif(g)==typeid(Rectangle))
            draw_impl(dev, (Rectangle&)g);
        else if(typeif(g)==typeid(Cycle))
            draw_impl(dev, (Cycle&)g);
        ...
    }
    但是,他们却有着天壤之别。首先,rtti分派是侵入的。如果需要增加一个图形,需要在draw函数中增加分派代码。而Runtime Unbound方案则只需要用新的concept重载draw函数即可。
    其次,rtti版本有多少图形类,就需要多少if...else...,而Runtime Unbound则是一对多的。如果有几个图形类内容不同,但有相同的接口,符合同一个concept,那么只需针对concept编写一个函数版本即可。 比如,如果有一个特别的CycleEx类,使用外界正方形的左上角/右下角坐标描述,正好符合Ellipses concept,那么只需将CycleEx map到Ellipses上即可,无需多加任何代码。
    最后,rtti需要获取类型信息,然后做线性比较,性能无法优化。但Runtime Unbound通过concept表的相互匹配,仅牵涉数值操作,有很大的优化空间。
    那么这样一种运行时分派有什么好处呢?我们看到图形类上的draw函数接受一个monitor类型参数,它代表设备。如果哪一天需要向另一种设备,比如 printer,输出图形,那么就需要在图形类上增加另一个版本的draw函数。如果类是别人开发的,那么就增加沟通的负担。如果类是外来的,我们无法修 改,那么只能通过adapter之类的笨拙手段处理。为了让monitor之类同图形本身没有关联的东西分离,应当使用自由函数执行draw操作。但普通 函数只能接受确定的类型重载,而传统的函数模板则限于编译期使用,无法进行运行时分派。所以,如果能够使用concept重载函数,并且赋予 Runtime Unbound机能,那么便可以用最简单的形式针对一类类型进行处理,效能高得多。

运行时concept

   语言层面的concept无法做到这些,因为它是编译期机制。为此,我们需要有一种运行时的concept,或者说二进制级别的concept。

    一个concept包含了与一个或若干个类型有关的一组函数,包括成员函数和自由函数。于是,我们就可以用一个类似“虚表”的函数指针表(暂且称为 ctable吧)存放concept指定的函数指针。这样的ctable依附在动态对象上,就像vtable一样。每个对象都会匹配和map到若干个 concept。因此,每个动态对象会有一个concept表,其中存放着指向各ctable的指针,以及相应的concept基本信息。

    当一个“用户”(函数或模板)需要在运行时链接到对象上的时候,它会提交一个concept的代码(全局唯一)。系统用这个代码在动态对象的 concept表上检索,获得指向所需concept的指针,并且填写到“用户”给出的一个“插入点”(一个指针)中。随后“用户”便可以直接通过这个 “插入点”间接调用所需的函数,成员或自由函数。

    在这里,concept的巧妙之处在于,将一族函数集合在一起,作为一个整体(即接口)。那么,在执行运行时匹配的时候,不再是一个函数一个函数地查询, 可以一次性地获知这些函数是否存在。这就很容易地规避了类型安全保证操作的损耗。如果使用hash查询,那么可以在O(1)实现concept匹配。另 外,一个concept的hash值可以在编译时计算好,运行时链接只需执行hash表检索,连hash值计算也可以省去。

    一个动态对象可以直接用指向concept ctable的指针表示。在不同concept之间转换,相当于改变指针的指向,这种操作非常类似OOP中的dynamic_cast。

    对于如下的动态对象定义:

    Shape g=Cycle();

    会创建一个Cycle对象,在对象上构建起一个concept表,表中对应Cycle所有符合的concept。并且建立一组ctable,每个 ctable对应一个concept。每个concept表项指向相应的ctable。而符号g则实际上是指向所建立对象的Shapes ctable的指针。

    对于函数:

    void draw(Shape g);

    draw(g);

    调用g时,由于draw的参数是Shape concept,而g正是draw所需的concept,所以无需在对象g的concept表上匹配,可以直接使用这个ctable指针。这就是说,只要 所用动态对象(g)的concept同使用方(draw函数)能够匹配,便可以直接使用指向ctable的指针链接(编译时链接),无需在运行时重新匹 配。只有发生concept转换时,才需要在concept表中搜索,获得所需的ctable指针:

    Swappable s=g; //Swappable是另一个concept

    这种情况同dynamic_cast极其相似。也可以模仿着采用concept_cast之类的操作符,使得concept转换显式化,消除隐式转换的问题(强concept化)。

    所以,Runtime Unbound在运行时concept的作用下,具有同动多态相同的底层行为。因而,他们的性能也是一样的。很多用于动多态的方案和算法都可以直接用于运行时concept。

Runtime Unbound和Runtime Bound

    对于runtime unbound同runtime bound之间的差异前面已经有所展示。在其他方面,两者还存在更多的差别。
    首先,就像绘图案例中展示的那样,runtime unbound是非侵入的。runtime unbound不要求类型继承自同一类型,只需将类型同concept关联起来便可。
    其次,concept不是一种局限于OO的技术,不仅涉及成员函数,还包括了自由函数,范围更广,更加灵活。
    最后,实现上,Runtime Unbound和Runtime Bound之间有惊人的相似之处。两者都采用一个函数指针表作为操作分派;都采用一个指向函数表的指针作为入口;一个动态对象上的concept之间的转 换,也同动多态对象一样,在不同的函数表间切换。他们唯一的不同,是实现接口的机制。
    动多态用类型兼任接口,通过继承和虚函数实现接口的功能。用类型作为类型的接口,使得这两个本来独立的概念交织在一起。增加整个类型体系的复杂度和耦合度。    concept则利用独立的系统描述、表达和管理接口。类型则回归到表达业务对象的功能上来。
    动多态在使用类型表达接口的时候,便很容易地引入一个麻烦的问题,表达功能的类型和表达接口的类型混合在一起,使用时必须通过一些方法区分出哪些是接口, 哪些是功能类型。这增加了对象模型的复杂性。而concept则独立于类型体系之外,所有对接口的操作都是单一的,检索和匹配来得更加方便快捷。
    作为继承体系的基础部分,动多态的抽象接口必须在继承结构的最顶端。那么这些抽象类型必须先于其他类型出现。这对系统的早期设计产生很大的压力,往往一个基础抽象接口设计有误,便会造成整个体系的变更。
    而concept是独立于类型的,那么任何时候都可以将一个类型同接口绑定。接口甚至可以在类型体系基本建立之后才确定。这种灵活性对复杂软件的开发至关重要,去掉了长期以来套在人们头上的枷锁。
    前面已经提到,在不需要concept转换的情况下,无需执行运行时的concept匹配,所有的调用具有同动多态一样的效率(都是间接调用)。在执行 concept转换时,无需象动多态那样在复杂的继承体系上检索,只需执行concept表的hash匹配,效率反而更高,而且更简单。考虑到这些情况, 我们可以认为concept化的Runtime Unbound多态完全能够替代传统的动多态。也就是说,我们不再需要动多态了
     想象一下,如果一门语言能够拥有运行时concept,那么它完全可以只保留Static Unbound和Runtime Unbound多态,而放弃Runtime Bound多态。一旦放弃动多态(没有了虚函数和虚表),那么对象模型便可以大大简化。所有对象只需要线性分布,基类和成员依次堆叠在一起,也没有 vtable的干扰,对象结构可以做到最简单。同时,继承也回归了代码重用的传统用途。而且,对象独立于接口存储,在能够在编译时静态链接的时候,可以作 为静态对象使用。而在需要动态对象的地方,又可以很容易地转换成动态对象,只需要为其附上concept表和ctable。一切都简化了。对象模型也更加 容易统一。
    这对于很多底层开发的程序员对于c++复杂而又混乱的对象模型难以接受。如果能够废除虚函数,简化对象模型,那么对于这些底层开发而言,将会带来直接的好 处。只要确保不使用concpt定义对象、实例化模板,便可以使整个软件执行Static Unbound。这相当于去掉OOP的C++。否则,就启用Runtime Unbound,实现运行时多态。

总结

    Static Unbound和Runtime Unbound作为一对亲密无间的多态技术,体现了最完善的抽象形式。两者各踞一方,相互补充,相互支援。而且两者具有统一的表现形式,大大方便了使用, 对于软件工程具有非凡的意义。另一方面,Runtime Bound多态作为OO时代的产物,体现了静态类型语言在运行时多态方面的最大努力。但是,随着运行时concept的引入,Runtime Unbound多态自身存在的静态类型安全问题和性能问题,都能够得到很好的解决。至此,Runtime Unbound便具备了替代Runtime Bound的实力。相信在不久的将来,Runtime Bound将会逐渐步入它的黄昏。

参考

  1. http://groups.google.com/group/pongba/web/Runtime+Polymorphic+Generic +Programming.pdf。大牛人Jaakko Järvi等写的关于Runtime concept的文章,讲解了runtime concept的概念的实现方法,并在ConceptC++上以库的形式实现。其中使用传统的动多态实现runtime concept,这表明动多态的实现机制同runtime concept是一致的。当然库的实现很复杂,这是“螺蛳壳里做道场”,无奈之举。Runtime concept还是应当在语言中first-class地实现。
  2. http://www.lubomir.org/academic/MinimizingCodeBloat.pdf。也是Jaakko Järvi写的,运行时分派的文章。
  3. http://opensource.adobe.com/wiki/index.php/Runtime_Concepts。
  4. Inside C++ Object Model。

附录 Runtime Concept的具体实现

    我们有一个concept:
    concept Shape<T>
    {
        void T::load(xml);
        void T::draw(device);
        void move(T&);
    }
    另外,还有一个代表圆的concept:
    concept Cycles<T> :
        CopyConstructable<T>,
        Assignable<T>,
        Swappable<T>,
        Shape<T>
    {
        T::T(double, double, double);
        double T::getX();
        double T::getY();
        double T::getR();
        void T::setX(double);
        void T::setY(double);
        void T::setR(double);
    }
    现在有类型Cycle:
    class Cycle
    {
    public:
        Cycle(double x, double y, double r);
        Cycle(Cycle const& c);
        Cycle& operator=(Cycle const& c);
        void swap(Cycle const& c);
        void load(xml init);
        void draw(device dev);
        double getX();
        double getY();
        double getR();
        void setX(double x);
        void setY(double y);
        void setR(double r);
    private:
        ...
    };
    当定义一个动态对象:
    Shape g=Cycle();
    便会形成如下图的结构:

    g实际上是一个指针,指向concept表的Shape项,而Shape项指向Shape对应的ctable。由于Cycle refine自Shape等众多concept,那么Cycle的ctable实际上包含了这些concept的ctable,所以只需一个Cycle的 ctable,而其他concept都分别指向其中各自相应的部分。ctable中的每一个项则指向具体的函数体。
    如果遇到语句:
    Swappable h=concept_cast<Swappable>(g);
    那么,将会执行一个搜索,用concept Swappable的id(比如hash码)在concept表中检索是否存在Swappable项。如果存在,就将对应项的指针赋给h。这种操作同 dynamic_cast操作非常相似,只是相比在复杂的对象结构中查询更加简单迅速。
    concept表置于对象的头部或尾部,这是为了便于对象检索concept接口。每个类型的ctable只需一份。
    对象本体可以很容易地同concept表分离,在完全静态的情况下,concept表是不需要的。如果需要runtime多态,加上concept表即可。

posted @ 2007-12-06 17:20 longshanks 阅读(3690) | 评论 (12)编辑 收藏