多分派

多分派或譯多重派發（multiple dispatch）或多方法（multimethod），是某些程式語言的一個特性，其中的函數或者方法，可以在運行時間（動態的）基於它的實際參數的類型，或在更一般的情況下於此之外的其他特性，來動態分派。多分派是對單分派多態的推廣，這裡的函數或方法調用，基於在其上調用方法的對象的派生類型，而動態分派。多分派使用一個或多個實際參數的組合特徵，路由動態分派至實現函數或方法。

## 理解分派

軟體工程師通常把代碼寫進代碼塊中，代碼塊通常稱作過程、函數、方法。代碼通過被調用來執行，調用時將控制權傳入函數中，當函數執行完成後將控制權返回給調用者。

函數名通常用來描述函數的目的。有時會將多個函數起同樣的名稱。比如同名函數在邏輯上處理相同的任務，但是操作在不同類型的輸入值上。在這種情況下，無法僅僅通過函數名，來判斷目標代碼塊。那麼，函數的實際參數的個數和類型，也就被用來判斷。

通常，單分派面向對象語言，在調用一個方法時，方法參數中一個參數會被特殊對待，並用來決定哪一個方法（如果有多個同名方法）會被調用。在許多語言中，這個特殊的參數是在語法上指明的，許多程式語言在調用方法時，把特殊參數放在小圓點（`.`）之前。例如 `special.method(other, arguments, here)`，這樣 `lion.sound()` 將會發出獅吼，同時 `sparrow.sound()` 只會吱吱地叫。一般來說，對於面向對象的程式語言，這個小圓點之前的參數（上例中的`lion`和`sparrow`）被稱為接收者。

相反，在實現了多分派的語言中，被調用的函數，即是那些參數個數一樣多，並且類型也匹配的調用。在調用中並沒有特殊參數，來決定那個方法被調用。也就是說，所有參數的運行時類型都參與分派。CLOS是早期和著名的多分派語言。

### 數據類型

對於編譯時間可以區分數據類型的程式語言，在交替 (形式語言理論)（alternative）函數中進行選擇，可以發生在編譯時間，創建交替函數用於編譯時間選擇的活動，通常被叫做函數重載。

在有些程式語言中，這種數據類型的識別，可以被延後至運行時間（後期綁定）。交替函數的選擇發生在運行時間，並依據動態確定的函數實際參數的類型。以這種方式選擇交替實現的函數，通常被稱為多方法。

### 理論

多分派語言的理論首先由Castagna等人開發，它為具有後期綁定的重載函數定義了模型。它產生了面向對象語言的協變與逆變問題的首次形式化，和二元方法（binary method）問題的一種解法。

## 例子

可以通過例子更加清晰的區分多分派和單一分派。假想一個遊戲，它有兩種（使用者可見的）物體：小行星和太空船；當兩個物體要相撞的時候，程序需要依據什麼物體要相撞而做不同的事情。

### 內建多分派

#### Common Lisp

在具有多分派的Common Lisp語言中，可以在Common Lisp對象系統中如下這樣實現：

```lisp
(defclass asteroid ()  ((size :reader size :initarg :size)))
(defclass spaceship () ((size :reader size :initarg :size)))
(defun space-object (class size) (make-instance class :size size))

; collide-with是具有多分派的泛化函数
(defmethod collide-with ((x asteroid)  (y asteroid))  "a/a")
(defmethod collide-with ((x asteroid)  (y spaceship)) "a/s")
(defmethod collide-with ((x spaceship) (y asteroid))  "s/a")
(defmethod collide-with ((x spaceship) (y spaceship)) "s/s")

(defun collide (x y)
  (if (and (> (size x) 100) (> (size y) 100))
    "big-boom"
    (collide-with x y)))

(print (collide (space-object 'asteroid 101)  (space-object 'spaceship 300)))
(print (collide (space-object 'asteroid 10)   (space-object 'spaceship 10)))
(print (collide (space-object 'spaceship 101) (space-object 'spaceship 10)))
```

