軟件進(jìn)程計(jì)算結(jié)構(gòu)分析

(武漢大學(xué) 計(jì)算機(jī)學(xué)院 武漢 430072)

摘 要：以數(shù)學(xué)語(yǔ)義分析并描述軟件進(jìn)程計(jì)算結(jié)構(gòu)，建立了實(shí)用計(jì)算原型樹(shù)。在此基礎(chǔ)上，實(shí)現(xiàn)計(jì)算結(jié)構(gòu)模塊化處理及建立模塊化展開(kāi)公式，使軟件進(jìn)程的計(jì)算從節(jié)點(diǎn)算子的計(jì)算轉(zhuǎn)換成模塊算子計(jì)算。

關(guān)鍵詞：數(shù)學(xué)語(yǔ)義; 計(jì)算結(jié)構(gòu); 原型樹(shù); 計(jì)算單位; 模塊

中圖分類(lèi)號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)05-1733-03

Analysis of computational structure of software process

LI Hui CHEN Shihong

（School of Computer Wuhan University Wuhan 430072 China）

Abstract:This paper analyzed and described the computational structure of software process (SP) by mathematical semantics and established a practical computing prototype tree. On the basis of that fulfilled modularized processing of computational structure and establishment of modularized expansion formula. Converted the computing of software process from node operator computing to modular operator computing.

Key words：mathematical semantics; computational structure; prototype tree; computing unit; module

0 引言

在前面研究基礎(chǔ)上，本文以數(shù)學(xué)語(yǔ)義分析和描述軟件進(jìn)程SP計(jì)算結(jié)構(gòu)，建立了SP模塊M（θ，X）之算子θ∈ASeteq（M）的遞歸分解式：

pt（θ）= tree（θ，Nos，E）（1）

把 θ展開(kāi)成計(jì)算原型樹(shù)prictr（θ，t），表達(dá)SP實(shí)施處理計(jì)算的基本算法結(jié)構(gòu)。其中ASeteq（M）是實(shí)現(xiàn)模塊M的所有等價(jià)算子集合。值得指出的是，式（1）只考慮了θ函數(shù)映射的組合結(jié)構(gòu)，即

ρ（θ）={θ1，θ2，…，θk}[ρ∈ρθ]  k＞1（2）

其中：ρθ是算子θ的所有分解運(yùn)算的集合。

式（1）還不是SP的實(shí)際計(jì)算結(jié)構(gòu)。 θ函數(shù)映射除了組合結(jié)構(gòu)之外，還有遞歸（重復(fù)）結(jié)構(gòu)。現(xiàn)有的程序設(shè)計(jì)語(yǔ)言都有相應(yīng)的語(yǔ)法規(guī)定，以語(yǔ)法形式同時(shí)規(guī)定這兩種結(jié)構(gòu)。完善實(shí)現(xiàn)θ函數(shù)的結(jié)構(gòu)特征，還必須擴(kuò)充計(jì)算原型樹(shù)prictr（θ，t）公式。在理論和技術(shù)上，它自身提供了這種擴(kuò)充的基礎(chǔ)。本文的首要目的是：在數(shù)學(xué)語(yǔ)義的基礎(chǔ)上，使prictr（θ，t）實(shí)現(xiàn)θ函數(shù)的組合和遞歸兩種結(jié)構(gòu)，滿足SP實(shí)際計(jì)算結(jié)構(gòu)要求，并在此基礎(chǔ)上建立它的理論模型。

