2018, Vol. 39
膜计算(membrane computing, MC)也称P系统, 是自然计算的一个分支。它通过模拟细胞、组织、器官等生物结构处理化学物质的方式, 建立具有良好计算性能的计算模型。该模型具有同步性、非确定性、并行性等性质, 可应用于分布式系统和并行计算的形式化建模[1], 实现了分布式系统以及并行计算中复杂度较高的通信过程的建模, 保证了二者通信过程的安全性以及正确性[2]。
1998年, 罗马尼亚籍国际信息科学院院士Gheorghe Pǎun提出了MC的定义。此后, Pǎun等[3]对MC中的通信机制进一步探讨, 提出了分布式P系统, 使MC初步具有了膜间对象传递的功能。Qi等[4]提出了细胞膜演算的概念, 并将该演算应用于网格事物的形式化建模中。Krishna等[5]提出了移动膜的概念, 移动膜融合了进程演算等演算方法, 拥有更多的反应规则类型以及通信机制。Aman等[6]提出了扩展移动膜的概念, 对表层膜的定义进行了深入的探讨, 打破了MC定义中表层膜不能传递对象的规定。同时, MC类形式化方法已经成功应用于图形学、密码学、系统生物学[7-9]等。
尽管MC类形式化方法对区域间通信问题有很好的建模能力, 能够完成对分布式系统和并发系统中组件的输入分配、网格事物的信息交互、服务组合的信息传递以及组合过程等的形式化建模。但对演化这一普遍存在于系统中的问题进行建模时, 因为MC类形式化方法无法在建模完成的系统中添加反应规则, 且建模完成的系统中不存在演化所需的规则, 所以MC类形式化方法不适用于演化过程的建模。针对这个不足, 本文提出一种可以对系统的演化过程进行建模的形式化模型—通信膜演算(communication membrane calculus, CMC)。CMC可以在已有的模型中添加演算规则, 适用于对系统演化过程的建模。CMC既是对MC类形式化方法的一种扩展, 也是对演化的形式化方法工作的一个补充。CMC可以对软件演化、本体演化、软件产品线演化等演化过程进行建模, 是一种具有通用性的形式化方法。
本文给出CMC的定义及操作语义; 利用自动机, 对CMC的性质进行了分析, 分析了CMC适用于演化过程建模的能力; 通过一个软件产品线演化场景的形式化建模, 说明了CMC对于系统演化过程建模的适用性。
1 通信膜演算CMC模型包含三个主要元素:膜结构、对象、反应规则。CMC的演算过程可以概括为:它开始于通信膜系统的某个初始格局(初始的膜结构和每个区域内的初始对象), 演算随着格局的转移进行下去, 直至在某个膜内出现演算结果时停止。
上述描述的具体定义如下:
定义1 膜是CMC系统中将系统环境分割成独立空间的边界, 膜以及膜所围成的空间用一对带有下角标的中括号表示, 其中下角标表示该膜的名字。如[m]m表示该膜的名字为m。
定义2 膜结构是指CMC系统中膜的层次结构, 膜结构中存在三种结构关系:独立关系、包含关系和并列关系, 用独立的中括号、中括号的相互嵌套和并列表示三种关系。
在CMC中, [m]m表示独立关系, 是一个单层膜结构; [m[n]n]m表示包含关系, 这种膜结构可以称为父子膜; [m]m[n]n表示并列关系, 这种膜结构可以称为兄弟膜。任意的膜结构均能由[m]m、[m[n]n]m、[m]m[n]n这三种结构经过多次的相互包含、并列组合而成, 可以说[m]m、[m[n]n]m、[m]m[n]n是最基本的三种结构。
定义3 一个膜形成的空间去掉其子膜形成的空间称为这个膜所形成的区域。
如果一个膜中不存在子膜, 那么这个膜形成的空间就是这个膜所形成的区域。
定义4 CMC系统中的对象通常用A:B形式表示, A是对象的名字, 用字母表示, B是对象的类别。
在CMC中, 一个对象可以是一个分子、原子或者某种化学物质。在一个膜内, 同一种对象可以同时存在多个。
定义4中的对象类别用C、O或R表示, O类的对象能够触发膜类和对象类的反应规则, R类的对象能触发对象类和规则类的反应规则, C类的对象具有O或R中的一种属性, 如a:O, a:R, a:C均可以表示对象。
定义5 对象多重集是同一种对象可以出现多次的对象的集合。如{a:O, a:O, b:R}表示含有两个a:O一个b:R的对象多重集。
定义6 CMC系统中指导某个区域内的膜结构、对象多重集、反应规则发生变化的规则称为反应规则。反应规则用A→B形式表示, →前是一个对象多重集, →后是该规则所在区域的变化结果, 该结果可以为一个膜、一个对象多重集、一个反应规则集或是特定的符号。
CMC的具体定义如下:
定义7 通信膜演算是一个多元组
Π=(V, μ, O1, …, On, (R1, ρ1), …, (Rn, ρn))
式中:V是系统中包含的所有对象的集合; μ为包含n个膜的膜结构; Oi, 1≤i≤n是膜i内的对象多重集; (Ri, ρi), 1≤i≤n, 是膜i内的反应规则以及反应规则间优先级的集合; Ri是膜内的反应规则集合; ρi是规则间的优先级的集合, 规则间的优先级用>表示, >前规则优先于>后的规则进行反应。
定义8 CMC系统中, 某一时刻由膜结构、对象多重集、反应规则集、反应规则优先级集合所组成的多元组称为当前时刻的系统格局; 系统反应开始前定义的格局为这个系统的初始格局; 所有反应结束后的格局为这个系统的终止格局。
定义7是CMC的抽象定义, 而定义8描述了CMC系统在某一时刻的具体状态。定义7与定义8的关系类似于面向对象中类与实例的关系。
CMC系统利用反应规则的演算过程就是这个系统的格局依照已有的转换规则由初始格局转换为终止格局的过程。
2 规则的操作语义CMC有九种反应规则, 为了方便叙述, 先给出几个字符的解释。N为膜的名字集合, V*为对象集合, Rm为膜m内的反应规则集合, ρm为膜m内的规则优先级集合:
1)[mu:C]m→[mv:C]m, 其中m∈N, u:C, v:C∈V*, 记为:u:C→v:C。
这类规则称做对象变化规则, 表明对象的名称或者数量的变化。
2)[k]k[mu:C]m→[kv:C]k[m]m、[k[mu:C]m]k→[k[m]mv:C]k或[m[k]ku:C]m→[m[kv:C]k]m, 其中k, m∈N, u:C, v:C∈V*, 记为:u:C→v:Cin_k。
这类规则叫做对象传递规则。对象从膜m传入到膜k中, 膜k可以是膜m的兄弟膜、父膜或者子膜。
3)[k[mu:O]m]k→[k]k, 其中k, m∈N, u:O∈V*, 记为:u:O→σ。
这类规则叫做膜溶解规则。膜m溶解后, m内的对象与子膜变为其父膜k的对象与子膜, 膜m内的反应规则集合及优先级集合消失。
4)[ku:O]k→[k[m]m]k, 其中k, m∈N, u:O∈V*, 记为:u:O→[mμ, O1, …, On, (R1, ρ1), …, (Rn, ρn)]m。
这类规则叫做膜创建规则。创建的膜m只能为触发反应的对象所在膜k的子膜, 并且在膜创建规则中需要给出膜m的所有信息。
5)[mu:O]m[k]k→[k[m]m]k, 其中k, m∈N, u:O∈V*, 记为:u:O→λk。
这类规则叫做膜移入规则。膜m与其内部子膜、对象多重集、反应规则集等全部移入到膜k中, 膜m成为k的子膜。
6)[k[mu:O]m]k→[k]k[m]m, 其中k, m∈N, u:O∈V*, 记为:u:O→ηk。
这类规则叫做膜移出规则。膜m与其内部子膜、对象多重集、反应规则集等全部移出膜k, 膜m成为k的兄弟膜。
7)[mu:R]m→[m(ri, ρi), (ri, ρi)]m, 其中m∈N, u:R∈V*, (ri, ρi)∈(Rm, ρm), 记为:u:R→(ri, ρi)copy。
这类规则叫做规则复制。膜m中的规则(ri, ρi)由对象u:R触发, 进行复制, 使得膜m中存在两条规则(ri, ρi)。
8)[k]k[mu:R]m→[k(ri, ρi)]k[m]m、[k[mu:R]m]k→[k[m]m(ri, ρi)]k或[m[k]ku:R]m→[m[k(ri, ρi)]k]m, 其中k, m∈N, u:R∈V*, (ri, ρi)∈(Rm, ρm), 记为:u:R→(ri, ρi)in_k。
这类规则叫做规则传递。膜m中的规则(ri, ρi)由对象u:R触发, 传到膜k中, 变成膜k的规则。
9)[mu:R]m→[m(Rm, ρm)/(ri, ρi)]m, 其中m∈N, u:R∈V*, (ri, ρi)∈(Rm, ρm), 记为:u:R→(ri, ρi)delete。
这类规则叫做规则删除。膜m中的规则ri由对象u:R触发, ri与u:R→(ri, ρi)delete两条反应规则同时被删除。
CMC默认所有的膜均具有传递功能。从规则复制、传递以及删除的操作语义可以看出, 复制、传递以及删除的都是存在于规则集合中的反应规则。
反应规则1)~2)是对象类反应规则, 触发这两条反应的对象以及生成的对象可以是O或R中的任意一种。反应规则3)~6)是膜类反应规则, 触发这4条反应的对象只能是O类的。反应规则7)~9)是规则类反应规则, 触发这3条反应的对象只能是R类的。
定义9 如果一条反应规则ri的变化结果是两种或两种以上类型的反应规则的变化结果的并集, 那么反应规则ri就是一条复合规则。
在给出一个系统的反应规则的定义时, 可以用复合规则的形式将几种存在于同一膜中的反应规则进行整合, 减少规则的个数。
3 非确定自动机C-NA本节将利用自动机对系统演化过程进行建模。将系统的演化过程用非确定自动机C-NA表示。C-NA是一个五元组, 用(S, Σ, f, s0, Z)表示。
在C-NA中, 状态是CMC系统格局的抽象表示, 如果CMC系统刻画的是一个不会发生演化的格局, 那么C-NA的状态集合中只有一个状态, 这个状态既是初始状态又是终止状态; 如果CMC系统刻画了一个格局的演化过程, 那么C-NA就是一个状态转换的过程。本文中, CMC系统是指刻画了一个格局演化过程的系统。
C-NA中的状态s用三元组(τ, O, ψ)表示。其中, τ表示该状态所有带有名字的膜以及膜间关系, 可以用一对带下角标的中括号表示膜, 下角标为膜的名字, 膜间关系用中括号的并列和嵌套表示, 并且τ≠∅;O为该状态包含的对象多重集的集合, O可为空; ψ表示该状态中每一个对象多重集所在的膜的名字的集合。
本文将一条反应规则作为C-NA字母表Σ中的一个字符。这样字母表中的字符就可以分为九类字符。但反应规则中有复合规则这种特例, 所以需要对复合规则进行拆分。如果一条复合规则ri包含n(n为2~9的整数)种反应规则, 需要引入对象πi作为中间消耗对象对其进行拆分, 拆分原则如下:
1) 引入n个对象π1, π2, …, πn,
2) 反应规则ri的“→”前的对象多重集Oi作为拆分后第一条规则的“→”前的对象多重集, 第一条规则的→后为引入的n个对象, 第一条规则为:Oi→π1, π2, …, πn;
3) ri中“→”后每一种结果相应变为一条新的反应规则“→”后的结果, 新的反应规则“→”前的对象在π1, π2, …πn中选取一个, 且保证每个πi都能触发一条反应规则。
如规则a:O→a:Oin_2σ, 需要引入对象π1, π2, 并将规则拆分为a:O→π1π2、π1→a:Oin_2和π2→σ。
在C-NA中状态转移函数表示格局使用反应规则转变为另外一个格局的过程。同时初始格局得到的状态构成了初始状态集, 终止格局得到的状态构成了终止状态集。
对于任意一个CMC系统ΠS, 把ΠS的初始格局抽象为一个初始状态集S0, 每一次演化得到的格局均抽象成一个状态集Si, ΠS的终止格局抽象为终止状态集SZ, 那么就能得到ΠS的状态集合SS=S0∪…∪Si∪…∪SZ。同时将ΠS中所有膜内拆分过的反应规则集进行合并, 得到ΠS的反应规则的并集RS=R1∪R2∪…∪Rn。这样, 我们就能将一个演化的CMC系统ΠS转换为C-NA, 转换算法如下:
输入:一个CMC系统ΠS; 输出:C-NA自动机(S, ∑, f, s0, Z)。
1) 将ΠS的初始格局抽象为初始状态集S0, 另s0=S0;
2) 将ΠS的终止格局抽象为终止状态集SZ, 另Z=SZ;
3) 将ΠS中除了终止格局每一次演化得到的格局均抽象成一个状态集Si, 另S=S0∪…∪Si∪ …∪SZ;
4) 将ΠS中所有复合规则进行拆分, 与不需拆分的反应规则合并得到反应规则集合的并集RS=R1∪R2∪…∪Rn, 另Σ=RS;
5) 将ΠS中任意格局使用一条反应规则转换为另外一个格局这个过程, 映射为状态si使用一个字符ri转换另外一个状态si+1的过程, 即将格局转换过程映射si×ri→si+1, 另f={s0×r0→s1, …, si×ri→ si+1, …, sZ-1×rZ-1→sZ};
6) 输出(S, Σ, f, s0, Z)。
对于任意一个CMC系统, 系统的格局转换过程就是自动机中的状态转移过程。系统的每一个格局都映射为自动机中的一个状态。
例如, CMC系统Π=({a:O, b:O}; [1]1; a:O; ({a:O→b:O}, ∅))可以映射为M=({[1a:O]1, [1b:O]1}, {a:O→b:O}, f, {[1a:O]1}, {[1b:O]1}), 其中f定义为f([1a:O]1, a:O→b:O)={[1b:O]1}。
因为状态集合SS既可以是有限的, 又可以是无限的。CMC可以映射为非确定有限自动机(NFA)或者非确定无限自动机(NIA)。为了叙述简便, 文中用γ1, γ2, …, γ9分别表示第2节中的9类反应规则, 即γ1, γ2, …, γ9表示9类字符。
4 CMC的性质分析拟用自动机理论对CMC是否适用于描述系统的演化过程进行分析。由于对象的类别不会影响系统格局的变化过程与变化结果, 将不考虑对象的类别。
4.1 可达状态分析对于任意一个状态, 它转换后得到的状态越多, 说明这个状态的演化能力越强。本节讨论一些状态以及它们转换后得到的状态, 并将这些状态与已有的MC类形式化方法的相应状态进行对比。
定义10 对于任意两个状态si和sm, 若能够调用一次或多次状态转换函数将si转换为sm, 那么sm就称为si的可达状态; 如果不存在状态转换函数使得si转换为sm, 则称sm为si的不可达状态; si的所有可达状态构成的集合Ssi称为si的可达状态集。
状态定义三元组中τ的结构与第1节中提及的膜结构相似。在C-NA中, 任意一个状态中的τ都能由[]、[[]]、[][]3种基本结构组合得到, 单层膜结构[]可以说是一个最简结构。在这3种基本结构中添加对象多重集得到的状态, 通过调用状态转换函数, 可以转换为任意一种状态。接下来, 本文将以这3种基本结构入手, 在结构中添加对象多重集作为初始状态, 来研究这些初始状态的可达状态集。
一条反应规则发生反应的最基本条件是至少存在一个对象来触发该反应规则。所以选择在3种基本结构中添加一个对象作为基本状态。在[]结构中添加一个对象得到状态[0o]0, 在[[]]结构中添加一个对象得到状态[0[1o]1]0和[0o[1]1]0, 在[][]结构中添加一个对象得到状态[0]0[1o]1和[0o]0[1]1。状态[0]0[1o]1和[0o]0[1]1为对称状态, 得到的可达状态也是对称的, 所以只讨论[0o]0[1]1即可。这样, 就能得到一个基本状态集合S0={[0o]0, [0o]0[1]1, [0[1o]1]0, [0o[1]1]0}。这4种基本状态, 在可以任意调用状态转换函数的情况下, 可以转换为任意状态。下文将依次讨论这4种基本状态的可达状态集。
对于状态转换函数的一个映射si×ri→si+1, 它是状态si使用一个字符ri转换另外一个状态si+1的过程。状态转换函数根据不同的输入字符, 可以将状态si转换为不同状态si+1。而这些不同的si+1构成的集合为si的可达状态集。
一个状态利用状态转换函数发生状态转换, 在输入字符为γ1、γ2、γ3、γ4、γ5、γ6时, 需要调用1次状态转换函数, 在输入字符为γ7、γ8、γ9时, 需要调用2次状态转换函数。接下来, 将根据调用状态转换函数的次数, 分两种情况讨论S0中状态的可达状态集。
表 1为S0中的四个状态在调用输入字符分别为γ1、γ2、γ3、γ4、γ5、γ6的状态转换函数, 得到的可达状态。如第二行第二列的状态[0p]0是状态[0o]0调用输入字符为γ1的状态转换函数得到的可达状态。表 1中“—”表示所在列的状态, 与所在行的字符共同作用下, 映射值为空。将表 1中的可达状态放入到集合中, 可以得到S0的可达状态集S1S0={[0p]0, [0[1]1]0, [0[1p]1]0, [0]0, [0[1[2]2]1]0, [0]0[1]1, [0p[1]1]0, [0[1]1[2]2]0, [0p]0[1]1, [0]0[1p]1, [0[2]2]0[1]1}。
|
表 1 S0调用γ1, γ2, …, γ6的可达状态 Tab.1 The reachable states of S0 by using γ1, γ2, …, γ6 |
接下来将分析调用输入字符为γ7、γ8、γ9的状态函数得到的可达状态集。假设反应规则γ7、γ8、γ9中包含的复制、传递或者删除的规则是γ1、γ2、γ3、γ4、γ5、γ6中的一种。表 2给出了四种初始状态先调用输入字符为γ7、γ8、γ9的状态转换函数, 再调用输入字符为γ1、γ2、γ3、γ4、γ5、γ6的状态转换函数得到的可达状态, 其中第二至四列、第五至七列和第八至十列中的状态分别表示[0o]0、[0[1o]1]0和[0o[1]1]0的可达状态。
|
|
表 2 S0的可达状态 Tab.2 The reachable states of S0 |
表 2中的状态为该状态所在区域内对应的初始状态, 第一次调用输入字符为该状态所在列对应字符的状态转换函数, 再调用输入字符为该状态所在行对应字符的状态转换函数得到的状态。如第二行第三列的状态[0p]0对应的初始状态是[0o]0, 所以该状态是初始状态[0o]0先调用输入字符为γ7的状态转换函数, 再使调用输入字符为γ1的状态转换函数得到的可达状态。包含对象q的状态表示调用输入字符为γ7、γ8、γ9中的一种状态转换函数得到的可达状态; 包含p的表示调用输入字符为γ7、γ8、γ9中的一个字符的状态转换函数, 再调用输入字符为γ1、γ2、γ3、γ4、γ5、γ6中的一种状态转换函数得到的可达状态; “—”表示所在区域内的初始状态不能调用输入字符为γ8的状态转换函数发生状态转换。
从表 2中, 可以得到S0的可达状态集SS02={[0p]0, [0[1]1]0, [0[1p]1]0, [0]0, [0[1[2]2]1]0, [0]0[1]1, [0p[1]1]0, [0[1]1[2]2]0, [0p]0[1]1, [0]0[1p]1, [0[2]2]0[1]1, [0]0[1[2]2]1, [0q]0, [0q]0[1]1, [0q[1]1]0, [0[1q]1]0}。将SS01与SS02比较可以知道, SS01⊂SS02。即通过调用输入字符为γ7、γ8、γ9的状态转换函数, 可以得到更多的可达状态。
字符γ1、γ2、γ3、γ4、γ5、γ6是在已有的几种MC类形式化方法的操作语义上, 通过化简、融合、重新定义等几种方式得到的, 字符γ7、γ8、γ9是CMC中特有的。可以说, CMC与已有的MC类形式化方法相比, 能够得到更多的可达状态, 更适合演化问题建模。
4.2 转换步数分析将利用转换步数, 分析CMC和已有MC类形式化方法对一个状态转换另外一个特定状态的转换过程的描述能力。
定义11 状态si调用n次状态转换函数转换为状态sm, 调用的n次状态转换函数中的输入字符分别为a1, a2, …, an, 那么< a1, a2, …, an>称为si到sm的转换路径; 调用状态转换函数的次数n称为si到sm的转换步数, n为整数且n≥-1, n=-1表示si为sm的不可达状态。
同样, 本节也将分两部分对转换步数进行讨论。首先讨论调用输入字符为γ1、γ2、γ3、γ4、γ5、γ6的状态转换函数, 将S0中四个基本状态相互映射需要使用的转换步数; 其次讨论调用输入字符为γ1、γ2、γ3、γ4、γ5、γ6、γ7、γ8、γ9的状态转换函数, 将S0中四个基本状态相互映射需要使用的转换步数。
为了叙述方便, 用字符的类别代替字符表示状态的转换路径。如:状态si转换为状态sm的转换路径为 < a1, a2, a3, a2>, 所属的字符类别为γ1、γ2、γ3、γ2, 那么就用γ1γ2γ3γ2代替 < a1, a2, a3, a2>表示状态si转换为状态sm的转换路径。
假设四种基本状态都有一个单层膜结构的状态与其构成兄弟状态。这个单层膜结构的状态能够调用所有类型的状态转换函数, 并包含足够多的对象多重集; 基本状态中只有一个对象, 并且基本状态在初始格局时不能调用任何状态转换函数使其发生状态转换。接下来将研究如何利用这个与基本状态存在兄弟关系的单层膜, 使只包含一个对象的基本状态发生状态转换。不考虑单层膜结构的状态的转换结果, 只研究基本状态之间相互转换需要的转换步数与转换序列, 可以得到表 3和表 4。表 3~4中, 数字表示初始状态转换为终止状的转换步数, 数字后序列为转换序列。
|
|
表 3 使用γ1、γ2、γ3、γ4、γ5、γ6的转换步数和转换路径 Tab.3 Transition steps and transition paths by using γ1, γ2, γ3, γ4, γ5, γ6 |
|
|
表 4 使用γ1、γ2、γ3、γ4、γ5、γ6、γ7、γ8、γ9的转换步数和转换路径 Tab.4 Transition steps and transition paths by using γ1, γ2, γ3, γ4, γ5, γ6, γ7, γ8, γ9 |
从表 3中可以看到, 四种基本状态在不能调用状态转换函数使其发生状态转换的前提下, 只有[0o]0可以被动的发生状态转换。这说明, 只有同时存在状态和状态转换函数, 状态才能发生转换。
表 3是在状态转换函数的输入字符为γ1、γ2、γ3、γ4、γ5、γ6这6种字符时得到的转换步数与转换路径。表 4在表 3的基础上增加了3类输入字符, 这时初始状态转换为特定状态需要的转换步数以及转换路径发生了变化。
表 4中的转换路径不是唯一的, 表中给出的序列是能保证转换步数最少的一种序列。
将表 4与表 3进行对比, 表 3中的-1在表 4中变为了大于0的正整数, 即利用包含字符γ7、γ8、γ9的状态转换函数, 可以将表 3中的不可达状态变为可达状态。对于表 3中的可达状态, 表 4没有改变转换步数。
表 3与表 4的对比结果说明, CMC没有改变已有MC类形式化方法对格局转换过程的描述能力, 已有MC类形式化方法能够描述的格局转换过程, CMC也同样能够描述。在初始格局和终止格局相同的情况下, CMC可以使用多种转换路径将初始格局转换为终止格局。同时, 在初始格局相同的情况下, CMC能够使格局的演化结果变多, 得到更多的终止格局。
4.3 NIA说明C-NA是由一个CMC系统映射而成的。在CMC系统中, 存在格局不断变化无法生成终止格局的情况, 这时的CMC系统就映射为了一个NIA。由于系统格局不断变化且不终止, 导致了自动机中状态集为无限集合。
CMC系统映射成的C-NA时, 存在使C-NA是一个NIA的情况, 如:
1) 系统中存在一条对象变化规则, 该规则“→”后的对象多重集是“→”前对象多重集的n(n>1)倍;
2) 系统中存在一条膜创建规则, 且该规则创建的膜中出现膜创建规则的循环, 或创建的膜包含触发该规则的对象多重集并且能将此对象多重集传递到该规则所在的膜中。
上述两种情况, 第一种情况是因为不断增加对象多重集使得状态不断增多, 第二种情况是因为膜结构不停发生改变使得状态不断增多, 这两种情况均导致了状态集是无穷集。C-NA是NIA的情况有许多, 这里不一一列举。
将CMC映射为一个NIA, 是由于CMC系统定义中的反应规则使得CMC系统的格局不断变化导致的。虽然这种情况的系统格局不断变化, CMC仍然可以对演化过程进行建模。对于任意CMC系统, 不期望该系统映射为NA后是NIA。所讨论的映射为NIA的情况, 可以作为判断系统是否存在不停机状况的一个依据。
5 软件产品线演化过程建模及分析将MobileMedia(M-M)这款软件产品线作为实例分析的对象, 利用CMC对该产品线的一种演化过程进行了建模, 说明CMC对系统演化过程建模的适用性。
5.1 MobileMedia形式化建模M-M是一款能够生成移动端媒体播放器的具有代表性的软件产品线。目前, M-M已有6个版本[10-13], 因此本文以M-M的演化为例, 对其进行建模。同时, 特征模型是目前使用较多的一种刻画软件产品线结构以及功能的方式, 特征模型以树的形式给出功能之间的关联关系[14]。
M-M的现有特征较多, 所以本文选取了M-M的特征模型中的4个具有代表性特征(MobilePhoto(MP)、PhotoManagement(PM)、SMSTransfer(ST)和Favourite(F))进行建模。这4个特征能够体现M-M的层析结构以及特征之间的关系。其中, MP和PM为强制特征, ST和F为选择特征。利用M-M生成软件时, 生成的软件必须具有强制特征, 同时需要根据用户需求, 在选择特征中进行特征挑选。利用CMC对这个特征模型进行建模, 模型1:M-M的建模。模型如下所示:
ΠMM=(V, μ, OMM, OMP, OPM, OST, OF, (RMM, ρMM), (RMP, ρMP)(RPM, ρPM), (RST, ρST), (RF, ρF));
V={OStart：O, OMMtoMP：O, OMMtoPM：O, OStart2：O,
Ofinish：OOMMtoST：O, OMMtoF：O, OMPfinish：O,
OPMfinish：O, Υ}; μ=[MM[MP]MP[PM]PM[ST]ST[F]F]MM;
OMM=OStart：O, OMP, OPM, OF=∅;
RMM={OStart：O→OMMtoMP：Oin_MPOMMtoPM：Oin_PMOStart2：O,
OStart2：O→OMMtoST：Oin_ST, OStart2：O→OMMtoF：Oin_F,
OMPfinish：OOPMfinish：OOfinish：O→Υ}, RMP={OMMtoMP：O→OMPfinish：Oin_MM}, RPM={OMMtoPM：O→OPMfinish：Oin_MM},
RST={OMMtoST：O→Ofinish：Oin_MM}, RF={OMMtoF：O→Ofinish：Oin_MM}; ρ=∅。
这里, 膜[MM]MM表示整个M-M, 膜中的子膜表示M-M中的各个特征。[MP]MP与[PM]PM分别表示MP和PM, [ST]ST和[F]F分别表示ST和F。在利用M-M生成一个软件的过程时, 只有当膜[MM]MM中同时存在OMPfinish：O, OPMfinish：O, Ofinish：O这三个对象, 软件产品线才算完整运行一次。
5.2 MobileMedia演化过程建模Neves等通过分析M-M不同版本间的区别, 总结出添加特征、将特征类型进行转换等8种不同类型的演化场景[15-16]。特征类型转换这种演化场景, 是软件产品线最常见的一种演化。本节以将一个强制特征转化为一个选择特征这种演化场景为例, 说明CMC对演化过程建模的适用性。
在模型1中, PM是一个强制特征, 如果将这个强制特征变为选择特征, 需要在M-M模块中与PM这个强制特征相关的信息进行修改, 同时需要PM中的信息进行修改, 使PM中的信息以及向M-M模块传递的信息变为选择特征需要的信息类型。为了对这个演化过程进行建模, 本节将在模型1中添加一个包含演化规则集的演化膜。当演化发生时, 就可以从演化规则集中调用相应的规则使得PM特征发生演化。建立的模型2:M-M的一种演化场景建模:
ΠEMM=(V, μ, OMM, OR, OMP, OMP, OPM, OST, OF, (RMM, ρMM), (RR, ρR), (RMP, ρMP), (RPM, ρPM), (RST, ρST), (RF, ρF));
V={OStart1：O, OMPtoAP：O, OStart2：O, OMtoA：R, OMPtoAP1：O, Υ, OM：O, OA：O, OMtoA1：R, OChMPtoAP：O, OChA：O,OAP：O}μ = [MM[R]R[MP]MP[PM]PM [ST]ST[F]F]MM;
OMM=OStart：O, OR=∅, OMP=∅, OPM=∅, OST=∅, OF=∅;
RMM={OStart：O→OMMtoMP：Oin_MPOMMtoPM：Oin_PM OStart2：O, OStart2：O→OMMtoST：Oin_ST, OStart2：O→ OMMtoF：Oin_F, OMPfinish：OOPMfinish：OOfinish：O→ Υ},
RR={OMPM-APM：O→OMPM-APM1：ROMPM-APM2：RODelete1：Rin_MMODelete2：Rin_MMODelete：Rin_PM, OMPM-APM1：R→(ODelete1：R→(OStart：O→OMMtoMP：Oin_MP OMMtoPM：Oin_PMOStart2：O, ∅)delete, ∅)copy(ODelete2：R→(OMPfinish：OOPMfinish：OOfinish：O→Υ, ∅)delete, ∅)copy (ODelete：R→(OMMtoPM：O→OPMfinish：Oin_MM, ∅)delete, ∅)copy(OStart：O→OMMtoMP：Oin_MPOStart2：O)copy (OStart2：O→OMMtoPM：Oin_PM)copy(OMPfinish：OOfinish：O→Υ)copy (OMMtoPM：O→ OPMfinish：Oin_MM)copy, OMPM-APM2：R→(ODelete1：R→(OStart：O→OMMtoMP：Oin_MPOMMtoPM：Oin_PMOStart2：O, ∅)delete, ∅)in_MM(ODelete2：R→(OMPfinish：OOPMfinish：OOfinish：O→Υ, ∅)delete, ∅)in_MM(ODelete：R→(OMMtoPM：O→OPMfinish：Oin_MM, ∅)delete, ∅)in_PM(OStart：O→OMMtoMP：Oin_MPOStart2：O)in_MM(OStart2：O→OMMtoPM：Oin_PM)in_MM (OMPfinish：OOfinish：O→Υ)in_MM(OMMtoPM：O→Ofinish：Oin_MM)in_PM},
RMP={OMMtoMP：O→OMPfinish：Oin_MM}, RPM={OMMtoPM：O→OPMfinish：Oin_MM}, RST={OMMtoST：O→Ofinish：Oin_MM}, RF={OMMtoF：O→Ofinish：Oin_MM};ρ=∅。
将PM这个强制特征变为选择特征的过程可以描述为:演化膜R解析演化场景后, 生成触发演化需要的对象多重集{OMPM-APM1：R, OMPM-APM2：R, ODelete1：R, ODelete2：R, ODelete：R}。对象多重集{OMPM-APM1：R, OMPM-APM2：R}触发规则的复制、传递等反应规则, 使得膜[MM]MM和膜[PM]PM具有发生演化的反应规则。膜[MM]MM和膜[PM]PM利用接收到的反应规则和对象多重集发生演化, 使得[PM]PM具有向膜[MM]MM传递对象Ofinish：O的反应规则。
分析模型2的初始格局与终止格局, 膜[MM]MM、[MP]MP、[PM]PM、[ST]ST和[F]F中的规则类型以及数量近似于不变, 但膜[MM]MM和[PM]PM中部分反应规则发生了变化, 这个使得反应规则发生变化的过程就是M-M的演化过程。模型2可以说明, CMC可以对软件产品线的演化过程进行建模。
5.3 实例分析与结论如果利用修改模型1的方式对上述演化场景进行建模, 膜[MM]MM内的传递对象的反应规则需要改变, 同时膜[PM]PM向膜[MM]MM传递的对象需要由OPMfinish:O变为Ofinish:O。这相当于在自动机中, 初始状态以及终止状态不发生改变, 转换路径、中间状态发生了变化。
已有的MC类形式化方法无法修改转换路径以及中间状态。因此, 已有的MC类形式化方法无法通过修改模型1中的对象、反应规则这种途径, 对将PM这个强制特征演化为选择特征的演化过程进行建模。
如果对将PM这个强制特征演化为选择特征的演化结果建模, 需要对模型1刻画的字母表中的字符进行修改。已有的MC类形式化方法不支持反应规则的变化, 如果利用已有的MC类形式化方法对演化结果进行建模, 需要舍弃模型1, 重新构建一个刻画演化结果的形式化模型。
模型2是利用CMC对将PM这个强制特征演化为选择特征的演化过程以及演化结果建立的形式化模型。模型2在模型1的基础上添加了一个演化膜R, 这样就可以通过传递R中规则的形式完成系统的演化, 同时演化后的系统就是该演化场景结果的模型。模型2调用输入字符为(γ7, γ8, γ9)的状态转换函数, 修改了模型1的字母表、转移路径以及中间状态。
模型2充分说明, CMC可以通过修改转移路径以及中间状态的方式完成对系统演化过程和演化结果的建模。与已有的MC类形式化方法相比, CMC适用于对演化过程的建模。
6 结论1) 对MC类形式化方法进行了扩展, 提出了一种新的膜演算:通信膜演算。CMC在原有的MC类形式化方法定义的基础上增加了规则的传递、复制和删除, 使得反应规则也具有了动态变化的能力, 这使得CMC比已有的MC类形式化方法具有更多的通信机制与变化机制。
2) 利用CMC可以对系统演化过程进行建模, 本文利用MobileMedia演的实例说明了CMC对演化过程建模的适用性。但是, 本文只是在理论上验证了CMC可以应用于系统的演化过程建模, 同时并没有完成CMC工具的实现。
在将来的研究中, 将进一步完善基于通信膜演算的系统演化模型, 研究如何利用通信膜演算的性质保障系统演化过程的一致性和安全性, 并设计CMC的实现工具。
| [1] |
PǍUN G. Computing with membranes[J]. Journal of computer and system sciences, 2000, 61(1): 108-143. DOI:10.1006/jcss.1999.1693 (  0)
|
| [2] |
PǍUN G. 膜计算导论[M]. 潘林强, 曾湘祥, 宋弢, 等译. 武汉: 华中科技大学出版社, 2012: 383-390. PǍUN G. Membrane computing an introduction[M]. PAN Linqiang, ZENG Xiangxiang, SONG Tao, et al, trans. Wuhan: Huazhong University of Science & Technology Press, 2012: 383-390. ( 0)
|
| [3] |
QI Zhengwei, LI Minglu, FU Cheng, et al. Membrane calculus:a formal method for grid transactions[J]. Concurrency and computation:practice and experience, 2006, 18(14): 1799-1809. DOI:10.1002/(ISSN)1532-0634 ( 0)
|
| [4] |
KRISHNA S N, PǍUN G. P systems with mobile membranes[J]. Natural computing, 2005, 4(3): 255-274. DOI:10.1007/s11047-005-3771-7 ( 0)
|
| [5] |
AMAN B, CIOBANU G. Describing the immune system using enhanced mobile membranes[J]. Electronic notes in theoretical computer science, 2008, 194(3): 5-18. DOI:10.1016/j.entcs.2007.12.003 ( 0)
|
| [6] |
CIOBANU G, PǍUN G, PÉREZ-JIMÉNEZ M J. Applications of membrane computing[M]. Berlin, Heidelberg: Springer, 2006.
( 0)
|
| [7] |
戚正伟, 尤晋元. 基于细胞膜演算的Web服务事务处理形式化描述与验证[J]. 计算机学报, 2006, 29(7): 1137-1144. QI Zhengwei, YOU Jinyuan. The formal specification and verification of transaction processing in Web services by membrane calculus[J]. Chinese journal of computers, 2006, 29(7): 1137-1144. ( 0)
|
| [8] |
PǍUN G. A quick introduction to membrane computing[J]. The journal of logic and algebraic programming, 2010, 79(6): 291-294. DOI:10.1016/j.jlap.2010.04.002 ( 0)
|
| [9] |
KRISHNA S N, CIOBANU G. On the computational power of enhanced mobile membranes[C]//Proceedings of the 4th Conference on Computability in Europe. Athens, Greece, 2008: 326-335.
( 0)
|
| [10] |
GAIA F N, FERREIRA G C S, FIGUEIREDO E, et al. A quantitative and qualitative assessment of aspectual feature modules for evolving software product lines[J]. Science of computer programming, 2014, 96: 230-253. DOI:10.1016/j.scico.2014.03.006 ( 0)
|
| [11] |
BEOHAR H, VARSHOSAZ M, MOUSAVI M R. Basic behavioral models for software product lines:expressiveness and testing pre-orders[J]. Science of computer programming, 2016, 123: 42-60. DOI:10.1016/j.scico.2015.06.005 ( 0)
|
| [12] |
RINCÓN L, GIRALDO G, MAZO R, et al. Method to identify corrections of defects on product line models[J]. Electronic notes in theoretical computer science, 2015, 314: 61-81. DOI:10.1016/j.entcs.2015.05.005 ( 0)
|
| [13] |
WHITE J, GALINDO J A, SAXENA T, et al. Evolving feature model configurations in software product lines[J]. Journal of systems and software, 2014, 87: 119-136. DOI:10.1016/j.jss.2013.10.010 ( 0)
|
| [14] |
BORBA P, TEIXEIRA L, GHEYI R. A theory of software product line refinement[J]. Theoretical computer science, 2012, 455: 2-30. DOI:10.1016/j.tcs.2012.01.031 ( 0)
|
| [15] |
NEVES L, TEIXEIRA L, SENA D, et al. Investigating the safe evolution of software product lines[C]//Proceedings of the 10th ACM International Conference on Generative Programming and Component Engineering. Portland, Oregon, USA, 2011: 33-42.
( 0)
|
| [16] |
NEVES L, BORBA P, ALVES V, et al. Safe evolution templates for software product lines[J]. Journal of systems and software, 2015, 106: 42-58. DOI:10.1016/j.jss.2015.04.024 ( 0)
|