Wing of Dream 梦境之翼

编程范式(Programming Paradigms)

作为专业程序员，对方法论的持续抽象绝对是一项明智的长期投资。

Robert W. Floyd在1978年图灵奖颁奖礼上如是说[RWF79]，这里所说的“方法论”即编程范式(Programming Paradigms)。范式一词源自Thomas S. Kuhn的《科学革命的结构》，Kuhn认为过去数个世纪的科学变革，实质上是主宰范式的更替，而这些范式却都曾在一段时期内常自认为能够独立揭示科学的内涵[TSK62]。具体到程序设计领域，范式表示为编程活动中存在的公共风格或方法论。例如，结构化编程可看作是上世纪70年代的主宰范式，但并非唯一。即使是忠实的拥趸也必须承认，结构化编程在解决某些问题时并不理想，于是持续有诸如分支限定(branch-and-bound)、分治(divide-and-conquer)、状态机(state machine)等其他更高层级范式的提出。或许有人认为使用较为底层的编程范式照样可以完成绝大部分任务，但却低估了软件的运行效率和经济效益等重要因素。因此Floyd认为，编程技术得以持续进步的重要前提即是新范式的发明、阐释和交流。

编程范式的概念组成(Conceptual Composition of Programming Paradigms)

任何一种编程范式都可以被看作是由一组编程概念(Programming concepts)，通过组装内核语言(Kernel language)而形成[PVR04]。从数量上看，编程语言要比编程范式种类更多，编程概念则较少，假设存在n种概念，则理论上可以有2ⁿ种范式。下面以一些重要的编程概念为例：

• 变量(Variables)，通常由标识符(Identifier)和存储变量(Store variable)组成，前者相当于变量的名字，后者则是变量在内存中的实际位置。一个变量需要使用声明语句加以创建，例如：

1
2

declare
V=9999*9999

这里declare语句的作用相当于执行创建标识符和存储变量两个任务。

• 函数(Functions)。函数由标识符、参数列表和函数体组成，标识符的作用与变量一致，参数列表规定函数的输入，而函数体用于容纳一段程序代码，例如：

1
2
3
4

declare
fun {Fact N}
if N==0 then 1 else N*{Fact N-1} end
end

在该例中，Fact函数接受参数N，并且计算并返回N的阶乘。值得注意的是，函数体中的代码包含了条件表达式，以及对应于阶乘数学定义的递归表达式。递归使函数具有相对复杂的数学表达能力，例如求解组合数函数：

1
2
3
4

declare
fun {Comb N K}
{Fact N} div ({Fact K}*{Fact N-K})
end

尽管该函数体只有一条语句，但精确反映了组合数的数学定义。但需要注意，Comb函数本身需要依赖之前定义的Fact函数，这种使用已有函数组成新函数的形式，被称作函数抽象(Functional abstraction)。

• 表(Lists)。当参与计算的数达到一定数量，就需要一个方便的方式表示数的集合了。例如计算杨辉三角( Pascal’s triangle)，其实质是对组合数在自然数序列上的枚举，即“从n中取k个数”，其中n为自然数序列，k则是从0到n范围内的自然数，在杨辉三角中n表示三角形的行数，而k表示为列数。那么为了保存该问题中的数列，就需要引出表的定义：

1

T=[5, 6, 7, 8]

表实际上是一条由连接构成的链，其中每个连接由两部分组成：表元素和剩余链部分的引用。Lisp语言使用cons函数动态地在表中创建新的连接，类似地这里用H|T表示cons，例如：

1
2
3

H=4
T=[5, 6, 7, 8]
M=H|T

该例中M的值为[4, 5, 6, 7, 8]。反过来，也可以在一个表中实现逆cons操作，例如：

1
2
3

L=[5 6 7 8]
{Browse L.1}
{Browse L.2}

这里L.1输出5，L.2输出为6, 7, 8。

表通常支持模式匹配(Pattern matching)操作，目的是更方便对表进行分解，例如该例中的case指令：

1
2
3

declare
L=[5 6 7 8]
case L of H|T then {Browse H} {Browse T} end

这里case通过指定一种cons模式对表L进行分解，并使用H和T两个局部变量保存分解后的值，该局部变量的作用域仅限于case语句的then..end代码块内。

