基于推理機(jī)制的邏輯語(yǔ)言在Web服務(wù)組合機(jī)制中的應(yīng)用

趙瑩映，章 韻

（南京郵電大學(xué)計(jì)算機(jī)學(xué)院 南京 210003）

1 引言

隨著人們?nèi)找嫣嵘木W(wǎng)絡(luò)需求，加上WWW自身發(fā)展的重要導(dǎo)向，一個(gè)新興的課題——語(yǔ)義Web及其自動(dòng)組合服務(wù)應(yīng)運(yùn)而生，Web服務(wù)這樣一種第三產(chǎn)業(yè)的衍生物，毫無(wú)爭(zhēng)議地成為眼下新晉的研究課題之一。Web服務(wù)組合管理關(guān)鍵技術(shù)的目標(biāo)就是讓網(wǎng)絡(luò)協(xié)議規(guī)范化、服務(wù)項(xiàng)目原子化、服務(wù)內(nèi)容組合化。語(yǔ)義Web服務(wù)組合作為一種能夠快速提供復(fù)雜型組合服務(wù)的方法近年來(lái)得到廣泛關(guān)注，同時(shí)為了達(dá)到上述目的，對(duì)其進(jìn)一步的研究是必不可少的，而如何提高服務(wù)組合的可用性和實(shí)際性則成為Web服務(wù)組合管理中必備的組成部分和亟待解決的關(guān)鍵問題。

所謂Web服務(wù)[1,2]，是指一個(gè)應(yīng)用程序能夠給外界提供一個(gè)通過Web進(jìn)行調(diào)用的API，即用戶可以通過簡(jiǎn)單方式向Web發(fā)送請(qǐng)求，讓W(xué)eb調(diào)用其應(yīng)用程序，等待查看返回結(jié)果?；谡Z(yǔ)義的Web自動(dòng)組合服務(wù)，是指用一種或多種語(yǔ)義標(biāo)記語(yǔ)言描述服務(wù)提供者提供的各個(gè)原子服務(wù)，使其成為可被計(jì)算機(jī)或服務(wù)器理解的知識(shí)，進(jìn)而通過情景演算推理機(jī)制，使得計(jì)算機(jī)可針對(duì)用戶的需求發(fā)現(xiàn)知識(shí)并對(duì)其加以重組，以此產(chǎn)生一系列組合形式的服務(wù)回饋用戶。

Prolog[3]（programming in logic），即人們通常所說的人工智能語(yǔ)言，是一種建立于邏輯學(xué)理論基礎(chǔ)之上的邏輯編程語(yǔ)言，其最重要的應(yīng)用在于自然語(yǔ)言的理解以及智能知識(shí)庫(kù)的構(gòu)建，它采用一些代替邏輯語(yǔ)言的符號(hào)表示程序的內(nèi)容，因此具有相對(duì)較快的編程速度。平臺(tái)無(wú)關(guān)性讓Prolog程序的應(yīng)用范圍更廣，更能夠滿足編寫者的需求。在Web服務(wù)的研究過程中，原子服務(wù)的描述是一個(gè)不容忽視的問題，因?yàn)闀?huì)影響到推理階段的質(zhì)量。而Prolog較強(qiáng)的遞歸功能和內(nèi)部事實(shí)數(shù)據(jù)庫(kù)功能可以勝任這項(xiàng)工作，下文所要提到的擴(kuò)展后的Golog系列應(yīng)用都能證明選用這類語(yǔ)言可以解決在研究中遇到的諸多問題。

2 Prolog下的情景演算理論

情景演算[4]適用于描述動(dòng)態(tài)變化的世界，是一種關(guān)于狀態(tài)、行為和行為作用于狀態(tài)的結(jié)果的形式化謂詞演算。由一系列行為構(gòu)成的一種可能的世界歷史，以一種一階專有詞語(yǔ)狀態(tài)來(lái)表示。

預(yù)先把知識(shí)表達(dá)為關(guān)于狀態(tài)和行為的公式，然后用一階謂詞演算的推理系統(tǒng)來(lái)解決實(shí)際中所遇到的問題，這是解決Web服務(wù)組合應(yīng)用的在理論上的一個(gè)可行的辦法。因?yàn)樵谶壿嬛?，用戶總是?duì)目標(biāo)加以詢問，而對(duì)這樣一個(gè)詢問的回答是構(gòu)造一個(gè)能夠到達(dá)期望狀態(tài)的計(jì)劃或組合，和現(xiàn)實(shí)中用戶對(duì)其期望服務(wù)產(chǎn)品的詢問過程是很類似的。

