论文部分内容阅读
摘 要：基于构件的软件开发是当前软件开发的主流泛型。如何形式化地刻画构件的组装过程是业界关注的重要问题之一。本论文对Petri网进行扩展，作为演化活动的表示基础。在此基础上分析了构件的动态性质与结构性质，给出了组装的原理、组装的方式与组装的框架，对复合组装的行为与框架性质进行分析。
关键词：Petri网；构件性质；构件组装
1 构件的Petri网表示及性质
1.1 扩展Petri网表示构件
形式化构件定义由两个部分组成，输入输出规约，把构件封装为一个边界单入口单出口的接口规约，其次是由构件内部组成，内部包括构件的功能化属性和参数化属性，参数化属性是内部组成间的联系机制，功能化发生是实现内部间交互式行为的动作部件，这些部件间的相互关系组成了一个构件内部实体，通过规约相互依赖、相互生存、相互作用，从而在接口处产生一组操作序列，引发构件行为并感染其他相连接的构件。
定义1 构件C由一个4元组组成，是Petri网的一种扩展，C=：
①P为有限库所集，表示构件状态；其中P？勐{p，ip，op}；其中ip，op出入口处的特殊库所，是构件间相互通信、相互作用、相互依赖的接口库所；
②T为有限变迁集，表示构件操作与实现，构件的行为动作；
③F？哿P×T∪T×P，表示有向的弧集，是构件内部相互操作行为与状态的约束关系；
④W为非空有限集，表示库所变迁中功能属性和参数化属性组合及数量，构件C中弧集集合的权函数与容量函数产生的数据类型集；
⑤I/O={IP，OP}IP/OP？哿P分别为构件C的边界出入口集，有？坌ip∈IP，？坌op∈OP
定义2 构件网C-net（CN）系统是由多元组组成CN=
其中，C为基网，C由无限个子构件C1C2C3…CK组成，M为构件系统的标识集，当M=M0时系统为初始标识，L为连接件，连接构件网中所有构件从面组成一个构件网拓扑结构。
1.2 构件的分析方法
1.2.1 结构化简
结构化简用于处理与分析复杂问题的一种手段，基本原则在保持化简前后构件网性质不变前提下，将多个不同的位置或迁移抽象为单个的位置或迁移。同时保持构件网的活性、有界性和安全性等。几种结构化简方案：（图1）
1.2.2 覆盖树
覆盖树设∑=（P，T，F，W，M0），是一个构件网系统。∑的可达树是这样的一棵树，它的节点用从P到N∪{？棕}的函数标记，它的弧用T的元素标记。
2 层次Petri网描述复合构件组装
2.1 复合组装行为分析方法
2.1.1 二叉树结构表示复合构件网组装运算
我们可以用二叉树的结构和动态特性来表达复合构件组装过程的运算表达，根据层次Petri网描述复合组装过程，显然也是递归的分层过程。
2.1.2 构件网系统可替换性分析
构件的可替代性，指组装框架中一个构件被另外一个属性性质相同的构件替换，替换后不影响整个框架性质与功能，构件框架中表达可替换性引入投影继承。
①如果构件网中扩展构件从构件网事件流中得到一个标识，经过变换处理后该标识产生的结果返回到构件系统中，那么该扩展构件满足投影继承。
②如果构件网中扩展的构件，运行过程与结果不改变构件网执行特性，那么任意结构的扩展构件加入构件网中满足投影继承。
③如果构件网中扩展的构件，在扩展后能够正常启动系统，并且扩展后的构件不影响构件网原系统的控制指挥权，那么该扩展的构件结构满足投影继承。
如果替换的构件满足以上3个投影继承规则之一，则该构件网有可替换性。
证明：根据三种投影规则，第一种扩展构件经过变换处理标识后产生结果返回到构件系统中，结构上构件网保持有界性、安全性、公平性和活性，所以是可替换的。第二种扩展的构件，运行结果不改变构件网特性，过程中结构上构件网也保持有界性、安全性、公平性和活性，所以是可替换的。第三种扩展的构件能够正常启动系统，不影响构件网原系统的控制指挥权，并且结构上构件网保持有界性、安全性、公平性和活性，所以是可替换的。
2.2 复合组装框架性质分析
2.2.1 复合构件网可靠性判定
进行构件组成的必要前提是组装后的复合构件能够保持原有构件的特征，保证组装方式的可靠性。
定义 4 一个复合构件网CN是可靠的，当且仅当：
①CN是安全的；
②任一初始状态ip的可达状态M，必存在从M到状态op的发生序列：M[t>M′，M′={ip→op}；
③不存在死锁与陷阱状态： （·pp·）， （p··p）
④状态op是唯一的正常结束状态：M[t>M′并且Mop。
定理2 如果构成复合构件网的每个构件网C1，C2，…，Ck是可靠的，则复合构件网是可靠的。
证明 对于由4种操作组装形成的复合构件网：
①由之前定理可知4种基本操作都是安全的，CN初始状态只有一个标识，而且每个子构件网安全的，因此它是安全的；
②我们对其中第一种顺序组装方式进行证明：
？坌M′∈R（M0），（CN，M0）[t>M′，因为CN中只有一个标识，此时若标识在构件网C2，由于C2是可靠的，则（CN，M′）[t>（CN，{op2=OP}）；若标识位于C1，则有（CN，M′）[t>（CN，{op1}），类似可证明选择，并行，重复组装结构；
③我们对其中的选择组装为例子证明：
对于tip1，tip2，top1，top2，显然它们是使能的，对于？坌t∈Ti，因为Ci（i=1，2）是可靠的，也不会存在死变迁，由此不存在死锁陷阱，其他三种类型的组装方式也可类似证明； ④反证法，假如状态op不是唯一正常结束状态，那么？埚M∈R（M0）使得（CN，M0）[t>M且M是一个结束状态，由条件2知（CN，M0）[t>M？圯（CN，M0）[t>op这是矛盾的；综合1，2，3，4，定理得证。
2.2.2 动态不变性判定
定义5 由两个构件C1=，C2=及连接件L通过组装操作而形成的构件网成为复合构件网CN=，我们分解组装操作为4类，既顺序，选择，并行，重复：
CN+=（C1+C2），CN=（C1C2），CN=（C1C2），CN*=（C1*）；
定义6 集合N，Ni？哿N，？椎为N上的一个函数，г：？椎（N）→？椎（Ni），使得？坌？椎（N），？椎（Ni），гN→Ni（？椎（N））为从？椎（N）删除属于N-Ni的字符后所得到的，称гN→Ni是从N到Ni的投影。
由子系统综合而成的大系统应该保持系统在状态行为的特征，也就是说，大系统的状态与行为系统与原子系统是相吻合的。
定理3 构件复合组装操作满足状态不变性、行为不变性。
证明 ①使用例证法，在上图例子中（二叉树结构表达式（a+b*）（cd）所对应的复合构件网组装过程），对应不同的组装操作，复合构件网所对应的投影分别为
CN+=a+b={N|N=N1+N2，N1∈a，N2∈b}，гN→N2（CN+）=a；
CN=ab={N|N=N1N2，N1∈a∪b，N2∈c∪d}，гN→N2（CN）=a∪b；
CN=ab={N|N=N1N2，N1∈c，N2∈d}，гN→N2（CN）=c；
CN*=b*，{N|N=n*，N∈b}，гN→n（CN+）=b；
由此得到，4种组装后的复合构件网满足状态行为完全不变性；
②因为4种组装操作所形成的复合构件网，在输入时候只存唯一标识M0，而且4个构件网a，b，c，d互相不重叠，因此复合构件网上投影分别等于各自构件的初始状态，即满足状态行为完全不变性。
2.2.3 良性判定
定义7 在构件网CN=中，如果满足下列条件，则称构件C是良性的：
①构件CN是单入口，单出口的，即|CN.ip|=1，|CN.op|=1；
②对于？坌p∈P、？坌t∈T，若（p，t）F或（t，p）∈F，构件C是匹配的；
③对于？坌t∈T和？坌pi∈·t，有WF（pi，t）=C.W，（i=1，2，…，n）；
定理4 两个良构构件网C1=，C2=及连接件L，通过4种组装方式而形成的复合构件网CN=也是良性的。
证明 我们在此对4种组装操作中的其中一种顺序组装进行证明，其他三类组装的证明相似。
由于C1=，C2=是两个良构构件网，根据构件良构的性质①有|C1.ip|=1，|C1.op|=1；|C2.ip|=1，|C2.op|=1，且C1.op，C2.ip出入口合并，合并后CN.ip，CN.op 分别由C1.ip，C2.op中的入接口合并而成，因此构件网CN仍是单入口，单出口的，即|CN.ip|=1，
|CN.ip|=1；CN满足构件良构的性质①；
由于C1=，C2=是两个良构构件，根据构件性质有对于？坌p′∈P1∪P2，？坌t′∈T1∪T2，若（p′，t′）∈F1F2或（t′，p′）∈F1F2，则p与t之间匹配的；根据顺序组装规则中的WF（P1.op，t）∈CN.W；WF（t，P2.ip）∈CN.W；因此连接件与P1.op，P2.ip之间类型匹配的，在组合后的构件网CN中，对于？坌p∈P和？坌t∈T，若（p，t）∈F或（t，p）∈F，则构件CN中的p与t是类型匹配的，CN满足构件良构的性质②；
由于C1=，C2=是两个良构构件，根据良构的性质③对于？坌t′∈T和？坌pi∈·t′（i=1，2，…，n），有WF（pi，t）=CN.W。根据顺序组装规则，构件网CN中对于tT和？坌pi∈·t（i=1，2，…，n）都满足于WF（pi，t）=CN.W，因此CN满足构件良构的性质③；
综上所述，定理得证。
3 总结
本文基于Petri网给出了构件的表示模型，并在此基础上给出了构件网的可靠性判定、动态不变性以及良性判定方法。上述方法的给出为演化活动的自动执行奠定了理论基础。
在接下来的工作中，将对该方法的普适性进行检验。同时，并在此基础上建立软件演化活动综合管理机制，为进一步提高软件演化效率提供理论支持。
参考文献：
[1]OMA. 1998. The Common Object Request Broker： Architecture and Specification 2.2.
[2]Dale Rogerson著，杨秀章译. COM技术内幕[M].北京：清华大学出版社，1999.
[3]Rima Patel Sriganesh Gerald Brose著，罗时飞译. 精通EJB（第三版）[M].电子工业出版社，2006.
[4]袁崇义.Petri网原理与应用[M].北京：电子工业出版社，2005.
[5]李彤，孔兵，金钊，王黎霞.软件并行开发过程[M].科学出版社，2003.
[6]Tong Li. An Approach to Modelling Software Evolution Processes[M]. 北京：清华大学出版社，2008.
[7]李长云，何频捷，李玉龙.软件动态演化技术[M].北京大学出版社，2007.
关键词：Petri网；构件性质；构件组装
1 构件的Petri网表示及性质
1.1 扩展Petri网表示构件
形式化构件定义由两个部分组成，输入输出规约，把构件封装为一个边界单入口单出口的接口规约，其次是由构件内部组成，内部包括构件的功能化属性和参数化属性，参数化属性是内部组成间的联系机制，功能化发生是实现内部间交互式行为的动作部件，这些部件间的相互关系组成了一个构件内部实体，通过规约相互依赖、相互生存、相互作用，从而在接口处产生一组操作序列，引发构件行为并感染其他相连接的构件。
定义1 构件C由一个4元组组成，是Petri网的一种扩展，C=
①P为有限库所集，表示构件状态；其中P？勐{p，ip，op}；其中ip，op出入口处的特殊库所，是构件间相互通信、相互作用、相互依赖的接口库所；
②T为有限变迁集，表示构件操作与实现，构件的行为动作；
③F？哿P×T∪T×P，表示有向的弧集，是构件内部相互操作行为与状态的约束关系；
④W为非空有限集，表示库所变迁中功能属性和参数化属性组合及数量，构件C中弧集集合的权函数与容量函数产生的数据类型集；
⑤I/O={IP，OP}IP/OP？哿P分别为构件C的边界出入口集，有？坌ip∈IP，？坌op∈OP
定义2 构件网C-net（CN）系统是由多元组组成CN=
其中，C为基网，C由无限个子构件C1C2C3…CK组成，M为构件系统的标识集，当M=M0时系统为初始标识，L为连接件，连接构件网中所有构件从面组成一个构件网拓扑结构。
1.2 构件的分析方法
1.2.1 结构化简
结构化简用于处理与分析复杂问题的一种手段，基本原则在保持化简前后构件网性质不变前提下，将多个不同的位置或迁移抽象为单个的位置或迁移。同时保持构件网的活性、有界性和安全性等。几种结构化简方案：（图1）
1.2.2 覆盖树
覆盖树设∑=（P，T，F，W，M0），是一个构件网系统。∑的可达树是这样的一棵树，它的节点用从P到N∪{？棕}的函数标记，它的弧用T的元素标记。
2 层次Petri网描述复合构件组装
2.1 复合组装行为分析方法
2.1.1 二叉树结构表示复合构件网组装运算
我们可以用二叉树的结构和动态特性来表达复合构件组装过程的运算表达，根据层次Petri网描述复合组装过程，显然也是递归的分层过程。
2.1.2 构件网系统可替换性分析
构件的可替代性，指组装框架中一个构件被另外一个属性性质相同的构件替换，替换后不影响整个框架性质与功能，构件框架中表达可替换性引入投影继承。
①如果构件网中扩展构件从构件网事件流中得到一个标识，经过变换处理后该标识产生的结果返回到构件系统中，那么该扩展构件满足投影继承。
②如果构件网中扩展的构件，运行过程与结果不改变构件网执行特性，那么任意结构的扩展构件加入构件网中满足投影继承。
③如果构件网中扩展的构件，在扩展后能够正常启动系统，并且扩展后的构件不影响构件网原系统的控制指挥权，那么该扩展的构件结构满足投影继承。
如果替换的构件满足以上3个投影继承规则之一，则该构件网有可替换性。
证明：根据三种投影规则，第一种扩展构件经过变换处理标识后产生结果返回到构件系统中，结构上构件网保持有界性、安全性、公平性和活性，所以是可替换的。第二种扩展的构件，运行结果不改变构件网特性，过程中结构上构件网也保持有界性、安全性、公平性和活性，所以是可替换的。第三种扩展的构件能够正常启动系统，不影响构件网原系统的控制指挥权，并且结构上构件网保持有界性、安全性、公平性和活性，所以是可替换的。
2.2 复合组装框架性质分析
2.2.1 复合构件网可靠性判定
进行构件组成的必要前提是组装后的复合构件能够保持原有构件的特征，保证组装方式的可靠性。
定义 4 一个复合构件网CN是可靠的，当且仅当：
①CN是安全的；
②任一初始状态ip的可达状态M，必存在从M到状态op的发生序列：M[t>M′，M′={ip→op}；
③不存在死锁与陷阱状态： （·pp·）， （p··p）
④状态op是唯一的正常结束状态：M[t>M′并且Mop。
定理2 如果构成复合构件网的每个构件网C1，C2，…，Ck是可靠的，则复合构件网是可靠的。
证明 对于由4种操作组装形成的复合构件网：
①由之前定理可知4种基本操作都是安全的，CN初始状态只有一个标识，而且每个子构件网安全的，因此它是安全的；
②我们对其中第一种顺序组装方式进行证明：
？坌M′∈R（M0），（CN，M0）[t>M′，因为CN中只有一个标识，此时若标识在构件网C2，由于C2是可靠的，则（CN，M′）[t>（CN，{op2=OP}）；若标识位于C1，则有（CN，M′）[t>（CN，{op1}），类似可证明选择，并行，重复组装结构；
③我们对其中的选择组装为例子证明：
对于tip1，tip2，top1，top2，显然它们是使能的，对于？坌t∈Ti，因为Ci（i=1，2）是可靠的，也不会存在死变迁，由此不存在死锁陷阱，其他三种类型的组装方式也可类似证明； ④反证法，假如状态op不是唯一正常结束状态，那么？埚M∈R（M0）使得（CN，M0）[t>M且M是一个结束状态，由条件2知（CN，M0）[t>M？圯（CN，M0）[t>op这是矛盾的；综合1，2，3，4，定理得证。
2.2.2 动态不变性判定
定义5 由两个构件C1=
CN+=（C1+C2），CN=（C1C2），CN=（C1C2），CN*=（C1*）；
定义6 集合N，Ni？哿N，？椎为N上的一个函数，г：？椎（N）→？椎（Ni），使得？坌？椎（N），？椎（Ni），гN→Ni（？椎（N））为从？椎（N）删除属于N-Ni的字符后所得到的，称гN→Ni是从N到Ni的投影。
由子系统综合而成的大系统应该保持系统在状态行为的特征，也就是说，大系统的状态与行为系统与原子系统是相吻合的。
定理3 构件复合组装操作满足状态不变性、行为不变性。
证明 ①使用例证法，在上图例子中（二叉树结构表达式（a+b*）（cd）所对应的复合构件网组装过程），对应不同的组装操作，复合构件网所对应的投影分别为
CN+=a+b={N|N=N1+N2，N1∈a，N2∈b}，гN→N2（CN+）=a；
CN=ab={N|N=N1N2，N1∈a∪b，N2∈c∪d}，гN→N2（CN）=a∪b；
CN=ab={N|N=N1N2，N1∈c，N2∈d}，гN→N2（CN）=c；
CN*=b*，{N|N=n*，N∈b}，гN→n（CN+）=b；
由此得到，4种组装后的复合构件网满足状态行为完全不变性；
②因为4种组装操作所形成的复合构件网，在输入时候只存唯一标识M0，而且4个构件网a，b，c，d互相不重叠，因此复合构件网上投影分别等于各自构件的初始状态，即满足状态行为完全不变性。
2.2.3 良性判定
定义7 在构件网CN=
①构件CN是单入口，单出口的，即|CN.ip|=1，|CN.op|=1；
②对于？坌p∈P、？坌t∈T，若（p，t）F或（t，p）∈F，构件C是匹配的；
③对于？坌t∈T和？坌pi∈·t，有WF（pi，t）=C.W，（i=1，2，…，n）；
定理4 两个良构构件网C1=
证明 我们在此对4种组装操作中的其中一种顺序组装进行证明，其他三类组装的证明相似。
由于C1=
|CN.ip|=1；CN满足构件良构的性质①；
由于C1=
由于C1=
综上所述，定理得证。
3 总结
本文基于Petri网给出了构件的表示模型，并在此基础上给出了构件网的可靠性判定、动态不变性以及良性判定方法。上述方法的给出为演化活动的自动执行奠定了理论基础。
在接下来的工作中，将对该方法的普适性进行检验。同时，并在此基础上建立软件演化活动综合管理机制，为进一步提高软件演化效率提供理论支持。
参考文献：
[1]OMA. 1998. The Common Object Request Broker： Architecture and Specification 2.2.
[2]Dale Rogerson著，杨秀章译. COM技术内幕[M].北京：清华大学出版社，1999.
[3]Rima Patel Sriganesh Gerald Brose著，罗时飞译. 精通EJB（第三版）[M].电子工业出版社，2006.
[4]袁崇义.Petri网原理与应用[M].北京：电子工业出版社，2005.
[5]李彤，孔兵，金钊，王黎霞.软件并行开发过程[M].科学出版社，2003.
[6]Tong Li. An Approach to Modelling Software Evolution Processes[M]. 北京：清华大学出版社，2008.
[7]李长云，何频捷，李玉龙.软件动态演化技术[M].北京大学出版社，2007.