菜单一般都呈树型结构（即所谓的一级、二级、三级菜单等），而将菜单项表示为树的结点，如：

 

public class MenuItem

{

}

 

MenuItem中的ID、Parent、Visited表示了树结点的特征。

 

而菜单的操作又大都会涉及到对菜单树的遍历，所以，很自然地会想到，如果将树的操作抽象出来，代码会更加简化。

 

为了提高树的代码的重用性，或者说，为了使树更加一般化，我们用泛型来表示，如：

 

public class Tree<T>

{

}

 

我们希望能用类型参数T表示树的结点类型，这样，就可以使得我们定义的Tree适用于一般化的情况。

 

但这样编译通不过，因为编译器无法确知T含有Parent成员，所以t.Parent为非法结构。如何解决这个问题呢？

 

解决的办法就是要让编译器知道T含有Parent成员，直接的办法是利用C#泛型的约束，如：

 

public class Tree<T> where T : MenuItem

{

}

 

但这样一来，Tree就绑定于MenuItem结构了，而这并不是我们所希望的。

 

C#泛型的约束（constraints）是一个非常优美的设计，合理使用约束，可以写出简洁、高效、类型安全的代码。但对于我们的例子，如何让一般化的Tree不依赖于特定的MenuItem呢？

 

在我们对Tree的定义中，T是树的结点类型，菜单树只是树的一种，我们希望在Tree中表达一般的树，而不仅仅是菜单树。仔细考察上面的定义，我们发现MenuItem的定义中，表示树的本质的是三个成员：ID, Parent, Visited，只要有一种办法能够让编译器知道T包含这三个成员就行了。由此我们自然想到了接口（interface），一般的约束都表示为接口，如果接口能够表示这三个成员，则问题即可迎刃而解。

 

C#的接口不仅可以是method interface，还可以是property interface，如此，我们可以将上述三个成员表示为ITree接口，如：

 

public interface ITree

{

}

 

而将Tree<T>表示为：

 

public class Tree<T> where T : ITree

{

}

 

而此时的MenuItem可以表示为：

 

public class MenuItem : ITree

{

}

 

这样一来，我们就可以写如下代码：

 

List<MenuItem> mList = MenuManager.GetMenuList();

Tree<MenuItem> tree = new Tree<MenuItem>(mList);

if (tree.HasChild(mid)) { }

 

Thanks for C#'s Generics to write these elegant codes!

 

今天才看到——大三元没了！

 

已经N年没去过南京了。去年大年初一，冒着严寒，搭乘火车，风尘仆仆赶往南京，为的是到大三元，再次品尝那时时萦回在心中的萨其玛。然而，在新街口地铁一出来，却找不到原来的“南京”了！

 

中山路已经不认识了，原来的建筑已经全部拆除，取而代之的是一幢幢的摩天大楼，南京要急着“现代化”了……

 

妻说，南京建成这样，大三元肯定没有了。但就是不死心，在中山路上狂奔，希望上天能够眷顾一下这份虔诚……

 

今天，看到“南京拆迁、改制，老字号正在消失”这篇短文，心彻底凉了！

 

没有了大三元的南京，还是南京么？如果一座城市，没有了那份让人牵挂的生活温馨，就只是一座石头森林而已！

具有实践精神的理论家；我们时代的达芬奇

                                                       ------高德纳访谈录

文/丁力  译/赵斯思  审校/高昂

 