在情景演算中，定義“流”表示那些和某個(gè)特定狀態(tài)s相關(guān)聯(lián)的函數(shù)以及關(guān)系這樣的原子合式公式，世界的狀態(tài)則可以表示為這種謂詞流的值。流F（x,s）以狀態(tài)s為它的最后一個(gè)參數(shù)。狀態(tài)s是一系列原子行為，且從某個(gè)特定的初始狀態(tài)S0開始執(zhí)行的一個(gè)歷史序列。常量S0表示初始狀態(tài) （initial situation），即在此狀態(tài)下沒有任何行為發(fā)生，為流的初值。函數(shù)do(a,s)將狀態(tài)和行為映射到一個(gè)新的狀態(tài)，表示在狀態(tài)s下執(zhí)行a的后續(xù)狀態(tài)（successor situation）。行為本身可以參數(shù)化，例如put(x,y)指代行為：把x物體放在y物體上，進(jìn)而do(put(A,B),s)就表示了在世界的狀態(tài)為s下時(shí)，將A置于B上所產(chǎn)生的新的狀態(tài)。

用以表示變化情景一系列過程的情景演算，作為一套完整的一階邏輯公式，其基本要素在于行為、流和狀態(tài)。論域則由一系列公式規(guī)定，規(guī)定如下：

·對(duì)于每一個(gè)行為都有一個(gè)行為前提公理；

·對(duì)每一個(gè)流都有一個(gè)后續(xù)狀態(tài)公理；

·公理可以在各種各樣的狀態(tài)下對(duì)世界加以描述；

·存在基本定理，該定理可以與研究領(lǐng)域無(wú)關(guān)。

2.1 情景演算理論

為刻畫動(dòng)態(tài)變化的世界，狀態(tài)演算的行為理論D包含初始狀態(tài)公理 （initial situation axiom）、行為前提公理（action precondition axiom）、后續(xù)狀態(tài)公理（successor state axiom）、唯一命名公理（unique names axiom）等，其形式化定義如之后內(nèi)容所述[5]。

2.1.1 定義形式的行為前提公理

假設(shè)情景演算語(yǔ)言Lsitcalc(language of situation calculus)中含有有限多個(gè)函數(shù)符A1,…,An，則一定有有限多個(gè)行為前提公理，如式（1）所示：

其中，Poss(a,s)(possible)是一個(gè)特殊的流，表示行為a在狀態(tài)s下是可執(zhí)行的?！鞘切袨榭蓤?zhí)行的所有前提條件，例如 表示在狀態(tài)s下，若存在拿著 o的前提條件，drop(o)行為就可以執(zhí)行；再如表示如果pickup(o)這樣的行為在狀態(tài)s下能夠執(zhí)行，則物體o一定沒有被拿著，并且在行為執(zhí)行者的承重范圍之內(nèi)。

按照 Lloyd-Topor的標(biāo)準(zhǔn)形式定義 Poss(a,s)，如式（2）所示：

2.1.2 后續(xù)狀態(tài)公理下“流”的定義

在合適的初始數(shù)據(jù)庫(kù)條件下，對(duì)于關(guān)系流F，后續(xù)狀態(tài)公理可以由F的定義式或推論式告知。

下面把F當(dāng)作擁有后續(xù)狀態(tài)定理Dss的一個(gè)關(guān)系流：

進(jìn)一步而言，DS0是一個(gè)封閉初始數(shù)據(jù)庫(kù)，所以其包含了一個(gè)F的基本公理：

則式（5）就是F的定義形式：

2.1.3 行為理論定義

在情景演算語(yǔ)言Lsitcalc中，允許D成為一個(gè)基本行為理論，則有如下性質(zhì)。

·Lsitcalc沒有函數(shù)謂詞流，而僅含有有限多個(gè)關(guān)系流和函數(shù)符。

·DS0是其閉包形式。在關(guān)系流的相等條件全部移除的情況下讓成為 DS0，則由Lsitcalc中所有非流形

式的謂詞符號(hào)和唯一確定的命名公理構(gòu)成。

·Dunsit在基本定理狀態(tài)下由兩個(gè)唯一的命名公理構(gòu)成，也即：S0≠do(a,s)，連同模式中所有的例子，t[s]≠s表示對(duì)于每個(gè)分類狀態(tài)中不同于s自身的專有名詞都提及狀態(tài)變量s。

進(jìn)而每當(dāng)G成為L(zhǎng)sitcalc中的可回溯語(yǔ)句(regressable sentence)時(shí)，式（6）成立，定義情景演算語(yǔ)言的行為理論 D，如式（6）所示：

