Wing of Dream 梦境之翼

面向对象——概念与建模

由前文编程范式我们知道，对象作为最基础的编程概念广泛存在于各类编程范式中，采用这种范式的语言被称为基于对象语言(Object based language)。本文讨论的面向对象(Object oriented)的概念则首次出现在1967年诞生的Simula 67，其中除了对象概念本身外，还进一步提出了继承和多态这两个重要特性，成为此后长期影响学术界的语言之一。而面向对象在工业界的兴起则始于上世纪80年代，以Smalltalk和C++的相继发明为标志，深刻影响了此后近四十年的软件工程。

基本概念

继承是区分面向对象和基于对象的重要特征，大部分面向对象语言的继承是采用类(Class)实现的(注意“类”和“对象”是完全不同的编程概念)。我们知道类可被看作是能够创建对象的工厂对象，继承则允许增量式地进行对象扩展。因此，类作为数据抽象的核心，在其基础上实现继承就自然地支持增量式的数据抽象。除了类之外，面向对象还支持一种基于原型(Prototype)的特殊实现，后者通常并不包含类定义，任何对象都能够唯一地指定另一个对象作为其原型，其中对象的属性和事件沿原型链传递查找，从而实现继承。从支持增量式对象扩展的角度看，类继承和原型继承没有本质区别。下面讨论在面向对象语境下的一些重要概念。

• 类。类是一个可能同时包含部分具体实现的抽象数据类型[BMR97]，其被用于描述一组存在于内存中且可直接被用于计算的实例。类的特点在于其同时扮演了模块和类型两种角色。其中模块作为一种语法概念，通常被用于表示软件分解单元，而类型则被用于动态对象的静态描述，相当于一种语义概念。在非面向对象模式中，上述两种概念通常是被分开表示的。

在某些面向对象系统中(例如Smalltalk和Ruby)，类自身也可能是通过对象实现的，这种实例依然是其本身的类被称作元类(Metaclass)，面向对象语言或编程环境的作者可以利用元类方便地实现某些动态扩展特性，例如Ruby的单例类。

• 对象。对象是指某个类的运行时实例[BMR97]。

虽然“对象”一词最初来源于对真实世界物体的描述，但在实际编程场景中对象已经不仅仅被用于描述真实物体，例如用于描述一组配置属性等因技术需求而诞生的对象。对象是通过引用(Reference)进行表示的，并且可以被自身或其它对象引用。一个对象引用唯一地指向了该对象唯一且不变的标识(Identity)。对象标识是用于区分不同对象的唯一凭证。

对象的创建过程通常是在面向对象系统中默认定义的，一般包括分配内存空间和初始化两个步骤，前者由系统自身负责，后者允许在程序中自定义初始化过程。以Java的面向对象系统为例，类支持以构造函数(Constructor)定义初始化过程，如果某个类没有包含显式的构造函数，编译器会自动加入一个默认的无参构造函数并在其中调用父类的无参构造函数。

• 组合与聚合。如果采用引用表示对象，那么对象之间就可以通过引用产生关联(Association)。但是仅使用引用不足以描述对象间真实的关系特征，从而无法满足忠实建模(Faithful modeling)。组合(Composition)关系是指一个对象包含了另一个对象的值，这种关系超过了一般引用的定义，特别是指被包含对象的生命周期被限制在其父对象内。聚合(Aggregation)关系指一个对象由另外多个对象组成，其组成关系通过引用实现。与组合的区别在于，聚合中被包含对象的生命周期不受父对象限制。

从面向对象中对关系分类的角度看，组合与聚合可以统一被看作客户(Client)关系，其实质是对对象间关系的描述。

• 继承。继承描述了一种类之间的扩展关系。在面向对象中，类本身具备良好的模块化特性，从而能够满足信息隐藏的原则，但模块化并不直接提供增量式设计和开发的途径。继承支持了类之间的扩展、特化和组成关系，显著增强了面向对象的可重用性和可扩展性。其中包括四个重要的衍生概念:

  • 重定义(Redefinition)，指子类能够重新实现父类中定义的过程，有时也称作覆盖(Override)。
  • 多态(Polymorphism)，指一个变量实体或数据结构元素，在具备可控静态声明的前提下能够在运行时阶段绑定至不同类型的对象。例如当类A继承类B，那么类A的对象a，可以被赋于类型为B的变量b，且并不违反类型检查。
  • 静态类型(Static typing)，前面提到多态的前提是具备“可控静态声明”，具体是指对于一个变量的声明类型(也称变量的静态类型)，尽管允许其被赋予不同类型(也称变量的动态类型)，但其动态类型必须是静态类型的后代(后代定义包含其自身)。
  • 动态绑定(Dynamic binding)，是指变量所指向对象的动态类型决定被调用操作的具体位置。

本质上，继承同时包含了两个角色且互有重叠:模块和类型。从模块的角度看，继承提供了一种有效的可重用特性。这里提到的有效是指当类A继承类B时，A就立即拥有了B的全部特性，且无须进行任何改动。从类型的角度看，继承同时增强了可重用性和可扩展性，这主要体现在: 1.对于类Rectangle继承类Polygon，即Rectangle的全部实例同时也是Polygon全部实例的子集。2.对于类A继承类B，那么B的任意实例所具有的操作也同时存在于A。在许多文献中，继承也被称作is-a关系。

• 多重继承。在真实世界中，对象可能同时包含了不同领域的抽象，对应在面向对象中就是多重继承，即一个类可以同时拥有多个父类。例如，类Teacher和类Student都继承了类UniversityPerson，这时需要一个类TeachingAssistant且同时继承自类Teacher和类Student，也就是说通过两个父类间接继承了类UniversityPerson，即重复继承。重复继承可能会造成一定的函数访问冲突，特别是当调用类TeachingAssistant的对象的name函数，而其实际上位于类UniversityPerson时，系统就面临多重函数查找路径的问题。而由此引发的复杂性使得多重继承在许多现代面向对象实践中被认为弊大于利，且不被推荐使用。但不可否认，多重继承实际上体现了真实世界原本的复杂性。

在支持多重继承的面向对象系统中，通常采用复制(Replication)和共享(Sharing)两个策略解决前述重复继承问题。复制是指当遇到重复继承时，子类实际上包含了所有继承路径上属性和函数的副本，程序这时需要具体指定被调用副本的名称。共享是指程序可以指定在子类中只保留一份来自祖先的副本，这样就避免了名字冲突的问题，例如C++的虚继承(Virtual inheritance)。

许多现代面向对象语言不支持多重继承，但同时为了保留一定的设计能力大多采用了折衷方案，例如Java的接口(Interface)、Ruby的混入(Mixin)等。

• 泛型。继承本质上体现了一种纵向的层级扩展关系，由上至下可以被看作是面向对象从抽象化到特化。而泛型(Genericity)则支持横向的同级扩展关系，即类型参数化。

泛型最经典的案例就是编程语言标准库中常见的容器类，例如Set、List、Map等，这些容器类实际上是参数化的抽象数据类型，其本身包含了抽象数据类型中的具体操作，并藉由客户代码通过指定参数决定具体的元素类型。由于历史的原因，许多现代编程语言中虽然提供了泛型特性，但其实现原理差别巨大。例如C++的模板能完整地重新编译目标代码，最终根据模板参数生成不同的函数和类；而Java的泛型实际上是一种为了增强代码类型安全的语法特性，编译器对泛型语法进行类型检查，并最终通过类型擦除(Type erasure)生成无类型参数的目标代码；C#的泛型实现则介于C++的灵活和Java的简易之间，通过运行时实化(Reification)进行类型检查和具体操作，从而避免了类型擦除的缺点(例如无法实现泛型数组)，同时把类型参数保留在运行时，从而满足在泛型条件下支持反射。

面向对象建模(Object Oriented Modeling)

从上世纪80年代起，随着工业界对面向对象语言从逐渐认识到深入实践，面向对象开始代替传统的结构化方法成为主宰范式。但是，基于面向对象的软件开发很快就面临了更多数量的对象以及更加复杂的关系，实现系统设计也变得空前复杂。作为OO的早期布道者之一，Grady Booch等分别在面向对象的基本概念基础上发展出了一系列全新的建模方法，被统称为面向对象建模。

统一建模语言(Unified Modeling Language, UML)

1997年，Three amigos在Grady Booch的Booch method、James Rumbaugh的Object modeling technique(OMT)以及Ivar Jacobson的Object oriented software engineering(OOSE)的基础上，正式发布了UML 1.1。UML是一种编程语言无关的通用建模技术，旨在采用统一语言对复杂问题的不同关注点进行建模。

UML由图形标记(Graphical notations)和元模型(Meta-model)组成。其中图形标记定义了相关概念的图形表示法，也是UML建模的主要工具。元模型是一种对UML模型的形式化表示方法，用于对UML规格说明的精确表达。后者常被用于构建基于UML的计算机辅助软件工程(Computer Aided Software Engineering, CASE)系统。这里只讨论UML的图形标记方法。

下图展示了UML 2.5.1的图形标记分类[UML17]。其中结构图(Structure diagrams)用于代表系统中对象的静态结构，通常能够表示系统的核心概念及行为定义，但并不包括行为的动态细节。行为图(Behavior diagrams)表示系统中的动态行为，包括方法、协作、活动和状态历史记录等。

随着UML被纳入国际标准，其复杂度不断增加，即使由对象管理组织(Object Management Group, OMG)定义的狭义UML规范也已经十分臃肿，使其逐渐脱离了日常的软件设计实践。但不可否认，UML的核心内容依然在面向对象建模中占据权威地位。为了保证UML的实用性，本文接下来只讨论核心的图形标记[MFR03]。

• 类图(Class diagrams)，表示系统中的对象类型及其相互之间的静态关系。如下图所示:

在上图中，每个方框表示类的属性和操作，方框间的实线表示类的相互关系，在每种关系上还标记了两个类之间的多重关系(Multiplicity)。关系是UML中最复杂的概念之一，甚至允许通过构造型(Stereotype)对关系进一步扩充。UML的基本关系种类包括：1. 关联(Association)，指类之间的持续性关系，例如类的属性类型，关联采用实线表示，并且可以是无向、单向和双向，带方向的关联进一步揭示了源类中包含以目标类作为类型的属性；2. 依赖(Dependency)，指一个元素(Supplier)的变更可能引起另一个元素(Client)的变更，依赖采用单向的虚线表示；3. 泛化(Generalization)，表示类之间的类型层级关系，例如继承采用带三角箭头的实线表示，如果目标类是接口类，那么采用带三角箭头的虚线表示，抽象类需要额外使用斜体表示。

从上述关系的定义来看，依赖是含义最广泛的关系，也是面向对象建模中需要仔细考虑的问题。过多的依赖路径会导致修改时发生涟漪效应(Ripple effect)，从而降低系统的可维护性。关联进一步包含了前文讨论的组合和聚合关系，其中组合使用一端实心菱形和单向箭头的实线表示，聚合采用一端空心菱形和单向箭头的实线表示，分别如下图所示:

UML中的大部分工具实质上都是为了设置约束，但仅通过图形标记无法表示所有类型的约束，因此UML支持使用{}表示自定义的约束。自定义约束的具体形式没有严格限定，可以是自然语言、伪代码，也可以采用对象约束语言(Object constraint language, OCL)。