並且對其他方法也是類似的。沒有使用顯式測試和「動態轉換」。

在這裡的宏`defclass`定義里的槽指定`(size :reader size :initarg :size)`中，首位的`size`是槽名字，其後是2個槽選項：`:reader size`指定在名為`size`的泛化函數上定義一個無限定符（unqualified）方法來讀取這個槽的值，`:initarg :size`聲明一個名為`:size`的初始化參數並指定這個初始化參數初始化這個槽。在這裡的標準泛化函數`make-instance`應用`(make-instance class :size size)`的參數中，`class`是要實例化的類，`:size size`是由成對的名字與值構成的初始化參數列表。

由於多分派的存在，方法要定義在類中並包含在對象中的傳統想法，變得不再吸引人了，上述每個`collide-with`方法，都附屬於兩個不同的類而非一個類。因此方法調用的特殊語法，一般會消失，從而方法調用看起來完全就像正常的函數調用，並且方法被組織入泛化函數而非類中。

#### Julia

Julia有內建的多分派，並且它是語言設計的中心。Julia版本的例子如下：

```julia
abstract type SpaceObject end

struct Asteroid <: SpaceObject
    size::Int
end
struct Spaceship <: SpaceObject
    size::Int
end

collide_with(::Asteroid, ::Asteroid)   = "a/a"
collide_with(::Asteroid, ::Spaceship)  = "a/s"
collide_with(::Spaceship, ::Asteroid)  = "s/a"
collide_with(::Spaceship, ::Spaceship) = "s/s"

collide(x::SpaceObject, y::SpaceObject) =
    x.size > 100 && y.size > 100 ? "Big boom!" : collide_with(x, y)
```

輸出：

```julia-repl
julia> collide(Asteroid(101), Spaceship(300))
"Big boom!"

julia> collide(Asteroid(10), Spaceship(10))
"a/s"

julia> collide(Spaceship(101), Spaceship(10))
"s/s"
```

#### C#

C#在版本4（2010年4月），使用關鍵字`dynamic`，介入了對動態多方法的支持。下面的例子展示多方法。像很多其他靜態類型的語言語言一樣，C#還支持靜態方法重載，Microsoft預期開發者在多數場景下會選用靜態類型超過動態類型。`dynamic`關鍵字支持COM對象和動態類型的.NET語言的互操作。

<image>

下面的例子使用了C# 9和C# 10介入的特徵比如記錄類型：

```c#
using static ColliderLibrary;

Console.WriteLine(Collide(new Asteroid(101), new Spaceship(300)));
Console.WriteLine(Collide(new Asteroid(10), new Spaceship(10)));
Console.WriteLine(Collide(new Spaceship(101), new Spaceship(10)));

string Collide(SpaceObject x, SpaceObject y) =>
    x.Size > 100 && y.Size > 100
        ? "Big boom!"
        : CollideWith(x as dynamic, y as dynamic); // Dynamic dispatch to CollideWith method

class ColliderLibrary {
    public static string CollideWith(Asteroid x, Asteroid y) => "a/a";
    public static string CollideWith(Asteroid x, Spaceship y) => "a/s";
    public static string CollideWith(Spaceship x, Asteroid y) => "s/a";
    public static string CollideWith(Spaceship x, Spaceship y) => "s/s";
}

abstract record SpaceObject(int Size);
record Asteroid(int Size) : SpaceObject(Size);
record Spaceship(int Size) : SpaceObject(Size);
```

輸出：

```output
Big boom!
a/s
s/s
```

#### Groovy

Groovy是兼容/互用於Java的通用的JVM語言，它對立於Java，使用後期綁定/多分派。