• 基于表的函数应用(Functions over lists)

现在设计函数计算杨辉三角，计算原理是，对于第n行数列，分别将其左移一位和右移一位生成两个新的数列(末端补0)，然后将两列相加，即得到第n+1行数列。下面用自上而下法编程解决该问题。

1
2
3
4
5
6
7

declare Pascal AddList ShiftLeft ShiftRight
fun {Pascal N}
  if N==1 then [1]
  else
      {AddList {ShiftLeft {Pascal N-1}} {ShiftRight {Pascal N-1}}}
  end
end

该函数在最顶端模拟了前述文字描述的算法，其余函数可分别表示为：

1
2
3
4
5

fun {ShiftLeft L}
  case L of H|T then
  H|{ShiftLeft T}
  else [0] end
end

1

fun {ShiftRight L} 0|L end

1
2
3
4
5
6
7

fun {AddList L1 L2}
  case L1 of H1|T1 then
      case L2 of H2|T2 then
          H1+H2|{AddList T1 T2}
      end
  else nil end
end

可以看出，当程序引入了函数和表操作时，其复杂度也相应增加。那么应如何判别该程序的正确性呢？

• 正确性(Correctness)。程序的正确性验证是一个非常复杂的问题，因为它不仅涉及编写的程序本身，还依赖对编译器、运行时系统、操作系统、硬件环境乃至其它物理因素的正确性验证。因此对程序的正确性验证首先要确定一个合理范围，并假设范围之外的部分是可信的，例如要验证前面计算阶乘的代码片段，通常需要经过以下步骤：1. 建立对应编程语言中各种操作的数学模型，称作语义模型。2. 定义程序的行为，通常是对程序输入和输出的数学定义，称作程序的规格说明。3. 基于1的语义模型，借助数学方法推导程序的运行结果，从而证明程序符合2定义的规格说明。

• 复杂度(Complexity)。这里主要指时间复杂度。观察前面给出的Pascal函数，{Pascal N-1}在函数体中出现了两次，由于其递归的特性，最终计算量将正比于2ⁿ，从而当输入稍大时就会导致很长的运行时间。为了提高程序运行效率，可以消除一次{Pascal N-1}的计算，所以有：

1
2
3
4
5
6
7

fun {FastPascal N}
  if N==1 then [1]
  else L in
      L={FastPascal N-1}
      {AddList {ShiftLeft L} {ShiftRight L}}
  end
end

改进后的程序时间复杂度达到了n²的多项式时间，从而远好于之前的指数时间。理想状态的时间复杂度应尽量满足低阶多项式时间。

• 懒求值(Lazy evaluation)。一般而言被直接调用的函数会立即被计算，这种模式被称作及早求值(Eager evaluation)，与之相反则被称作懒求值。在懒求值下，计算只会在其结果被需要时发生。懒求值对于程序代码的优化有一定意义，如下例：

1
2
3

fun lazy {Ints N}
  N|{Ints N+1}
end

如果Ints函数是及早求值，那么调用该函数会直接进入死循环，直到调用栈溢出，但懒求值则不会。例如：

1
2

L={Ints 0}
case L of A|B|C|_ then {Browse A+B+C} end

该例只会导致Ints被执行三次，模式匹配中抽出的A、B、C将等于列表中的前三个数。与及早求值相比，懒求值其实意味了对程序的更多控制权，避免像普通的递归函数一样过早进行了大量计算。

• 高阶编程(Higher-order programming)。如果需要计算一个杨辉三角的变种，例如每行数列的获取不是通过对上一行的数做加法，而是改用减法、异或等算术表达式，那么最直观的方法就是对Pascal程序进行改造，特别是替换FastPascal函数中的AddList为新的函数调用。这就导致FastPascal函数可能需要频繁修改，甚至重复才能满足不同类型的计算需求。高阶编程允许将函数作为另一个函数调用的参数，从而满足统一的代码实现：

1
2
3
4
5
6
7

fun {GenericPascal Op N}
  if N==1 then [1]
  else L in
      L={GenericPascal Op N-1}
      {OpList Op {ShiftLeft L} {ShiftRight L}}
  end
