并發(fā)面向?qū)ο笾械睦^承反常現(xiàn)象（

1、王生原 等:并發(fā)面向?qū)ο笾械睦^承反?，F(xiàn)象963并發(fā)面向?qū)ο笾械睦^承反?，F(xiàn)象*Supported by the National Natural Science Foundation of China under Grant No.60373000 (國家自然科學(xué)基金); the National High-Tech Research and Development Plan of China under Grant Nos.863-317-01-04-99, 2001AA115126 (國家高技術(shù)研究發(fā)展計(jì)劃(863); the National Grand Fundamental Resea

2、rch 973 Program of China under Grant No.G1999032706 (國家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃(973); the Key Science-Technology Project of the National Ninth Five-Year-Plan of China under Grant No.98-780-01-07-03 (國家“九五”重點(diǎn)科技攻關(guān)項(xiàng)目); the Defense Pre-Research Project of the Ninth Five-Year-Plan of China (國家“九五”國防預(yù)研基金); the National

3、 Research Foundation for the Doctoral Program of Higher Education of China (國家教育部博士點(diǎn)基金); the Ministry & Commission-Level Research Foundation of China (部委級基金); the Natural Science Foundation of Gansu Province of China under Grant No.ZS991-A25-014-G (甘肅省自然科學(xué)基金)作者簡介: 王生原(1964),男,山西應(yīng)縣人,博士,副教授,主要研究領(lǐng)域

4、為分布對象計(jì)算,Petri網(wǎng)應(yīng)用,嵌入式軟件環(huán)境;楊良懷(1967),男,博士,講師,主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫系統(tǒng)實(shí)現(xiàn)技術(shù),數(shù)據(jù)倉庫,半結(jié)構(gòu)化數(shù)據(jù),Web數(shù)據(jù)集成,數(shù)據(jù)挖掘;袁崇義(1941),男,教授,博士生導(dǎo)師,主要研究領(lǐng)域?yàn)椴⑿杏?jì)算,Petri網(wǎng)理論及應(yīng)用;楊萍(1964),女,副教授,主要研究領(lǐng)域?yàn)槿斯ぶ悄?王生原1+, 楊良懷2, 袁崇義3, 楊 萍41(清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系,北京 100084)2(新加坡國立大學(xué) 計(jì)算學(xué)院 計(jì)算機(jī)科學(xué)系,新加坡)3(北京大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)系,北京 100871)4(蘭州大學(xué) 信息科學(xué)與工程學(xué)院,甘肅 蘭州 730000)Inheritance

5、 Anomaly in Concurrent Object Orientation*WANG Sheng-Yuan1+, YANG Liang-Huai2, YUAN Chong-Yi3, YANG Ping41(Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)2(Department of Computer Science, School of Computing, National University of Singapore, Singapore)3(De

6、partment of Computer Science and Technology, Beijing University, Beijing 100871, China)4(School of Information Science and Technology, Lanzhou University, Lanzhou 730000, China)+ Corresponding author: Phn: +86-10-62645407, Fax: +86-10-62645000, E-mail: wsy, Received 2002-10-08; Accepted 2003-01-05Ab

7、stract:The combination of concurrency and object orientation is definitely natural except for inheritance. One of the interferences between inheritance and concurrency is inheritance anomaly. Although having been researched extensively, inheritance anomalies are still only vaguely defined and often

8、misunderstood, and no much formal work has been done. A new viewpoint is set forth for understanding inheritance anomalies, in which each subtyping relation has its specific incremental inheritance. Related concepts and definitions are formalized through the language of Category. Some issues are wel

9、l adapted to distinguish and explain different standpoints about inheritance anomalies, and can serve as guidelines in the modeling of inheritance.Key words:concurrency; object orientation; inheritance anomaly; incremental inheritance; category theory摘 要:如果不考慮繼承性,并發(fā)性與對象技術(shù)的結(jié)合是很自然的.繼承反常(又稱繼承異常)現(xiàn)象是繼承性和