```groovy
/*
    Groovy implementation of C# example above
    Late binding works the same when using non-static methods or compiling class/methods statically
    (@CompileStatic annotation)
*/
class Program {
    static void main(String[] args) {
        println Collider.collide(new Asteroid(101), new Spaceship(300))
        println Collider.collide(new Asteroid(10), new Spaceship(10))
        println Collider.collide(new Spaceship(101), new Spaceship(10))
    }
}

class Collider {
    static String collide(SpaceObject x, SpaceObject y) {
        (x.size > 100 && y.size > 100) ? "big-boom" : collideWith(x, y)  // Dynamic dispatch to collideWith method
    }

    private static String collideWith(Asteroid x, Asteroid y) { "a/a" }
    private static String collideWith(Asteroid x, Spaceship y) { "a/s" }
    private static String collideWith(Spaceship x, Asteroid y) { "s/a" }
    private static String collideWith(Spaceship x, Spaceship y) { "s/s"}
}

class SpaceObject {
    int size
    SpaceObject(int size) { this.size = size }
}

@InheritConstructors class Asteroid extends SpaceObject {}
@InheritConstructors class Spaceship extends SpaceObject {}
```

### 庫擴展多分派

在不於語言定義或語法層次支持多分派的語言中，可能經常使用擴展庫來增加多分派。

#### Python

Python可以使用第三方庫擴展來增加多分派。例如，最早提出的模塊multimethods.py，提供了CLOS風格的多方法而不用變更語言的底層語法或關鍵字。Guido van Rossum使用Python 2.4介入的修飾器（decorator），建立了具有簡化語法的多方法的簡單實現。multipledispatch庫採用的形式與之一致。

模塊multimethod，採用了修飾器和Python 3.5介入的類型提示實現多方法，下面的多方法例子還基於了Python 3.10介入的聯合類型（`types.UnionType`）在Python 3.10之前的版本中，`SpaceObject`可以採用抽象基類：

python

from abc import ABCMeta, abstractmethod

class SpaceObject(metaclass=ABCMeta):

@abstractmethod

def __init__(self): pass

SpaceObject.register(Asteroid)

SpaceObject.register(Spaceship)

：

```python
from multimethod import multimethod

class Asteroid():
    def __init__(self, size=0):
        self.size = size

class Spaceship():
    def __init__(self, size=0):
        self.size = size

SpaceObject = Asteroid | Spaceship

@multimethod
def collide_with(x :Asteroid, y :Asteroid):
    return "a/a"

@multimethod
def collide_with(x :Asteroid, y :Spaceship):
    return "a/s"

@multimethod
def collide_with(x :Spaceship, y :Asteroid):
    return "s/a"

@multimethod
def collide_with(x :Spaceship, y :Spaceship):
    return "s/s"

def collide(x :SpaceObject, y :SpaceObject):
    assert isinstance(x, SpaceObject) \
        and isinstance(y, SpaceObject) 
    print("Big boom!" if x.size>100 and y.size>100
        else collide_with(x, y))
```

其執行：

```pycon
>>> collide(Asteroid(101), Spaceship(300))
Big boom!
>>> collide(Asteroid(10), Spaceship(10))
a/s
>>> collide(Spaceship(101), Spaceship(10))
s/s
```

plum庫也實現了這種形式的多分派。

#### JavaScript

JavaScript和TypeScript不在語言語法層次上支持多方法，但可以通過第三方庫擴展來增加多分派。例如，使用multimethod包，它提供了多分派、泛化函數的實現。這個庫的JavaScript的動態類型版本例子：

```javascript
import { multi, method } from '@arrows/multimethod'

class Asteroid {}
class Spaceship {}

const collideWith = multi(
    method([Asteroid, Asteroid], (x, y) => {
        // deal with asteroid hitting asteroid
    }),
     method([Asteroid, Spaceship], (x, y) => {
        // deal with asteroid hitting spaceship
    }),
    method([Spaceship, Asteroid], (x, y) => {
        // deal with spaceship hitting asteroid
    }),
    method([Spaceship, Spaceship], (x, y) => {
        // deal with spaceship hitting spaceship
    }),
)
```