其中， 是正效果公理，描述了相關(guān)的行為和條件集合，使得流F的值在a執(zhí)行后為真； 是負(fù)效果公理，描述了相關(guān)的行為和條件集合，使得流F的值在a執(zhí)行后為假。

Duna表示行為的唯一命名公理；Dunsit表示基礎(chǔ)的、領(lǐng)域無(wú)關(guān)的公理；例如，有 3個(gè)行為 pickup(x)、putdown(x)和drop(x)以及 3 個(gè)流變量 holding(x)、putdown(x)和 hot(x)。

2.2 情景演算理論應(yīng)用

行為前提公理相當(dāng)于存在于情景演算中的知識(shí)描述，因此對(duì)于Web服務(wù)上的各種原子服務(wù)需要先行加以描述，將其存放于事實(shí)數(shù)據(jù)庫(kù)中，再根據(jù)其推理機(jī)制不斷產(chǎn)生后續(xù)狀態(tài)。例如，用戶想要購(gòu)買一張旅游飛機(jī)票，就會(huì)對(duì)應(yīng)一種原子行為BuyAirTicket(ticketName)，如果機(jī)場(chǎng)的飛機(jī)票仍有剩余，也就是說可以滿足用戶的消費(fèi)請(qǐng)求，則執(zhí)行結(jié)果是可使用戶得到這張飛機(jī)票，對(duì)應(yīng)BuyAirTicket(ticketName)生效，流 F為 Own(ticketName)。此時(shí)，正效果公理作用于流

相反的，在機(jī)場(chǎng)方的立場(chǎng)上，相應(yīng)的售票過程則產(chǎn)生了一個(gè)負(fù)效果公，作用于流F，此時(shí)流F的作用結(jié)果為

最終，通過不斷的推理產(chǎn)生了一系列的行為序列 ，這恰恰是研究過程中最需要得到的。因此，選用情景演算及其語(yǔ)言在Web服務(wù)中可為用戶帶來(lái)極大的方便。

2.3 Prolog的應(yīng)用

Prolog沒有特定的運(yùn)行順序，沒有明顯的控制語(yǔ)句，它不同于C語(yǔ)言等面向過程的編程語(yǔ)言以及C++等面向?qū)ο蟮木幊陶Z(yǔ)言的數(shù)據(jù)獨(dú)立于程序的做法，Prolog僅僅存在變量和常量，只要匹配綁定就可以繼續(xù)執(zhí)行程序。其精髓之處就在于有類似人腦的全面求解和強(qiáng)大遞歸功能，會(huì)窮盡自己的搜索和遞歸本領(lǐng)給出各種詳盡的答案。

一個(gè)基本的Prolog程序由4部分組成[6]：論域、謂詞、子句以及目標(biāo)。論域段用來(lái)命名，有助于定義謂詞的文檔化。此外還可聲明標(biāo)準(zhǔn)論域中未定義的數(shù)據(jù)結(jié)構(gòu)等內(nèi)容；謂詞段相當(dāng)于普通編程語(yǔ)言中的函數(shù)聲明。謂詞定義中的語(yǔ)句用來(lái)聲明所謂函數(shù)名及其參數(shù)的論域；子句段是Prolog程序的核心，放置事實(shí)數(shù)據(jù)和規(guī)則描述，相當(dāng)于普通編程語(yǔ)言中的函數(shù)體。目標(biāo)程序會(huì)對(duì)其進(jìn)行操作，用以得出滿足程序條件的目標(biāo)；目標(biāo)段可以理解成C語(yǔ)言中的main()函數(shù)。其間放置的是Visual Prolog程序的開始目標(biāo)或聯(lián)系到Web服務(wù)中用戶的需求。如果這個(gè)段里的所有子目標(biāo)全部成功，則程序成功終止，反之失敗。

Prolog作為邏輯推理語(yǔ)言，其原理建立于一階邏輯之上，采用情景演算理論，對(duì)世界的事物和行為加以描述。下面考慮一個(gè)實(shí)例，考慮一個(gè)對(duì)于家庭關(guān)系的一階邏輯理論：

根據(jù)Lloyd-Topor的標(biāo)準(zhǔn)化形式進(jìn)行簡(jiǎn)單地推導(dǎo)以及對(duì)事實(shí)數(shù)據(jù)用謂詞加以描述，形成事實(shí)數(shù)據(jù)庫(kù)，則有：

對(duì)于這樣的式子，不難采用上述的謂詞描述理論，將其實(shí)現(xiàn)在Prolog中：

