2022年并发面向对象中的继承反常现象 .pdf

并发面向对象中的继承反常现象1王生原杨良怀袁崇义杨萍Abstract.如果不考虑继承性， 并发性与对象技术的结合是很自然的。继承反常2（inheritance anomaly）现象是继承性和并发性不相容的主要原因之一。现阶段人们对继承反常现象的认识有许多模糊之处，出发点不尽相同，形式化的工作也很少。本文认为继承反常这一概念应有针对性，对不同的subtyping 关系应考虑其特有的渐增式继承（incremental inheritance ）方法，这有利于把握继承反常现象的实质，而不被各类不同的观点所误导，同时也丰富了“在并发面向对象语言中应将inheritance 层次和 subtyping 层次区别对待”这一认识的内涵。在阐述基本观点后， 本文采用范畴论的术语对继承反常现象给出了一种形式化的定义，并对并发面向对象技术中继承性的建模提出相关的建议。Key Words:并发性；面向对象；继承反常；渐增式继承；范畴论1. 引言Inheritance（继承）是面向对象理论和技术中主要的概念之一。大多数人已认同这样的观点：一个程序设计语言，即使它支持对象（Object）和类（ Class）的概念，如果不支持inheritance ，那么也不能称为是面向对象语言。继承是类之间的一种层次关系。Superclass 描述了同类subclass 的共性（泛化） ，而subclass 旨在继承其superclass 的这种共性，并扩展其特性（特化） 。继承是代码重用（Code Reuse）的重要途径之一。在一般的面向对象语言中，类层次自动对应了一种类型层次WZ88 ，这样， superclass和 subclass 之间的关系自然是一种supertype 和 subtype 之间的关系。 这种对应关系难免使人们在 inheritance 和 subtyping 之间产生模糊的认识。对于大多数顺序的面向对象语言来说，inheritance 和 subtyping 不加以区分几乎不会造成什么影响。但随着把并发性(concurrency）引入面向对象语言中（如Agha86 America90 Yonezawa90） ，人们发现inheritance和subtyping 之间并不容易协调，会出现所谓的继承反常（Inheritance Anomaly ）现象 MY93。在并发面向对象语言（COOL）中，对象是很自然的并发单元。对象之间的通信和同步依靠消息传递， 而对象内部的并发活动则是通过共享变量方式进行通信和同步。无论对象之间还是对象内部的通信和同步，都和同步代码（Synchronization Code）有关。同步代码的主要作用是对对象内部及其与外界的接口的并发活动（如并发方法， 内部线程， 对共享变量的操作等）进行一种约束，即同步约束（Synchronization Constrains ） 。在 inheritance 层次中，方法（及属性）的增改很可能会破坏这种约束。换句话说，subclass 要兼容其superclass 的这种同步约束，很可能必须对相关的superclass 代码进行实质性修改，而不可能重用它们。这 种 现 象 在 MY93 中 被 首 次 称 为 继 承 反 常 。 在 此 之 前也 有 许 多 这 方 面 问 题 的 讨 论（America87KL89） ，目前仍很受关注（LLNW96CRR98） 。对于继承反常现象，目前的解决方案主要有两类：（ 1）设计更强的同步机制MY93 ；（2）去掉同步原语Meseguer93LLNW96。但这些方法只能有限地减小继承反常的危害，并不能从根本上解决问题。面对所遇到的困难，有人在考虑是不是存在概念上的误区BCC95 ，目前这仍是一个开放的话题。实际上，除了同步约束，继承反常现象也可能是由其它情况引起的（ABSB94 ） ，这说明继承反常应属inheritance 本身的特征。本文认为继承反常这一概念应有针对性，并发面向对象中的继承不能只狭隘地沿用顺序程序中渐增式的继承（incremental inheritance ） ，对不同的subtyping 关系应考虑其特有的渐1Supported by the National Natural Science Foundation of China under grant No. 69973003, and by the China NKBRSF (973) under grant G1999032706. 2又译：继承异常 . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - 增式继承方法。 这有利于把握继承反常现象的实质，而不被各类不同的观点所误导，同时也丰富了“在并发面向对象语言中应将inheritance 层次和 subtyping 层次区别对待”这一认识的内涵。另一方面，不同背景和意义的“继承反常”足以使读者产生困惑。如有些工作称可以避开继承反常现象Meseguer93LLNW96，而另一些工作则认为继承反常是不可避免的CRR98 。究其原因主要是这方面的形式化工作很少，且不够全面。本文在上述观点的基础上，采用范畴论的术语对继承反常现象给出了一种形式化的定义。第 2 节通过经典实例使读者初步认识继承反常现象；第 3 节分析继承反常现象的实质及阐述本文理解这种现象的基本观点；第4 节用范畴论的术语形式地定义继承反常现象；第5节利用本文的定义对文献中出现的有关继承反常现象的典型情形进行了解释，并结合本文的观点，对并发面向对象技术中继承性的建模提出一些有益的建议。2. 认识继承反常现象class Buffer int in= out=0, bufSIZE; method put() when (in = out + 1) out+; /rest code of get() ; class Buffer2: Buffer method get2() when (in = out + 2) out + = 2; /rest code of get2() ; class GBuffer: Buffer bool after_put = false; method gget() when (!after_put & (in = out + 1) out+; after_put = false; /rest code of gget() ;method put() when (in = out + 1) out+; after_put = false; /rest code of get() ; class LockableBuffer: Buffer bool locked = false; method lock() when (!locked) locked = true ; method unlock() when (locked) locked = false ; method put() when (!locked & (in = out + 1) out+; /rest code of get() ; 图 2.1 有界缓冲区类Buffer，及其子类Buffer2 、GBuffer 和 LockableBuffer 考虑图 2.1，类 Buffer 实现了一个有限缓冲区类型，可以并发地接受消息put 和 get。同步机制采用了“method guards ”方式，即为每一method 附加一个 guard 谓词，在图.1 中形如“ method method_name when guard” 。如果对类Buffer增加新方法gget 来构造子类GBuffer ，就不得不修改同步代码，从而方法 put 和 get 的代码须重新定义。这里 gget 的行为同 get，但不可以紧跟在put 之后执行。同样，构造Buffer 的另一个子类LockableBuffer 也会引发同样的问题。这种“为获有效继承而必须对父类代码进行实质性修改的现象”就是所谓的继承反常（Inheritance Anomaly ）MY93 。继承反常这一概念是针对某种特定的语言机制而言的。图2.1 中采用“ method guards”同步机制，类Buffer2 可以不加修改地继承Buffer 的方法 put 和 get（其中新方法get2 为每次从缓冲区取出个元素）。而语言ACT+ （一种基于Actor 的语言 KL89 ）采用 Behavior Abstractions 机制，Buffer2 在继承 Buffer 时不可避免地要重新定义方法put 和 get，见图 2.2。下一节我们将讨论如何准确地理解继承反常现象，阐述本文的基本观点。3. 理解继承反常现象综合各种观点，要理解和解释继承反常现象，首先须正确区别inheritance层次和subtyping 层次及深刻领会二者的联系。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - 3.1 区别 Inheritance和 Subtyping Inheritance 是类（ class）之间的一种层次关系，而subtyping 是类型（ type）之间的层次关系。 Type具有类型检测（type-checking）的语义，可以利用谓词来定义，即满足该谓词的所有对象都具有这种类型；而 class 具有实例创建的语义，是产生实例的模板 （templates） 。每个 class 对应一种特定的type，这种 type 的谓词是该class 模板的一种规范；但反过来每个 type 不一定都对应一个class，因为一种谓词未必可以成为某个模板的规范WZ88 。class b_buf: ACTOR / b_buf is an Actor int in, out, bufSIZE; behavior: empty = put; partial = put, get; full =get; public: void b_buf() in = out = 0; become empty; void put() in+; / store an item if (in = out + size) become full; else become partial; void get() out+; / remove an itemif (in = out) become empty; else become partial; class b_buf2: b_buf / b_buf2 is a subclass of b-buf behavior: x_empty = put; x_one = put, get; x_partial = put, get, get2; x_ full = get, get2; / x_empty renames empty, x_partial redefines partial; x_full redefines full; public: void b_buf() in = out = 0; become x_empty; void get2() out += 2; / definiton of get2if (in = out) become x_empty; else if (in = out + 1) become x_one; else become x_partial; / The following re-defines the methods in b-buf. void put() in+; if (in = out + size) become x_full; else if (in = out + 1) become x_one; else become x_partial; void get() out+; if (in = out) become x_empty; else if (in = out + 1) become x_one; else become x_partial; 图 2.2 用 ACT+ 描述的有界缓冲区类b_buf，及其子类b_buf2 在面向对象语言中，class 是一个语法单位，它包含若干属性及方法的说明，每个class的实例共享这些说明。Type可看作是共有某些外部可观察（externaly observable ）行为特性的实例的集合，即type 实际上是一种对其元素的行为规范（对应以上所述的“一种谓词”America91 ） ，如抽象数据类型（abstract data types ）是较常用的行为规范技术。Subtype 是根据谓词来修改，而subclass 是根据模板来修改。Inheritance 属于后者，而subtyping 属于前者。Inheritance提供了一种类之间共享代码的机制。通过inheritance ，subclass 可重用（ reuse）superclass的代码。 P.America 指出 America91 ，通过 inheritance 进行代码共享不一定自动带来行为的特化（如引入或修改的新的属性和方法可能破坏原有的属性和方法赖以发挥作用的不变量）， 并认为应该用subtyping 而不是 inheritance 来特指行为特化。本文中subtyping 的概念满足可替换性原则(Principle of Substitutability)WZ88 ：An instance of a subtype can always be used in any context in which an instance of a supertype was expected.综上所述， inheritance 是在代码层次上作修改，而subtyping 是在语义层次上作修改。前名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 者是代码共享的一种重要途径，但不能保证subclass 能够继承 superclass 的行为；后者要求subtype 保持 supertype 的某种外部可观察行为（或语义行为），在规范一级共享，同代码没有关系。 Inheritance 层次关系可以理解为“is_similar_to ” （或“ like” ）的关系，而将“is_a”关系用在理解subtyping 层次关系更妥 （可以描述成 “从某种语义行为来看，B 是 A 的 subtype?每个 B 的实例 is_a A 的实例”）。3.2 渐增式继承Subtyping 要求 subtype保持 supertype的某种行为（可看作是一种不变量，比如同步约束） ，subclass 在增加新的属性或方法时，为了避免破坏这种不变量，难免要对从superclass 继承下来的代码进行扩展或修改。而这种扩展或修改很可能是重大的或实质性的，结果使得inheritance 层次从代码共享的角度看变得没有意义。这便是继承反常的（非形式）含义。那么什么样的扩展或修改算是重大的或实质性的呢？这是比较含糊的说法，以至于多种关于继承反常的说法使读者产生误解。如有些工作称可以避开继承反常 Meseguer93 LLNW96，而另一些工作则认为继承反常是不可避免的CRR98 。CRR98 在 inheritance必须是渐增式的假设下，给继承反常下了一个形式化的定义。按此定义， 先前人们声称对继承反常问题的解决都是部分的，即没有任何一种解决方案是彻底的。这是一个极端的定义，它所规定的渐增式继承不允许对继承下来的代码作任何形式的修改。为了对人们在解决这个问题上的努力有所区别，同时兼顾到不同的语言特征，我们有必要对“渐增式继承”采取较为灵活的解释。首先，对于不同的并发面向对象语言（COOL） ，渐增式继承的含义应该有所不同。如对基于 Petri 网的 COOL（Lakos95 BCC95 ） ，将子网（ Subnets）关系看作渐增式继承是恰当的，没必要苛求子类网中新增的部分与从父类继承的部分不相交。参考图3.1，N0是 N1、N2和 N3的子网， N1、N2和 N3渐增继承了N0。然而，这种子网关系的继承只强调了网结构（代码）的重用，而未顾及行为的重用。在顺序的面向对象程序设计中，代码的重用是inheritance 的一个主要目的， 而行为的重用几乎可以不去考虑， 因为方法之间最多只有调用关系，没有同步代码带来的同步约束，其它约束（如实时方面的约束）只是在特定情况下才考虑。对于并发面向对象的程序，情况就不同了，代码的重用固然是inheritance 的一个重要目的， 但行为的重用更突显其重要地位，也成为问题的焦点。行为的重用在COOL 中是由 subtyping 关系体现的。从前面章节的讨论可知，代码重用和行为重用之间的不兼容是产生继承反常的根源。因此，为了兼顾两种重用，在COOL 中严格区分inheritance 层次和 subtyping 层次成为一种趋势，许多语言设计了这样的机制，如CO-OPN/2 Biberstein97 。甚至我们认为，为方便不同的应用，一个COOL 支持多个不同的subtyping 层次是很有必要的。实际上，在多数（顺序的和并发的）面向对象语言中，至少有一个蕴涵的subtyping 层次：即supertype 的实例可接受什么消息，在其subtype 的实例中也可接受同样的消息（这是多态性的一种）。图3.1 ( N 1 ptN0,N 2pjN 0 及N3lcN 0)N3N2N0N1aaaabbbbccccb0b0b1b1至于要支持什么样的subtyping 层次关系，应根据应用的目标来确定，这方面人们已有名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - 许多工作 LS94 。作为一个例子，VB97 中基于封装（ encapsulation）和抽象（ abstraction）的思想利用分支双模拟等价（branching-bisimulation equivalance ）关系定义了Petri 网间的两个 subtyping 关系 (原文称为动态行为继承)，分别记为pt和pj，前者具有 blocking 语义（即限定 subtype 的实例只接受其supertype 的实例所能接受的消息），后者具有hiding 语义（即将 subtype 的实例中不属于其supertype 的实例所能接受的消息隐藏起来，看作内部活动）。在图 3.1 中，有 N1 ptN0，即在阻止N1中 b0发生的前提下，N1和 N0的动态行为（在分支双模拟的意义下）是一致的；同时N2 pj N0，即将 N2中的 b1看作内部活动，N2和 N0的动态行为是一致的。图中还有N3 l c N0，等价于N3pt N0 N3pj N0。面对不同的subtyping 关系，继承反常的多少是不相同的，CRR98 的定义中也注意到了这一点。进一步，我们还认为，对不同的subtyping 关系，“渐增式继承”的含义也应有所区分，这既有利于更客观地比较和评价人们提出的各种解决继承反常的方法，也利于在实际开发中更方便地实现相应的subtyping 关系。例如，对于在VB97 中，针对 subtyping 关系pt、pj和l c（参见图3.1）分别给出了相应的继承保持变换规则（inheritance-preserving transformation rules ） ，它们都可被包括在相应subtyping 关系的“渐增式继承”集合之中。3.3 理解继承反常（非形式定义）本文基于以下观点来理解继承反常现象（读者可结合第4 节的形式定义一起阅读）：（1）不同的语言机制有不同的继承反常现象，因此继承反常的定义是针对语言的（可参考第 2 节） 。（2）语言机制确定后，其class 和 type 系统就确定了，有什么样的inheritance 规则和什么样的 subtyping 关系也确定了。 每一个 class都有一个唯一的type 与之对应（可以是多对一） ，但一个 type 不一定有与其对应的class (参见第 4节中 type 函数的定义 )。（3） 我们把一个inheritance 规则理解为所有class 的集合上的一种先序（preorder） 关系。一组inheritance规则定义了一种inheritance层次关系，当一个class A 仅采用该组的inheritance 规则可构造出另一个class B， 则 A 和 B 之间就具有这种inheritance 层次关系（可对照定义4.4 中范畴 CR的定义）。 某个语言中由全部inheritance 规则定义的inheritance 层次关系称为该语言的完整inheritance 层次关系（可对照定义4.4 中范畴 CL来理解）。（4）一种 inheritance 层次关系实现某种subtyping 关系，如果任何具有这种inheritance层次关系的两个class对应的两个type 之间都具有这种subtyping 关系。在这里应注意的是：本文中，继承层次关系P 实现 Subtyping 关系 p，是指存在从关系P 到关系 p 的保序映射，不必要是双射（参见定义4.6，实现函子F 是从 Class 范畴映射到Type 范畴） 。大多数面向对象的语言都默认如下的Subtyping 关系：type （B）是 type （A）的子类型iff B 是 A 的子类（这里指在完整inheritance 层次关系下， B 继承 A） 。若对任何一种继承层次关系都这样定义其相应的Subtyping 关系， 自然它就实现这个Subtyping 关系。 在实用中， 可以对某一种特定的继承层次关系规定一种相应的Subtyping 关系（定义方法类似，也可参考第 5 节例 5.1.1） ，如 wz88 中所述的 4 种继承关系都可对应各自相应的一种Subtyping 关系。但在本文的理论研究中，不必规定任何一种继承层次关系都实现该语言中的某一Subtyping关系。（5）设 P 和 Q 是可以实现某种subtyping 关系 p 的两个 inheritance 层次关系，且P 包含Q。 A 是任何一个class。若在关系P 下， A 的任何 subclass B， 都存在与 B 有着 （对于 Subtyping关系 p）相兼容的 （即语义行为一致的）type 的 class C，使得在关系Q 下 C 是 A 的 subclass，则称在这种subtyping 关系下 inheritance 层次关系P 可继承归约到inheritance 层次关系Q。（这已经是一个半形式化的叙述了，完全非形式的说法很难准确表述，形式化定义参见定义4.7）对于某种 Subtyping 关系 p，两个 class B 和 C “具有兼容的type”意味着 type（B）是type（C） （在 p 下）的子类型，同时type（C）也是 type（B） （在 p 下）的子类型。本文中Subtyping 关系是一种先序关系（pre-order ） ，而非偏序关系（partial order ） （前者不要求反对称性），因此 B 和 C “具有兼容的type”不代表type（B）= type（C） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - 现举例说明两个继承层次之间“可继承归约到”关系的含义。设继承层次关系P 和 Q分别用继承规则集R/ 和 R 来刻画，满足R? R/? RL。这里，用RL=r1，r2， ，rn表示语言 L 的继承机制，其中r1，r2， ，rn为语言 L 的所有 inheritance 规则（参见第4 节） 。不妨设 R/=r1，r2，R= r1。假定对于类 A，B 和 C，有 r1，r2，这样在继承层次关系P 和 Q 下，对应于类A，B 和 C 的关系图可由图3.3.1（a）和（ b）表示。设 P 实现某种 Subtyping 关系 p2，因为 R? R/，所以 Q 也实现 Subtyping 关系 p2（参考第4节命题 4.1 和命题 4.2） 。设图 3.3.1（ d）表示在关系p2 下，对应于类型type（A） ，type（B）和 type（C） 的关系图。从该图可知，对于Subtyping 关系 p2，B 和 C 具有兼容的type，即满足 p2 以及 p2（参考上述讨论） 。这个例子中，在关系P 下，对 A 的子类 C，存在与 C 有（对于Subtyping 关系 p2 而言）相兼容的 type 的类 B，而在关系Q 下， B 也是 A 的子类。若这个命题对任何的A 和 C 都成立，就有：在 Subtyping 关系 p2 下，继承层次关系P“可继承归约到”继承层次关系Q。其实际含义为：对于由p2 所定义的行为继承关系（即Subtyping 关系）而言，继承层次关系Q 的实现能力足以替代继承层次关系P 的实现能力。在此例中，继承规则r2只是丰富了实现（由p2 所定义的）行为继承的手段（增加了可用性）。ACB(a) 在继承层次关系P 下type(A)type(B)type(C)(d) 在Subtyping 关系p2下type(A)(c) 在Subtyping 关系p1下type(B)type(C)ACB(b) 在继承层次关系Q 下图3.3.1（6）一种语言机制中可以存在多种subtyping 关系。每一种subtyping 关系都规定一种inheritance 层次关系为其相应的“渐增式继承”关系。这个“渐增式继承”关系一定是可以实现该 subtyping 关系的。这里， “渐增式继承”是一个相对的概念，意指“理想”的继承方式。例如，“只修改分离出来的同步代码而不修改方法体”的继承方式已经足够“理想”了，你可以将这种继承看作是“渐增式继承” ；但你也可规定“同步代码和方法体都不修改”的继承方式才是“理想”的“渐增式继承” 。本文中，“继承反常”的定义依赖于“渐增式继承”，因而也是一个相对的概念。“渐增式继承”概念的相对性有利于区分不同的研究对“继承反常” 问题的解决程度。（7）对某一种subtyping 关系， 若所有可以实现这种subtyping 关系的 inheritance 层次关系都可继承规约到该subtyping 关系的“渐增式继承”关系，则对于这种subtyping 关系，该语言没有继承反常（anomaly-free） 。 （参见定义4.8（2） ）“无继承反常” 意味着任何一种inheritance 层次关系可实现的行为继承层次（subtyping关系）都可由“理想”的继承方式（“渐增式继承” ）来实现。（8）若对于某一语言的所有subtyping 关系，该语言都没有继承反常，则这种语言不存在继承反常，否则就存在继承反常。（参见定义4.9）（9）对某一种 subtyping 关系，“渐增式继承” 关系的限制条件越放宽（即“渐增式继承”名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - 关系所包含inheritance 规则越多），继承反常越少（参见命题4.3） 。因为一个inheritance 层次关系都可继承规约到“渐增式继承”关系的可能性增大了。（10）对某一种subtyping 关系，若加强此关系的条件，而“渐增式继承”关系不变，则继承反常会减少（参见命题4.4） 。因为可实现这种subtyping 关系的 inheritance 层次关系变少了。下一节中将采用范畴论的术语对上述概念进行完全形式化的描述，其中 inheritance 层次关系对应一个Class 范畴， subtyping 关系对应一个Type 范畴。4. 定义继承反常现象范畴论 Peirce91ML71 的观点抽象层次较高，能帮助我们把握继承反常现象的本质，给其一个清晰且精练的形式定义。先介绍本节将用到的三个概念：范畴（category） 、子范畴（subcategory）和函子（ functor ） 。定义 4.1 一个范畴C 包含： （1）对象（objects） 集 ob C ； （ 2） 对每个对象有序对（A， B） ，相应有一个射 （morphisms）的集合 hom C（A，B） （若可从上下文得知C，可简记为hom(A，B） ） ，其中的射具有论域（domain）A 和余论域 （codomain）B； （3）对任何对象三元组（A，B，C） ，有一个从hom(A,B) hom( B,C)到 hom( A,C) 的映射：（ f,g）g f。C 中的对象和射满足以下条件：(C1) 若（ A,B ）（ C,D） ，则 hom(A,B) 和 hom(C,D) 不相交； (C2) 若 fhom( A,B) ，ghom(B,C)，hhom( C,D) ，则 (hg)f=h(gf)；(C3) 对应每个对象A 都有一个恒等射 1Ahom( A,A) ，使得对任何fhom( A,B) ，有 f1A= f，对任何 ghom(B,A) ，有 1A g= g。定义 4.2 范畴 D 是范畴 C 的一个子范畴，当且仅当（1）ob D ? ob C； （2）对所有A,Bob D， 有 hom D( A,B) ? homC ( A,B) ； （3） 对 Aob D， 和 1AhomC (A,A) 有 1Ahom D( A,A) ；（4）对 fhom D( A,B) ，ghom D(B,C) 及 g fhom C ( A,C) ，有 g fhom D ( A,C) 。若 D 是范畴 C 的子范畴，同时ob D = ob C，则 D 称为范畴 C 的宽子范畴（ wide subcategory ） 。定义 4.3 设 C，D 为范畴，从C 到 D 的一个函子F 包含： （1）一个从 ob C 到 ob D 的映射A FA； （ 2）对任何A,Bob C，从 homC ( A,B) 到 hom D( A,B) 有一个映射f F(f)。F应满足以下条件（C1）如果 gf 定义在 C 中，则 F(gf) =F(g) F(f)； （C2）F(1A)= 1FA。设（并发）面向对象语言L 中，所有 class 的集合为 ClassL，所有 type 的集合为TypeL。每一 AClassL是产生实例的一个模板，用instances(A) 表示 A 的所有实例的集合；对TTypeL，class A 实现 T 当且仅当? ainstances(A).aT。记 type(A) = T | A 实现 T （参见CRR98 ） ， 这里 为最大下界算符。 这里我们约定： 对任何 AClassL， 都有 type(A) TypeL。用继承规则集RL=r1，r2， ，rn表示 L 的继承机制，其中每一ri? ClassLClassL为一先序（preorder） 关系，即满足自反性和传递性。L 的所有 subtyping 关系表示为集合PL=p1，p2， ，pm，其中每一pi ? TypeLTypeL，也是先序关系。对任何pPL，我们把相应于p的渐增式继承用继承规则集Rp? RL表示。定义 4.4 设 R ? RL，范畴 CR定义为：（ 1）ob CR = ClassL； （2）对所有 A，Bob CR，hom（A, B）是由下列算法确定的最小集：（） 若存在 rR，使（A, B）r，则 rhom( A, B)；（）若对Cob CR存在 r1 hom(A, C)，r2 hom(C, B)，则 r2r1hom(A, B)（）反复使用（）、 （）。易验证 CR符合定义4.1。称 CR为一个基于L 的 Class范畴（在不致混淆的情形下，简称为Class范畴）。若 R= RL，则称 CR为基于 L 的完全 Class 范畴（对应语言L的完整 inheritance 层次关系），记为 CL。命题 4.1 设 R?RL，R/? R， R 定义的 Class 范畴为 CR，R/ 定义的 Class 范畴为 CR/，则CR/是 CR的子范畴，并称之为CR的子 Class 范畴。证明：由定义4.4，对任何A, Bob CR=ob CR/，hom CR/ (A, B) ? hom CR ( A, B)。推论 4.1 任何 R ? RL定义的 Class 范畴 CR都是 CL的子 Class 范畴。定义 4.5 设 p PL，定义范畴Tp为： （1） ob Tp = TypeL； （2）对任何 A，Bob Tp，(A, B)homTp(A, B) 当且仅当(A, B) p。称 Tp为一个 Type 范畴，它实际上也是一个先序集范畴。定义 4.6 设 CR为一个 Class 范畴，Tp为一个 Type 范畴，F 为满足以下条件的映射（从 ob CR到 ob Tp） ：对任何 Aob CR，FA=type(A)。若 F 是从 CR到 Tp的函子（参考定义4.3） ，则称CR实现 Tp， F 为实现函子。 （参考图4.1）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - 命题 4.2 设 CR/ 是 CR的子 Class 范畴， CR实现 Tp，则 CR/ 也实现 Tp。证明： CR/ 实现 Tp可使用与 CR实现 Tp相同的实现函子。定义 4.7 设 CR是 CR/ 的子 Class 范畴，Tp为一个 Type 范畴，CR/ 实现 Tp (由命题 4.2，CR也实现 Tp)，F 为实现函子。称对于Type 范畴 Tp，CR/可继承归约到CR，记为 CR/?pCR，当且仅当对任何A, B/ob CR= ob CR/，若存在 f /hom CR/ ( A, B/ )，则存在 fhom CR ( A, B)， 使得(FB，FB/ ) homTp(FB，FB/) (FB/，FB)homTp(FB/，FB)。 （参考第 3.3 节（5）及图 4.2）注：(FB，FB/ ) homTp(FB，FB/)意味着 type（B/）是 type（B） （在 p 下）的子类型，而(FB/，FB)homTp(FB/， FB)意味着 type （B） 是 type （B/） （在 p 下）的子类型。 (FB， FB/ ) homTp(FB，FB/) (FB/，FB) homTp(FB/，FB)说明对于Subtyping 关系 p，B 和 B/“具有兼容的type” 。定义 4.8 （1）设 R ? RL且 CR实现 Tp。若对于任何CR/，CR/ 实现 Tp，都满足CR/?pCR，则称在继承规则集R 作用下，对于由p 确定的子类型关系，L 无继承反常（anomaly-free） 。（2）若在渐增式继承规则集Rp作用下，对于由p 确定的 subtyping 关系， L 无继承反常，则称对于由p 确定的子类型关系