是什么讓Julia變得獨(dú)一無二？

作者：盧鑫旺 2022-10-28 10:17:58

一文了解Julia的多重派發(fā)

　　作者丨Erik Engheim

　　譯者 | 盧鑫旺

　　審校丨諾亞

　　Julia作為一門編程語言，雖然發(fā)展很快，但其生態(tài)系統(tǒng)仍有進(jìn)步空間，加上Julia把重點(diǎn)放在了科學(xué)計(jì)算這一相對(duì)小眾的領(lǐng)域，因而關(guān)注度不如Python等熱門語言。但是，這些事實(shí)都無法掩蓋Julia在科學(xué)計(jì)算領(lǐng)域的巨大的優(yōu)勢(shì)。

　　多重派發(fā)（multiple dispatch）是Julia編程語言的殺手級(jí)特性，不過卻幾乎沒有開發(fā)人員聽說過它，更鮮有人知道它是什么以及是如何工作的。這不奇怪，因?yàn)楹苌儆姓Z言支持多重派發(fā)，而那些能支持多重派發(fā)的語言又往往很好地隱藏了它。因此，在我大談特談多重派發(fā)的厲害之前，我必須先解釋它到底是什么。

　　我先給你一個(gè)提示：它與函數(shù)的調(diào)用方式有關(guān)，讓我們來后退一步來詳細(xì)說明。

　　當(dāng)程序運(yùn)行并遇到函數(shù)調(diào)用時(shí)，它必須找出并跳轉(zhuǎn)到要執(zhí)行的代碼。在一些過程編程語言（如C或者Pascal）中，這個(gè)過程很直接。每個(gè)函數(shù)都被實(shí)現(xiàn)為一個(gè)子例程，在內(nèi)存中有唯一的位置，調(diào)用函數(shù)只需跳轉(zhuǎn)到子例程的內(nèi)存地址，并執(zhí)行每個(gè)指令即可，直到處理器遇到返回指令。

　　在處理函數(shù)指針時(shí)，事情變得有些棘手。我們跳轉(zhuǎn)到的子例程可以在運(yùn)行時(shí)期間更改，因?yàn)榇a允許更改函數(shù)指針中存儲(chǔ)的子例程地址。我為什么要提到這些細(xì)節(jié)？因?yàn)槲蚁氡磉_(dá)的是，調(diào)用函數(shù)并決定執(zhí)行什么代碼并不總是一件小事。

　　思考一下在面向?qū)ο缶幊讨幸{(diào)用一個(gè)方法的復(fù)雜性。

1. warrior.attack(knight)

　　比如我們定義了一個(gè)叫“戰(zhàn)士”的類Warrior，Warrior類中的成員函數(shù) attack 并不是對(duì)應(yīng)到一個(gè)有指定內(nèi)存地址的子例程。當(dāng)attack方法被一個(gè)warrior對(duì)象調(diào)用時(shí)，決定跳轉(zhuǎn)到哪個(gè)子例程的復(fù)雜過程就會(huì)啟動(dòng)。我們必須確定是哪一個(gè)Warrior類的實(shí)例化對(duì)象在調(diào)用attack方法。你可以想象不同類型層次結(jié)構(gòu)的“戰(zhàn)士”類的實(shí)例化對(duì)象，比如弓箭手，槍手或者騎士。

上圖是具有不同屬性的“戰(zhàn)士”類的對(duì)象的類型結(jié)構(gòu)

　　因?yàn)楣值墓舴绞讲煌陂L(zhǎng)槍手或騎士，所以不同的“戰(zhàn)士”類的對(duì)象的攻擊方法都不一樣。通過一個(gè)稱為單一派發(fā)的過程，我們決定調(diào)用哪個(gè)方法。從低級(jí)的角度來看，我們?cè)噲D確定在執(zhí)行warrior.attack(knight)這條語句時(shí)跳轉(zhuǎn)到哪個(gè)子例程。

　　單一派發(fā)如何工作取決于我們討論的是動(dòng)態(tài)類型語言還是靜態(tài)類型語言。我們看一下它在動(dòng)態(tài)類型語言中的工作原理，因?yàn)槲覀儗堰@個(gè)過程和Julia語言進(jìn)行比較，同時(shí)后者也是一種動(dòng)態(tài)類型的語言。

