编译器逼出的编程范式：双分派（访问者模式）
|
1
|
java,算法
|
246

今天在V2社区冲浪的时候看到了一篇讨论访问者模式这个设计模式的帖子，发现自己还不了解这个模式于是便学习了一下；没想到这个设计模式的出现竟然和编译器的动态链接相关行为的局限有关…… 还蛮有意思的，开帖子记录一下。

背景问题

先贴一段代码

public class FruitTest {
    public static void main(String[] args) {
        Parent boy = new Boy();
        Fruit apple = new Apple();
        Orange orange = new Orange();
        boy.eat(apple);
        boy.eat(orange);
    }
}

class Fruit {}
class Apple extends Fruit {}
class Orange extends Fruit {}

class Parent{
    public void eat(Fruit fruit) {
        System.out.println("parent.eat Fruit");
    }
    public void eat(Apple apple) {
        System.out.println("parent.eat Apple");
    }
    public void eat(Orange orange) {
        System.out.println("parent.eat Orange");
    }
}

class Boy extends Parent {
    @Override
    public void eat(Apple apple) {
        System.out.println("boy eat Apple");
    }

    @Override
    public void eat(Fruit fruit) {
        System.out.println("boy eat Fruit");
    }

    @Override
    public void eat(Orange orange) {
        System.out.println("boy eat Orange");
    }
}

那么在不看答案的情况下，你觉得这段代码的输出是什么呢？
答案是输出为“一行“boy eat Fruit，一行“boy eat orange”

但是这是为什么呢？ 为什么编译器看起来能够根据被调用的类的实际类型来选择方法，但是没能根据参数的实际类型来选择合适的方法呢?

这就引出了这个所谓的“局限”： 单分派机制与重载机制 （有时候也把他们叫做动态分派、静态分派）

单分派与方法重载

  • 单分派是方法调用的一种分派机制，java、C++、PHP等多数语言都使用这种机制；指的是在运行时根据被调用对象的动态类型[1]来决定调用的具体实现。
  • 方法重载则是编译时首先根据被调用对象的静态类型和传入参数的静态类型选择最匹配的方法。

返回到最开始boy和apple的例子：

  • 在编译期，编译器会根据调用对象的静态类型和入参的静态类型来选择一个最匹配的方法，而apple变量的静态类型是Fruit，所以在编译器就决定了最后输出一定是"eat fruit"
  • 在运行期，虽然boy的静态类型是Parent类型，但是JVM根据单分派原则需要根据boy变量的动态类型来决定选择哪一个方法的实现来执行[2]，所以最后可以输出"bot eat XXX"

练练手

下面这个例子还掺杂了接口，会稍稍复杂一些，但是也更贴近日常会写的代码，来猜猜他的输出？

interface Element {
    void accept(Visitor visitor);
}

class ConcreteElementA implements Element {
    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this); // 这里需要传递自己以匹配正确的方法
    }
}

class ConcreteElementB implements Element {
    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this); // 同上
    }
}

interface Visitor {
    void visit(Element element); // 通用方法
}

class ConcreteVisitor implements Visitor {
    @Override
    public void visit(Element element) {
        System.out.println("访问者处理通用的元素");
    }

    public void visit(ConcreteElementA element) {
        System.out.println("访问者处理 A 类型的元素");
    }

    void visit(ConcreteElementB element) {
        System.out.println("访问者处理 B 类型的元素");
    }
}

public class ShapeTest {
    public static void main(String[] args) {
        ConcreteElementA element = new ConcreteElementA();
        ConcreteVisitor visitor = new ConcreteVisitor();

        element.accept(visitor); // 调用哪个 visit？
    }
}

你看，这里visitor和element的静态类型都是实现类的类型，那么是不是编译期的方法重载就不会干扰我们了？
错~ 实际上这段代码的输出还是“访问者处理通用的元素”！
编译器在编译的时候发现ConcreteElementA类型只有一个accept(Visitor)的方法，方法内容是调用Visitor接口的visit方法，而visitor接口的visit方法只有一个接收Element的默认实现……那么任你如何分派，都不会去调用ConcreteVisitor实现类中的其他方法了……

这个异常是不是藏得很深了呢，但是我觉的日常我们应该也不会写出这么绕的代码……
这段代码其实是基于访问者模式做了一点小改动，下面我们来正式介绍这个模式

访问者模式

先提一句，访问者并不是常用的设计模式， 因为它不仅复杂， 应用范围也比较狭窄。

既然上面已经给出了访问者模式的错误实现，那么这里就先给出正确实现，之后再讨论这个设计模式的其他细节。

package top.tarvis.util2024;

interface Element {
    void accept(Visitor visitor);
}

class ConcreteElementA implements Element {
    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this); // 这里需要传递自己以匹配正确的方法
    }
}

class ConcreteElementB implements Element {
    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this); // 同上
    }
}

interface Visitor {
    void visit(Element element); // 通用方法
    //下面两行是与上文中错误实现的唯一区别，这样可以帮助编译器根据入参的类型来调用不同的方法
    void visit(ConcreteElementA element);
    void visit(ConcreteElementB element);
}

class ConcreteVisitor implements Visitor {
    @Override
    public void visit(Element element) {
        System.out.println("访问者处理通用的元素");
    }

    public void visit(ConcreteElementA element) {
        System.out.println("访问者处理 A 类型的元素");
    }

    void visit(ConcreteElementB element) {
        System.out.println("访问者处理 B 类型的元素");
    }
}

public class ShapeTest {
    public static void main(String[] args) {
        ConcreteElementA element = new ConcreteElementA();
        ConcreteVisitor visitor = new ConcreteVisitor();

        element.accept(visitor); // 调用哪个 visit？
    }
}

