（计算机应用技术专业论文）rcos的操作语义及其在程序分析中的应用.pdf

- j d i s s e r t a t l 0 nf o r m a s t e rd e g r e e ，2 010 s c h o o lc o d e ：10 2 6 9 s t u d e n tn u m b e r ：5 2 0 8l5 0 0 0 0 6 e a r c n an r m a lu n 姗r t v t h eo p e r a t i o n a ls e m a n t i c sf o r r cosa n di t sa p p l i c a t i o ni n p r o g r a ma n a l y s i s d e p a r t m e n t ： m a j o r ： s u b j e c t ： t u t o r ： a u t h o r ： s o f t w a r ee n g i n e e r i n gi n s t i t u t e c o m p u t e ra p p l i c a t i o nt e c h n o l o g y t r u s t w o r t h yc o m p u t i n g p r o f e s s o rh ej i f e n g f e n gl i b o 一 2 01 0 0 4 华东师范大学学位论文原刽性声明 郑重申明：本人呈交的学位论文疋o s 的操作语义及其在程序分析中的应 用，是在华东师范大学攻读琢生博士( 请勾选) 学位期问，在导师的指导下进行 的研究工作及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他 个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均 已在文中作了明确说明并表示谢意。 作者签名：遇丞尘遗日期：勿本牛月f2 r 华东师范大学学位论文著作权使用声明 r c o s 的操作语义及其在程序分析中的应用系本人在华东师范大学攻读学 位期间在导师指导下完成的硕士博士( 请勾选) 学位论文，本论文的研究成果归华 东师范大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并 向主管部门和相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和 电子版：允许学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校 将学位论文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的 标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文牛， 于年月r 解密，解密后适用上述授权。 ( v ) 2 不保密，适用上述授权。 聊妊蚓 本人签名：冯币q 液本人签名：缨型：! 坠 少o 年十月l 2 同 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定 过的学位论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有 效) ，未经上述部门审定的学位论文均为公开学位论文。此申明栏不填写的，默认为公开学 位论文，均适用上述授权) t t 冯利波硕士学位论文答辩委员会成员名单 姓名职称单位备注 刘静教授华东师范大学软件学院主席 朱惠彪教授华东师范大学软件学院 蒲戈光副教授华东师范大学软件学院 孙海英讲师华东师范大学软件学院秘书 摘要 r c o s 是ar e f i n e m e n tc a l c u l u sf o ro b j e c ts y s t e m s ( 对象系统的精化演算) 的简称。它以 统一程序设计理论( u n i f y i n gt h e o r i e so f p r o g r a m m i n g ) 【3 为基础，是一种面向对象的描述语 言，定义了一种用于描述面向对象程序设计结构的形式规范。r c o s 具有非常守富的语言特 征，包括子类( s u b t y p e s ) 、引用类型( r e f e r e n c et y p e ) 、可见性( v i s i b i l i t y ) 、继承( i n h e r i t a n c e ) 、 多态( p o l y m o r p h i s m ) 、动态绑定( d y n a m i cb i n d i n g ) 等。本文采用形式化的方法给出y r c o s 的 一种结构化操作语义。对于段r c o s 程序，按照操作语义给出的变迁规则模拟执行就能动 态的产生对象图，而另一方面静态分析程序段的类声明部分就能得到对应的类图。对象图 和类图构成了r c o s 程序的抽象模型。 文中给出的操作语义一方面能动态地构建了对象图，同时又能捕获对象之间的关系。 这样有助于帮助理解程序的行为，使得在程序分析方面起到了定的作用，尤其在当前软 件工程领域有着j 。泛应用的设计模式的识别上。文中将设计模式的性质定义为两类：通用 属性和用户相关属性。 为了能描述对象图或者类图上对象与对象或者类与类之间的关系，我们定义了一种关 系演算，将类之间的关系分为继承和包含，对象之间的关系分为创建、调用和引用。文中 选取抽象工厂模式、观察者模式、组成模式等为例，说明该关系演算能刻画设计模式性质。 最后，本文给出一种通用的检查算法。在此基础上，又通过实验来说明算法的高效性以及 能在程序段中自动判断设计模式是否正确的应用，从而能自动识别程序段中好的模式和坏 的模式。 关键词：设计模式，性质检查，关系演算，操作语义 a b s t r a c t 妃o si ss h o r tf o rar e f i n e m e n tc a l c u l u sf o r0 b j e c ts y s t e m s ，w h i c hi sk n o w na s ar e f i n e m e n t c a l c u l u sf o ro b j e c to r i e n t e ds y s t e m s r c o sp r e s e n t sam a t h e m a t i c a lc h a r a c t e r i z a t i o no fo b j e c t - o r i e n t e dc o n c e p t sa n di sb a s e do nt h ep r e d i c a t el o g i ci nh o a l ea n dh e su n i f y i n gt h e o r i e so f p r o g r a m m i n g ( u t p ) i ti ss i m i l a rt oj a v aa n dc ha n dc a p t u r e st h ef e a t u r eo fs u b t y p e s ，v i s i b i l i t y , r e f e r e n c et y p e s i n h e r i t a n c ea n ds oo n i nt h ep a p e r , w ef i r s tp r e s e n tak i n do fs t r u c t u r eo p e r a t i o n a ls e m a n t i c sf o rr c o s t h eg i v e n o p e r a t i o n a ls e m a n t i c sp l a yag r e a ti m p o r t a n ti np r o g r a m m i n ga n a l y s e ，e s p e c i a l l yi nt h ed e s i g np a t - t e r nr e c o g n i t i o n 【8 ，9 】t oc o n s t r u c tt h ea b s t r a c tm o d e lf r o mr c o si n s t e a do fa n a l y z i n gd i r e c t l y o ns o u r c ec o d e ，w ec o m b i n es t a t i ca n dd y n a m i ca n a l y s i st o g e t h e rt oa c h i e v eb e t t e rc h e c k i n ge f f i - c i e n c y c l a s sd i a g r a m sa n do b j e c tg r a p h sa l eo b t a i n e dw i t ht h ea n a l y s i so fr c o sp r o g r a m t h e g i v e no p e r a t i o n a ls e m a n t i c sf o rr c o sw i t ht h eo b j e c tg r a p hi sg i v e na st h eb a s i sf o rr e p r e s e n t i n g o b j e c tr e l a t i o n s h i p s ar e l a t i o n a lc a l c u l u si sp r o p o s e dt os p e c i f yt h ep a t t e r np r o p e r t i e sw ew o u l dl i k et oc h e c k w e c l a s s i f yt w oc a t e g o r i e so f p r o p e r t yf o rp a t t e r n s ：g e n e r a lp r o p e r t ya n du s e r - r e l a t e dp r o p e r t y ag e n - o r a la l g o r i t h mf o rc a l c u l a t i n gr e l a t i o n a lp r e d i c a t e si sp r e s e n t e dt op e r f o r mt h ep r o p e r t yc h e c k i n g t h ee x a m p l e so fd e s i g np a t t e r n sf r o mg o f 【5 】，s u c ha sa b s a a c tf a c t o r yp a t t e r n , o b s e r v e rp a t t e r n , c o m p o s i t ep a t t e r ne t c ，a r ea l s op r o v i d e dt oi l l u s t r a t et h ee f f e c t i v e n e s so f o u ra p p r oa c _ hf r o mw h i c h w ec a nt e l lw h e t h e rs o m op a t t e r n sa l ou s e dc o r r e c t l y f i n a l l yw ei m p l e m e n tat o o la n dd os o m e e x - p c r i m e n tt oc h e c kd e s i g np a n e mt h r o u g hs t a t i ca n dd y n a m i cw a y s t h u sw e f i n i s ht h eg o a lt h a tt o c h e c kw h e t h e rd e s i g np a t t e r n sa r eu s e dc o r r e c t l yi n0 r d e rt oa c h i e v et h eg o a l st h a td e s i g np a t t e r n s c a l lb ei d e n t i f i e da u t o m a t i c a l l y ( g o o dp a t t e r na l ef o u n do rb a dp a t t e r nm a ye x i s ti ns y s t e m s ) k e yw o r d s ：r c o s ；d e s i g np a t t e r n s ；p r o p e r t yc h e c k i n g ；r e l a t i o n a lc a l c u l u s ；o p e r a t i o n a l s e m a n t i c s 目录 第一章引 言 1 1 研究背景。 1 2 研究内容 1 3 文章的组织结构 第二章背景知识 2 1 r c o s 简介 2 2 形式语义学简介 2 3 设计模式简介 第三章 3 1 3 2 3 3 r c o s 的操作语义 r c o s 语法规则。 变迁规则一， 妃o s 的操作语义 第四章设计模式的规范与性质 4 1 模型生成。 4 2 关系演算 4 3 设计模式的性质表示举例 第五章性质检测 5 1 可满足性算法 5 2 实验 第六章总结与展望 6 1总结。 6 2 展望 参考文献 致谢 2 4 4 5 7 9 9 n h 侈加挖m 抄汐驼 靳弱卯 鳃 柏 发表论文和科研情况 1 v 4 1 第一章引言弟一早引苗 在本章中，我们先介绍了本论文的研究背景以及研究问题，接下来大致描述了本论文 的主要研究内容，即首先给出了r c o s 语言的一种操作语义。接着说明该操作语义在程序分 析中的一个应用，即模式识别。为了能够判断在以r c o s 为元语言编写的程序中，是否正确 地运行了某种设计模式，从而进一步能自动识别出程序中好的模式和坏的模式。最后，介 绍了本论文的文章组织结构。 1 1 研究背景 r c o s 【6 】全称足ar e f i n e m e n tc a l c u l u sf o ro b j e c ts y s t e m s ( 对象系统的精化演算) ，以统 一程序设计理论( u n i f y i n gt h e o r i e so f p r o g r a m m i n g ) 【3 为基础而提出来的。它定义了一种 用于描述面向对象程序设计结构的形式规范。作为一种面向对象的描述语言，它具有非 常丰富的语言特征，包括子类( s u b t y p e s ) 、引用类型( r e f e r e n c et y p e ) 、可见性( v i s i b i l i t y ) 、继 承( i n h e r i t a n c e ) 、多态( p o l y m o r p h i s m ) 、动态绑定( d y n a m i cb i n d i n g ) 等。 自8 0 年代开始，设计模式在计算机系统领域，尤其是面向对象的设计过程中得到了越 来越广泛的应用。设计模式的引入有助于人们降低代码的复杂度，提高软什质量。然而，实 践证明，很多时候由于人们对设计模式在理解上存在偏差甚至是错误或者因为在代码实现 的时候与原先设计的时候存在差异导致设计模式的错误应用屡见不鲜。为了避免这样的错 误发生，国内外一些学者试图将设计模式进行形式化描述 1 ，4 】，却发现这不是什容易的 事情。他们中大多数都是按照从需求到代码的重组来开展工作的，文章 1 3 ，7 将设计模式 看成逻辑抽象模型，在这方面做出了不错的成绩。举个例子来讲，e d e n 提出了一种符号逻 辑语言l e p u s ，该语言可以被用于描述面向对象的体系结构 2 】。龙泉等研究了设计模式的 重组规则以及关于r c o s 的精化规则【l o ，l1 】。 1 2 研究内容 本研究的主要内容采用结构化操作语义的方法给出了疋o s 语言的一个操作语义。基于 该操作语义的变迁规则，执行程序可以动态地得到程序的对象图。另一方面，由于r c o s 语 言明确标准的关于类声明的语法，我们可以通过静态的分析程序的源代码得到类图。和以 1 3 文章的组织结构 第一章弓t 言 往的工作不同的是，在本文中我们采用动态和静态相结合的方式从r c o s 源代码中构造了 抽象模型( 类图和对象图) 。该操作语义能够在程序分析方面有种重要的应用，文中研究了 其在模式识别上的应用。 为了能够判断在以r c o s 为元语言编写的程序中，是否正确地运行了设计模式，从而进 一步能自动识别出程序中好的模式和坏的模式。基于实际问题分析的需要，我们将设计模 式的性质分成了两类，一类是通用属性，而另外一类是用户相关属性。第二类属性是第一 类属性的灵活扩展，这样处理的目的是尽管随着代码复杂度加大等原因，我们可以发现用 户虽然正确选择了某种设汁模式，但是实际上内部并没有按照其正确运行等的一系列错 误。 文中为了刻画类与类之间或者对象与对象之间的关系，我们引入了一种关系语言，该 关系演算在表达能力上把类之间的关系分为继承( i n h e r i t a n c e ) 和包含( c o n t a i n ) ；对象之间的 关系存在着创建( c r e a t e ) 、调用( c a l f ) 和引用( r e f e r e n c e ) - - - - 种。同时，通过对几类典型的设计模 式举例，发现该关系演算语言能很好的描述之前提到的设计模式的性质。最后，我们给出 了一种通用的检验算法，在此基础上通过实验来说明算法的高效性以及能在程序段中识别 出设计模式是否正确的得到了应用。 我们实现算法的思路是：对于给定的r c o s 程序，我们模拟的让两个进程并行的去实 施：通过静态分析程序源码得到类图和根据造作语义动态执行进程获得对象图。对象图和 类图构成了r c o s 模型。谓词作为纽带，一方面能描述r c o s 模型上各个类以及对象之间的 关系，同时又能表达设计模式所包含的通用属性和用户相关属性。最后，r c o s 模型和模式 的性质都输入到关系分析器巾进行验证。 1 3 文章的组织结构 第二章是相关背景知识的概述。主要有三部分内容，分别介绍了r c o s 语言的主要特 征以及国内外学者围绕其所做的一些研究工作以及形式语义学的起源、分类和面向 对象语言中的设计模式。 第三章主要介绍了r c o s 语言盼些主要语法，并给出了相应的操作语义。不同于之 前的工作【1 6 】，在该操作语义定义的结构中，我们给出了对象图的定义，也就是说为 下文对象图在程序的执行过程中自动生成打下了基础。 第四章中我们引入了谓阋演算，并运用该谓阋演算用描述几类典型的设计模式的性 质。在这里，我们把设计模式的性质分成了两类，一类是通用属性，而另外一类是用 户相关属性。第二类属性是第一类属性的灵活扩展，这样处理的目的是尽管随着代 码复杂度加大等原因，我们可以发现用户虽然正确选择了某种设计模式，但是实际 上内部并没有按照其正确运行等的一系列错误。 2 1 3 文章的组织结构 第一章弓l 言 第五章概述了类图和对象图，并通过例子来说明如何从程序中得剑类图并自动生成 对象图。接下来，我们又给出了相应的检查算法，并通过实验来说明如何进行验证 的。 第六章是结束语，对本文的研究工作进行了总结和展望。 3 丛一立 弟一草 背景矢n 1 4 识月京大以 本文研究中，主要以r c o s 语言为研究对象，给出了它的种操作语义，在研究分析其 在程序分析中的一- 种应用一一设计模式识别。在本章中，我们依次对r c o s 语言、形式语义 学和设计模式逐一做个简单的介绍，为后面章节的工作做好铺垫。 2 1r c o s 简介 r c o s 鼬, r e f i n e m e n tc a l c u l u sf o ro b j e c ts y s t e m s ( 对象系统的精化演算) 的简称。它是 由华东师范大学软件学院的何积牛院士、澳门联合国大学软什研究所的李小山、刘志明 博士于2 0 0 5 年合作提出的。r c o s 是一种面向对象描述语言，定义了一种用于描述面向对 象程序设计结构的形式规范。尽管r c o s 没有考虑垃圾回收( g a r b a g ec o l l e c t i o n ) ，属性隐 藏( a t t r i b u t eh i d i n g ) ，多继承( m u l t i p li n h e r i t a h o e ) 和错误处理机制( e x c e p t i o nh a n d l i n g ) 等。 但它仍具有非常丰富的语言特征，包括子类( s u b t y p e s ) ，引用类型( r e f e r e n c et y p e ) ，可见 性“i s i b i l i t y ) ，继承( i n h e r i t a n c e ) ，动态绑定( d y n a m i cb i n d i n g ) ，多态( p o l y m o r p h i s m ) 等。 r c o s 的语法包括面向对象系统，类卢明，命令和表达式，其主要语法e j a v a 和c + + 类 似。r c o s p a 文献 3 】中的统一程序设计理论( v m f y i n gt h e o r i e so f p r o g r a m m i n g , u t p ) 为基础， 它的语义模型提供了个演算用以支持面向对象设计中的结构和行为精化( r e f i n e m e n t ) 。它 能够很好地描述面向对象设计和程序，并利用精化规则从需求到分析到设计再到实现整个 过程的求精化简。r c o s 是用于推理验证不同抽象层次上的面向对象软件，包括规格说明， 设计和程序。 澳门联合国大学软件研究所的刘志明博士领导了个团队致力于妃o s 工具的开发与 研究。该工具支持r c o s 方法用于建模、分析、验证和保持正确性的转换，以及从设计模 式生成可验证的代码。它是在e c l i p s e 平台上实现的，使用了u m l 的原形，同时与其他基 于u m l 软什工程工具的兼容。 4 2 2 形式语义学简介第二章背景知识 2 2 形式语义学简介 2 2 1 形式语义学的起源 随着计算机科学技术的日新月异，程序语言学迅猛发展。语言学的研究般可分为 三部分；语法学( s y n t a x ) 、语义学( s e m a n t i c s ) 和语用学( p r a g m a t i c s ) 。5 0 年代是计算机语言兴 起的年代，在这一阶段早期，计算机语言的设计往往主要强调其“力便”的面，而忽略 其“严格”的一一面，因而对语言的语义，甚至是语法，未f 严格的定义，从而语言设计者、 实现者和使用者对同一语言的语义缺乏共同的理解，造成了一定程度的混乱。 为了正确、有效地使用程序设计语言，必须弄清楚语言中各成分的含义，并且要求计 算机系统执行这些成分所产生的效果和它的语义完全一致。由于自然语言存在歧义性，加 上经过实践的证明，必须以数学为工具，利用符号和公式，精确地定义和解释计算机程序 设计语言的语义，即用形式化的语言和方法，这就产生了形式语义学【1 9 。 2 2 2 形式语义学的分类 6 0 年代是计算机语言形式语义学诞生的1 0 年，形式语义学的四大流派皆渊源予这一时 期。其中，1 9 6 4 年被认为是操作语义学和指称语义学的诞生年代。l a n d i n 关于操作语义的 奠基性文章“表达式的机械化处理”和s t r a c h e y 关于指称语义的奠基性文章“关于形式语 义学( t o w a r d saf o r m a ls e m a n t i c s ) ”都问世于这一年。1 9 6 7 年f o l y d 发表的论文“给程序赋予 语义( a s s i g n i n gm e a n i n gt op r o g r a m s ) ”是公理学语义诞生的标志。而最年轻的代数语义学， 是7 0 年代中期在抽象数据类型理论的基础上发展起来的。 公理语义 公理语义是在程序正确性验证的基础上发展起来的，它给出了一种方法，使人们能在 给定的前提下，验证某种特定的性质是否成立。继f l o y d 断言之后，1 9 6 9 年h o a r e 发表的“计 算机程序设计一个公理学基础( a na x i o m a t i cb a s i sf o rc o m p u t e rp r o g r a m m i n g ”是f l o y d 方法 的改进。在h o a r e - - 元组p q r 中，我们称p 为前置条件，r 为后置条件。它的整体意思是假 设程序q 在执行前，条t q p 成, - r ，并且q 的执行能终止，那z , q 终止以后有条竹r 成立。举个 例子来看，例如： r ( e ) i z ：= e ) 7 ( z ) 表示：若在执行赋值语句2 ：= e 时，前提条件r ( e ) 成立，则在执行后条件r ) 成立。因此，公 理方法的基础是一个逻辑系统，包括一组公理和推理规则。 指称语义 最早提出指称语义思想的是英国牛津大学的教授c h r i s t o p h e rs t r a c h e y 教授，之后d a n a s c o t t 教授的论域理论为指称语义学打下了坚实的理论基础。指称语义的基本思想是使语言 5 2 2 形式语义学简介 第二章背景知识 的每个成分对应于- 个数学对象，它不涉及语言的执行过程，而只是考虑各成分执行的 ， 最终效果，并认为此最终效果不依赖于其执行过程。由于指称语义是基于数学理论提出来 的，这就便于我们去研究程序，举个例子来讲可以去证明两个程序的等价等。目前有很多 种方法来描述指称语义的，比如c s p 的欠败成功( f a i l u r e s d i v e r g e n c e s ) 模型，u i p 方法等。 代数语义 代数语义学始于对抽象数据类型的研究，它的特点是用代数的方法来处理满足一计算 逻辑的各种模型，把模型的集合看成是代数结构。代数语义学的公理规定了算子的组合规 则和约束，算子集和域上的值集的关系正好是代数系统研究的范畴。因此，在代数语义中， 处理要研究健康条件，完备性等公理体系的概念外，还要研究模型之间的关系。指称语义 可以进步推导出程序的- 些有趣的性质，当然这些性质也可以通过操作语义利用互模拟 理论得到。它们大多数都用代数法则简洁而优美的表示出来。而大多数代数法则可以表示 成等式如p = q ，也就足说p 在任何时刻都能被q 所替代。从这个意义上来说，程序可以利 用代数法则化成规范形式。 操作语义 1 9 6 1 年英国的p j l a n d i n 使用“栈环境控制外储”抽象机器( 简称s e c d ) ，第一次系 统地、严格地陈述了表达式的操作语义。同时，毋m 公司的维也纳实验室在6 0 年代提出了 描述操作语义的一种元语言一一维也纳定义语言( 简称v 】) l ) 。到了1 9 8 1 年，英国爱丁堡大 学的p l o t k i n 教授提出了种新的操作语义描述方法，该方法称为结构化的操作语义。它的 基本细想是符合成分的操作语义应该可以归结为它的各个组成部分的操作语义。这种方法 具有指称语义学的结构式特征。 程序语言的操作语义显示了该程序是如何运行的 1 7 】。程序的操作语义不是定义程 序执行后所观察到得整体效果，而足给出程序执行过程中可能发生的单步步骤所构成的 完备集合。个单步步骤的操作语义通常以s o s ( 结构化操作语义，s 咖c t u r a jo p e r a t i o n a l s e m a n t i c s ) 【1 8 的形式给出。在很多语言中s o s 已经成功的被用来描述操作语义，s o s 中 每个单独的步骤表示为个变迁。个程序语言的操作语义通常包含系列变迁规则的 集合。 每+ 个变迁规则都有如下的形式； c _ c 其中c 是用来描述程序在进行一个典型步骤前的执行机制状态的结构，c 7 则是用 来描述执行后的状态的。对于一些语言而言，程序的变迁规则有好几种类型，为此变 迁c 哼可以被扩展成如下形式： c 上c r 6 鼻 ： - p 2 3 设计模式简介第二章背景知识 其中三可以被认为足变迁类型。 对于某些语言，他们的操作语义被要求去建立一个能描述单个事什。的行为，这样的 话，变迁规则义可以写成t 其中，n 是可以被程序立即执行的动作。 c 二c 2 3 设计模式简介 “软什危机”使程序设计人员明白难于维护的软件成本是极其昂贵的，当软什的规模 不断扩大时，这种软件的综合成文更加难以负担，并且即使投入了高昂的资金也不能确保 得到可靠的产品。而软什复用、软件熏构和设计模式作为解决这一问题的有效方法，成为 软件工程领域的重要研究课题。软件复用的主要思想是，将软什堪称是由不同功能部分 的“组件”所拼装而成，每一个组件可以被设计为完成同类工作的通用t 具，这样如果完 成各种工作的组什被建立起来以后，编写特定软什的工作就只足将各种不同组什组织品住 哪个的简单问题，这对于软什产品的最终质量和维护丁作都有本质性的改变。软什霞构指 在不改变代码的外部行为的情况下而修改源代码，所以也被称为代码重构。重构既不修正 错误，也不增加新的功能性，其目的是提高代码的可读性和修正代码内都的结构设计。为 了达到软件复用的要求，需要综合考虑代码设计的合理性与可扩展性，设计模式作为前人 经验的总结，经过了长期的验证，为此提供了一条途径。 模式，就是在特定场合下，对特定问题的经验解决方法的总结，而设计模式( d e s i g n p a t t e r n ) 这一术语最早出现在建筑行学和人类学中，意在提供一套针对建筑设计中经常出现 的各种问题的解决方案。当时建筑行业的设计师们意识到需要共享正确有效的设计思路， 从分享经验和吸取教训中获益。c h i r s t o p h e ra l e x a n d e r 在他的书t h et i m e l e s sw a yo f b u i l d i n g 中提出了“质量能够客观评价吗? ”的思想，旨在预示人们希望能够就某些东西达成共识。 同时，他在描述城市和建筑模式时说：“每一个模式描述了个在我们周围经常发生的阀 题，以及该问题的解决方案的核心，这样，你就能一次又一次的使用该方案而不必做曩复 劳动”。受此观点的影响，8 0 年代后期，设计模式进入了计算机系统领域，面向对象的设计 与开发方法逐渐得到普及。在软什开发过程中，也会在菜特定场合中遇到先前经常出现 或感觉曾相识的问题，套用原有的已经证明过的解决方案，或参考别人的成熟方法往往十 分有效。通过将这种经验和技巧积累并加以抽象，最终形成了软什开发中的设计模式。其 本质上是工程经验的总结，参照开闭，里氏代换，合成复用等多种面向对象的设计原则，实 现了提高代码复用度与可扩展性，从而增强系统可维护性的目的。 g o f 合著的设计模式【5 】( 1 9 9 5 年出版) 第一次将设计模式提升到理论的高度，并 7 2 3 设计模式简介第二章背景知识 将之规范化。书中从动机、适用性、参与者、应用场景、实现、应用效果、解决方案等多 方面描述了设计模式。对于特定的设计问题，书中提供了个经过充分验证的通用模式 的解决方案，每个模式通过描述其组成方式、责任、相互关系以及它们的协作方式来具 体指定。一般而言，一个完整的设计模式由四个基本要素组成：模式名称( p a t t e r nn a m e ) ，问 题( p r o b l e m ) ，解决方案( s o l u t i o n ) 和效果( c o n s e q u e n c e s ) 。问题，即模式适用的场景；解决方案 描述设计巾各组成部分( 如类、对象) 的功能及协作关系；效果用于评价应用模式后的结果 与负作用。当然在实际的系统设计与开发中，加上随着系统规模的日益庞大，没有种设计 模式能够独立解决所有问题，设计模式之间存在着相互支持、相互依赖的关系。理解设计 模式及其相互间的关系，有助于很好地解决多模式协同应用时产生的新问题。 g o f 的设计模式中共收录了2 3 种经典模式，当然真正的设计模式不止2 3 种。而 这2 3 种模式又根据设计目的的不同分为三大类：创建型模式、行为型模式以及结构型模 式。 创建型模式和对象的创建过程有关。通过实例化将职责委托给其他对象，隔离客户 程序与具体类型实例化的依赖关系，保证外部系统获得期望的具体类型实例且不发 生直接的引用。创建型模式有s i n g l e t o n 模式，a b s t r a c tf a c t o r y 模式等。 结构型模式用于处理类或对象的组合。通过构建比较灵活的体系，组织不同的对象， 在这个的基础上完成比较复杂的类型系统，同时参与组合的各类型之间始终保持相 对松散的结构关系。典型的结构型模式有c o m p o s i t e 模式，a d a p m r 模式等。 行为型模式描述了类和对象的交互、分配职责、相互问的通信模式等，关注于应 用运行过程中的算法的提供和通信关系的梳理。典型的行为型模式有o b s e r v e r 模 式，i t e r a t o r 模式等。 设计模式的核心思想是“封装变化”。无论哪种模式，都是寻找软件中可能存在的“变 化”，然后利用抽象的手段对这些变化进行封装。在面向对象开发过程中，设计模式为提高 系统的质量与可扩展性提供了保障，在代码复用、增强可读性、提高代码可靠性、降低组 建耦合度等方面发挥着至关重要的作用。 在本文的研究工作中，我们将借用操作语义学的手段来研究r c o s 语言，其具体的操作 语义的规则请见下章。 8 第三章r c o s 的操作语义 本章中，我们先介绍了面向对象语言r c o s 的语法规则，包括面向对象系统、类声明、 表达式和命令等。接着，以s o s ( 结构化操作语义) 的形式给出了r c o s 操作语义的变迁规 则。为了使得定义的变迁结构中包含的信息恰到好处，引进了对象池和运行环境等概念： 同时又把对象图概念嵌入到变迁结构中。最后，依次给出了r c o s 的操作语义，包括原予命 令和复合语句的操作语义。 3 1r c o s 语法规则 r c o s 的主要部分与j a v a 和c + + 语法相似，其语法包括面向对象系统、类声明、命令和 表达式 6 】。 在r c o s 中，一个面向对象系统( 或者程序) s 通常被表示为 s = c d e c l s m a i n 的形式，包括有限个类的声明部分c d e d s 和一个主方法m a i n 。其中主方法m a i n 形 如( e x t v a r ，c ) ，此处e x t v a r 是有限个外部变量的集合，c 为一个命令。由于r c o s 中主方 法m a i n 无法直接获得类的属性，于是它只能调用类声明部分中方法和操作外部变量。 3 1 1 类声明 类声明部分c d e c l s 是一系列有限个类声明的串行，即 c d e c l s ：= c d e c h ；c d e c l 2 ；c d , e 弛s k 其中每个c d e c l s f 的形式如下g c l a s s ne x t e n d s m p r i v a t e 矾t l2a l ，= a m ； p r o t e c t e dv 1v l = b i ，u n = k ； p u b l i cw 1t 0 1 = e l ，w k = e k ； m e t h o dm l ( t n2 ：1 1 ，t 1 2y i 2 ，t i 3z 1 3 ) 【c l 9 3 1 r c o s 语法规则第三章r c o s 脓作语义 m l ( 噩1 锄l ，丑2 扰2 ，丑3 忍3 ) ( q ) ) 其中： 每个类都被声明为私有p r i v a t e 或者公共舭6 跣c 。默认的属性为公共。 类和类m 是不同的类名，且类m 为类的直接父类。 蒯z p r i v a t e ( p r o t e c t e d 、p u b l i c ) 声明了类的私有( 保护、公共) 属性、类型及初始 值。 关键字m e t h o d 声明了方法m t 以及对应的输入参数t a 妃1 ，输出参数互2y i l 和输入输 出参数砀麓1 。 戗是方法砚的方法体，它是一系列命令，将在下文中给出定义。 3 1 2 表达式 r c o s 系统中，表达式的构造如下： l e ：= z is e l f l e a e ：= zei sceo a in u l l s e l fi ( c ) ef ( e ) 其中： z 表示个变量，口表示一个属性。 s e l f 是当前时刻的活动对象的引用。 l e a 表示对那个：e 所指向对象的属性a 的引用。而e o 则表示e 的一个属性a 。 n u l ln u l l 表示特殊类m 珏，l 的一个特殊对象，它可以是所有类的予类。 ( c ) e 是类型铸造。 f ( e ) 表示一个私有类型的内嵌表达式。 3 1 3 命令 r c o s 语言支持典型的面向对象编程构造： 1 0 c qb 睁c c o n d i t i o n a l e n c礼d 礼一d e t e r m i n i s m b 幸c i n t e r a t i o n z e m ；型；笪) m e t h o dc a l l l e ：= e a s s i g n m e n t lc 亿e 叫( 2 e ) 【e 】o b j e c tc r e a t i o n 这里： 6 是布尔表达式，e 是表达式，j e 是可能出现在赋值等式左边的表达式。 l e m ( 当型；笪) 表示对象f e 一个方法m 的调用；其中表达式e ，口，t 分别表示输入参数，输 出参数和输入输出参数。 v a ttz = e 表示一个本地变量z 的声明，其类型为t ，初始值为e 。e n dz 则表示解除 本地变量z 的作用域。 c n e w ( z e ) e 仓 j 建一个类型为c 的新对象，它的属性初始值为之前c 中所定义的，它 被赋予个引用指向2 e 。 s k i p 表示没有任何副作用的空语句；c h a o s 表示忽略；ci - ic 为非确定性选择；c ；c 为 串行语句；c 司b c 为条件选择，和大部分语言中流行的t ，语句类似；b 幸c 为迭代； 在r c o s 中，s 七p ，c h a o s ，cnc 的引入是为了规范和精化的需要。 3 2 变迁规则 在给出操作语义的结构之前，我们首先引入几个能记录状态的变量。直觉上，我们很 容易发现，一个疋o s 系统是由一族有着某种关系的对象组成，而每个对象则分别拥有自己 的状态和行为。从全局角度来看，系统的运行状况可以通过观测所有对象的状态来刻画。 显而易见，串行程序的执行也实实在在的在对象之间发生交互【1 5 ，1 6 】。 对象和对象池 定义3 2 1 对象和对象池 3 2 变迁规则 第三章r c o s 的操作语义 对象池 答u ) 对象 e 箩 其中，佗i t i a l t y p e c n a m e ，a t t r sd ：e u a t t r _ n a m e _ v a l u e ) 对象池足一一系列对象的集合，每个对象t 则是个三元组，第一个元素的记是相关对 象的唯一标识；i n i t i a i t y p e c n a m e 是对象的原始类型，这里的原始类型是对象的真 正类型。比如有这样一个程序段： a 0 = 竹e 伽b ( ；) 类型b 衍生出类型a ，a 类型的变量0 是b 类型的一个对象的引用，从而变量0 的原始类型 足b ，而非a ；a t t r s 包含了对象的所有属性，它的每个元素都是属性名字到它所对应的值 的个映射。 运行环境 直观上来看一个运行着的程序，我们可以认为那是一系列串行的方法调用，而每个方 法又和一组与之对应的变量息息相关。基于这个事实，我们可以认为程序的运行环境就是 个堆栈。堆栈中的每个元素都记录了方法和其相关的变量。当方法调用开始时，运行的 堆栈中会压入一个元素，直到方法调用结束时，顶端元素会被吐出来。由于r c o s 系统支持 并发算子，那么它的运行环境可以看成是些列堆栈的集合 1 6 ，1 5 】。 首先给出关于堆