康 輝，張雙雙，2，梅 芳

（1.吉林大學，計算機科學與技術學院，長春130012；2.吉林信息安全測評中心，長春130062）

隨著面向服務的計算（Service-oriented computing SOC／Service-oriented architecture，SOA）技術［1］和業(yè)務流程管理（Business process management，BPM）技術［2］的廣泛應用以及對軟件可信性要求越來越高，很多學者用π演算和Petri網(wǎng)作為服務組合和業(yè)務流程技術的理論基礎。π演算用來描述拓撲結構動態(tài)變化的并發(fā)系統(tǒng)，通過相應的數(shù)學分析方法，對系統(tǒng)的屬性和行為進行分析。但是π演算［3－7］的進程表達式比較繁瑣，不能形象地反應系統(tǒng)物理結構信息，不能刻畫系統(tǒng)的真并發(fā)行為，而且從系統(tǒng)驗證角度來看，其支持工具少，僅有MVB和HAL等幾種自動驗證工具，這樣給后續(xù)的形式化驗證帶來了困難。Petri網(wǎng)［8－9］是一種形式化圖形驗證工具，它側(cè)重于系統(tǒng)的結構描述和性質(zhì)分析，并且能有效地刻畫系統(tǒng)真正的并發(fā)語義。它是一種可用網(wǎng)狀圖形表示的系統(tǒng)模型［10－11］，適合描述異步、并發(fā)、分布式的系統(tǒng)，既可用于靜態(tài)的結構分析，又可用于動態(tài)的行為分析。

由于π演算存在固有缺陷，很多學者已經(jīng)在將π演算向Petri網(wǎng)轉(zhuǎn)換這方面做了很多研究［12－13］，例如Raymond Devillers［12］等人已經(jīng)提出了其轉(zhuǎn)換的一般方法。但是對于π演算中遞歸結構的轉(zhuǎn)換，目前仍然空白。在π演算中，對遞歸的表達是其基本的語義，較為簡單；而在一般Petri網(wǎng)中，對遞歸的描述非常困難。實際應用π演算時遞歸結構經(jīng)常出現(xiàn)，因此，本文給出了一種π演算中遞歸結構轉(zhuǎn)換為Petri網(wǎng)的方法。

1 基本概念及轉(zhuǎn)換規(guī)則

1.1 基本概念

關于π演算的基本概念，在文獻［3］中已有詳細介紹在此不再贅述。在給出π演算中遞歸表達式基本形式之前，先看一個例子：

式（1）中每個通道a、b、c、…中都保存著一個數(shù)值h′（這個數(shù)值可以不一樣），從已知通道a開始，讀取通道內(nèi)當前值h′加到現(xiàn)有的值上，直到得到的h值大于10時可以選擇執(zhí)行輸出該值。這樣，從a開始到輸出h時所有計算過的通道即是該get函數(shù)的路徑。

在式（1）中，既有自調(diào)用的算子，又有非自調(diào)用的算子，并且有選擇運算符“＋”將兩個進程相連。在不滿足遞歸出口條件時，多次執(zhí)行前綴算子ab獲取下一個通道，并執(zhí)行計算h值操作。當滿足遞歸出口條件時，可以選擇繼續(xù)自調(diào)用，也可以終止調(diào)用過程。

本文給出了一種一般π演算的遞歸表達式的基本形式：

當然，在一些表達式中也會出現(xiàn)有多個自調(diào)用表達式的形式，比如：

在式（3）至式（5）中，均有兩次自調(diào)用，雖然在轉(zhuǎn)換時與式（2）有點不同，但基本轉(zhuǎn)換思路大致相同。為了方便描述轉(zhuǎn)換過程，在本文中，以式（2）這種遞歸形式為例。

為了更好地記錄遞歸運算的層次，本文引入軌跡的概念。通常，軌跡一般用來指進程P所依次執(zhí)行的一系列活動，一般用〈action1，action2…〉表示。

定義1 軌跡：π演算遞歸結構執(zhí)行時，為了記錄遞歸運算的層次，我們將遞歸調(diào)用的順序稱為軌跡，用字母trail表示。調(diào)用一次用σ1表示，調(diào)用第二次用σ2表示，以此類推，調(diào)用第n次用σn表示，則進程中遞歸結構執(zhí)行的軌跡trail＝〈σ1，σ2，…，σn〉。