10、并發(fā)性不相容的主要原因之一.現(xiàn)階段人們對繼承反?，F(xiàn)象的認(rèn)識(shí)有許多模糊之處,出發(fā)點(diǎn)不盡相同,形式化的工作也很少.對不同的subtyping關(guān)系考慮其特有的漸增式繼承方法有利于把握繼承反?，F(xiàn)象的實(shí)質(zhì),也豐富了“在并發(fā)面向?qū)ο笳Z言中應(yīng)將inheritance層次和subtyping層次區(qū)別對待”這一認(rèn)識(shí)的內(nèi)涵.在闡述基本觀點(diǎn)之后,采用范疇論的術(shù)語對相關(guān)的概念和定義做了形式化工作.一些觀點(diǎn)和結(jié)論適用于區(qū)分和解釋相關(guān)工作的出發(fā)點(diǎn)和貢獻(xiàn),并對并發(fā)面向?qū)ο蠹夹g(shù)中繼承性的建模問題有所啟示.關(guān)鍵詞:并發(fā)性;面向?qū)ο?繼承反常;漸增式繼承;范疇論中圖法分類號:TP301文獻(xiàn)標(biāo)識(shí)碼: AInheritance(繼承

11、)是類(class)之間的一種層次關(guān)系.在一般的面向?qū)ο笳Z言中,類層次自動(dòng)對應(yīng)了一種類型(type)層次1,這樣,superclass和subclass之間的關(guān)系自然是一種supertype和subtype之間的關(guān)系.1 認(rèn)識(shí)繼承反?，F(xiàn)象如圖1所示,類Buffer實(shí)現(xiàn)了一個(gè)有界緩沖區(qū)類型,可以并發(fā)地接受消息put和get.同步機(jī)制采用了“method guards”方式,即為每一個(gè)method附加一個(gè)guard謂詞2.構(gòu)造Buffer的另一個(gè)子類LockableBuffer也會(huì)引發(fā)同樣的問題.這種“為獲得有效繼承而必須對父類代碼進(jìn)行實(shí)質(zhì)性修改的現(xiàn)象”就是所謂的繼承反常(inheritance

12、anomaly)35.Interest patternsVectorclusteringPatternderivationFeatureextractionDocumentdatabaseVectordatabaseDocumentclustersInteresttopicsFig.1 Mining interest patterns圖1 興趣模式的挖掘過程2 理解繼承反?，F(xiàn)象2.1 區(qū)別Inheritance和Subtyping綜合各種觀點(diǎn),要理解和解釋繼承反?，F(xiàn)象,首先必須正確區(qū)別inheritance層次和subtyping層次,并深刻領(lǐng)會(huì)二者的聯(lián)系6,7.對于這個(gè)問題,文獻(xiàn)1,8的觀點(diǎn)

13、是比較權(quán)威的.在此基礎(chǔ)上,我們的理解是:Inheritance是在代碼層次上作修改,而subtyping是在語義層次上作修改.前者是代碼共享的一種重要途徑,但不能保證subclass能夠繼承superclass的行為;后者要求subtype保持supertype的某種外部可觀察行為(或語義行為),在規(guī)范一級共享,同代碼沒有關(guān)系.Inheritance層次關(guān)系可以理解為“is_similar_to”(或“l(fā)ike”)的關(guān)系,而將“is_a”關(guān)系更適合用在理解subtyping層次關(guān)系上,見表19.Table 1 Latency of macro-instructions表1 宏指令的時(shí)延Acro

14、nymMacro-InstructionsLatency (ns)Event symbolValueSymbolNSINET_SLICE_INIT()87tan(a,e)NSTNET_SLICE_STOP()154-NSENET_SLICE_EXIT()904 (1.4%)tgn(g,e)NSOInter-Overhead between NET_SLICE_START() and NET_SLICE_STOP()150ton(o,e)NSAOverhead of NET_SLICE_START()303tbn(b,e)命題1. 設(shè)RÍRL,R¢ÍR,R定義的Cl

15、ass范疇為CR,R¢定義的Class范疇為CR¢,則CR¢是CR的子范疇,并稱之為CR的子Class范疇.證明:對任何A,BÎob CR=ob CR¢,homCR¢(A,B)ÍhomCR(A,B).推論1. 任何RÍRL定義的Class范疇CR都是CL的子Class范疇.2.2 漸增式繼承Subtyping要求subtype保持supertype的某種行為(可看作是一種不變量,比如同步約束)10.Subclass在增加新的屬性或方法時(shí),為了避免破壞這種不變量,難免要對繼承的代碼進(jìn)行擴(kuò)展或修改.這種擴(kuò)展或修改很可能

16、是重大的或?qū)嵸|(zhì)性的,結(jié)果使得代碼共享失去意義.這便是繼承反常的直觀含義.假定非線性優(yōu)化問題:(1)的近似解為,其中由邊界條件決定.確定其余幾個(gè)Bézier系數(shù)是一個(gè)非線性約束優(yōu)化問題.我們采用基于一維線性搜索的整體收斂的Newton迭代方法來求解.其基本的迭代格式為步長采用回溯線性搜索方法確定,下降方向是Newton方向,這種非線性優(yōu)化方法是一個(gè)比較成功的具有整體收斂性的方法,對于初值的選擇沒有苛刻的要求.InternetResponseRequestBrowserFront_end serverBack_end serverBack_end serverBack_end serve

