（计算机应用技术专业论文）基于逻辑的软件演化执行引擎研究.pdf

摘要 软件演化是指在软件系统的生命周期中软件维护和软件更新的 动态行为。随着软件系统规模的不断扩大以及需求的不断变化，对软 件模型演化能力的要求也越来越高。目前，软件模型的演化方法主要 采用图形的方式来处理。这种描述方式比较复杂，表达能力有限。特 别是当软件系统规模增大时，图变换方式的表达和处理能力明显不 足，速度和效率也明显下降。 论文通过分析软件模型演化的图变换技术，提出一种基于带属性 类型图的软件结构形式化描述方法，并进一步将其转化成谓词描述， 给出两者互转化机制。这种方式既保证图形化特征又降低逻辑表达式 描述的复杂度，提高了演化效率。在谓词逻辑的基础上，提出了软件 演化操作语言s e o l ，以描述软件演化操作。同时构建了s e o l 语言 的执行机制，从而最终达到软件模型演化的目的。论文针对s e o l 语 言，在e c l i p s e 平台下以插件的形式设计并实现了一个针对软件演化 的执行引擎工具。该工具采用三层模型设计思想，使整个系统结构清 晰并具有良好的扩展性。 最后，论文通过分析软件重构经典案例邮件系统的演化，论述了 邮件系统演化的执行过程。从实践上证明了基于逻辑的软件演化方法 的可行性和正确性。 关键词软件演化，带属性类型图，谓词逻辑，软件演化操作语言 a b s t r a c t s o f t w a r ee v o l u t i o ni sad y n a m i ca c t i v i t yo fs o f t w a r em a i n t e n a n c ea n d u p d a t ei nt h el i f ec y c l eo fs o f t w a r es y s t e m w i t ht h es c a l e so fs o f t w a r e s y s t e me x p a n d i n ga n dr e q u i r e m e n tc h a n g i n g ，i t i se x p e c t e dt h a tt h e e v o l u t i o na b i l i t yo fs o f t w a r em o d e lb e c o m e ss t o n g e r a tp r e s e n t , e v o l u t i o no fs o f t w a r em o d e lm a i n l ya d o p t st h ew a yo fg r a p h t h i s d e s c r i p t i o nw a yi sc o m p l e x a n di t s d e s c r i b i n ga b i l i t y i sl i m i t e d e s p e c i a l l yw h e nt h e s c a l e so fs o f t w a r es y s t e me x p a n d ，d e s c r i b i n ga n d e x e c u t i n ga b i l i t yo fg r a p h t r a n s f o r m a t i o na sw e l la si t s s p e e da n d e f f i c i e n c ye v i d e n t l yd e s c e n d t h i st h e s i sp r o p o s e sak i n d o ff o r m a l i z e dw a yf o rd e s c r i b i n gs o f t w a r e s t r u c t u r eu s i n ga t t r i b u t e dt y p eg r a p h ( a t g ) b ya n a l y s i n gt h eg r a p h t r a n s f o r m a t i o nt e c h n o l o g yi nt h ef i e l do fs o f t w a r em o d e le v o l u t i o n f u r t h e r , i ti st r a n s f o r m e di n t ol o g i cd e s c r i p t i o n a n dt h et r a n s f o r m a t i o n m e c h a n i s mb e t w e e nt h e mi sg i v e n i nt h i sw a y , i tc o u l dn o to n l yh o l dt h e g r a p hp r o p e r t yb u ta l s or e d u c et h ec o m p l e x i t yo fl o g i ce x p r e s s i o na n d u l t i m a t e l yr a i s et h ee v o l u t i o ne f f i c i e n c y b a s e do np r e d i c a t el o g i c ，t h i s t h e s i sp r o p o s e ss o f t w a r ee v o l u t i o no p e r a t i o n a ll a n g u a g e ( s e o l ) f o r d e s c r i b i n gs o f t w a r ee v o l u t i o no p e r a t i o n s ，a n db u i l d ss e o u se x e c u t i o n m e c h a n i s mf o ra c h i e v i n gt h ep r o c e s so fe v o l u t i o n t h i st h e s i sd e s i g n sa n d r e a l i z e sa ne x e c u t i o ne n g i n ef o rs o f t w a r ee v o l u t i o nb a s e do ns e o lu n d e r t h ee c l i p s ep l a t f o r ma sap l u g - i n t h es y s t e mh a sac l e a rs t r u c t u r ea n d g o o de x p a n s i b i l i t yb yt a k i n ga d v a n t a g eo fm v c a r c h i t e c t u r em o d e l i n g i nt h ee n d t h i st h e s i sa n a l y s e st h ee v o l u t i o np r o c e s so f m a i ls y s t e m w h i c hi sac l a s s i c a lc a s ei nt h ef i e l do fs o f t w a r er e f a c t o r i n g ，a n da d d r e s s e s t h ee x e c u t i o ne v o l u t i o np r o c e s so fm a i ls y s t e m i tp r a c t i c a l l yp r o v e st h e f e a s i b i l i t ya n dv a l i d i t yo fs o f t w a r ee v o l u t i o nb a s e do nl o g i c k e yw o r d ss o f t w a r ee v o l u t i o n ，a t t r i b u t e dt y p eg r a p h ，p r e d i c a t e l o g i c ，s o f t w a r ee v o l u t i o no p e r a t i o n a ll a n g u a g e 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：盆莹日期：皿链月卫日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者躲盟导师签名伽嘶期：轼年d 牟日 ， 硕士学位论文第一章绪论 1 1 研究背景与意义 第一章绪论 软件是为解决客观世界中存在的问题而产生的，是对客观世界的建模，是客 观事物的一种反映。客观世界是永恒变化的，因此软件的演化性是优秀软件的基 本特征【l l 。软件的演化性指的是软件系统的各个组成部分可以增加、删除和更新， 软件系统的内部结构可以调整 2 1 。 软件演化在遗留系统的现代化改造研究中有着广泛的应用。由于商业环境的 急剧变化对软件提出了随需应变的迫切要求，软件系统变成遗留系统的周期已大 大缩短。这些成熟的遗留软件系统变得脆弱、不灵活以及不可扩展，无法满足不 断变换的业务需求。因此迫切需要维护和演化。软件演化允许系统考虑广泛的新 需求，并且获得完整的新功能。不仅是在指令级( 代码级) 改变软件，而且是在 体系结构级( 模型级) 做出改变，从而使它更容易与其它软件集成，使得遗留系 统成为财产而不是债务吲。软件重构是软件演化的一种。在软件演化领域中，重 构是指在不改变软件外部行为的条件下，对软件的内部结构所作的一种调整。对 软件内部的代码、结构进行重组，使之更为清晰、具有更高的效率，其目的在于 不改变软件可观察行为的前提下提高可理解性和降低修改的成本【4 】。 软件演化领域中，随着系统规模的不断扩大、复杂性不断增加以及需求不断 变化，对软件模型的演化能力的要求也越来越高。软件模型演化的发展趋势是具 有直观性、描述能力强的特点以及能与最新的软件开发方法集成。目前针对软件 模型演化主要采用图变换技术嘲。图变换为软件系统的描述和演化提供了一个形 式化和直观的方法。但在利用图变换处理可视化建模和演化时，采用图形描述方 式往往比较复杂，表达能力有限。而且当系统规模增大时，对图的维护相当困难， 这种图匹配方式的表达和处理能力明显不足，速度和效率也明显下降。此外，现 有的图变换工具无法提供灵活的用户自定义演化操作，难以处理复杂模型。 针对上述问题，本文提出使用带属性的类型图对软件结构进行建模，并将其 转换为谓词逻辑的描述形式，最后使用基于逻辑的软件演化操作语言s e o l 定义 演化操作，以达到实现模型演化的目的。基于上述理论研究，设计并实现一个针 对软件模型的演化引擎。带属性的类型图具有形式化语义、图形化特征、较完整 的表达能力和层次性的特点，能满足软件建模的需要。谓词逻辑是一种表达力很 强的形式化语言，能够对模型进行形式化描述。两者的结合能够使软件模型不仅 具有良好的图形表现形式又有严格的形式化描述，能描述现有软件系统的各种复 硕士学位论文第一章绪论 杂关系。在实现性能上比图匹配方法具有更高的效率。 1 2 国内外研究水平与现状 1 2 1 软件演化 软件演化( s o f t w a r ee v o l u t i o n ) 指在软件系统的生命周期内软件维护和软件更 新的行为和过程【6 】。在现代软件系统的生命周期内，演化是一项贯穿始终的活动， 系统需求改变、功能实现增强、新功能加入、软件体系结构改变、软件缺陷修复、 运行环境改变都要求软件系统具有较强的演化能力，能够快速适应改变，减少软 件维护的代价。 软件体系结构( s o f t w a r ea r c h i t e c t u r e ) 7 】是软件演化研究与实践的重要领域之 一。它作为需求规约与系统实现之间的桥梁，软件体系结构为系统的构造和组装 提供了指导性的蓝图。具体而言，软件体系结构有助于理解大型软件系统，揭示 系统的变化性，在高层校验和验证目标系统等【舯。当外界环境或需求发生变化时， 体系结构也随之变化以适应客观需求。从软件生命周期的角度看，软件演化是软 件开发的延续，所以研究软件体系结构的演化具有极其重要的现实意义。 国内外的研究机构在软件体系结构模型演化理论和技术进行了广泛的研究， 其主要研究工作有： 1 基于构件的软件体系结构演化研究 软件体系结构为软件系统提供了一个结构、行为和属性的高级抽象。软件结 构由构成系统的元素描述、这些元素之间的相互作用、指导元素集成的模式以及 这些模式的约束组成，这些元素就称为软件构件【9 ，1 0 1 。由于构件的提出，软件开 发过程可认为是构件开发和基于体系结构的构件组装【l l 】。而当前对软件构件的描 述通常都采用图形加文本的方式或形式化描述语言 1 2 , 1 3 , 1 4 1 ，这些描述对构件的动 态、互操作和演化特征方面的描述能力明显不足。文献【1 5 】提出了基于构件运算 的软件演化方法研究，把软件演化归结为增加构件、删除构件和修改构件关系， 研究这三种变化所引起的体系结构的变化，以及对应体系结构的构件运算表达式 的改变。这样就把软件演化归结为构件运算表达式的变动，运用代数理论对基于 构件的软件演化理论与方法进行研究。 目前传统的软件产业，其基本模式均是以符合标准的零部件( 构件) 生产以及 基于标准构件的产品组装的【1 6 1 ，这种软件模型具有标准化和复用性的优点。但是 在实现演化过程中容易导致由构件引起的失配问题( 包括由于系统对构件基础设 施、构件控制模型和构件数据模型的假设存在冲突引起的失配) 【1 7 】。另外，由于 2 硕士学位论文 第一章绪论 过于标准化的固有操作，使得无法提供灵活的用户自定义演化操作。 2 基于图的软件体系结构演化研究 基于图的体系结构将软件系统抽象为一个无向图或有向图。在文献【1 8 】中提 出了一种叫做k - c o m p o n e n t 的元模型。在k c o m p o n e n t 元模型中，一个有向配 置图被用来表示应用系统的软件体系结构。其中的图节点表示实体接口，类型标 签表示实体，有向边表示连接件。一个反射机制被设计用来在这个有向配置图和 目标系统之间建立因果连接，有向配置图和目标系统之间是模型和实现的关系， 从而使得配置图反映系统的真实软件体系结构。 在文献 1 9 ，2 0 o f 提出一种基于图的分布式w e b 应用软件系统架构技术。利 用严格定义的图作为描述软件体系结构的基本手段，并用图上的操作来支持系统 体系结构的动态重配置。这种以图来表示的软件体系结构不仅仅是高层的抽象描 述，同时也是具体的可操作的对象实体，从而有助于提高体系结构与最终实现之 间的可追溯性。但由于分布式系统的各个节点需要维护一个全局拓扑结构图，在 系统规模增大的情况下，图的维护变得相当困难。同时基于图的体系结构在进行 动态演化时，需要对图的整体拓扑结构进行变换，包括图的状态信息的转换。对 于大型的软件系统，动态演化的复杂程度和代价都相当大，使得这一结构难以适 应i n t e m e t 的动态广域计算环境。 1 2 2 图变换技术 图变换( g r a p ht r a n s f o r m a t i o n ) 的主要思想是应用图产生式规则进行的图修改 2 q 。因为图具有一定的数学理论基础，可用于数学推理和定理证明瞄】。而且图 变换已经形成了一套比较完整的数学理论 2 3 1 ，可用于证明图变换的某些性质。由 于它具有形式化和直观的特点，是现有可视化语言的理论基础之一。图变换能为 可视化模型的操作提供可视化和基于规则的方法。 图变换规则可以形式地表示为p ：l 山r ，其中三和r 分别称为左图( 也称为 左模式) 和右图( 右模式) ，图映射厂则用于指明工和r 之间的关系。当且仅当三的 某个顶点y 在图变换中没有被删除也没有被修改时，存在顶点，r 满足： ( y ，y 。l 厂。通常，可以通过给三和尺中的顶点编号来描述图映射厂。如果 ，l ，y r 而且y 和，具有相同的编号，那么，f y ，l 厂。应用图变换规则p 对 图g 进行一次转换，可以形式化地表示为t ：g 卫：与日，其中图映射m 是一个 匹配m ：l - - - g 。在图转换t 中，模式三在g 中的一个实例m ( 三) 被尺的实例m ( r ) 所取代，m ( l r ) 被删除，同时添加m ( r 一三) 。其中m 是m 的同匹配( c o - m a t c h ) ， 如图1 1 所示的图产生式规则【2 3 1 。 3 硕士学位论文第一章绪论 l z 一，r 埘l 肼 g h 图1 - 1 图产生式规则 因为图和图变换具有一定的数学理论基础，而且以图的形式描述模型和代码 非常自然、直观，所以目前许多模型转换技术都采用了图变换的方式。文献 【2 4 ，2 5 ，2 6 】中使用图变换技术对软件模型进行转换，将模型的演化规则描述为图 变换规, 贝j j ( p r o d u c t i o n ) 。文献【2 7 】提出了将j a v 玳码以图的形式描述，利用图文法 系统a g g ( a t t d b u t e dg r a p hg r a m m a r s ) 2 s , 2 9 】工具定义图变换规则，将代码的重构转 换为图的变换，最终达到软件重构的目的。 图变换技术为描述系统及其演化提供了一个形式化和直观的方法。但在利用 图变换处理可视化建模和演化时，采用图形的描述方式比较复杂，表达能力有限。 而且图匹配方式是一个n p c 0 m p l 曲e 问题【3 0 j ，当软件系统规模增大时，这种图形 方式的处理能力明显不足，速度和效率也明显下降。此外现有的图变换工具无法 提供灵活的用户自定义演化操作，对复杂模型难以处理。所以图变换技术需要增 加新的机制，以增强表达能力和处理性能。 1 3 研究内容 在软件演化领域中，对软件模型演化采用图变换技术具有形式化和直观性的 优点。但是当软件系统规模不断扩大、复杂性不断增加以及需求不断变化时，这 种图匹配方式的表达和处理能力明显不足，速度和效率也明显下降。在分析现有 基于图变换的软件演化方法技术的不足基础上，本文在基于图变换的软件模型演 化方面展开了研究，主要研究内容包括以下几个方面： 1 ) 提出一种基于逻辑的软件演化机制。定义了基于带属性的类型图的软件模 型的描述形式。结合谓词逻辑，提出了软件结构的谓词描述方法，并给出带属性 的类型图与谓词描述这两者的互转换对应关系。然后采用基于逻辑的软件演化操 作语言s e o l 描述演化操作，实现演化过程。软件演化过程如图l - 2 所示。 4 硕士学位论文第一章绪论 圈转化囤嚣二 图l - 2 软件演化过程 2 ) 在e c l i p s e 平台下以插件的形式设计和实现一个基于s e o l 语言的软件演 化执行引擎工具。 3 ) n 用软件演化执行引擎分析并实现邮件系统的演化过程。以实例证明基于 逻辑的软件演化理论的正确性和可行性。 1 4 论文的组织 本文共分为六章，各部分安排如下： 第一章为绪论部分，主要介绍了软件模型演化方面的国内外研究水平与现 状、论文的选题和研究意义以及本文的主要工作和研究重点。 第二章介绍了带属性的类型图的基本概念和基于带属性类型图的软件模型 描述，以及软件模型的谓词逻辑描述形式，并建立了带属性的类型图和谓词逻辑 描述之间的互转换机制。 第三章重点介绍了软件演化操作语言s e o l 的基本概念和处理机制。论述了 基于s e o l 语言的基本图变换操作和复杂图变化操作。以软件结构图的演化为 例，给出了一些复杂图变换操作的组合定义。 第四章在讨论s e o l 语言的基础上，设计并实现了一个基于s e o l 语言的软 件演化执行引擎，对并对该引擎的设计思想，系统结构、实现方法和技术进行了 论述。 第五章通过软件重构的经典案例邮件系统的演化过程，讲解了基于s e o l 语 言的软件演化执行引擎的使用过程与步骤，验证了基于逻辑的软件演化理论的可 行性和正确性。 第六章对论文所做的工作进行总结，并提出了今后进一步的研究方向。 5 硕士学位论文第二章基于带属性类型图的软件模型描述 第二章基于带属性类型图的软件模型描述 带属性类型图【3 1 l ( a t t r i b u t e dt y p eg r a p h ) 软件演化中的图 换( g r a p h t r a n s f o r m a t i o n ) 技术上有着广泛的应用。在图文法系统a g g 工具中以a t g 图作 为模型，描述图操作规则。文献【2 7 】提出了将j a v a 代码以a t g 图的形式描述， 以达到软件重构的目的。可见，由于a t g 图的图形化特征、表达能力强和形式 化等特点，在软件演化过程中使用其描述模型和代码已成为一种共识。 2 1 带属性类型图定义 根据对e 图【3 2 】的定义，引入了带属性的类型图的概念，即在a t g 图中允许 节点和边都有属性。属性值存储在集合k 中，在图中对应为节点属性边和边属性 边。 e - 图：一个e - 图g 。i 圪，虼，最，如，( 舳峭，t a r g e t j ) e g ，m 。翻 ，其中虼为图 节点集合，为数据节点集合，最为图边集合，为节点属性边集合，为 边属性边集合。 s o u r c e g ：磊_ k ，边到源节点( 图节点) 的映射； t a r g e t c ：- - 圪，边到终节点( 图节点) 的映射； s o u r c e ：目寸k ，节点属性边到对应图节点的映射； t a r g e t m ：专，节点属性边到数据节点的映射： s o u r c e u ：屋寸最，边属性边到对应图边的映射； t a r g e t u ：玩寸，边属性边到数据节点的映射； 从e 图的定义可知，它是对有向图的扩充，允许有向图的节点和边具有属 性。属性的描述存储在属性边集合和艮中。属性值存储在集合中。 属性图：给定一个数据基调d s i g = ( s d ，o p d ) ，s d 为数据类别集，o p d 操作 符集，s ：s o 为属性值对应的类别集，则一个属性图a g = ( g ，d ) ，其中g 为 e 一图，d 为基调d s i g 上的数据代数，且u ，。t 皿= 。 对于属性图而言，引入类型的概念，即定义了属性图的节点和边的类型。由 此引入带属性的类型图a t g ，用来描述类型也即a t g 的节点和类型之间的关系 也即a t g 的边。并由此得到a t g 图的定义。 定义2 - 1 一个带属性的类型刚3 3 j 是一个带属性图a t g = ( 粥，z ) ，其中粥为 e 图，z 为一个终结d s i g 代数，其载体集z = s 1 ，v s s d 。 6 硕士学位论文第二章基于带属性类型图的软件模型描述 2 2 基于a t g 的软件模型描述 带属性的类型图是一种基于图形的形式化描述方法，采用带属性的类型图 作为描述软件结构的基本单位，具有一定的内容、结构与约束以及良好的描述能 力，被普遍应用于软件模型演化领域以及可视化语言中模型或元模型的建立。 带属性的类型图作为一种元模型描述了图的类型( a t g 的节点) 和类型间的 关系( a t g 的边) 。通过对图的类型间的定义( 边的属性) 可以确定图与图之间的 关系，由此可以在图变换的规则下对图进行转化。而图中各元素则采用属性集描 述。在带属性的类型中，存在一个节点集、一个边集、一个节点属性集和一个边 属性集。同时还包括两个映射，用于描述节点与边之间的关系。 对于软件系统结构的图形化描述和表达，目前常用的方式是采用 u m l ( u n i f i e dm o d e l i n gl a n g u a g e ) 虱来表示。但是在软件系统结构中的同一组件 连接器的多个实例间可以有完全不同的内部结构和端口，而u m l 中的组件与连 接器的多个实例是完全相同；并且对于某些软件结构描述语言，行为协议是软件 结构中的连接器的一部分，而u m l 需要用其它的模型( 如序列协作图) 来模拟。 所以需要采用一种描述表达能力更强的图形结构来描述软件结构。在带属性的类 型图中通过对节点集和边集属性的绑定，可以扩大软件抽象构件与构件连接的描 述范围与能力，表述复杂的软件体系结构。 在描述软件演化的软件系统结构中，本文采用了基于带属性的类型图的软件 体系结构描述。它的组成部分有：节点、边和属性。简单而言，节点表示实体， 边表示实体与实体之间的关系，属性表示节点以及边的具体相关信息。图内的元 素采用下面的方式定义： 1 ) a t g 图中节点的描述对象为软件实体，节点的属性用来描述节点信息。 如类型，函数等； 2 ) a t g 图中边的描述对象为软件实体之间的关系，边的属性用来描述实体 关系的类型。如调用、继承等； 3 ) a t g 图中节点与边的映射集则用来确定节点与边之间的对应关系，如边 描述的是哪两个节点之间的关系等。 由上述三点可以得到软件结构a t g 的抽象语法示意图，如图2 1 所示。图中 c o m p o n e n t n o d e 表示软件组件节点，它带有两个属性t y p e 和n a m e ，分别用来表示 组件的名称和组件类型。r n o d e 表示资源节点，用来描述软件结构中组件与组件 直接的共享资源。c o m p o n e n t l i n k 和r l i n k 分别表示组件与组件和组件与资源之间 的连接关系。在图2 1 中，对于节点( n o d e ) 和连接( l i n k ) 都只给出了必要的属性， 由于具体软件系统的组件、资源和关系可能存在多种复杂的情况，所以节点和连 7 硕士学位论文第二章基于带属性类型图的软件模型描述 接的属性可以交给用户自定义以适应不同类型的软件系统，使软件结构的a t g 描述具有更好的灵活性和扩展性。 图2 1 软件结构a t g 的抽象语法示意图 由于带属性的类型图可以对节点与边给出自由的属性定义，因此采用a t g 图来描述软件结构具有很大的灵活性，可以适应于大部分的软件体系结构定义。 采用这种方法描述软件体系结构可以在最大程度上体现软件各模型之间的关系， 有利于软件结构与软件关系特征的提取；同时，也可以很好地表现软件体系结构 的变动信息，有利于软件演化过程分析。 2 - 3 软件模型的谓词表达形式 逻辑演算的形式化方法在众多科学研究中，尤其是在计算机科学中有着十分 重要的作用和广泛的应用。逻辑演算具有如下特点：形式化的描述，较强的表达 能力，一阶谓词逻辑中的消解( 亦称归约) 推理，一阶谓词表达式的集合是否可合 一这个问题是可判定的 3 4 1 。因此，由于谓词逻辑具有形式化描述能力以及出于软 件演化操作实现的考虑，需要将软件体系结构的图形描述转化为谓词逻辑的形 式。 在谓词逻辑中，一个谓词可分为个体和谓词名两个部分。个体表示某个独立 存在的事物或者某个抽象的概念；谓词名表示个体的性质、状态或个体间的关系。 一阶谓词逻辑语言定义如下： 定义2 2 一个一阶谓词逻辑语言l l 是一个四元组( p r e d ，f , v a r , g o n ) 。其中p r e d 表示谓词集合，f 表示符号函数集合，v a r 表示变量集合，g o n 表示逻辑符号集 8 硕士学位论文 第二章基于带属性类型图的软件模型描述 ，v ，1 - v ，了 。由于常量可以看作是没有参数的函数符号，所以也用f 表示 常量集合。 在软件结构的谓词描述中，对软件的构件实体，将实体的属性作为谓词名， 而实体的名称作为个体描述。对于软件实体之间的连接，则将它们的属性作为谓 词名，关系连接的两个构件实体的名称作为个体。软件结构的谓词定义如下： 定义2 - 3 一个软件结构s 是一个四元组 。其中c 表示类的集合， m 表示方法的集合，v 表示变量的集合，p 表示类、方法和变量之间的关系以及 他们属性的集合。 由定义2 3 可知，集合c 、m 和v 是组成软件的实体，集合p 是软件结构 ( 包括c ，m 和v 的属性和他们之间的关系) 的描述，代表软件的重要特性， 也是影响软件可扩展性的重要因素。所以本文为了描述简洁，省略对集合c 、m 和v 的描述，重点研究谓词集合p 。 2 4a t g 模型与谓词描述的对应关系 带属性的类型图是以图形化的方式来描述软件结构，它直观地表示了软件结 构中实体的相互关系，具有很强的可视性，便于用户理解整个系统结构。而使用 谓词逻辑描述软件体系结构则是进行软件演化智能化处理的一个重要条件。出于 对演化操作的执行和实现的考虑，在软件演化过程中需要将这两种描述方法结合 起来。这样结合的好处有：一方面，采用图形化的描述方式更有利于体现软件结 构的特点，保证图形可视化的特性，方便用户了解软件系统的结构和状态；另一 方面，采用谓词对软件系统结构描述具有形式化和简洁特点。此外，后文提出的 软件演化操作语言也是基于谓词逻辑的语言，将带属性的类型图转换为谓词逻辑 的形式，即是为演化操作的实现提供了前提。换言之，具体的演化操作将不再对 图形进行操作，而是将演化问题转化为对谓词表达式进行操作。相比图变换中的 图匹配方法这个n p 完全问题，在性能上有较强优势，能够大大提高演化操作的 效率。 对于带属性的类型图而言，任何软件的描述信息都可以由图的组成成分是否 存在来表示( 构成软件体系结构的逻辑表达式) ，即使用谓词的函数符号来描述 图的组成成分。谓词集合中的”e x i s t s ”可用来描述图的组成成分是否存在。具体而 言，带属性的类型图用函数符号n o d e ( 节点) 、e d g e ( 边) 和a t t r i b u t e ( 属性) 来描述其 软件组成成分。为了对节点和边加以区分，这里采用了标号( 1 a b e l ) 1 3 5 1 的描述方式。 对带属性的类型图的组成成分描述如表2 - l 所示。其中”? ”开头的符号表示为变 量。 9 硕士学位论文第二章基于带属性类型图的软件模型描述 节点 n o d e ( ? l a b e l ，? t y p e ) 边 e d g e ( ? e l a b e l ，? e t y p e ，? s l a b e l ，? s t y p e ， ? t l a b e l ，? t t y p e ) 标号) 白? l a b e l ，类型为? t y p e 的节 点。 标号为? e l a b e l ，类型为? e t y p e 的 边，其源节点和终节点的标号 和类型分别是( ? s l a b e l ，? s t y p e ) 和( ? t l a b e l ，? t t y p e ) 。 属性 a t t r i b u t e ( ? l a b e l ，? t y p e ，? a t y p e ，? a n a m e ， 标号为? l a b e l ，类型为? t y p e 的模 ? a v a l u e ) 型成分的属性类型、名称和值 分别为? a t y p e ，? a n a m e ，? a v a l u e 。 由此可见，利用表2 - 1 给出的函数符号，可以描述带属性的类型图里的组成 成分，从而达到带属性的类型图和谓词描述一一对应的关系。那么对于以带属性 的类型图描述的软件系统结构，可由上述函数符号描述集表示。 带属性的类型图的存储格式为g x l ( g r a p he x c h a n g el a n g u a g e ，图交换语 言) 【蚓文件形式。g x l 是为基于图形的工具所设计的一个标准交换格式，它被 定义为x m l 的子语言，以统一的格式为转换实例图提供支持【3 7 1 。从形式上来看， g x l 是基于类型属性的有序有向图。从概念上来看，可扩展到对超图和等级图 的支持。从图的结构来看，g x l 为定义一系列特殊匹配的图型转换格式提供了 内核 3 8 l 。通过使用这种一般图模型，g x l 对几乎所有种类的图形交互提供了一 个通用的支持。可见，g x l 作为一个x m l 子语言，为带类型属性的有向顺序图 的交互提供了一个标准的转换语言。 g x l 具有完整且详细定义的d t d ( d o c u m e n tt y p ed e f i n i t i o n ) ，通过d t d 规 定了g x l 中节点和边的描述范围和描述能力。具体而言，g x l 提供了铲l ，g r a p h ， a t t r i b u t ev a l u e s ，t y p e ，n o d e ，e d g e ，r e l m i o n ，a t t r i b u t e 和r e l e n d 等元素，其节点和边的 d t d 定义如下： 由此可见对节点而言，组成元素i d 和t y p e 可用谓词表达式n o d e ( ? l a b e l ，? t y p e ) 描述。其节点属性的扩展形式为 n o d e a t t r - e x t e n s i o n ”，可用对应谓词表达式 a t t r i b u t e ( ? l a b e l ，? t y p e ，? a t y p e ，? a n a m e ，? a v a l u e ) 。同样地，对于边的组成元素i d ， t y p e ，f r o m 和t o ，可用e d g e ( ? e l a b e l ，? e t y p e ，? s l a b e l ，? s t y p e ，? t l a b e l ，? t t y p e ) 描述。边的属 性的扩展形式为 e d g e a m - e x t e n s i o n ”，其对应的谓词表达式也可以用 a t t r i b u t e ( ? l a b e l ，? t y p e ，? a t y p e ，? a n a m e ，? a v a l u e ) 描述。该对应关系只关注图形中的节 点，边和属性。对于图形的其他信息保留不变。由于g x l 可以清晰地描述a t g 图中节点和边的信息，所以在软件结构的a t g 描述到谓词逻辑描述的转换中选 择用g x l 作为中介。在g x l 中节点或边的类型直接对应软件结构谓词逻辑描述 中的谓词名，而节点或边的属性可以直接对应于谓词逻辑中的个体。通过对于 g x l 的解析规则的定义可以方便地建立由软件结构图描述到谓词描述描述的转 换规则，从而实现由可视化到基于谓词的形式化的软件结构的自动转换。 2 5 本章小结 本章首先介绍了带属性的类型图的基本概念，定义了基于带属性的类型图的 软件演化模型的描述形式。考虑到谓词逻辑的特点和软件演化操作中具体实现性 能和效率问题，提出了以谓词逻辑描述软件体系结构，并给出带属性的类型图与 谓词描述这两者的对应关系，定义了组成软件系统的各类元素的属性特征。为后 文的基于逻辑的软件演化的实现提供了必要条件。 硕士学位论文 第三章基于逻辑的软件演化操作语言s e o l 第三章基于逻辑的软件演化操作语言s e o l 软件演化操作的描述是软件演化理论中重点研究的对象，它关系到演化操作 的具体实现。现有的软件演化描述方法语义不明确，扩展性和描述能力都有待提 高。因此，文献【3 9 】提出了一种软件演化操作语言s e o l ( s o f f w a r ee v o l u t i o n o p e r a t i o n a ll a n g u a g e ) 来描述软件演化操作。s e o l 语言结合谓词逻辑以形式化方 式描述，这样有利于软件演化操作描述的分析和操作实施的自动化实现。 3 1s e o l 的基本概念 3 1 1s e o l 的语法规则 语法规则是为了防止用户使用建模工具建立的模型出现逻辑错误而建立的 一系列规则，它是判断所建的模型是否有效与正确的依据。s e o l 语言采用大多 数程序设计语言所使用的上下文无关文法定义语法规则。下面用e b n f 概括演化 操作的主要语法规则。 o p e r a t i o n ：一x , ( p r e c o n d i t i o n , - , p o s t c o n d i t i o n ) l ( p r e c o n d i t i o n l o p e r a t i o n , - , o p e r a t i o n ) i ( o p e r a t i o n , - ”，o p e r a t i o n ) , ” p r e c o n d i t i o n ：= b a s i c p r e e o n d i t i o n i ( p r e c o n d i t i o ni t a f t , p r e c o n d i t i o n ) ； p o s t c o n d i t i o n ：= b a s i c p o s t c o n d i t i o n l ( p o s t c o n d i t i o n ，” ”，p o s t c o n d i t i o n ) ； 其中o p e r a t i o n 为演化操作主体，p r e c o n d i t i o n 为演化操作的前提条件， b a s i c p r e c o n d i t i o n 为演化操作的基本前提条件，p o s t c o n d i t i o n 为演化操作的后置条 件，b a s i c p o s t c o n d i t i o n 为演化操作的基本后置条件。 由此可知，对软件演化操作的描述s e o l 语言是通过对软件模型的前置条件 和后置条件的描述来实现的。前置条件表示演化操作之前软件应该满足的状态。 同时也起到两个作用，一方面对所需的软件成分进行查询，另一方面对软件的改 变进行合法化检查。后置条件则表示演化操作之后软件所处的状态。 此外，s e o l 语言通过选择组合和顺序组合的方式重用已有的演化操作描述。 1 2 硕士学位论文 第三章基于逻辑的软件演化操作语言s e o l 为软件演化操作提供了一个灵活、易用和可扩展的描述形式。 从上文对o p e r a t i o n 的定义可以看出演化操作主体有以下四种形式： 基本形式：” , p r e c o n d i t i o n , - ”，p o s t c o n d i t i o n ，” ”； 条件扩展形式：” , p r e c o n d i t i o n , = , o p e r a t i o n , ) ； 选择组合形式：” , o p e r a t i o n , , o p e r a t i o n , ) ； 顺序组合形式：” , o p e r a t i o n ，= ”，o p e r a t i o n , ) ”； 基本形式是由前置条件和后置条件构成，一般用来描述细粒度的软件变化：条 件扩展形式用来扩展已有的演化操作的前提条件；选择组合形式是指两个演化操 作中任何一个如果前置条件成立便执行该演化操作；顺序组合形式指两个演化操 作必须按先后顺序执行，并且后一个演化操作执行的前提是前一个演化操作执行 成功。后三种演化操作形式都是通过基本形式组合而成，一般用来描述粗粒度的 软件变化。 3 1 2s e o l 表达式 演化操作表达式形式如定义3 1 所示。假定肌为所有符合p r e c o n d i t i o n 描 述的符号序列构成的集合，p o s t 为所有符合p o s t c o n d i t i o n 描述的符号序列构成的 集合，c a l l 为所有符合o p e r a t i o n c a l l 描述的符号序列构成的集合。 定义3 1s e o l 表达式c x p e x p ：= b a s i c e x p l q m e ”l ”f a l s e ”i t u n d e f i n e d ” b a s i c e x p ：= ( ” t t ，( r ”，b ) i b ”- , b a s i c e x p ) i ( b a s i c e x p , - , b a s i c e x p ) i ( b a s i c e x p , 母”, b a s i c e x p ) ) , ) ”) l o p c a l l 其中，口p r e ，b p o s t ，o p c a l l c a l l ， t r u e ”、 f a l s e ”和”u n d e f i n e d ”为 演化操作表达式处理的结果。 i m e ”表示演化操作处理成功，t f a l s e ”表示演化操 作处理失败，”u n d e f i n e d ”表示演化操作由于前置条件为假，演化操作未执行而导 致其对应的后置条件不能满足。 硕士学位论文第三章基于逻辑的软件演化操作语言s e o l 3 2s e o l 的处理机制 3 2 1 合一算法 s e o l 语言的执行处理是采用人工智能的合一算法【4 0 1 实现的。谓词逻辑中的 替换合一是符号推理中模式匹配的基本技术。一