end

GenericPascal就是理想的统一代码实现，允许通过Op传递所需的计算函数，避免了计算功能需要扩展时再次发生修改的可能。

• 并发(Concurrency)。真实世界中存在大量相互独立、且根据自身情况决定执行节奏的活动，这被称为“并发”。除非程序建立了通信机制，否则并发的活动相互间不会发生干涉。程序中的并发通常借助线程实现，如下例所示：

1
2
3
4

thread P in
  P={Pascal 30}
  {Browse P}
end

当线程代码开始运行时，尽管Pascal函数的执行需要较长时间，但程序本身依然会继续向下执行。

• 数据流(Dataflow)。如果某个操作引用了一个尚无法被绑定的变量，例如在并发编程中，该变量正在被另一个线程所绑定，那么理想的行为是请求绑定的一方陷入阻塞，直到获得该变量的绑定，这被称为数据流。例如：

1
2
3

declare X in
thread {Delay 10000} X=99 end
{Browse start} {Browse X*X}

上例中X*X会发生阻塞，直到X被主线程绑定。

• 显式状态(Explicit state)。与并发类似，真实世界中也会存在某种行为依赖于历史记录的情况，这就需要程序语言的函数具有维持内部状态的能力，大多数情况下我们把这种状态保存在变量中，这里使用内存单元(Memory cell)表示，以便和前文同样提到的变量概念进行区分。下例显示了如何在FastPascal中引入显式状态：

1
2
3
4
5
6

declare
C={NewCell 0}
fun {FastPascal N}
C:=@C+1
{GenericPascal Add N}
end

• 对象(Objects)。对象即带有内部状态的函数，一个包含多个函数的对象例子如下：

1
2
3
4
5
6
7
8
9
10
11

declare
  local C in
  C={NewCell 0}
  fun {Bump}
    C:=@C+1
    @C
  end
  fun {Read}
    @C
  end
end

本例中local..end定义了变量C的作用域范围，也就是说C对local..end定义的代码范围之外的部分不可见，即封装(Encapsulation)。封装意味着隔离了对象状态与程序的其它部分，从而具有了信息隐藏的特性。此外，该对象还包含两个方法：Bump和Read实现对其状态的操作，即对象的接口(Interface)。一旦对象的接口能维持一致，那么客户程序就无需了解对象具体的方法实现，并能够直接调用任何具有相同接口的对象方法，这种特性即多态(Polymorphism)。在封装和多态背后，针对接口与其实现的分离即数据抽象(Data abstraction)的实质。

• 类(Classes)。对象极大提升了程序的可复用性和可维护性，那么如果程序中需要超过一个对象呢？一种解决办法就是创建一个“工厂对象”，将其用于生产更多的对象，这个工厂对象即类(Class)。下例演示了如何利用函数创建类：

1
2
3
4
5
6
7
8
9
10
11
12
13

declare
fun {NewCounter}
C Bump Read in
  C={NewCell 0}
  fun {Bump}
    C:=@C+1
    @C
  end
  fun {Read}
      @C
  end
  counter(bump:Bump read:Read)
end

该例中NewCounter函数每次调用都能返回一个具有独立内部状态以及Bump和Read函数的新函数(对象)，即利用了前文提到的高阶编程的概念。对类的使用如下所示：

1
2
3

declare
Ctr1={NewCounter}
Ctr2={NewCounter}

其中Ctr1和Ctr2相当于独立的对象，程序进而可以通过.操作符调用其中的方法，例如：

1

{Browse {Ctr1.bump}}

值得注意的是，截至目前我们介绍了类和对象的概念，但这并非面向对象编程(Object oriented programming)的全部，也不意味着使用类和对象的编程概念就可以被称为“面向对象语言”。

• 非确定性和时间(Nondeterminism and time)。当程序具有并发和状态等概念时，问题就会变得更加复杂，这是因为并发所引起的线程时序是非确定的，而状态的改变也会因此变得不稳定。这里需要强调，非确定性本身不会带来问题，只有当程序中的非确定性具有可观测性时，进而引发的竞争条件才会导致潜在问题。

1
2
3
4
5
6
7
8

declare
C={NewCell 0}
thread
  C:=1
