并發面向對象中的繼承反常現象 *

王生原 ¹⁺ ,? 楊良懷 ² ,? 袁崇義 ³ ,? 楊 ? 萍 ⁴

¹ ( 清華大學 計算機科學與技術系 , 北京 ? 100084)

² ( 新加坡國立大學 計算學院 計算機科學系 , 新加坡 )

³ ( 北京大學 計算機科學技術系 , 北京 ? 100871)

⁴ ( 蘭州大學 信息科學與工程學院 , 甘肅 蘭州 ? 730000)

Inheritance Anomaly in Concurrent Object Orientation ^*

WANG Sheng-Yuan¹⁺,? YANG Liang-Huai²,? YUAN Chong-Yi³,? YANG Ping⁴

¹ (Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)

² (Department of Computer Science, School of Computing, National University of Singapore, Singapore)

³ (Department of Computer Science and Technology, Beijing University, Beijing 100871, China)

⁴ (School of Information Science and Technology, Lanzhou University, Lanzhou 730000, China)

+ Corresponding author: Phn: +86-10-62645407, Fax: +86-10-62645000, E-mail: wsy@163.net, http://www.tsinghua.edu.cn

Received 2002-10-08; Accepted 2003-01-05

?

Abstract :?? 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 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 well 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

摘? 要 :???? 如果不考慮繼承性 , 并發性與對象技術的結合是很自然的 . 繼承反常 ( 又稱繼承異常 ) 現象是繼承性和并發性不相容的主要原因之一 . 現階段人們對繼承反常現象的認識有許多模糊之處 , 出發點不盡相同 , 形式化的工作也很少 . 對不同的 subtyping 關系考慮其特有的漸增式繼承方法有利于把握繼承反常現象的實質 , 也豐富了 “ 在并發面向對象語言中應將 inheritance 層次和 subtyping 層次區別對待 ” 這一認識的內涵 . 在闡述基本觀點之后 , 采用范疇論的術語對相關的概念和定義做了形式化工作 . 一些觀點和結論適用于區分和解釋相關工作的出發點和貢獻 , 并對并發面向對象技術中繼承性的建模問題有所啟示 .

關鍵詞 :???? 并發性 ; 面向對象 ; 繼承反常 ; 漸增式繼承 ; 范疇論

中圖法分類號 :? TP301 　　　文獻標識碼 : A

Inheritance( 繼承 ) 是類 (class) 之間的一種層次關系 . 在一般的面向對象語言中 , 類層次自動對應了一種類型 (type) 層次 ^[1] , 這樣 ,superclass 和 subclass 之間的關系自然是一種 supertype 和 subtype 之間的關系 .

1? ?? 認識繼承反常現象

如圖 1 所示 , 類 Buffer 實現了一個有界緩沖區類型 , 可以并發地接受消息 put 和 get . 同步機制采用了 “method guards” 方式 , 即為每一個 method 附加一個 guard 謂詞 ^[2] . 構造 Buffer 的另一個子類 LockableBuffer 也會引發同樣的問題 . 這種 “ 為獲得有效繼承而必須對父類代碼進行實質性修改的現象 ” 就是所謂的繼承反常 (inheritance anomaly)^[3~5].

2? ??

Interest patterns

Vector clustering

Pattern derivation

Feature extraction

Document database

Vector database

Document clusters

Interest topics

Fig.1 ?Mining interest patterns 圖 1 ? 興趣模式的挖掘過程

理解繼承反常現象

2.1? ? 區別Inheritance 和Subtyping

綜合各種觀點 , 要理解和解釋繼承反常現象 , 首先必須正確區別 inheritance 層次和 subtyping 層次 , 并深刻領會二者的聯系 ^[6,7] . 對于這個問題 , 文獻 [1,8] 的觀點是比較權威的 . 在此基礎上 , 我們的理解是 :Inheritance 是在代碼層次上作修改 , 而 subtyping 是在語義層次上作修改 . 前者是代碼共享的一種重要途徑 , 但不能保證 subclass 能夠繼承 superclass 的行為 ; 后者要求 subtype 保持 supertype 的某種外部可觀察行為 ( 或語義行為 ), 在規范一級共享 , 同代碼沒有關系 .Inheritance 層次關系可以理解為 “is_similar_to”( 或 “like”) 的關系 , 而將 “is_a” 關系更適合用在理解 subtyping 層次關系上 , 見表 1^[9].

Table 1 ?Latency of macro-instructions

表 1 ? 宏指令的時延

命題 1 . 設 R í R _L ,R ￠ í R ,R 定義的 Class 范疇為 C _R ,R ￠ 定義的 Class 范疇為 C _{R ￠} , 則 C _{R ￠} 是 C _R 的子范疇 , 并稱之為 C _R 的子 Class 范疇 .

證明 : 對任何 A ,B ? ob C _R =obC_{R ￠} ,hom_{CR ￠} (A,B) í hom_CR (A,B).??????????????????????????????????????????????????????????????????????????????????? □

推論 1 . 任何 R í R _L 定義的 Class 范疇 C _R 都是 C _L 的子 Class 范疇 .

2.2? ? 漸增式繼承

Subtyping 要求 subtype 保持 supertype 的某種行為 ( 可看作是一種不變量 , 比如同步約束 )^[10].Subclass 在增加新的屬性或方法時 , 為了避免破壞這種不變量 , 難免要對繼承的代碼進行擴展或修改 . 這種擴 展或修改很可能是重大的或實質性的 , 結果使得代碼共享失去意義 . 這便是繼承反常的直觀含義 .

假定非線性優化問題 :