多态的背后：VTable

前面提到的单分派之类的概念可能有些眼花缭乱，现在来介绍一下是什么样的底层机制造成了编译器/执行器的这种行为。
隆重介绍——VTable：VTable（虚函数表）并不是所有编程语言都有的特性，但确实在许多面向对象编程语言中作为一种实现多态性的机制存在。

使用VTable或类似机制的语言:

  • C++: 最典型的VTable实现，用于支持虚函数调用
  • Java: 使用类似机制实现方法调度，但在语言层面不直接暴露
  • C#: 通过虚方法表实现多态性
  • D语言: 采用类似C++的VTable机制
  • Rust: 通过vtable实现trait对象

不使用VTable的语言:

  • Python、JavaScript、Ruby: 这些动态语言通常使用方法查找（method lookup）或消息传递机制
  • 纯函数式语言: 如Haskell，使用不同的多态实现方式
  • Go: 使用接口的隐式实现而非传统VTable

C++ 中的VTable结构

基本结构：
本质是一个函数指针数组
每个包含虚函数的类拥有一个唯一的VTable
数组中每个条目指向一个虚函数的实现
内存布局

类对象内存布局:
+----------------+
| vptr          | --> 指向VTable的指针(由编译器添加)
+----------------+
| 成员变量1      |
+----------------+
| 成员变量2      |
+----------------+
| ...           |
+----------------+

VTable结构:
+----------------+
| 类型信息(RTTI) |
+----------------+
| 虚函数1的指针   |
+----------------+
| 虚函数2的指针   |
+----------------+
| ...           |
+----------------+

继承情况：

子类继承父类时，会复制并修改父类的VTable
被子类重写的函数，其指针会被更新为子类实现
多重继承时可能有多个VTable或需要指针偏移调整

Java中的VTable（方法表）

Java虽然不直接暴露VTable概念，但JVM内部使用类似机制：

方法表：

每个类加载时创建方法表
所有非private/static/final方法默认为"虚方法"
表按方法签名排序，子类覆盖方法保持相同位置

调用机制：

invokevirtual操作码执行时:

  1. 获取对象的实际类型
  2. 在该类型的方法表中查找方法
  3. 执行找到的方法实现

接口方法：

Java 8前使用更慢的查找方式处理接口
Java 8后使用invokedynamic和方法句柄优化

Rust中的Trait对象

Rust使用”胖指针“[3]分配对象

// 胖指针结构(简化表示)
struct TraitObject {
    data: *mut (), // 指向实际数据
    vtable: *mut VTable // 指向虚函数表
}

// 虚表包含
struct VTable {
    size: usize, // 类型大小
    align: usize, // 对齐要求
    method1: fn(*mut ()), // 方法指针
    method2: fn(*mut ()),
    // ...更多方法
}

VTable对性能的影响

每次虚函数调用需要额外的内存访问（加载VTable指针、查表等），所以相对直接找到目标方法的情况性能会有非常微小的下降；以及不同语言的编译器/运行时会尝试通过去虚拟化、假设内联等技术来减轻这些开销。

Python如何不使用VTable实现多态

1.Duck Typing (鸭子类型)
如果一个东西走起来像鸭子，叫起来像鸭子，那么他就是一只鸭子…… 学院派的讲法是：对象的类型由其行为（方法和属性）决定，而不是由继承关系来决定

以迭代器为例，只要一个类实现了next()和iter()两个方法，那么他就是一个迭代器，对应的对象就可以 for num in MyIter(2) 被for循环遍历

2.动态方法查找
python解释器的每次方法调用都会在对象的dict或类的方法解析顺序(MRO)中查找，而不是通过预先构建的表 （作为一个解释型语言也没有预先建表的机会）

Go如何不使用VTable实现多态

ps. 目前还不会Go，所以先复制上来，正确性存疑……
Go使用接口(interface)实现多态，但方式独特：

1.隐式接口实现：
无需显式声明实现了某个接口
只要类型方法集包含接口要求的所有方法，就算实现了该接口

2.接口值与iTable：
Go接口值包含两部分：类型信息和数据指针
运行时按需创建"接口表"(iTable)，包含方法地址映射
iTable会被缓存复用，非传统VTable

3.示例

type Speaker interface {
    Speak() string
}

type Dog struct{}
func (d Dog) Speak() string {
    return "Woof!"
}

type Cat struct{}
func (c Cat) Speak() string {
    return "Meow!"
}

func MakeItTalk(s Speaker) {
    fmt.Println(s.Speak())
}

func main() {
    MakeItTalk(Dog{})  // 输出: Woof!
    MakeItTalk(Cat{})  // 输出: Meow!
}

Tips

  1. ^这里的动态类型值得就是对象的真实的类型，而下文的静态类型指的是代码中声明的类型；例如背景问题小节代码中的boy变量，动态类型就是Boy，而静态类型则是Parent
  2. ^这也是OOP语言实现多态的基础 不是么？
  3. ^胖指针是rust中一种特殊类型的指针，与普通指针不同，它不仅包含指向数据的内存地址，还携带额外的元数据。
参考文章
https://zhuanlan.zhihu.com/p/380161731
https://www.zhihu.com/question/28462483
https://refactoringguru.cn/design-patterns/visitor-double-dispatch
https://refactoringguru.cn/design-patterns/visitor
https://v2ex.com/t/1101064

评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
并查集

							
							

							
Java19 协程初探

							
							

							
@ExceptionHandler 原理浅析

							
							

							
博客搭建日志

							
							

							
Floyd 判圈算法