《軟件學(xué)報(bào)》排版樣例2005版

王生原楊良懷袁崇義楊萍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）InheritanceAnomalyinConcurrentObjectOrientationSupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.60373000（國家自然科學(xué)基金）;theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNos.863-317-01-04-99,2001AA115126（國家高技術(shù)研究發(fā)展計(jì)劃（863））;SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.60373000（國家自然科學(xué)基金）;theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNos.863-317-01-04-99,2001AA115126（國家高技術(shù)研究發(fā)展計(jì)劃（863））;theNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.G1999032706（國家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃（973））;theKeyScience-TechnologyProjectoftheNational'NinthFive-Year-Plan'ofChinaunderGrantNo.98-780-01-07-03（國家“九五”重點(diǎn)科技攻關(guān)項(xiàng)目）;theDefensePre-ResearchProjectofthe'NinthFive-Year-Plan'ofChina（國家“九五”國防預(yù)研基金）；theNationalResearchFoundationfbrtheDoctoralProgramofHigherEducationofChina（國家教育部博士點(diǎn)基金）;theMinistry&Commission-LevelResearchFoundationofChina（部委級(jí)基金）;theNaturalScienceFoundationofGansuProvinceofChinaunderGrantNo.ZS991-A25-014-G（甘肅省自然科學(xué)基金）作者簡介：王生原（1964-）,男,山西應(yīng)縣人,博士,副教授，主要研究領(lǐng)域?yàn)榉植紝?duì)象計(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)槿斯ぶ悄?WANGSheng-Yuan1+,YANGLiang-Huai2,YUANChong-Yi3,YANGPing41（DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084,China）2（DepartmentofComputerScience,SchoolofComputing,NationalUniversityofSingapore,Singapore）3（DepartmentofComputerScienceandTechnology,BeijingUniversity,Beijing100871,China）4（SchoolofInformationScienceandTechnology,LanzhouUniversity,Lanzhou730000,China）+Correspondingauthor:Phn:+86-10-62645407,Fax:+86-10-62645000,E-mail:wsy@163.net,Received2002-10-08;Accepted2003-01-05Abstract:Thecombinationofconcurrencyandobjectorientationisdefinitelynaturalexceptforinheritance.Oneoftheinterferencesbetweeninheritanceandconcurrencyisinheritanceanomaly.Althoughhavingbeenresearchedextensively,inheritanceanomaliesarestillonlyvaguelydefinedandoftenmisunderstood,andnomuchformalworkhasbeendone.Anewviewpointissetforthforunderstandinginheritanceanomalies,inwhicheachsubtypingrelationhasitsspecificincrementalinheritance.RelatedconceptsanddefinitionsareformalizedthroughthelanguageofCategory.Someissuesarewelladaptedtodistinguishandexplaindifferentstandpointsaboutinheritanceanomalies,andcanserveasguidelinesinthemodelingofinheritance.Keywords: concurrency;objectorientation;inheritanceanomaly;incrementalinheritance;categorytheory摘要：如果不考慮繼承性，并發(fā)性與對(duì)象技術(shù)的結(jié)合是很自然的.繼承反常（又稱繼承異常）現(xiàn)象是繼承性和并發(fā)性不相容的主要原因之一.現(xiàn)階段人們對(duì)繼承反?，F(xiàn)象的認(rèn)識(shí)有許多模糊之處，出發(fā)點(diǎn)不盡相同，形式化的工作也很少.對(duì)不同的subtyping關(guān)系考慮其特有的漸增式繼承方法有利于把握繼承反?，F(xiàn)象的實(shí)質(zhì)，也豐富了“在并發(fā)面向?qū)ο笳Z言中應(yīng)將inheritance層次和subtyping層次區(qū)別對(duì)待”這一認(rèn)識(shí)的內(nèi)涵.在闡述基本觀點(diǎn)之后,采用范疇論的術(shù)語對(duì)相關(guān)的概念和定義做了形式化工作 .一些觀點(diǎn)和結(jié)論適用于區(qū)分和解釋相關(guān)工作的出發(fā)點(diǎn)和貢獻(xiàn)，并對(duì)并發(fā)面向?qū)ο蠹夹g(shù)中繼承性的建模問題有所啟示.關(guān)鍵詞：并發(fā)性;面向?qū)ο?繼承反常;漸增式繼承;范疇論中圖法分類號(hào):TP301 文獻(xiàn)標(biāo)識(shí)碼:AInheritance（繼承）是類（class）之間的一種層次關(guān)系.在一般的面向?qū)ο笳Z言中，類層次自動(dòng)對(duì)應(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ī)制采用了“methodguards”方式，即為每一個(gè)method附加一個(gè)guard謂詞[2].構(gòu)造Buffer的另一個(gè)子類LockableBuffer也會(huì)引發(fā)同樣的問題.這種“為獲得有效繼承而必須對(duì)父類代碼進(jìn)行實(shí)質(zhì)性修改的現(xiàn)象”就是所謂的繼承反常（inheritanceanomaly）[3~5].Fig.1Mininginterestpatterns圖1興趣模式的挖掘過程2理解繼承反?，F(xiàn)象2.1區(qū)別Inheritance和Subtyping綜合各種觀點(diǎn)，要理解和解釋繼承反?，F(xiàn)象，首先必須正確區(qū)別inheritance層次和subtyping層次，并深刻領(lǐng)會(huì)二者的聯(lián)系叫.對(duì)于這個(gè)問題，文獻(xiàn)[1，8]的觀點(diǎn)是比較權(quán)威的.在此基礎(chǔ)上，我們的理解是:Inheritance是在代碼層次上作修改，而subtyping是在語義層次上作修改.前者是代碼共享的一種重要途徑，但不能保證subclass能夠繼承superclass的行為;后者要求subtype保持supertype的某種外部可觀察行為（或語義行為），在規(guī)范一級(jí)共享,同代碼沒有關(guān)系.Inheritance層次關(guān)系可以理解為“is_similar_to”（或Tike”）的關(guān)系，而將“is_a”關(guān)系更適合用在理解subtyping層次關(guān)系上，見表1[9].Table1Latencyofmacro-instructions表1宏指令的時(shí)延Acronym Macro-Instructions Latency(ns) _ .〔EventsymbolValue Symbol /NSI NET_SLICE_INIT()NST NET_SLICE_STOP()NSE NET_SLICE_EXIT()Inter-OverheadbetweenNET_SLICE_START()NSO andNET_SLICE_STOP() NSA OverheadofNET_SLICE_START() 87 Ta n(a，e)154 一 一904(1.4%) 七 n(y，e)150 匕 n(o，e) 303 n^ 命題1.設(shè)RJRl，R'JR，R定義的Class范疇為CR，R定義的Class范疇為CR,，則命是CR的子范疇,并稱之為Cr的子Class范疇.證明:對(duì)任何4BcobCR=obCR,，homCr（A，B）JhomC*A，B）.推論1.任何RJRl定義的Class范疇CR都是CL的子Class范疇.