end
thread
  C:=2
end

在本例中，从字面上无法判断出在某个时刻变量C的值，即所谓的可观测非确定性。在这种情况下，程序的线程之间会因为交叉存取(Interleaving)问题而变得极不稳定，因此避免和限制交叉存取是保证高质量程序的重要经验之一。

• 原子性(Atomicity)。解决交叉存取问题的途径之一就是引入原子操作(Atomic operation)。原子性意味着任何中间状态都无法被观测，即从初始态直接跳跃至最终态。原子操作的实现方法之一即引入锁(Lock)对象，锁保证了在任何时刻只有一个线程在其中执行，此时其它线程只能在锁外等待。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

declare
C={NewCell 0}
L={NewLock}
thread
  lock L then I in
    I=@C
    C:=I+1
  end
end
thread
  lock L then J in
    J=@C
    C:=J+1
  end
end

锁的使用一般包含两步操作：1.创建锁对象；2.使用锁对象加锁并执行目标代码。代码运行结束后锁对象被立即释放，后续线程可以继续对该对象加锁。

编程范式的分类(Taxonomy of Programming Paradigms)

由于概念——范式——语言之间的组合构成关系，理论上说出于更上层次范式和语言的数量相比较于编程概念而言是十分巨大的。然而在多数情况下，实用的范式应当是图灵完备的。例如函数式编程，基于头等函数(First-class function)或闭包(Clusure)的概念，因此其相当于和λ算子等价，从而可以被证明图灵完备。下面讨论由基本编程概念组合而成的编程范式类别，这种分类法覆盖了绝大多数的实用编程范式(在[PVR04]中也被称作计算模型)。

声明式模型(Declarative model)

作为最早出现也是最简单的编程范式类别，声明式是指通过定义数学函数实现编程，从而使其最易被推导和测试，也是所有其它类别的编程范式的基础。

声明式编程首先定义了语法(Syntax)和语义(Semantics)的概念，其中语法用于规定合法的语言形式，由于编程不可能像自然语言完全一样灵活自由，因此通常具有极为限定的语法形式和约束。一种常用的语法标记即扩展巴科斯范式(Extended Backus-Naur Form, EBNF)，其基本形式是从非终结符开始，由左向右列出记号(Token)序列，其中任何遇到的终结符可以被直接加入序列，而非终结符则需要被它的展开式替换，并在选择项(Choice)前任选一个作为替换。上述这种语法定义形式被称为上下文无关文法(Context-free grammars)，因为其非终结符在任何情况下的展开都是唯一确定的。须知上下文无关文法是可能会存在歧义的，例如：

1
2

<exp> ::= <int>|<exp> <op> <exp>
<op> ::= + | *

对于表达式2 * 3 + 4来说，其解析树存在两种可能，一种的叶结点是2 * 3和4，另一种的叶结点是2和3 + 4。为了消除这种歧义性，编程语言层面会定义更多约束以保证确定性：例如确定运算符优先级或者定义计算表达式的默认方向。

在语义方面，无论现代编程语言被设计得多复杂，其底层一定是基于一个纯数学的、易于推导的模型，这种模型被称作内核语言。实际上，本文所讨论的编程范式，就是通过定义内核语言形成对编程语言的语义化翻译，进而更容易被机器或操作系统所识别。

声明式编程有时也被称为无状态式编程，也即以下两种编程范式的核心思想——函数式编程(Functional programming，例如Scheme和Standard ML)和逻辑式编程(Logic programming，例如Prolog)。以该范式为基础为编程语言构建了庞大的特性集合，例如大部分常用的语法规则、编译技术、内存管理技术和异常管理技术等，都超出了本文的主题。

并发声明式模型(Concurrent declarative model)

该范式在声明式编程的基础上引入并发的概念。在本文的编程概念部分就已经讨论过，并发本身并不显著提高复杂度，只有并发和状态同时存在时问题才可能会出现，即前文提到的可观测非确定性问题。并发声明式的主要特点在于数据流概念的引入，既保留了声明式编程的基本特征，也允许更加灵活的增量执行属性，且避免引入可观测非确定性。