至此的工作并沒有得到延伸，由情景演算中的各種一階邏輯定理以及公式的匹配情況發(fā)現(xiàn)，在Prolog Interpreter之上擴(kuò)展的Golog系列是能夠勝任的，而用Prolog語(yǔ)言是可以編寫出用戶所想要的各種描述。綜上所述，在本課題中，用戶需要的只是掌握情景演算的理論，將所要表述的各種服務(wù)以及其推理過程用情景演算語(yǔ)言加以概括，Golog上只需要再描述就能達(dá)到所要的目標(biāo)。

3 基于推理機(jī)制的Golog語(yǔ)言

Golog[7]主要用于機(jī)器人的高階編程、軟件agent高階編程、過程階段控制、程序控制、離散事件模擬、復(fù)雜數(shù)據(jù)及數(shù)據(jù)庫(kù)處理等復(fù)雜的場(chǎng)合。Golog語(yǔ)言可以描述機(jī)器人或agent的能力、環(huán)境并允許對(duì)其行為進(jìn)行推理和決策，可以表示例如行為的前提和結(jié)果，其他能夠產(chǎn)生知識(shí)的行為、其他agent的動(dòng)作以及自然事件等，并對(duì)其進(jìn)行推理。Golog是基于Prolog編譯環(huán)境的一種擴(kuò)展，由Golog_swi.pl中的謂詞流定義完成。

對(duì)于情景演算中的復(fù)雜程序，主要討論用一些擴(kuò)充的邏輯符號(hào)（例如while、if等）作為邏輯表達(dá)語(yǔ)言的縮寫來(lái)定義復(fù)雜行為表達(dá)。這些邏輯表達(dá)應(yīng)當(dāng)理解為在情景演算中擴(kuò)充其理論的公式。下面定，δ是一個(gè)復(fù)雜行為的表述。直覺上，根據(jù)情景演算中的介紹，會(huì)擴(kuò)充到一個(gè)情景演算公式中，說明執(zhí)行一系列δ所規(guī)定的行為會(huì)將世界的狀態(tài)從s改變到s′。因?yàn)閺?fù)雜行為是不確定的，也就是說會(huì)有各種各樣的執(zhí)行結(jié)果以及狀態(tài)終結(jié)。下面給出一些具體例子。

開車出游：走向自己的車，進(jìn)入車內(nèi)，開動(dòng)車，行駛到山東，這一系列行為可表示為

將桌上的所有東西都放到地板上：

編譯器預(yù)先假定了一個(gè)背景基本行為理論，采用了合適的Prolog語(yǔ)句加以描述?？梢钥吹降氖?，對(duì)于各種程序的Golog求解方案實(shí)際上都是在證明可回溯語(yǔ)句，即可以表述為，在一個(gè)準(zhǔn)確的Prolog工具上，Golog總是確定Prolog子句以及其背景行為理論的。在Prolog環(huán)境下做如下假設(shè)：

·Lsitcalc沒有函數(shù)流，而且只含有有限多個(gè)關(guān)系流和行為函數(shù)符號(hào)；

·基本行為理論有一個(gè)閉包初始化數(shù)據(jù)庫(kù)DS0，也即DS0提供了一系列合適的唯一命名公理；DS0為每一個(gè)非流謂詞符提供了一個(gè)定義；對(duì)于每一個(gè)關(guān)系流提供了一個(gè)關(guān)系 。

在如上所述的假設(shè)的支持下，經(jīng)過Lloyd-Topor變形公式的推導(dǎo)轉(zhuǎn)換后就有了一個(gè)正確的Golog環(huán)境。

在此對(duì)購(gòu)買飛機(jī)票的問題給出一些復(fù)雜的可能。

因?yàn)樵趯?shí)際的程序執(zhí)行過程中，不會(huì)總是給出真假值，更可能的情況是將輸出轉(zhuǎn)化為謂詞的形式，產(chǎn)生一種類似于知識(shí)的結(jié)果（這樣更符合人腦推理時(shí)的特性）或者輸出一系列程序執(zhí)行后所產(chǎn)生的信息集合。

回到購(gòu)買飛機(jī)票的過程，假設(shè)有一個(gè)新的原子行為叫做定位機(jī)票LocateAirTicket，表示在機(jī)場(chǎng)方出售機(jī)票之前查找定位用戶所需要的航班線路，則其行為的執(zhí)行結(jié)果（如果為正效果）則是機(jī)票的價(jià)格已知，此時(shí)正效果公理為：則有，

。

