Feron's BLOG

编程范型

发表于 | 分类于 | | 阅读次数
个人整理的资料

编程范型

从网上找到的资料整理而成

编程范型或编程范式－Programming paradigm，（范即模范之意，范式即模式、方法），是一类典型的编程风格，是指从事软件工程的一类典型的风格（可以对照方法学）。如：函数式编程、程序编程、面向对象编程、指令式编程等等为不同的编程范型。
编程范型提供了（同时决定了）程序员对程序执行的看法。例如，在面向对象编程中，程序员认为程序是一系列相互作用的对象，而在函数式编程中一个程序会被看作是一个无状态的函数计算的序列。
正如软件工程中不同的群体会提倡不同的“方法学”一样，不同的编程语言也会提倡不同的“编程范型”。一些语言是专门为某个特定的范型设计的（如 Smalltalk 和 Java 支持面向对象编程，而 Haskell 和 Scheme 则支持函数式编程），同时还有另一些语言支持多种范型（如 Ruby 、 Common Lisp 、 Python 和 Oz ）。
很多编程范型已经被熟知他们禁止使用哪些技术，同时允许使用哪些。例如，纯粹的函数式编程不允许有副作用[1]；结构化编程不允许使用goto。可能是因为这个原因，新的范型常常被那些习惯于较早的风格的人认为是教条主义或过分严格。然而，这样避免某些技术反而更加证明了关于程序正确性——或仅仅是理解它的行为——的法则，而不用限制程序语言的一般性。
编程范型和编程语言之间的关系可能十分复杂，由于一个编程语言可以支持多种范型。例如，C++设计时，支持过程化编程、面向对象编程以及泛型编程。然而，设计师和程序员们要考虑如何使用这些范型元素来构建一个程序。一个人可以用 C++ 写出一个完全过程化的程序，另一个人也可以用 C++写出一个纯粹的面向对象程序，甚至还有人可以写出杂揉了两种范型的程序。

面向代理编程

面向代理编程 (Agent-oriented programming，缩写为AOP) ，一种编程典范，它的观点主要集中于软件代理人（Software agent）之上。它是由面向对象程序设计所发展出来。相对于面向对象程序设计以对象为主，代理人导向程序设计则是以代理人为核心。代理人可以被视为是对象的进一步抽象化。

基于组件的软件工程

基于组件的软件工程 (Component-based software engineering，简称CBSE) 或基于组件的开发 (Component-Based Development，简称CBD) 是一种软件开发范型。它是现今软件复用理论实用化的研究热点，在组件对象模型的支持下，通过复用已有的构件，软件开发者可以“即插即用”地快速构造应用软件。这样不仅可以节省时间和经费，提高工作效率，而且可以产生更加规范、更加可靠的应用软件。

声明式编程