2.2漸增式繼承Subtyping要求subtype保持supertype的某種行為（可看作是一種不變量，比如同步約束）[iO].Subclass在增加新的屬性或方法時(shí),為了避免破壞這種不變量，難免要對(duì)繼承的代碼進(jìn)行擴(kuò)展或修改.這種擴(kuò)展或修改很可能是重大的或?qū)嵸|(zhì)性的,結(jié)果使得代碼共享失去意義.這便是繼承反常的直觀含義.假定非線性優(yōu)化問題：minjj1+z2+z2dxdy

zv*Q， 3，的近似解為z（X，y）=￡￡bBn（x）Bn（y），其中b，b，b，b由邊界條件決定.確定其余幾個(gè)Bezier系數(shù)是一個(gè)非iji i 0j3ji0i3線性約束優(yōu)化問題.莪們?采用基于一維線性搜索的整體收斂的Newton迭代方法來求解.其基本的迭代格式為X'+1=xi+X?p.步長人采用回溯線性搜索方法確定，下降方向p是Newton方'向，這種非線性優(yōu)化方法是一個(gè)比較成功的具有整體收斂性的方法，對(duì)于初值的選擇沒有苛刻的要求.Fig.2TheframeworkoftheTB-CCRDbasedDWSS圖2基于標(biāo)記的緩存協(xié)作DWSS系統(tǒng)框架Response基于TB-CCRD的新系統(tǒng)采用與Linux直接路由式虛擬服務(wù)器相同的框架結(jié)構(gòu)[11].如圖2所示,DWSS的各個(gè)后端服務(wù)器通過高速以太網(wǎng)相互連接,它們屏蔽ARP協(xié)議,并擁有與前端機(jī)相同的IP（記為vIP）和Web服務(wù)端口號(hào)（記為vPort）,在用戶看來，這個(gè)系統(tǒng)就相當(dāng)于一個(gè)IP地址為vIP,服務(wù)端口號(hào)為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地址）的標(biāo)記,并轉(zhuǎn)發(fā)數(shù)據(jù)包;后端機(jī)則負(fù)責(zé)處理由前端機(jī)轉(zhuǎn)發(fā)而來的用戶數(shù)據(jù)包并直接回應(yīng)用戶，具體包括建立/拆除與用戶的TCP連接、TCPFig.2TheframeworkoftheTB-CCRDbasedDWSS圖2基于標(biāo)記的緩存協(xié)作DWSS系統(tǒng)框架Response2.2.1定義繼承反?，F(xiàn)象本節(jié)是對(duì)上述觀點(diǎn)的形式化描述，可與第2.2節(jié)對(duì)照閱讀.范疇論的觀點(diǎn)層次較高,易于抽象出問題的本質(zhì).與程序P在F下運(yùn)行等價(jià)的錯(cuò)誤影響程序PF有(2)InitPF=InitP，VarpF=VarF，(2)UnitPF=D[A1?F;A2十F;...;A〃十F],WherePF=WhereP^FaultAssumptionF，」2.2.2解釋繼承反?，F(xiàn)象例1:在談到順序面向?qū)ο笳Z言時(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)系）,它對(duì)應(yīng)的Type范疇記為7L，滿足:G實(shí)現(xiàn)rL，實(shí)現(xiàn)函子為F:VA（AMbCL^FA=type（A））.L無p-繼承反常.因?yàn)轫樞蛎嫦驅(qū)ο笳Z言不提供定義subtyping關(guān)系的機(jī)制，所以這種默認(rèn)的subtyping關(guān)系是語言中惟一的subtyping關(guān)系，這些語言L無繼承反常.3結(jié)束語本文形式地給出了“繼承反常現(xiàn)象”的一種一般性定義.定義對(duì)每一種Subtyping關(guān)系都有其相對(duì)應(yīng)的“漸增式繼承”，使其更具有普適性.文中“漸增式繼承”是一個(gè)相對(duì)的概念，這有助于對(duì)人們“使繼承反?，F(xiàn)象得到緩解”的努力得以分類和評(píng)價(jià).致謝在此，我們向?qū)Ρ疚牡墓ぷ鹘o予支持和建議的同行，尤其是北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系袁崇義教授、屈婉玲教授領(lǐng)導(dǎo)的討論班上的同學(xué)和老師表示感謝.References:CliftonC,LeavensGT，ChambersC,MillsteinT.MultiJava:modularopenclassesandsymmetricmultipledispatchforJava.ACMSIGPLANNotices,2000,35(10):130-145.WegnerP,ZdonikSB.Inheritanceasanincrementalmodificationmechanismorwhatlikeisandisn'tlike.In:GjessingS,NygaardK,eds.Proc.ofitheECOOP'88.LNCS322,Heidelberg:Springer-Verlag,1988.55-77.WaxmanBM.Routingofmultipointconnections.IEEEJournalonSelectedAreasinCommunications,1988,6(9):1617-1622.YonezawaA.ABCL:AnObject-OrientedConcurrentSystem.Cambridge:MITPress,1990.MatsuokaS,YonezawaA.Analysisofinheritanceanomalyinobject-orientedconcurrentprogramminglanguages.In:Agha G,WegnerP,YonezawaA,eds.ResearchDirectionsinConcurrentObject-OrientedProgramming.Cambridge:MITPress,1993.107-150.HemigeV.Object-Orienteddesignofthegroupwarelayerfortheecosysteminformationsystem[MS.Thesis].UniversityofMontana,1995.RoseA,PerezM,ClementsP.Modecharttoolsetuser'sguide.TechnicalReport,NML/MRL/5540-94-7427,Austin:UniversityofTexasatAustin,1994.KeeneSE.AProgrammer'sGuidetoObject-Orien