《程序员》杂志的一位作者袁泳先生，曾经说过高德纳是一位文艺复兴时期式的天才人物，这说的是他的博学，以及他同时具备的灵巧的编程能力。在分工越来越细致的现代社会，这确实非常罕见，就像一个人自己制造一架飞机，他既要考虑空气动力学问题，也要考虑飞机上的每棵螺丝钉的固定方式。也确实使我们想到达芬奇，后者创造了享誉后世的《蒙娜丽莎》，《计算机编程艺术》在计算机领域的影响可以与之媲美，同时也是机器设计方面的专家。从计算机科学史上说，高德纳正是生逢其时。1936年，图灵发表了《论可计算数及其在判定问题上的应用》一文，确立了可计算模型。1953年，巴克斯发明了Fortran语言。从1960年代起，高德纳以他的博识与耐心开始了《计算机编程艺术》的写作，该书旨在对计算机科学理论的数学背景与历史，做一梳理和总结。现在大学计算机系的《数据结构》课程的内容基本来自该书。有人更是把它与牛顿的《自然哲学和数学原理》并列，选为对世界历史发生影响的十大科学著作，这不无理由。高德纳本人在36岁时，获得了计算机科学的最高荣誉---图灵奖。从1993年起，他主要专心致力于完成七卷本的《计算机编程艺术》一书。几个星期以前，我们采访了他。使我们特感幸运与欣悦的是，高德纳先生对我们的采访表现出极大的热诚，在繁忙工作中抽出宝贵时间，细致地回答了我们的问题，并在通信中特别强调希望用他的中文名字。从这里，不难看出他对中国和中国文化的热爱。这在采访的本文中也有所体现。当我们谈到最早的算法时，他特别提到《九章算术》，这本即使中国人也很少读过的书。或者我们可以将此看作一种激励，正如高德纳在采访中所说，计算机科学的思想来自世界各个地域、各种文明。可以期待，今天的中国也会产生如刘徽、秦九韶那样的数学高手，对计算机科学与技术做出独特的贡献。

 

以下是采访的本文：

 

本刊记者：什么是最早的算法？

 

高德纳：我想，第一个“真正的”算法可以追溯到大约4000年前，它们以楔型文字记载在粘土板上。我在文章“史前巴比伦算法”中对此有过讨论（我将其翻译为现代注记方式），这篇文章也重印为我的书《计算机科学论文精选》的第十一章。

 

当然，这些早期的算法并不是很精巧。它们解释了如何以计算的方式解决这些问题，但后来发现使用代数方法能更好地解决它们。最早的“有意义的”算法,它对于今天的程序员们仍然很重要,是最大公约数的求解。其中一个算法被称为欧几里德算法，它被记载于欧几里德几何原本上,尽管它来自于欧多克索斯和其它一些更早期的人物。这种算法基于辗转相除法。另一个算法仅需要除以二，因此非常适合当前的二进制计算机。这个算法可能发源于2000年前的中国——这要取决于我们如何理解经典的《九章算术》中一些句子的隐藏的含义（我在我的书《半数值算法》的340到341页和中文版的309页讨论了这个问题）。

 

本刊记者：奥运会今年夏天在中国举行，这是对于中国来说是一件很重要的事情，因为它有一些特殊的含义，也许是一个符号，表示中国人能像接受希腊火炬一样接受西方文化。希腊先哲毕达哥拉斯说过“我喜欢作为奥运会的观众胜过成为一个运动员或商人”。现在很多中国人也成为了奥运会观众，我来问个问题：为什么希腊人发现的数学对于人类文明（包括计算机科学）如此重要？

高德纳：希腊数学家发明的最伟大的东西是严格证明的概念。这个概念将数学与其它知识区别开来，其它知识往往是基于事实的累计、由老师传授给学生的并由社会共识所评估（举个例子，物理中，并不知道一个假设的真假，而只能等着所谓专家们的想法越来越趋于统一。但是在数学中，很多事情都是无可辩驳的，或者说不存在不同的观点），纵观人类历史，那些没有遵从希腊方式理解数学的文明把数学认为是应该记忆的规则而不是可以由逻辑推演而来的事实。在这些文明（例如古代中国、日本、印度和哥伦布发现之前的美洲等）中，人们发现了很多重要的数学原理但是也犯了很多错误，因为学生否决老师是不明智的！这也是为什么我如此感激史前的希腊数学家教会其他人如何真正的证明问题。

 

另一方面，我希望澄清一点，我相信所有文明之间都是相互学习的。我为计算机科学这个全世界成千上万的人的共同成果而庆祝，每个人都为此贡献了他们从经验中而来的重要观点。

本刊记者：如何看待数学和计算机科学之间的关系，特别是数学和算法学习之间的关系？

 