• 对象图(Object diagrams)，是指系统在某个时间点的对象快照，也被称作实例图。虽然类图能够完整表达对象的结构信息，但有时候并不容易理解，对象图能够以某个真实案例对前者进行补充。如下图所示:

• 包图(Package diagrams)，指一组类或嵌套包的集合。包也被称作命名空间(Namespace)，其作用是定义比类层次更高的系统结构。包图在UML中使用带标签名的方框表示，包之间也可以定义类似类图中关系。如下图所示:

• 部署图(Deployment diagrams)，指系统的物理结构，特别是软件及其所运行的硬件框架。如下图所示:

• 组合结构图(Composite diagrams)，指对一个类的内部结构进行层级表示，从而使其更容易被理解。以类TV Viewer为例，下面是TV Viewer的类图:

如果用组合结构图进一步描述TV Viewer，则如下图所示:

• 组件图(Component diagrams)。在UML中，组件是一种从功能角度上看可以独立分发和升级的模块。组件图用于表示组件之间的交互关系，如下图所示:

• 时序图(Sequence diagrams)，表示一组对象及其之间的协作关系。具体来说，时序图通常限定在一个单独的场景下，包含了一组对象以及依据用例而发生的对象间消息传递，特别是展示了消息发生的顺序信息。如下图所示:

在时序图中，由于第一个消息通常不在参与者(Participants)中，因此也被称作创始消息(Found message)。另外，时序图中的参与者是可以被动态创建和销毁的。同时消息传递过程也支持循环、分支以及异步等特性。

• 状态机图(State machine diagrams)，也称作状态图，表示单个对象的整个生命周期行为。在面向对象中状态具体包括了对象中所有属性值的集合，而状态图则侧重于抽象的状态定义，即提供不同的事件响应方式。一个简单的状态图例子如下:

该状态图表示了一座城堡中的安全机关。图中方框表示一个状态，除了状态名之外，还可以填入状态的内部活动，包括状态事件(Event)、看守(Guard)和活动(Activity)，当某个事件发生时，可根据当前状态选择迁移(Transition)或保持状态不变。更进一步，状态既可以是静止的也可以是活动的，例如当前对象某个正在发生的动作。状态也可以被分组，其作用是表示组内所有子状态的同一个向外部某个超状态(Superstate)迁移的路径。

在并发场景中，单个状态可以被分割成几个正交的子状态图，一个闹钟的例子如下图所示:

该图中用一个历史伪状态标记代替了初始状态标记，意味着当开关打开时，初始状态应为上一次开关关闭时所处的状态。

值得注意的是，状态图对应着两种可能的实现，一种是采用控制流代码或面向对象实现，另一种是基于状态表的解析和查询。前者具有更加复杂的代码结构，且需要持续维护相关代码；后者需要在初期实现一个较复杂的状态表解析和查询特性，后期则主要集中于状态表的数据维护。无论采用哪一种实现，其最终代码都具有一定的样板特征，因此结合代码生成技术都是更好的选择。

• 活动图(Activity diagrams)，表示过程逻辑的业务流程的行为，且通常是跨多个用例或线程的行为。先看一个活动图的例子:

从上例可以看出，该活动图与传统的流程图十分类似，最主要的区别在于前者支持并发活动，例如分叉(fork)操作可以产生并发的子活动，所有子活动的同步操作通过结合(join)进行。活动图中的动作(Action)之间使用流(Flow)或者边(Edge)进行连接，且可以被进一步分解成更多子活动，如下图所示:

一般而言，活动图更多聚焦于描述业务过程而非实现，但通过分区(Partition)可以进一步表示不同动作的负责对象，如下图所示:

活动图支持基于信号的动作触发场景，信号可以被直接触发并接收，也可以通过定时器触发，如下图所示:

活动图还进一步支持采用动作方框下放置别针(Pin)表示该动作的输入和输出参数，如果某个动作的输出与下一个动作的输入参数不同，还需要使用参数变换(Transformation)使其一致。当一个动作会导致下一个动作触发多次时，可以采用扩展区域(Expansion regions)标记需要响应多次的动作集合，如下图所示:

在该例中，扩展区域中的动作流程可能会部分导致终止，因此采用终止流(Flow final)进行标记。

• 通信图(Communication diagrams)，在UML 1.x中被称作协作图(Collaboration diagram)，用于表示对象交互过程中的数据连接，如下图所示:

通信图所表达的信息与时序图类似，形式相对灵活但不如后者规整，因此其受欢迎程度也不如后者。

• 交互概述图(Interaction overview diagrams)，指结合了活动图和时序图的概述表示。如下图所示:

交互概述图实际上是一种针对对象交互行为的整体表现方案的总结。

• 时间图(Timing diagrams)，表示单个或一组对象交互的时间约束。特别是当对象的某个状态存在一定时间约束时，如下图所示:

• 用例图(Use case diagrams)，表示系统的功能需求。用例(Use case)是一种对用户与系统或系统自身交互的描述。用例更注重用户的一般目标，与用户场景(User scenario)不同，后者详细描述了用户与系统的每一步交互(这里的用户不仅指人类)，如果交互过程中发生分支则产生新的场景。也就是说，一个用例包含了许多用户场景。下图是一个用例图的例子:

用例是对系统功能的更高级描述，与极限编程中的用户故事(User stories)相比，后者侧重于表示系统特性，且可以用于安排迭代计划，而用例则是单纯的系统功能性描述。在具体实践中，一个特性可能直接对应用例，或者用例中的一个步骤，也可能对应于其中一个场景。而大多数情况下用例要比特性具有更粗的粒度。

结论

本文首先讨论了面向对象的核心概念；随着面向对象编程的流行，开发中面临的问题复杂度不断提升，由此催生了面向对象建模技术。UML旨在实现语言无关的通用建模语言，被广泛用于面向对象分析(OOA)和设计(OOD)等活动。另一方面，随着相关国际标准的建立，UML也逐渐变得更加臃肿，因此实践中，视实际情况选择性地对工具进行裁剪就变得尤为重要。

引用

BMR97, Object-Oriented Software Construction

UML17, The unified modeling language specification

MFR03, UML Distilled