一般的声明式编程都是按照语句的出现顺序、由左至右依次执行，这种执行方式即所谓的及早求值或数据驱动求值(Data driven evaluation)。在某些应用场景中，及早求值并非最佳方案。例如在同时包含生产者和消费者的程序中，传统的及早求值要求生产者确定是否已经发送了完整的数据，而如果由消费者来负责就能进一步保证处理后的数据完整性，后者就采用了懒求值的思想，也被称作需求驱动求值(Demand driven evaluation)。在声明式编程中引入懒求值的特性，即懒声明式模型(Lazy declarative model)。该范式允许在某些潜在的无限制数据结构基础上实现编程，更有利于资源管理和程序结构的模块化。

懒求值最早是在函数式编程中被发现，最初仅被视为声明式编程的一种执行策略，可用于帮助设计具有良好平摊性或最坏时间上界的算法；后来被进一步应用于包含声明式子集且更具表达性的范式中，强化其模块化特性。采用懒求值的例子包括Haskell和Miranda。

消息传递并发式模型(Message-passing concurrent model)

由于前文所描述的并发声明式编程不具备可观测非确定性，使其在描述能力上有所限制。例如经典的C/S系统，任何时刻服务器都无法预知客户端发来的下一条消息，而这在并发声明式编程中就无法实现。而消息传递并发式编程则在前者的基础上引入了一个异步通信信道，任何程序中的实体都能从该信道中写入和读取消息，从而满足了可观测非确定性编程的需求。该范式创建了一个具有关联流的信道——端口(Port)。任何实体可以向该端口发送消息，一个具体的作法是创建一个流对象并将其和对应端口相关联，这里称其为端口对象。于是，实体就可以通过该端口对象对其它端口对象发送和接收消息。一个端口对象通常是一个声明式的递归过程，从而使其拥有声明式编程的一部分特性。

采用消息传递并发式的例子包括Actor模型和Erlang。

状态式模型(Stateful model)

状态式编程，也称命令式编程(Imperative programming)。本质上状态式相当于声明式+显式状态的组合，这里的显式状态是指某个过程调用依赖于超出该过程生命周期的状态，且该状态没有出现在过程的调用参数列表中。状态式编程增强了范式的抽象能力，这种能力被视为构建复杂系统的关键。以传统的无状态编程为例，尽管程序中的一个过程可以根据外界传递的参数做出对应的行为，但这始终是针对特定输入而产生确定性结果。而对于状态式编程而言，其自身拥有了更多能力从而变得相对较“智能”，这也更接近对真实世界活动的模拟。

范式的抽象能力可以通过以下特性衡量：1.封装性；2.组合性；3.可实例化和可调用性。其中，封装性的意义在于，我们知道程序的可推导性能够保证其正确性，但显式状态的引入会使得程序推导变得十分困难，一个例子是带有边际效应(Side effect)的函数。而封装性的提高可以降低状态带来的不利影响，特别是维持不变量(Invariant)，这在一定程度上提高可推导性。

状态式编程能够描述出行为依据状态而发生变化的程序，从而进一步有利于模块化程序，且如果封装和不变量使用得当，则其会拥有与声明式编程相当的可推导能力。

在状态式编程的基础上，采用一组交互式数据抽象的集合描述最终程序，即面向对象式模型(Object oriented model)。这里的数据抽象具有状态化和对象化二元特性。状态化意味着模块化能力，而对象化则进一步启发了多态和继承——这就是面向对象编程的基本原理。多态允许更细粒度的模块化，在合理的职责划分下依旧能保证统一接口；而继承则开辟了增量式的抽象构建，使程序模块易于复用，从而降低潜在的开发成本。

在最近40年里，面向对象编程在工业界和学术界都得到了深入研究和广泛应用，并且在绝大多数现代编程语言中都得到了支持。

共享状态并发式模型(Shared-state concurrent model)

与消息传递并发式类似，共享状态并发式也提供了可观测非确定性编程的能力，区别在于后者借助了共享且可变的显式状态（这里称作单元）而非异步通信信道来实现。尽管实质上都是状态化，但共享状态并发式编程较前者具有更加复杂的实现。