高德纳：你可以参照我对第二个问题的回答，我认为数学对于程序员最重要的意义在于它告诉我们如何证明我们的程序将会在所有情况下正常工作。若非如此，我们就得为此担心，尽管我们的程序通过了已有的所有测试，但或许明天它在处理另外一些新数据时就会出错。

 

当然，仅仅知道程序能正常工作这一点并不够。有了数学，我们可以证明一个程序比另一个程序快成千上万倍。某些时候，我们甚至能证明程序是“最好的”（best possible）——根据某些标准，没有其它程序会比它好。

本刊记者：这个问题是关于您的书《计算机编程艺术（The Art of Computer Programming）》，写这本书的主要目的是什么呢？您是否试图构建一个算法体系？您是如何选择主题呢？

 

高德纳：我写《计算机编程艺术》的主要目地是组织和理解一些广泛被各种程序使用的最基础的想法。只要可能，我使用数学给出对于每种基础的方法的对于精 确效率的计量的理解。此外，我尽量叙述每一种方法的历史，因为理解这些方法是如何被发现的有助于我们在现时和今后发明新的方法。

 

但是，书的主题是1962年选定的，这时计算机科学还没发展到一个作者无法掌握的规模。因此，没有像操作系统、并行处理、分布式处理之类的资料。此外，我更多地使用整数而不是浮点数。我把高级数学主题，例如数值分析、计算几何留给别人讨论。我关注的是程序员与机器间的低层次接口，为支持高级应用程序而用于构建库和工具的基础的子程序。然而，尽管将主题列表做了如此多限制，我这个关于计算科学的一小部分仍旧是一个如此巨大的主题，我需要为剩下的内容工作20年！所以，我希望一直保持健康。

 

本刊记者：我的很多朋友都尝试过阅读《计算机编程艺术》，但是他们发现这非常困难。我听说一个小说家——詹姆斯乔伊斯（James Joyce），《尤利西斯》（Ulysses）的作者——有人为他的小说写了本书，名字叫《乔伊斯小说指导》，我不知道有没有针对《计算机编程艺术》的类似书籍，比如 《计算机编程导论阅读指导》。您能给《计算机编程艺术》的读者一些建议吗？

 

高德纳：《计算机编程艺术》不是为所有人写的。大约每50个人中就有一个能发展出独特的看问题的方式，这使他们成为真正的程序员。像你我这样的人，倾向于将知识用特殊的形式在脑中组织以便于更好地利用电脑。每50人中的另外49人不该从事编程这一行，尽管他们可以使用计算机完成一些不需要编程的任务。

 

对程序员来说，拥有非程序员的朋友是非常重要的，所以对于你所说的你有朋友阅读《计算机编程艺术》非常困难，我并不觉得奇怪。当然，你的朋友也许不应该阅读你看过的所有书籍，你也不应期待能轻易看懂他们的书籍！最好的方法是团队合作，用天分和技巧作为补充。

本刊记者：您认为对最近一些年来说，计算机科学最需要解决的问题是什么？

 

高德纳：我在所有地方都看到很大的发展的潜能。所以，从这些同样精彩的候选者中我无法选择。机器人、加密、制图（mapping）、动态规划、大量文本或大量DNA序列的搜索等等，都亟待提高。

 

总的来说，我认为我期待的主要进步来自于程序员和非程序员的合作。比如，人类能更好地理解动作。我相信很多针对医生、化学家、物理学家、生物学家等的将数据以动画形式表现出来的工具应该被开发出来。要实现它们，需要优秀的程序员实现动画，与能够理解人类视觉能力的优秀的图形设计师一起工作，与知道哪些数据需要被理解的优秀的医生、化学家、物理学家和生物学家一起工作。

 

本刊记者：我听说狄克斯特拉（Edsger W. Dijkstra）曾经试图解决这样的问题：什么是正确的程序？所谓的形式证明？现在在软件工业中，我们主要依靠测试而编写正确的程序。有没有可能在理论上找到一种方法让我们知道程序是否正确，尤其是对大规模的程序？

 