声明式编程 ( Declarative programming ) 是一种编程范式，与命令式编程相对立。它描述目标的性质，让电脑明白目标，而非流程。声明式编程不用告诉电脑问题领域，从而避免随之而来的副作用。而指令式编程则需要用算法来明确的指出每一步该怎么做。
声明式编程通常被看做是形式逻辑的理论，把计算看做推导。声明式编程因大幅简化了并行计算的编写难度，自2009起备受关注。
声明式语言包括数据库查询语言 ( SQL, XQuery ) ，正则表达式，逻辑编程，函数式编程和组态管理系统。
声明式编程通过函数、推论规则或项重写 (term-rewriting) 规则，来描述变量之间的关系。它的语言运行器 (编译器或解释器) 采用了一个固定的算法，以从这些关系产生结果。
声明式编程语言通常用作解决人工智能和约束满足问题。

  • 函数编程

    函数式编程 (functional programming) 或称函数程序设计，又称泛函编程，是一种编程典范，它将电脑运算视为数学上的函数计算，并且避免使用程序状态以及易变对象。函数编程语言最重要的基础是λ演算 (lambda calculus)。而且λ演算的函数可以接受函数当作输入（引数）和输出（传出值）。
    比起命令式编程，函数式编程更加强调程序执行的结果而非执行的过程，倡导利用若干简单的执行单元让计算结果不断渐进，逐层推导复杂的运算，而不是设计一个复杂的执行过程。

  • 约束编程

    约束编程 (Constraint programming)是一种编程典范，在这种编程范式中，变量之间的‘关系’是以约束的形式陈述（组织）的。这些‘关系（约束）’和命令式编程语言元素不同的是：它们并非明确说明了要去执行的步骤中的某一步，而是规范其解的一些属性。这样看来，约束编程是一种声明式的编程范式。

  • 逻辑编程

    逻辑编序是种编程典范，它设置答案须匹配的规则来解决问题，而非设置步骤来解决问题。过程是

    事实+规则=结果。
    不同的方法，可以看Inductive logic programming。

    逻辑编程的要点是将正规的逻辑风格带入计算机程序设计之中。数学家和哲学家发现逻辑是有效的理论分析工具。很多问题可以自然地表示成一个理论。说需要解答一个问题，通常与解答一个新的假设是否跟现在的理论无冲突等价。逻辑提供了一个证明问题是真还是假的方法。创建证明的方法是人所皆知的，故逻辑是解答问题的可靠方法。逻辑编程系统则自动化了这个程序。人工智能在逻辑编程的发展中发挥了重要的影响。

    猴子和香蕉问题是逻辑编程社区的著名问题。电脑须自行找出令猴子接触香蕉的可行方法，取代程序员指定猴子接触香蕉的路径和方法。

    逻辑编程创建了描述一个问题里的世界的逻辑模型。逻辑编程的目标是对它的模型创建新的陈述。世界上知识不断澎涨。传统来说，我们会将一个问题陈述成单一的假设。逻辑编程的程序通过证明这个假设在模型里是否为真来解决问题。

    一些经常用到逻辑编程工具的范畴：

    专家系统，程序从一个巨大的模型中产生一个建议或答案。
    自动化证明定理，程序产生一些新定理来扩充现有的理论。
    最常用的逻辑编程语言是Prolog，另外有较适用于大型方案的Mercury。详尽的清单可见于Category:逻辑编程语言。

    • 回答集编程

      回答集编程是语法上类似传统逻辑编程而语义上密切于非单调逻辑的一种声明式编程。在传统逻辑编程和回答集编程之间的主要区别是如何表示否定为失败。在传统逻辑编程中，否定为失败指示推导失败；在回答集编程中，它指示一个文字的一致性。

      语法

      回答集编程由规则的集合构成，每个规则由一个头部和一个后部构成:
      1
      head \leftarrow body

    规则的头部和后部二者都是文字的集合，每个文字都是可能被否定的原子。与传统逻辑程序相反，原子都是命题而不是一阶的，并且可以使用两种形式的否定去否定它们: 经典否定(指示为$ \neg $ )和否定为失败(指示为 $not$)。文字要么是原子要么是(使用经典否定)否定的原子。下面是一个例子程序:

    1
    2
    3
    4
    5
    a \leftarrow b, not~c        
    a, not~\neg c \leftarrow not~d, \neg e       
    \neg c \leftarrow not~\neg e, a

    依据第一个规则， $a$ 是真，只要$b$ 是真，并且 $c$ 可以被假定为假而不产生矛盾。

    语义

    程序的语义基于它的回答集，每个回答集都是文字集合。对于不包含否定为失败的程序，程序的语义基于闭包和最小性的概念:

    程序在一个文字集合下闭合，如果这个集合包含至少一个在某个规则的头部中的文字，而总是包含在规则的体部中的所有文字。
    文字集合是一个程序回答集，如果在这个程序闭合于的文字集合中、它(在集合的容量(containment)上)是最小化的。
    如果程序包含使用否定为失败否定的一些文字，语义要求额外的简约概念:

    一个程序在一个文字集合下的简约是通过对每个规则进行下列变更而获得的程序:
    除去在头部中的、使用否定为失败否定的并且在集合中的所有文字；
    除去在后部中的、使用否定为失败否定的并且在集合中不包含的所有文字；
    删除整个规则，如果在应用完上面两个规则之后，它仍然包含(使用否定为失败)否定的原子。
    文字集合是一个程序的回答集，如果它是这个程序在这个集合自身下的简约的回答集。换句话说，可以通过运行下列非确定性的算法来计算一个回答集可以:

    选择文字集合 L;
    计算程序 P 在 L 下的简约 PL;
    如果 L 是 PL 所闭合的最小化文字集合则
    输出 L

    最初的文字集合 L 的选择是非确定性的。确定 L 是否为一个回答集的算法，首先计算程序在 L 下的简约，并接着检查 L 是否是这个无否定为失败的程序的回答集。

    一个回答集程序可以有零个、一个或多个回答集。一个程序蕴涵一个文字，如果它的所有的回答集都包含这个文字。

