跳至內容

多分派

維基百科,自由的百科全書

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

理解分派

[編輯]

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

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

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

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

數據類型

[編輯]

對於編譯時間可以區分數據類型的程式語言,在交替英語Alternation (formal language theory)(alternative)函數中進行選擇,可以發生在編譯時間,創建交替函數用於編譯時間選擇的活動,通常被叫做函數重載

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

例子

[編輯]

可以通過例子更加清晰的區分多分派和單一分派。假想一個遊戲,它有兩種(用戶可見的)物體:飛船和小行星。當兩個物體要相撞的時候,程序需要依據什麼物體要相撞而做不同的事情。

具有內建多分派的語言

[編輯]

Common Lisp

[編輯]

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

(defgeneric collide (x y))
(defclass asteroid () ())
(defclass spaceship () ())
(defmethod collide-with ((x asteroid) (y asteroid))
  ;; deal with asteroid hitting asteroid
  )
(defmethod collide-with ((x asteroid) (y spaceship))
  ;; deal with asteroid hitting spaceship
  )
(defmethod collide-with ((x spaceship) (y asteroid))
  ;; deal with spaceship hitting asteroid
  )
(defmethod collide-with ((x spaceship) (y spaceship))
  ;; deal with spaceship hitting spaceship
  )

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

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

Julia

[編輯]

Julia有內建的多分派,並且它是語言設計的中心[3]。Julia版本的例子如下:

collide_with(x::Asteroid, y::Asteroid) = ... # deal with asteroid hitting asteroid
collide_with(x::Asteroid, y::Spaceship) = ... # deal with asteroid hitting spaceship
collide_with(x::Spaceship, y::Asteroid) = ... # deal with spaceship hitting asteroid
collide_with(x::Spaceship, y::Spaceship) = ... # deal with spaceship hitting spaceship

C#

[編輯]

C#在版本4(2010年4月),使用關鍵字dynamic,介入了對動態多方法的支持[4]。下面的例子展示多方法協同於在版本8(2019年9月)中介入的switch表達式[5]。像很多其他靜態類型的語言語言一樣,C#還支持靜態方法重載[6],Microsoft預期開發者在多數場景下會選用靜態類型超過動態類型[7]dynamic關鍵字支持COM對象和動態類型的.NET語言的互操作。

class Program
{
    static void Main()
    {
        Console.WriteLine(Collider.Collide(new Asteroid(101),  new Spaceship(300)));
        Console.WriteLine(Collider.Collide(new Asteroid(10),   new Spaceship(10)));
        Console.WriteLine(Collider.Collide(new Spaceship(101), new Spaceship(10)));
    }
}

static class Collider
{
    public static string Collide(SpaceObject x, SpaceObject y) =>
        ((x.Size > 100) && (y.Size > 100)) ?
            "Big boom!" : CollideWith(x as dynamic, y as dynamic);
    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";
}

abstract class SpaceObject
{
    public SpaceObject(int size) => Size = size;

    public int Size { get; }
}

class Asteroid : SpaceObject
{
    public Asteroid(int size) : base(size) { }
}

class Spaceship : SpaceObject
{
    public Spaceship(int size) : base(size) { }
}

輸出:

big-boom
a/s
s/s

Groovy

[編輯]

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

/*
    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 {}

用多分派庫擴展的語言

[編輯]

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

JavaScript

[編輯]

JavaScriptTypeScript不在語言語法層次上支持多方法,但可以通過庫來增加多分派。例如,使用multimethod包[9],它提供了多分派、泛化函數的實現。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有對應的靜態類型版本。[a]

Python

[編輯]

可以使用擴展來向Python增加多分派。例如,最早的模塊multimethods.py[10],它為Python提供了CLOS風格的多方法而不用變更語言的底層語法或關鍵字。在功能上,這非常類似於CLOS例子,但是語法是常規Python的。[b] Guido van Rossum使用Python 2.4介入的修飾器(decorator),出品了多方法的具有簡化了的語法的一個簡單實現,他為此定義了multimethod修飾器[11][c] multipledispatch[12]採用的形式與之一致。

模塊multimethod[13],採用了修飾器和Python 3.5介入的類型提示實現多方法:

from multimethod import multimethod

class Asteroid(): pass

class Spaceship(): pass

@multimethod
def collide_with(x: Asteroid, y: Asteroid):
    '''deal with asteroid hitting asteroid'''
    print("asteroid hitting asteroid")

@multimethod
def collide_with(x: Asteroid, y: Spaceship):
    '''deal with asteroid hitting spaceship'''
    print("asteroid hitting spaceship")

@multimethod
def collide_with(x: Spaceship, y: Asteroid):
    '''deal with spaceship hitting asteroid'''
    print("spaceship hitting asteroid")

@multimethod
def collide_with(x: Spaceship, y: Spaceship):
    '''deal with spaceship hitting spaceship'''
    print("spaceship hitting spaceship")
>>> a = Asteroid()
>>> b = Spaceship()
>>> collide_with(a, b)
asteroid hitting spaceship

此外,還有PEAK-Rules包提供語法類似上述例子的多分派[14],它後來被替代為PyProtocols[15]。Reg庫也支持多分派和謂詞分派[16]

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

#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 Object System庫,而以某種形式手工實現。動態分派經常使用enum來標識一個對象的子類型,然後可通過在函數指針分支表英語branch table中查找這個值來完成。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 /* not a type of thing itself, instead used to find number of things */
} 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);
}