這個庫還有TypeScript有對應的靜態類型版本。TypeScript的多方法示例：

```typescript
import { multi, method, Multi } from '@arrows/multimethod'

class Asteroid {}
class Spaceship {}

type CollideWith = Multi & {
    (x: Asteroid, y: Asteroid): void
    (x: Asteroid, y: Spaceship): void
    (x: Spaceship, y: Asteroid): void
    (x: Spaceship, y: Spaceship): void
}

const collideWith: CollideWith = multi(
    method([Asteroid, Asteroid], (x, y) => {
        // deal with asteroid hitting asteroid
    }),
    method([Asteroid, Spaceship], (x, y) => {
        // deal with asteroid hitting spaceship
    }),
    method([Spaceship, Asteroid], (x, y) => {
        // deal with spaceship hitting asteroid
    }),
    method([Spaceship, Spaceship], (x, y) => {
        // deal with spaceship hitting spaceship
    }),
)
```

#### C++

用C++17編寫的YOMM2第三方庫，提供了開放多方法的快速且正交性的實現。上述例子可通過它實現為：

```cpp
#include <yorel/yomm2/keywords.hpp>

import std;

using std::unique_ptr;

class Collideable {
public:
    virtual ~Collideable() = default;
};

class Asteroid : public Collideable {
    // ...
};

class Spaceship : public Collideable {
    // ...
};

register_classes(Collideable, Spaceship, Asteroid);

declare_method(void, collideWith, (virtual_<Collideable&>, virtual_<Collideable&>));

define_method(void, collideWith, (Collideable& left, Collideable& right)) {
    // default collision handling
}

define_method(void, collideWith, (Asteroid& left, Asteroid& right)) {
    // handle Asteroid-Asteroid collision
}

define_method(void, collideWith, (Asteroid& left, Spaceship& right)) {
    // handle Asteroid-Spaceship collision
}

define_method(void, collideWith, (Spaceship& left, Asteroid& right)) {
    // handle Spaceship-Asteroid collision
}

define_method(void, collideWith, (Spaceship& left, Spaceship& right)) {
    // handle Spaceship-Spaceship collision
}

int main(int argc, char* argv[]) {
    yorel::yomm2::update_methods();

    unique_ptr<Collideable> a1(std::make_unique<Asteroid>());
    unique_ptr<Collideable> a2(std::make_unique<Asteroid>());
    unique_ptr<Collideable> s1(std::make_unique<Spaceship>());
    unique_ptr<Collideable> s2(std::make_unique<Spaceship>());
    // note: types partially erased

    collideWith(*a1, *a2); // Asteroid-Asteroid collision
    collideWith(*a1, *s1); // Asteroid-Spaceship collision
    collideWith(*s1, *a1); // Spaceship-Asteroid collision
    collideWith(*s1, *s2); // Spaceship-Spaceship collision

    return 0;
}
```

### 模擬多分派

#### C

C語言沒有動態分派，它必須手工的以某種形式實現。經常使用一個`enum`來識別一個對象的子類型。動態分派可以在一個函數指針分支表中查找這個值來完成。下面是採用C語言的簡單例子：

```c
typedef void (*CollisionCase)(void);

void collision_AA(void) 
{ /* handle Asteroid-Asteroid collision  */ };
void collision_AS(void)
{ /* handle Asteroid-Spaceship collision */ };
void collision_SA(void)
{ /* handle Spaceship-Asteroid collision */ };
void collision_SS(void)
{ /* handle Spaceship-Spaceship collision*/ };

typedef enum {
    THING_ASTEROID = 0,
    THING_SPACESHIP,
    THING_COUNT /* 它自身不是事物类型，转而用来表示事物的数目 */
} Thing;

CollisionCase collisionCases[THING_COUNT][THING_COUNT] = {
    {&collision_AA, &collision_AS},
    {&collision_SA, &collision_SS}
};

void collide(Thing a, Thing b)
{
    (*collisionCases[a][b])();
}

int main(void) 
{
    collide(THING_SPACESHIP, THING_ASTEROID);
}
```