定義2 逆軌跡：與軌跡相應地，在遞歸返回時其軌跡稱為逆軌跡，記為trail－1，上述遞歸返回的逆軌跡即為trail－1＝〈σn，σn－1，…，σ1〉。

在本文中，π演算進程P轉(zhuǎn)換而成的Petri網(wǎng)記為NP，NP是一個有向連通圖，其節(jié)點分別稱為庫所和變遷。這些節(jié)點通過有向弧相連。相同類型的兩個節(jié)點之間是不允許相連的。

1.2 轉(zhuǎn)換規(guī)則

遞歸π演算向Petri網(wǎng)轉(zhuǎn)換要遵循一些轉(zhuǎn)換規(guī)則，在本文中將這些規(guī)則概括為兩類：基本進程的轉(zhuǎn)換規(guī)則以及組合規(guī)則。

1.2.1 基本進程轉(zhuǎn)換規(guī)則

對于向子網(wǎng)K（ρ）的轉(zhuǎn)換，是根據(jù)表達式ρ的語法樹，其組成為給定基本子項（進程項0，進程調(diào)用，內(nèi)部動作以及輸入輸出前綴）的圖轉(zhuǎn)換。

由于不涉及任何的名字操作，因此進步進程項0和內(nèi)部動作前綴τ十分簡單。進程調(diào)用X（α1，…，αnX）也類似，但是結果將產(chǎn)生一個層次變遷，它將通過標識等價規(guī)則進行激發(fā)變換［10］。

具體的轉(zhuǎn)換規(guī)則如圖1所示。

圖1 空進程、啞動作τ、進程調(diào)用、動作前綴向Petri網(wǎng)轉(zhuǎn)換規(guī)則Fig.1 Translation rules from o，τ，the process call and the prefix to Petri nets

1.2.2 組合規(guī)則

本節(jié)中的組合規(guī)則用于合并Petri網(wǎng)的算子，包括前綴組合規(guī)則、選擇組合規(guī)則、并行組合規(guī)則以及范圍處理規(guī)則，其中前3個規(guī)則給出了合并標簽庫所、相應的持有者的方法［12］。

假設有網(wǎng)Ni＝（∪，Ti，ιi）（i＝1，2）是兩個不相干的未標記的Petri網(wǎng)，并且有?s1，s1∈，?s2，s2∈，如果ι1（s1）＝（λ，D1），ι2（s2）＝（λ，D2），那么D1＝D2，即被相同符號標識的持有者庫所也有同樣的值類型集合。下面將給出四種組合規(guī)則的形式化處理方法，如圖2所示。前綴組合規(guī)則：N1.N2。假設N1有唯一的入口控制庫所和唯一的出口控制庫所（出口控制庫所記作s1），通過如下步驟獲得組合結果：

（1）網(wǎng)N1和網(wǎng)N2并排放置。

（2）對應每個s2∈°N2，創(chuàng)建一個新的庫所s′2，用符號i標識，同時將網(wǎng)N1和網(wǎng)N2中在si和t∈Ti（i∈｛1，2｝）的弧Ψ在新的庫所s′2和t上標記，并使用同樣的注釋符號和同樣的弧類型（無向或是有向的）標記，而后網(wǎng)N1的唯一出口控制庫所和網(wǎng)N2的出口控制庫所將被刪除。

（3）對于有相同標識符號和類型的持有者庫所將被合并為一個持有者庫所，并且如前一樣，具有相同的標識符號和類型，在原來的網(wǎng)N1和網(wǎng)N2中連接合并的持有者庫所與變遷之間的弧及注釋標識在合并后的持有者庫所中保持不變。

1）選擇組合規(guī)則：N1＋N2，可通過如下過程獲得圖轉(zhuǎn)換結果：

①網(wǎng)N1和網(wǎng)N2并排放置。

對于每個s1∈°N1和s2∈°N2，創(chuàng)建一個新的庫所s，用符號e標識，并且使得每個在si和t∈Ti，i∈｛1，2｝的弧Ψ在新的庫所s和變遷t上作同樣標識，即使用相同的注釋符號和相同的弧類型（無向或是有向的）；類似地，對于每個s1∈和s2∈，創(chuàng)建一個新的庫所s，用符號x標識，其連接性與上面規(guī)則定義一致。最后，將原來在網(wǎng)N1和網(wǎng)N2中標識的入口控制庫所（被符號e標識）和出口控制庫所（被符號x標識）刪除。

