基于推理機制的邏輯語言在Web服務組合機制中的應用

趙瑩映，章 韻

（南京郵電大學計算機學院 南京 210003）

1 引言

隨著人們日益提升的網絡需求，加上WWW自身發展的重要導向，一個新興的課題——語義Web及其自動組合服務應運而生，Web服務這樣一種第三產業的衍生物，毫無爭議地成為眼下新晉的研究課題之一。Web服務組合管理關鍵技術的目標就是讓網絡協議規范化、服務項目原子化、服務內容組合化。語義Web服務組合作為一種能夠快速提供復雜型組合服務的方法近年來得到廣泛關注，同時為了達到上述目的，對其進一步的研究是必不可少的，而如何提高服務組合的可用性和實際性則成為Web服務組合管理中必備的組成部分和亟待解決的關鍵問題。

所謂Web服務[1,2]，是指一個應用程序能夠給外界提供一個通過Web進行調用的API，即用戶可以通過簡單方式向Web發送請求，讓Web調用其應用程序，等待查看返回結果。基于語義的Web自動組合服務，是指用一種或多種語義標記語言描述服務提供者提供的各個原子服務，使其成為可被計算機或服務器理解的知識，進而通過情景演算推理機制，使得計算機可針對用戶的需求發現知識并對其加以重組，以此產生一系列組合形式的服務回饋用戶。

Prolog[3]（programming in logic），即人們通常所說的人工智能語言，是一種建立于邏輯學理論基礎之上的邏輯編程語言，其最重要的應用在于自然語言的理解以及智能知識庫的構建，它采用一些代替邏輯語言的符號表示程序的內容，因此具有相對較快的編程速度。平臺無關性讓Prolog程序的應用范圍更廣，更能夠滿足編寫者的需求。在Web服務的研究過程中，原子服務的描述是一個不容忽視的問題，因為會影響到推理階段的質量。而Prolog較強的遞歸功能和內部事實數據庫功能可以勝任這項工作，下文所要提到的擴展后的Golog系列應用都能證明選用這類語言可以解決在研究中遇到的諸多問題。

2 Prolog下的情景演算理論

情景演算[4]適用于描述動態變化的世界，是一種關于狀態、行為和行為作用于狀態的結果的形式化謂詞演算。由一系列行為構成的一種可能的世界歷史，以一種一階專有詞語狀態來表示。

預先把知識表達為關于狀態和行為的公式，然后用一階謂詞演算的推理系統來解決實際中所遇到的問題，這是解決Web服務組合應用的在理論上的一個可行的辦法。因為在邏輯中，用戶總是對目標加以詢問，而對這樣一個詢問的回答是構造一個能夠到達期望狀態的計劃或組合，和現實中用戶對其期望服務產品的詢問過程是很類似的。

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

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

·對于每一個行為都有一個行為前提公理；

·對每一個流都有一個后續狀態公理；

·公理可以在各種各樣的狀態下對世界加以描述；

·存在基本定理，該定理可以與研究領域無關。

2.1 情景演算理論

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

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

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

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

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

2.1.2 后續狀態公理下“流”的定義

在合適的初始數據庫條件下，對于關系流F，后續狀態公理可以由F的定義式或推論式告知。

下面把F當作擁有后續狀態定理Dss的一個關系流：

進一步而言，DS0是一個封閉初始數據庫，所以其包含了一個F的基本公理：

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

2.1.3 行為理論定義

在情景演算語言Lsitcalc中，允許D成為一個基本行為理論，則有如下性質。

·Lsitcalc沒有函數謂詞流，而僅含有有限多個關系流和函數符。

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

式的謂詞符號和唯一確定的命名公理構成。

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

進而每當G成為Lsitcalc中的可回溯語句(regressable sentence)時，式（6）成立，定義情景演算語言的行為理論 D，如式（6）所示：

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

Duna表示行為的唯一命名公理；Dunsit表示基礎的、領域無關的公理；例如，有 3個行為 pickup(x)、putdown(x)和drop(x)以及 3 個流變量 holding(x)、putdown(x)和 hot(x)。

2.2 情景演算理論應用

行為前提公理相當于存在于情景演算中的知識描述，因此對于Web服務上的各種原子服務需要先行加以描述，將其存放于事實數據庫中，再根據其推理機制不斷產生后續狀態。例如，用戶想要購買一張旅游飛機票，就會對應一種原子行為BuyAirTicket(ticketName)，如果機場的飛機票仍有剩余，也就是說可以滿足用戶的消費請求，則執行結果是可使用戶得到這張飛機票，對應BuyAirTicket(ticketName)生效，流 F為 Own(ticketName)。此時，正效果公理作用于流