编程范式(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

数据模型与数据建模(Data Model and Data Modeling)

信息系统(Information Systems)是人类社会重要的基础应用之一，也是计算机自诞生起最重要的应用领域。在计算机信息系统中，数据(Data)作为信息的主要载体，也是沟通人与硬件系统的桥梁，其复杂性不言而喻。可以说，本文涉及的数据模型与数据建模技术的发展，始终是以弥补人机之间的鸿沟为目标的。

数据模型

在设计信息系统时，为了应对信息的复杂性，人们利用数据模型描述数据元素、元素间关系及其与真实世界实体的映射，从而达成抽象且一致的信息表示。初期的数据模型包括文件系统模型(File System Model)、层级模型(Hierarchical Model)和网络模型(Network Model)等。

文件系统模型利用计算机文件系统模拟制表(Tabulation)，包含一般表格中的字段、记录等概念、且具备顺序和随机访问文件的能力，数据可按文本或二进制类型进行存储。这是一种非常简洁的数据模型，诸如csv、dsv等标准格式至今仍被广泛使用。

层级模型与文件系统模型拥有类似的字段和记录等概念，所不同的是记录之间可以按树形结构进行关联，从而表示记录之间的关系。相比较于文件系统模型，层级模型能够显式表达记录间的连接关系，并允许按照标准的树遍历算法进行数据遍历；缺点在于子记录只能拥有唯一的父记录，反过来则没有限制。发布于1966年的IBM Information Management System(IMS)就是基于层级模型构建。

网络模型旨在克服层级模型对关系限制的缺陷，允许每条记录拥有多个父记录和子记录。从数据模式(Data Schema)的描述上来看，网络模型的对象关系呈现出一个通用的网状结构，从而具有较层级模型更好的表达能力。1969年，数据系统语言委员会(CODASYL)下属的数据仓库任务小组(DBTG)发布了网络模型规范，该规范包括了一种用于定义数据模式的数据定义语言(DDL)，以及能够被嵌入宿主语言的数据操纵语言(DML)，首次提出了独立于宿主语言的数据语言的概念，并且通过国际标准化组织制定了多项标准。但是自诞生后，网络模型并未被工业界和学术界广泛接纳，并在此后十年的竞争中败给更具形式化能力的关系模型(Relational Model)和后续模型。

Edgar F. Codd在1970年提出了关系模型[EFC70]，其包含两个主要内容：

1. 对应于N个数据集合，使用N元关系组表达集合间的关系，使模型具备更精确的数学表达能力。

2. 一种具有强描述能力的全局数据子语言，该语言基于结构化一阶谓词逻辑算子，能够用于表达基于关系模型的数据操作。

关系模型为设计人员提供了统一抽象的界面，很好地隐藏了数据操作与底层系统交互的实现细节。但是也存在一些不足：

1. 根据关系模型的数学定义，集合之间的关系通过维护单独的N元关系组实现，其实质是集合间的笛卡尔积。但是通过这种形式化表示无法进一步揭示笛卡尔积的基数信息，而实践证明这种数量关系在描述数据模型时非常重要。

2. 与问题1类似，关系模型的形式化表达缺乏一定的语义信息，无法进一步揭露关系的实质。尽管这种针对关系的语义信息不是始终必要的，但实践证明语义对数据模型的可表达能力具有重要意义。

为了解决上述问题，Peter Chen进一步发展出了实体-关系模型(ER模型)，后者成为当前数据模型的重要描述工具和行业标准[PPC76]。ER模型包含四个主要概念：实体(Entity)，即现实世界的实例，通常是名词形式；关系(Relationship)，实体间的关联方式，通常是动词形式；类型(Type)，对实体的类别定义，通常是名词形式；角色(Role)，对实体在某个关系下的特殊定义，通常也是名词形式[PPC02]。

ER模型的一个重要技术是实体-关系图(ER Diagram，ER图)，即用图展示前述的概念及其联系，其中方框表示实体的类型；菱形表示关系；圆圈表示实体或关系类型的属性；实体类型关系和实体属性关系上还标注了数量关系。一个典型的ER图如下图所示。

尽管本节介绍的数据模型为数据表达提供了形式化工具，但是在面对复杂系统时，设计人员不可能凭空得出系统终极的数据表示，于是数据建模就成为支撑构建数据模型的重要方法论。

数据建模

实践表明，在软件需求分析起初就需要开始构建数据模型，数据建模应关注数据的需求和实现等特定方面。一般的数据建模过程依次产生下列三种数据模型：

1. 概念数据模型(Conceptual Data Model)，从高层角度描述系统的信息需求，具体包括主要的信息概念及其相互关系。1969年，网络模型之父Charles W. Bachman提出了数据结构图(Data Structure Diagram)[CWB69]，并将其用于描述概念数据模型。

2. 逻辑数据模型(Logical Data Model)，描述信息中领域的具体结构，例如表、列及其关系等。在复杂度较低时，设计人员往往可以跳过概念数据模型，从而直接得出逻辑数据模型。该模型与概念数据模型都是独立于具体的持久化技术（例如通用的数据库管理系统）。

3. 物理数据模型(Physical Data Model)，满足非功能需求的且可立即被实现的数据模型。该模型与存储技术、维护技术和更新/查询场景等因素密切相关。

数据分类

在开始构建数据模型之前，需要首先识别系统需求中的数据分类，从而确定相应的问题范围，并使用相应的数据模型进行建模。实践中存在多种逻辑思维实践以实现前期的数据分析，[DMG08]描述了一种被广泛认可的数据分类方式，把数据按照特性划分为下列六类：

主数据(Master Data)，表示业务需求中出现的人物、地点、事物等信息。

事务性数据(Transactional Data)，表示业务发生时伴随的内部或外部事件或事务，例如发起订单、创建发票、支付等活动。

引用数据(Reference Data)，表示被系统、应用、数据存储、进程、报表乃至事务性或主数据所引用的值或分类模式的集合，例如状态码、名词简写、产品类型等静态数据。

元数据(Metadata)，表示数据本身的数据，方便数据的检索、解释和使用。

历史数据(Historical Data)，表示在某个时刻发生、且不可修改的数据，例如日志。

临时数据(Temporary Data)，表示因为某些技术需求而被临时创建的数据，通常没有独立的业务含义。

值得一提的是，上述分类方法只应被看作一个指导性原则，具体实践时应视上下文灵活调整。在本例中，对应前面提到的三种数据模型，概念数据模型通常考虑主数据和元数据，逻辑数据模型进一步包括了事务性和引用数据，物理数据模型最终实现覆盖全部类型的数据。采用前文提到的ER模型即可对这三种数据模型分别建模。

关系范式

在构建逻辑和物理数据模型时，为了能尽可能降低关系模型中的关系表示所带来的数据冗余，从而加强数据的一致性，关系模型提出了规范化(Normalization)的概念，以对关系表示本身进行约束，并在此后一段时间相继发展出了多种范式。其中常用的范式包括：第一范式(1NF)，即没有多值属性的关系；第二范式(2NF)，即满足第一范式且非主属性不依赖任何候选键的子集；第三范式(3NF)，即在第二范式的基础上不存在传递依赖。虽然规范化对强化数据一致性约束方面有促进作用，但其造成的后果是使许多数据表示被物理隔离，从而在实现数据操作方面引起额外耗费。因此在实际设计数据模型时，规范化设计的采用是和系统的非功能需求(Non-functional requirement)密切相关的。

结论

数据模型是信息系统设计的重要内容，在经历上世纪70年代的激烈竞争后，关系模型因占据理论高位更加受到学术界青睐，最终成就了80年代起通用关系型数据库系统的统治地位。ER模型和ER图因其更具表达能力，从而成为最重要的数据建模工具。数据模型方法领域的先驱Bachman(网络模型)、Codd(关系模型)和Chen(ER模型)也先后因其开创性贡献而获颁图灵奖。

引用

CWB69, Data Structure Diagrams

EFC70, A Relational Model of Data for Large Shared Data Banks

PPC76, The Entity-Relationship Model-Toward a Unified View of Data

PPC02, Entity-Relationship Modeling: Historical Events, Future Trends, and Lessons Learned

DMG08, Executing Data Quality Projects: Ten Steps to Quality Data and Trusted Information

上接软件设计与架构笔记(4)

前文描述的HIPO模型是一个典型的基于结构图的IPO系统设计模型，其基本思想依然是由顶至下，逐步求精。基于经验Larry进一步总结了通用的系统设计准则[SMC74]。

1. 程序结构和问题结构。减少程序变更所造成影响的重要方法之一，就是保证设计结构匹配问题本身的结构。由顶至下的思维模式会天然形成一种层级结构，因此重点在于如何决定设计单元在相同层级，或隶属于不同层级，而关键又在于理解问题本身。

2. 模块控制范围和决策影响范围。控制范围指模块以及归属于该模块的子模块的集合；影响范围指某个设计决策所造成变更的所有模块集合。当设计决策的影响范围尽可能位于该决策所在的模块控制范围之内时，该系统设计就可以被认为是“简洁”的。保持简洁性的方法之一可以是提升某些决策相关的元素的层级；或者把受到相同决策影响，但位于不同控制结构的模块重新划分至相同控制范围。

3. 模块大小。模块的实际大小可被用于描述潜在问题的信号。过小的模块可能缺少功能性绑定，而过大的模块可能涵盖了超过一个功能性绑定。前者可以通过inline的方式消除以减少模块规模，后者由于可理解性和可读性问题需要进行进一步拆分。

4. 错误和文件终止处理。当模块的一部分功能需要通知其调用者发生某件错误时，可通过返回某种错误参数实现，该参数的值最好是二元类型，对于流数据处理的EOF标记也需要进行类似处理。同时这些参数也不应该包含如何处理当前错误的信息，而是由调用者决定。当然，如果模块本身不需要错误标记时，系统设计就更简洁了。

5. 初始化。某些模块由于需要依赖初始化操作，从而可能存在“简洁”但导致“弱绑定”的设计。例如，读模块的access方法可能会遇到“文件未打开”的错误，如果选择将错误信息返回，调用者自然会选择调用open方法然后重新read；但另一种维护“黑盒性”的做法是，在access内部遇到该错误时自动通过open和reread进行恢复，那么调用者就不需要知道“文件未打开”这种错误并且重复进行处理了。

6. 模块选择。消除重复的功能，而非消除重复的代码。如果只是通过抽取的方式简单消除重复代码，那么有可能导致某个变更造成更多的修改。一种识别该问题的方法是，关注那些被其它不同模块调用，以及调用其它不同模块的对象，判断是否存在其子功能与不同的模块集合关联的情况，如果是则意味着存在层级或模块缺失的可能。

7. 隔离软件规格说明。软件设计规格的重要内容就是描述特定的数据类型、记录布局以及索引结构，设计应尽量使其与系统其他模块进行隔离，从而减少规格变更导致的重写。

8. 参数数量。尽量减少模块间调用的参数数量（不只是个数），如果参数中存在一个完整的数据记录，应尽量只传递必要的数据记录，否则也会导致该记录的变更对模块造成潜在影响。

结构化分析(Structured Analysis)

随着软件设计方法论的发展和问题复杂度的增加，人们发现设计不再是解决复杂系统面临的唯一难题。比如，传统的软件设计过程一般是按由顶至下的方法，依照需求规格说明(requirement specification)给出具体的软件对象定义，那么如何构建规范合理的需求规格说明呢？另外，如果软件设计过程愈加复杂，是否可以按照经典的分治法(divide-and-conquer)对其进行分解和简化呢？

世界上存在多种多样的原始需求形态，例如采用文字叙述(narrative)可以说是最普遍的形式之一。当问题复杂度增加时，软件设计已经不能从简单的叙述中加以消化并诞生，于是就出现了需求分析的过程。这种把问题从原始形式转换成可进一步规范设计的规格说明的过程，被称为系统分析。结构化分析作为软件系统分析最早流行起来的方法论，是在早期工业界数十年的探索中发展起来的。

由于传统的文字叙述不足以表达复杂系统，人们开始重视并使用符号语言，例如德国数学家Carl Adam Petri发表于1962年的Petri Net。60年代中期，女数学家Erna Schneider Hoover在贝尔实验室领导了一支团队，其目标是分析电话交换机系统的性能和宕机时间，Erna使用了Petri Net来模拟复杂的电话交换系统。受此启发，同时困扰于晦涩难懂的叙述式规格说明的年轻工程师Tom DeMarco由此开始开发一套网络符号语言，由此发展并最终在1978年发表了结构化分析方法[TOM78]。

结构化分析与传统系统分析

Tom认为传统的系统分析包含如下目标：

1. 确定最优化目标。

2. 生成该目标的细节描述，并且能够被后期的实现过程用于评估该目标是否实现。

3. 生成该目标相关的重要参数预测，包括花费、收益、日程以及性能特性。

4. 得出所有被影响部分之上的项的并发性。

为了达成这些目标，系统分析活动需要涉及用户沟通、撰写规格说明、损耗收益研究、可行性分析以及估算等。然而，这些活动都因高复杂性存在很多问题。针对这些问题，结构化分析进一步拓展了系统分析的目标：

1. 分析的产生物必须是可维护的，特别是针对目标文档(Target Document)。

2. 必须采用有效的分割方法解决大小的问题，摒弃维多利亚小说式的规格说明。

3. 尽可能使用图形表达。

4. 必须区分逻辑和物理设计，并且基于此在分析师和用户之间合理分配职责。

5. 必须在具体实现之前构建逻辑系统模型，使用户熟悉系统特性。

同时，结构化分析描述了一系列可被用于不同分析阶段的工具：数据流程图(Data Flow Diagram, DFD)、数据字典(Data Dictionary)以及逻辑策略表达工具，例如结构化英语(Structured English)、决策表(Decision Tables)以及决策树(Decision Trees)等。

数据流程图

DFD是一种描述相互关联的过程的网络，其作用是帮助分割需求，并在撰写规格说明之前记录这种分割。与普通流程图的区别是，DFD只聚焦在数据流动的过程，因此基本没有任何关于循环或逻辑决策的控制信息。为了举例说明DFD，[TOM78]描述了一个软件咨询公司的自动化管理和运营辅助系统，该系统的功能包含了学员注册、支付、人员管理、课程管理等方面。下图是对该公司的早期运营模型的描述：

该图是一种Logical DFD，图中的输入被称作事务(Transaction)。以其中一条主要路径的部分为例，该路径共描述了5种事务：Cancellations, Enrollments, Payments, Inqueries和Rejects(这里指不属于前4种类型的事务的统称)，以及数据在这些事务间可能的流动关系。此外还有一种包含了系统具体实现信息的DFD，被称作Physical DFD。

DFD有时又被称作气泡图(Bubble Diagram)，原因是其描述数据转换过程的符号——气泡。此外DFD还包含命名向量，用于表示数据路径；直线段，表示文件或数据库；矩形(或称为源/入节点)，表示网络的起点或数据的接收者(通常是当前领域外的人或组织)。

DFD清晰地表达了工具的自然特征——如果DFD存在任何错误，也应当是显而易见、毋庸置疑的，这无疑减少了分析师与用户间产生认知分歧的可能。另一方面，实践证明DFD无论在概念描述或是建模方面都有显著价值。更重要的是，它提供了一种基于功能的系统分割方法，并且描述了不同部分之间的接口。在系统评审中，任何接口或过程的缺失都能够证明当前DFD的缺陷——这比纯粹的数学方式更加直观和有效。

在实际分析活动中通常使用分级数据流程图(Levelled DFD, LDFD)逐步求精分割系统功能。在LDFD中，通常存在3层、有时甚至更多层具有不同功能解析度的DFD。

Level 0，也被称为上下文图，通常仅包含一个气泡——也就是系统总的过程单位以及其它元素。这种图可以被用于和最宽泛的用户进行交流，例如干系人、业务分析员、数据分析员以及程序员。

Level 1，对上下文图的唯一气泡进行细分，将其分解成不同过程单位，以及相关的文件或数据库。

Level 2，进一步对Level 1进行划分，因此需要更多的文字和符号标记。

Level 3+，一般很少出现Level 3+的DFD，原因是这种级别的DFD可能存在过多的细节，从而导致难以沟通、比较和有效建模的问题。

数据字典

数据字典用于追踪和评估系统不同部分之前的接口，是对DFD的一种有效补充。以前面描述的系统DFD为例，过程3和7之间的数据流动Payment-Data，可以用如下公式进一步描述：

Payment-Data = Customer-Name +              
               Customer-Address +
               Invoice-Number +
               Amount-of-Payment

换句话说，Payment-Data包括了该公式右值的所有数据项，且这些数据项需依序且非空。更进一步，数据字典还可能需要对某些数据项进行进一步描述，例如Invoice-Number：

Invoice-Number = State-Code +
                 Customer-Account-Number +
                 Salesman-ID +
                 Sequential-Invoice-Count

与DFD类似，数据字典也是呈现了由顶至下的细分过程。每个DFD应该携带相应的数据字典描述，二者共同组成了系统分析的图形化产生物。

逻辑策略表达

逻辑策略表达用于替代传统冗长的文字叙述式的规格说明。最常见的结构化表达方式被称作结构化英语，例如采用按行缩进的方式表述不同层级的规格说明：

1
2
3
4
5
6
7
8
9
10
11

If the amount of the voice exceeds $500.
    If the account has any invoice more than 60 days overdue.
        hold the confirmation pending resolution of the debt.
    Else (account is in good standing).
        issue confirmation and invoice.
Else (invoice $500 or less).
    If the account has any invoice more than 60 days overdue.
        issue confirmation, invoice and write message on the 
        credit action report.
    Else (account is in good standing).
        issue confirmation and invoice.

使用决策表表达上述规格说明，结果如下：

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

                       RULES
CONDITIONS              1  2  3  4

1.Invoice > $500        Y  N  Y  N
2.Account overdue
by 60+ days             Y  Y  N  N

ACTIONS

1.Issue confirmation    N  Y  Y  Y
2.Issue Invoice         N  Y  Y  Y
3.Msg to C.A.R.         N  Y  N  N

决策树的表达结果如下：

结论

结构化设计为软件设计提供了有效的结构图工具，以及作者Larry富有经验的设计准则，至今仍极具指导意义。为了保证设计阶段能使用清晰有效的规格说明，结构化分析提供了强大的DFD分析工具和规格说明描述工具，尽管其核心依然是逐步求精的设计思想，但已经开始涉足于比编程活动更加宽泛的软件工业领域，最终形成了较为独立的需求工程，成为软件构建过程中不可或缺的环节。

引用

SMC74, Structured design

TOM78, Structured Analysis and System Specification

结构化分析与设计方法(Structured Analysis and Design Methods)

除了指导程序设计，结构化方法还被广泛应用于系统分析和设计领域，成为软件设计方法论的开端。从时间轴来看，从结构化编程到结构化程序设计，再到软件的结构化设计和分析，软件设计的方法论是从底向上发展的，其根本推动力是日益增加的系统复杂性。

结构化设计(Structured Design)

1974年，Larry Constantine等提出了一系列通过降低系统复杂性，从而提高编码、调试、修改等工作效率的软件设计思想，并将其统一命名为结构化设计[SMC74]。通用的结构化设计思想包括简洁性和可观测性，其中，简洁性作为衡量和评估设计方案的主要度量指标，体现在分割后的系统模块间具有设计、开发、更正、修改的独立性；可观测性则体现了软件易被感知功能和原理的能力。尽管系统分割具有良好的工程意义，但其引起的模块间重叠部分代码以及相互关系反而可能会增加复杂性。前文我们已经介绍了信息隐藏这一重要的模块化概念，结构化设计则提出了一个更具实践意义的设计指标：耦合(coupling)。

耦合

通常情况下，更少或更简洁的模块间连接就意味着更好的可理解性，同时变更或出错所引起的模块间传递也会受到抑制。系统复杂度不仅体现在模块间的连接数量，更体现在每个连接所承担的关联强度，这种强度的度量被称作耦合度。强耦合意味着高复杂度，造成模块难以被理解、修改和更正的后果。因此，软件设计可以通过建立模块间的弱耦合降低系统复杂度。

一个特定连接产生的耦合度是一个包含多重因子的函数，这些因子包括连接复杂度、连接指向模块自身亦或其内部、连接所发送或接收的内容等，Larry将其归纳为三个主要的耦合因子：接口复杂度、连接类型和通信类型。耦合度受这三个因子的变化规律如下表所示：

Larry认为，弱耦合应具有接口简单直观，只通过名字引用其它模块，以及尽量仅通过数据进行通信等特征，反之则会增加耦合度。具体来说：

1. 接口复杂度，指模块间接口是否能清晰地表述连接，而不是包含了过多的信息导致难以理解。特别当多个模块通过共享一个公共环境(common environment)实现交互时，该公共环境中任意元素的增加都可能会导致系统整体复杂度的显著提升。例如在M个对象中，存在M(M-1)对相互关系，假设这些对象之间的公共环境包含N个元素，那么就有NM(M-1)对一阶关系，亦即变更或错误传递的可能路径数量。可见接口复杂度对系统整体复杂度的显著影响。

2. 连接类型，指模块间相互关联的形式，例如仅通过模块名字进行关联，还是进一步引用了模块内部的元素。在后一种情况下，该模块内部的修改很可能传递至其它依赖它的模块，导致潜在的复杂度增加。

3. 通信类型，指模块间通信内容的形式。对于系统中任何有效模块，其或者通过传递数据实现通信，或者通过被“控制”进行某项任务。显然，仅通过数据实现通信的接口更易被理解，而控制类型的通信使模块功能难以被直观理解。

实现弱耦合的途径不一，一个方向是尽量降低元素间关系发生在不同模块间的可能，简单来说就是最小化模块间的关联，并且保证元素间关系只发生在相同模块内部。为了验证元素间关系是否都存在于模块内，Larry同时给出了一个描述模块内部元素间相互绑定程度的指标：内聚(Cohesiveness)。

内聚

由前述可知，实现内部高度绑定的模块，就能够达到降低耦合的目标，即模块自身的强内聚性。一般而言，对模块内聚程度的描述可以被划分成如下六个层级（由弱到强的非线性关系）：

1. 巧合的(Coincidental)。例如元素通过某种模块化方法被“无意间”划分到某个共同模块中，或者某个模块的创建仅仅是为了消除重复代码。在这种情况下，模块极易因为变更而变得“不可重用”，因此这类绑定只是发生于巧合之中。

2. 逻辑的(Logical)。这种关系通常隐含了某种逻辑联系，例如负责程序中所有输入输出的模块，或者负责操作所有数据的模块。其问题在于，以此类关系实现的模块易存在内部元素间的相互缠绕，从而降低元素间的独立性，同时也会导致模块接口的复杂性增加。

3. 一时的(Temporal)。该关系建立在逻辑层面的关系基础上，同时元素间还存在某种时间上的一致性。例如程序的初始化、终止、清理等阶段的操作，其元素间存在一定的功能逻辑，同时也常一起发生。尽管如此，这种关系依然存在于逻辑层面类似的缺陷。

4. 通信的(Communicational)。元素间通过相同输入/输出数据集合的引用进行关联，例如“打印”和“装订”文件，显示出更强的绑定关系。

5. 连续的(Sequential)。如果某个元素的输出恰好是另一个元素的输入，即意味着目标问题可以通过简单流程图进行描述和解决，那么其存在连续的强绑定关系。但需要注意，这种过程式处理会导致该模块独立于程序的其它功能部分，从而使其难以被其它系统模块复用。这也是连续层面与进一步功能层面关系所导致的内聚度存在较大差距的原因。

6. 功能的(Functional)。在这种层面的关系下，模块中的元素都与同一个独立功能相关。一种判断某个模块是否为功能层面的绑定的方法是，通过一句话描述该模块功能，然后进行验证：

   1. 该句是否为复合句，是否包含逗号、多个动词等等，如果是则该模块可能包含连续或通信层面的绑定；

   2. 如果语句中包含时间相关的词，那么可能存在一时或连续层面的绑定；

   3. 如果语句中动词的操作对象不是一个特定对象，那么可能存在逻辑层面绑定；

   4. 如果语句中包含初始化、清理等词，说明可能是一时层面的绑定。

值得注意，元素间可能存在多个上述的关系，而通常我们可以使用其中内聚度表现最高的关系表示整体程度。但是如果模块中没有一组元素的关系表现为功能层面绑定，那么该模块的内聚性就表现较低。

可预测模块

模块的可预测性是指当给定相同的输入时，该模块每次被调用所发生的操作也完全相同，亦即独立于环境的特性。不可预测的模块不一定是存在错误的，例如当模块内部维持某种状态，该状态在针对当前模块的操作下会发生不断变化，从而导致返回结果或实际发生操作的不同。这种不可预测的模块在实际应用中经常发生，尽管是无错误的。模块的可预测性，有时也被成为“黑盒性”，使该模块能较容易被清楚地理解，例如通过简单的注释、描述性的名字或者良好定义的接口等方法。

结构化设计技术

软件设计过程可以被看作包含一般设计和详细设计两个部分。一般设计的目的在于确定系统需要的函数有哪些(回答what)，详细设计描述如何实现这些函数(回答how)。这些设计阶段需要确定函数标识、函数范围结构的调用参数和调用关系、所关联的模块等信息，并且保证模块能够被独立设计、实现和测试。

结构图(Structure Chart)

传统的流程图方法能够描述代码块执行的顺序和条件分支，但是在一般设计阶段，由于我们侧重于了解what，流程图会不可避免地增加设计复杂度。因此这里介绍一种较为简单的结构图用于表述函数及其调用关系。结构图所包含的符号标记如下图所示：

假设某系统设计包含三个模块，分别是A、B和C，其中模块间的关系是A调用B，B调用C；从执行顺序上看，B的代码会首先执行，然后是C，最后是A。那么上述信息可以分别用结构图和流程图表示如下：

从上图可以看出，相比于流程图，结构图能够清楚表示模块间关系，并且有潜力进一步描述模块的接口信息，这恰好是在一般程序设计阶段需要进行的工作，流程图就不具有优势。

基于结构图的软件设计过程

下面以设计一个较为复杂的模拟输入——处理——输出(Input Process Output, IPO)类型的系统为例，给出一种衍生自结构图、由IBM开发的基于层次输入处理输出(Hierarchical IPO)图的一般设计过程：

Step 1. 根据问题描述，绘出系统大致的功能性草图。本例中模拟系统的大致功能是一个数据输入、处理和输出的过程，其大致可以被描述如下：

Step 2. 识别外部的概念数据流，指来源于系统外的、独立于具体物理I/O设备的相关数据流。在本例中，概念数据流包括输入参数、格式化的返回结果等。

Step 3. 识别问题中的主要概念数据流(包括输入和输出)，确定该问题的功能图中的“最高级抽象”节点。对于输入的数据流而言，其抽象节点存在于距离物理输入形态最远，但依然可以视作输入数据的阶段。本例中该节点可能在于构建矩阵阶段。同时，针对输出数据流可以把结果矩阵作为输出的抽象节点，如下图所示。

Step 4. 根据前面步骤得到的信息，针对每个抽象输入数据节点，使用一个源模块(source module)表示其结构。相应设计对应的入模块(sink module)。通常系统存在一个源和入分支，具体参数依赖问题描述而定，但其通用模式如下图所示。

在本例中，模块A即系统入口，也就是说模块A的功能意味着整个问题的解决；模块B用于获取主要数据流；模块C用于把主要输入流变换成主要输出流；模块D用于处理主要的输出数据流。

Step 5. 针对源模块，通过识别其中最后一次变换操作，生成当前模块的数据返回形式，然后再识别前一次变换的抽象节点。对于入模块，与源模块相反，通过识别其中第一次处理操作，确认抽象输出节点，直到获取期望的输出形式。基于逐步求精的思想重复步骤5，直到抵达最初的源模块和最后的入模块。构建出的部分结构图如下所示。

在这一逐步求精的设计过程中，划分的终止条件因具体问题而异，通用的判断方法之一即前文提到的耦合与内聚等设计思想。

（未完待续）

结论

结构化设计的兴起使结构图及其衍生工具成为软件设计领域的重要工具。同时，在软件设计模块化道路上的深入实践也促使许多重要的软件设计思想被提出，诸如耦合、内聚等重要概念被广泛用于指导包括结构化设计及后续的设计方法论，影响至今。

引用

SMC74, Structured design

模块化编程(Modular Programming)：信息隐藏与职责分割

上世纪60年代起，人们意识到实现复杂系统的前提是把系统合理分割为相互独立的部分，这些独立的部分被称作模块。与前文提到的结构化编程和过程式编程的区别是，一个模块可包含若干个子程，也允许组装不同模块以实现子程或程序。D.L. Parnas把这种编程技术称为模块化编程[DLP72]，其中模块意味着任务职责，而模块化设计则表示一系列的跨模块的“系统级”设计决策。自此，模块化成为软件设计领域的重要主题之一。

针对模块化的研究包含两个基本组成部分：

1. 一个良好的模块化系统（设计）应具备哪些特征？

2. 一个良好的模块化系统（设计）应如何实现？

信息隐藏(Information Hiding)

最初的软件设计方法论认为，组织应当建立统一的文档管理系统，软件由设计人员设计好后开放给全体人员，从而让每个人都尽量了解设计背后包含的一系列决策。1971年，Parnas首次提出信息隐藏的概念，反驳了前述的传统设计“广播”实践[DLP71]。

从软件结构的角度看，软件设计包含了对模块自身特征以及模块间的连接(connetion)的描述，其中连接意味着设计对模块间作用的假设。而我们已经知道软件结构最重要的两个目标：系统变更和正确性检验，而一个好的软件结构应使上述目标变得更加容易。以简化系统变更为例，如何使针对当前模块的变更不会传递到其它模块呢？答案当然是应尽量使针对当前模块的变更不至于打破其它模块对其所做的假设，即连接的稳定性。那么如何保证连接的稳定呢？直观来看当然是尽量减少假设的规模，即减少连接所包含的信息。

再以软件文档系统为例，实践证明，保证系统设计文档和代码的一致性需要花费可观的成本，这在大多数组织来说都难以实现。同时为了保证文档自身的可理解性，一个好的实践是建立组织统一的标准和术语，但实践证明这也很难做到，因为假设总会根据需求发生变更，而一旦新的假设违反了组织统一标准，则会引起标准的误用，而反过来扩展标准又有可能造成对已有文档假设的破坏。上述复杂性意味着，在一个实践统一文档标准的组织内，标准会尽量维持系统设计的最小假设，而这又会与文档本身的知识传递作用相违背。

Parnas认为设计人员应尽量“控制”信息的传播，例如在设计中只使用外部接口描述该模块，从而避免细节过早暴露，对外部隐藏那些尚待决定、不稳定或不应被外部了解的具体实现。

职责分割(Responsibility Segment)

人们普遍认为应根据功能职责划分系统模块，但缺少统一的划分方法，导致具体划分时会出现不同结果，原因在于实际问题域的复杂性。以比较简单的经典KWIC系统为例，考虑如下两种模块化设计方案：

1. 系统被划分成5个部分：分别是输入模块I、循环移位(circular shift)模块C、字母排序(Alphabetizing)模块A、输出模块O和主控制模块M。具体来说，I接受行格式的数据输入，把每个单词用四个字母进行压缩表示，其余字母作为单词的结尾，然后将其存储到系统核心(core)；当I读完所有数据，C先对核心中每行数据进行循环移位处理，并记录每条新数据到原始数据的索引，最后把数据存储回核心；然后，A从核心中读取数据，把C中生成的数据按字母进行排序并存储回核心；最后O把A中排序好的数据结合I中获得的原始数据进行匹配和格式化输出；主控制模块M负责控制其余模块的调用顺序，进行错误处理和进行一些必要的空间分配等操作。从实践角度考虑，该方案具备良好的职责分割和接口设计。

2. 系统被划分成6个部分：行存储模块L、输入模块I’、循环移位器C’、排序器A’、输出模块O’ 和主控制模块M’。具体来说，L负责提供对行数据进行操作的功能，例如常见的增删改查等；I’负责读入数据并调用L写入数据；C’用来计算并返回所有的循环移位索引。A’的功能是返回给定索引序号的字母序序号；O’用于输出L或C’中包含的数据；M’与方案1中M的功能类似。该方案也具有良好的职责分割和接口设计。

为了进一步比较这两种方案的区别，首先来看两者在分析该问题时所作出的设计决策及其可能影响：

1. 输入格式。

2. 存储介质，例如把所有行数据存储在core中，那么假设数据集较大，则该决策就会面临挑战。

3. 存储压缩，例如对每个单词进行压缩，假设数据集不大，处理时间反而会因为不必要的压缩而增加。

4. 为循环移位器创建索引，而非直接存储所有数据，对于较小的数据集而言，后一选项可能更加合适。

5. 为所有数据进行一次性按字母序排序，而非只在需要时进行搜索或只进行部分排序。在某些场景中，可能更希望把索引计算量分配至不同时间的字母序操作中。

以下分别使用是否容易变更、是否可独立开发和是否便于理解三个具有共识的软件设计目标分析和比较上述方案。

易变更性，由于都拥有唯一的输入模块，那么决策1的任何潜在变化都不会导致输入模块以外的变化；对决策2和3来说，由于涉及数据的格式表示，方案1中由于多个模块都需要直接读写core中的数据，一旦存储格式因假设发生变化就会导致所有关联模块的修改，相应的方案2由于独立出了行存储功能，因此依旧把改动影响限制在了一个模块之内。同样，决策4的变更可能导致存储格式的变化，方案2中的C’模块只用于计算而非存储，因此变更影响小于方案1；决策5的情况则与决策4类似，方案2具有更好的易变更性。

可独立开发，方案1的模块间接口实际上是通过数据存取间接实现的，其实质是数据格式和表结构的设计，在这种情况下，所有相关模块的接口设计都存在一定联系。而方案2通过若干个函数及其参数就实现了模块间的接口，因此对模块分别可独立开发有更好的支持。

可理解性，根据方案1，为了理解模块职责，需要至少理解模块I、C、A内部的实现，特别是数据存取的设计和实现，才能了解模块间的相互关系；相反方案2只需要通过接口函数的定义就可以了解模块职责了。

从职责分割的角度来说，上述两种方案都给出了初看相当合理的划分，但经过分析我们的结论显然是方案2比方案1更好，那么如何实现诸如本例中更好的职责分割呢？

一种用于模块分割的标准与系统设计方法

实际经验表明，人们直观上会倾向于作出符合上节提到的方案1的设计，这是因为方案1更加显而易见：例如借助流程图(flowchart)工具描述系统功能和流程，再自然映射在模块的划分上。而方案2的核心在于每个模块都努力隐藏其设计决策，包括接口和定义也都以较少的信息呈现，Panars认为这反映了一种以隐藏自身设计决策为目标的模块间分割标准，与传统的流程式思考模式有显著区别。

由于构建计算机系统的复杂性，设计人员在60年代起开始采用一些系统模拟语言(Simulation languages)辅助系统设计。显然，当系统需求越复杂，模拟语言也就会变得更复杂，就越难以满足设计人员的目标，因此模拟语言最初的应用并不成功。1968年，沃森研究院的F. W. Zurcher描述了一种迭代式的多层建模方法，通过在不同的抽象层级(Levels of abstraction)上安排设计决策，为设计人员提供了有效的系统思考工具。

Zurcher提出在一个模型中构建系统的多重表示，即抽象层级。以计算机系统为例，在最上层，该模型只表示系统的若干基本任务，并且给定这些功能所达到的目标，即始终优先回答what；进一步，在下一层引入CPU、存储层级和文件系统的概念，并指定连接上层每个任务的程序和数据的划分；然后，再下一层级描述更加细节的系统表示，直到完整描述了整个系统设计，即回答how。迭代在实现上述方法中同样重要。在采用模拟语言时，先实现上一层的系统设计描述程序，程序应包括本层所含的所有抽象定义；在进入下一层时，构建一个独立的可被上层操作的实现本层抽象意义的模拟程序，从而实现迭代式的层次设计结构。

这种层级建模方法中，每一层都仅包含该层定义范围内的设计决策，即令设计人员更容易理解模型及其具体行为，并且把针对设计的修改限定在本层级范围内，降低了设计变更的影响范围。当进入正式实现阶段时，编程人员可以用具体的算法和数据结构实现替换最底层的模拟程序，从而构建完整系统。

结论

如果说结构化编程奠定了现代编程语言的基础，那么模块化编程则为软件设计提供了应对复杂问题的有效工具。与结构化编程和过程式编程几乎一锤定音相比，模块化编程在过去50年间历经了长期演进，虽然70年代开始大量编程语言开始引入模块(module)的概念，但抽象表达本身的复杂性使整个软件设计和开发过程经历了飞速的变革，而这一切源于模块化的设计思想。

引用

[DLP72], On the Criteria to be Used in Decomposing Systems into Modules

[DLP71], Information distribution aspects of design methodology

[FWZ68], ITERATIVE MULTI-LEVEL MODELLING - A METHODOLOGY FOR COMPUTER SYSTEM DESIGN

结构化编程(Structured Programming)：计算语言的突破

上世纪50-60年代，人类的计算能力实现了迅猛发展，各界对计算机的应用也有很高期许，越来越多的领域希望得到强大的计算赋能从而实现飞跃。然而当面临的问题越多、越复杂时，人们在解决问题的道路上发现了一条巨大的鸿沟，即以现有的软件构建理论和方法难以应对这些挑战。机遇与挑战并存，这场软件危机(Software Crisis)最终促成了软件工程作为一门独立的学科从计算机科学的襁褓中成长起来。

软件危机这个词最早在1968年的北约组织软件工程会议上被诸多与会者提出[NATO68]，由此引发的技术创新和组织行为思辨至今依然活跃。而更现实的影响是，科学家们首先在编程语言本身找到了突破口——结构化编程。

发明于上世纪50年代的ALGOL语言，首次用begin…end语句引入了代码块的概念，通过限定其中变量声明的词法作用域，提高程序的可读性，从此引起了围绕代码块的研究。1966年，论文[Bohm66]证明使用三种基本的程序结构就能表达任何可计算函数：顺序执行、条件选择和循环迭代，这为随后针对结构化编程的讨论提供了理论依据。1968年，Dijkstra发表了著名的”GOTO语句有害“的观点，并且肯定了如条件选择、循环等语句的应用，同时称GOTO语句应该在所有“高级语言”（这里指除了机器码之外的语言）中被废除[EWD68]。Dijkstra认为应当尽可能减少静态程序和动态运行进程之间的差距，而GOTO语句造成了大量程序难以被理解，即人很难从混乱的静态代码中认识程序的真正意图。这一废除GOTO语句的言论激起旷日持久的争论，反对者认为GOTO所具有的灵活性能满足持续的系统优化工作，但争论两方基本同意应当对GOTO限制使用。于是，结构化编程开始被广泛接受。

伴随着结构化编程的普及，过程式编程(Procedural programming)也在60年代起被许多流行语言采纳，如COBOL和BASIC。这种编程方法以代码块为基础，允许使用子过程（也称子程或函数）编写程序单元，并且可以被程序随时调用。使得来自不同程序员甚至不同组织的代码变得简单可复用，为随后代码库的流行奠定基础。

结构化程序设计与分析

结构化编程实现了编程语言的巨大进步，作为首席布道者，Dijkstra发表了很多关于程序的可理解性以及结构化编程实践的原则性观点[EWD70]，但如何设计结构化程序还需要进一步说明。1971年，在计算机教育领域功勋卓著的Niklaus Wirth详细解释了一种自顶而下逐步求精的程序设计方法，并以数学中经典的八皇后问题（把这个著名问题作为编程案例，原因之一是尚无该问题的已知解析解）为例演示了程序设计从问题分析到实现的过程[NW71]。

简单分析可以得到八皇后问题的直观解法：对于全体候选解的集合A，其中每个解元素x满足条件函数p，即(x ∈ A) ∧ p(x)，则：

1
2
3

repeat Generate the next element of A and call it x
until p(x) ∨ (no more elements in A);
if p(x) then x = solution

由排列组合知识可知，集合A的空间可达2³²，枚举算法效率较低。通过对问题进一步的分析，使用回溯法解决该问题的算法效率较高，即：

1
2
3
4

j := l;
repeat trystep j;
if successful then advance else regress
until (j < 1) ∨ (j > n) 

以上述程序分析结果为基础构建程序，按照回溯算法的基本思想，首先依照specification给出初步实现：

1
2
3
4
5
6
7

variable board, pointer, safe;
considerfirstcolumn;
repeat trycolumn;
  if safe then
  begin setqueen; considernextcolumn
  end else regress
until lastcoldone ∨ regressoutoffirstcol

根据现有结构化编程语言的表达能力，对如下指令进一步分解：

trycolumn:

1
2
3

procedure trycolumn;
repeat advancepointer; testsquare
until safe ∨ lastsquare 

regress:

1
2
3
4
5
6
7
8
9
10
11

procedure regress;
begin reconsiderpriorcolumn
  if ¬ regressoutoffirstcol then
  begin removequeen;
      if lastsquare then
      begin reconsiderpriorcolumn;
          if ¬ regressoutoffirstcol then
              removequeen
      end
  end
end

截至目前，如需对上述程序中的指令做进一步分解，就需要设计额外的数据表示了。通过分析待分解语句，可知需要设计一个记录每位皇后位置的数据表示，例如使用二维数组表达棋盘上的每个方块。这里给出一个优化的数据表示方式：

1
2

integer j (0 ≤ j ≤ 9)
integer array x[1:8] (0 ≤ x[i] ≤ 8) 

其中j表示当前被检查的列序号，一维数组x用于存储上一次被检查方块的坐标，程序的部分指令可以被进一步细化为：

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

procedure considerfirstcolumn;
  begin j := 1; x[1] := 0 end
procedure considernextcolumn;
  begin j := j + 1; x[j] := 0 end
procedure reconsidetpriorcolumn; j := j - 1
procedure advancepointer;
  x[j] := x[j] + 1
Boolean procedure lastsquare;
  lastsquare := x[j] = 8
Boolean procedure lastcoldone;
  lastcoldone := j > 8
Boolean procedure regressoutoffirstcol;
  regressoutoffirstcol := j < 1 

接下来考虑剩余指令testsquare、setqueen和removequeen。

指令testsqaure需要验证是否满足问题条件，通过已知的x数组应不难通过计算进行判定，问题是可能导致较高的计算量，同时考虑到testsquare的调用频次较高，这里采用额外数据表示进行优化，设计三个Boolean型数组，其意义如下：

1
2
3

a[k] = true : no queen is positioned in row k
b[k] = true : no queen is positioned in the /-diagonal k
c[k] = true : no queen is positioned in the \-diagonal k 

那么testsquare就可以用简单的布尔运算表示，其余指令也可以通过上述结构完成：

1
2
3
4
5
6

procedure testsquare;
  safe := a[x[j]] ∧ b[j+x[j]] ∧ c[j-x[j]]
procedure setqueen;
  a[x[j]] := b[j+x[j]] := x[j-x[j]] := false
procedure removequeen;
  a[x[j]] := b[j+x[j]] := c[j-x[j]] := true 

此时发现上述实现的x[j]调用次数过多，为了进一步优化，把x[j]用变量i表示，从而有：

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

procedure testsquare;
  safe := a[i] ∧ b[i+j] ∧ c[i-j]]
