日历

September 2009
M T W T F S S
« Aug   Oct »
 123456
78910111213
14151617181920
21222324252627
282930  

冒号课堂§3.1:泛型范式

冒号课堂

第三课 常用范式(1)

课前导读

这一课介绍了四个常用的编程范式:泛型式、元编程、切面式和事件驱动式。与上节课类似,这些介绍也都是入门性的,目的是让读者认识到范式的多样性与差异性。

本课共分四节——

1.泛型范式——抽象你的算法

2.超级范式——提升语言的级别

3.切面范式——多角度看问题

4.事件驱动——有事我叫你,没事别烦我

3.1 泛型范式——抽象你的算法

郑晖

摘要

泛型式编程简谈


以类行杂,以一行万

《荀子•王制篇》

!预览

  • 算法串联数据,如脊贯肉;数据实化算法,如肉附脊

  • 泛型编程是算法导向的,即以算法为起点和中心点,逐渐将其所涉及的概念内涵模糊化、外延扩大化,将其所涉及的运算抽象化、一般化,从而扩展算法的适用范围

  • 思想是鸡,结论是蛋

?提问

  • 泛型编程有哪些优点?

  • STL有哪些要素?各自有什么作用?

  • 泛型编程的泛化对象是什么?

  • 泛型编程的核心思想是什么?

:讲解

冒号重新开讲:“你们会不会经常遇到这样的情景:一遍又一遍地写着相似的代码,有心将其归并,却因种种原因无法践行。”

逗号心有戚戚焉道:“是啊,有时明明两个函数的实现几乎是一模一样的,就因为某些参数不匹配,无法合而为一。”

“有一种编程范式可以解决这个问题,它打破了不同数据类型之间的壁垒,让你的代码不再臃肿,这——就是泛型编程。”冒号的语调和说辞不免令人联想到电视上的减肥广告,“Generic Programming,简称GP,其基本思想是:将算法与其作用的数据结构分离,并将后者尽可能泛化,最大限度地实现算法重用。这种泛化是基于模板(template)的参数多态(parametric polymorphism),相比OOP基于继承(inheritance)的子类型多态(subtyping polymorphism),不仅普适性更强,而且效率也更高。这不能不说是一种异数——我们知道,普适性往往是以效率为代价的。如果一定要找出代价的话,那就是其用法稍微复杂一些,可读性稍微差一些。GP最著名的代表是C++中的STL(Standard Template Library),其后亦为Java、C#、D等语言所吸纳[1]。此外,一些函数式语言如Ocaml、Standard ML、Haskell等也支持GP。”

冒号写下两段代码——

C++(泛型编程):

    template <typename T>
    T max(T a, T b)       // 求出两个数中的较大者
    {
            return  (a > b) ? a : b;
    }

C(宏定义):

    #define max(a,b) ((a) > (b) ? (a) : (b))
    

“求两个数中的较大值是经常遇到的问题。”冒号解说着,“对于静态类型语言[2]来说,若参数类型不同,即使函数体相同也不能合为一体。如果语言不支持重载(overload),还可能出现maxInt、maxLong、maxFloat、 maxDouble之类的函数名,冗赘而丑陋。尽管在C中可用宏定义(macro definition)来实现,但无法保证类型安全,而C++模板则兼顾类型安全和代码重用,并且由于是在编译期间展开的,效率上也不损失。不止于此,C++支持运算符重载,除数值类型外,一切定义了‘>’ 运算的数据类型均可调用max函数,真是一举N得,N趋向无穷大啊!”

冒号边说边比划,夸张的语气和手势逗得大家都笑了。

引号提出疑问:“Java的一切对象都是Object类型,只要将所有参数都换成Object类型,岂不也是一种泛化?”

冒号答道:“首先,基本类型如int、float等不是Object的子类,虽然Java 新增了自动装拆箱(autoboxing/unboxing)的功能,但要付出性能的代价。更重要的是,这将不可避免地需要类型的显式转换(explicit conversion或cast),无法在编译期间施行严格的类型检查,由此丧失了静态类型语言的优势,为bug大开方便之门。这也是Java最终引入泛型的原因,虽然有些姗姗来迟。类似地,C/C++中的通用指针void *也有类型安全问题。”