圖2 組合規(guī)則Fig.2 Composition rules

②具有相同名字的持有者庫所的合并可參見前綴組合規(guī)則。

2）并行組合規(guī)則：N1｜N2，可通過如下過程獲得圖轉(zhuǎn)換結果：

①網(wǎng)N1和網(wǎng)N2并排放置；

②具有相同名字的持有者庫所的合并可參見前綴組合規(guī)則。

3）范圍處理規(guī)則：N＝sco（N1），可通過如下過程獲得圖轉(zhuǎn)換結果：

①對于每對變遷t1，t2∈T1，其中t1和t2分別被snd或rcv所標識，創(chuàng)建一個新的變遷t，用符號τ標識，而在變遷t與庫所s上的弧注釋符號是在變遷t1與庫所s以及變遷t2與庫所s的弧注釋符號的簡單合并。在這里注意在snd所標識的變遷周圍的弧與rcv所標識的變遷周圍的弧是互不相干的，所以不需要進行反復的合并操作。

②最后刪除被snd和rcv所標識的變遷以及與其相連接的弧。

2 遞歸π演算向Petri網(wǎng)的轉(zhuǎn)換及等價性證明

2.1 準備與討論

類似于式（1）中的例子，當數(shù)據(jù)h滿足h＞10時才可以選擇執(zhí)行h.0，因此在執(zhí)行遞歸時要判斷是否滿足遞歸出口的條件。因此在遞歸調(diào)用和遞歸返回間加入一個判定庫所，用來存儲判定是否滿足遞歸出口條件的判定托肯。判定托肯的形式為F.D或者T.D，其中F.D表示不滿足遞歸出口條件，D表示這個托肯的類型是判定托肯（decision token）；T.D表示滿足遞歸出口條件。

對于如何記錄當前數(shù)據(jù)屬于哪次遞歸操作，本文采用trail.data.place的形式，即當前軌跡.數(shù)據(jù)值.所在庫所的形式存儲在棧庫所中。

對于軌跡，在執(zhí)行遞歸調(diào)用時，調(diào)用一次用σ1標記，調(diào)用第二次用σ2標記，…，調(diào)用第n次用σn表示，進程中遞歸結構執(zhí)行的軌跡trail＝〈σ1，σ2，…，σn〉。例如遞歸主體X（a1，…，an）將用軌跡標記為σ1，σ2，…，σn.X（a1，…，an）。對于遞歸主體后面的Q（a″1，…，a″n），在遞歸返回之前是不執(zhí)行的，在執(zhí)行Q（a″1，…，a″n）時是按照軌跡〈σ1，σ2，…，σn〉的逆軌跡〈σn，σn－1，…，σ1〉執(zhí)行的。

2.2 遞歸π演算向Petri網(wǎng)的轉(zhuǎn)換

對于π演算遞歸結構向Petri網(wǎng)的轉(zhuǎn)換，本文采用層次化方法，即將表達式中的每一個子表達式（包括遞歸主體）都先轉(zhuǎn)換成對應的子網(wǎng)，然后組合起來；如果自調(diào)用表達式?jīng)]有滿足遞歸出口條件，那么對自調(diào)用表達式的網(wǎng)結構進行進一步細化，將下一次調(diào)用的網(wǎng)結構展開代替上一層中自調(diào)用表達式對應的網(wǎng)結構。

下面給出關于式（2）的遞歸結構全景圖第一層，如圖3所示。

說明：

（1）最開始的庫所e與最后的庫所x是此π演算表達式對應網(wǎng)結構的控制庫所，這是假設該表達式是一個主式；如果此遞歸π演算表達式是其他π演算表達式的子式，這兩個庫所應換成與外界相連、用于傳遞控制信號的內(nèi)部庫所i。

圖3 典型π演算遞歸結構轉(zhuǎn)換結果全景圖第一層Fig.3 First layer of franslation panoramic view from typical recursionπcalculus to Petri net