高德纳：在我回答第二个问题的时候，我提到使用数学去证明（不是重复地测试直到你找不到错误）的重要性。狄克斯特拉和其他人都发展了验证正确性方法，这些方法可以放大,以验证“大”程序。但是，如你指出的，软件工业界并没有真正遵从他们的建议。部分的问题在于——“大”的含义一直在变：当我们有一个可以工作的大程序，人们常常就想写一个更大的，这也就更加难以验证。验证技术从没有跟上人们对于代码体积越来越大的胃口。

 

我将会试着同时从理论和实践上解释我的态度。拿我的程序TeX做例子，它按照今天的标准来说并不“大”，它只有500页的代码。我并没有完成对于TeX完全的形式化的正确性证明，尽管我非常喜欢数学证明。但是，我已经非常熟悉验证的基础，我知道如何非形式化地使用它们——大体上我知道如何证明正确性，如果我有时间去研究每一个琐碎的细节（grind through the gory details）。

 

没有这些基础知识，我的程序可能会经常崩溃，像你我知道的一些商业软件一样。有了这些知识，我就能写出非常稳定和好用程序，但也仅是在我测试了它之后！

 

让我从另一个不同角度再说一遍：没有理论，我不知道程序可被证明的正确是什么意思，我挣扎前进（flounder）。但是尽管有了理论，我也不能确定我的程序是好的，除非我进行了广泛的测试！

 

为什么？因为在现实中，没有程序能被真正被证明是正确的：假定的“证明”可能包含错误。如果某人给我看一个经过形式化证明的程序，我不得不检查一下验证过程有没有错误。验证过程也许由机器完成，但是机器逻辑也许是错误的，如此这般。这是一个永无终点的循环。

 

数学展示给我们理想，我们可以检查证明，直到我们认为它们是合理的。但是只有不会犯错的超人能真正得出证明是正确的结论。

 

进一步来说，证明程序是否满足它的规格说明（specification）的想法也是值得怀疑的，因为规格说明本身可能是不正确的。实际上TeX并没有精确的规格说明，如果有，我也认为它完全没有用处！（不是每个人同意我这个观点，但他们应该设计并实现一个完美排版软件，在我已完成了TeX这个排版软件的时候。）

 

总之，我认为将“形式证明”和“测试”分裂开来是危险的。最好的做法是正确地同时使用两种方法。我在我的著作《Literal Programming》的第十章和第十一章详细地讨论了TeX的调试（在《Digital Typography》的第三十四章中讨论了后续开发）。

 

本刊记者：我们的杂志名字叫《程序员》，所以我的最后一个问题是：什么是程序员，您如何看待程序员？

 

高德纳：程序员选取一个抽象的算法，并将其转化为以某种定义良好的语言写成的程序中的具体形式，程序才可以被机器执行。

 

“算法”之于“程序”就类似于“信息”之于“数据”：信息是理想化的抽象的概念，它或多或少可以由某种精确的方法将其编码为数据，以完美地表达。一个算法是一种理想化的可计算的为某些任务服务的过程，它或多或少可以由某种精确的方法将其编码为程序，以完美地表达。但是程序员事实上不仅仅是写程序的人。真正的任务是编写可以被人们阅读的程序，而不仅仅是编写可以被机器分析的程序，因为人们会需要验证它（非形式化的）、修改它和维护它。这就是为什么我坚信“作文式程序设计（literate  programming）”——像文学创作那样写程序，写出自己的风格，为他人所欣赏。

 

注：

 

1、文章转自CSDN。

 

2、高德纳，可能我们更熟悉他的原名：Donald Knuth，《The Art of Computer Programming》的作者，斯坦福大学教授。

 

3、如果这篇文章同时附有原文就更好了。

今天一大早，看到live.com又变了，不是变坏了，而是越变越好了。

 

首先，顶部的广告条不见了，这一方面增大了有效版面，另外，也提高了下载的速度。

 

还有一些细节上的变化，如Profile的图片，增加了一个漂亮的“相框”。

 

但这些仍然不足以让人“额手称庆”，让人真正惊喜的是SkyDrive终于对China开放了！

 

通俗地讲，SkyDrive就是一个大容量的“网络硬盘”（25GB）。等了很久了，一直没有对China开放。久等不至，热情渐渐冷却……，却在不经意中，发现了灯火阑珊中的倩影……