　　想象我們有兩個(gè)Warrior類的實(shí)例化對(duì)象warrior a和 warrior b，a戰(zhàn)士正在攻擊b戰(zhàn)士。我們的第一步是要確定戰(zhàn)士a的類型是什么。在動(dòng)態(tài)類型語言中，每個(gè)類對(duì)象都知道它的類型是什么。以O(shè)bject-C語言為例，每個(gè)對(duì)象都有一個(gè)叫“isa”的屬性，這個(gè)屬性指向了一個(gè)類對(duì)象來描述當(dāng)前對(duì)象是一個(gè)什么類型。在下圖中，我們模擬了這個(gè)過程，a戰(zhàn)士是Archer類的實(shí)例化對(duì)象，Archer類包含了每個(gè)實(shí)現(xiàn)方法的函數(shù)指針，為了找到正確的方法，我們對(duì)”attack”方法進(jìn)行字典查找。

動(dòng)態(tài)類型語言使用單一派發(fā)來定位要執(zhí)行的代碼

　　上圖中方法名末尾的感嘆號(hào)可能看起來很奇怪。不用擔(dān)心，這只是一種命名約定，在Lisp語言和Julia語言中很流行，用于更改函數(shù)。它沒有語義。

　　嚴(yán)格地說，在大多數(shù)動(dòng)態(tài)語言中談?wù)摵瘮?shù)指針是錯(cuò)誤的。例如，在Ruby中，你實(shí)際上并沒有指向任何具有機(jī)器代碼的子例程，而是指向通過解析方法生成的抽象語法樹（AST）。Ruby解釋器解釋AST以運(yùn)行方法中的代碼。

y=4*(2+x)的語法樹（AST）

　　我們剛才討論的稱為單一派發(fā)（single dispatch），因?yàn)橛晌覀冏约焊鶕?jù)單個(gè)對(duì)象決定調(diào)用什么方法。對(duì)象b的類型不會(huì)以任何方式影響方法查找過程。相比之下，對(duì)于多重派發(fā)，函數(shù)調(diào)用中的每個(gè)參數(shù)都在決定選擇調(diào)用哪個(gè)方法中起了作用。我知道這聽起來很奇怪，所以讓我通過解釋單一派發(fā)的問題來給你一個(gè)使用多重派發(fā)的動(dòng)機(jī)。

多重派發(fā)解決了什么問題？

　　我們用Julia編寫了一個(gè)battle!函數(shù)，它通過調(diào)用attack!函數(shù)來模擬兩個(gè)戰(zhàn)士a，b進(jìn)行戰(zhàn)斗，并根據(jù)結(jié)果將信息打印出來。下面的大部分代碼是易懂的。在Julia中，我們用::來把變量名與變量類型分開。因此，在示例代碼中，a::Warrior是在告訴Julia battle!函數(shù)有一個(gè)名為a的Warrior類型的參數(shù)。

1. function battle!(a::Warrior, b::Warrior)  
2.     attack!(a, b)  
3.     if a.health == 0 && b.health == 0  
4.         println(a.name, " and ", b.name, " destroyed each other")  
5.     elseif a.health == 0  
6.         println(b.name, " defeated ", a.name)  
7.     elseif b.health == 0  
8.         println(a.name, " defeated ", b.name)  
9.     else  
10.         println(b.name, " survived attack from ", a.name)  
11.     end  
12. end

　　觀察上邊的代碼并問自己這樣一個(gè)簡(jiǎn)單的問題：類似的代碼在C++或者Java中是否有效？乍一看，這似乎是可能的。這兩種語言都允許你定義具有相同名稱但不同參數(shù)的多個(gè)函數(shù)，你可以編寫類似下面的Julia代碼的代碼：

1. function attack!(a::Archer, b::Archer)  
2.     if a.arrows > 0  
3.         shoot!(a)  
4.         damage = 6 + rand(1:6)  
5.         b.health = max(b.health - damage, 0)  
6.     end  
7.     a.health, b.health  
8. end  
9.   
10. function attack!(a::Archer, b::Knight)  
11.     if a.arrows > 0  
12.         shoot!(a)  
13.         damage = rand(1:6)  
14.         if b.mounted  
15.             damage += 3  
16.         end  
17.         b.health = max(b.health - damage, 0)  
18.     end  
19.     a.health, b.health  
20. end  
21.   
22. function attack!(a::Knight, b::Knight)  
23.     a.health = max(a.health - rand(1:6), 0)  
24.     b.health = max(b.health - rand(1:6), 0)  
25.     a.health, b.health  
26. end