SP計(jì)算結(jié)構(gòu)，依據(jù)特征的不同提取，在實(shí)際處理計(jì)算時(shí)，一個(gè)可求解問(wèn)題P常常抽象成不同的抽象類(lèi)型。現(xiàn)有程序設(shè)計(jì)語(yǔ)言中常見(jiàn)的抽象類(lèi)型有功能（Fun）、數(shù)據(jù)（Da）和對(duì)象（Ob）三類(lèi)。式（1）適用所有類(lèi)型^[1]，它們具有相似的遞歸分解過(guò)程。但是，P取不同抽象類(lèi)型，程序設(shè)計(jì)語(yǔ)言內(nèi)含的軟件體系結(jié)構(gòu)模式、數(shù)據(jù)類(lèi)型以及適應(yīng)的基本算子體系各不相同。P的抽象類(lèi)型一旦確定，則它的所有進(jìn)程SP的類(lèi)型也將隨著確定，并在運(yùn)行過(guò)程中始終保持不變。不同類(lèi)型的差異對(duì)SP的影響歸結(jié)為四個(gè)方面：a）M（θ，X）的算子和數(shù)據(jù)的定義、性質(zhì)和結(jié)構(gòu)都會(huì)不一樣；b)影響?yīng)泉纸膺\(yùn)算的性質(zhì)和選取；c)形成算子分解的不同環(huán)境條件；d)影響計(jì)算原型prictr（θ，t）計(jì)算單位的提取和計(jì)算結(jié)構(gòu)的組成。

在prictr（θ，t）上，算子分布影響它的計(jì)算結(jié)構(gòu)。算子分布的基本特征是：a)有些算子只在一個(gè)節(jié)點(diǎn)出現(xiàn)一次；b)有些算子可能多次出現(xiàn)在不同的節(jié)點(diǎn)；c)算子不可能在一條路徑的節(jié)點(diǎn)多次重復(fù)出現(xiàn)。第一類(lèi)節(jié)點(diǎn)稱為單次節(jié)點(diǎn)，第二類(lèi)稱為多重節(jié)點(diǎn)。一條計(jì)算路徑多次重復(fù)出現(xiàn)的節(jié)點(diǎn)稱為重復(fù)節(jié)點(diǎn)，重復(fù)節(jié)點(diǎn)不能自然生成，有待其擴(kuò)充。在現(xiàn)實(shí)計(jì)算世界，只出現(xiàn)第一類(lèi)節(jié)點(diǎn)的prictr（θ，t）雖然完全可能存在，但畢竟不是常見(jiàn)的現(xiàn)象，多數(shù)情況會(huì)出現(xiàn)多重節(jié)點(diǎn)或重復(fù)節(jié)點(diǎn)。本文討論的問(wèn)題還包括：多重節(jié)點(diǎn)帶來(lái)prictr（θ，t）怎樣的結(jié)構(gòu)變化；在三類(lèi)節(jié)點(diǎn)隨機(jī)出現(xiàn)時(shí)，在prictr（θ，t）中如何提取計(jì)算單位，形成SP實(shí)際計(jì)算結(jié)構(gòu)。

為了下面的討論，在這里先引入計(jì)算單位概念。

計(jì)算單位定義為具有封閉、獨(dú)立處理計(jì)算功能的模塊；獨(dú)立自主完成自身全部處理計(jì)算過(guò)程，不求助外部訪問(wèn)和支援；它的封閉性，使其內(nèi)部世界被外界視為一個(gè)黑箱，不能進(jìn)入內(nèi)部訪問(wèn)，只能通過(guò)它的接口交換信息和控制調(diào)度。 

計(jì)算單位可以組裝更大的計(jì)算單位，計(jì)算單位有粒度（規(guī)模）大小之分，不同大小粒度的計(jì)算單位可形成嵌套體系，這種嵌套體系成為它們相對(duì)抽象化程度的刻度系統(tǒng)。粒度測(cè)度計(jì)算單位抽象化程度，最小粒度計(jì)算單位是最基本的計(jì)算單位，處于嵌套體系最內(nèi)層，不可能從中再抽象提取更小刻度的計(jì)算單位。Prictr（θ，t）的抽象運(yùn)算以一定粒度提取計(jì)算單位，抽象運(yùn)算是分解運(yùn)算的逆運(yùn)算。分解—抽象運(yùn)算對(duì)求解問(wèn)題實(shí)現(xiàn)計(jì)算結(jié)構(gòu)性分析—綜合，最終實(shí)現(xiàn)prictr（θ，t）以計(jì)算單位為構(gòu)件的計(jì)算結(jié)構(gòu)模式。計(jì)算單位具有多種結(jié)構(gòu)形態(tài)，本文將分析說(shuō)明prictr（θ，t）的算子分布引起其結(jié)構(gòu)形態(tài)的變化，所有形態(tài)變化由三種基本形態(tài)，即線性、重復(fù)和網(wǎng)格組合形成。