17、r.Fig.2 The framework of the TB-CCRD based DWSS圖2 基于標(biāo)記的緩存協(xié)作DWSS系統(tǒng)框架基于TB-CCRD的新系統(tǒng)采用與Linux直接路由式虛擬服務(wù)器相同的框架結(jié)構(gòu)11.如圖2所示,DWSS的各個(gè)后端服務(wù)器通過高速以太網(wǎng)相互連接,它們屏蔽ARP協(xié)議,并擁有與前端機(jī)相同的IP(記為vIP)和Web服務(wù)端口號(記為vPort),在用戶看來,這個(gè)系統(tǒng)就相當(dāng)于一個(gè)IP地址為vIP,服務(wù)端口號為vPort的Web服務(wù)器.在新系統(tǒng)中,前端機(jī)負(fù)責(zé)接收來自用戶的數(shù)據(jù)包,發(fā)放用于指示處理該數(shù)據(jù)包最適當(dāng)?shù)姆?wù)器ID(可以是后端機(jī)在系統(tǒng)內(nèi)部的標(biāo)識(shí)符,也可以是它的MAC地

18、址)的標(biāo)記,并轉(zhuǎn)發(fā)數(shù)據(jù)包;后端機(jī)則負(fù)責(zé)處理由前端機(jī)轉(zhuǎn)發(fā)而來的用戶數(shù)據(jù)包并直接回應(yīng)用戶,具體包括建立/拆除與用戶的TCP連接、TCP連接轉(zhuǎn)交以及提供URL內(nèi)容等工作.2.2.1 定義繼承反?，F(xiàn)象本節(jié)是對上述觀點(diǎn)的形式化描述,可與第2.2節(jié)對照閱讀.范疇論的觀點(diǎn)層次較高,易于抽象出問題的本質(zhì).與程序P在F下運(yùn)行等價(jià)的錯(cuò)誤影響程序PF有(2)InitPF=InitP,VarPF=VarF,UnitPF=ðA1ÅF;A2ÅF;AnÅF,WherePF=WherePÙFaultAssumptionF.2.2.2 解釋繼承反?，F(xiàn)象例1:在談到順序面向?qū)ο笳Z

19、言時(shí),一般不涉及繼承反?，F(xiàn)象.這是因?yàn)?這類語言L都默認(rèn)一個(gè)特殊的subtyping關(guān)系p(由RL定義的完整inheritance層次關(guān)系被默認(rèn)為相應(yīng)于p的漸增式繼承關(guān)系),它對應(yīng)的Type范疇記為TL,滿足:CL實(shí)現(xiàn)TL,實(shí)現(xiàn)函子為F:"A(AÎob CL®FA=type(A).L無p-繼承反常.因?yàn)轫樞蛎嫦驅(qū)ο笳Z言不提供定義subtyping關(guān)系的機(jī)制,所以這種默認(rèn)的subtyping關(guān)系是語言中惟一的subtyping關(guān)系,這些語言L無繼承反常.3 結(jié)束語本文形式地給出了“繼承反?，F(xiàn)象”的一種一般性定義.定義對每一種Subtyping關(guān)系都有其相對應(yīng)的“漸增

20、式繼承”,使其更具有普適性.文中“漸增式繼承”是一個(gè)相對的概念,這有助于對人們“使繼承反常現(xiàn)象得到緩解”的努力得以分類和評價(jià).致謝 在此,我們向?qū)Ρ疚牡墓ぷ鹘o予支持和建議的同行,尤其是北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系袁崇義教授、屈婉玲教授領(lǐng)導(dǎo)的討論班上的同學(xué)和老師表示感謝.References:1 Clifton C, Leavens GT, Chambers C, Millstein T. MultiJava: modular open classes and symmetric multiple dispatch for Java. ACM SIGPLAN Notices, 2000,35(10)

21、:130-145.2 Wegner P, Zdonik SB. Inheritance as an incremental modification mechanism or what like is and isnt like. In: Gjessing S, Nygaard K, eds. Proc. of the ECOOP88. LNCS 322, Heidelberg: Springer-Verlag, 1988. 55-77.3 Waxman BM. Routing of multipoint connections. IEEE Journal on Selected Areas

22、in Communications, 1988,6(9):1617-1622.4 Yonezawa A. ABCL: An Object-Oriented Concurrent System. Cambridge: MIT Press, 1990.5 Matsuoka S, Yonezawa A. Analysis of inheritance anomaly in object-oriented concurrent programming languages. In: Agha G, Wegner P, Yonezawa A, eds. Research Directions in Con

23、current Object-Oriented Programming. Cambridge: MIT Press, 1993. 107-150.6 Hemige V. Object-Oriented design of the groupware layer for the ecosystem information system MS. Thesis. University of Montana, 1995.7 Rose A, Perez M, Clements P. Modechart toolset users guide. Technical Report, NML/MRL/5540-94-7427, Austin: University of Texas