句号发表他的看法:“泛型虽好,似乎只是某些局部才用到的技术,不具有前面几种范式的渗透性。”

冒号听罢不语,返身在黑板上写下几道题——

  1. 从一个整数数组中随机抽取十个数,对其中的素数求和

  2. 将一个无序整数集中所有的完全平方数换成其平方根

  3. 从学生成绩表中,列出门门都及格且平均分在70分以上的学生名单

  4. 在一个着色二元树中,将所有的红色结点涂成蓝色

  5. 将一个字符串从倒数第三个字符开始反向拷贝到另一个字符串中

  6. 每从标准输入读取一个非数字的字符X,于标准输出打印“X不是数字字符”

句号暗忖,这有何难?不过是些常规题罢了。不料冒号的问题却出人意表:“请问它们之间有何共同之处?能否共享同一段代码?”

见众人缄默已久,冒号接着投影出一段代码——

template <class Iterator, class Act, class Test>
void process(Iterator begin, Iterator end, Act act, Test test)
// 对容器中在给定范围内(即起于begin止于end)所有满足给定条件的元
//素(即test(元素)==true)进行处理(即act(元素))
{
    for ( ; begin != end; ++begin)    // 从头至尾遍历容器内元素
        if (test(*begin)) act(*begin); // 若当前元素满足条件,则对其采取行动
}

“STL有三要素:算法(algorithm)、容器(container)和迭代器(iterator)。算法是一系列切实有效的步骤;容器是数据的集合,可理解为抽象的数组;迭代器是算法与容器之间的接口,可理解为抽象的指针或者游标。”冒号讲述道,“算法串联数据,如脊贯肉;数据实化算法,如肉附脊。只有抽象出表面的数据,算法的脊梁才能显现。以上几题看似风马牛不相及,若运用泛型思维,便可发现它们的共性:对指定集合中满足指定条件的元素进行指定处理。用模板语言,寥寥数行即勾勒完毕。”

问号诧异道:“相比前面的max模板,这儿连元素的数据类型T都不见了?”

冒号回答:“元素被容器封装了。”

问号追问:“可连容器也看不到啊?”

冒号料有此问:“容器通过它的迭代器参与算法。”

句号豁然开朗:“通过模板,泛化了容器——可以是数组、列表、集合、映射、队列、栈、字符串等等;泛化了元素——可以是任何数据类型;泛化了处理方法和限定条件——可以是任何函数。”

冒号提醒道:“补上两点:这里的处理方法和限定条件不限于函数,还可以是函子(functor)[3]——自带状态的函数对象;另外迭代器也被泛化了——可以从前往后移动,可以从后往前移动,可以来回移动,可以随机移动,可以按任意预先定义的规律移动。”

叹号由衷感叹:“果然强悍无比啊!”

逗号倒也心细:“最后一题中标准输入也算容器吗?”

“为什么不呢?只要一个对象配备了迭代器,它就可以作为容器来对待。I/O流上就有现成的迭代器,当然你也可以自行定制。索性我们来看看这道题的解法吧。”冒号给出了第六题的实现代码——

#include <iostream>
#include “process.h” // 前述process所在的头文件

using namespace std;

// 判断字符是否为非数字字符
bool notDigit(char c)
{
    return (c < '0') || (c > '9');
}

// 打印非数字字符
void printNondigit(char c)
{
    cout << c << "不是数字字符" << endl;
}

int main()
{
    process(istream_iterator<char>(cin), istream_iterator<char>(),
            printNondigit, notDigit);

    return 0;
}

逗号打量了半天:“这里完全看不到I/O读取的过程,也看不到通常的迭代循环,简洁得难以置信。”

冒号补充道:“不光是代码简洁,它还让人摆脱了底层编码的细节,在更高更抽象的层次上进行编程设计。”

引号发觉:“开始谈起泛型编程时,您特别强调它对数据类型的抽象。现在看起来,它也能对函数进行抽象呢。”

“说得没错,条件是被抽象的函数或者方法具有相同的签名(signature)或接口(interface)。不过别忘了,在C和C++中的函数——准确地说是函数指针——也能作为数据类型。但不管怎样,这都表明泛型编程不仅能泛化概念,还能泛化行为。”冒号目光转向句号,“现在还有人认为泛型编程的渗透性不够强吗?”