（2）圖中的庫所d是本文新加庫所——判定庫所，存儲了判定是否滿足遞歸出口條件的判定托肯F.D和T.D。

（3）在自調(diào)用表達式對應的網(wǎng)結構與判定庫所d之間有一條弧相連，表示在執(zhí)行自調(diào)用表達式時，其中的條件發(fā)生了變化，這個變化的條件要及時傳給判定庫所，使判定庫所做出合理的判斷。

（4）在P（a1，…，an）、Q（a″1，…，a″n）等表達式前進行了軌跡的標記；而表達式R（b1，…，bn）卻沒有軌跡標記，因為在遞歸調(diào)用時此表達式只執(zhí)行一次。

（5）判定庫所對應一個判斷邏輯，嚴格來講，如果系統(tǒng)中有多個遞歸表達式，則每一個表達式單獨對應一個判定庫所。

（6）出于版面考慮，這里沒有畫出棧庫所、名字持有者庫所、標簽庫所以及相關弧。

式（2）遞歸結構全景的第二層如圖4所示。

圖4 典型π演算遞歸結構轉(zhuǎn)換結果全景圖第二層Fig.4 Second layer of translation panoramic view from typical recursionπcalculus to Petri net

類似地，調(diào)用多次的π演算表達式對應的網(wǎng)結構也能夠給出。

對于形如式（2）的π演算表達式，采用層次化方法，將π演算遞歸結構轉(zhuǎn)換成Petri網(wǎng)的步驟為：

（1）按照1.2節(jié)中的基本進程轉(zhuǎn)換規(guī)則及組合規(guī)則將P（a1，…，an）、R（b1，…，bn）以及Q（a″1，…，a″n）分別轉(zhuǎn)換成對應的子網(wǎng)NP1、NP2、NP3。

（2）將自調(diào)用表達式X（a′1，…，a′n）先看做一個整體表示，對應的網(wǎng)結構先用NP0表示。各個組成部分用構造sco（NP1｜NP2｜NP3｜NP0）網(wǎng)連接起來，這將多種標簽庫所和可能來自不同部分的有uv和v標記的變遷對合并起來。這個構造并不合并其他的持有者庫所。移除所有標記為uv和u－v的變遷。

（3）判斷X（a′1，…，a′n）是否滿足遞歸出口條件，若不滿足，將X（a′1，…，a′n）視為X（a1，…，an），轉(zhuǎn)步驟（1）。用不同的標記來記錄不同的調(diào)用；若滿足，轉(zhuǎn)（4）。

（4）將圖3中的變遷P（a1，…，an）用子網(wǎng)NP1替換，如果NP1只有一個輸入庫所e，那么將此庫所與開始的庫所e合并，仍舊記為e；否則創(chuàng)建一個輔助變遷t1，使開始庫所e指向輔助變遷t1，然后由變遷t1指向NP1所有的輸入庫所e，再將NP1所有的輸入庫所e改為內(nèi)部庫所i。

同樣地，如果NP1只有一個輸出庫所x，將此庫所與最后庫所x合并，記為x；否則創(chuàng)建一個輔助變遷t2，使NP1所有的輸出庫所x指向輔助變遷t2，然后由變遷t2指向最后的庫所x，再將NP1所有的輸出庫所x改為內(nèi)部庫所i。

在用NP2、NP3替換R（b1，…，bn）、Q（a″1，…，a″n）時也做同樣的處理。

（5）將相同的名字持有者庫所合并，與原庫所相連的弧以原方式練到合并后的庫所上。將需要保存數(shù)據(jù)的變遷用弧與棧庫所相連。

（6）為了得到完整的變遷網(wǎng)NP，向輸入庫所中插入一個小黑點作為托肯，并把下面的通道插入到持有者庫所中去：

①把ζ（α）插入到每個α標記的持有者庫所中，其中α∈domain（ζ）；

②把a.a.K插入到標簽庫所中，其中對于每一個a∈konwn（ζ）；

③把n.N插入到標簽庫所中，其中n∈C＼konwn（ζ）；

④把Δ.R插入到標簽庫所中，其中Δ∈rstr（ζ）。

2.3 互模擬等價

