程序设计的要素

C++STL可能是语言标准库中最令人印象深刻的成就。大多数程序员都在抱怨他们的语言的默认字符串性能不够好，几乎每个标准的C++字符串函数实际上都在任意字符序列上运行。设计您自己的容器？Find_if和内置的一样好用。它这样做的同时，通常比您自己编写的代码性能更好。

Alex Stepanov是实现这一点的人，编程元素(Elements of Programming，EOP)是他对自己编写泛型代码方法的200页赞颂。他相信编程可以从一门艺术转变为一门以数学为基础的严格学科，我长期以来一直钦佩他的渊博知识和影响力。事实上，他多年来一直在我喜欢和他共进午餐的人名单上名列前茅。(读者们好-有人能帮忙吗？)。

现在，我要写一篇负面评论来毁了这一切。

EOP有一个很好的开始和一个很好的结束。第一章解释了核心编程语言概念，如类型和状态-使用非标准术语，但从解释的清晰度来看，可能是故意的。这在他的伟大想法中达到了顶峰，他认为能够在任何类型上编写程序，提供称为概念的操作和属性捆绑包，在它们进入C++标准之前的十多年里，本书对此进行了解释。后记是对这种方法的力量的几页反思。

在这11个章节中，他玩着同样的游戏：定义一个新的抽象，然后展示一系列可以用它编写的函数。不幸的是，这些函数和抽象在很大程度上并不是很有趣。

有一个著名的网站叫做Project Euler，在那里用户编写代码来解决数学问题，比如“在棋盘游戏大富翁的修改版本中，玩家最有可能落地的三个方块是什么？”我以前的编程竞赛教练反对用它来练习，因为“它不是真正的编程，也不是真正的数学。”

我认为这是对EOP的恰当描述，特别是前半部分。这从第2章开始，这一章是关于涉及对自身重复应用某些函数(迭代)的很酷的算法。我在本科生最喜欢的一堂课就是关于这个主题的，但我仍然不喜欢这一章，因为我不知道这些算法除了利基数学主题之外的任何应用。这在第5章有了新的进展，在大约5页的篇幅里，他从解释交换性到定义么半群、群和环的代数结构，一直到代数模块(与软件模块无关)。我无法理解这些解释对那些还不知道这些概念的人有用，当然对已经知道这些概念的人也没有用。虽然我确实知道组在软件工程中的许多用法-作为可逆操作概念的抽象-但他实际上在本章的其余部分都在考虑最大公约数函数的泛化。

我吃力地读完了这些章节，为书的后半部分感到兴奋，它主要集中在迭代器和容器上，这是与典型软件工程更相关的东西。然而，在看到列表复制功能的各种变体的无穷无尽的列表之后，我发现自己没有更多的满足感，很快就回到了浏览页面的状态。

除了我的长期目标是找到所有关于软件设计的好文章之外，我在读这本书时还有一个短期目标：一个学生想让我在这本书的基础上授课。但是，这本书读到一半时，我的截止日期很快就要到了，我还没有找到任何足够有用的材料，可以供有经验的工程师上软件设计课。

然后我注意到，所有章节都是由更深层次的原则生成的，即提出一个良好的抽象来编写泛型函数。我的想法是，也许我可以将EOP作为一本问题书，告诉他们查看泛型函数的描述，然后提出可以针对它们编写的代码和抽象。唉，选题不适合这个目的。例如，书中有一节涉及通过矩阵求幂来计算整数序列。对于很多上过线性代数课程的人来说，让学生自己想出这个问题太熟悉了，而对于没有上过这门课的人来说，这是不可能的。我确实设计了一堂课，让学生们想出他们自己对泛型编程问题的抽象，但我使用了与书完全无关的例子。

我问推荐EOP的朋友他从这本书中学到了什么，他的第一个回答是使用后藤健二的技术优雅地表达状态机。我同样喜欢这一部分，但是，唉，这是我从这本书中得到的唯一具体的东西。我会在这篇评论的最后给你解释，剩下的200页就省下你了。

我有数学本科学位，写过几篇关于泛型编程的论文，所以我知道我读这本书是为了让别人受益。尽管如此，我认为如果不是这样，我的观点不会改变，我真的希望帮助理解许多确实非常喜欢它的读者的观点。相反，我发现自己同意这位亚马逊评论家的观点，尽管我对斯捷潘诺夫太钦佩了，不会考虑给他一个一星级的评级：

如果您曾经编写过泛型函数，那么您已经知道类型参数必须遵守一组前提条件。这本书列出了一大堆类型、数字、代数结构、迭代器等的定义，以便让人们很容易被数学符号迷惑。它做得很草率，用C++编写了一些琐碎的泛型算法。不管人们在多大程度上利用这个话题来完成一些有趣的事情，这本书都不会回避。