句号腆然一笑。

“这些只是泛型编程的冰山一角。重要的是,我们不是在玩弄花哨的技巧,而是在用一种新的视角去审视问题。”冒号总结道,“泛型编程是算法导向的(Algorithm-Oriented),即以算法为起点和中心点,逐渐将其所涉及的概念(如数据结构、类)内涵模糊化、外延扩大化,将其所涉及的运算(函数、方法、接口)抽象化、一般化,从而扩展算法的适用范围。这非常类似数学思维——当数学家证明完一个定理后,总会试图在保持核心思想的前提下,尽可能地放宽题设,增强结论,从而推广定理。外行人常以为数学定理最重要,其实数学思想才是数学的精髓。比如举世皆知的哥德巴赫猜想和费尔马大定理,人们在攻克它们的过程中产生的新思想、新理论、新方法,已远远超过了定理本身的意义。数学家们甚至不愿这些猜想被过早地解决,怕扼杀了会下金蛋的鸡。在他们眼里,思想是鸡,结论是蛋。这也无怪乎STL会出自一位学数学的人之手了[4]。”

“我怎么觉得更像是出自一位菜场大妈之口呢?” 逗号打趣道,“不信你们听嘛,算法好比脊骨、数据好比猪肉、思想好比母鸡、结论好比鸡蛋。我没说错吧?”。

众人哑然失笑。

,插语

  1. 但它们的实现机制却大不相同:C++和D采用类型模板(template),Java采用类型擦除(type erasure),C#采用类型具化(reification),相应的表现也有显著差异。

  2. 静态类型语言在编译期间或运行之前施行类型检查(type checking)。后有详论。

  3. 又称function object,在C++中指重载了函数调用算符(operator())的类,在Java和C#中可通过interface来实现。

  4. STL的发明者Alexander Stepanov曾是莫斯科大学数学系的学生(1967-1972)。

。总结

  • 泛型编程能打破静态类型语言的数据类型之间的壁垒,在不牺牲效率并确保类型安全的情况下,最大限度地提高算法的普适性。

  • STL有三要素:算法、容器和和迭代器。算法是一系列可行的步骤;容器是数据的集合,是抽象化的数组;迭代器是算法与容器之间的接口,是抽象化的指针。算法串联数据,数据实化算法。

  • 泛型编程不仅能泛化算法中涉及的概念(数据类型),还能泛化行为(函数、方法、运算)。

  • 泛型编程是算法导向的,以算法为中心,逐渐将其所涉及的概念内涵模糊化、外延扩大化,将其所涉及的运算抽象化、一般化,从而提高算法的可重用性。

“”参考

  1. Bjarne Stroustrup.The C++ Programming Language, Special ed..Reading, MA:Addison-Wesley,2000.507-516,549-560

相关文章

Share
 请您评分1星(很差)2星(不行)3星(一般)4星(不错)5星(很棒)

5 comments to 冒号课堂§3.1:泛型范式

  • leon

    Really inspiratinal about Generic Programming.

  • Todd

    >> STL有三要素:算法、容器和和迭代器。

    一句话点出了STL的精髓,太好了!有点儿奇怪的是相比STL,在C#中很少用到迭代器,难得是因为有foreach的原因?

    • 无论是C#还是Java,foreach语法只是在遍历时把迭代器隐藏了,这是一种更高层次的抽象机制。然而在需要对容器构造特殊的遍历方式时,迭代器还是不能少的,与是否采用foreach无关。

      • Todd

        个人比较了一下STL和C#的泛型类库:
        STL中算法,容器,迭代器同为一等公民,reverse(s.begin(), s.end())这样的写法是很好的体现;而相比之下,C#算法不够泛,多是作为容器类的成员方法提供,基本上算法是二等公民,而迭代器由于有foreach语法结构也被淡化了。

        可以认为,STL的设计是3个要素并重,而C#是以容器为核心。

        • 从某种角度说,这正是不同编程范式带来的差别:C++允许自由函数的存在,不局限于OO范式,故泛型算法更加普适,不必附着于某个容器类。比如,C++里头文件<algorithm>中均是自由函数(包括你提到的std:reverse)。但在C#和Java中就无法办到这一点,除非采用静态类。

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

This blog is kept spam free by WP-SpamFree.