双重分派：增强类型化面向对象语言中的动态重载与协变专门化的方法

理论计算机科学电子笔记138（2005）59-78www.elsevier.com/locate/entcs将双调度转换为单调度洛伦佐·贝蒂尼DipartimentoodiSistemieInforormatica，Universita`diFirenze，Via Lombroso 6/17，50134 Firenze，Italy{bettini，capecchi，venneri}@dsi.unifi. It摘要类型化面向对象语言的可扩展性和可重用性的目标提出了双重分派的要求不仅根据接收器的运行时类型（单调度），而且根据参数的运行时类型动态选择方法的机制。然而，许多主流语言，例如，C++和Java都没有提供，只能采用单调度。在本文中，我们提出了一个通用的技术，增加双重分派作为一个类型安全的语言功能，从而产生动态重载和协变专门化的方法，而不扩展基本语义。为此，我们引入一个玩具的核心语言，扩展到一个完整的形式（非封装）多方法。然后定义了一个从多方法到核心语言的翻译算法，该算法仅使用静态重载和单分派的标准机制来实现双分派作为一个主要特性，我们的翻译保留了类型安全性，它既不使用RTTI也不使用类型向下转换，并且在方法选择过程中不会引入关键的开销。关键词：双调度，多方法，动态重载，程序转换。1引言双重分派是动态选择方法的能力，不仅根据接收器的运行时类型（单分派），而且根据参数的运行时类型（当考虑所有参数时，我们有多个分派）。虽然双重分派是一个古老的概念，在文献中被广泛研究，但许多主流语言都没有提供这种强大的机制;由于缺乏这种机制，程序员被迫求助于RTTI（运行时类型信息）机制和if语句来手动探索对象的运行时类型，并进行类型向下转换，以便根据其运行时表示强制查看对象。事实上，在许多1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.09.01160L. Bettini等人理论计算机科学电子笔记138（2005）59在这种情况下，这些方法是解决语言中缺乏双重分派的必要解决方案[19]。面向对象的设计不鼓励这些技术，因为它们破坏了可重用性，并逃避了静态类型检查的约束。更干净的解决方案，如访问者模式[16]，仍然需要程序员的注意和努力。相反，将双重分派作为一种语言特性，允许编译器分析代码，检查类型正确性，并通知程序员潜在的错误。另一方面，众所周知，双重分派提高了面向对象编程的可扩展性;也就是说，它允许方法的安全协变专门化[21，3，7]，其中子类被允许通过专门化其参数来重新定义方法例如，协变专门化为二元方法的问题提供了一个平滑的解决方案[5]（即，作用于相同类型的对象的方法：接收者和参数）。在子类中专门化二进制方法，并要求在运行时根据参数的实际类型和接收者执行代码选择时，新代码替换旧定义，这在本文中，我们展示了如何多方法[12，22，8，4]，支持双重分派和协变专门化的机制，可以通过静态重载和单分派来实现。 多方法可以被看作是与同一消息名称相关联的一组分支，即，重载方法，但是选择根据多个调度动态地发生在我们的方法中，我们将多方法限制为双重分派。我们的目标是定义一种通用的技术来扩展具有双重分派（和动态重载）的语言。为了做到这一点，我们提出了一种内核面向对象语言（受C++和Java的启发），它支持动态和静态重载（即，双重分派和单一分派两者），并且我们提供了一种翻译算法，其在给定使用双重分派的程序的情况下，产生等效程序（即，具有相同的语义），其仅使用单个分派。这种翻译被认为是由程序翻译器（预处理器）自动执行的，程序翻译器必须在实际的语言编译器之前运行我们应用这个翻译算法在C++中实现了这种预处理器的实现doublecpp（免费提供在http://www.lorenzobettini.it/software/doublecpp请参阅具有经验丰富，在许多案例研究中。给定一个使用新语言结构的C++程序，doublecpp生成标准的C++代码。在相关的方法中，我们的建议有四个独特的特点：• 我们提供了一个完整形式的多方法，没有封装（参见，例如，[5，9]）以牺牲模块化为代价。使用封装的多方法L. Bettini等人理论计算机科学电子笔记138（2005）5961首先根据接收器的运行时类，然后根据变元的运行时类来执行方法选择。相反，在我们的解决方案中，接收者和参数通过双重分派平等地参与方法选择，而不使用任何优先级。另一方面，封装的多方法具有模块化的主要优点，允许更平滑地单独编译类，而完整的多方法则无法实现。• 我们的翻译是保守的，因为它保留了静态重载，同时增加了动态重载的附加形式特别是，新机制在语义上与静态重载和标准动态绑定一致• 我们的翻译生成的代码既不使用RTTI，也不使用更重要的类型向下转换，这在其他提案中非常常见（在第5节中讨论），并且是众所周知的类型安全违规的来源事实上，我们的解决方案的特点是保持类型安全的关键问题.• 关于实际的评估，我们的翻译在方法选择过程中不会引入关键的开销：它发生在常量时间内，因为它基本上使用了两次动态绑定，并且重载由编译器一次性地静态解决。应用于我们实现doublecpp的基准实际上证实了这一点。我们想强调的是，我们的翻译不是访问者模式的自动实现[16]（尽管它可能会提醒其结构）;相反，它是一个更一般概念的实现，即，双重派遣访问者模式是一种“遍历多态对象集合”的编程原则例如，编译器的情况就是这样：访问者类是所有在抽象语法树上执行几个控制的类，树的节点然后，如果语言不提供双重分派，程序员必须编写代码以获得类似的效果。此外，访问者模式倾向于模拟封装的多方法功能，这使得当派生类想要实现额外的分支（例如，虽然使用我们的方法可以直接实现二进制方法，但它们很难使用访问者模式来实现。62L. Bettini等人理论计算机科学电子笔记138（2005）59我program：：=classdef类定义： ：=classA：A1{i∈ ITif i =exp;分支方法j;j∈J}的情况;分支方法：：=消息分支TJk（ Tk x）;k∈K端exp：：=||||xthis.l梅泰因沃克新类名梅德夫：：=TJ classname：： message（ T x）body主要：：=身体身体：：={localdecl;stmnt;returnexp}本地decl：：=T 1 x 1;... ;Tnxnstmnt：：=|methinvokleft=exp|stmnt1;stmnt2左：：=|X这个.l梅泰因沃克：：=|receiver_req_ message（ expJ）receiver_←_message（ expJ）接收器：：=|exp超级表1玩具语言2玩具DO：一个最小的核心语言与双分派在本节中，我们将介绍一种内核语言toyDO，其正式定义见表1。它用于：(i)抽象出主流语言的基本面向对象特性，如Java和C++，这些特性与我们L. Bettini等人理论计算机科学电子笔记138（2005）5963的目的相关(ii)）通过动态重载（双分派）支持多方法定义和多方法选择。关于第二点，玩具DO，广泛受到Castagna语言KOOL的启发[8，9]。然而，与KOOL的功能性质不同，toyDO是一种处理副作用的命令式语言。64L. Bettini等人理论计算机科学电子笔记138（2005）59为了帮助抽象，我们在toyDO的语法中采用以下简化：• 类字段都是私有的，而方法都是公有的;• 方法总是返回一个值（因为方法体包含一个final return语句）;• 一个程序只是由一系列的类定义组成，然后是一系列的方法定义（类定义只声明方法的签名，而不是它们的实现），然后是一系列的语句，它们在C++和Java中扮演着main的角色;• 我们允许方法体调用超类中的方法的实现，并使用构造super（这个超类方法是静态选择的）;• 由于我们只对研究双重分派感兴趣（而不是更一般的多重分派），我们进一步简化了我们的语言，方法只接受一个参数。此外，在Java和C++中，重载方法选择不考虑返回类型，子类不能改变方法的返回类型• classA：A1表示A1是A的超类。在本文中，为了简单起见，我们只允许单继承。 在4.2节的结尾，我们暗示了如何处理多重继承（就像doublecpp的实现一样）。子类化意味着子类型化，这里用≤（即，A≤A1）。最后，关于玩具DO语法的关键点，根据以下规则编写多方法：多方法被定义为与同一消息名称相关联的一组分支，即，重载方法。直觉上，一个multi方法的所有分支代表了不同参数的不同行为。子类可以通过提供额外的分支并重新定义其中的一些分支来扩展多方法的定义。我们语言中的关键问题是方法调用。为了弄清在处理双重分派时，我们区分了两种不同的方法调用语言结构，←和：• receiver←message（expJ）用于标准静态重载方法调用，即，多方法的分支是根据静态选择的，根据参数的静态类型（静态重载），根据接收方的运行时类型（单次调度）进行• 接收方的请求消息（expJ）用于动态重载方法调用，其中根据接收器的运行时间类型和L. Bettini等人理论计算机科学电子笔记138（2005）5965classA{m个分支T（T1 t）;T（T2 t）;端n个分支S（S1 t）;S（S2 t）;端}的情况;B类：A{m个分支T（T2t）;T（T3 t）;端n个分支S（S3 t）;端}的情况;Fig. 1. 使用多种方法在玩具DO参数（double dispatch）;其中接收器可以是exp或super。让我们通过一个简单的例子来非正式地说明方法选择的语义考虑图1中的代码（假设如果i≤j，则Tj≤Ti）和以下代码：A=newA;T1 t =新T 2;a←m（t）; //静态重载amysql（t）; //动态重载然后，根据静态重载语义执行第一个方法调用选择A：：m（T1），而根据动态重载语义执行的第二个方法调用选择A：：m（T2）。在multimethod的分支中，参数类型的协变特化可以通过构造事实上，B重新定义了分支m（T2），但也通过添加一个新的分支m（T3）来专门化多方法，其中T3≤T2。同样，multi方法的最专门化的分支将动态地在属于子类的对象上选择调用因此，考虑以下代码：Aa =newB;T 1 t=newT 1;amysql（t）; //动态重载t =newT 2;amysql（t）; //动态重载t =newT 3;amysql（t）; //动态重载第一个调用将选择A：：m（T1），第二个将选择B：：m（T2），因为B重新定义了分支m（T2），第三个将选择B：：m（T3），因为B为m（T3）定义了一个专门的分支。让我们注意到，接收者和参数一起参与方法的动态选择，没有任何优先级，如[8]和[10]中所示。66L. Bettini等人理论计算机科学电子笔记138（2005）59[11]的对称多重分派。不同的是，封装的多方法[5，9]的特征在于接收者优先于参数。3键入多个方法和方法调用玩具语言的类型系统是相当标准的，因为它涉及到核心的面向对象结构。由于空间有限，我们省略了对这个问题的全面处理，我们限制了我们对有关多方法和方法选择的类型问题的注意力：在下文中，概述了这个主题的要点我们使用多类型的概念（广泛受[8，9]的启发）来为多方法分类。一种多类型传感器的形式为：n ={I1→T1，...，I n→ T n}其中每个输入类型Ii是一对类型（A×B）。分型。子类型以一种非常自然的方式扩展到多类型。让我们假设箭头和产品类型的标准子类型关系，即，A≤A1，B≤B1<$（A×B）≤（A1×B1）和A≤ A1，B≤ B1< $A1→ B≤ A→ B1然后，1≤2当且仅当对于2中的每个箭头类型，1中至少有一个更小（或相等）的箭头类型。多种类型的良好形成。多类型由三个关键的一致性条件约束。多类型I ={I1→T1，.，I n→T n}是良构的当且仅当对于任何I i，I j（ii = j）：(i) 所有输入类型都是成对不同的;(ii) 如果Ii≤Ij，则Ti<$Tj;(iii) 如果Ii和Ij有一组公共子类型，那么对于每一组公共子类型，必须恰好有一个箭头类型Ik→Tk，使得Ik是这个集合的最大类型。条件（i）是重载定义的标准。条件（ii）是特定于多方法的;我们需要Ti<$Tj（而不是[8，9]中的Ti≤TjL. Bettini等人理论计算机科学电子笔记138（2005）5967根据C++和Java的哲学，在重载方法选择中不使用返回类型。条件（iii）涉及在良好类型的方法选择中没有歧义（见下文）。注意，人们可能会考虑采用更自由的类型规程，只在方法调用时检查第三个条件（没有歧义）。这是使用的策略，例如，C++和Java。这将使类型检查更加复杂，虽然对于静态重载这仍然是可行的，但在存在动态重载的情况下，它将使类型检查也更加低效，因为每次使用方法时，都应该检查该方法调用中涉及的整个类层次结构，以确保动态不会发生二义性。此外，正如第5节所暗示的，我们使用λobject [8，9]开发了基于这些良构条件的翻译的形式理论。3.1类型规则我们回想一下，在超类中定义的多方法可以通过继承其定义并可能添加新分支来在派生类中扩展。而且，它的一些分支的行为可以在子类中被重写，同时保留参数的类型和返回类型。多方法声明的类型规则。类C中的多方法m具有多类型的n ={（C×A1）→T1，.，（C×A n）→T n} J我的•A1→T1，.，A n→T n是m的所有分支的类型，定义如下：C、温度;•J是m在C的超类中的（可能是空的）多类型;• 它是很好的形成。话让我们注意到，通过格式良好，在子类中重写一个multi方法的某个分支可能需要重写其他分支，以获得一个格式良好的multi方法。例如，如果一个类A定义了具有以下类型T1→T和T2→T的多方法m的两个分支，其中T2≤T1，并且m的第一个分支在A的子类B中被覆盖，则由于第三个条件，所得到的多型m，n ={（A×T1）→T，（A×T2）→T，（B×T1）→T}为了有一个好的类型覆盖这个多方法，程序员应该重新定义68L. Bettini等人理论计算机科学电子笔记138（2005）59另一分支（例如，通过简单地调用超类实现），从而得到良构的多类型T={（A×T1）→T，（A×T2）→T，（B×T1）→T，（B×T2）→T}.从实践的角度来看，一个更灵活的策略应该包括自动插入这种琐碎的覆盖在需要的时候。更一般地说，超类中multi方法的所有分支都可以自动插入到派生类中，只要它们没有在派生类中重新定义，从而获得继承的完整形式的复制语义[2]。我们的解决方案更简单，但从形式的角度来看是等价的doublecpp的实现使用了复制语义的完整形式，因此程序员不会被迫编写这种琐碎的方法重写。多方法调用的类型规则。在一个具有类型B参数的类型A的接收对象上调用m（都带有结构←和结构 ） 具 有 类 型 Ti 有 一 个 箭 头 类 型 （ AJ×BJ ） →T∈ 使 得 （ A×B ） ≤（AJ×BJ）。上述格式良好的条件在类型化中起着至关重要的作用方法调用。由于T是良构的，条件（ii）确保了类型T对于任何这样的对（AJ×BJ）都是唯一的最重要的是，条件（iii）涉及在解释通过静态和动态重载语义调用m。也就是说，通过条件（iii），存在一个且仅一个分支，其输入类型类型（A1×B1）使得（A1×B1）≤（A×B）≤（AJ×BJ）.因此，对类型良好的方法调用的评估有两个重要的特点：(i)）保留静态类型（主题减少），(ii)）不会由于歧义或消息未被理解而达到4从双重派遣到单一派遣在本节中，我们将展示如何将任何使用双分派（double dispatch，DSO）的玩具DO程序转换为仅使用单分派（dynamic binding，动态绑定）和静态重载（static overloading，←）的等效程序。为此，我们将使用玩具SO来表示玩具DO 的子集，如表1所定义，但以下条款除外的方法调用，这是减少到一个结构，即，静态重载方法调用：receiver←message（exp）L. Bettini等人理论计算机科学电子笔记138（2005）5969在4.1节中对基本思想进行了非正式介绍之后，在4.2节中定义了从玩具DO到玩具SO的翻译算法。4.1非正式的基本思想为了给一个基本的想法，建议的翻译，我们考虑的例子。为了简单起见，我们在类声明中写了分支的声明和定义，省略了return。假设我们有下面的类定义（在左边），其中TiclassC1{m个分支T（T1x）;T（T2x）;端C1c=新C1;T1t=新T2;cm（t）}在这个程序中，将选择C1中m的第二个分支，因为尽管静态地声明为T1，但t动态地属于T2类型假设类C1、T1和T2被修改如下：classC1{mDB分支T（T1x）{x←dispm（this）}结束;m个分支T（T1x）;T（T2x）;端}classT1{分支机构分布T（C1x）{x←m（this）}端}classT2：T1{分支机构分布T（C1x）{x←m（this）}端}然后我们将方法调用c←m（t）转换为c←mDB（t）。很容易验证：(i) 方法调用x←dispm（this）将选择T2中dispm的（唯一）分支，因为动态绑定也用于静态重载调用;(ii) T2中的方法调用x←m（this）将使用静态重载，因此将根据参数的静态类型在C1中选择m的一个分支：参数this是T2类型，因此将选择C1中m的第二个因此，转换后的程序中的c←mDB（t）导致具有与原始程序中的c<$m（t70L. Bettini等人理论计算机科学电子笔记138（2005）59现在让我们把这个例子变得更复杂一点（T4≤T2）：classC2：C1{m个分支T（T4x）;端}C1c = 新C2;T1t=新T4;cm（t）在C2中，动态重载语义将再次选择T（T4x）;.在这种情况下，程序将被翻译如下（类C1的翻译与以前一样，T1和T2的翻译是相同的）：classC2：C 1{mDB分支T（T1x）{x←dispm（this）}结束;m个分支T（T4x）;端classT1{分支机构分布T（C1x）{x←m（this）};T（C2x）{x←m（this）}端}}classT2：T 1{分支机构分布T（C1x）{x←m（this）};T（C2x）{x←m（this）}端类T4：T 2{分支机构分布T（C2x）{x←m（this）}端}}同样，让我们解释方法调用c←mDB（t）（替换为c←m DB（t））。m（t））：(i) 由于采用了动态绑定，C2中的mDB将被动态地选择(ii) 方法调用x←dispm（this）将静态地选择T1中dispm的第二个分支，因为这是（静态地）C2类型，但由于采用了动态绑定，因此T4中提供的此类方法的版本实际上是动态调用的(iii) T4中的方法调用x←m（this）将根据参数的静态类型选择C2中m的一个分支：参数this是T4类型的，因此将选择C2中m的分支T（T4x）因此，转换后的程序中的c←mDB（t）具有与c*相同的行为。m（t）在原始程序中。总之，我们的翻译的想法是，动态重载语义可以在静态重载语义语言中通过利用动态绑定（即，一次分派）和两次静态重载：通过这种方式，可以利用运行时动态地选择正确的方法L. Bettini等人理论计算机科学电子笔记138（2005）5971消息接收者和参数的类型请注意，我们的翻译为每个同名的multi方法m引入了一个新的multi方法，并添加了一个sunixDB（用于DouBle分派）。这个新的多方法mDB在类Ci中的分支从m的分支开始构建，如下所示：• 我们考虑Ci中m的所有参数类型Tj的集合τ（包括从所有超类继承的分支）;• 然后，我们考虑包含最大类型的τ的子集，并且对于该子集中的每个类型Ti，我们向具有类型Ti的参数的Ci中的mDB添加分支。例如，如果参数类型的集合是{T1，T2，T3，S1，S2}，其中T3≤T2≤T1与S2≤S1无关，则最大类型的子集是{T1，S1}。 此操作的正确性依赖于多种类型。例如，考虑上面定义的类别及其翻译：• 类C1中的多方法m具有类型T1和T2的参数。T1是最大的，所以C1中的重载方法mDB有一个参数类型为T1的分支;• 同样，类C2中的多方法m具有类型T4的参数，并且从C1继承具有参数T1和T2的两个分支。T1是这些类型T2和T4中的最大值，因此C2中的重载方法mDB有一个参数类型为T1的分支。类似地，在Ti类中引入了一种新的多方法dispmdispm的分支构建如下。让我们考虑在类Ci中多重方法m的定义。对于每个类型Ti，使得Ti是m中分支的参数的类型，我们在类Ti中添加一个分支以dispm，参数类型为Ci。我们在每个类Tj中添加相同的分支到dispm，使得Tj≥Ti，并且Tj是m的分支的参数的类型，Ci或在超类Ck（Ck≥Ci）中.让我们再考虑一下上面的类别•T1和T2是m在C1中的分支的参数类型，因此我们在T1和T2中添加一个分支来disp m，参数类型为C1。• T4是C 2中m分支的参数类型，因此我们在T 4中添加一个分支来dispm，参数类型为C2。此外，由于T4≤T2且T2是m在C1（C2≤C1）中的分支的参数类型，我们在T2中添加一个分支到dispm，参数类型为C2;递归地，我们将这样一个分支添加到T1，因为T2≤T1且T1是m在C1（C2≤C1）中的分支的参数72L. Bettini等人理论计算机科学电子笔记138（2005）59因此，方法mDB旨在静态地使用Ci的类型并且动态地使用Tj的类型，而方法dispm恰好具有相反的任务。这两个方法一起实现了动态重载语义。让我们观察一下，如果一个派生类，比如C3≤C2，没有在m中引入任何新的专门分支，而只是重新定义了继承的分支，那么就不需要这样一个额外的mDB方法：由于动态绑定，最重新定义的出于同样的原因，对于类Ti中的这样的类C3，不需要dispm此外，可能的中间类Tj4.2翻译算法我们以自上而下的风格呈现翻译算法，定义了以下我们使用的每个附加过程。我们希望观察到翻译是在良好类型的程序上定义的，因此我们在定义算法时假设了关于正确程序的此外，所有类型和子类型关系都是根据在类型检查算法期间收集的类型和子类型环境来考虑的，并且在翻译算法中没有显式化。定义4.1[特殊化类型pe]LetmmmchesTJl（Tlx）;l∈Lend是多重方法的声明。然后我们说每个Tl都是一个特化m的类型（在其类型用于方法m的专门化中的形式参数的意义上，即，在m的分支之一中）。惯例。在算法的定义中，我们将使用以下约定：• MD表示当前程序中的方法定义集• A←←TJm（Tx）意味着将TJ（Tx）的分类与当前程序中A类中的多方法m相关联，当然，如果该分支还不存在。如果multi方法在A中不存在，它也会创建multi方法声明;• MD←TJA：：m（T x）body表示方法定义TJA：：m（T x）body添加到当前程序中，当然，如果它还没有出现;• superclass（A）返回A的直接超类，如果A没有超类，则返回nil定义4.2[isspecializingtype谓词]isspecializingtype（A，m，T，TJ）检查类型T是否被A或AL. Bettini等人理论计算机科学电子笔记138（2005）5973JImulti-methodm分支中的参数类型（返回类型TJ的对象）：isspecializingtype（A，m，T，TJdef）=的m：{（Ai×Tj）→TJi∈Iji∈Ji}ijii∈I使得A≤Aiji∈JisuchthatTTJ翻译算法将玩具DO程序翻译成等效的玩具SO程序如下：对于each多方法mk：{（Ai×Tj）→TJi∈Iji∈Ji}和对于eachi∈Iiji且ji∈Ji：addmethod（Ai，mk，Tj，TJ）ijiadddispatch（Ai，mk，Tj，TJ）iji因此，翻译算法本质上包括为每个多方法m的每个分支调用两个过程：第一个用于构建mDB，第二个用于构建dispm。这两个子程序定义如下：(i)）addmethod（A，m，T，TJ）向类A中的mDB添加一个分支;添加的分支的类型不一定是T→TJ，但它可以是TJJ→TJ，其中T≤TJJ：实际上，TJJ将是所有类型Tl中的sup，使得T≤Tl，并且Tl被用作A或A中的m超类A.addmethod（A，m，T，TJdef）=的如果m：{（Ai×Tj）→TJi∈Iji∈Ji}thenijiletTh= sup≤{Tl|T≤Tli∈I，ji∈Ji. ji= l<$A≤Ai}inA←←TJmDB（Thx）MD←TJA：：mDB（Th x）{returnx←dispm（this）}注意，mDB可以有几个分支：实际上，正在被翻译的重载方法m可能使用来自不相关层次结构的特殊化类型：对于这些层次结构中的每一个，我们必须向mDB添加一个分支。(ii)）adddispatch（A，m，T，TJ）添加一个分支到dispm，参数类型为A在类T中，前提是T是m在A或超类A.此外，它通过调用74L. Bettini等人理论计算机科学电子笔记138（2005）59自己递归地：adddispatch（A，m，T，TJdef）=的如果是specializingtype（A，m，T，TJ），则T←←TJdispm（Ax）MD←TJT：：dispm（A x）{returnx←m（this）}endif如果superclass（T）/=nil，则adddispatch（A，m，superclass（T），TJ）endif请注意，该过程跳过（即，不修改）T的层次结构中可能的中间类，它们不是m的任何分支的专门化类型。最后，每个动态重载方法调用exp<$m（expJ）都被转换为exp←mDB（expJ）。上面定义的翻译过程的一个相关性质是类型的保留：玩具DO的每个良好类型化的程序被翻译成玩具SO的良好类型化的程序。由于篇幅所限，我们无法对这一问题作出正式说明。我们只提到关键的技术步骤：(i)）在翻译期间添加的新的mDB和dispmmulti方法是良好类型的（特别地，对于多类型的multi方法m，对应的mDB被给予子类型的multi）;(ii)任何类，通过添加新方法修改后，仍然保持良好的类型。最后，关于实际评估，翻译后的代码是有效的，因为它利用了动态绑定两次，因此方法调用与多方法的分支数量以及类层次结构的深度和宽度无关这种选择背后的理性与主流面向对象语言（如C++和Java）中的动态绑定实现相同：方法的“正确”版本的动态选择不是通过自下而上检查对象的类层次结构来执行的;方法调用是通过访问由同一类的对象共享的虚拟方法表来执行的，并且包含指向最专用方法的[20]）。这允许在恒定时间内在运行时高效地选择方法（即，独立于方法的数量和类层次结构）。遵循类似的方法，我们在运行时不通过检查参数的动态类型（使用RTTI信息）来选择正确的分支，而是通过将方法调用分派给接收者和参数（即，我们实际上执行双重分派）。注4.3[多重继承。] 该算法的扩展到L. Bettini等人理论计算机科学电子笔记138（2005）5975多重继承的情况需要一些额外的步骤来定义两个子过程addmethod和adddispatch，以确保新创建的multimethodmDB和dispm在存在多个不相关的超类的情况下也满足良好格式的条件（iii事实上，多重继承在doublecpp中处理。5结论和相关工作我们提出了一种翻译算法，允许以类型安全的方式实现双重分派（即，动态重载和协变专门化）。这种翻译本质上是修改类，使其可以由预处理器执行这种方法足够通用，可以应用于许多命令式OO语言，如Java、C++和C#。关于进一步的发展，我们的建议的理论问题将在一篇配套论文中提出，其中：语言玩具DO的语义是通过翻译到λobject [8，9]来定义的，λ object是一种用于建模面向对象特征的Meta语言。我们建议的元理论是在λ对象的形式化设置中这样陈述的，λ对象提供了一个形式化的合适框架，但非常接近面向对象语言的实际实现据我们所知，λobject是唯一一个直接处理多方法和动态重载的理论模型，因此它似乎是一个适合我们目的的框架。我们还在研究如何推广我们的方法来实现多分派，而不仅仅是双重分派。这种泛化将基于一系列涉及多方法所有参数的分派调用我们的方法的一个缺点是缺乏模块化，这也影响了单独的编译。这是因为我们的翻译也修改了用作多方法分支参数基于运行时类型检查和动态类型转换的解决方案并不支持这个问题;相反，这些解决方案的特征在于方法选择的复杂性取决于分支的数量和层次结构中的类的数量，而我们的解决方案动态方法重载选择是恒定的（如本节后面进一步讨论的）。模块化和优化的代码涉及两种不同类型的用户：程序员对模块化和单独编译感兴趣，因为较少的编译将增加生产力时间。另一方面，最终用户会欣赏到更好的性能。我们在实现doublecpp时考虑了这些需求：当给定命令行选项--modular时，76L. Bettini等人理论计算机科学电子笔记138（2005）59它生成这样的模块化代码，而不是我们的翻译所描述的代码生成的代码仍然基于_DB方法的生成，但是这些生成的方法的主体通过使用RTTI来检测正确的分支当然，这两种策略生成的代码是等价的。那么，我们可以设想以下发展情景：• 程序员可以在他的程序开发期间使用模块化代码生成策略;将需要更少的编译，实际上甚至比他直接使用访问者模式更少• 在部署应用程序时，可以用DoubleECP重新预处理整个代码，从而生成更快的代码。我们还使用了两种不同的策略来评估我们方法的性能，正如预期的那样，我们的翻译生成的代码优于使用动态类型检查和强制转换的代码。我们认为，本文中提出的转换是一种方法添加策略，可以在链接时由（修改后的）C++编译器执行而不需要真正修改源代码。这些方法可以直接添加到编译器生成的文件对象注意，在链接时，所有编译文件都可用。我们正在调查这个问题。关于相关的工作，我们只提到直接支持多方法和多分派作为语言特征的语言，Dylan[23]，BeCecil[10]，CLOS[18]，我们集中在那些基于程序转换的语言上。与我们更接近的工作是寄生方法[4]，这是Java的扩展，允许实现多个方法。它被认为是模块化的，这一选择影响了设计的许多方面：寄生方法被封装，因此在方法选择中，接收器在参数之前被评估;最专门化的方法的选择通过instanceof检查和随之而来的类型转换进行，因此它不执行con-type。与我们的解决方案一样，但基本上与分支数量呈线性关系寄生方法由于使用方法的文本顺序而变得复杂，以便解决选择正确分支的歧义;所有方法必须在接收器的类中声明，以便消除类依赖性。付出的代价是多方法参数的类层次结构必须被预期，限制了可相比之下，我们的方法实现了非封装的多方法（以牺牲模块性为代价），不使用RTTI机制，并导致更好的性能。MultiJava[11]是Java语言的一个扩展，支持开放类（可以向其中添加新方法而无需编辑类的类型）。L. Bettini等人理论计算机科学电子笔记138（2005）5977直接）和（非封装的）多方法。以许多限制为代价，MultiJava允许使用只有开放类语法的多方法，并且只用于导入开放类定义的程序;方法选择通过级联if语句来执行，以在运行时测试参数类型。Cmm[24]是一个在C++中提供CLOS风格的多方法的预处理器同样在这种情况下，类型转换和RTTI被大量利用，从而降低了这些方法调用期间的性能。此外，由于缺少分支，可能会引发其他方法在Java中提供了多重分派而不扩展类型系统：JMMF[14]是一个使用反射机制实现的框架，而在[6]中，一个新的构造是使用ELIDE（一个为Java添加高级功能而实现的框架）创建的这些建议的主要缺点是，由于缺少或不明确的分支而导致的类型错误在运行时被异常捕获。[13]提出了JVM的一个扩展，在Java中提供多分派，而不修改语法和类型系统：程序员直接选择应该使用多分派的类这种方法的问题是，为单个分派编写的代码被粗略地切换到多个分派，从而产生了模糊的方法调用和返回类型的问题关于同一主题的其他建议，如[17，15]，其特点是它们没有提供任何自动预处理代码的方法，因此它们更类似于模式或习惯用法（如访问者）。此外，它们中的一些是针对特定场景的，例如基本上是为二进制方法设计的，或者它们需要程序员进行大量手动编程，通常不需要静态检查正确性。[1]的第11章提出了一些解决方案，允许通过巧妙地使用泛型编程（模板）在C++中实现这种方法不会扩展语言，并且仍然会引发由于缺少分支而导致的运行时错误此外，虽然模板的使用减少了必须显式编写的代码量（w.r.t.其他基于Java的解决方案），程序员仍然明确要求编写一些代码来实现双重分派。在某些情况下，他甚至必须提供目标类的层次结构顺序此外，[1]中提出的一些方法不能处理从多方法中指定的目标类派生的类的对象它们不能正确地与继承一起工作）。78L. Bettini等人理论计算机科学电子笔记138（2005）59致谢我们感谢匿名推荐人的有益建议，以澄清文件的某些方面引用[1] A.亚历山大雷斯库现代C++设计，泛型编程和设计模式应用。艾迪森·韦斯利2001年[2] D.安科纳湾Drossopoulou和E.祖卡 重载和继承。 《傻瓜8》，2001年。[3] F. 班奇永角Delobel和P.Kanellakis（eds.）实现面向对象的数据库系统：O2的故事。摩根·考夫曼1992年[4] J. Boyland和G.卡斯塔尼亚Parasitic Methods：Implementation of Multi-Methods for Java.在Proc of OOPSLAACM，1997年。[5] K. B.布鲁斯湖Cardelli，G.霍普金斯对象组，G。Leavens和B. C.皮尔斯关于二进制方法。对象系统的理论与实践，1（3）：217[6] 卡 本 内 托 。 java 中 使 用 elide 框 架 的 多 重 分 派 的 实 现 。 可 在 www.example.com 上 查 阅http://www.cs.ubc.ca/。[7] G. 卡 斯 塔 尼 亚 协 变 性 和 逆 变 性 ： 没 有 原 因 的 冲 突 。 ACM Transactions on ProgrammingLanguages and Systems，17（3）：431[8] G.卡斯塔尼亚类型化面向对象语言的一种元语言。Theoretical Computer Science，151（2）：297[9] G.卡斯塔尼亚面向对象编程：统一的基础。理论计算机科学进展。Birkhauser，1997年。[10] C. Chambers和G.T. 莱文斯BeCecil，A core object-oriented language with block structureand multimethods：Semantics and typing.《傻瓜4》，1996年。[11] C.克利夫顿，G.T.莱文斯角Chambers和T.米尔斯坦MultiJava：Java的模块化开放类和对称多重分派。ACM SIGPLAN Notices，35（10）：130[12] L.G.德塞尔和R·P·加布里埃尔。通用Lisp对象系统：概述。在Proc. ECOOP，LNCS第276卷，第151-170页。Springer，1987年。[13] C. Dutchyn，P. Lu，D. Szafron，S. Bromling和W.霍斯特Java虚拟机中的Multi-Dispatch：设计与实现。在Proc. of the 6 th USENIX Conf. on Object-Oriented Technologies and Systems（COOTS[14] R. Fo