当我阅读斯捷潘诺夫的其他材料时，我为这本本可以成为的书而哀悼。斯捷潘诺夫显然关心这些抽象概念和算法，以至于他在大体上相同的材料上写了第二本书，用了更喋喋不休的阐述，章节更明确地专注于纯粹的数学。如果他设法向我传达这种感激之情，那会有什么不同呢？演讲结束后的第二天，我观看了斯捷潘诺夫的一位亲密同事的演讲。“在这个菜单中，你可以选择一堆行，然后将它们拖到其他地方，”他在动画幻灯片上解释道。“你们中有多少人能在一行中实现这一点？”这让我想再次打开关于“旋转算法”的第10.4节。

我开始看他在亚马逊举办的研讨会。我只有几堂课，但我已经被他的高超的教学能力迷住了。我觉得我和他在一起解决问题。当他讲述他如何发明“规则类型”的故事时，我感觉我学到了一个伟大的秘密，这种类型在整个EOP中都在使用，但从未被激发出来。老实说，我仍然不知道这个系列讲座是关于什么的，但我希望在我完成后推荐它。

简而言之，斯捷潘诺夫给了编程世界很多礼物，而EOP不是其中之一。

除了少数例外，EOP既没有教授日常编程中有用的抽象，也没有教您发明自己的技能。

“从代码中的一个位置到另一个位置的最快方法是转到。”

-Alexander Stepanov许多迭代算法可以被描述为状态机：首先它寻找一个X，然后对它执行Y，然后它寻找另一个X，依此类推。Stepanov主张使用Goto的样式，而不是试图将状态机中的循环变成结构化循环，每个机器状态都有一个Goto-Label。

在寻找最好地说明这一点的示例时，我希望代码少于40行(这排除了Stepanov的示例)，在几乎没有上下文或C++知识的情况下可以理解，并且不等同于正则表达式。因此：

在我的去功能化演讲中，我展示了许多状态机是从递归函数派生的，通过在递归调用之间为程序中的每个点创建一个状态进行迭代遍历。在那次演讲中，我以打印二叉树为例完整地演示了这一点。事实证明，添加圆括号大大增加了派生的难度，因为在处理节点之后可能需要打印任意数量的右括号。而这一困难来自于试图将状态机推向循环。

在本例中，正如我从一个递归函数开始编写这个示例一样，递归版本非常简单：

Void print_tree_rec(tree*t){if(t！=null){printf("；("；)；print_tree_rec(t->；left)；printf("；%d"；，t->；element)；print_tree_rec(t->；right)；printf("；)"；)；}}。

但是，对于其他状态机来说，递归版本就不那么容易了。例如，Dijkstra早在1961年就创建了用于解析算术表达式的“分流码数”算法，但我直到2007年才意识到使用重新函数化技术发现了递归等效项。

我承认：当我第一次考虑如何使这个递归函数迭代时，我没有得到它，并且不得不查找它。解决方案是将图中的“NEXT FROM STACK”状态与其后继状态合并，从而产生一个具有两个嵌套WHILE循环的解决方案，代价是一些重复的代码。

然而，基于后藤健二的版本很好地读出了这张图。这段代码中需要注意的一点是：虽然堆栈s被初始化为NULL，但是Push()和POP()调用实际上可以更改它。

Void print_tree(tree*t){tree*cur=t；STACK*s=NULL；BEGIN_PRINT_NODE：if(cur==NULL){GOTO DISPATCH_STACK_FRAME；}ELSE{printf("；("；)；PUSH(LEFT_CHILD，CUR，s)；CUR=CUR-&>；LEFT；GOTO BEGIN_PRINT_NODE；}PRINT_ELEMENT：printf("；%d"；，cur-&>element)；PUSH(right_Child，cur，s)；cur=cur-&>；right；goto start_print_node；Finish_print_node：printf("；)"；)；goto调度_栈_帧；调度_栈_帧：std：：Pair<；DIR，tree*>；top_frame；if(s=null)转到End；top_frame=POP(S)；cur=top_frame.Second；如果(top_frame.first==Left_Child)转到print_element；否则转到Finish_print_node；end：return；}。

无论是我还是推荐这本书的朋友，自从读了这本书后，都没有机会使用过这一技巧。但是当你实现状态机的时候，这可能是一个很好的把戏--对于那些从小学习后藤被认为有害的人来说，这是一个令人愉快的惊喜。

更新：读者格雷格·乔根森(Greg Jorgensen)写道，他在1991年从“计算机语言”(Computer Language)杂志上保存了一篇关于这个主题的文章。我已经用这种风格写了几个FSM，并取得了成功的结果。其中一个仍然在图形终端仿真程序的内部使用。