C語言使用C Object System庫，可以支持類似於CLOS的動態分派。它是完全可擴展的並且方法不需要任何的手工處理。動態消息（方法）通過COS分派器來分派，它比Objective-C更快。下面是使用COS的例子：

```c
#include <stdio.h>
#include <cos/Object.h>
#include <cos/gen/object.h>

/* 类 */
defclass (Asteroid)
/* 数据成员 */
endclass

defclass (Spaceship)
/* 数据成员 */
endclass

/* 泛化函数 */
defgeneric (_Bool, collide_with, _1, _2);

/* 多方法 */
defmethod (_Bool, collide_with, Asteroid, Asteroid)
    /* deal with asteroid hitting asteroid */
endmethod

defmethod (_Bool, collide_with, Asteroid, Spaceship)
    /* deal with asteroid hitting spaceship */
endmethod

defmethod (_Bool, collide_with, Spaceship, Asteroid)
    /* deal with spaceship hitting asteroid */
endmethod

defmethod (_Bool, collide_with, Spaceship, Spaceship)
    /* deal with spaceship hitting spaceship */
endmethod

/* 用例 */
int main(int argc, char *argv[])
{
    OBJ a = gnew(Asteroid);
    OBJ s = gnew(Spaceship);

    printf("<a,a> = %d\n", collide_with(a, a));
    printf("<a,s> = %d\n", collide_with(a, s));
    printf("<s,a> = %d\n", collide_with(s, a));
    printf("<s,s> = %d\n", collide_with(s, s));

    grelease(a);
    grelease(s);
}
```

#### C++

截至目前，C++本身只支持單分派，下面是使用`dynamic_cast`來模擬多分派的例子：

```cpp
 // Example using run time type comparison via dynamic_cast

 struct Thing {
     virtual void collideWith(Thing& other) = 0;
 };

 struct Asteroid : Thing {
     void collideWith(Thing& other) {
         // dynamic_cast to a pointer type returns NULL if the cast fails
         // (dynamic_cast to a reference type would throw an exception on failure)
         if (auto asteroid = dynamic_cast<Asteroid*>(&other)) {
             // handle Asteroid-Asteroid collision
         } else if (auto spaceship = dynamic_cast<Spaceship*>(&other)) {
             // handle Asteroid-Spaceship collision
         } else {
             // default collision handling here
         }
     }
 };

 struct Spaceship : Thing {
     void collideWith(Thing& other) {
         if (auto asteroid = dynamic_cast<Asteroid*>(&other)) {
             // handle Spaceship-Asteroid collision
         } else if (auto spaceship = dynamic_cast<Spaceship*>(&other)) {
             // handle Spaceship-Spaceship collision
         } else {
             // default collision handling here
         }
     }
 };
```

#### Java

在Java這種只有單分派但支持方法重載的語言中，多分派可以通過多層單分派來模擬：

<image>

```java
interface Collideable {
    void collideWith(final Collideable other);

    /* These methods would need different names in a language without method overloading. */
    void collideWith(final Asteroid asteroid);
    void collideWith(final Spaceship spaceship);
}

class Asteroid implements Collideable {
    public void collideWith(final Collideable other) {
        // Call collideWith on the other object.
        other.collideWith(this);
    }

    public void collideWith(final Asteroid asteroid) {
        // Handle Asteroid-Asteroid collision.
    }

    public void collideWith(final Spaceship spaceship) {
        // Handle Asteroid-Spaceship collision.
    }
}

class Spaceship implements Collideable {
    public void collideWith(final Collideable other) {
        // Call collideWith on the other object.
        other.collideWith(this);
    }

    public void collideWith(final Asteroid asteroid) {
        // Handle Spaceship-Asteroid collision.
    }

    public void collideWith(final Spaceship spaceship) {
        // Handle Spaceship-Spaceship collision.
    }
}
```

