Java*中运行时泛型的高效编译与实现技术

理论计算机科学电子笔记138（2005）95-116www.elsevier.com/locate/entcsJava*中运行时泛型的高效编译米尔科·维罗利DEIS，Universit`adegliStudidiBolognavia Venezia 52，47023 Cesena，Italy电子邮件地址：mviroli@deis.unibo.it摘要在Sun Microsystems呼吁将泛型添加到Java编程语言中的几年之后，JDK 1.5将最终提供对泛型的编译时支持。然而，与当前的.NET公共语言的实现不同的是，没有提供对泛型的运行时支持（通常也称为类型参数的重新定义），这导致了许多众所周知的不足之处，这些不足之处可能是至关重要的。 在本文中，我们提出了EGO编译器（精确泛型的需求）。这是与Sun Microsystems合作开发的一个项目的结果，该项目作为一个插件以平滑的方式提供运行时泛型，而不需要对JVM或任何其他运行时支持进行任何更改。核心解决方案是基于类型传递风格的代码的复杂转换，其中运行时类型信息根据需要自动创建，尽可能限制运行时开销，同时保持与遗留Java代码的互操作性。我们介绍了这一发展的主要方面，从基本设计到实施和部署问题。本文讨论了在主流编程语言上实现高级类型系统时提出的许多相关问题，并对一些有效的实现技术进行了探讨。关键词：Java，参数多态性，编译技术，运行时类型1介绍尽管面向对象编程语言的高级类型系统的研究仍然是一个非常活跃的领域，但我们正在目睹主流编程语言发展的巨大惯性。因为*这项工作得到了MIUR（意大利教育、大学和研究部）PRIN 2004项目“可扩展对象系统（EOS）"的部分支持。1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.09.01396M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）95在实际评估语言扩展时，它们的广泛传播、诸如性能和表达性之类的通常方面并不是唯一的关注点相反，通常会出现许多其他技术问题，包括例如与遗留应用程序的兼容性和部署问题，这是从未看到有希望的提案进入主流的原因之一。事实上，理论和实际建议之间仍然存在很大差距，这就要求研究和评估普遍适用的实施和部署技术。朝着这个方向，我们考虑在Java编程语言中的泛型类型的运行时支持的情 况 期 待 已 久 的 Java 泛 型 扩 展 最 终 与 JDK 1.5 （ 也 称 为 J2SE5.0 ，http://www.java.sun.com）一起发布，但没有运行时支持，因此导致相当不完整的实现-参见例如[14，2，19]。由于泛型类型只是作为编译时抽象来引入以增强安全性，它们从不进入运行时域，因此它们几乎不与重要的Java框架集成，例如序列化，持久化，JavaBean等-更不用说与标准Java类型管理的有限集成（例如，关于向下转换和运算符instanceof）。此外，运行时泛型被证明可以支持跨平台编程习惯用法的开发，例如表达式问题[16]。尽管如此，运行时泛型已经在竞争对手的框架中实现了，.NET [10，9，15，3]。有几个原因导致Sun Microsystems发布了这个解决方案，其中最重要的是处理全局JVM扩展的困难，以及迄今为止编译时解决方案的不足— 无论是在性能、兼容性还是与Java框架的平滑集成方面在本文中，我们提出了EGO编译器（精确泛型按需）。这是与SunMicrosystems合作开发的一个项目的结果，该项目的目标是评估对运行时泛型的平滑支持，这不需要在JVM或Java Java编译环境（JRE）的任何其他组件上进行更改我们设想和开发的解决方案是基于类型传递风格[19，18]的复杂代码转换-也称为类型参数的重新定义（或提升[12]）-其中运行时类型信息根据需要自动创建，并缓存以供将来使用。我们的解决方案的主要特点包括（i）运行时开销在10%以内，（ii）与GJ [14]相似的兼容性和互操作性，（iii）作为一个单独的（和小的）模块添加到Sun为了清楚起见，在M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）9597下面我们参考gjavacfor Sun虽然编译时方法通常用于非常简单的翻译-类似于GJ的泛型[14]，内部类[4]，自动装箱，JDK 1.5中的for-each循环-我们在这里展示了即使是复杂的翻译也可以以令人满意的方式解决性能和兼容性问题特别是，我们的工作开发和改进了我们在[19，18]中提出的LM翻译器设计。EGO设计中引入的主要创新包括：（i）按需创建类和方法的描述符，最小化空间开销并允许多态递归[19];（ii）优化泛型子类化的处理，保留Java单独编译属性;（iii）完全处理参数方法的本文的其余部分如下：第2节描述了运行时泛型类型问题的基本背景;第3节讨论了EGO编译器的主要设计选择，包括翻译模式和相应的运行时效果;第4节讨论了在Sun的gjavac编译器中的实现以及部署问题;第5节介绍了初始性能结果;第6节将EGO翻译策略与一些严格相关的建议进行了比较;第7节提供了总结性评论和对未来工作的2背景在Sun Microsystems呼吁将泛型添加到Java编程语言[ 11 ]几年之后这种实现基于GJ [14]：泛型类型和方法用于通过避免依赖向下转换来增强安全性，然后它们被编译器简单地擦除到相应的单态字节码中。实现的解决方案非常简单，因为不需要更改字节码规范或JVM实现。此外，编译后的代码可以轻松地与现有的Java应用程序进行互操作，从而简化了将应用程序转换为泛型版本的任务。1我们的工作实际上是在引入变量参数类型之前开发的[7]添加到JDK 1.5的通配符机制中[17]：我们实际上是指在添加通配符之前的Sun在下文中，我们将从这种机制中抽象出来，因为它对这里研究的运行时问题起着主要的正交作用98M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）95然而，这种方法有一个公认的问题[14，2，18]：泛型从未被视为对象的运行时类型，因此任何试图恢复对象类型的尝试总是产生相应的单态版本。例如，当使用Java API通过网络发送List String>对象时，接收方读取Object元素，并且只能将其向下转换为List-即原始类型列表[6]。试图将其向下转换为List< String>（或List< String>）会发出编译时警告：这样的转换在运行时永远不会失败，但稍后可能会产生令人困惑的异常。请参见以下代码：//让列表持久化列表字符串>String s = new String s>（10）;...ObjectOutputStre amoos=newObjectOutputStr eam（. . . ）;oos.writeObject（l）;...//另一个应用程序读取列表ObjectInputStreamois=new ObjectInputStream（...）; Objecto=ois.readObject（）;List> l=（List>）o;//发出警告...int i=l.get（0）;//抛出ClassCastException在这种情况下，对象o只是一个List，任何向下转换都是基于无法验证的列表内容的假设而插入的（事实上，在上面的代码中是错误的！）。 在翻译后的代码中，变量i被赋值给表达式（NULL）l.get（0），这会引发ClassCastException。 读者应该注意到，列表中的给定元素实际上可以在以后访问，例如。 由一些独立的代码，不能预期访问元素可能会导致异常-这被程序员认为是所谓的堆污染。最后，编写发出这些安全警告的代码是糟糕的编程实践.程序员被允许明智地使用泛型类型，直到它们由于某种原因被扩展，从那时起坚持使用它们的单态版本：这明智地减少了泛型在许多相关Java应用程序中的优势。原则上，避免这个问题的最合理的解决方案是扩展JVM和字节码规范，以便将泛型类型视为第一类类型：例如，C#编程语言中的泛型建议[9，15]或Java的PolyJ建议[8]中所采用的方法。然而，这种解决方案很难实现，因为JVM中的泛型可能会影响运行时的几个关键和复杂的方面，例如即时编译和优化。更重要的是，它的部署也会更加困难，因为它需要全世界所有的Java安装M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）9599完全更新，并且还将使正在进行的应用程序开发转向泛型的任务复杂化替代的可能性进行了评估，其功能对运行时支持和部署的影响有限一方面，一些方法是基于在加载时将通用源代码转换为标准代码的思想[1]。这需要提供一个不同的类加载器，而不是更改编译器，只能通过JRE的补丁安装。另一方面，已经提出了纯翻译方法，其目的是仅通过编译器产生标准字节码来提供泛型例如Pizza [13]的代码扩展技术，其优化版本NextGen [2]以及LM translator [19，18]的类型传递方法尽管这些建议原则上以其易于部署而吸引人，但它们最初被认为是“玩具”解决方案，有时以不适当的方式解决诸如性能和向后兼容性之类的3设计在现有的翻译技术中，LM翻译器的框架似乎提供了一个足够灵活的环境，用于将效率和有效性推向主流版本所需的水平该方法的主要思想是在创建对象时将泛型类型具体化为一个实际的进一步参数（称为描述符这种方法的关键方面，在函数设置中称为类型参数提升[12]，是动态创建此类描述符所需的开销。[19]中的工作表明，所有需要的描述符都可以在加载利用它们的泛型类时创建，从而大大减少了对执行时间的影响。通过这个想法的发展，EGO编译器已经开发出以下功能：• 懒惰。描述符是在第一次需要时创建的，而不是在加载时创建的。这防止了对通常的Java类加载动态的任何干扰，并避免了无限多态递归的问题[19]。• 等网站和资源类型传递转换模式不仅适用于泛型类，而且适用于泛型方法（也处理动态分派）、泛型内部类、接口和数组。• E.效率。一些技术被引入来处理效果-100M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）95类对X，Y>{Xx;Y y;Pair（X x，Y y）{ this.x=x; this.y=y;}public void run（）{返回intn = nums（x. nums（））;}public void run（）{return new Pair Y，X>（y，x）;} Pair Z，Y> chgFirst（Z z）{ returnnew Pair Z，Y>（z，y）;} Pair X，Z> chgSecond（Z z）{return reverse（）.chgFirst（z）.reverse（）;}Pair X，X> dupFirst（）{ returnchgSecond（x）;}}Fig. 1. 使用泛型例如与Java和GJ代码的互操作性以及对单独编译的支持• 很有效率。获得良好的翻译代码性能的需求普遍影响到翻译的所有方面，直到EGO成功地满足其目标的开销限制。• 实现模块化。EGO编译器被实现为gjavac的模块化扩展，包括在泛型类型注释之后和类型擦除之前应用于抽象语法树（AST）的进一步翻译步骤。在本节中，我们将重点描述由EGO编译器实现的翻译的主要方面遵循标准方法[14，2，19，18]，我们通过示例详细介绍了这种转换，展示了如何将通用源代码转换为通用源代码，并添加了让对象携带完整运行时类型所需的代码作为一个正在运行的示例，我们考虑图1中报告的类，它表示一对通用对象。类型变量X和Y抽象了该对中第一个和第二个元素的类型，由字段x和y表示。方法show（）举例说明创建一个实例化的对Pair String，String>，而方法reverse（）创建一个对（Pair Y，X>），其实例化取决于X和Y的当前赋值。其他三个方法chgFirst（）（更改对中的第一个元素）、chgSecond（）（更改对中的第二个元素）和dupFirst（）（复制第一个元素M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）95101public abstract classC {public_D p[];//类型参数public_Df[];//朋友描述符public_D encl;//封装描述符public int id;//唯一标识符public static class Cla extends_D {//Class descriptorpublic Cla h[];//超类链public Class cl;//当前java.lang.Classpublic int depth;//继承层次结构中的DephtpublicCla[] int;//接口描述符publicVPMT vpmt;//虚拟参数方法表...publicboolean isInstance（Object）{.} //类型测试publicObject cast（Object o）{.}//Downcasts}publicstatic class Arr extends Cla {.}//数组描述符public static class transmitted_D{.} //方法描述符public Met的单元格满足;.}public static class String extends_D {.}//方法描述符publicstatic interface Parameter {//Facility to retrieve descriptor Cla$getD（）;}public staticclass VPMT{//public static class Class Class{//描述符管理器publicstatic Cla_DObj;//对象描述符publicstaticManmanager=newMan（）;//单例管理器}图二. 用于管理描述符的第二个是泛型方法的定义和使用3.1描述符的管理类型传递方法的显著特征是类型参数被具体化为定义它们的泛型构造的实际参数。特别地，EGO将描述符与每个泛型抽象（类、方法、数组等）相关联。这是一个运行时实体（Java对象），代表一个实例化环境，也就是说，保存类型参数的实例化信息，泛型抽象的标识信息，以及出于性能原因而在EGO中，描述符被实现为库类D的对象（在包ego中），它支持翻译代码的执行。其一般结构如图2所示。类D是一个抽象基类，用于：（i）类描述符（Cla），用于处理泛型类、接口和内部类;（ii）数组描述符（Arr）;102M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）95以及（iii）方法描述符（Met），用于处理泛型方法-以及稍后描述的MetCell类。每个这样的子类被定义为D的静态内部类。其他一些静态内部类也被定义为提供各种工具，例如类VPMT（虚拟参数方法表），用于在动态调度的情况下提供方法描述符的管理[18]，以及类Man，管理器跟踪在当前运行时创建的描述符。所有描述符都保持对类型参数（D.p）描述符的引用，对于友元类型-依赖于当前实例化- （D.f），用于封闭类型-内部类的外层类或方法的接收者-（D.encl），以及一个唯一的标识符D.id，一旦创建描述符，管理器就会将其关联特别是，类描述符还具有一个描述符数组，包含超类型链（D. h），当前类型的java.lang.Class表示（D.cl），继承链中当前描述符的深度（D.depth），所有实现接口的描述符集（D. int），最后是对VPMT的引用（D.vpmt）。由于描述符是相当复杂的结构，因此很容易认识到为什么必须仔细研究实现以最小化创建和处理它们的成本3.2转换泛型类我们在这里详细分析了泛型类是如何翻译的，提供了相当普遍的见解的行为的EGO编译器。翻译类Pair-暂时忽略方法chgFirst（）、chgSecond（）和dupFirst（）— 这将导致图3中的代码。除了方法、字段和构造函数的实际翻译之外，翻译器还添加了一些周围的代码。这包括严格依赖于类Pair的描述符管理逻辑，因此需要存储在类中以支持单独编译。受保护的实例字段$d存储表示对象运行时类型的描述符，公共实例方法$getD用于从外部访问它。静态方法$crCLA、$C和$O$CLA提供了创建和访问描述符的工具，静态字段$d c用于缓存当前类中使用的描述符，最终$depth跟踪类Pair在泛型类层次结构中的深度3.2.1一般翻译模式我们通过实际描述类中定义的翻译来提供有关此周围代码的详细信息构造函数被添加了一个D.Cla类型的参数，其内容将存储在字段$d中：这意味着M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）95103class Pair X，Y>实现ego。_ D.参数{//类转换X x; Yy;对（自我。_ D.Cla $d，Xx，Yy）{this.$ return$d;这x= x;这个.y= y;}public void run（）{返回new Pair String，String>（（ego._D.Cla）$C（1），getString（）; getString（）;}public void run（）{return new Pair Y，X>（（ego._ D.Cla）$O$CLA（$d，0），y，x）;}//返回列表公众的自我D.Cla $getD（）{//调用描述符返回$d;}自我保护D.Cla $d;//局部描述符私人的静态自我D[] $d_c=新自我。D[2];//在代码中使用的描述符protectedstatic int $depth = 1;//层次结构中的深度//创建对描述符公共静态自我。D.Cla $crCLA（自我。_ D.Cla[] x0）{. 个文件夹//C语言描述符私人的静态自我public int findDuplicate（int findDuplicate）{如果（$d_c[pos]！= return $d_c[pos];switch（pos）{//Stringcase 0：return $d_c[pos]=ego._C. String（String）;//对String，String>case 1：return $d_c[pos]=$crCLA（new ego._ D.Cla[]{（ego._ D.Cla）$C（0），（ego._ D.Cla）$C（0）}）;}返回null;}//使用JavaScript私人的静态自我D $O$CLA（自我）public int findDuplicate（intfindDuplicate）{如果（desc.h！= null）desc = desc.h[desc.depth-Pair.$ depth]; if（desc.f[pos]！= return desc.f[pos];public void run（）{//对Y，X>case 0：return desc.f[pos]=$crCLA（new ego._D.Cla[]{desc.p[1]，desc.p[0]}）;}返回null;}}图三. 类Pair104M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）95包含有关当前实例的运行时类型的信息，这些信息是从调用构造函数的客户端传递来的。方法show（）和reverse（）描述了这种一般类型的具体化模式新对T，R>（x，y）-->新对T，R>（/* 描述对于配对T，R>*/，x，y）即，适当的表达式被添加为负责高效地创建/检索描述符的第一参数。就访问适当的描述符而言，泛型类型可以有两种不同的类型：（i）它们可以独立于当前的泛型实例化，例如方法show（）中的类型Pair String，String>，我们称之为闭合（C）类型，或者（ii）它们可以包括作用域的类型变量，例如方法reverse（）中的Pair Y，X>，我们称之为开放（O）类型。这两种类型需要不同的管理，如下所示。23.2.2处理封闭类型类中的封闭类型是静态已知的：它们可以在类加载时创建，如LM [19]。然而，更好的策略是只在第一次实际需要时创建它们，在以后的访问中重用它们。为了实现这一点，作为第一步，翻译器收集并枚举要编译的类的所有封闭类型请注意，因为类型参数也是由描述符描述的，所以它们也要在封闭类型列表中考虑。在图3的例子中，这个列表由类型String和Pair String，String>组成。作为第二步，翻译器添加静态数组字段$d c，它将包含这些封闭类型的描述符，以及用于访问它们的方法$C特别地，这个方法被称为在$d c中传递槽位置：如果槽当前不是空的，则简单地返回现有的描述符，否则描述符将被创建并存储在槽中这个创建是依靠方法$crCLA获得的，该方法接收关于类型参数的信息并产生相应的描述符。最后，翻译插入一个表达式的的种（自我。D.Cla）$C（i）在代码的每一个需要第i个描述符的地方。请注意，封闭类型的这种管理在任何使用泛型类型的客户端中都是必要的，而与它是否是泛型无关。[2]我们把[19，18]中被称为绑定类型的东西称为开放类型：受[15]的启发，我们相信“开放”这个词M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）951053.2.3处理开放类型开放类型的管理方式类似，但具有更高的间接级别。 事实上，Pair Y，X>的参数不是静态已知的，而是取决于类的当前实例化：例如，在PairString，String>上调用reverse（）会导致Pair String，String>的创建，从而将String替换为Y并将String替换为X。为了处理这种情况，当编译泛型类时，翻译器首先收集并枚举它内部的所有开放类型-在我们的示例中只有类型Pair Y，X>。 因此，类的实例化与一个所谓的友元类型列表[19]，它是通过将实例化传播到类中的开放类型而获得的封闭类型。例如，类型Pair String，String>与唯一的友元类型PairString，String>相关联--通过从类Pair X，Y>中的开放类型Pair Y，X>替换获得。转换的第二步创建方法$O$CLA，用于访问友元类型的描述符为了将一个类型链接到它的友元类型，我们让一个描述符携带它的友元类型的描述符数组，存储在字段D.f中。因此，方法$O$CLA被构造为接受一个描述符和一个槽位置，从而产生相应友元类型的描述符特别地，对于方法$C，如果槽不为空，则仅访问它，否则将创建一个新的描述符在我们运行的示例中，只能访问插槽#0：通过传递Pair String，String>的描述符，它返回例如PairString，String>，它是通过考虑参数desc.p[0]和desc.p[1]来构造的-即，X和Y的当前实例化。最后，翻译者插入表达（ego. D.Cla）$O$CLA（$d，i）当需要类的当前描述符$d的第i个开放类型3.2.4双缓存描述符在静态字段$d c和局部描述符的实例D.f中缓存描述符提供了快速检索描述符的问题的解决方案：在第一次访问之后，检索描述符的成本与访问数组的元素一样-通常比创建对象快一个数量级[19]。尽管如此，第一次需要这样的描述符时，它必须通过方法$crCLA创建。为此，我们还依赖于LM translator的全局缓存技术，也就是说，不是每次都创建描述符，而是将它们注册到管理器D.Man中-使用称为hash-consing的技术（参见例如[15]）。通过利用哈希表，管理器能够以有效的方式识别描述符是否已经创建（例如，通过应用的另一类106M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）95并且在这种情况下将现有的一个返回给请求者。实际上，这种双重缓存技术不仅优化了时间性能，而且还保证了很小的空间开销，因为实际上只保留了一个泛型类型的描述符这种管理的细节存储在类D.Man和方法$crCLA中，为了简洁起见，这里没有报告，因为它们与[19]中已经讨论过的那些类似。只需注意，描述符在运行时被收集到一个集中的表结构中，并在需要时填充，并且被从泛型类和需要利用泛型类型的客户端类创建的对象引用3.3翻译的其他方面使我们的翻译方法成功的有趣和关键问题实际上包括泛型类以外的其他方面，我们在这里简要描述。然而，为了简洁起见，我们省略了泛型内部类、接口和数组的管理，这与泛型类的管理类似。3.3.1运行时类型信息当前的原型的EGO编译器已经开发的目标是评估的可实现性和性能的类型传递方法。然而，语言的语法和语义与GJ [14]相同，这意味着运行时类型的信息从未被实际利用（例如：向下转换和类型测试仍然使用GJ的擦除方法进行转换）-这就是为什么我们的Pair示例忽略了这些方面。然而，[19]中讨论的访问和利用描述符的技术适用于EGO，无需修改。例如，让v代表用于访问Pair String的描述符的表达式，String>，我们有翻译：o instanceof Pair String，String> --> v.isInstance（o）（Pair String，String>）o-->(Pair）v. cast（o）方法isInstance和cast（类D.Cla）简单地尝试通过接口D访问o<其他类型的运行时内省，例如，支持持久性所需的那些要素也同样实现。M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）951073.3.2处理继承一个泛型类扩展另一个泛型类的情况实际上比[19]中考虑的要棘手。为了简单起见，我们考虑引用声明：类D< X，Y> extends C< X>{.}限制空间开销是我们项目的一个关键目标，因此，我们必须确保从泛型类创建的任何对象最多携带一个描述符。因此，翻译将使只有C声明额外的字段$d：D不会用一个新的字段来掩盖这个定义，而是简单地利用C类型D T，R>的实例将被传递类型D T，R>的描述符，例如，通过收集D但是，如果由于某种原因，在这样的对象上调用了C的方法m--或者是因为在D中调用了super，或者是因为D没有覆盖m--那么m的代码可能会访问当前描述符的某个朋友，假设它是C T>的描述符，而不是！为了有效地解决这个微妙的问题，我们让每个描述符携带从其类型向上的继承链（D.Cla.h），以及它在该链中的位置（D. Cla.depth）。此外，我们让每个类在静态字段$depth中携带它在链3中的位置。然后，通过利用这两个值，方法$O$CLA中的第一条指令获得了方法m中要考虑的正确描述符-参见图3。3.3.3泛型方法泛型方法，如类Pair X，Y>中的chgFirst（）和chgSecond（），与泛型类的处理方式类似类D.Met的方法描述符具有参数（D.p）和友元（D.f）的描述符，作为类的描述符，并将接收相应调用的类型的描述符存储在D.encl方法描述符在调用时传递给方法，它们可以是关闭的或打开的，分别通过方法$C和$O$MET访问，并且可以有友元类型和友元方法。但仍有两个主要的复杂情况出现。一方面，方法描述符应该在其类中携带方法的唯一标识符：在单独的编译设置中，没有办法让客户端知道这个标识符-任何一代的唯一标识符都应该是本地的，并且在每次重新编译类时更新，而客户端无法跟踪它。因此，如果没有接收者类的帮助，客户端无法创建具有全局有效性的方法描述符为了有效地解决问题，客户需要-3这是通过将$depth赋值给顶部泛型类中的1，并在每个子类中增加它来实现的：例如在D中，我们有$depth=C。深度+1。这种管理允许在链中插入和删除类，而不需要全局重新编译。108M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）95class Pair X，Y>实现ego。_ D.参数{...对chgFirst（ego._ D. Me tC ell$md，Zz）{$d.compDyn（$d.h[0]，$d，1，0）;returnnewPair< Z，Y>（（ego._ D.C（a）$C（2），z，y）;} Pair X，Z> chgSecond（ego._ D.MetCell $md，Z z）{$md.compDyn（$d.h[0]，$d，0，1）;返回reverse（）。chgFirst（（ego._ D.M et Cel l）$O $ME T（$md. m∈t，0），z）。return（）;}public void run（）{returnchgSecond（（ego. _D. Me tCe ll）$O$C LA（$d，2），x）;}}见图4。 类Pair实际上处理方法描述符的包装器，而不是方法描述符。这些被称为方法单元，由类D.MetCell实现。在调用时，客户端传递一个包含原型描述符的方法单元，该原型描述符第一次接收调用的方法使用该信息来完成原型，并在单 元 中 存 储 适 当 的 方 法 如 图 4 所 示 ， 这 个 任 务 是 通 过 方 法D.MetCell.compDyn（）实现的，为了简洁起见，没有报告其细节。第二个复杂性是由于动态调度。正如在[18]中广泛讨论的那样，直到正确的方法被动态解析，才知道要传递的实际描述符用于处理此问题的技术使类描述符携带对其VPMT的引用-一个包含对方法描述符的引用的表，并且其中每个描述符在该表中的位置在 相同的遗传链。然后，实际传递的方法描述符对应于接收方的静态类型：方法D.MetCell.compDyn（）的另一个任务是在实际接收方的VPMT中查找适当的方法描述符M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）951094实施、部署、互操作性4.1EGO在编译器应用鉴于我们的翻译方法的性质，合理的做法是利用gjavac编译器（1. 5版）中现有的对泛型的支持，并将EGO部署为它的模块化扩展。因此，EGO翻译被实现为gjavac这相当于产生额外的方法、字段、形式参数，并在涉及泛型类型的地方更改表达式。因此，EGO实现被认为是一个单独的模块，可以很容易地添加到现有的编译器中，也可以简化更新到新的gjavac版本的任务。编译器的现有步骤如下：（i）解析，在命令行中指定的所有文件的源代码被解析，为它们中的每一个创建一个AST，该AST被插入到待编译的树的队列（ii）属性，每个AST的每个节点都注释有关于其（通用）类型的信息，创建用于感兴趣的编程结构的符号，并执行语义检查以控制程序是否格式良好和类型化4;（iii）擦除，根据GJ翻译[14，5]，每个AST都被替换为擦除版本;（iv）代码生成，产生二进制代码。在属性和擦除之间调用EGO模块，通过以下步骤翻译AST：• 执行收集阶段，该阶段遍历泛型类的树并检索封闭和开放类型/方法的列表。在这样做时，必须特别小心，以便正确填写这些列表，例如，如果Pair String，String>是一个封闭类型，那么String本身将被添加为封闭类型，如图3的示例所示。• 执行装饰阶段，向AST添加与周围代码对应的所有子树：附加方法、字段和形式参数。这些子树被构建为已经被注释，并且新的所需符号被添加到由编译器管理的符号表中：以这种方式，这些新的子树与现有属性一致，因此不需要全局重新属性。• 最后，执行进一步的遍历，该遍历转换涉及泛型类型上的运行时信息的所有表达式，例如另外，如果要编译的源文件利用了另一个类的功能，它也会被解析并插入到队列中。110M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）95翻译表达式new Pair< String，String>（..）（<$C（1），..）.注意，通过这个实现，gjavac的解析、属性、擦除和代码生成的现有阶段保持不变：对gjavac源代码所需的唯一更改是在属性和擦除之间的主循环中调用EGO4.2部署目前，EGO编译器部署了两个jar文件。一个包含编译器本身，它将通过适当的脚本调用另一个是一个17KB的库，包含类D及其子类的实现：当编译器被调用时，或者当编译器生成的代码被执行时，这个jar这意味着任何使用EGO创建的应用程序都将与这个jar一起发布，然后可以将其视为插入JRE的系统库，或者作为应用程序本身的一部分。读者应该注意到，这种部署比任何其他支持运行时泛型的解决方案都不那么重要，这些解决方案需要在JVM中进行更改，在JRE的类加载器中进行更改，或者使用代码专门化来4.3与遗留Java代码的互操作性GJ和JDK的1.5版本的设计选择的主要原因之一与互操作性有关：不仅用户根本不需要更改他们的JRE，而且应用程序可以优雅地转换为他们的泛型版本，因为遗留字节码将特别是，就标准JVM而言，泛型类的字节码等价于其单态版本的字节码。因此，为了保持相似的属性，这在主流编程框架的扩展上下文中非常关键，EGO必须具有等效的互操作性属性。更深入的研究表明，在当前的gjavac中，类的签名在泛型和擦除之后并没有完全改变，但可能会有一些额外的桥接方法-用于适应重写，如[14，13]所述这意味着遗留应用程序实际上可能通过Java检查的内省来揭示这显然被Sun开发人员认为是一个次要方面。相应地，对于EGO来说，保留类签名类似于gjavac的签名是足够的，对新方法（和字段）的添加取模。这是通过适应上一节M. Viroli/Electronic Notes in Theoretical Computer Science 138（2005）95111class Pair X，Y>实现ego。_ D.参数{...//桥接到Pair Object，Object> Pair（X x，Yy）{这个（（ego._ D.Cla）$C（0），x，y）;}//EGO翻译对（自我。_ D.Cla $d，Xx，Y y）{...}//桥接到Pair< Object，Objectct>。ch gF ir st Pair Z，Y> chgFirst（Z z）{returnthis.chgFirst（（e go. _D. M etC el l）$C（1），z）;}//EGO翻译对chgFirst（ego._ D. Me tC ell$md，Zz）{...}}图五. 桥梁建造者和方法利用与GJ类似的桥接技术：需要额外参数的构造函数和方法也保留在其原始版本中，这只是将调用重定向到具有额外参数的翻译版本，传递默认描述符。考虑图5中报告的类Pair X，Y>的翻译版本的细节。如果一个遗留的Java代码创建了一个pair，它会利用构造函数的两个参数：由于我们的桥接技术，这相当于创建一个pair对象，携带Pair Object，Object>-的描述符，方法也是如此。这种技术保证了EGO与GJ具有相同的互操作性-事实上，参数的数量