本文定義了從遞歸π演算到Petri網(wǎng)的語義轉(zhuǎn)換，從而產(chǎn)生了有限結構轉(zhuǎn)換網(wǎng)——NP，它是具有有限庫所、變遷和弧的網(wǎng)結構，該遞歸結構的標號遷移系統(tǒng)ItsP與轉(zhuǎn)換后的Petri網(wǎng)所對應的標號遷移系統(tǒng)ItsNp是強互模擬。

定理1 NP是具有有限庫所、變遷和弧的Petri網(wǎng)圖，并且使得ItsP和ItsNp是互為強互模擬的標號遷移系統(tǒng)。

證明 基本π演算部分的Petri網(wǎng)語義等價證明在文獻［12］中詳細介紹了轉(zhuǎn)換的思想、方法以及相關的語義等價證明，在此不再贅述。

關于遞歸結構的Petri網(wǎng)語義等價的證明采用數(shù)學歸納法。具體如下：

設K為遞歸結構執(zhí)行次數(shù)，即遞歸層數(shù)。

（1）當K＝1時，按照文中所述遞歸π演算向Petri網(wǎng)的轉(zhuǎn)換方法，其直接轉(zhuǎn)換為不帶遞歸結構的基本π演算，其互模擬等價性是已知的。

（2）假設當K＝n時，從遞歸π演算向Petri網(wǎng)的轉(zhuǎn)換具有互模擬等價性，那么證明當K＝n＋1時互模擬等價仍成立。由于當K＝n時，前n層的遞歸調(diào)用已經(jīng)實現(xiàn)，即可以將前n層遞歸調(diào)用得到的π演算表達式看做一個復雜無遞歸的基本π演算表達式，這樣再加上第n＋1層的遞歸調(diào)用轉(zhuǎn)化為（1）中的形式，此時K′＝1，符合（1）中所證互模擬等價。因此當K＝n＋1時遞歸π演算向Petri網(wǎng)轉(zhuǎn)化的互模擬等價性成立。證畢。

對不同密度、不同施肥處理的相對增加量進行雙因素方差分析，結果表明(表5)：3種不同施肥處理并未對毛竹相對增產(chǎn)量產(chǎn)生顯著差異(P=0.138>0.05)；在試驗所設2種密度中，低密度毛竹林相對增加產(chǎn)量顯著高于高密度毛竹林(P=0.023<0.05)。

3 更簡潔的Petri網(wǎng)表示

Petri網(wǎng)是一個很好的描述與分析并行系統(tǒng)的模型。但是當遞歸結構遞歸的次數(shù)較多時，會產(chǎn)生巨大的Petri網(wǎng)。尤其是在實際應用中，如果系統(tǒng)過大或較復雜時，會遇到結點數(shù)過多的情況。系統(tǒng)的組合狀態(tài)數(shù)又隨結點數(shù)成指數(shù)函數(shù)增長，這就是所謂的組合爆炸問題。解決結點數(shù)過多引起的組合爆炸問題的辦法是盡量減少模型的結點個數(shù)。為了使轉(zhuǎn)換后的Petri網(wǎng)較為簡潔，本文給出了壓縮的Petri網(wǎng)圖，它保留了系統(tǒng)的語義，并編碼完全相同的軌跡集合。

3.1 一種更簡潔的Petri網(wǎng)表示

分析如式（2）形式的π演算的遞歸結構，如果該π演算表達式不滿足遞歸出口條件，那么會循環(huán)執(zhí)行自調(diào)用表達式之前的子表達式P（a1，…，an），執(zhí)行過程大致如圖5所示。

如果π演算表達式的遞歸結構執(zhí)行多次，那么會產(chǎn)生巨大的Petri網(wǎng)，因此本文考慮將其進行簡化，得到一種更簡潔的Petri網(wǎng)表示。受圖3啟發(fā)，本文將典型π演算遞歸結構轉(zhuǎn)換結果用全景圖表示，如圖6所示。

這里需要考慮以下幾個問題：

圖5 π演算表達式遞歸結構執(zhí)行圖Fig.5 Execution ofπcalculus expression recursive structure

圖6 一種更簡潔的Petri網(wǎng)表示Fig.6 A more compact representation of Petri net