相反的，在機場方的立場上，相應的售票過程則產生了一個負效果公，作用于流F，此時流F的作用結果為

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

2.3 Prolog的應用

Prolog沒有特定的運行順序，沒有明顯的控制語句，它不同于C語言等面向過程的編程語言以及C++等面向對象的編程語言的數據獨立于程序的做法，Prolog僅僅存在變量和常量，只要匹配綁定就可以繼續執行程序。其精髓之處就在于有類似人腦的全面求解和強大遞歸功能，會窮盡自己的搜索和遞歸本領給出各種詳盡的答案。

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

Prolog作為邏輯推理語言，其原理建立于一階邏輯之上，采用情景演算理論，對世界的事物和行為加以描述。下面考慮一個實例，考慮一個對于家庭關系的一階邏輯理論：

根據Lloyd-Topor的標準化形式進行簡單地推導以及對事實數據用謂詞加以描述，形成事實數據庫，則有：

對于這樣的式子，不難采用上述的謂詞描述理論，將其實現在Prolog中：

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

3 基于推理機制的Golog語言

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

對于情景演算中的復雜程序，主要討論用一些擴充的邏輯符號（例如while、if等）作為邏輯表達語言的縮寫來定義復雜行為表達。這些邏輯表達應當理解為在情景演算中擴充其理論的公式。下面定，δ是一個復雜行為的表述。直覺上，根據情景演算中的介紹，會擴充到一個情景演算公式中，說明執行一系列δ所規定的行為會將世界的狀態從s改變到s′。因為復雜行為是不確定的，也就是說會有各種各樣的執行結果以及狀態終結。下面給出一些具體例子。

開車出游：走向自己的車，進入車內，開動車，行駛到山東，這一系列行為可表示為

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

編譯器預先假定了一個背景基本行為理論，采用了合適的Prolog語句加以描述?？梢钥吹降氖牵瑢τ诟鞣N程序的Golog求解方案實際上都是在證明可回溯語句，即可以表述為，在一個準確的Prolog工具上，Golog總是確定Prolog子句以及其背景行為理論的。在Prolog環境下做如下假設：

·Lsitcalc沒有函數流，而且只含有有限多個關系流和行為函數符號；

·基本行為理論有一個閉包初始化數據庫DS0，也即DS0提供了一系列合適的唯一命名公理；DS0為每一個非流謂詞符提供了一個定義；對于每一個關系流提供了一個關系 。

在如上所述的假設的支持下，經過Lloyd-Topor變形公式的推導轉換后就有了一個正確的Golog環境。

在此對購買飛機票的問題給出一些復雜的可能。

因為在實際的程序執行過程中，不會總是給出真假值，更可能的情況是將輸出轉化為謂詞的形式，產生一種類似于知識的結果（這樣更符合人腦推理時的特性）或者輸出一系列程序執行后所產生的信息集合。

回到購買飛機票的過程，假設有一個新的原子行為叫做定位機票LocateAirTicket，表示在機場方出售機票之前查找定位用戶所需要的航班線路，則其行為的執行結果（如果為正效果）則是機票的價格已知，此時正效果公理為：則有，

。

再給出一個后續狀態公理的實例，例如這位用戶擁有了這張飛機票，那么粗略地想，只有兩種可能，一是他購買了這張機票且機票有庫存；二是他本來就擁有這張機票（不考慮具體得到方式），且他不想退票，用下式以描述他的擁有飛機票的這個行為：

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

推論1 Golog中后續狀態公理的應用定式：

這表示流在狀態do(a,s)當且僅當執行使其正效果公理

或在其已經為真的時候不執行負效果公理。

下面繼續說明行為前提公理的表述實例。以下為有多個前提條件的行為前提公理定義式：

那么，比如購買飛機票的原子行為前提條件在于用戶的信用卡、賬號等信息都是存在且可用的，則下述對應關系成立：

如果說正負效果公理中的輸出過程會產生一個知識性結果，那么輸入過程則是知識性前提。可以想象，在一個行為執行之前，各類參數的值是一定會被知曉的，例如在購票過程中：

這是很容易被理解的。

下面的推論可以被簡單證明。

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

是符合人類生活習慣

4 結束語

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

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

1 梁晟．基于語義Web的服務自動組合技術研究．中國科學院軟件研究所博士學位論文，2004

2 袁書?。赪eb的自動組合服務框架的研究．華東師范大學碩士學位論文，2008

3 雷英杰，張雷，邢清華等．Visual Prolog語言教程．西安：陜西科學技術出版社，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 邢星．語義Web服務自動組合方法研究．大連海事大學碩士學位論文，2008

10 楊紅蘭．自動組合服務框架的研究和設計．電腦知識與技術，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