1 擴(kuò)充遞歸公式

遞歸計(jì)算是可計(jì)算函數(shù)的一個(gè)重要結(jié)構(gòu)特征，式（1）不能直接實(shí)現(xiàn)遞歸計(jì)算。本章將擴(kuò)充式（1）的數(shù)學(xué)語(yǔ)義，在prictr（θ，t）的基礎(chǔ)上使之同時(shí)支持遞歸計(jì)算。

依據(jù)分解計(jì)算原則，式（1）約定：對(duì)于算子 θ，它的原型樹(shù)prictr（θ，t）的任何一條路徑上的算子系列，具有嚴(yán)格遞減包含關(guān)系，不允許任何算子重復(fù)出現(xiàn)。按函數(shù)結(jié)構(gòu)遞歸公式定義，算子的重復(fù)是其函數(shù)自身的重復(fù)，意味著實(shí)現(xiàn)它的算法過(guò)程重復(fù)，也就是它的原型樹(shù)重復(fù)。這個(gè)原則對(duì)每個(gè)子算子θj∈prictr（θ，t）的重復(fù)請(qǐng)求也正確。因此，在原型樹(shù)prictr（θ，t）上實(shí)現(xiàn)任何算子的重復(fù)有兩種途徑：a)在prictr（θ，t）生成后，依次遍歷其節(jié)點(diǎn)，對(duì)需要重復(fù)算子的所在節(jié)點(diǎn)加注某種重復(fù)標(biāo)志（如‘*’），或稱重復(fù)遍歷法。b)在prictr（θ，t）生成過(guò)程中，對(duì)需要重復(fù)的節(jié)點(diǎn)即席加注某種重復(fù)標(biāo)志（如‘*’）；伴隨prictr（θ，t）的遞歸展開(kāi)過(guò)程，逐點(diǎn)重復(fù)節(jié)點(diǎn)的加注過(guò)程，或稱重復(fù)插入法。在prictr（θ，t）中，加注節(jié)點(diǎn)注明該節(jié)點(diǎn)的算子及其原型樹(shù)重復(fù)。例如，子算子θj∈prictr（θ，t）的節(jié)點(diǎn)已加注重復(fù)標(biāo)志‘*’，則顯示θj及其prictr（θj，h）（prictr（θ，t））是重復(fù)因子，并分別可表示為θj和prictr（θj，h）。兩種加注過(guò)程作用于prictr（θ，t）實(shí)現(xiàn)重復(fù)加注運(yùn)算，這個(gè)運(yùn)算以符號(hào)‘Re’表示。 正式定義如下:

定義1 算子θ的重復(fù)運(yùn)算定義為

Re（ρt（θ））= prictr（θ，t）; ρ∈ρθ（3）

a)ρθ是θ的分解運(yùn)算集合。

b)0≤｜*｜≤k（4）

其中：｜*｜表示‘*’的值；k是有限正整數(shù)。

c)｜*｜=0（5）

表示prictr（θ，t）沒(méi)有重復(fù)。

定義1說(shuō)明：a)算子θ的任何分解運(yùn)算ρ∈ρθ均可能實(shí)現(xiàn)重復(fù)；b)算子θ的重復(fù)是其原型樹(shù)prictr（θ，t）的重復(fù)；c)重復(fù)運(yùn)算Re施加于prictr（θ，t）不改變其原型結(jié)構(gòu)，它自身可能或不重復(fù)。