再給出一個(gè)后續(xù)狀態(tài)公理的實(shí)例，例如這位用戶擁有了這張飛機(jī)票，那么粗略地想，只有兩種可能，一是他購(gòu)買了這張機(jī)票且機(jī)票有庫(kù)存；二是他本來(lái)就擁有這張機(jī)票（不考慮具體得到方式），且他不想退票，用下式以描述他的擁有飛機(jī)票的這個(gè)行為：

這里，給出一種猜想，目前正在證實(shí)階段。

推論1 Golog中后續(xù)狀態(tài)公理的應(yīng)用定式：

這表示流在狀態(tài)do(a,s)當(dāng)且僅當(dāng)執(zhí)行使其正效果公理

或在其已經(jīng)為真的時(shí)候不執(zhí)行負(fù)效果公理。

下面繼續(xù)說明行為前提公理的表述實(shí)例。以下為有多個(gè)前提條件的行為前提公理定義式：

那么，比如購(gòu)買飛機(jī)票的原子行為前提條件在于用戶的信用卡、賬號(hào)等信息都是存在且可用的，則下述對(duì)應(yīng)關(guān)系成立：

如果說正負(fù)效果公理中的輸出過程會(huì)產(chǎn)生一個(gè)知識(shí)性結(jié)果，那么輸入過程則是知識(shí)性前提。可以想象，在一個(gè)行為執(zhí)行之前，各類參數(shù)的值是一定會(huì)被知曉的，例如在購(gòu)票過程中：

這是很容易被理解的。

下面的推論可以被簡(jiǎn)單證明。

推論3 Golog中對(duì)行為前提公理的描述為：

是符合人類生活習(xí)慣

4 結(jié)束語(yǔ)

經(jīng)過從復(fù)習(xí)離散數(shù)學(xué)到學(xué)習(xí)情景演算理論，從下載Prolog編譯環(huán)境到Golog的一般推論，本課題中關(guān)于邏輯部分上的研究已初見成效。在許多理論上的例子和情景演算中的式子可以被稍加變化應(yīng)用在計(jì)算機(jī)語(yǔ)言中，的確是非常令人欣慰的事。本文對(duì)于Prolog語(yǔ)言能夠在Web服務(wù)中應(yīng)用做了詳細(xì)闡述，毫無(wú)疑問地證明了其可行性，而Golog推理理論的提出同時(shí)也提示了研究下一步的方向。

Web組合服務(wù)的初衷是美好的，是能夠滿足人們需求且最終能被廣泛使用的，而語(yǔ)義Web對(duì)計(jì)算機(jī)的發(fā)展更是大有裨益。但由于時(shí)間的原因，這部分的工作仍然處于未完成階段，例如Golog中的推理過程描述以及后續(xù)過程中程序的拼接、平臺(tái)與平臺(tái)之間的相互適應(yīng)，還有更多的問題值得去研究和討論。

1 梁晟．基于語(yǔ)義Web的服務(wù)自動(dòng)組合技術(shù)研究．中國(guó)科學(xué)院軟件研究所博士學(xué)位論文，2004

2 袁書?。赪eb的自動(dòng)組合服務(wù)框架的研究．華東師范大學(xué)碩士學(xué)位論文，2008

3 雷英杰，張雷，邢清華等．Visual Prolog語(yǔ)言教程．西安：陜西科學(xué)技術(shù)出版社，2004

4 MedjahedB，Bougueltaya A，ElmagarmidA.Composingweb services on the semantic web．The VLDB Journal,2003,12（4）

5 Reiter R.Knowledge in Action:LogicalFoundations for Describing and Implementing Dynamical Systems.MIT Press,2001

6 Brna P.Prolog Programming:A First Course.http://comp.mq.edu.au/units/comp248/resources/brna-prolog-book.pdf,2001

7 Slormeger K，Kurtz B L．Syntax and Semantics of Programming Languages．New York：Addison Wesley，1995

8 Mitola J，Maguire G Q．Cognitive radio:making software radios more personal．IEEE Personal Communication，1999，6（4）

9 邢星．語(yǔ)義Web服務(wù)自動(dòng)組合方法研究．大連海事大學(xué)碩士學(xué)位論文，2008

10 楊紅蘭．自動(dòng)組合服務(wù)框架的研究和設(shè)計(jì)．電腦知識(shí)與技術(shù)，2007（16）

11 Wohed P，Wil M P，Marion D，et al．Analysis of web services composition languages：the case of BPEL4WS.Proceedings of the 22nd International Conference on Conceptual Modelling （ER）,Springer,Chicago IL,USA,2003:200～215