如何高效且通用地实现Multiple dispatch（多分派）？

多重分派是OOP语言中传统单分派（single dispatch）的实用泛化机制，但高效简洁的实现方式并不明确。单分派的实现很简单：任何教材或网站都会告诉你，对象拥有包含方法列表的vtable，可在运行时索引调用。但大量资料只讲多重分派的用法和优势，却没能清晰解释其实现原理，因此我想知道：该如何实现它？

约束条件 #

一个令人满意的解决方案需要具备以下必备特性：

• 支持外部类型：比如库中有Animal类，我能在独立代码中创建Cat子类，无需修改或重新编译库，就能将其用于库中的任意函数。
• 支持外部方法重写：若库中存在attack(Animal predator, Animal prey)函数，我可在自有代码中实现attack(Cat predator, Mouse prey)，无论谁（我、库或其他使用者）调用attack(new Cat(), new Mouse())，都会执行这个自定义函数。
• 正确处理子类型分派：如果我创建Lion类但未重写attack(Cat predator, Mouse prey)，调用attack(new Lion(), new Mouse())时会执行attack(Cat predator, Mouse prey)。

理想情况下，高效实现还应具备以下特性（并非必须）：

• 多重分派的时间复杂度不应随类型或方法重写数量呈O(n)增长，否则数量增多时分派速度会急剧下降。
• 若方法仅基于单个参数分派，效率应和基于vtable的单分派一致，即时间复杂度为O(1)。

如果某个多重分派实现具备上述特性，其功能至少与基于vtable的单分派相当，可视为令人满意的方案。

无效解决方案 #

我见过一些无法满足上述约束的方案：

• 访问者模式：无法满足“支持外部类型”的必备特性。必须为每个要分派的类型单独编写方法，新增类型时需添加新方法，这会迫使库重新编译。
• 按类型划分维度的N维数组：比如给Animal=0、Cat=1、Lion=2、Mouse=3，调用attack(new Lion(), new Mouse())时查找attack_vtable[2][3]，里面存着指向attack(Cat predator, Mouse prey)的指针。但该方案预设类型数量固定，需要为每个类型分配唯一连续编号并使用固定大小的数组。
• 遍历所有可用方法查找最佳匹配：这种方式效率低下，且难以满足“支持外部方法重写”的特性，因为库无法知晓自有代码中的attack(Cat predator, Mouse prey)。

我也查阅过一些多重分派的论文，但这些论文要么晦涩难懂，要么对缺乏理论计算机科学基础的人完全不友好。

是否存在一种能够满足（或至少大部分满足）上述约束的多重分派实现方式？

内容的提问来源于stack exchange，提问作者v-rob