還可以在一層或兩層上使用運行時`instanceof`檢查。

#### Python

在Python中可以通過採用標準庫`functools`中的`singledispatchmethod`，將方法變換為單一分派泛化函數，這個實際上是雙分派的多分派例子還可以實現為：

```python
from functools import singledispatchmethod

class Asteroid():
    def __init__(self, size=0):
        self.size = size
    @singledispatchmethod
    def collide_with(self, other): pass
    
class Spaceship():
    def __init__(self, size=0):
        self.size = size
    @singledispatchmethod
    def collide_with(self, other): pass

SpaceObject = Asteroid | Spaceship

@Asteroid.collide_with.register
def _(self, other :Asteroid):
    return "a/a"
@Asteroid.collide_with.register
def _(self, other :Spaceship):
    return "a/s"

@Spaceship.collide_with.register
def _(self, other :Asteroid):
    return "s/a"
@Spaceship.collide_with.register
def _(self, other :Spaceship):
    return "s/s"

def collide(x, y):
    assert isinstance(x, SpaceObject) \
        and isinstance(y, SpaceObject) 
    print("Big boom!" if x.size>100 and y.size>100
        else x.collide_with(y))
```

下面的例子通過命名約定採用了反射式實現方式模擬多分派：

```python
class SpaceObject():
    def collide_with(self, *args):
        key = ('_'+type(self).__name__
            +''.join('_'+type(i).__name__ for i in args)
            +'__collide')
        return (self.__getattribute__(key)(*args)
            if key in self.__dir__() else None)

class Asteroid(SpaceObject):
    def __init__(self, size=0):
        self.size = size
    def _Asteroid_Asteroid__collide(self, other):
        return "a/a"
    def _Asteroid_Spaceship__collide(self, other):
        return "a/s"

class Spaceship(SpaceObject):
    def __init__(self, size=0):
        self.size = size
    def _Spaceship_Asteroid__collide(self, other):
        return "s/a"
    def _Spaceship_Spaceship__collide(self, other):
        return "s/s"

def collide(x, y):
    assert isinstance(x, SpaceObject) \
        and isinstance(y, SpaceObject) 
    print("Big boom!" if x.size>100 and y.size>100
        else x.collide_with(y))
```

其執行：

```pycon
>>> collide(Spaceship(101), Asteroid(300))
Big boom!
>>> collide(Asteroid(10), Asteroid(10))
a/a
>>> collide(Spaceship(101), Asteroid(10))
s/a
```

## 程式語言支持

### 主范型

- Julia

### 支持通用的多方法

- C♯ 4.0
- Cecli (程式語言)
- Clojure
- Common Lisp（通過Common Lisp對象系統）
- Dylan
- Fortress (程式語言)
- Groovy
- Lasso (程式語言)
- Nim，在v0.20之後泛化方法被廢止，使用多方法需要加編譯指令
- Raku
- R
- Seed7
- TADS
- VB.Net，通過後期綁定，還通過.Net DLR
- Wolfram語言，通過符號模式匹配
- Xtend

### 通過擴展

- 任何.NET語言（通過庫MultiMethods.NET）
- C（通過庫C Object System）
- C#（通過庫multimethod-sharp）
- C++（通過庫yomm2和omm）
- D（通過庫openmethods）
- Factor（通過標準multimethods詞彙表)
- Java（使用擴展MultiJava）
- JavaScript（通過包@arrows/multimethod）
- Perl（通過模塊Class::Multimethods）
- Python（模塊multimethod、multipledispatch或plum）
- Racket（通過庫multimethod-lib）
- Ruby（通過Multiple Dispatch庫、Multimethod包和Vlx-Multimethods包）
- Scheme（通過TinyCLOS）
- TypeScript（通過包@arrows/multimethod）