事件驱动程序设计

事件驱动程序设计 (Event-driven programming) 是一种电脑程序设计模型。这种模型的程序运行流程是由用户的动作（如鼠标的按键，键盘的按键动作）或者是由其他程序的消息来决定的。相对于批处理程序设计 (batch programming) 而言，程序运行的流程是由程序员来决定。批量的程序设计在初级程序设计教学课程上是一种方式。然而，事件驱动程序设计这种设计模型是在交互程序 (Interactive program) 的情况下孕育而生的。

事件驱动程序可以由任何编程语言来实现，然而使用某些语言来撰写会比其他的语言来的简单。有些集成开发环境（简称IDE）也会影响实现事件驱动程序设计的难易程度。有的 IDE 会使的开发工作变的很简单，有的则否。

  • 面向服务的体系结构

    面向服务的体系结构 (service-oriented architecture) 并不特指一种技术，而是一种分散式运算的软件设计方法。软件的部分组件(呼叫者)，可以透过网络上的通用协定呼叫另一个应用软件元件执行、运作，让呼叫者获得服务。SOA原则上采用开放标准、与软件资源进行交互并采用表示的标准方式。因此应能跨越厂商、产品与技术。一项服务应视为一个独立的功能单元，可以远端存取并独立执行与更新，例如在线上线查询信用卡账单。

SOA中的一项服务应有以下四个特性，

  • 针对某特定要求的输出，该服务就是运作一项商业逻辑
  • 具有完备的特性 (self-contained)
  • 消费者并不需要了解此服务的运作过程
  • 可能由底层其他服务组成

  • SOA的原则

    以下指导原则是开发，维护和使用SOA的基本原则，
  • 可重复使用, 粒度, 模组性, 可组合型, 物件化原件, 构件化以及具交互操作性
  • 符合开放标准(通用的或行业的)
  • 服务的识别和分类，提供和发布，监控和跟踪。

下面是一些特定的体系架构原则，

  • 服务封装
  • 服务松耦合(Loosely coupled) - 服务之间的关系最小化，只是互相知道。
  • 服务契约 - 服务按照服务描述文档所定义的服务契约行事。
  • 服务抽象 - 除了服务契约中所描述的内容，服务将对外部隐藏逻辑。
  • 服务的重用性 - 将逻辑分布在不同的服务中，以提高服务的重用性。
  • 服务的可组合性 - 一组服务可以协调工作并组合起来形成一个组合服务。
  • 服务自治 – 服务对所封装的逻辑具有控制权
  • 服务无状态 – 服务将一个活动所需保存的资讯最小化。
  • 服务的可被发现性 – 服务需要对外部提供描述资讯，这样可以通过现有的发现机制发现并访问这些服务。

除此以外，在定义一个SOA实现时，还需要考虑以下因素，

  • 生命周期管理
  • 有效使用系统资源
  • 服务成熟度和性能

命令式编程

指令式编程 (Imperative programming) ，是一种描述电脑所需作出的行为的编程典范。几乎所有电脑的硬件工作都是指令式的；几乎所有电脑的硬件都是设计来运行机器码，使用指令式的风格来写的。较高级的指令式编程语言使用变量和更复杂的语句，但仍依从相同的典范。菜谱和行动清单，虽非计算机程序，但与指令式编程有相似的风格：每步都是指令，有形的世界控制情况。因为指令式编程的基础观念，不但概念上比较熟悉，而且较容易具体表现于硬件，所以大部分的编程语言都是指令式的。