　　代碼的細(xì)節(jié)并不重要。我想讓你從這個(gè)代碼示例中了解到的是，我們已經(jīng)定義了三個(gè)attack!函數(shù)。每個(gè)定義接受不同類型的實(shí)參。在C++和Java中，我們稱這個(gè)函數(shù)為重載。在編譯時(shí)，編譯器將通過檢查調(diào)用站點(diǎn)上每個(gè)輸入實(shí)參的類型來選擇要調(diào)用的適當(dāng)函數(shù)。

　　關(guān)鍵點(diǎn)是：C++編譯器不可能猜出battle!函數(shù)調(diào)用的是哪個(gè)attack!函數(shù)，因?yàn)樗恢缹?shí)參a和b的具體類型。編譯器只知道這兩個(gè)實(shí)參都是Warrior類型的某個(gè)子類型。至于到底是哪個(gè)子類型只能在代碼實(shí)際運(yùn)行時(shí)確定。這是一個(gè)遺憾，因?yàn)楹瘮?shù)重載只在編譯時(shí)工作。

　　在這種情況下，多重派發(fā)可以做單一派發(fā)和函數(shù)重載都不能做的事情：它可以在運(yùn)行時(shí)根據(jù)參數(shù)a和b的類型選擇正確的代碼。

多重派發(fā)是如何工作的？

　　還記得如何通過在運(yùn)行時(shí)查找正確的方法來完成單一派發(fā)嗎?多重派發(fā)也是關(guān)于如何選擇正確的方法。你剛才看到的attack!定義實(shí)際上不是函數(shù)定義，而是方法定義。在定義attack!函數(shù)時(shí)，你可以這樣寫：

function attack! end

　　為什么沒有參數(shù)呢？因?yàn)樵贘ulia中函數(shù)沒有參數(shù)，只有方法中有參數(shù)。與面向?qū)ο蟮恼Z言不同，Julia中的方法是附加到函數(shù)而不是類上的。

　　因此，Julia中的函數(shù)調(diào)用首先通過查找被調(diào)用的函數(shù)來執(zhí)行。Julia在每個(gè)函數(shù)上注冊(cè)一個(gè)方法表。從上到下搜索這個(gè)表，以找到一個(gè)方法，該方法接受與函數(shù)調(diào)用站點(diǎn)提供的輸入實(shí)參類型相匹配的實(shí)參類型。

函數(shù)被調(diào)用時(shí)Julia如何使用多重派發(fā)

　　來定位正確執(zhí)行的代碼

　　Julia是一種即時(shí)（JIT）編譯語言，因此方法源代碼需要幾個(gè)步驟才能轉(zhuǎn)化為可執(zhí)行的機(jī)器碼：

　　1.當(dāng)Julia文件加載到內(nèi)存中時(shí)，將解析每個(gè)方法的源代碼并將其轉(zhuǎn)換為抽象語法樹（AST）。

　　2.每個(gè)方法的AST都存儲(chǔ)在正確函數(shù)的正確方法表中。

　　3.在運(yùn)行時(shí)，當(dāng)一個(gè)方法被定位時(shí)，我們首先獲得AST, AST被JIT編譯器轉(zhuǎn)化為機(jī)器碼并緩存以供以后查找。

　　這個(gè)過程實(shí)際上比我在這里展示的要復(fù)雜得多。你可以看到，抽象語法樹可以非常通用。它可以是為數(shù)字參數(shù)定義的計(jì)算。無論參數(shù)是16位無符號(hào)整數(shù)還是32位有符號(hào)整數(shù)，執(zhí)行的計(jì)算都是相同的。但是，這些情況的程序集代碼看起來不一樣。因此，同一個(gè)AST可以產(chǎn)生多個(gè)機(jī)器碼子例程。Julia將為方法表中的每個(gè)案例添加一個(gè)條目。因此，方法表并不局限于為其編寫源代碼的方法的數(shù)量。

什么讓Julia的多重派發(fā)獨(dú)一無二

　　每次調(diào)用Julia中的函數(shù)時(shí)，都會(huì)執(zhí)行一個(gè)方法查找?；蛘吒_切地說，從Julia開發(fā)人員的角度來看，情況就是這樣。代碼運(yùn)行時(shí)就好像每次都是這樣。

