面向模型的变换型软件开发方法研究* 北京大学 张乃孝 许卓群 屈婉玲 On the Model-Oriented Transformational Method of Software Development Zhang Naixiao Xu Zhuoqun Qu Wanling (Peking University, Beijing 100871) Abstract From the fact that the software models are objects of researching of software development methods, the issues of value-oriented models and object-oriented models are discussed. We believe that the models which combine values and objects will be powerful tools using in the research. A kernel language developed from the view of data abstraction is proposed for building the hierarchical models. The transitions between models are implemented according to the idea of program transformation. The efficiency of model transitions is improved by partial implementation. These are the basic principles of the model-oriented transformational method of software development. Key Words: Model-Oriented, Data Abstraction, Program Transformation, Partial Implementation. 摘要 本文从软件方法学研究的对象为软件模型这一基本事实出发,分析了面向值 的模型和面向对象的模型的各自特点, 指出结合值与对象的模型应是软件方法学研 究的趋势; 并根据数据抽象的观点提出一种构造分层模型的核心语言, 建议采用程 序变换的思想实现不同层模型之间的转换, 采用部分实现的思想提高模型转换的效 率, 这些思想的结合便形成“面向模型的变换型软件开发方法”的精髓。 关键字: 面向模型, 数据抽象, 程序变换, 部分实现. ------------------------------------------------- * 本项研究得到国家自然科学基金和863的资助 前言 一切科学研究都是以客观事物为对象。通过对个别事物的研究而总结出的一般 事实和规则，便形成这一领域的理论。理论的一种解释称作它的一个模型(model)， 如果在这个模型上，该理论中的所有事实和规则都能解释为真[16]。模型是研究理 论的重要工具，也是检验理论价值的主要手段。 计算机发展到今天，几乎能应用到所有领域，其主要原因在于几乎所有实用的 理论都可以用计算机来模拟, 这种模拟是通过程序和软件的方式来完成. 换句话说, 程序和软件都是计算机中对客观事物建立的模型. 然而, 在软件本身的理论研究中, 我们所关心的不是某一个具体软件的模型, 而是一般软件的(抽象)模型. §⒈ 模型的研究应走值和对象相结合的道路 一个软件的模型包含对这个软件所要模拟的对象及其操作的描述。目前对软件 模型的描述有两种典型的方式，一种称为“面向值的(value-oriented)”，另一种 称为“面向对象的(object-oriented)”。 函数型程序设计(例如FP)提供了一种典型的面向值的模型[1],它用“值”来模 拟一切实际对象。对值的处理用函数来表示，函数也是值，它由参数的值唯一确定。 函数型方法通过对函数(常量是零目函数)的不同组合方式来处理已有的数据和程序， 构造出新的程序(软件)[14]。这种模型具有良好的数学性质，便于证明生成程序(软 件)的正确性，但是用这种纯数学的模型模拟实际问题有时不够直观和自然, 另外这 种纯数学模型的建立和理解都需要程序员具有较好的数学修养。对目前大多数程序 员而言尚有一定困难。 面向对象的思想采用计算机中的“对象”来模拟实际问题中的对象[15]。在典 型的面向对象的程序设计语言(例如Smalltalk)中，一切都是对象。对象通过“消息 (message)”来处理，而处理的实体由“方法(method)”决定。方法不同于函数，因 为方法运用的效果不仅仅取决于消息中的参数，还依赖于对象自身的“状态”这种 面向对象的风格在许多情况下比值要自然、直观, 但是数学性质不如面向值的模型 清晰, 实现起来系统开销也比较大, 特别是为了实现“动态多态性 (dynamic poly- morphism)”,采用“动态联接技术 (dynamic binding)”，将许多工作留在运行时 进行，使目标软件的运行效率受到较大影响。 事实上，值与对象的概念从计算机一诞生便已紧密地结合在一起。值和地址是 计算机中最基本的两个概念，运算器和存储器是计算机中两个最重要的部件，这些 都标志着对值和对象处理的结合。在大多数高级语言中，常量和变量共存，表达式 和赋值语句密切配合。就是在著名的软件开发的形式方法VDM和Z中，值与对象也是 共存的，它们为软件建立的抽象模型实质上是一种对象模型(VDM中称之为“基于状 态的数据类型”)，而在刻画模型相关的状态时，它们又都采用值的模型 (VDM中称 之为“函数数据类型”，例如集合、序列、元组等)[3]。 我们提出面向模型的概念, 只强调模型, 而不限制模型的表达方法, 其目的是 试图将面向对象与面向值的方法紧密结合于一体,使模型具有更强的灵活性和适应性。 过去的问题在于, 忽略了值与对象的本质区别, 在计算机, 语言和软件中混淆了这 两个重要的概念, 结果使程序设计复杂化。通过十多年关于方法学的深入研究, 人 们不仅认识到值与对象的区别, 同时也认识到它们都是程序中不可缺少的抽象表示 形式 [11]。在新的认识基础上将两者结合起来是软件模型发展的必然。 §⒉ 数据抽象是构造模型的主要手段 “数据抽象(data abstraction)”是程序设计方法学中一个极为重要的思想[4], 是七十年代方法学研究的主要成果。 众所周知, 算法+数据结构=程序, 程序的复杂性主要依赖于数据表示的复杂性 和在该表示上实现操作的复杂性。但是随着程序规模的扩大, 其复杂性随数据复杂 性飞速增长, 结果导致了软件危机。模块化的思想, 使用了抽象与分解的原则。每 个模块的设计属于小型程序的设计(programming in the small)问题, 主要研究小 姵绦蛑械氖萁峁购退惴*, 产生的结果是一个具有独立功能的程序部件。大型程序 设计(programming in the large)以这些模块为基础, 关心的重点是如何把软件系 统分解成互相联系的若干模块, 研究如何定义模块的界面, 如何管理模块和使用模 块的问题。 抽象数据类型(abstract data type -- ADT)是数据抽象发展的最新阶段[17], 一个抽象数据类型不仅定义了所关心的值的集合, 同时也包括对这些值的操作的集 合。按抽象数据类型观点分解模块, 产生了以数据为中心的数据抽象模块 (而不是 功能抽象模块)。这种模块体现了“信息隐蔽” 的原则, 只给用户提供一个使用的 界面, 而将模块的实现细节隐蔽起来。抽象数据类型的思想将类型与模块统一起来, 模块之间的界面不再是复杂的数据, 而是在类型上定义的那些操作。使用ADT的思 想,程序设计者可以定义自己需要的各种类型, 并实现这些类型上的各种操作。 由于这种数据抽象的思想可以反复使用, 所以我们可以开发一个分层的类型系 统, 以这种类型系统为依托,来描述软件的抽象模型,使程序员可以在足够抽象的层 次上分解软件, 并将实现抽象的信息保存在软件之中, 然后通过一步一步的模型转 换工作, 得到越来越具体的软件模型, 直到最终可直接执行的软件。显然这样开发 的软件结构清晰, 易于阅读和维护, 正确性也容易证明。 为支持这种模型分层的思想,在我们的核心语言中, 不仅提供一组基本的类型, 同时还提供一套有力的类型扩充功能, 使用户能自己定义需要的各种抽象数据类型, 为了同时支持对值和对象的处理,类型上的操作可以定义成函数型的(表达式),也可 以定义成基于状态的(语句)。为了防止由于对值和对象的滥用所带来的副作用, 在 语言中严格区分值与变量的概念, 并且使用Dijkstra-Gries风格的(过程型)的控制 结构[5,6],使抽象程序的语义尽量清晰, 正确性证明也比较简单。这种语言每经过 一次扩充, 便向用户提供了一个新的使用界面。用这个语言作核心建立的开发环境 是一棵语言树, 不同的用户可以在这棵树的不同结点上进行工作, 并可根据软件模 型的需要修改原来的结点或生成新的结点, 而这个树的每个叶结点所对应的便是一 个面向某类应用领域的用户专用语言。在这个意义下软件开发、语言扩展与环境扩 展都统一起来了。 §⒊ 程序变换是实现模型转换的有效方法 数据抽象为构造软件模型提供了有力的工具, 首先用户可以使用一种足够抽象 的专用语言书写出软件的一个抽象模型( 形式规范 specification),然后从这个规 范出发, 开发出可运行的软件。在VDM中这个过程称为“模型规范的具体化”,它是 分成两步来完成的: 第一步是数据的精化, 将抽象类型描述的系统状态表示成计算 机能够接受的形式；第二步是运算的分解, 即将运算的规范分解, 推导出在具体计 算机能接受的状态下可以正确运行的程序[10]。但是由于经过精化后的系统状态越 具体, 状态不变式也越复杂, 使相应状态上的运算规范也越难以分解, 所以用这种 方法时, 被开发系统本身的复杂度并未取得实质性的降低。从程序设计语言的角度 看, 要实现一个用专用语言书写的抽象模型, 相当于实现这个语言的编译(或解释) 系统, 或者相当于给出模型中用户定义的抽象类型的实现模块。 “程序变换(program transformation)”是软件开发的另一种方法, 研究程序 变换的最初动机是希望在函数型程序与过程型程序之间建立起桥梁，其基本思想是 把程序设计的过程分为生成阶段和改进阶段。首先通过对问题的分析制定形式规范, 并生成一个程序，通常是一种函数型的“递归方程(recursion equation)”; 然后 通过一系列保持正确性的源程序到源程序的变换, 把函数型风格转换成过程型风格, 并进行数据结构和算法的求精, 最终得到一个有效的面向过程的程序[12]。这种变 换过程是一种严格的形式推导过程, 所以只需对变换前的程序的规范加以验证, 变 换后的程序的正确性将由变换法则的正确性来保证。 目前最有名的程序变换系统是由西德慕尼黑计算中心 F.L.Bauer教授领导的研 究组研制的CIP。这个系统采用人-机交互方式, 通过人的干预来控制变换过程中不 确定的选择, 达到提高系统效率和缩小系统规模的目的。尽管如此, 由于要考虑通 用性问题, 系统中需要支持一个适于描述各级程序的“广谱语言 ( Wide Spectrum Language)”[2]及其庞大的编译系统; 为了提高目标程序的效率, 系统又必须提供 大量的用于各级程序之间转换的规则, 所以变换系统仍然十分复杂, 而能真正完成 的变换问题的规模一直停留在实验性小型程序上, 加上递归方程表达问题的能力有 娨欢ň窒扌*, 所以CIP系统的研究虽然已有十多年的历史, 但仍未真正实用。 美国康乃尔大学D.Gries教授领导的研究组从1988年开始,在美国科学基金的资 助下,从事一种新的变换型语言“Polya”的研究。在该语言中第一次把程序变换功 能作为语言机制引入, 使用户能自己定义变换的功能和控制变换的实现[7]。Polya 语言研究的成功, 有希望为各种专用的变换系统提供一个统一的生成环境, 把程序 变换系统的复杂性降低; 使变换型方法从理论研究向实用阶段过渡。 我们从Polya语言的设计思想中吸取了这种灵活的定义变换和控制变换的机制, 从Ada语言中吸取了类型定义与类型实现分离的思想,在考虑模型的转换时采用变换 型方法。用这种方法每步将一种或几种抽象类型的数据表示精化, 同时用变换规则 把这些类型上的运算分解, 以避免传统面向模型方法(VDM) 的开发过程中, 数据精 化与运算分解分离所产生的弊病。 通过变换规则控制和实现抽象数据类型的思想是一种大胆的尝试, 从变换系统 处理的对象是各类源程序的角度看, 这种变换与函数型程序设计一样, 都是研究程 序的构造、分解、生成和转换; 但从处理的方法看, 把类型实现的知识表示成变换 规则, 反复通过“规则匹配─变量替换─生成目标─置换源程序”的方式完成变换, 这种变换又与逻辑型程序设计相似[20]。 面向模型的变换型软件开发方法, 根据数据抽象的原则将语言分层, 不同的用 户处理不同的问题时, 可以定义不同的语言(簇)。在专用的语言(簇)内考虑源程序 之间的变换问题, 比在广谱语言中考虑变换要简单得多; 同时, 我们按抽象类型将 变换规则分组, 把同一类型运算的变换规则封装在一起, 暂时称之为“变换模块”。 一个变换模块中给出一种抽象类型的数据表示和在这种表示下运算的变换规则。这 种处理的结果使大型系统的开发过程可以从抽象模型出发, 经过多次保持正确性的 源─源变换, 最终得到可以运行的具体系统。这时每次变换只要考虑一个或若干个 变换模块中的规则, 逐步实现高层模型到低一层模型的正确转换。通过这种方法使 大型系统的变换复杂度大大降低。特别有意义的是: 这些按抽象类型封装起来的变 换模块, 实际上组成了一种“可重用的程序部件 (reusable unit)”, 与传统重用 部件不同的是: 通常所研究的都是程序代码(例如子程序)的重用, 而变换模块能提 供生成代码的规则的重用。为了提高变换模块的可重用性, 在变换模块的定义中可 以引入包括类型在内的多种参数化描述[18]。 * §⒋ 部分实现是提高模型变换效率的根本途径 软件运行效率是软件能否实用的关键, 许多新的方法学理论上非常完美, 但至 今未能大量应用, 其中一个主要障碍就是效率问题。 “部分实现(partial implementation)”是对抽象表示中所关心的部分运算提 供的一种具体实现方法。对一种抽象表示的不同部分实现适用于不同应用。在程序 的形式开发中, 对某些抽象表示使用适当的部分实现通常比它的全部实现更适合。 这不仅表现了极大的可重用性, 也便于实现早期的“原型(prototype)”[13]。 例如: 在我们构造软件的模型时, 经常用到“集合”这个抽象表示, 而关于集 合的运算可以有: 求并集、交集、差集以及在集合中插入、删除、检索等。如果完 全实现集合类型, 则要设计一种通用的集合表示, 并在这种表示上实现其所有的运 算。但无论哪一种表示都只能使其中某些运算有效进行, 若以此为标准处理各种集 合变量, 其结果对某些(也许是多数)应用并不是最佳的。但如果我们知道每个集合 变量所表示的对象和具体用法后, 情况就可以改变。例如某个集合变量表示一个字 典, 而字典的操作大量是检索, 较少执行插入和删除, 那么我们选用一种树型表示 (例如二叉排序树、AVL树、字符树等)也许是适当的。进一步讲,若该字典是一静态 结构, 则采用一种适当的散列表来表示也许更好[19]. 我们采用部分实现的思想, 把抽象类型的定义和实现进一步分离。在类型定义 时, 仅定义类型名 (包括参数)和所有该类型上运算 (包括零目运算─常量)的文法 (包括抽象文法和具体文法), 而把这个类型的各种部分实现分别用不同的变换模块 来描述。同一个类型的不同实现中包含的运算可以相同, 也可以不同; 同一运算在 不同的实现中不仅可以采用不同的算法, 甚至可以具有完全不同的效果。例如对抽 象“序列”类型的一种部分实现可以相当于“栈”, 而另一种相当于“队列”。使 用者根据程序中不同变量的用法, 可以指定抽象类型的不同实现模块, 类型相同的 不同变量允许采用不同的部分实现技术。这样, 一方面通过类型定义向用户提供足 姽怀橄蟮谋硎*, 以提高语言的层次及编程的效率; 另一方面通过引入新的变换模块 控制抽象变量的实现, 提高目标程序的效率。 这种类型定义与实现分离的作法也起到将程序设计语言与规范说明语言的形式 统一的作用。作为规范说明语言 ,只需要定义足够抽象的描述工具, 而不必考虑这 些抽象表示的实现。例如在VDM的规范说明语言中,集合、映射、序列和组合类型为 其描述工具。包含这四种类型定义的语言形式上具有与 VDM等同的描述能力, 用它 来书写规范时, 系统能根据类型定义中的语法属性检查规范的语法, 至于是否能使 所描述的软件直接执行并不属规范描述语言的要求。但是如果我们根据部分实现的 思想, 对规范中的所有抽象变量都提供一种实现方法 (一个变换模块), 这个规范 便成为可执行的程序, 规范语言即成了一种高级的程序设计语言, 这时的系统即为 软件规范提供了一个快速原型。 结论 方法学的研究既是一种思想方法和工作方式的研究, 同时也是对支持这种方法 学的语言、工具和环境的研究。面向模型的变换型软件开发方法希望向软件工作者 提供一种简单且有效的开发软件的方法, 包括: 第一, 提供一个支持这种方法学的核心语言簇。用这个语言簇可以生成多种层 次的规范描述语言、程序设计语言, 用它们来编程可以使编程效率大大提高。 第二, 提供一种使用核心语言开发软件的方法。这是一种系统的严格的开发方 法, 用它可以开发出结构清晰、正确、可靠、可维护并且十分有效的目标软件。 第三, 提供一个可扩充模块库, 用于存放可重用的变换模块。 为此必须解决许多十分棘手的问题, 例如: 程序变换在程序语言中的表示方法; 程序变换系统的支撑算法; 分层类型系统的功能设计; 类型检查和类型推理的核心 算法; 变换模块库的逻辑结构和存储结构; 变换模块之间的相关性和继承性; 核心 语言的语义及其它有关的理论基础等。在研究中，我们的原则是使这种开发方法尽 可能思想清晰、结构简单, 而目标是降低系统开发的复杂度。 著名计算机科学家 David Gries、C.A.R.Hoare和K.W.Kennedy等人在给美国科 学基金委员会的一份报告中指出:“通常, 重大的突破并不来自一个新概念的创立, 而来自于在各种预期的目标之间找到一个正确的平衡。”他们认为目前计算机科学 的发展已经达到了这种水平: 有可能用统一的理论来考虑软件系统的各种特性和软 件工程的各种技术, 并使之提高一大步, 使今后软件工程的活动能在一个统一的、 适当的软件环境中进行[8]。 参考文献 *[1] J.Backus Can Programming be Liberated from the VonNeumann Style? Comm. ACM, August, 1978 [2] F.L.Bauer etc. Towards a Wide Spectrum Language to Swapport Program Specification and Program Development LNCS 69, Springer-Verlag 1979 [3] D.Bjoner,C.B.Jones The Vinenna Development Method: The Meta-language LNCS 61, 1978 [4] L.Cardelli and P.Wegner On Understanding Types,Data Abstraction and Polymorphism ACM Computing Surveys 1985 [5] E.W.Dijkstra A Discipline of Programming Prentice Hall, Englewood Cliffs, New Jersey, 1976 [6] D.Gries * The Science of Programming Springer_Verlag, 1981 [7] D.Gries and D.Volpano The Transform--A new language construct Tech. Rpt. CS Dept. Cornell Univ. 1989 [8] J.E.Hopcroft and K.W. Kennedy Computer Science--Achievements and Opportunities Society for Inductrial and Applied Math. 1989 [9] E.Horowitz Fundamentals of Programming Languages Springer-Verlag 1983 [10] C.B.Jones Systematic Software Development Using VDM PHI Ltd. 1990 [11] B.J.Maclennan Values and Objects in Programming Language SIGPLAN Notices, Dec.1982 p70-79 [12] H.A.Partsch etc. Specification and Transformation of Programming Springer-Verlag 1990 [13] J.Prins Partial Implementations in Program Derivation Ph.d. Thesis, CS Dept. Cornell Univ, 1987 [14] C.Reade Elements of Functional Programming Addison-Wesley 1989 [15] D.Robson Object-Oriented Software System Byts, Aug. 1981. [16] J.Woodcook,M.Loomes Software Engineering Mathematics Pitman Publishing 1988 [17] 陈火旺等 程序设计方法学基础 湖南科学技术出版社 1987 [18] 张乃孝 程序变换在程序语言中的一种表示 软件学报 (即将发表) [19] 张乃孝等 数据结构基础 北京大学出版社 1991 [20] 张乃孝 程序变换过程的分析与设计 计算机学报 <即将发表>