對于遞歸出口之前每次執(zhí)行的表達式P（a1，…，an），其每次具體執(zhí)行是不一樣的，我們在其前面用軌跡標記，表示按照軌跡σ1，σ2，…，σn執(zhí)行，這里的軌跡是根據(jù)判定庫所的變化一步一步生成的。然后在執(zhí)行遞歸返回時，Q（a″1，…，a″n）按照軌跡σ1，σ2，…，σn的逆軌跡σn，σn－1，…，σ1執(zhí)行。

3.2 等價性證明

本文給出了Np的一種更簡潔Petri網(wǎng)表示，記為Nc，它是具有有限庫所、變遷和弧的網(wǎng)結構，保留了系統(tǒng)的語義，編碼完全相同的軌跡集合。

定理2 Nc是具有有限庫所、變遷和弧的Petri網(wǎng)圖，并且使得Np和Nc編碼完全相同的軌跡集合（激發(fā)順序）。

證明 針對遞歸結構，分別從遞歸調(diào)用、遞歸出口及遞歸返回三部分考慮其執(zhí)行的軌跡集合。

（1）對每次遞歸調(diào)用執(zhí)行的表達式P（a1，…，an），Np和Nc的執(zhí)行軌跡均為｛σ1，σ2，…，σn｝。

（2）對遞歸出口執(zhí)行的表達式R（b1，…，bn），由于只執(zhí)行一次，因此其軌跡集合可以忽略。

（3）對遞歸返回表達式Q（a″1，…，a″n），Np和Nc的軌跡集合均為｛σn，σn－1，…，σ1｝。證畢。

4 結束語

通過對π演算遞歸結構和Petri網(wǎng)的經(jīng)典理論進行研究分析，本文首先給出了遞歸π演算的基本形式，然后將遞歸π演算向Petri網(wǎng)進行轉(zhuǎn)換，并證明這種轉(zhuǎn)換的互模擬等價性；隨后針對多次遞歸的情況對由π演算遞歸結構轉(zhuǎn)換得到的Petri網(wǎng)進行簡化，得到了一種保持系統(tǒng)語義的、編碼完全相同的軌跡集合的更簡潔的Petri網(wǎng)，與原Petri網(wǎng)相比能夠提高對于模型驗證的效率，比如對移動系統(tǒng)的驗證等。

［1］Thomas E.Service-Oriented Architecture（SOA）：Concepts，Technology，and Design［M］.New Jersey：Prentice Hall，2005.

［2］Leymann F，Roller D，Schmidt M T.Web services and business process management［J］.IBM Systems Journal，2002，41（2）：198-211.

［3］Milner R，Parrow J，Walker D.A calculus of mobile processes part I／II［J］.Journal of Information and Computation，1992，100（1）：1-77.

［4］Milner R.Communication and Concurrent［M］. New Jersey：Pretice Hall，1989.

［5］Roland Meyer.A theory of structural stationarity in theπ-Calculus［J］.Acta Informatica，2009，46：87-137.

［6］Michele B，Davide S.A fully abstract semantics for causality in the Pi calculus［C］∥Proceedings of STACS＇95，LNCS，Springer，1995，900：243-254.

［7］Baeten J C M，Bergstra J A，Klop J W.An operational semantics for process algebra［J］.Mathematical Problems in Computation Theory，1988，21：47-81.

［8］Eile B，Raymond D，Maciei K.Petri Net Algebra［M］.Bolin：Springer，2001.

［9］Ulrich B，Daniel M.Object-oriented concepts for coloured Petri nets［C］∥IEEE International Conference on Systems，Man and Cybernetics，1993，3：279-286.

［10］Peschanski F，Klaudel H，Devillers R.A Petri Net Interpretation of Open Reconfigurable Systems［C］∥PETRI NETS 2011，LNCS 6709，2011：208-227.

［11］Christensen S，Hansen N D.Coloured Petri nets extended with place capacities，test arcs and inhibitor arcs［J］.Application and Theory of Petri Nets，1993，691：186-205.

［12］Raymond D，Hanna K，Maciej K.A compositional Petri net translation of general Pi calculus terms［J］. Formal Aspects of Computing，2008，20：429-450.

［13］Peschanski F，Klaudel H，Devillers R.A decidable characterization of a graphical pi-calculus with iterators［C］∥In：Infinity.EPTCS，2010，39：47-61.