Prictr（θ，t）含有加注算子，實(shí)現(xiàn)θ或其子算子的重復(fù)計(jì)算，將可計(jì)算函數(shù)的組合與遞歸兩種計(jì)算結(jié)構(gòu)融為一體，實(shí)現(xiàn)了算子的完整計(jì)算。Prictr（θ，t）稱為擴(kuò)充遞歸公式，它的遞歸過(guò)程稱為擴(kuò)充遞歸過(guò)程。帶*節(jié)點(diǎn)的原型樹(shù)若含有帶*的子節(jié)點(diǎn)，則形成重復(fù)嵌套，后者是前者的內(nèi)層重復(fù)；在前者的每個(gè)周期內(nèi)后者重復(fù)運(yùn)行。重復(fù)嵌套現(xiàn)象還可能繼續(xù)擴(kuò)展，甚至形成多層重復(fù)嵌套體系。定義1直接得到下面的推論。

推論1 對(duì)于可求解問(wèn)題p，它的任何軟件進(jìn)程Sp，

ρt（θ）= prictr（θ，t）[ρ∈ρθ，θ∈ASeteq（M）] 

Re（ρt（θ））= prictr（θ，t）（6）

其中：prictr（θ，t）是實(shí)用計(jì)算原型樹(shù)。 

2 計(jì)算原型網(wǎng)格化處理

在以前討論中，每個(gè)軟件進(jìn)程Sp定義成一個(gè)模塊M，對(duì)M處理的原型樹(shù)不只一個(gè)，而是一個(gè)集合PRICTR（M）。推論1的結(jié)論可直接推廣到這個(gè)集合，于是有下面的推論。

推論2 對(duì)于每個(gè)可求解軟件進(jìn)程Sp，則

Re（PRICTR（M））=PRICTR（M）（7）

或prictr（θ，t）∈PRICTR（M）

Re（prictr（θ，t））∈PRICTR（M）（8）

求解Sp的實(shí)用計(jì)算原型樹(shù)集PRICTR（M）可分為線性和非線性兩個(gè)子集。

線性計(jì)算原型樹(shù)定義為：它的節(jié)點(diǎn)彼此包含互不相同的算子，同時(shí)不包含重復(fù)節(jié)點(diǎn)，它的根節(jié)點(diǎn)稱為線性節(jié)點(diǎn)。非線性計(jì)算原型樹(shù)中有多個(gè)節(jié)點(diǎn)包含有相同的算子，這些節(jié)點(diǎn)不位于同一條路徑上；或者其中包含有重復(fù)節(jié)點(diǎn)。非線性原型樹(shù)的根節(jié)點(diǎn)稱為非線性節(jié)點(diǎn)。

對(duì)于非線性計(jì)算原型樹(shù)，不失一般性，假定多次出現(xiàn)的算子在不同節(jié)點(diǎn)展開(kāi)的子原型樹(shù)具有相同的形態(tài)。在這樣的假定下，包含同一個(gè)算子的多個(gè)節(jié)點(diǎn)，事實(shí)上匯聚到一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)稱為多重節(jié)點(diǎn)。多重節(jié)點(diǎn)匯聚到達(dá)所有相同算子節(jié)點(diǎn)的路徑，則原型樹(shù)形態(tài)實(shí)質(zhì)上成為網(wǎng)狀結(jié)構(gòu)。非線性實(shí)用計(jì)算原型樹(shù)prictr（θ，t）可能同時(shí)包含多重節(jié)點(diǎn)和重復(fù)節(jié)點(diǎn)，組成復(fù)雜的網(wǎng)格結(jié)構(gòu)。

Prictr（θ，t）網(wǎng)格化處理算法是將具有相同算子的節(jié)點(diǎn)匯集于多重節(jié)點(diǎn)；設(shè)計(jì)多重節(jié)點(diǎn)的通用接口，協(xié)調(diào)、滿足所有到達(dá)路徑對(duì)數(shù)據(jù)和資料的要求。

