第四章形式化说明技术4.1概述非形式化方法的缺点4.1.13用自然语言书写的系统规格说明书，可能存在矛盾、二义性、含糊性、不完整性及抽象层次混乱等问题。所谓矛盾是指一组相互冲突的陈述。二义性是指读者可以用不同方式理解的陈述。系统规格说明书是很庞大的文档，因此，几乎不可避免地会出现含糊性。实际上，这样笼统的陈述并没有给出任何有用的信息。不完整性可能是在系统规格说明中最常遇到的问题之一。抽象层次混乱是指在非常抽象的陈述中混进了一些关于细节的低层次陈述。这样的规格说明书使得读者很难了解系统的整体功能结构。4.1.2形式化方法的优点人在理解用自然语言描述的规格说明时，容易产生二义性。为了克服非形式化方法的缺点，人们把数学引入软件开发过程，创造了基于数学的形式化方法。在开发大型软件系统的过程中应用数学，能够带来下述的几个优点：数学最有用的一个性质是，它能够简洁准确地描述物理现象、对象或动作的结果，因此是理想的建模工具。数学特别适合于表示状态，也就是表示做什么”。需求规格说明书主要描述应用系统在运行前和运行后的状态，因此，数学比自然语言更适于描述详细的需求。在理想情况下，分析员可以写出系统的数学规格说明，它准确到几乎没有二义性，而且可以用数学方法来验证，以发现存在的矛盾和不完整性，在这样的规格说明中完全没有含糊性。但是，实际情况并不这么简单，软件系统的复杂性是出了名的，希望用少数几个数学公式来描述它，是根本不可能的。此外，即使应用了形式化方法，完整性也是难于保证的：由于沟通不够，可能遗漏了客户的一些需求；规格说明的撰写者可能有意省略了系统的某些特征，以便设计者在选择实现方法时有一定自由度：要设想出使用一个大型复杂系统的每一个可能的情景，通常是做不到的。在软件开发过程中使用数学的另一个优点是，可以在不同的软件工程活动之间平滑地过渡。不仅功能规格说明，而且系统设计也可以用数学表达，当然，程序代码也是一种数学符号（虽然是一种相当繁琐、穴长的数学符号)。数学作为软件开发工具的最后一个优点是，它提供了高层确认的手段。可以使用数学方法证明，设计符合规格说明，程序代码正确地实现了设计结果
第四章 形式化说明技术 4.1 概述 4.1.1 非形式化方法的缺点 用自然语言书写的系统规格说明书，可能存在矛盾、二义性、含糊性、不完整性及抽象 层次混乱等问题。 所谓矛盾是指一组相互冲突的陈述。 二义性是指读者可以用不同方式理解的陈述。 系统规格说明书是很庞大的文档，因此，几乎不可避免地会出现含糊性。实际上，这样 笼统的陈述并没有给出任何有用的信息。 不完整性可能是在系统规格说明中最常遇到的问题之一。 抽象层次混乱是指在非常抽象的陈述中混进了一些关于细节的低层次陈述。这样的规格 说明书使得读者很难了解系统的整体功能结构。 4.1.2 形式化方法的优点 人在理解用自然语言描述的规格说明时，容易产生二义性。为了克服非形式化方法的缺 点，人们把数学引入软件开发过程，创造了基于数学的形式化方法。 在开发大型软件系统的过程中应用数学，能够带来下述的几个优点： 数学最有用的一个性质是，它能够简洁准确地描述物理现象、对象或动作的结果，因此 是理想的建模工具。数学特别适合于表示状态，也就是表示“做什么”。 需求规格说明书主要描述应用系统在运行前和运行后的状态，因此，数学比自然语言更 适于描述详细的需求。在理想情况下，分析员可以写出系统的数学规格说明，它准确到几乎 没有二义性，而且可以用数学方法来验证，以发现存在的矛盾和不完整性，在这样的规格说 明中完全没有含糊性。但是，实际情况并不这么简单，软件系统的复杂性是出了名的，希望 用少数几个数学公式来描述它，是根本不可能的。此外，即使应用了形式化方法，完整性也 是难于保证的：由于沟通不够，可能遗漏了客户的一些需求；规格说明的撰写者可能有意省 略了系统的某些特征，以便设计者在选择实现方法时有一定自由度；要设想出使用一个大型 复杂系统的每一个可能的情景，通常是做不到的。 在软件开发过程中使用数学的另一个优点是，可以在不同的软件工程活动之间平滑地过 渡。不仅功能规格说明，而且系统设计也可以用数学表达，当然，程序代码也是一种数学符 号(虽然是一种相当繁琐、冗长的数学符号)。 数学作为软件开发工具的最后一个优点是，它提供了高层确认的手段。可以使用数学方 法证明，设计符合规格说明，程序代码正确地实现了设计结果
4.1.3应用形式化方法的准则人们对形式化方法的看法并不一致。形式化方法对某些软件工程师很有吸引力，其拥护者甚至宣称这种方法可以引发软件开发方法的革命；另一些人则对把数学引入软件开发过程持怀疑甚至反对的态度。编者认为，对形式化方法也应该“一分为二”，既不要过分夸大它的优点也不要一概排斥。为了更好地发挥这种方法的长处，下面给出应用形式化方法的几条准则，供读者在实际工作中使用。(1）应该选用适当的表示方法。通常，一种规格说明技术只能用自然的方式说明某一类概念，如果用这种技术描述其不适于描述的概念，则不仅工作量大而且描述方式也很复杂。因此，应该仔细选择一种适用于当前项自的形式化说明技术。(2）应该形式化，但不要过分形式化。目前的形式化技术还不适于描述系统的每个方面。但是，也不能因此就认为完全没必要采用形式化方法。形式化规格说明技术要求我们非常准确地描述事物，因此有助于防止含糊和误解。事实上，如果用形式化方法仔细说明系统中易出错的或关键的部分，则只用适中的工作量就能获得较大回报。(3）应该估算成本。为了使用形式化方法，通常需要事先进行大量的培训。最好预先估算所需的成本并编入预算。(4）应该有形式化方法顾问随时提供咨询。绝大多数软件工程师对形式化方法中使用的数学和逻辑并不很熟悉，而且没受过使用形式化方法的专业训练，因此，需要专家指导和培训。(5）不应该放弃传统的开发方法。把形式化方法和结构化方法或面向对象方法集成起来是可能的，而且由于取长补短往往能获得很好的效果。(6)应该建立详尽的文档。建议使用自然语言注释形式化的规格说明书，以帮助用户和维护人员理解系统。(7）不应该放弃质量标准。形式化方法并不能保证软件的正确性，它们只不过是有助于开发出高质量软件的一种手段。除了使用形式化说明技术外，在系统开发过程中仍然必须一如既往地实施其他质量保证活动。(8）不应该盲目依赖形式化方法。这种方法不是包治百病的灵丹妙药，它们只不过是众多工具中的一种。形式化方法并不能保证开发出的软件绝对正确，例如，无法用形式化方法证明从非形式化需求到形式化规格说明的转换是正确的，因此，必须用其他方法（例如，评审、测试)来验证软件正确性。(9）应该测试、测试再测试。形式化方法不仅不能保证软件系统绝对正确，也不能证明系统性能或其他质量指标符合需要，因此，软件测试的重要性并没有降低。(10）应该重用。即使采用了形式化方法，软件重用仍然是降低软件成本和提高软件质量的惟一合理的方法。而且用形式化方法说明的软件构件具有清晰定义的功能和接口，使得它们有更好的可重用性。4.2有穷状态机4.2.1概念下面通过一个简单例子介绍有穷状态机的基本概念。一个保险箱上装了一个复合锁，锁有三个位置，分别标记为1、2、3，转盘可向左(L)或向右(R)转动。这样，在任意时刻转盘都有6种可能的运动，即1L、1R、2L、2R、3L和3R。保险箱的组合密码是1L、3R、2L，转盘的任何其他运动都将引起报警
4.1.3 应用形式化方法的准则 人们对形式化方法的看法并不一致。形式化方法对某些软件工程师很有吸引力，其拥护 者甚至宣称这种方法可以引发软件开发方法的革命；另一些人则对把数学引入软件开发过程 持怀疑甚至反对的态度。编者认为，对形式化方法也应该“一分为二”，既不要过分夸大它的 优点也不要一概排斥。为了更好地发挥这种方法的长处，下面给出应用形式化方法的几条准 则，供读者在实际工作中使用。 (1) 应该选用适当的表示方法。通常，一种规格说明技术只能用自然的方式说明某一类 概念，如果用这种技术描述其不适于描述的概念，则不仅工作量大而且描述方式也很复杂。 因此，应该仔细选择一种适用于当前项目的形式化说明技术。 (2) 应该形式化，但不要过分形式化。目前的形式化技术还不适于描述系统的每个方面。 但是，也不能因此就认为完全没必要采用形式化方法。形式化规格说明技术要求我们非常准 确地描述事物，因此有助于防止含糊和误解。事实上，如果用形式化方法仔细说明系统中易 出错的或关键的部分，则只用适中的工作量就能获得较大回报。 (3) 应该估算成本。为了使用形式化方法，通常需要事先进行大量的培训。最好预先估 算所需的成本并编入预算。 (4) 应该有形式化方法顾问随时提供咨询。绝大多数软件工程师对形式化方法中使用的 数学和逻辑并不很熟悉，而且没受过使用形式化方法的专业训练，因此，需要专家指导和培 训。 (5) 不应该放弃传统的开发方法。把形式化方法和结构化方法或面向对象方法集成起来 是可能的，而且由于取长补短往往能获得很好的效果。 (6) 应该建立详尽的文档。建议使用自然语言注释形式化的规格说明书，以帮助用户和 维护人员理解系统。 (7) 不应该放弃质量标准。形式化方法并不能保证软件的正确性，它们只不过是有助于 开发出高质量软件的一种手段。除了使用形式化说明技术外，在系统开发过程中仍然必须一 如既往地实施其他质量保证活动。 (8) 不应该盲目依赖形式化方法。这种方法不是包治百病的灵丹妙药，它们只不过是众 多工具中的一种。形式化方法并不能保证开发出的软件绝对正确，例如，无法用形式化方法 证明从非形式化需求到形式化规格说明的转换是正确的，因此，必须用其他方法(例如，评 审、测试)来验证软件正确性。 (9) 应该测试、测试再测试。形式化方法不仅不能保证软件系统绝对正确，也不能证明 系统性能或其他质量指标符合需要，因此，软件测试的重要性并没有降低。 (10) 应该重用。即使采用了形式化方法，软件重用仍然是降低软件成本和提高软件质 量的惟一合理的方法。而且用形式化方法说明的软件构件具有清晰定义的功能和接口，使得 它们有更好的可重用性。 4.2 有穷状态机 4.2.1 概念 下面通过一个简单例子介绍有穷状态机的基本概念。 一个保险箱上装了一个复合锁，锁有三个位置，分别标记为 1、2、3，转盘可向左(L) 或向右(R)转动。这样，在任意时刻转盘都有 6 种可能的运动，即 1L、1R、2L、2R、3L 和 3R。 保险箱的组合密码是 1L、3R、2L，转盘的任何其他运动都将引起报警
状态集J：（保险箱锁定，A，B，保险箱解锁，报警。输入集K：（1L，1R，2L，2R，3L，3R。转换函数T：如表4.1所示。初始态S：保险箱锁定。终态集F：（保险箱解锁，报警}。如果使用更形式化的术语，一个有穷状态机可以表示为一个5元组(，K，T，S，F)，其中：是一个有穷的非空状态集；K是一个有穷的非空输入集：T是一个从(I-F)XK到」的转换函数；SEJ，是一个初始状态；FJ，是终态集。1L3R2L初始态保险箱锁定AB终态保险箱解锁转盘的转盘的转盘的任何其任何其任何其它移动它移动它移动-报警终态图1保险箱状态图有穷状态机的概念在计算机系统中应用得非常广泛。例如，每个菜单驱动的用户界面都是一个有穷状态机的实现。一个菜单的显示和一个状态相对应，键盘输入或用鼠标选择一个图标是使系统进入其他状态的一个事件。状态的每个转换都具有下面的形式：当前状态（菜单）+事件（所选择的项）下个状态。为了对一个系统进行规格说明，通常都需要对有穷状态机做一个很有用的扩展，即在前述的5元组中加入第6个组件一一谓词集P，从而把有穷状态机扩展为一个6元组，其中每个谓词都是系统全局状态Y的函数。转换函数T现在是一个从(J-F)XKXP到」的函数。现在的转换规则形式如下：当前状态（菜单）+事件（所选择的项）+谓词下个状态。4.2.2例子为了具体说明怎样用有穷状态机技术表达系统的规格说明，现在用这种技术给出大家熟悉的电梯系统的规格说明。首先给出用自然语言描述的对电梯系统的需求：在一幢m层的大厦中需要一套控制n部电梯的产品，要求这n部电梯按照约束条件C1，C2和C3在楼层间移动。C1：每部电梯内有m个按钮，每个按钮代表一个楼层。当按下一个按钮时该按钮指示灯亮，同时电梯驶向相应的楼层，到达按钮指定的楼层时指示灯熄灭。C2：除了大厦的最低层和最高层之外，每层楼都有两个按钮分别请求电梯上行和下行。这两个按钮之一被按下时相应的指示灯亮，当电梯到达此楼层时灯熄灭，电梯向要求的方向
状态集 J：｛保险箱锁定，A，B，保险箱解锁，报警｝。 输入集 K：｛1L，1R，2L，2R，3L，3R｝。 转换函数 T：如表 4.1 所示。 初始态 S：保险箱锁定。 终态集 F：｛保险箱解锁，报警｝。 如果使用更形式化的术语，一个有穷状态机可以表示为一个 5 元组(J，K，T，S，F)，其 中： J 是一个有穷的非空状态集； K 是一个有穷的非空输入集； T 是一个从(J-F)×K 到 J 的转换函数； S∈J，是一个初始状态； F J，是终态集。 图 1 保险箱状态图 有穷状态机的概念在计算机系统中应用得非常广泛。例如，每个菜单驱动的用户界面都 是一个有穷状态机的实现。一个菜单的显示和一个状态相对应，键盘输入或用鼠标选择一个 图标是使系统进入其他状态的一个事件。状态的每个转换都具有下面的形式： 当前状态〔菜单〕+事件〔所选择的项〕 下个状态。 为了对一个系统进行规格说明，通常都需要对有穷状态机做一个很有用的扩展，即在前 述的 5 元组中加入第 6 个组件——谓词集 P，从而把有穷状态机扩展为一个 6 元组，其中每 个谓词都是系统全局状态 Y 的函数。转换函数 T 现在是一个从(J-F)×K×P 到 J 的函数。现在 的转换规则形式如下： 当前状态〔菜单〕+事件〔所选择的项〕+谓词 下个状态。 4.2.2 例子 为了具体说明怎样用有穷状态机技术表达系统的规格说明，现在用这种技术给出大家熟 悉的电梯系统的规格说明。首先给出用自然语言描述的对电梯系统的需求： 在一幢 m 层的大厦中需要一套控制 n 部电梯的产品，要求这 n 部电梯按照约束条件 C1， C2 和 C3 在楼层间移动。 C1：每部电梯内有 m 个按钮，每个按钮代表一个楼层。当按下一个按钮时该按钮指示 灯亮，同时电梯驶向相应的楼层，到达按钮指定的楼层时指示灯熄灭。 C2：除了大厦的最低层和最高层之外，每层楼都有两个按钮分别请求电梯上行和下行。 这两个按钮之一被按下时相应的指示灯亮，当电梯到达此楼层时灯熄灭，电梯向要求的方向
移动。C3：当对电梯没有请求时，它关门并停在当前楼层。现在使用一个扩展的有穷状态机对本产品进行规格说明。这个问题中有两个按钮集。n部电梯中的每一部都有m个按钮，一个按钮对应一个楼层。因为这m×n个按钮都在电梯中，所以称它们为电梯按钮。此外，每层楼有两个按钮，一个请求向上，另一个请求向下，这些按钮称为楼层按钮。电梯按钮的状态转换图如图4.2所示。令EB(e,f)表示按下电梯e内的按钮并请求到f层去。EB(e,f)有两个状态，分别是按钮发光(打开)和不发光(关闭)。更精确地说，状态是：EBON(e,f)：电梯按钮(e,f)打开EBOFF(e,f)：电梯按钮(e,f)关闭如果电梯按钮(e,f)发光且电梯到达f层，该按钮将熄灭。相反如果按钮熄灭，则按下它时，按钮将发光。上述描述中包含了两个事件，它们分别是：EBP(e,f)：电梯按钮(e,f)被按下EAF(e,f)：电梯e到达f层EBP(e, f)EBOFF(e,f)EEON(e,)EAF(e,)图2电梯按钮的状态转换图FBpOMd,J)FBOnd,J)FBOFF(d,)EAF(l, n,J)图3楼层按钮的状态转换图为了定义与这些事件和状态相联系的状态转换规则，需要一个谓词V(e,f)，它的含义如下：V(e,f)：电梯e停在f层如果电梯按钮(e,f)处于关闭状态（当前状态），而且电梯按钮(e,f)被按下（事件），而且电梯e不在f层（谓词），则该电梯按钮打开发光（下个状态）。状态转换规则的形式化描述如下：EBOFF(e,f)+EBP(e,f)+not V(e,f)EBON(e,f)反之，如果电梯到达f层，而且电梯按钮是打开的，于是它就会熄灭。这条转换规则可以形式化地表示为：EBON(e,f)+EAF(e,f) EBOFF(e,f)接下来考虑楼层按钮。令FB(d,f)表示f层请求电梯向d方向运动的按钮。楼层按钮的状态如下：FBON(d,f)：楼层按钮(d,f)打开FBOFF(d,f)：楼层按钮(d,f)关闭
移动。 C3：当对电梯没有请求时，它关门并停在当前楼层。 现在使用一个扩展的有穷状态机对本产品进行规格说明。这个问题中有两个按钮集。n 部电梯中的每一部都有 m 个按钮，一个按钮对应一个楼层。因为这 m×n 个按钮都在电梯 中，所以称它们为电梯按钮。此外，每层楼有两个按钮，一个请求向上，另一个请求向下， 这些按钮称为楼层按钮。 电梯按钮的状态转换图如图 4.2 所示。令 EB(e,f)表示按下电梯 e 内的按钮并请求到 f 层 去。EB(e,f)有两个状态，分别是按钮发光(打开)和不发光(关闭)。更精确地说，状态是： EBON(e,f)：电梯按钮(e,f)打开 EBOFF(e,f)：电梯按钮(e,f)关闭 如果电梯按钮(e,f)发光且电梯到达 f 层，该按钮将熄灭。相反如果按钮熄灭，则按下它 时，按钮将发光。上述描述中包含了两个事件，它们分别是： EBP(e,f)：电梯按钮(e,f)被按下 EAF(e,f)：电梯 e 到达 f 层 图 2 电梯按钮的状态转换图 图 3 楼层按钮的状态转换图 为了定义与这些事件和状态相联系的状态转换规则，需要一个谓词 V(e,f)，它的含义如 下： V(e,f)：电梯 e 停在 f 层 如果电梯按钮(e,f)处于关闭状态〔当前状态〕，而且电梯按钮(e,f)被按下〔事件〕，而且 电梯 e 不在 f 层〔谓词〕，则该电梯按钮打开发光〔下个状态〕。状态转换规则的形式化描述 如下： EBOFF(e,f)+EBP(e,f)+not V(e,f) EBON(e,f) 反之，如果电梯到达 f 层，而且电梯按钮是打开的，于是它就会熄灭。这条转换规则可 以形式化地表示为： EBON(e,f)+EAF(e,f) EBOFF(e,f) 接下来考虑楼层按钮。令 FB(d,f)表示 f 层请求电梯向 d 方向运动的按钮。 楼层按钮的状态如下： FBON(d,f)：楼层按钮(d,f)打开 FBOFF(d,f)：楼层按钮(d,f)关闭
如果楼层按钮已经打开，而且一部电梯到达f层，则按钮关闭。反之，如果楼层按钮原来是关闭的，被按下后该按钮将打开。这段叙述中包含了以下两个事件。FBP(d,f)：楼层按钮(d,f)被按下EAF(1...n,f)：电梯1或...或n到达f层其中1...n表示或为1或为2...或为n。为了定义与这些事件和状态相联系的状态转换规则，同样也需要一个谓词，它是S(d,e,f)，它的定义如下。S(d,e,f)：电梯e停在f层并且移动方向由d确定为向上(d=U)或向下(d=D)或待定(d=N)。这个谓词实际上是一个状态，形式化方法允许把事件和状态作为谓词对待。使用谓词S(d,e,f)，形式化转换规则为：FBOFF(d,f)+FBP(d,f)+not S(d,1...n,f)FBON(d,f)FBON(d,f)+EAF(1...n,f)+S(d,1...n,f))FBOFF(d,f)其中，d=UorD。也就是说，如果在f层请求电梯向d方向运动的楼层按钮处于关闭状态，现在该按钮被按下，并且当时没有正停在f层准备向d方向移动的电梯，则该楼层按钮打开。反之，如果楼层按钮已经打开，且至少有一部电梯到达f层，该部电梯将朝d方向运动，则按钮将关闭。在讨论电梯按钮状态转换规则时定义的谓词V(e,f)，可以用谓词S(d,e,f)重新定义如下：V(e,f)=S(U,e,f)or S(D,e,f)orS(N,e,f)定义电梯按钮和楼层按钮的状态都是很简单、直观的事情。现在转向讨论电梯的状态及其转换规则，就会出现一些复杂的情况。一个电梯状态实质上包含许多子状态。下面定义电梯的3个状态：M(d,e,f)：电梯e正沿d方向移动，即将到达的是第f层S(d,e,f)：电梯e停在f层，将朝d方向移动(尚未关门)W(e,f)：电梯e在f层等待（已关门)其中S(d,e,f)状态已在讨论楼层按钮时定义过，但是，现在的定义更完备一些
如果楼层按钮已经打开，而且一部电梯到达 f 层，则按钮关闭。反之，如果楼层按钮原 来是关闭的，被按下后该按钮将打开。这段叙述中包含了以下两个事件。 FBP(d,f)：楼层按钮(d,f)被按下 EAF(1.n,f)：电梯 1 或.或 n 到达 f 层 其中 1.n 表示或为 1 或为 2.或为 n。 为了定义与这些事件和状态相联系的状态转换规则，同样也需要一个谓词，它是S(d,e,f)， 它的定义如下。 S(d,e,f)：电梯 e 停在 f 层并且移动方向由 d 确定为向上(d=U)或向下(d=D)或待定(d=N)。 这个谓词实际上是一个状态，形式化方法允许把事件和状态作为谓词对待。 使用谓词 S(d,e,f)，形式化转换规则为： FBOFF(d,f)+FBP(d,f)+not S(d,1.n,f) FBON(d,f) FBON(d,f)+EAF(1.n,f)+S(d,1.n,f) FBOFF(d,f) 其中，d=UorD。 也就是说，如果在 f 层请求电梯向 d 方向运动的楼层按钮处于关闭状态，现在该按钮被 按下，并且当时没有正停在 f 层准备向 d 方向移动的电梯，则该楼层按钮打开。反之，如果 楼层按钮已经打开，且至少有一部电梯到达 f 层，该部电梯将朝 d 方向运动，则按钮将关闭。 在讨论电梯按钮状态转换规则时定义的谓词 V(e,f)，可以用谓词 S(d,e,f)重新定义如下： V(e,f)=S(U,e,f)or S(D,e,f)or S(N,e,f) 定义电梯按钮和楼层按钮的状态都是很简单、直观的事情。现在转向讨论电梯的状态及 其转换规则，就会出现一些复杂的情况。一个电梯状态实质上包含许多子状态。 下面定义电梯的 3 个状态： M(d,e,f)：电梯 e 正沿 d 方向移动，即将到达的是第 f 层 S(d,e,f)：电梯 e 停在 f 层，将朝 d 方向移动(尚未关门) W(e,f)：电梯 e 在 f 层等待(已关门) 其中 S(d,e,f)状态已在讨论楼层按钮时定义过，但是，现在的定义更完备一些