procedure setqueen;
  a[i] := b[i+j] := c[i-j] := false
procedure removequeen;
  a[i] := b[i÷j] := c[i-j] := true
procedure considerflrstcolumn ;
  begin j:= 1; i:= 0 end
procedure advancepointer; i := i + l
procedure considernextcolumn
  begin x[j] := i; j:=j+l; i := 0 end
Boolean procedure lastsquare;
  lastsquare := i = 8 

通过inline替换程序中的部分指令，其余采用过程调用，从而最终实现如下程序：

1
2
3
4
5
6
7
8
9

j := 1; i := 0;
repeat
  repeat i := i + 1 ; testsquare
  until safe ∨ (i = 8);
  if safe then
  begin setqueen; x[j] := i; j := j + 1; i := 0
  end else regress
until (j > 8) ∨ (j < 1);
if i > 8 then PRINT(x) else FAILURE 

前述过程清晰解释了逐步求精这种非常经典的结构化程序的分析和设计过程，从早期分析确定适用算法，然后利用基本的结构化编程元素描述初步程序，对复杂过程进一步分解，同时考虑额外必要的数据表示和程序运行效率优化，最终使用目标编程语言实现程序。这是一种具有普遍适用意义的编程方法论，也呼应了Wirth的那句名言：程序=算法+数据结构。

