趙瑩映,章 韻
(南京郵電大學(xué)計算機(jī)學(xué)院 南京 210003)
隨著人們?nèi)找嫣嵘木W(wǎng)絡(luò)需求,加上WWW自身發(fā)展的重要導(dǎo)向,一個新興的課題——語義Web及其自動組合服務(wù)應(yīng)運而生,Web服務(wù)這樣一種第三產(chǎn)業(yè)的衍生物,毫無爭議地成為眼下新晉的研究課題之一。Web服務(wù)組合管理關(guān)鍵技術(shù)的目標(biāo)就是讓網(wǎng)絡(luò)協(xié)議規(guī)范化、服務(wù)項目原子化、服務(wù)內(nèi)容組合化。語義Web服務(wù)組合作為一種能夠快速提供復(fù)雜型組合服務(wù)的方法近年來得到廣泛關(guān)注,同時為了達(dá)到上述目的,對其進(jìn)一步的研究是必不可少的,而如何提高服務(wù)組合的可用性和實際性則成為Web服務(wù)組合管理中必備的組成部分和亟待解決的關(guān)鍵問題。
所謂Web服務(wù)[1,2],是指一個應(yīng)用程序能夠給外界提供一個通過Web進(jìn)行調(diào)用的API,即用戶可以通過簡單方式向Web發(fā)送請求,讓W(xué)eb調(diào)用其應(yīng)用程序,等待查看返回結(jié)果?;谡Z義的Web自動組合服務(wù),是指用一種或多種語義標(biāo)記語言描述服務(wù)提供者提供的各個原子服務(wù),使其成為可被計算機(jī)或服務(wù)器理解的知識,進(jìn)而通過情景演算推理機(jī)制,使得計算機(jī)可針對用戶的需求發(fā)現(xiàn)知識并對其加以重組,以此產(chǎn)生一系列組合形式的服務(wù)回饋用戶。
Prolog[3](programming in logic),即人們通常所說的人工智能語言,是一種建立于邏輯學(xué)理論基礎(chǔ)之上的邏輯編程語言,其最重要的應(yīng)用在于自然語言的理解以及智能知識庫的構(gòu)建,它采用一些代替邏輯語言的符號表示程序的內(nèi)容,因此具有相對較快的編程速度。平臺無關(guān)性讓Prolog程序的應(yīng)用范圍更廣,更能夠滿足編寫者的需求。在Web服務(wù)的研究過程中,原子服務(wù)的描述是一個不容忽視的問題,因為會影響到推理階段的質(zhì)量。而Prolog較強(qiáng)的遞歸功能和內(nèi)部事實數(shù)據(jù)庫功能可以勝任這項工作,下文所要提到的擴(kuò)展后的Golog系列應(yīng)用都能證明選用這類語言可以解決在研究中遇到的諸多問題。
情景演算[4]適用于描述動態(tài)變化的世界,是一種關(guān)于狀態(tài)、行為和行為作用于狀態(tài)的結(jié)果的形式化謂詞演算。由一系列行為構(gòu)成的一種可能的世界歷史,以一種一階專有詞語狀態(tài)來表示。
預(yù)先把知識表達(dá)為關(guān)于狀態(tài)和行為的公式,然后用一階謂詞演算的推理系統(tǒng)來解決實際中所遇到的問題,這是解決Web服務(wù)組合應(yīng)用的在理論上的一個可行的辦法。因為在邏輯中,用戶總是對目標(biāo)加以詢問,而對這樣一個詢問的回答是構(gòu)造一個能夠到達(dá)期望狀態(tài)的計劃或組合,和現(xiàn)實中用戶對其期望服務(wù)產(chǎn)品的詢問過程是很類似的。
在情景演算中,定義“流”表示那些和某個特定狀態(tài)s相關(guān)聯(lián)的函數(shù)以及關(guān)系這樣的原子合式公式,世界的狀態(tài)則可以表示為這種謂詞流的值。流F(x,s)以狀態(tài)s為它的最后一個參數(shù)。狀態(tài)s是一系列原子行為,且從某個特定的初始狀態(tài)S0開始執(zhí)行的一個歷史序列。常量S0表示初始狀態(tài) (initial situation),即在此狀態(tài)下沒有任何行為發(fā)生,為流的初值。函數(shù)do(a,s)將狀態(tài)和行為映射到一個新的狀態(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下時,將A置于B上所產(chǎn)生的新的狀態(tài)。
用以表示變化情景一系列過程的情景演算,作為一套完整的一階邏輯公式,其基本要素在于行為、流和狀態(tài)。論域則由一系列公式規(guī)定,規(guī)定如下:
·對于每一個行為都有一個行為前提公理;
·對每一個流都有一個后續(xù)狀態(tài)公理;
·公理可以在各種各樣的狀態(tài)下對世界加以描述;
·存在基本定理,該定理可以與研究領(lǐng)域無關(guān)。
為刻畫動態(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è)情景演算語言Lsitcalc(language of situation calculus)中含有有限多個函數(shù)符A1,…,An,則一定有有限多個行為前提公理,如式(1)所示:
其中,Poss(a,s)(possible)是一個特殊的流,表示行為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ù)庫條件下,對于關(guān)系流F,后續(xù)狀態(tài)公理可以由F的定義式或推論式告知。
下面把F當(dāng)作擁有后續(xù)狀態(tài)定理Dss的一個關(guān)系流:
進(jìn)一步而言,DS0是一個封閉初始數(shù)據(jù)庫,所以其包含了一個F的基本公理:
則式(5)就是F的定義形式:
2.1.3 行為理論定義
在情景演算語言Lsitcalc中,允許D成為一個基本行為理論,則有如下性質(zhì)。
·Lsitcalc沒有函數(shù)謂詞流,而僅含有有限多個關(guān)系流和函數(shù)符。
·DS0是其閉包形式。在關(guān)系流的相等條件全部移除的情況下讓成為 DS0,則由Lsitcalc中所有非流形
式的謂詞符號和唯一確定的命名公理構(gòu)成。
·Dunsit在基本定理狀態(tài)下由兩個唯一的命名公理構(gòu)成,也即:S0≠do(a,s),連同模式中所有的例子,t[s]≠s表示對于每個分類狀態(tài)中不同于s自身的專有名詞都提及狀態(tài)變量s。
進(jìn)而每當(dāng)G成為Lsitcalc中的可回溯語句(regressable sentence)時,式(6)成立,定義情景演算語言的行為理論 D,如式(6)所示:
其中, 是正效果公理,描述了相關(guān)的行為和條件集合,使得流F的值在a執(zhí)行后為真; 是負(fù)效果公理,描述了相關(guān)的行為和條件集合,使得流F的值在a執(zhí)行后為假。
Duna表示行為的唯一命名公理;Dunsit表示基礎(chǔ)的、領(lǐng)域無關(guān)的公理;例如,有 3個行為 pickup(x)、putdown(x)和drop(x)以及 3 個流變量 holding(x)、putdown(x)和 hot(x)。
行為前提公理相當(dāng)于存在于情景演算中的知識描述,因此對于Web服務(wù)上的各種原子服務(wù)需要先行加以描述,將其存放于事實數(shù)據(jù)庫中,再根據(jù)其推理機(jī)制不斷產(chǎn)生后續(xù)狀態(tài)。例如,用戶想要購買一張旅游飛機(jī)票,就會對應(yīng)一種原子行為BuyAirTicket(ticketName),如果機(jī)場的飛機(jī)票仍有剩余,也就是說可以滿足用戶的消費請求,則執(zhí)行結(jié)果是可使用戶得到這張飛機(jī)票,對應(yīng)BuyAirTicket(ticketName)生效,流 F為 Own(ticketName)。此時,正效果公理作用于流
相反的,在機(jī)場方的立場上,相應(yīng)的售票過程則產(chǎn)生了一個負(fù)效果公,作用于流F,此時流F的作用結(jié)果為
最終,通過不斷的推理產(chǎn)生了一系列的行為序列 ,這恰恰是研究過程中最需要得到的。因此,選用情景演算及其語言在Web服務(wù)中可為用戶帶來極大的方便。
Prolog沒有特定的運行順序,沒有明顯的控制語句,它不同于C語言等面向過程的編程語言以及C++等面向?qū)ο蟮木幊陶Z言的數(shù)據(jù)獨立于程序的做法,Prolog僅僅存在變量和常量,只要匹配綁定就可以繼續(xù)執(zhí)行程序。其精髓之處就在于有類似人腦的全面求解和強(qiáng)大遞歸功能,會窮盡自己的搜索和遞歸本領(lǐng)給出各種詳盡的答案。
一個基本的Prolog程序由4部分組成[6]:論域、謂詞、子句以及目標(biāo)。論域段用來命名,有助于定義謂詞的文檔化。此外還可聲明標(biāo)準(zhǔn)論域中未定義的數(shù)據(jù)結(jié)構(gòu)等內(nèi)容;謂詞段相當(dāng)于普通編程語言中的函數(shù)聲明。謂詞定義中的語句用來聲明所謂函數(shù)名及其參數(shù)的論域;子句段是Prolog程序的核心,放置事實數(shù)據(jù)和規(guī)則描述,相當(dāng)于普通編程語言中的函數(shù)體。目標(biāo)程序會對其進(jìn)行操作,用以得出滿足程序條件的目標(biāo);目標(biāo)段可以理解成C語言中的main()函數(shù)。其間放置的是Visual Prolog程序的開始目標(biāo)或聯(lián)系到Web服務(wù)中用戶的需求。如果這個段里的所有子目標(biāo)全部成功,則程序成功終止,反之失敗。
Prolog作為邏輯推理語言,其原理建立于一階邏輯之上,采用情景演算理論,對世界的事物和行為加以描述。下面考慮一個實例,考慮一個對于家庭關(guān)系的一階邏輯理論:
根據(jù)Lloyd-Topor的標(biāo)準(zhǔn)化形式進(jìn)行簡單地推導(dǎo)以及對事實數(shù)據(jù)用謂詞加以描述,形成事實數(shù)據(jù)庫,則有:
對于這樣的式子,不難采用上述的謂詞描述理論,將其實現(xiàn)在Prolog中:
至此的工作并沒有得到延伸,由情景演算中的各種一階邏輯定理以及公式的匹配情況發(fā)現(xiàn),在Prolog Interpreter之上擴(kuò)展的Golog系列是能夠勝任的,而用Prolog語言是可以編寫出用戶所想要的各種描述。綜上所述,在本課題中,用戶需要的只是掌握情景演算的理論,將所要表述的各種服務(wù)以及其推理過程用情景演算語言加以概括,Golog上只需要再描述就能達(dá)到所要的目標(biāo)。
Golog[7]主要用于機(jī)器人的高階編程、軟件agent高階編程、過程階段控制、程序控制、離散事件模擬、復(fù)雜數(shù)據(jù)及數(shù)據(jù)庫處理等復(fù)雜的場合。Golog語言可以描述機(jī)器人或agent的能力、環(huán)境并允許對其行為進(jìn)行推理和決策,可以表示例如行為的前提和結(jié)果,其他能夠產(chǎn)生知識的行為、其他agent的動作以及自然事件等,并對其進(jìn)行推理。Golog是基于Prolog編譯環(huán)境的一種擴(kuò)展,由Golog_swi.pl中的謂詞流定義完成。
對于情景演算中的復(fù)雜程序,主要討論用一些擴(kuò)充的邏輯符號(例如while、if等)作為邏輯表達(dá)語言的縮寫來定義復(fù)雜行為表達(dá)。這些邏輯表達(dá)應(yīng)當(dāng)理解為在情景演算中擴(kuò)充其理論的公式。下面定,δ是一個復(fù)雜行為的表述。直覺上,根據(jù)情景演算中的介紹,會擴(kuò)充到一個情景演算公式中,說明執(zhí)行一系列δ所規(guī)定的行為會將世界的狀態(tài)從s改變到s′。因為復(fù)雜行為是不確定的,也就是說會有各種各樣的執(zhí)行結(jié)果以及狀態(tài)終結(jié)。下面給出一些具體例子。
開車出游:走向自己的車,進(jìn)入車內(nèi),開動車,行駛到山東,這一系列行為可表示為
將桌上的所有東西都放到地板上:
編譯器預(yù)先假定了一個背景基本行為理論,采用了合適的Prolog語句加以描述??梢钥吹降氖?,對于各種程序的Golog求解方案實際上都是在證明可回溯語句,即可以表述為,在一個準(zhǔn)確的Prolog工具上,Golog總是確定Prolog子句以及其背景行為理論的。在Prolog環(huán)境下做如下假設(shè):
·Lsitcalc沒有函數(shù)流,而且只含有有限多個關(guān)系流和行為函數(shù)符號;
·基本行為理論有一個閉包初始化數(shù)據(jù)庫DS0,也即DS0提供了一系列合適的唯一命名公理;DS0為每一個非流謂詞符提供了一個定義;對于每一個關(guān)系流提供了一個關(guān)系 。
在如上所述的假設(shè)的支持下,經(jīng)過Lloyd-Topor變形公式的推導(dǎo)轉(zhuǎn)換后就有了一個正確的Golog環(huán)境。
在此對購買飛機(jī)票的問題給出一些復(fù)雜的可能。
因為在實際的程序執(zhí)行過程中,不會總是給出真假值,更可能的情況是將輸出轉(zhuǎn)化為謂詞的形式,產(chǎn)生一種類似于知識的結(jié)果(這樣更符合人腦推理時的特性)或者輸出一系列程序執(zhí)行后所產(chǎn)生的信息集合。
回到購買飛機(jī)票的過程,假設(shè)有一個新的原子行為叫做定位機(jī)票LocateAirTicket,表示在機(jī)場方出售機(jī)票之前查找定位用戶所需要的航班線路,則其行為的執(zhí)行結(jié)果(如果為正效果)則是機(jī)票的價格已知,此時正效果公理為:則有,
。
再給出一個后續(xù)狀態(tài)公理的實例,例如這位用戶擁有了這張飛機(jī)票,那么粗略地想,只有兩種可能,一是他購買了這張機(jī)票且機(jī)票有庫存;二是他本來就擁有這張機(jī)票(不考慮具體得到方式),且他不想退票,用下式以描述他的擁有飛機(jī)票的這個行為:
這里,給出一種猜想,目前正在證實階段。
推論1 Golog中后續(xù)狀態(tài)公理的應(yīng)用定式:
這表示流在狀態(tài)do(a,s)當(dāng)且僅當(dāng)執(zhí)行使其正效果公理
或在其已經(jīng)為真的時候不執(zhí)行負(fù)效果公理。
下面繼續(xù)說明行為前提公理的表述實例。以下為有多個前提條件的行為前提公理定義式:
那么,比如購買飛機(jī)票的原子行為前提條件在于用戶的信用卡、賬號等信息都是存在且可用的,則下述對應(yīng)關(guān)系成立:
如果說正負(fù)效果公理中的輸出過程會產(chǎn)生一個知識性結(jié)果,那么輸入過程則是知識性前提。可以想象,在一個行為執(zhí)行之前,各類參數(shù)的值是一定會被知曉的,例如在購票過程中:
這是很容易被理解的。
下面的推論可以被簡單證明。
推論3 Golog中對行為前提公理的描述為:
是符合人類生活習(xí)慣
經(jīng)過從復(fù)習(xí)離散數(shù)學(xué)到學(xué)習(xí)情景演算理論,從下載Prolog編譯環(huán)境到Golog的一般推論,本課題中關(guān)于邏輯部分上的研究已初見成效。在許多理論上的例子和情景演算中的式子可以被稍加變化應(yīng)用在計算機(jī)語言中,的確是非常令人欣慰的事。本文對于Prolog語言能夠在Web服務(wù)中應(yīng)用做了詳細(xì)闡述,毫無疑問地證明了其可行性,而Golog推理理論的提出同時也提示了研究下一步的方向。
Web組合服務(wù)的初衷是美好的,是能夠滿足人們需求且最終能被廣泛使用的,而語義Web對計算機(jī)的發(fā)展更是大有裨益。但由于時間的原因,這部分的工作仍然處于未完成階段,例如Golog中的推理過程描述以及后續(xù)過程中程序的拼接、平臺與平臺之間的相互適應(yīng),還有更多的問題值得去研究和討論。
1 梁晟.基于語義Web的服務(wù)自動組合技術(shù)研究.中國科學(xué)院軟件研究所博士學(xué)位論文,2004
2 袁書俊.基于Web的自動組合服務(wù)框架的研究.華東師范大學(xué)碩士學(xué)位論文,2008
3 雷英杰,張雷,邢清華等.Visual Prolog語言教程.西安:陜西科學(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 邢星.語義Web服務(wù)自動組合方法研究.大連海事大學(xué)碩士學(xué)位論文,2008
10 楊紅蘭.自動組合服務(wù)框架的研究和設(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