Prictr（θ，t）網(wǎng)格基于多重節(jié)點(diǎn)形成，網(wǎng)格化處理后，它的節(jié)點(diǎn)分成兩類(lèi)，即網(wǎng)格節(jié)點(diǎn)和非網(wǎng)格節(jié)點(diǎn)。前者是位于網(wǎng)格上所有的節(jié)點(diǎn)；后者不是網(wǎng)格上的所有節(jié)點(diǎn)。這些節(jié)點(diǎn)具有線性性，或是重復(fù)節(jié)點(diǎn)。

一個(gè)實(shí)用計(jì)算原型樹(shù)prictr（θ，t）由線性、重復(fù)和多重三類(lèi)節(jié)點(diǎn)組合構(gòu)成，它們的不同分布形成不同的實(shí)際計(jì)算結(jié)構(gòu)。這三類(lèi)節(jié)點(diǎn)具有不同的性質(zhì)，在網(wǎng)格化處理過(guò)程中出現(xiàn)和形成的先后順序不一樣。首先，重復(fù)節(jié)點(diǎn)自主和封閉性，不僅影響原型樹(shù)的網(wǎng)格化處理、多重節(jié)點(diǎn)的形成、線性節(jié)點(diǎn)的存在性，最終還影響prictr（θ，t）的計(jì)算結(jié)構(gòu)形態(tài)。重復(fù)節(jié)點(diǎn)算子誘發(fā)它的原型樹(shù)重復(fù)運(yùn)行，形成一個(gè)獨(dú)立的重復(fù)結(jié)構(gòu)。重復(fù)結(jié)構(gòu)的重復(fù)體就是它的原型樹(shù)，而其重復(fù)次數(shù)依賴環(huán)境和條件確定，具有不確定性和非線性性。重復(fù)節(jié)點(diǎn)參與多重節(jié)點(diǎn)組成，必須謹(jǐn)慎重復(fù)條件的處理，重復(fù)體內(nèi)的計(jì)算結(jié)構(gòu)不參與體外節(jié)點(diǎn)的多重處理和線性化處理。因此，prictr（θ，t）的網(wǎng)格化處理之前必須首先處理重復(fù)節(jié)點(diǎn)。最后實(shí)施線性化處理。

關(guān)于prictr（θ，t）的網(wǎng)格化處理有如下推論：

推論3 網(wǎng)格化處理分類(lèi)PRICTR（M）（θ∈ASeteq（M））

PRICTR（M）= PRICTR lin（M）∪PRICTRn lin（M）（9）

其中:‘lin’，‘n lin’是線性和非線性標(biāo)志。

a）PRICTRlin（M）是線性計(jì)算樹(shù)集合

prictr（θ，t）∈ PRICTRlin（M）

prictr（θ，t）=prictrlin（θ，t）（10）

其中：θ節(jié)點(diǎn)是線性節(jié)點(diǎn)。

b)非線性計(jì)算樹(shù)集合為PRICTRn lin（M）

prictr（θ，t）∈PRICTRn lin（M）

prictr（θ，t）=prictrn lin（θ，t）（11）

其中：θ節(jié)點(diǎn)是非線性節(jié)點(diǎn)。

3 計(jì)算原型模塊化處理

模塊化處理對(duì)實(shí)用計(jì)算原型樹(shù)prictr（θ，t），以計(jì)算單位為模塊進(jìn)行劃分形成模塊計(jì)算結(jié)構(gòu)，變換原型樹(shù)節(jié)點(diǎn)計(jì)算成等價(jià)的模塊計(jì)算。

根據(jù)上一章的分析，prictr（θ，t）隱含的計(jì)算單位可能有三種基本類(lèi)型，即線性、網(wǎng)格和重復(fù)。這些計(jì)算單位的性質(zhì)及其關(guān)系規(guī)定了模塊化算法必須遵循的基本過(guò)程。

原型樹(shù)prictr（θ，t）模塊化算法有以下三步：