????????????????????????????????????????????????????????????????????????????? ???????????????????????????????????????????????????????????????????????? (1)

的近似解為 , 其中 由邊界條件決定 . 確定其余幾個 Bézier 系數是一個非線性約束優化問題 . 我們采用基于一維線性搜索的整體收斂的 Newton 迭代方法來求解 . 其基本的迭代格式為

步長 采用回溯線性搜索方法確定 , 下降方向 是 Newton 方向 , 這種非線性優化方法是一個比較成功的具有整體收斂性的方法 , 對于初值的選擇沒有苛刻的要求 .

?

Internet

Response

Request

Browser

Front_end server

Back_end server

Back_end server

Back_end server

. . .

Fig.2? The framework of the TB-CCRD based DWSS 圖 2? 基于標記的緩存協作 DWSS 系統框架

基于 TB-CCRD 的新系統采用與 Linux 直接路由式虛擬服務器相同的框架結構 ^[11] . 如圖 2 所示 ,DWSS 的各個后端服務器通過高速以太網相互連接 , 它們屏蔽 ARP 協議 , 并擁有與前端機相同的 IP( 記為 vIP) 和 Web 服務端口號 ( 記為 vPort), 在用戶看來 , 這個系統就相當于一個 IP 地址為 vIP, 服務端口號為 vPort 的 Web 服務器 . 在新系統中 , 前端機負責接收來自用戶的數據包 , 發放用于指示處理該數據包最適當的服務器 ID( 可以是后端機在系統內部的標識符 , 也可以是它的 MAC 地址 ) 的標記 , 并轉發數據包 ; 后端機則負責處理由前端機轉發而來的用戶數據包并直接回應用戶 , 具體包括建立 / 拆除與用戶的 TCP 連接、 TCP 連接轉交以及提供 URL 內容等工作 .

2.2.1? ??? 定義繼承反常現象

本節是對上述觀點的形式化描述 , 可與第 2.2 節對照閱讀 . 范疇論的觀點層次較高 , 易于抽象出問題的本質 .

與程序 P 在 F 下運行等價的錯誤影響程序 P_F 有

2.2.2? ???

(2)

InitPF = InitP , VarPF = VarF , UnitPF = e [ A 1 ? F ; A 2 ? F ;…; An ? F ] , WherePF = WhereP ù FaultAssumptionF .

解釋繼承反常現象

例 1: 在談到順序面向對象語言時 , 一般不涉及繼承反常現象 . 這是因為 , 這類語言 L 都默認一個特殊的 subtyping 關 系 p ( 由 R _L 定義的完整 inheritance 層 次關系被默認為相應于 p 的漸增式繼承關系 ), 它對應的 Type 范疇記為 T _L , 滿足 :C_L 實現 T _L , 實現函子為 F : " A (A ? ob C _L ? F A = type (A)).L 無 p - 繼承反常 . 因為順序面向對象語言不提供定義 subtyping 關系的機制 , 所以這種默認的 subtyping 關系是語言中惟一的 subtyping 關系 , 這些語言 L 無繼承反常 .

3? ?? 結束語

本文形式地給出了 “ 繼承反常現象 ” 的一種一般性定義 . 定義對每一種 Subtyping 關系都有其相對應的 “ 漸增式繼承 ” , 使其更具有普適性 . 文中 “ 漸增式繼承 ” 是一個相對的概念 , 這有助于對人們 “ 使繼承反常現象得到緩解 ” 的努力得以分類和評價 .

致謝 ? 在此 , 我們向對本文的工作給予支持和建議的同行 , 尤其是北京大學計算機科學技術系袁崇義教授、屈婉玲教授領導的討論班上的同學和老師表示感謝 .

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):130-145.

? [2]? ?? Wegner P, Zdonik SB. Inheritance as an incremental modification mechanism or what like is and isn’t like. In: Gjessing S, Nygaard K, eds. Proc. of the ECOOP’88. LNCS 322, Heidelberg: Springer-Verlag, 1988. 55-77.

? [3]? ?? Waxman BM. Routing of multipoint connections. IEEE Journal on Selected Areas 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 Concurrent 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 user’s guide. Technical Report, NML/MRL/5540-94-7427, Austin: University of Texas at Austin, 1994.

? [8]? ?? Keene SE. A Programmer’s Guide to Object-Oriented Programming in Common LISP. Boston: Addison-Wesley Longman Publishing Co., Inc., 1988.

? [9]? ?? Guo L, Tang ZS. Specification and verification of the triple-modular redundancy fault-tolerant system. Journal of Software, 2003,14(1):28~35 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/14/28.htm

[10]? ?? Schutze, H. Dimensions of meaning. In: Whitelock P, ed. Proc. of the Supercomputing’92. Los Alamitos, 1992. 787~796. ftp://parcftp.parc.xerox.com/pub/qca/papers/

[11]? ?? Wang XW. Research on quality-of-service management and group communication mechanisms in distributed multimedia systems [Ph.D. Thesis]. Shenyang: Northeastern University, 1998 (in Chinese with English abstract).

附中文參考文獻 :

? [9]??? 郭亮 , 唐稚松 . 三機冗余容錯系統的描述和驗證 . 軟件學報 ,2003,14(1):28-35. http://www.jos.org.cn/1000-9825/14/28.htm

[11]??? 王興偉 . 分布式多媒體系統服務質量管理與組通信機制的研究 [ 博士學位論文 ]. 沈陽 : 東北大學 ,1998.

凡是有該標志的文章，都是該blog博主Caoer（草兒）原創，凡是索引、收藏
、轉載請注明來處和原文作者。非常感謝。