　　在支持多重派發(fā)的其他語言中，情況并非如此。只有以特殊方式標(biāo)記的函數(shù)才使用多重派發(fā)。否則，將執(zhí)行常規(guī)函數(shù)調(diào)用。為什么其他語言限制了多重派發(fā)的使用？因?yàn)樵贘ulia到來之前，多重派發(fā)非常慢。

　　不難想象為什么多重派發(fā)會(huì)比較慢。您可能需要通過一個(gè)大表進(jìn)行線性搜索O（N）的時(shí)間復(fù)雜度，而不是在常數(shù)時(shí)間內(nèi)進(jìn)行單個(gè)字典查找O(1)。函數(shù)可以有一個(gè)巨大的方法表。

　　Julia是如何規(guī)避這個(gè)問題的？Julia的設(shè)計(jì)理念是盡可能保持類型的穩(wěn)定。在Python或JavaScript等語言中，情況并非如此?？梢栽谶\(yùn)行時(shí)添加或刪除字段和方法。單個(gè)字段的類型可以更改。在Julia身上，類型被設(shè)計(jì)得更加固定。定義復(fù)合類型時(shí)，需要固定字段及其類型的數(shù)量。

　　這種設(shè)計(jì)選擇是如何影響多重派發(fā)的？這意味著由Julia JIT編譯器完成的代碼分析變得容易得多。代碼的行為變得更加可預(yù)測(cè)，這使得有可能識(shí)別更多的情況，在調(diào)用函數(shù)時(shí)應(yīng)該定位的方法變得完全確定和可預(yù)測(cè)。記住，如果函數(shù)調(diào)用的參數(shù)類型保持不變，那么Julia將始終查找相同的方法。如果代碼分析可以確定函數(shù)的哪些參數(shù)永遠(yuǎn)不會(huì)改變，那么JIT編譯器就可以用直接的函數(shù)調(diào)用替換多分派查找。如果代碼很短，甚至可以內(nèi)聯(lián)。

　　因此，Julia成功地將一開始的性能劣勢(shì)變成了性能優(yōu)勢(shì)。因此，Julia函數(shù)調(diào)用通常比面向?qū)ο笳Z言中的單一派發(fā)調(diào)用要快得多。

　　一旦你達(dá)到了閃電般的速度，那么在你的編碼風(fēng)格發(fā)生變化的任何地方都可以使用多重派發(fā)。始終保持多重派發(fā)對(duì)Julia社區(qū)中的軟件工程實(shí)踐產(chǎn)生了深遠(yuǎn)的影響。

通過多重派發(fā)重用代碼

　　面向?qū)ο笳Z言的用戶通過繼承類和實(shí)現(xiàn)接口來重用代碼，這允許將新代碼插入到現(xiàn)有框架中。Julia方法是在函數(shù)級(jí)重用。不同的開發(fā)人員都可以向相同的函數(shù)添加方法。我們不擴(kuò)展類，而是擴(kuò)展函數(shù)。因?yàn)楹瘮?shù)存在于較低的粒度級(jí)別，所以我們有更多的機(jī)會(huì)進(jìn)行代碼重用。

　　這種靈活性的一個(gè)簡(jiǎn)單例子是Julia標(biāo)準(zhǔn)庫中定義的show函數(shù)。Julia使用它在不同的上下文中顯示一個(gè)值。上下文可以是REPL(交互式命令行)、筆記本或IDE環(huán)境。匹配以下兩個(gè)簽名的方法可以添加到show函數(shù)中：

1. show(io::IO, mime, x)  
2. show(io::IO, x)

　　io對(duì)象表示用于顯示值x的目標(biāo)。io可以是控制臺(tái)窗口、文件、文本字符串、套接字或圖形顯示。值x可以是簡(jiǎn)單的數(shù)字、日期、文本字符串或更復(fù)雜的對(duì)象，如字典或數(shù)組。

　　與面向?qū)ο蟮木幊陶Z言不同，你可以沿著多個(gè)維度擴(kuò)展顯示功能。你可以為全新的IO子類型添加show方法，以在新的上下文中顯示現(xiàn)有的值類型。假設(shè)我們創(chuàng)建了特殊類型來表示溫度單位攝氏度、華氏度和開爾文。可以添加方法來顯示，以便用正確的單位顯示代表溫度的數(shù)字。

　　注意，在Julia中可以用等號(hào)定義一行函數(shù)。