结论

50年前的软件危机所揭露的问题成为今天软件工程研究的基石。GOTO语句的争论直至今天，从历史发展看，更多人选择支持Dijkstra的GOTO有害论，许多90年代以后出现的编程语言并没有在应用层面设计GOTO语句。但是，GOTO争论背后有关编程语言灵活和统一的争辩还远未结束。另一方面，结构化编程促成了一套良好的编程方法论，迄今Wirth的逐步求精方法还被采用于程序设计课程，为计算机教育的普及和广泛应用打下了坚实基础。同时，软件设计所要解决的问题也得以提升到更高的复杂度水平。

引用

NATO68, NATO Software Engineering Conference

Bohm66, Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules

EWD68, Go-to statement considered harmful

EWD70, Notes on structured programming

NW71, Program Development by Stepwise Refinement

《软件设计与架构笔记》系列，是笔者对自上世纪60年代末至今在工业界和学术界皆有一定影响的软件设计方法的学习和记录，期望通过历史的时间轴把握相关技术发展的脉络，尝试理解推动了这一领域中概念、方法、原则、模式、实践不断演进的若干基本动机，倚靠巨人的肩膀，但求一条少些人云亦云的实践之路。

自诞生之日起，软件设计就同时在工业界和学术界探索和实践着，然而二者的动机和方法大相径庭。例如计算机科学家Edsger W. Dijkstra，一生就致力于对计算的简洁性和精确性的探索，其工作背后蕴含了严谨的数学美学；而工业界则侧重于使用由计算衍生的自动化方法解决传统生产的问题，根本目的是追求经济利益的最大化。有趣的是，二者的偶然交汇就迸发出这一系列文章的主题——软件设计，而软件架构——作为稍晚出现的buzz word，有时也被本文采用以和行业用语保持一致。