大部分的高级语言都支持四种基本的语句：

  • 运算语句一般来说都表现了在内存内的数据进行运算的行为，然后将结果存入内存中以便日后使用。高级指令式编程语言更能处理复杂的表达式，可能会产生四则运算和函数计算的结合。
  • 循环语句容许一些语句反复运行数次。循环可依据一个默认的数目来决定运行这些语句的次数；或反复运行它们，直至某些条件改变。
  • 条件分支语句容许仅当某些条件成立时才运行某个区块。否则，这个区块中的语句会略去，然后按区块后的语句继续运行。
  • 无条件分支语句容许运行顺序转移到程序的其他部分之中。包括跳跃（在很多语言中称为Goto）、副程序和Procedure等。
    循环、条件分支和无条件分支都是控制流程。

早期的指令式编程语言都是电脑本身的机械语言。在这些语言中，指示非常简单，令硬件的运行更容易，却阻碍了复杂程序的设计。1954年开始开发的FORTRAN，是首个在复杂程序的设计中除掉机器码的编程语言。它是编译型的编程语言，容许命名变量、复杂的表达式、副程序和其他功能，这些功能现在在指令式语言中都非常普遍。后来的二十年中，可以看到大量的其他高级指令式编程语言出现。在1980年后，面向对象编程有迅速的发展；面向对象编程语言均有着指令式的风格，但增添了支持对象的功能。

  • 结构化程序设计

    结构化程序设计 (Structured programming) ，一种编程典范。它采用子程序、代码区块、for循环以及while循环等结构，来取代传统的 goto。希望借此来改善计算机程序的明晰性、质量以及开发时间，并且避免写出面条式代码。

结构化程序设计在1960年代开始发展，科拉多·伯姆及朱塞佩·贾可皮尼 (Giuseppe Jacopini) 于1966年5月在《Communications of the ACM》期刊发表论文，说明任何一个有goto指令的程序，可以改为完全不使用goto指令的程序，后来艾兹赫尔·戴克斯特拉在1968年也提出著名的论文《GOTO陈述有害论》（Go To Statement Considered Harmful），因此结构化程序设计开始盛行，此概念理论上可以由结构化程序理论所证明，而在实务上，当时也有像ALGOL一样，有丰富控制结构的编程语言来实现结构化程序设计。

  • 过程式程序设计

    过程式程序设计 (Procedural programming) ，又称过程式编程、过程化编程，一种编程典范，有时会被视为是指令式编程的同义语。派生自结构化编程 (Structured programming) ，主要采取程序调用 (procedure call) 或函数调用 (function call) 的方式来进行流程控制。流程则由包涵一系列运算步骤的程序 (Procedures) ，例程 (routines) ，子程序 (subroutines), 方法（methods），或函数（functions）来控制。在程序运行的任何一个时间点，都可以调用某个特定的程序。任何一个特定的程序，也能被任意一个程序或是它自己本身调用。

    著名的例子有Linux内核，git，以及Apache HTTP Server等。

面向对象程序设计

面向对象程序设计(Object-oriented programming，缩写：OOP)是种具有对象概念的程序编程典范，同时也是一种程序开发的抽象方针。它可能包含数据、属性、代码与方法。对象则指的是类的实例。它将对象作为程序的基本单元，将程序和数据封装其中，以提高软件的重用性、灵活性和扩展性，对象里的程序可以访问及经常修改对象相关连的数据。在面向对象程序编程里，计算机程序会被设计成彼此相关的对象。

面向对象程序设计可以看作一种在程序中包含各种独立而又互相调用的对象的思想，这与传统的思想刚好相反：传统的程序设计主张将程序看作一系列函数的集合，或者直接就是一系列对电脑下达的指令。面向对象程序设计中的每一个对象都应该能够接受数据、处理数据并将数据传达给其它对象，因此它们都可以被看作一个小型的“机器”，即对象。目前已经被证实的是，面向对象程序设计推广了程序的灵活性和可维护性，并且在大型项目设计中广为应用。此外，支持者声称面向对象程序设计要比以往的做法更加便于学习，因为它能够让人们更简单地设计并维护程序，使得程序更加便于分析、设计、理解。反对者在某些领域对此予以否认。