a)分離、提取重復(fù)計(jì)算單位。重復(fù)節(jié)點(diǎn)原型樹(shù)自成一個(gè)計(jì)算單位。但是，每個(gè)重復(fù)節(jié)點(diǎn)可能位于更大重復(fù)節(jié)點(diǎn)的原型樹(shù)之中，形成重復(fù)嵌套；嵌套的包含性（兩個(gè)重復(fù)計(jì)算單位要么有完全包含關(guān)系，要么彼此完全無(wú)關(guān)）可能形成多層次嵌套。多層重復(fù)嵌套必然存在一個(gè)最外層的重復(fù)計(jì)算單位，這個(gè)外層計(jì)算單位也就是最大的重復(fù)計(jì)算單位；最外層重復(fù)節(jié)點(diǎn)原型樹(shù)是嵌套（如果存在）的最大區(qū)域范圍。

這一步完成以下兩個(gè)具體操作：

(a)分離最大重復(fù)單位操作。確定最大（最外層）重復(fù)單位的重復(fù)節(jié)點(diǎn)原型樹(shù)。

(b)抽象提取操作。凡有重復(fù)嵌套存在，首先提取最外層重復(fù)節(jié)點(diǎn)原型樹(shù)，使它成一個(gè)獨(dú)立模塊——重復(fù)計(jì)算單位。抽象提取的具體操作是：將確定提取的重復(fù)節(jié)點(diǎn)原型樹(shù)自整體中剪去；這個(gè)重復(fù)節(jié)點(diǎn)加上標(biāo)記‘a(chǎn)b’，留在原來(lái)的位置作為一個(gè)抽象葉節(jié)點(diǎn)；剪裁出的原型樹(shù)分離整體、自成一個(gè)自立的重復(fù)計(jì)算單位。此時(shí)，具有抽象葉節(jié)點(diǎn)的原型樹(shù)成為新原型樹(shù)，或稱為被抽象化原型樹(shù)，并標(biāo)記‘a(chǎn)b’。例如，θj∈prictr（θ，t）是最外層（重復(fù)嵌套）重復(fù)節(jié)點(diǎn)算子，抽象提取它的子原型樹(shù)prictr（θj，h）（prictr（θ，t））：(a)自prictr（θ，t）剪去這個(gè)子原型樹(shù)，自成一個(gè)獨(dú)立模塊；(b)θ j的節(jié)點(diǎn)加上標(biāo)記‘a(chǎn)b’，留在原處，成為抽象葉節(jié)點(diǎn)；(c)prictr（θ，t）成為帶有抽象葉節(jié)點(diǎn)的計(jì)算樹(shù)prictr*ab（θ，t），其中θ j的節(jié)點(diǎn)為其抽象葉節(jié)點(diǎn)ab；(d)如果算子θ自身是重復(fù)節(jié)點(diǎn)，prictr（θ，t）抽象成一個(gè)孤立葉節(jié)點(diǎn)。上述過(guò)程(a)~(c)相當(dāng)于對(duì)其體內(nèi)的重復(fù)系統(tǒng)進(jìn)行處理。

單層重復(fù)節(jié)點(diǎn)（不在嵌套體內(nèi)）原型樹(shù)自身就是最大重復(fù)區(qū)域，直接進(jìn)行抽象提取。此步完成后，prictr（θ，t）實(shí)現(xiàn)了重復(fù)計(jì)算單位抽象，記為prictrab（θ，t）。

下面的推論表達(dá)prictrab（θ，t）的數(shù)學(xué)描述。

推論4 對(duì)于任何prictr（θ，t）∈PRICTRn lin（M）（θ∈ASeteq（M）），重復(fù)單位提取成為新的抽象原型樹(shù)

prictrab（θ，t）=tree（θ，Eab，Dab，I(xiàn)Dab）

（12）

其中：EabEE是prictr（θ，t）邊集，Eab是prictrab（θ，t）邊集；Dab=Dab1∪I(xiàn)Dab，Dab是prictrab（θ，t）的節(jié)點(diǎn)集，Dab1D是它的內(nèi)節(jié)點(diǎn)集，D是prictr（θ，t）的節(jié)點(diǎn)集；I(xiàn)Dab是prictrab（θ，t）的葉節(jié)點(diǎn)集；I(xiàn)Dab =I(xiàn)Dab1 ∪I(xiàn)Dab2，I(xiàn)Dab1I(xiàn)D，I(xiàn)D是prictr（θ，t）的葉節(jié)點(diǎn)集，I(xiàn)Dab2是prictrab（θ，t）重復(fù)抽象葉節(jié)點(diǎn)集。