THE Multiprogramming system：早期探索

1965年，Dijkstra在埃因霍温科技大学领导了一支团队在Electrologica(EL) X8上开发多道程序系统，该系统的主要目标是能够平滑地处理持续的用户程序流，并将其作为服务提供给学校。该系统的设计目标是：1.降低短程序运行的周转时间； 2.更经济地使用外设; 3.结合后备存储器的自动控制和中央处理器的经济使用; 4.验证一种经济可行性，即将EL X8用于运行在不依赖容量和计算能力，仅需要通用计算机灵活性的应用程序。

出于多道程序系统的复杂性，实时触发中断的偶然性和不可复现性使系统开发的debug面临挑战。为此，团队决定在系统构建之初就重视对debug能力的设计，从而在具体实现前就能证明系统的逻辑可靠性，并显著降低了实际bug数量。在论文EWD68中，为了提高可测试性，设计者采用层级结构划分整个系统，并以不同的职责区分系统层级：

0级，负责把逻辑可用的进程分配给处理器。为了防止任何进程独占处理器，该层实现了一个实时时钟中断功能。

1级，实现“段控制器”，通过中断与上层的顺序进程保持同步，负责从自动后备存储器中记录数据。

2级，实现“消息解释器”，负责在控制键盘的输入时产生中断，并且联接系统对话的操作员和特定的目标进程。

3级，实现与输入流缓冲和输出流解缓冲相关的顺序进程，通过逻辑通信单元实现对具体外设的抽象，并按照资源限制采用同步方法限制外设运行的数量。

4级，实现独立用户程序。

根据上述层级划分，团队制定了需求规格说明书，并依此实现系统。在验证阶段，在添加下一层级前，需要对前一层进行充分测试，例如针对0级中实现的实时中断和处理器分配，首先设计一个完整的测试状态空间，然后依次进行测试。而当对1级的“段控制器”进行测试时，可以在0级时制定的测试状态空间的基础上，通过引入“请求页”操作，实现状态空间的扩展，只需引入少量新的测试就可以满足当前层的测试需求，直至完成整个系统。

Dijkstra认为，虽然在概念和设计阶段花费了较长时间，但是该过程为系统贡献了良好的设计，避免传统非层级实现可能面临的测试状态空间“爆炸”问题，从而对系统质量提供保证。

虽然缺少定量的研究方法，发布于1968年的THE Multiprogramming System可以说是首次定性地证明了结构在软件设计中的重要作用，并且以系统的可测试性为例进行了深入阐释。

结论