Java

[編輯]

在只有單一分派的語言比如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檢查可以在一個或兩個層次上使用。

代碼示例

[編輯]
  1. ^ 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
      }),
    )
    
  2. ^ Python的multimethods.py示例:
    from multimethods import Dispatch
    from game_objects import Asteroid, Spaceship
    from game_behaviors import as_func, ss_func, sa_func
    collide = Dispatch()
    collide.add_rule((Asteroid, Spaceship), as_func)
    collide.add_rule((Spaceship, Spaceship), ss_func)
    collide.add_rule((Spaceship, Asteroid), sa_func)
    def aa_func(a, b):
        """Behavior when asteroid hits asteroid."""
        # ...define new behavior...
    collide.add_rule((Asteroid, Asteroid), aa_func)
    
    # ...later...
    collide(thing1, thing2)
    
  3. ^ Python的van Rossum最初的多方法實現:
    @multimethod(Asteroid, Asteroid)
    def collide(a, b):
        """Behavior when asteroid hits a asteroid."""
        # ...define new behavior...
    @multimethod(Asteroid, Spaceship)
    def collide(a, b):
        """Behavior when asteroid hits a spaceship."""
        # ...define new behavior...
    # ... define other multimethod rules ...
    

引用

[編輯]
  1. ^ Ranka, Sanjay; Banerjee, Arunava; Biswas, Kanad Kishore; Dua, Sumeet; Mishra, Prabhat; Moona, Rajat. Contemporary Computing: Second International Conference, IC3 2010, Noida, India, August 9–11, 2010. Proceedings. Springer. 2010-07-26 [2021-03-23]. ISBN 9783642148248. (原始內容存檔於2021-04-27). 
  2. ^ Igor Wojda. Programmer dictionary: Receiver. Kt.Academy. 2018-02-08 [2020-02-27] (英語). 
  3. ^ Bezanson, Jeff; Edelman, Alan; Karpinski, Stefan; Shah, Viral B. Julia: A fresh approach to numerical computing. SIAM Review. 7 February 2017, 59 (1): 65–98. arXiv:1411.1607可免費查閱. doi:10.1137/141000671. 
  4. ^ Using type dynamic (C# Programming Guide). [2020-05-14]. (原始內容存檔於2021-05-26). 
  5. ^ switch expression (C# reference). [2020-05-14]. (原始內容存檔於2021-06-28). 
  6. ^ Basic concepts. [2020-05-14]. (原始內容存檔於2021-04-16). 
  7. ^ Dynamic .NET - Understanding the Dynamic Keyword in C# 4. [2020-05-14]. (原始內容存檔於2021-05-24). 
  8. ^ Groovy - Multi-methods. [2021-04-15]. (原始內容存檔於2021-04-16). 
  9. ^ 9.0 9.1 9.2 @arrows/multimethod頁面存檔備份,存於互聯網檔案館) Multiple dispatch in JavaScript/TypeScript with configurable dispatch resolution by Maciej Cąderek.
  10. ^ multimethods.py頁面存檔備份,存於互聯網檔案館), Multiple dispatch in Python with configurable dispatch resolution by David Mertz, et al.
  11. ^ Five-minute Multimethods in Python. [2014-07-13]. (原始內容存檔於2021-05-29). 
  12. ^ 12.0 12.1 multipledispatch. [2021-04-15]. (原始內容存檔於2020-11-11). 
  13. ^ 13.0 13.1 Coady, Aric, multimethod: Multiple argument dispatching., [2021-01-28], (原始內容存檔於2020-12-31) 
  14. ^ PEAK-Rules 0.5a1.dev. Python Package Index. [21 March 2014]. (原始內容存檔於2017-03-14). 
  15. ^ PyProtocols. Python Enterprise Application Kit. [26 April 2019]. (原始內容存檔於2021-05-05). 
  16. ^ 16.0 16.1 Reg. Read the docs. [26 April 2019]. (原始內容存檔於2021-03-05). 
  17. ^ 17.0 17.1 C Object System: A framework that brings C to the level of other high level programming languages and beyond: CObjectSystem/COS. 2019-02-19 [2021-03-30]. (原始內容存檔於2021-05-01). 
  18. ^ Methods. The Julia Manual. Julialang. [11 May 2014]. (原始內容存檔於2016-07-17). 
  19. ^ Multimethods in C# 4.0 With 'Dynamic'. [2009-08-20]. (原始內容存檔於2009-08-25). 
  20. ^ Cecil Language. [2008-04-13]. (原始內容存檔於2016-09-01). 
  21. ^ Multimethods in Clojure. [2008-09-04]. (原始內容存檔於2015-09-20). 
  22. ^ Steele, Guy L. 28. Common LISP: The Language. Bedford, MA, U.S.A: Digital Press. 1990 [2021-03-30]. ISBN 978-1-55558-041-4. (原始內容存檔於2017-12-17). 
  23. ^ Background and Goals. [2008-04-13]. (原始內容存檔於2020-04-04). 
  24. ^ The Fortress Language Specification, Version 1.0 (PDF). [2010-04-23]. (原始內容 (PDF)存檔於2013-01-20). 
  25. ^ Multimethods in Groovy. [2008-04-13]. (原始內容存檔於2011-08-12). 
  26. ^ Methods – LassoGuide 9.2. [2014-11-11]. (原始內容存檔於2021-06-13). 
  27. ^ Visitor Pattern Versus Multimethods. [2008-04-13]. (原始內容存檔於2021-02-05). 
  28. ^ Nim Manual: Multi-methods. [2020-09-11]. (原始內容存檔於2021-06-15). 
  29. ^ Perl 6 FAQ. [2008-04-13]. (原始內容存檔於2012-03-13). 
  30. ^ How S4 Methods Work (PDF). [2008-04-13]. (原始內容存檔 (PDF)於2021-05-10). 
  31. ^ Multiple Dispatch in Seed7. [2011-04-23]. (原始內容存檔於2021-01-29). 
  32. ^ TADS 3 System Manual. [2012-03-19]. (原始內容存檔於2017-02-14). 
  33. ^ VB.Net Multiple Dispatch. [2020-03-31]. (原始內容存檔於2021-04-11). 
  34. ^ New Features in C#4.0 and VB.Net 10.0. [2020-03-31]. (原始內容存檔於2021-02-01). 
  35. ^ Notes for Programming Language Experts. [2016-08-21]. (原始內容存檔於2021-06-26). 
  36. ^ Multiple dispatch. [2021-03-30]. (原始內容存檔於2021-05-08). 
  37. ^ MultiMethods.NET. [2014-07-13]. (原始內容存檔於2010-02-26). 
  38. ^ multimethod-sharp. [2021-03-30]. (原始內容存檔於2016-01-23). 
  39. ^ yomm2. [2021-03-30]. (原始內容存檔於2020-11-12). 
  40. ^ multimethods. [2021-03-30]. (原始內容存檔於2020-11-22). 
  41. ^ openmethods
  42. ^ multimethods vocabulary. [2014-07-13]. (原始內容存檔於2021-04-29). 
  43. ^ MultiJava. [2014-07-13]. (原始內容存檔於2021-04-11). 
  44. ^ Class::Multimethods. [2014-07-13]. (原始內容存檔於2013-10-21). 
  45. ^ multimethod-lib. [2021-03-30]. (原始內容存檔於2021-04-29). 
  46. ^ The Multiple Dispatch Library. [2021-03-30]. (原始內容存檔於2021-04-30). 
  47. ^ Multimethod Package. [2021-03-30]. (原始內容存檔於2021-04-29). 
  48. ^ Vlx-Multimethods Package. [2021-03-30]. (原始內容存檔於2021-04-27). 
  49. ^ TinyCLOS. [2014-07-13]. (原始內容存檔於2008-12-11). 

外部連結

[編輯]
  • Stroustrup, Bjarne; Solodkyy, Yuriy; Pirkelbauer, Peter. Open Multi-Methods for C++ (PDF). ACM 6th International Conference on Generative Programming and Component Engineering. 2007 [2014-07-13]. (原始內容存檔 (PDF)於2021-04-29). 
  • Dynamic multiple dispatch. docs.racket-lang.org. [2018-03-12]. (原始內容存檔於2021-04-29).