θ j∈IDab2（prictr（θj，h）prictr（θ，t））∧

（prictr（θ j，h）prictrab（θ，t））（13）

推論4強(qiáng)調(diào)原型樹(shù)抽象化結(jié)構(gòu)保持樹(shù)型不變，重復(fù)節(jié)點(diǎn)成為它的抽象葉節(jié)點(diǎn)；可能存在重復(fù)嵌套，prictrab（θ，t）抽象葉節(jié)點(diǎn)，可能少于prictr（θ，t）體內(nèi)重復(fù)節(jié)點(diǎn)；重復(fù)體分離使多重節(jié)點(diǎn)的規(guī)模與數(shù)量可能都會(huì)相應(yīng)縮小與降低，甚至不再出現(xiàn)多重節(jié)點(diǎn)。

b)網(wǎng)格化處理。在prictrab（θ，t）上進(jìn)行，提取多重節(jié)點(diǎn)計(jì)算單位。網(wǎng)格化處理僅到達(dá)重復(fù)葉節(jié)點(diǎn)，重復(fù)節(jié)點(diǎn)也可成為多重節(jié)點(diǎn)，但在合成多重節(jié)點(diǎn)時(shí)，除了接口要進(jìn)行重新定義之外，還必須重復(fù)條件變化的設(shè)計(jì)。

在prictrab（θ，t）內(nèi)，多重節(jié)點(diǎn)可能形成復(fù)雜的網(wǎng)格關(guān)系，提取計(jì)算單位模塊必須處理這種網(wǎng)格關(guān)系。

不同多重節(jié)點(diǎn)的網(wǎng)格關(guān)系有三種基本形態(tài)：(a)彼此無(wú)關(guān)，互不相交也互不包含；(b)相交但互不包含；(c)包含關(guān)系。這三種關(guān)系交織組合，形成相交網(wǎng)格結(jié)構(gòu)。但不論網(wǎng)格如何復(fù)雜，所有多重節(jié)點(diǎn)必然按層次分布于prictrab（θ，t）。其中低層多重節(jié)點(diǎn)相對(duì)上層多重節(jié)點(diǎn)的關(guān)系有三種可能的情況：(a)不包含于任何上層多重節(jié)點(diǎn)體內(nèi)，自成一個(gè)獨(dú)立網(wǎng)格；(b)位于上層多重節(jié)點(diǎn)，嵌套于上層網(wǎng)格之內(nèi)；(c)同時(shí)位于多個(gè)多重節(jié)點(diǎn)體內(nèi)，成為二次或更高次多重節(jié)點(diǎn)，形成復(fù)雜網(wǎng)格關(guān)系。

破解可能出現(xiàn)的復(fù)雜網(wǎng)格關(guān)系不止一種算法。這里定義下面的算法。

網(wǎng)格化處理算法包括分離獨(dú)立網(wǎng)格結(jié)構(gòu)（包括嵌套）；分割相交網(wǎng)格；抽象處理獨(dú)立（包括分割后獨(dú)立）網(wǎng)格。其中抽象處理獨(dú)立（包括分割后獨(dú)立）網(wǎng)格如同重復(fù)單位的提取一樣（包括多重網(wǎng)格嵌套，提取最大計(jì)算單位）。自原型樹(shù)prictrab（θ，t）中剪去選定待處理多重節(jié)點(diǎn)原型樹(shù)，自成一個(gè)獨(dú)立單位；該多重節(jié)點(diǎn)仍留在原來(lái)的位置上，加上標(biāo)記‘a(chǎn)b’，成為一個(gè)抽象葉節(jié)點(diǎn)。

