【原题】 The Paradigms of Programming
【译题】 编程范式
【作者】 Robert W.Floyd
【题注】
Paradigm … [a. F. paradigme, ad.L. paradigma, a. Gr. παραδειγμα, pattern, example, fπαραδεικγν ? γαι to exhibit beside, show side by side …]
1. A pattern, exemplar, example.
1752 J. Gill Trinity v. 91
原型（The archetype）， 范式（The paradigm），标本（The exemplar），和 观念（ idea），
通过它们所有的事情得以实现（according to which all things were made）。
牛津英语词典
今天我想要讲的是编程范式，它们是如何影响了作为计算机程序设计师的我们之成功，它们应当如何来教授，它们应当如何寄宿在我们程序语言之中。
一个熟悉的编程范式例子就是结构编程技术( the technique of structured programming )，其在大多数编程方法论的处理中表现为是占统治地位的范式。结构编程，由 Dijkstra 【参见6 】， Wirth 【参见27，29】 ，Parnas 【参见21】还有其他人作出形式化，是由两个相（phases）组成的。
在自上而下设计的第一个相中作阶梯式的提纯，问题就被分解为非常小数量的更简单的子问题（In the first phase, that o f top-down design, or stepwise refmement, the problem is decomposed into a very small number o f simpler subproblems）。在模拟线性等式的编程解决方案中，说，第一级分解将会进入一个“将等式三角化”阶段（a stage of triangularizing the equations），其后的“三角化系统中的倒转代换（backsubstitution in the triangularized system）”阶段。这个渐进分解将会继续下去直至浮现上来的子问题对直接应对来说足够的简单为止。在联立方程（the simultaneous equation）的例子中，回代处理（the back substitution process）将进一步得到分解 作为一个“其为找到并存储第 i 个方程 的第 i 个变量值（which finds and stores the value of the ith variable from the ith equation）”过程的一个逆迭代（a backwards iteration）。然而进一步的分解将会衍生一个完全细节的算法。
结构化编程范式的第二个相是“使得来自具体对象和其背后的器的函数的工作向上，到达更加抽象的‘其贯穿用于通过自上而下设计的模块’对象和函数（entails working upward from the concrete objects and functions of the underlying machine to the more abstract objects and functions used throughout the modules produced by the top-down design）”。在线性方程的例子中，如果方程的系数是某个变量的有理函数（if the coefficients of the equations are rational functions of one variable），我们就可以首先设计多精度算术的表示和过程（multiple-precision arithmetic representation and procedures），然后，基于它们之上构建，一个表示“其自身算术过程”的多项式，等等。这种方法被指涉为抽象级别方法（the method of levels of abstraction），或信息隐藏（information hiding）。
结构化编程范式毫无疑问被普遍接受了（译注：指70年代末）。其最积极的拥护者会承认“其自身不足以使所有难问题变的容易些（it does not by itself suffice to make all hard problems easy）”。其它有一个更专门类型的高级别范式，如“分支界限（branch-and-bound）”【参见 17，20】 或“分治（divide-and-conquer ）”【参见1，11】技术，将继续是基本的。但是结构编程的范式能够扩展某人的设计能力，允许构建“太复杂而难于设计（that are too complicated to be designed）”程序而无需方法论支持就是可靠的（reliably without methodological support）。
我相信当前编程艺术的状态显示了“在我们关于‘存在的范式，教授编程范式的方式，我们编程语言支持或不支持的方式，那些范式的用户社区’的知识中”中，我们范式存量的不足（inadequacies in our stock of paradigms）。
计算机编程艺术的状态最近被 Robert Balzer 这样提到：“众所周知，软件处于令人沮丧的状态中。它是不可靠的，交付延迟的，对变化没有反应的，低效的，以及昂贵的。进一步而言，当前软件是劳动力密集型的，状况将随着需求的增加和劳动力成本的上升而进一步恶化 ”。如果这种口气听上去象是差不多十年前的著名“软件危机（software crisis）”，我们处在相同的状况已经有十到十五年的这个事实显示了“软件沮丧（software depression）”是一个更合适的术语。
Thomas S. Kuhn ，在《科学革命的结构》一书中【参见16】，描述了在过去几个世纪中的（pas’ everal centuries ）科学革命是“从占统治地位的范式之变更中浮现出来（arising from changes in the dominant paradigms）”。Kuhn 的一些观察看上去对我们的领域也合适。给学生科提供了当前科学知识的该科学教科书中，Kuhn 写到：
那些文本有，比如，常常是看上去蕴含说科学的内容是通过观察而来的独特例证（the content of science is uniquely exemplified by the observations），描述在字里行间的定律和定理（Those texts have, for example, often seemed to imply that the content of science is uniquely exemplified by the observations, laws and theories described in their pages）。
他还写到：
对范式的研究，包含了许多较之上面显示的命名远远需要细化的东西（including many that are far more specialized than those named illustratively above），其主要是为了“其后他/她会进行实践的”学生成为独特的科学社团成员。由于他/她加入了那些“已经从同一个具体模型中学习了他们领域之基础”的人，他/她接下来的实践将很少激起于基础之上的公然争论. …..
在计算机科学中，你可以看到几个这样的社区，每个都说自己的话并使用自己的范式。实际上，编程语言典型的鼓励使用某些范式，不鼓励另外一些。对 Lisp 编程有很好定义的学校，APE 编程， Algol 编程，等等。一些关注的是数据流（data flow），另一些则是控制流（control flow），作为关于一个程序的主要结构化信息。递归和迭代，拷贝和共享数据结构，名字调用和值调用，都有其信徒。
Kuhn 又说道：
旧有的学校渐渐消失。它们消失的部分原因是其成员转到了新的范式中去了。但总是有人坚守着这个或者那个老观点，而且他们简单的喜欢学位因而忘了其工作。
在计算中，对这样喜欢学位的人没有途径。我建议他们最好是成为软件开发管理人员。
Balzer， 在他无望的反对软件构建的陈述中，进而预言说自动编程将会拯救我们。我但愿自动编程能成功，但是，直到它们前清理了牛棚前，我们最好的期望是改进我们自己的能力。我相信我们关于“发展编程的一般实践（improve the general practice ofprogramming）”有的最好机会是“关注我们的范式（attend to our paradigms）”。
在 1960年代早期，对内容无关预言的解析是一个“既在编译开发也在自然语言中有迫切重要性（pressing importance in both compiler development and natural linguistics）”的问题。已经发表的算法通常既慢且错。John Cocke， 自称花了一点儿努力，就发现了一个快速和简单的算法【参见2】，基于一个现在是标准的“其是动态编程的计算形式（which is the computational form of dynamic programming）”范式。动态编程范式解决了一个对给定输入的“对所有更小的输入，通过第一次迭代就解决的”问题 （The dynamic programming paradigm solves a problem for given input by first iteratively solving it for all smaller inputs） 。Cocke的算法成功的发现了输入的所有子串的所有解析。在这个概念框架内，问题变的无足轻重了。算法的结果就是，其是第一个在多项式时间内可一致运行（uniformly run in polynomial time）。
在差不多同时，在经历发布了几个不正确的自顶向下分析程序（parsers）后，我处理“通过发明‘找到处理器的一个层级结构’范式（by inventing the paradigm of finding a hierarchical organization of processors）去设计一个正确的分析程序”问题，类似于一个人类组织的雇主雇佣和解雇属下，我的处理可以解决该问题，然后模拟该组织的行为【参见8】。对这种多递归过程（multiple recursive processes）的模拟让我使用递归协同程序去作为一个控制结构（use of recursive coroutines as a control structure）。我后来发现其它程序员在组合问题（combinatorial problems）上有麻烦，比如Gelernter 和他的几何定理证明机器【参见10】， 很明显发明了相同的控制结构。
John Cocke 和我的经历显示出那种“在编程中可以为续的进步需要的是持续的发明，精心设计，以及新范式的交流（ that continued advance in programming will require the continuing invention, elaboration, and communication of new paradigms）”的可能性（likelihood ）。
一个有效精心设计范式的例子是 Shortliffe 和 Davis 在 MYCIN 【参见24】项目上的工作 ，其对细菌传染病作出有技巧的诊断并推荐药物。MYCIN 是基于规则的系统， 基于一个独立规则的大集合，每一个规则都对适用性有一个可测试的条件，以及当该条件被满足时，有一个简单的结果行为。Davis 的 TEIRESIAS 【参见5】 程序修改了 MVCIN， 允许一个专家级用户改进 MVCIN 的性能。TEIRESIAS 程序通过“经由规则和允许它的条件去从一个不期望的结果去追踪返回职责（tracing responsibility backward from an undesired result through the rules and conditions that permitted it）”精心制作了范式。通过这种方法其对一个“并非一个程序员的”医药专家去让MVCIN的诊断能力改进变得技术上可行。虽然在 MVCIN 没有什么不可以在传统的使用条件迁移决策分支树中编码的（While there is nothing in MVCIN which could not have been coded in a traditional branching tree of decisions using conditional transfers），但正是使用了基于规则的范式，其带有后来对自修正的精心设计，才使得程序的交互进展成为可能（makes the interactive improvement of the program possible）。
如果编程艺术的一般进展需要持续的发明和精心设计的范式，那么独立程序员的技艺之提升就需要他扩展自己的范式库（repertory of paradigms）。以我自己设计困难算法的经验，我发现在扩展我自己的能力上一个特定技术最有用。 在解决了一个有挑战性的问题后，我从头做起再一次的解决了它，仅回溯了有识之士的早期解决方案（After solving a challenging problem, I solve it again from scratch, retracing only the insight of the earlier solution）。我再一次去解决这个，直到解决方案如我所期望的那样明显直白为止（I repeat this until the solution is as clear and direct as I can hope for）。然后我寻找一个之于处理类似问题的通用规则，其将会以最有效率的方式在第一时间引领我到之于该给定问题的方法。常常是这样的一个规则有永恒的价值。通过查找这样的一个通用规则， 我被从“先前提到的基于递归协同程序的解析算法（the previously mentioned parsing algorithm based on recursive coroutines ）”引导至“写非确定性程序的一般方法（the general method of writing nondeterministic programs）”【参见9 】，其然后通过宏指令扩展（by a macroexpansion ） 被转换到常规确定性的一个。这个后来建立起来的，使用在明显无关的“通过在人工智能中的计算机”问题解决领域中的范式，开始嵌入编程语言 PLANNER 【参见12 ，13】， MICROPLANNER 【参见25】，和QA4 【参见23】。
通过独立程序员获取的新范式可能是“可能受到读取其他人程序的激励（may be encouraged by reading other people’s programs）”，但这是受“被选出的对某范式同伴的限制，很可能为了它们和本地范式集的比较之故（ the limitation that one’s associates are likely to have been chosen for their compatibility with the local paradigm set） ”支配的。对之的证据就是我们的业界之广告频率，不是为了程序员，而是为了Fortran 程序员或者 Cobol 程序员。Fortran 规则可以在没几个小时内学到；相关范式的时间就长多了，对学习和遗忘具如是。
和相异约定下写出的程序作接触可能是有益的。在今年休息天访问了 MIT ，我见到了程序能力的许多例子，Lisp 程序员从一个单独数据结构中获得这种能力中 ，其也用作为了“在程序中出现的所有函数和操作”的，带有“将程序当作数据去操作的能力”的一个统一句法结构（which is also used as a uniform syntactic structure for all the functions and operations which appear in programs, with the capability to manip- ulate programs as data ）。虽然我自己先前的热情是对类似 Algol 家族的句法丰富语言而言的，我现在清晰且实在的看到 Minsky在1970年图灵演讲的力量【参见19】，在该次演讲中他认为， Lisp 的结构一致性和自参考能力（uniformity of structure and power of self reference）给“其内容是值得牺牲可视化形式的（whose content was well worth the sacrifice of visual form）”程序员以能力。我愿意达到关于这些方式的某些合适的综合。
自从我 1956 年进入计算机计算机领，每个人仍旧是希望设计一个新的编程语言。在斯坦福大学毕业生办公室的墙上写了一段话“较之写程序，我更愿意写那种帮助我去写程序的程序（I would rather write programs to help me write programs than write programs）”。在评估每年在新编程语言上的收获时，通过“通过扩展至它们所允许的程度和对有效编程范式的使用（by the extent to which they permit and encourage the use of effective programming paradigms） ”有助于对那些新编程语言作出分类。当我们把软件的范式弄明白时，我们发现有许多范式。Cordell Green【参见11】发现简单搜索和排序算法的形成机制，比如归并排序和快速排序，要求数以百计的规则，可能对大多数程序员而言，大多数这些规则有关的范式是熟悉的。通常我们的编程语言没有给我们什么助益，甚或者挫败我们，甚至是在使用熟悉的低层范式。一些例子如下。
假设我们在模拟一个捕食者系统的动力学种群（the population dynamics of a predator-prey system）——可能是， 狼和兔子。我们有两个等式：
W’ = f(W, R)
R’ = g(W, R)
其在一个时间周期的最后给出了狼和兔子的数量，作为一个在周期开始时的数量函数 。
一个通常初阶人员会犯的错误是：
FOR ∣ : . . . . DO
BEGIN
W := f(W, R);
R := g(W, R)
END
这里 g 是被 错误的 使用被修改量了的W 去求值的。为让程序运行起来，我们必需这样写：
FOR ∣ : . . . . DO
BEGIN
REAL TEMP;
TEMP := f(W, R);
R := g(W, R);
W := TEMP
END
初学者正确的相信说，我们不应当这样做。诸范式中最通用的一个，就像在捕食者模拟中，是将诸新值同时赋予诸状态向量组件的（simultaneous assignment of new values to the components of state vectors）。但对于让任何语言有一个“联立分配（simultaneous assignment）”操作，这仍旧很难。我们必需代之以“遍览机械的，费时的以及易错的操作”所引入的一个或多个零时变量，并对围绕在它们周围的新值做梳理（shunting the new values around through them）。
再次，有个看起来简单的问题：
读取文本的行，直至找到一个完全的空行为止。消除单词之间的冗余空格。打印文本，一行三十个字，单词不在行之间不折续。
由于所有输入和输出是使用多级迭代自然表达的，而且由于输入迭代不和输出迭代相嵌套，这个问题对在大多数编程语言中去编程就是令人惊异的难了【参见14】。如讲师所估计，初学者对其花了三四次，要么是以训练无素的混乱告终，要么带一个自制控制结构去使用显式增量和控制执行去模拟一些期望的迭代。
该问题是通过分解到“对输入，转换，以及一个字符流的输出的”三个流通联立程序【参见4】而自然形成的。但是，除了模拟语言外，我们编程语言中的少数一些有一个联立程序控制结构，足够允许对一种自然方式下的问题去编程了。
当一个语言让一范式惬意时，我会说这个语言支持该范式。当一个语言让一范式可行时，但不是惬意的，我会说该语言对该范式是若支持的。一如先前两个例子所显示的，我们的大多数语言对联立分配是弱支持的（only weakly support simultaneous assignment），且完全不支持联立程序（coroutines），所需要的机制，尽管说较之那些“调用名字的过程递归（those for recursive call-by-name procedures）”要简单的多而且有用的多 ，还是在十七年后实现了 Algol 语言族。
甚至是结构编程的范式顶多通过“我们许多的编程语言”被弱支持了。为了当在某人设计它时，写下联立方程求解器，他应当能写：
MAIN__PROGRAM:
BEGIN
TRIANGULARIZE;
BACK_SUBSTITUTE
END;
BACK_SUBSTITUTE:
FOR ∣ := N STEP -1 UNTIL 1 DO
SOLVLFOR__VARIABLE(I);
SOLVE_FOR__VARIABLE(I):
_ _ _
_ _ _
TRIANGULARIZE:
_ _ _
_ _ _
多精度算术过程程序
有理函数算术过程程序
声明数组
在大多数当前语言中，不可以提供主程序、过程，以及在这种命令下的数据声明。通常需要一些给人预备的“一准备排序的机制（ of a sort readily mechanizable）”文本洗牌（text-shuffling）。进一步的，任何在多于一个的多精度过程中使用的变量，必需对该程序的所有“其中可以完成多精度算术的”部分而言是全局的，因此就允许偶然修改，这和信息隐藏的原则相背离。最后 ，将一个问题过度细分到一个过程层级（the detailed breakdown of a problem into a hierarchy of procedures），这典型的会导致非常无效的代码，即便大多仅被一处调用的那些过程可有效通过宏扩展实现。
一个“较之结构化编程范式而言，甚至处于更高级别的抽象（at an even higher level of abstraction than the structured programming paradigm）”的范式是，对诸语言的一个层级之营造（is the construction of a hierarchy of languages），其中有“在操作着最抽象对象的最高级语言中的”编程，并被转换到下一级别语言的编程中（are translated into programs on the next lower level language）。例子包括了数个“公式－操纵语言（ormula-manipulation languages）”，其是在 Lisp， Fortran 和其它语言的基础上构建的。我们的大多数低层语言不能完全支持这样的诸超级结构（superstructures）。比如这大多数低层语言的诊断系统能够进行具体的浇筑，从而诊断消息仅仅在参考了更低级别的转写程序时才是智能的（For example, their error diagnostic systems are usually cast in concrete, so that diagnostic messages are intelligible only by reference to the translated program on the lower level）。
我相信编程作为一种手艺的持续进步，需要那种“其是支持它们用户社区的主要范式的（which support the major paradigms of their user’s communities）”语言的开发和宣传。一门语言的设计应当通过概述那些范式而被赶超 ， 包括了一个对“ 由组挫不受支持的范式而发的编程缺陷（the deficiencies in programming caused by discouragement of unsupported paradigms）”的研究。只要我提到过的诸范式和其它我没有提到过的诸范式仍旧是不被编程语言支持或是弱支持的话，我从我们语言的扩展，例如 Pascal 中的多种记录和指数集【参见15，28】中就不能得到满足。如果会有一个科学的编程语言设计的话，那么该设计很可能大面上是由“将语言匹配到它们所支持的设计方式（matching languages to the design methods they support）”所组成的。
我不是想让人联想说，对范式的支持受到我们编程语言本身的限制（I do not want to imply that support of paradigms is limited to our programming languages proper）。我们于其中编程的整个环境，诊断系统，文件系统，编辑器，以及所有的那些环境，当“对支持设计程序的方法谱线来说，是能或不能的（supporting or failing to support the spectrum of methods for design of programs）”时，是可以去分析的。有希望让这变的得到承认（There is hope that this is becoming recognized）。比如，最近在法国 IRIA 和其它地方的工作已经实现了编辑器，其能知晓它们所编辑的程序之结构【译注 7，18，26】。任何试过“改变每次发生的 X， 当一个程序中的一标识符没有足够改变其它 X 时（as changing every occurrence of X as an identifier in a program without inadvertently changing all the other X’s）”这样一个简单任务的人会同意这一点。
现在关于“教授计算机编程（teach as computer programming）”我要讲几句。我们不幸的强迫症的一部分是“出现在我们典型的选择教授什么时的，内容上的形式（with form over content）”，Minsky 对此在他的图灵演讲中深表了遗憾【参见19】。如果我问另一个教授在介绍性的编程课程中他教什么时，他大声回答的不外是 “Pascal”或者“FORTRAN”。我知道他在教一个语法，一个语义规则集，以及一些精巧的算法，让学生自己去发现一些设计过程。即便是基于结构化编程范式的课本，尽管在最高级别上给出了“我们可能叫做‘故事级（story）’编程设计的”方向，通常于中间级别无补，我们把这种级别叫做“段落（paragraph）”级。
我相信“显式的对所有级别的编程设计去教授系统方法集合（to explicitly teach a set of systematic methods for all levels of program design）”是可能的，而且那样训练出来的学生较之“那些通常完全是通过对精巧程序研究去教授的学生（those conventionally taught entirely by the study of finished programs）”有更大的知识储备（have a large head start）。
我们可以教什么的例子如下。
当我给学生介绍一门编程语言的输入能力时，我引入了一个为了交互输入的标准范式，以我称之为“提示__读取__检查__反馈（PROMPT_READ_CHECK_ ECHO）”的宏指令形式，其读取直至输入数据满足一个有效性测试，然后将其反馈到输出文件。这个宏，在一个级别上，本身是一个关于迭代和输入的范式。在同时，因为该宏一次次的进行读取而不是说“数据无效”，其立即就是一个比先前对“对循环执行‘n 以及 一般时间’（for the loop executed ‘n and a half times’）”教授的范式而言更通用的范式。
PROMPT __READ__CHECK__ECHO: 参数是一个字符串
PROMPT 要读取一个变量 V , 以及刻画了坏数据的一个条件 BAD;
PRINT ON__TERMINAL(PROMPT);
READ_FROM_TERMINAL(V);
WHILE BAD(V) DO
BEGIN
PRINT__ON TERMINAL(" 无效数据 ");
READ__FROM TERMINAL(V)
END;
PRINT__ON__FILE(V)
这个宏也在一个高层次上对“程序员在面向程序的使用中之职责（the responsibilities of the programmer toward the user of the program）”作了实例化，包括了“一个程序的每个组件应受到对来“其组件没有被设计过的”输入的保护（each component of a program should be protected from input for which that component was not designed）”观念。
Howard Shrobe 和其他 MIT 的程序员学徒组织（the Programmer’s Apprentice group）【参见22】成员已经成功的教授了新手学生广泛有用的一个范式，他们叫做是“形成/过滤/累积（generate/filter/accumulate）”。当问题是由“枚举一个集合的元素，过滤出一个子类，累积某些关于该子集的函数（enumerating the elements of a set, filtering out a subset, and accumulating some function of the elements in the subset ）”组成的时候，学生学会了识别许多表面类似的这些问题。学生所使用的 MACUSP 语言【参见18】支持这种范式；学生仅提供生成器，过滤器，以及累积器。
参考 （References）
1. Aho, A.V., Hopcroft, J.E., and Ullman, J.D. The Design and
Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass.
1974.
2. Aho, A.V., and Ullman, J.D. The Theory of Parsing, Translation,
and Compiling, Vol. 1: Parsing. Prentice-Hall, Englewood Cliffs, New
Jersey, 1972.
3. Balzer, R. Imprecise program specification. Report ISI/RR-75-
36, Inform. Sciences Inst., Dec. 1975.
4. Conway, M.E. Design of a separable transition-diagram
compiler. Comm. ACM 6, 7 (July 1963), 396-408.
5. Davis, R. Interactive transfer of expertise: acquisition of new
inference rules. Proc. Int. Joint Conf. on Artif. Intell., MIT,
Cambridge, Mass., August 1977, pp. 321-328.
6. Dijkstra, E.W. Notes on structured programming. In Structured
Programming, O.J. Dahl, E.W. Dijkstra, and C.A.R. Hoare,
Academic Press, New York, 1972, pp. 1-82.
7. Donzeau-Gouge, V., Huet, G., Kahn, G., Lang, B., and Levy, J.J.
A structure oriented program editor: A first step towards computer
assisted programming. Res. Rep. 114, IRIA, Paris, April 1975.
8. Floyd, R.W. The syntax of programming languages–a survey.
IEEE EC-13, 4 (Aug. 1964), 346-353.
9. Floyd, R.W. Nondeterministic algorithms. J.ACM 14, 4 (Oct.
1967), 636-644.
10. Gelernter. Realization of a geometry-theorem proving machine.
In Computers and Thought, E. Feigenbaum and J. Feldman, Eds.,
McGraw-Hill, New York, 1963, pp. 134–152.
11. Green, C.C., and Barstow, D. On program synthesis knowledge.
Artif. lntell. 10, 3 (June 1978), 241-279.
12. Hewitt, C. PLANNER: A language for proving theorems in
robots. Proc. Int. Joint Conf. on Artif. Intell., Washington, D.C.,
1969.
13. Hewitt, C. Description and theoretical analysis (using schemata)
of PLANNER… AI TR-258, MIT, Cambridge, Mass., April 1972.
14. Hoare, C.A.R. Communicating sequential processes. Comm.
ACM 21, 8 (Aug. 1978), 666-677.
15. Jensen, K., and Wirth, N. Pascal User Manual and Report.
Springer-Verlag, New York, 1978.
16. Kuhn, T.S. The Structure of Scientific Revolutions. Univ. of
Chicago Press, Chicago, Ill., 1970.
17. Lawler, E., and Wood, D. Branch and bound methods: A survey.
Operations Res. 14, 4 (July-Aug. 1966), 699-719.
18. MACLISP Manual. MIT, Cambridge, Mass., July 1978.
pending 11.18 afternoon
(未完)