系统的复杂性引出了软件设计问题。Dijkstra把软件开发过程划分成三个阶段：概念、构建和验证，并且由一个基于层级划分的设计案例指出结构因素在软件设计中的重要性。虽然工业界可能面临更多的问题（例如成本、人员、规模、业务复杂程度等），但是概念阶段产出的良好设计，能使验证阶段受益，从而实现整体的系统质量保证（笔者注：某种程度上也起到控制成本的作用），是THE多道程序系统的一项重要结论，也启发后人对软件概念阶段本身和其边际效应的进一步研究。

值得一提的是，按照不同职责划分层级，底层能够对上层隐藏其核心概念和具体实现，例如0级隐藏了处理器操作，1级隐藏了“页存储”机制，2级隐藏了电传打印控制台等。但是“信息隐藏”作为一个基本设计概念被明确提出，则是若干年以后了。

引用

[EWD68] EW Dijkstra, The structure of the ‘THE’-multiprogramming system.

Looking back to the past five years, my common experience for joining a project is always looking like this:

Learning business knowledge -> Revealing technical context -> Launching a new project and instilling good practices into the team to make better software as usual.

While it’s not always true for software engineers, I rarely got chance to work on the pre-existing codebase, not to mention a whole legacy engineering.

Things have changed since I stepped on a new journey. My very first challenge is taking over a legacy engineering. I call it legacy engineering because all I have to care is far more than only the codebase, although it is absolutely focal to tackle with the legacy code. The rest of this article will introduce the steps and thoughts I’ve taken during this process.

Communication

A good teacher can at least half the work. Everyone who ever worked in the team can teach and benefit, but the following question is how to learn from people more effectively. My answer is no doubt through good communication.

For those who are interested, I would suggest some great learnings like Nonviolent Communication and Crucial Conversations. No follow-up discussion since we’re not talking about psychology here, but remember it’s indeed the first priority soft skill as a professional.

Documentation

For a hand-over stage, documentation in any form is less effective than a good communication. But it’s worthy to keep valuable knowledge and make it more efficient to spread those to broader stakeholders. Again, it always depends on requirement at the moment for determining the scope of what should be documented. My personal inclination is several topics listed as follows:

1. Team specific knowledge that everyone should be aware of.
2. Any confusing/complicated part.
3. The reason for counter-intuitive decisions made by former team members.

It finally leads to three basic documents for me:

1. Feature list (Rough is good).
2. Team engineering practice, like workflow definition and release cycle.
3. Crucial code design.

Of course, the Evernote in hand to prepare for any unknown technologies and skills.

Codebase

Being familiar with codebase is always the top priority for a newbie, but former topics we just discussed would influence the effectiveness of codebase learning. As software engineering today has adopted many common practices like CI/CD and DevOps, those automation practices can help to guide people along with the code or script, rather than outdated document and lengthy tutorial.

Build (Pipeline)

Build automation is the most matured practice in nowadays software engineering. For a newbie, the build script provides panorama and coarse-grained view of system modularity and dependency, it would be even clearer if the team is maintaining an effective CI pipeline.

A undoubted fact is that the more matured for build automation, the more efficiency for a newbie to get first wave things done. Otherwise, it would take weeks to set up a local environment by referring to an far outdated guide and consulting different team members!

Test

It’s not very common to see “effective tests” in the codebase, not to mention the practice of the whole test pyramid or sandwich. Automation test is a proven practice to assure quality, sometimes it is promoted to be the specification of the codebase. However, bad practice for automation test also does harm other than keeping high quality.

For a newbie, in most cases, the tests especially the bad tests cannot help for specification at all, it shows less value than a good naming practice. My personal experience is that the test is not so good for early learning if it’s not well organized and properly implemented. That’s not saying that it doesn’t play vital role to indicate the consistency when any changes happen.

It’s usually easy for everyone to see the value of automation test, while it also makes this practice be one of the most confusing parts in modern software engineering as lack of deep understanding.

Operation

As DevOps is more adopted, it turns to be more necessary for a newbie to understand operation knowledge. Must-have topics include configuration management and specification of cloud platform and core systems.

Design (Structural) and Refactor

The core of codebase learning is about design. A design could be regarded as a collection of decisions along the software development. For a newbie, it’s more important to concentrate on the crucial design points than knowing every corners.

Although it varies for the different roles, as a backend newbie, the top concern comes into the structural design. To learn software structure,a good starting point could be any selected feature from both business and technical perspective, it can help dive into the deeper codebase to understand the structure, then forms into whole picture of modularity design.

A good approach is to elaborate design with some tools, CRC even Naked CRC is agiler, but UML is also very cool and common, it again depends on team background for these tools selection. More important is that whichever tool is used, only the leading design rules need to be considered, rather than drawing a full system map. During this process, design pattern may benefit but also cause restriction.

It’s not exactly same for design of software structure and logical data model, but the latter could also be learned via any cleaner ways (like E-R diagram), not necessary to dig into physical data model too early unless there is significant reason to do that.

Feature Enhancement

I wouldn’t suggest making big change or refactor on the legacy codebase which is just taken over unless the change is too small to cause any visible influence. Before doing any work alone, a newbie still needs to learn from core team members about:

1. Architecture Roadmap.
2. Non-functional requirements.
3. Technical debts and roadmap of resolution.

Despite the following work would be feature enhancement in most cases. I’d take different strategy depends on the potential influence of the change.

Here I’m not going to discuss the case of a tiny change, that wouldn’t be a big deal anyway. But if the change is going to happen on the higher level design rule but not touch leading yet (which usually implies a broader influence across code), I could try to add new features via extensional way (rather than editing as is code and making feature changes directly, methods metioned in Working effectively with legacy code are good guidance), and extra feature toggles may help for QA and CD.

The worst case is the desired change must happen on leading design rule, which means it won’t work with just simple extension, a big change is definitely required. Even in this case, I wouldn’t edit any as is code in an early stage, and purely technical refactor without guidance from business requirement is also not a good option. Instead, I’d create a separate package or namespace as the neighbor of the code which is going to die, and naming it “experiment” or anything makes sense. Using least effort to make experiment code work as well as automation test, without breaking any as is feature or code. Once new feature and refactor direction is confirmed, the experiment code can be transformed into formal and replace dead one.

The benefit of this “experimental duplication” is that I can continue looking at two implementations and making a trade-off when thinking of the design for following refactor until the new feature is completed and confirmed. Later on, refactor and clean-up can be done to completely remove the deprecation.

Conclusion

In this article, we discussed the strategies I would take while working with legacy engineering. Someone calls it reverse engineering to imply the digestion for an incredibly overdue but complicated legacy codebase or engineering. While in most cases it does not have to make upfront “reverse engineering” to reach critical decision for future, nor do a hasty change on codebase to cause risk. We can certainly take actions to delay that decision making, by mitigating waste and respecting the economic model of our beloved software industry.

测试金字塔理论被广泛应用于计划和实施敏捷软件开发所倡导的的测试自动化，并且取得了令人瞩目的成就。本文尝试从产品开发的角度出发，结合Kent Beck最近提出的3X模型和近年来迅速发展的自动化测试技术，提出并讨论一种新的测试层级动态平衡观：三明治模型。同时，为了应对端到端测试在实践中面临的种种挑战，设计并实现了一种面向用户旅程的端到端自动化测试框架——雪鸮。实际项目经验表明，雪鸮能够显著提升端到端测试的可维护性，减少不确定性影响，帮助开发人员更快定位和修复问题，对特定时期的产品开发活动更具吸引力。

背景

测试金字塔

按照自动化测试的层级，从下至上依次为单元测试、集成测试和端到端测试，尽量保持数量较多的低层单元测试，以及相对较少的高层端到端测试，这就是测试金字塔理论。随着敏捷软件开发的日益普及，测试金字塔逐渐为人所知，进而得到广泛应用。Mike Cohn、Martin Fowler以及Mike Wacker等先后对测试金字塔进行了很好的诠释和发展，其主要观点如下：

• 测试层级越高，运行效率就越低，进而延缓持续交付的构建-反馈循环。
• 测试层级越高，开发复杂度就越高，如果团队能力受限，交付进度就会受到影响。
• 端到端测试更容易遇到测试结果的不确定性问题，按照Martin Fowler的说法，这种结果不确定性的测试毫无意义。
• 测试层级越低，测试的代码隔离性越强，越能帮助开发人员快速定位和修复问题。

3X模型

2016年起，敏捷和TDD先驱Kent Beck开始在个人facebook主页撰写系列文章，阐述产品开发的三个阶段——Explore、Expand和Extract，以及在不同阶段中产品与工程实践之间的关系问题，即3X模型。近二十年软硬件技术的飞速发展，使得软件开发活动面临敏捷早期从未遇到的市场变革，而根据在facebook工作的经历，Kent Beck把产品开发总结为三个阶段：

• 探索（Explore），此时的产品开发仍处于非常初期的阶段，仍然需要花费大量时间寻找产品和市场的适配点，收益也是最低的阶段。
• 扩张（Expand），一旦产品拥有助推器（通常意味着已经找到了市场的适配点），市场需求就会呈现指数级上升，产品本身也需要具备足够的伸缩性以满足这些需求，由此收益也会快速上升。
• 提取（Extract），当位于该阶段时，公司通常希望最大化产品收益。但此时收益的增幅会小于扩张阶段。

Kent Beck认为，如果以产品是否成功作为衡量依据，那么引入自动化测试在探索阶段的作用就不大，甚至会延缓产品接受市场反馈循环的速度，对产品的最终成功毫无用处，还不如不引入；当位于扩张阶段时，市场一方面要求产品更高的伸缩性，另一方面也开始要求产品保证一致的行为（例如质量需求），那么此时就该引入自动化测试来保证产品的行为一致性；当产品最终处于提取阶段时，任何改动都应以不牺牲现有行为为前提，否则由此引发的损失可能远高于改动带来的收益，此时自动化测试就扮演了非常重要的角色。

测试工具爆炸式增长和综合技能学习曲线陡升

根据SoftwareQATest网站的历史数据，2010年记录的测试工具有440个，共划分为12个大类。这个数字到2017年已经变为560个，共15个大类，且其中有340个在2010年之后才出现。也就是说，平均每年就有50个新的测试工具诞生。

面对测试工具的爆炸式增长，一方面所支持的测试类型更加完善，更加有利于在产品开发过程中保证产品的一致性；另一方面也导致针对多种测试工具组合的综合技能学习曲线不断上升。在实践中，团队也往往对如何定义相关测试的覆盖范围感到不知所措，难以真正发挥测试工具的效用，也很难对产品最终成功作出应有的贡献。

从金字塔到三明治

作为敏捷在特定时期的产物，测试金字塔并不失其合理性，甚至还对自动化测试起到了重要推广作用。但是，随着行业整体技术能力的不断提升，市场需求和竞争日趋激烈，在项目中具体实施测试金字塔时往往遭遇困难，即便借助外力强推，其质量和效果也难以度量。

此外，随着软件设计和开发技术的不断发展，低层单元测试的传统测试技术和落地，因前、后端技术栈的多样化而大相径庭；同时，在经历过覆盖率之争，如何确保单元测试的规范和有效，也成为工程质量管理的一大挑战；高层的端到端测试则基本不受技术栈频繁更替的影响，随着不同载体上driver类技术的不断成熟，其开发复杂度反而逐渐降低。