当我们提到面向对象的时候，它不仅指一种程序设计方法。它更多意义上是一种程序开发方式。在这一方面，我们必须了解更多关于面向对象系统分析和面向对象设计（Object Oriented Design，简称OOD）方面的知识。许多流行的编程语言是面向对象的,它们的风格就是会透由对象来创出实例。

重要的面向对象编程语言包含Common Lisp、Python、C++、Objective-C、Smalltalk、Delphi、Java、Swift、C#、Perl、Ruby 与 PHP等。

  • 自动机编程

    自动机编程（Automata-based programming）是编程范式中的一种，是指程序或其中的部分是以有限状态机（FSM）为模型的程序，有些程序则会用其他型式（也更复杂）的自动机为其模型。

    有限状态机编程（FSM-based programming）大致上等同于自动机编程，但有限状态机编程专指以有限状态机为模型的程序。

    自动机编程有以下的二项特征：

    程序运行的时间中可以清楚划分成数个自动机的步骤（step），每一个步骤即为一个程序区块，有单一的进入点，可以是一个函数或其他程序。若有需要时，程序区块可以再依其状态的不同，划分为子区块。
    不同步骤的程序区块只能通过一组清楚标示的变量交换信息，这些变量称为状态（state），使用自动机编程的程序不能用其他不显然可见的方式标示状态，例如区域变量的数值、回传地址、目前程序指针的位置等。因此一程序在任二个不同时间下的差异，只有状态数值的不同，其余都相同。
    自动机编程的运行过程是一个由自动机步骤形成的循环。

    自动机编程中处理问题的思考方式很类似在利用图灵机、马尔可夫算法处理问题时的思考方式。

    示例：
    考虑一个C语言的程序，由标准输入流一行一行的读取数据，打印各一行的第一个英文单字。因此一开始需确认第一个英文单字之前是否有空白，若有，需读取所有空白后略过不打印，读取第一个英文单字然后打印，之后读取其他内容略过不打印，直到读到换行符号为止。任何情形下只要读到换行符号，就重新开始此算法，任何情形下只要读到文件结束（end-of-file）的符号，就结束程序。

    以下是传统指令式编程的C语言程序：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    #include <stdio.h>
    int main(void)
    {
        int c;
        do {
            c = getchar();
            while(c == ' ')
                c = getchar();
            while(c != EOF && c != ' ' && c != '\n') {
                putchar(c);
                c = getchar();
            }
            putchar('\n');
            while(c != EOF && c != '\n')
                c = getchar();
        } while(c != EOF);
        return 0;
    }

自动机编程的程序
上述问题也可以用有有限状态机的方式处理，此程序有三个不同的阶段：读取并跳过第一个单词前的空白、读取第一个单词并且打印、跳过后续的所有字符。以下将这三个阶段定义为三个状态before、inside及after。自动机编程的程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
int main(void)
{
    enum states {
        before, inside, after
    } state;
    int c;
    state = before;
    while((c = getchar()) != EOF) {
        switch(state) {
            case before:
                if(c == '\n') {
                    putchar('\n');
                } else
                if(c != ' ') {
                    putchar(c);
                    state = inside;
                }
                break;
            case inside:
                switch(c) {
                    case ' ':  state = after; break;
                    case '\n':
                        putchar('\n');
                        state = before;
                        break;
                    default:   putchar(c);
                }
                break;
            case after:
                if(c == '\n') {
                    putchar('\n');
                    state = before;
                }
        }
    }
    return 0;
}

虽然此程序较长，至少有一个明显的好处，程序中只调用一个读取字符的getchar()函数，而且程序中只有一个循环，不像之前程序使用四个循环。

此程序中while循环内的程序即为自动机的步骤，而循环本身即可重复的运行自动机的程序。

对应的有限状态机示意图
此程序实现如右图所示的有限状态机，其中N表示换行字符、S表示空白、A表示其他的字符。自动机依目前状态及读取的字符不同，会运行图中一个箭头所示的动作，可能是由一个状态跳到下一个状态，也者停在原来的状态。其中有些箭头有标示星号，表示需打印读到的字符。