前文已经提到，并发声明式编程不具备可观测非确定性，这点其实兼有利弊，特别是无法实现完全独立的并发线程，或是超过两条线程以上的通信，这也是状态化并发编程的主要目的。但是为了应对随之而来的即交叉存取问题，除了异步消息信道外，还可以通过引入锁、监控和事务等实现针对共享状态单元的原子操作，这些解决方案适用于不同的问题。

事实上，共享状态并发式编程在绝大多数语言中都得到了支持，这主要得益于状态式编程（特别是面向对象编程）的广泛应用。颇为讽刺的是，尽管这种范式可能受到了更加彻底的研究，但建立在其基础上的应用程序至今仍面临复杂且严峻的挑战。

关系式模型(Relational model)

声明式编程的基本特性源于数学计算，包括过程、输入参数、输出参数等概念。当一个给定输入参数集合仅有一组输出参数集合时，同样可以用关系式编程实现。后者比声明式具有更高的灵活性：1.允许有0至多个结果；2.输入参数和输入参数可以在每次调用时都不同。从而令关系式编程在数据库、歧义性语法解析和复杂组合问题的枚举实现等领域具有一定优势。

具体实现上，关系式在声明式基础上引入了选择(Choice)语句，这种选择语句能够通过搜索自由抽取出一个结果集，虽然算法是确定的，但最终结果仍然是非确定。Prolog的search特性就是基于这种范式的逻辑式编程语言。

编程范式的比较(Comparison of Programming Paradigms)

编程范式对软件工程的意义在于满足天然性(Natural)和高效性(Efficient)。天然性意味着相关程序使用了尽可能少的、与问题本身不相干的代码，例如某些纯技术原因导致的代码。一般采用模块化、非确定性和对接真实世界来衡量范式的天然性。高效性则意味着程序与解决同一问题的嵌入式编程只存在常数级差别。由于通常无法同时兼顾这两种属性，于是它们就成为衡量编程范式的重要工具。

声明式编程的简洁和可推导性，使得程序较易于保证正确性，尽管多数时候由于不可变(Immutable)数据类型而需要为计算结果开辟新空间，但这引来的性能损耗在真实场景中几乎可以忽略不计，因此总体上说声明式编程具有高效性。但在满足天然性方面，朴素的声明式编程首先并不具备模块化特性，除非向其注入显式状态；其次，虽然声明式编程支持并发，但由于本身不支持状态，从而不具备可观测非确定性；由于前两者不满足，声明式编程也就不具备对接真实世界的特性。因此可以认为声明式编程并不具备良好的天然性。

状态式编程一般要求程序采用顺序执行，但真实世界的实体通常既是状态的也是平行的，这就需要引入并发来解决这一问题，即增加可观测非确定性。另一方面，在分布式环境中，状态的存储也面临一致性和效率问题，于是导致了一套复杂的一致性等级和协调算法解决方案，极大提升了状态式编程在解决分布式问题中的复杂度。这些问题对面向对象编程同样适用，而对后者而言，其相较于其它范式显然更符合天然性要求，这也是其流行至今的原因之一。

在并发编程方面，并发声明式作为基于数据流的、最简单的并发编程范式，无疑是实现确定性并发编程的最佳工具；真实世界中更多时候面临着可观测非确定性问题的挑战，于是推动了消息传递和共享状态两种应对方案的出现。对于消息传递并发式来说，程序描述了一批相互协调的活动实体，更加适用于多代理场景，例如通信；而对于共享状态并发式来说，程序描述了一批实现一致性修改的数据仓库，适用于以数据为中心的计算场景。而事实上，这两种范式在真实的软件工程实践中是可以并存使用的。

结论

编程范式用于描述编程活动中的风格和方法论，该问题是软件设计和实现的共同基础。本文首先介绍了编程范式的基本组成和重要的编程概念，并在此基础上进一步介绍了一种编程范式分类法[PVR04]，并在此基础上对不同类型的编程范式进行了比较。了解这种分类法能够便于理解编程语言的动机和设计原理，并且掌握语言发展的历史、现状和趋势，从而为进一步构建得以实用的软件设计提供更好的理论和技术储备。

引用

[RWF79], The Paradigms of Programming

[TSK62], The Structure of Scientific Revolutions

[PVR04], Concepts, Techniques, and Models of Computer Programming