这里讨论一种新的测试层级分配策略，我们称之为三明治模型 。如下图所示，该模型允许对不同测试层级的占比进行动态调整，说明了倒金字塔形、沙漏形以及金字塔形分配对特定产品开发阶段的积极作用。

产品开发的自动化测试策略

根据3X模型，在探索初期往往选择避开自动化测试。一旦进入扩张期，产品的可伸缩性和行为一致性就成为共同目标，但此时也常会发生大的代码重构甚至重写，如果沿用测试金字塔，无论补充缺失的单元测试，还是只对新模块写单元测试，都既损害了产品的快速伸缩能力，也无法保证面向用户的产品行为一致性。因此，如果在探索后期先引入高层的端到端测试，覆盖主要用户旅程，那么扩张期内所产生的一系列改动都能够受到端到端测试的保障。

需要注意的是，用户旅程在产品即将结束探索期时通常会趋于稳定，在扩张期出现颠覆性变化的概率会逐渐减少，端到端测试的增长率会逐步下降。

除此以外，随着扩张期内不断产生的模块重构和服务化，团队还应增加单元测试和集成测试的占比。其中，单元测试应确保覆盖分支场景（可以在CI中引入基于模块的覆盖率检测）；集成测试和某些团队实践的验收测试，则需进一步覆盖集成条件和验收条件（在story sign-off和code review时验收）。

许多新兴的测试技术和工具擅长各自场景下的验收测试，但更重要的仍是识别产品阶段和当前需求，以满足收益最大化。

由此我们认为，随着产品开发的演进，测试层级的分配应参考三明治模型，动态调整层级占比，更加重视运营和市场反馈，致力于真正帮助产品走向成功。

端到端测试的机遇和挑战

与其他测试层级相比，端到端测试技术的发展程度相对滞后。一方面，作为其基础的driver工具要在相应载体成熟一段时间之后才能趋于稳定，web、mobile无不如是。另一方面，端到端测试偏向黑盒测试，更加侧重描述用户交互和业务功能，寻求硬核技术突破的难度较高，于是较少受开发人员青睐。但是，由于端到端测试更接近真实用户，其在特定产品开发活动中的性价比较高，有一定的发展潜力。

然而，当前实践中的端到端测试，普遍存在如下问题：

• 低可维护性。一般实践并不对测试代码质量作特别要求，而这点在端到端测试就体现得更糟。因为其涉及数据、载体、交互、功能、参照（oracle）等远比单元测试复杂的broad stack。虽然也有Page Object等模式的广泛应用，但仍难以应对快速变化。
• 低运行效率。如果拿单次端到端测试与单元测试相比，前者的运行效率肯定更低。因此只一味增加端到端测试肯定会损害构建-反馈循环，进而影响持续交付。
• 高不确定性。同样因为broad stack的问题，端到端测试有更高的几率产生不确定测试，表现为测试结果呈随机性成功／失败，进一步降低运行效率，使得真正的问题很容易被掩盖，团队也逐渐丧失对端到端测试的信心。
• 难以定位问题根因。端到端测试结果很难触及代码级别的错误，这就需要额外人工恢复测试环境并尝试进行问题重现。其中所涉及的数据重建、用户交互等会耗费可观的成本。

方法

为了解决传统端到端测试遇到的种种挑战，本文设计了一种面向用户旅程的端到端自动化测试框架——雪鸮（snowy_owl），通过用户旅程优先、数据分离、业务复用和状态持久化等方法，显著提高了端到端测试的可维护性，降低不确定性的影响，并且能够帮助团队成员快速定位问题。

用户旅程驱动

端到端测试应尽量贴近用户，从用户旅程出发能保证这一点。在雪鸮中，用户旅程使用被称作play books的若干yaml格式的文件进行组织，例如下列目录结构：

play_books/
  core_journey.yml
  external_integration.yml
  online_payment.yml

其中每个play book由若干plots所组成，plot用于表示用户旅程中的“情节”单位，其基本特征如下：

• 单一plot可以作为端到端测试独立运行，例如发送一条tweet的情节：

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

SnowyOwl::Plots.write 'send a plain text tweet' do
  visit '/login'
  page.fill_in 'username', with: 'username'
  page.fill_in 'password', with: 'password'
  page.find('a', text: 'Sign In').click
  # verify already login?
  page.find('a', text: 'Home').click
  # verify already on home page?
  page.fill_in 'textarea', with: 'Hello World'
  page.find('a', text: 'Send').click
  # verify already sent?
end

• 单一plot应是紧密关联的一组用户交互，并且具备体现一个较小业务价值的测试参照。
• plot可以被play book引用任意次从而组成用户旅程，play book同时定义了所引用plots之间的顺序关系，基本语法如下所示：

1
2
3
4

---
- plot_name: send a plain text tweet
  digest: 2aae6c35c94fcfb415dbe95f408b9ce91ee846ed
  parent: d6b0d82cea4269b51572b8fab43adcee9fc3cf9a

其中plot_name表示情节的标题，digest和parent分别表示当前情节引用在整个端到端测试过程中的唯一标识和前序情节标识，初期开发人员可以通过各个情节的引用顺序定义用户旅程，大多数情况下digest和parent将由系统自动生成并维护。

整个play books集合将是一个以plots为基础组成的森林结构，而端到端测试的执行顺序则是针对其中每棵树进行深度遍历。

通用业务复用

由于plot本身必须是一个独立可运行的端到端测试，那么plots之间通常会共享一部分交互操作，例如用户登录。雪鸮允许把高度可复用的交互代码进行二次抽取，称作determination：

1
2
3
4
5
6
7
8

SnowyOwl::Determinations.determine('user login') do |name, user_profile|
  # return if already login
  visit '/login'
  page.fill_in 'username', with: user_profile[:username]
  page.fill_in 'password', with: user_profile[:password]
  page.find('a', text: 'Sign In').click
  # verify already login?
end

这样，plot的代码就可以简化成:

1
2
3
4
5
6
7
8

SnowyOwl::Plots.write 'send a plain text tweet' do
  determine_user_login({username: 'username', password: 'password'})
  page.find('a', text: 'Home').click
  # verify already on home page?
  page.fill_in 'textarea', with: 'Hello World'
  page.find('a', text: 'Send').click
  # verify already sent?
end

这里应注意Determination和Page Object的区别。看似使用Page Object可以达到相同的目的，但是后者与Page这一概念强绑定。而Determination更加侧重描述业务本身，更符合对用户旅程的描述，因此比Page Object在plot中更具适用性。当然，在描述更低层的组件交互时，Page Object仍然是最佳选择。

测试数据分离

合理的数据设计对描绘用户旅程非常重要，雪鸮对测试逻辑和数据进行了进一步分离。例如用户基本数据（profile），同样是使用yaml文件进行表示：

data/
  tweets/
    plain_text.yml
  users/
    plain_user.yml

那么在plot的实现中，就可以使用同名对象方法替代字面值：

1
2
3
4
5
6
7
8

SnowyOwl::Plots.write 'send a plain text tweet' do
  determine_user_login({username: plain_user.username, password: plain_user.password})
  page.find('a', text: 'Home').click
  # verify already on home page?
  page.fill_in 'textarea', with: plain_text.value
  page.find('a', text: 'Send').click
  # verify already sent?
end

情节状态持久化

雪鸮的另一个重要功能是情节状态的持久化和场景复原。为了启用情节状态持久化，开发人员需要自己实现一个持久化脚本，例如对当前数据库进行dump，并按照雪鸮提供的持久化接口把dump文件存储至指定位置。

当端到端测试运行每进入一个新的情节之前，系统会自动执行持久化脚本。也就是说，雪鸮支持保存每个情节的前置运行状态。

当端到端测试需要从特定的情节重新开始运行时，雪鸮同样会提供一个恢复接口，通过用户自定义的数据恢复脚本把指定位置的dump文件恢复至当前系统。

该功能有两处消费场景：

• 由于broad stack的问题，端到端测试不确定性的技术因素一般较为复杂。实际经验表明，测试的随机失败率越低，就越难以定位和修复问题，而通过不断改进测试代码的方式消除这种不确定性的成本较高，效果也不好。但是，可以尽量消除不确定性带来的影响。例如，不确定测试导致的测试失败，通常会导致额外人工验证时间，完全可以选择让系统自动重试失败的测试。另一方面，重试会造成测试运行效率降低，特别是针对端到端测试。当一轮端到端测试结束后，雪鸮只会自动重试失败的情节测试，同时利用该情节对应的数据dump文件保证场景一致性，这就减少了重试整个端到端测试带来的运行效率下降问题。
• 当团队成员发现端到端测试失败，通常需要在本地复现该问题。而借助测试dump文件，可以直接运行指定plot测试，从而避免额外的人工设置数据和交互操作，加快问题定位和解决。

实践

雪鸮在笔者所在的项目有超过6个月的应用时间。该项目在产品开发方面长期陷入困境，例如过程中同时兼具了3X每个阶段的特点，不仅缺少清晰的产品主线，还背负了接棒遗留系统的包袱。这种状况对工程质量管理提出了更大挑战。

项目采用雪鸮对已有端到端测试进行了重构，生成了一个核心用户旅程和三个涉及外部系统集成的重要用户旅程，包含24个plots，9个determinations，使端到端测试实现了长期稳定运行。在本地相同软硬件环境下，不确定性导致的随机失败从原有10%降低至1%以内，部署至云环境并采用headless模式后，连续15天测试失败记录为零，运行效率的损失可以忽略不计。同时，当用户旅程产生新分支时，可以引入新的情节测试节点，并且根据业务需求将其加入现有play book树，从而实现端到端测试的快速维护。

持续集成与常态化运行

项目完整的端到端测试的平均运行时间保持在19分钟左右，为了不影响现有持续集成节奏，CI每30分钟自动更新代码并运行端到端测试，结果在dashboard同步显示，一旦发生测试失败，第一优先级查找失败原因并尝试在本地复现和修复。

常态化运行端到端测试的另一个好处是，能够以低成本的方式实现24小时监控系统各个组件的功能正确性，有助于更早发现问题：一次，产品即将上线的支付功能发生异常，查看CI记录发现端到端测试在晚上9:15左右出现了首次告警。通过及时沟通，确认是海外团队在当时擅自改动了支付网关的一个配置，造成服务不可用的问题，并迅速得以解决。

结论与展望

Kent Beck的3X模型，提出了从不同产品开发阶段看待工程实践的新视角。而敏捷一贯推崇的TDD等实践，更多体现在个人技术专长（Expertise）方面，与产品是否成功并无必然联系。然而，程序员的专业主义（Professionalism）的确同时涵盖了技术专长和产品成功两个方面，二者相辅相成。因此，如何通过平衡众多因素并最终提高整体专业性，这才是软件工程面临的经典问题。本文给出的测试三明治模型，目的就是帮助思考产品开发过程中测试层级间的平衡问题。

为了应对现有端到端测试面临的挑战，本文设计并实现了一种新的面向用户旅程的端到端测试框架，通过职责隔离、业务复用和状态持久化等手段，构建了易于维护且更加有效的端到端测试。同时，基于上述方法构建的测试代码，更易于和自动化测试的其他研究领域相结合，在诸如测试数据构建、用例生成、随机测试和测试参照增强等方向有进一步的应用潜力。