這一步的關(guān)鍵是分割相交網(wǎng)格。如果相交網(wǎng)格包含于一個(gè)更大的多重節(jié)點(diǎn)的原型樹(shù)，則不進(jìn)行分割，按嵌套結(jié)構(gòu)處理；否則，對(duì)于相交網(wǎng)格首先確定高次多重節(jié)點(diǎn)，每個(gè)高次多重節(jié)點(diǎn)都是一個(gè)網(wǎng)格交點(diǎn)，它們的抽象化形成抽象葉節(jié)點(diǎn)，則有可能分割相交網(wǎng)格。分割處理是一個(gè)過(guò)程，自第一級(jí)交節(jié)點(diǎn)開(kāi)始，每次分割之后已形成獨(dú)立結(jié)構(gòu)（包括嵌套）不再分割，下次分割只作用仍然相交的網(wǎng)格。這個(gè)過(guò)程至多進(jìn)行到最高次節(jié)點(diǎn)，必定終止，并使所有相交網(wǎng)格得到分割。

c)prictr（θ，t）模塊抽象。計(jì)算原型樹(shù)prictr（θ，t）模塊化算法前兩步依次完成了重復(fù)計(jì)算單位和網(wǎng)格計(jì)算單位的提取，形成的模塊各自獨(dú)立成為計(jì)算單位，這些計(jì)算單位抽象成葉節(jié)點(diǎn)，沉淀到prictrab（θ，t）的葉端。對(duì)應(yīng)每個(gè)抽象葉節(jié)點(diǎn)的計(jì)算單位，它們?cè)蜆?shù)仍然可能包含多重和重復(fù)節(jié)點(diǎn)，對(duì)它們還要進(jìn)行上面同樣的處理。因此，計(jì)算原型樹(shù)prictr（θ，t）模塊化算法也是一個(gè)反復(fù)進(jìn)行的遞歸過(guò)程。

Prictrab（θ，t）不一定再保持樹(shù)型結(jié)構(gòu)，但它的網(wǎng)格只可能體現(xiàn)在葉節(jié)點(diǎn)處，在葉節(jié)點(diǎn)層之上仍保持樹(shù)型結(jié)構(gòu)，這樣的prictrab（θ，t）稱為準(zhǔn)線性結(jié)構(gòu)，即LTree。這個(gè)準(zhǔn)線性結(jié)構(gòu)最終也被抽象（如果需要）成一個(gè)模塊，并記為Mab（θ）。

Mab（θ）與M（θ）的區(qū)別在于前者是以計(jì)算單位模塊展開(kāi)，而后者以節(jié)點(diǎn)展開(kāi)。

Prictrab（θ，t）所有抽象葉節(jié)點(diǎn)形成一個(gè)計(jì)算模塊集SetM（θ），其定義表達(dá)式為

SetM（θ）={Mab（θi）｜θi∈prictr（θ，t），θi=θi或θim｝ （14）

其中θmi表示多重算子。

下面的推論表達(dá)了Mab（θ）的數(shù)學(xué)描述。

推論5 對(duì)于任何prictr（θ，t）∈PRICTRn lin（M）（θ∈ASeteq（M）），抽象處理成一個(gè)計(jì)算模塊Mab（θ），它的計(jì)算結(jié)構(gòu)prictrab（θ，t）的定義表達(dá)式為

prictrab（θ，t）= LTree（θ，Eab，Dab，I(xiàn)Dab）(15)

其中:EabE，E是prictr（θ，t）邊集，Eab是prictrab（θ，t）邊集；Dab=D1∪I(xiàn)Dab，Dab是prictrab（θ，t）的節(jié)點(diǎn)集，D1D是其內(nèi)節(jié)點(diǎn)集，D是prictr（θ，t）的節(jié)點(diǎn)集；I(xiàn)Dab是prictrab（θ，t）的葉節(jié)點(diǎn)集；I(xiàn)Dab =I(xiàn)Dab1∪I(xiàn)Dab2，I(xiàn)Dab1I(xiàn)D，ID是