1. show(io::IO, t::Celsius)    = print(io, t.value, "°C")  
2. show(io::IO, t::Fahrenheit) = print(io, t.value, "°F")  
3. show(io::IO, t::Kelvin)     = print(io, t.value, "K")

　　為了理解這個(gè)擴(kuò)展機(jī)制為何如此強(qiáng)大，請(qǐng)?jiān)试S我指出一些你試圖使用面向?qū)ο缶幊虖?fù)制這個(gè)擴(kuò)展機(jī)制時(shí)會(huì)遇到的問題。你設(shè)計(jì)一個(gè)系統(tǒng)，其中每個(gè)對(duì)象都必須實(shí)現(xiàn)一個(gè)顯示方法來顯示，但這種選擇會(huì)導(dǎo)致幾個(gè)問題：

　　所有的類都必須繼承一個(gè)帶有show方法的基類。
　　每個(gè)對(duì)象將在每個(gè)IO對(duì)象類型上獲得相同的表示。

　　也就是說：許多面向?qū)ο蟮南到y(tǒng)最終都有過于復(fù)雜的基類。原因是你想為每個(gè)對(duì)象支持太多的功能：

　　在不同的上下文中可視化一個(gè)對(duì)象，比如在調(diào)試器中
　　用于打印或存儲(chǔ)到文件中的文本表示
　　為了允許使用集合中的對(duì)象使用哈希函數(shù)

　　例如，你可以在Java和Objective-C中找到這種模式。這種做法是僵化的。如果基類設(shè)計(jì)錯(cuò)誤，將對(duì)所有相關(guān)代碼產(chǎn)生嚴(yán)重后果。

　　更不用說，如果語言設(shè)計(jì)者忘記添加show方法，那么就沒有簡(jiǎn)單的方法來改進(jìn)它。只有對(duì)標(biāo)準(zhǔn)庫進(jìn)行更新才能修復(fù)它。作為第三方開發(fā)人員，你不能改造解決方案。相反，如果Julia標(biāo)準(zhǔn)庫沒有定義show函數(shù)，你可以很容易地自己定義它，并發(fā)布一個(gè)庫來實(shí)現(xiàn)公共對(duì)象的可視化，并且你可以將其分發(fā)給其他人。

　　u和v是向量，而A到F是點(diǎn)。向量表示點(diǎn)之間的差。u是點(diǎn)F和E的差。

　　讓我們多談?wù)処/O系統(tǒng)的問題。假設(shè)你已經(jīng)創(chuàng)建了一個(gè)名為Vector2D的2D向量類型。在控制臺(tái)中使用時(shí)，你可能希望將向量顯示為[4,8]，而如果I/O對(duì)象表示圖形顯示，則希望顯示箭頭。這兩種選擇在Julia中都是可能的，因?yàn)槟憧梢詾閕o參數(shù)是一個(gè)圖形顯示而x參數(shù)是一個(gè)2D向量的情況編寫專門的方法。相比之下，面向?qū)ο笳Z言只能根據(jù)io或x的類型選擇要執(zhí)行的方法，而不能同時(shí)根據(jù)兩者。記住，對(duì)于單一派發(fā)，在運(yùn)行時(shí)調(diào)用的方法是基于單個(gè)參數(shù)的類型選擇的，而不是基于多個(gè)參數(shù)的類型。

　　當(dāng)然，你可以拋出一個(gè)switch-case語句來處理不同的類型，但這是不可擴(kuò)展的。每次添加新類型時(shí)，都必須修改switch-case語句。這將阻止你將代碼作為可重用庫分發(fā)。庫用戶不應(yīng)該修改第三方庫的源代碼來擴(kuò)展它。

多重派發(fā)的效用

　　模擬不同類型的戰(zhàn)士之間的戰(zhàn)斗或者編寫I/O系統(tǒng)當(dāng)然只是幾種情況，這些情況可以簡(jiǎn)化編碼。當(dāng)我在電子游戲中編寫碰撞檢測(cè)代碼時(shí)，它第一次發(fā)現(xiàn)我需要這樣的東西。不同的游戲?qū)ο髸?huì)用不同的幾何形狀來表示。問題是計(jì)算兩個(gè)圓，兩個(gè)正方形或圓和正方形的交點(diǎn)是完全不同的。你不能只看一個(gè)參數(shù)就決定要使用的算法，你需要兩個(gè)參數(shù)。如果沒有多重派發(fā)，你的解決方案將變得混亂。