多重调度的难以理解的表现

在过场动画中，提议对朱莉娅语言的主要开发者之一斯蒂芬·卡平斯基（Stefan Karpinsky）解密报告。 在报告中，他讨论了便捷高效的多重调度的意外结果，这些结果被当作Julia的主要范例。

译者 ：该报告的标题引用了尤金·维格纳（Eugene Wigner）的文章“自然科学中数学的不可理解的效力”。

多重调度是Julia语言的关键范例，在它的存在期间，我们（该语言的开发人员）注意到了一些期望，但同时也令人困惑。 至少我们没有看到我们所期望的那样。 这就是事实– Julia生态系统中的代码重用程度达到惊人的水平，这比我所知道的任何其他语言都高得多。

我们不断地看到有人编写通用代码，有人定义了新的数据类型，这些人彼此不熟悉，然后有人将此代码应用于这种不寻常的数据类型……而这确实有效。 而且这种情况经常发生。
我一直认为应该从面向对象的编程中获得这种行为，但是我使用了许多面向对象的语言，事实证明，通常一切都无法在它们中起作用。 因此，在某种程度上，我想：为什么朱莉娅在这方面是一种有效的语言？ 为什么那里的代码重用级别如此之高？ 而且-从中可以学到什么教训，其他语言可以借鉴朱莉娅来变得更好？

有时，当我这样说时，公众不相信我，但是您已经在JuliaCon上了，因此您知道发生了什么，因此我将重点关注为什么会发生这种情况。

但是对于初学者-我最喜欢的例子之一。

幻灯片是Chris Rakaukas的工作成果。 他编写了各种非常通用的软件包来求解微分方程。 您可以根据需要输入双数或BigFloat。 然后他以某种方式决定要查看积分结果的错误。 还有一个Measurements程序包，它可以通过一系列公式跟踪物理量的值和误差的传播。 该软件包还使用Unicode字符±支持不确定性值的优美语法。 在幻灯片上可以看到，重力加速度，摆的长度，初始速度，偏斜角都是已知的，但存在某种误差。 因此，您定义了一个简单的摆，将其运动方程传递到求解器ODE和-bam！ - 一切正常 。 您会看到一个带有胡须错误的图形。 而且，我仍然没有显示用于绘制图形的代码也已通用化，您只是从Measurements.jl中输入了一个带有错误的值，并获得了一个带有错误的图形。

不同程序包的兼容性和代码的泛化程度简直让人难以接受。 它是如何工作的 ？ 原来是。

好吧，不是说我们根本没有想到这一点。 毕竟， 正是因为该语言允许我们表达广义算法，所以我们在语言中包含了多重调度的概念。 因此，以上所有内容都不是那么疯狂。 但是，从理论上了解这一点是一回事，而在实践中看到该方法确实有效是另一回事。 毕竟，C ++中的单次调度和运算符重载也应产生类似的结果-但实际上，它们经常无法按预期运行。

另外，我们在开发语言时所看到的比我们预想的还多：不仅在编写通用代码。 接下来，我将尝试说明更多。

因此，有两种类型的代码重用，它们有很大的不同。 一个是广义算法，这是他们记住的第一件事。 第二个不那么明显但似乎更重要的方面是Julia的简单性，它在各种软件包中使用相同的数据类型。 在某种程度上，发生这种情况是因为类型方法不会成为其使用的障碍：您无需就其继承的接口和方法与类型作者达成共识； 您可以简单地说：“哦，我喜欢这种RGB。我将对它进行自己的操作，但我喜欢它的结构。”

前言 多重调度与函数重载

现在，我不得不提到C ++或Java中的函数重载，因为不断有人问我有关它们的问题。 乍一看，它与多重调度没有什么不同。 有什么区别，为什么函数重载更糟？

我将从朱莉娅的例子开始：

 abstract type Pet end struct Dog <: Pet; name::String end struct Cat <: Pet; name::String end function encounter(a::Pet, b::Pet) verb = meets(a, b) println("$(a.name) meets $(b.name) and $verb") end meets(a::Dog, b::Dog) = "sniffs" meets(a::Dog, b::Cat) = "chases" meets(a::Cat, b::Dog) = "hisses" meets(a::Cat, b::Cat) = "slinks" 

我们定义Pet的抽象类型，为此引入Dog和Cat的子类型，它们有一个name字段（代码重复了一点，但是是可以容忍的），并定义了一个通用的“会议”功能，该功能Pet参数的Pet类型的两个对象。 在其中，我们首先计算由调用通用meet()函数的结果确定的“动作”，然后打印描述会议的句子。 在meets()函数中，我们使用多个分派来确定一只动物遇到另一只动物时所执行的动作。

添加几只狗和几只猫，然后查看会议结果：

 fido = Dog("Fido") rex = Dog("Rex") whiskers = Cat("Whiskers") spots = Cat("Spots") encounter(fido, rex) encounter(rex, whiskers) encounter(spots, fido) encounter(whiskers, spots) 

现在，我们将尽可能从字面上将其“翻译”为C ++。 用name字段定义Pet类-在C ++中我们可以做到这一点（顺便说一下，C ++的优点之一是甚至可以将数据字段添加到抽象类型中。然后我们定义基本的meets()函数，为两个Pet类型的对象定义encounter()函数，并且，最后，定义派生类Dog和Cat并为其进行重载meets() ：

 class Pet { public: string name; }; string meets(Pet a, Pet b) { return "FALLBACK"; } void encounter(Pet a, Pet b) { string verb = meets(a, b); cout << a.name << " meets " << b. name << " and " << verb << endl; } class Cat : public Pet {}; class Dog : public Pet {}; string meets(Dog a, Dog b) { return "sniffs"; } string meets(Dog a, Cat b) { return "chases"; } string meets(Cat a, Dog b) { return "hisses"; } string meets(Cat a, Cat b) { return "slinks"; } 

像Julia代码一样， main()函数可以创建狗和猫，并使它们满足：

 int main() { Dog fido; fido.name = "Fido"; Dog rex; rex.name = "Rex"; Cat whiskers; whiskers.name = "Whiskers"; Cat spots; spots.name = "Spots"; encounter(fido, rex); encounter(rex, whiskers); encounter(spots, fido); encounter(whiskers, spots); return 0; } 

因此，针对功能重载的多重调度。 ！

您认为通过多次分派返回代码是什么？

 Fido meets Rex and sniffs Rex meets Whiskers and chases Spots meets Fido and hisses Whiskers meets Spots and slinks 

 Fido meets Rex and FALLBACK Rex meets Whiskers and FALLBACK Spots meets Fido and FALLBACK Whiskers meets Spots and FALLBACK 

因此，在C ++方法中，归因于编译器使用在编译阶段静态派生的类型这一事实，因此，一般化的Julia代码的直接“翻译”没有给出所需的行为。 关键是我们要基于运行时变量具有的实际具体类型来调用函数。 模板函数虽然可以改善情况，但仍然需要在编译时静态地了解表达式中包括的所有类型，并且很容易提出一个不可能的示例。

对我来说，这样的例子表明，多重调度是正确的事情，而其他所有方法都不能很好地近似正确的结果。

现在让我们看看这样的表。 希望您觉得它有意义：

在没有调度的语言中，您只需编写f(x, y, ...) ，所有参数的类型都是固定的，即 对f()的调用是对单个函数f()的调用，该函数可以在程序中。 表达的程度是恒定的：调用f()总是只做一件事。 单一调度是1990年代和2000年代向OOP过渡的重大突破。 人们通常喜欢使用点语法。 并且出现了另一个表达机会：根据对象x ₁的类型调度呼叫。 表达机会的特征在于集合的力量| X ₁ | 具有f()方法的类型。 但是，在多次分派中，函数f()的潜在选项的数量等于参数可以所属的类型集的笛卡尔乘积的幂。 当然，实际上，在一个程序中几乎没有人需要这么多不同的功能。 但是这里的关键是，程序员可以使用一种简单而自然的方式来使用这种多样性的任何元素，这导致机会呈指数增长。

第1部分。通用编程

让我们谈谈通用代码-多重调度的主要功能。

这是通用代码的一个（完全人工的）示例：

 using LinearAlgebra function inner_sum(A, vs) t = zero(eltype(A)) for v in vs t += inner(v, A, v) #  ! end return t end inner(v, A, w) = dot(v, A * w) #    

这里的A有点像矩阵（尽管我没有指出类型，我可以用名字猜出一些东西），而vs是一些类似矢量的元素的向量，然后通过这个“矩阵”考虑标量积，对此给出了通用定义，但未指定任何类型。 这里的通用编程就是在循环中调用inner()函数（专业建议：如果您要编写通用代码，只需删除任何类型限制）。

因此，“看，妈妈，它有效”：

 julia> A = rand(3, 3) 3×3 Array{Float64,2}: 0.934255 0.712883 0.734033 0.145575 0.148775 0.131786 0.631839 0.688701 0.632088 julia> vs = [rand(3) for _ in 1:4] 4-element Array{Array{Float64,1},1}: [0.424535, 0.536761, 0.854301] [0.715483, 0.986452, 0.82681] [0.487955, 0.43354, 0.634452] [0.100029, 0.448316, 0.603441] julia> inner_sum(A, vs) 6.825340887556694 

没什么特别的，它可以计算一些值。 但是 -该代码是以通用的方式编写的，并且只要可以对它们执行相应的操作，该代码就可以对任何A和vs起作用。

至于特定数据类型的效率-多么幸运。 我的意思是，对于密集的矢量和矩阵，此代码将“按原样”进行操作-它将通过调用BLAS操作等生成机器代码。 等 如果传递静态数组，则编译器将考虑到这一点，扩展周期，应用向量化-一切都应如此。

但是更重要的是，该代码将适用于新类型，并且您不仅可以使它变得超级高效，而且还可以使它效率更高！ 让我们定义一个新的类型（这是机器学习中使用的实际数据类型），即单一矢量（单热矢量）。 这是一个向量，其中一个分量为1，所有其他分量为零。 您可以非常紧凑地想象它：只需存储向量的长度和非零分量的数量即可。

 import Base: size, getindex, * struct OneHotVector <: AbstractVector{Int} len :: Int ind :: Int end size(v::OneHotVector) = (v.len,) getindex(v::OneHotVector, i::Integer) = Int(i == v.ind) 

实际上，这实际上是添加它的包中的整个类型定义。 有了这个定义， inner_sum()也可以工作：

 julia> vs = [OneHotVector(3, rand(1:3)) for _ in 1:4] 4-element Array{OneHotVector,1}: [0, 1, 0] [0, 0, 1] [1, 0, 0] [1, 0, 0] julia> inner_sum(A, vs) 2.6493739294755123 

但是对于标量产品，这里使用通用定义-对于此类数据，它很慢，而不是凉爽！

因此，一般定义会起作用，但并非总是以最佳方式起作用，并且在使用Julia时可能会偶尔遇到此问题：“嗯，已调用了一般定义，这就是为什么此GPU代码已经运行了第五个小时了……”

默认情况下，在inner()将调用向量对矩阵乘积的一般定义，将其乘以单一向量后，将返回Vector{Float64}类型的列之一的副本。 然后，使用the矢量和此列调用标量积dot()的一般定义，这会做很多不必要的工作。 实际上，对于每个组件，都会选中“您等于一个吗？您呢？” 等

我们可以极大地优化此过程。 例如，只需选择一列即可用OneHotVector替换矩阵乘法。 很好，请定义此方法，仅此而已。

 *(A::AbstractMatrix, v::OneHotVector) = A[:, v.ind] 

这里就是力量 ：无论第一个参数是什么，我们都说“我们想派第二个参数 ”。 这样的定义将简单地将行从矩阵中拉出，并且比一般方法要快得多-删除了对列的迭代和求和。

但是您可以走得更远，直接优化inner() ，因为通过矩阵将两个through矢量相乘只会拉出该矩阵的一个元素：

 inner(v::OneHotVector, A, w::OneHotVector) = A[v.ind, w.ind] 

这就是承诺的超级双效率。 而所有需要的就是定义这个inner()方法。

此示例显示了多重调度的一种应用：有一个函数的一般定义，但是对于某些数据类型，它不能达到最佳效果。 然后，我们逐点添加了一种方法，该方法可以保留这些类型的函数行为 ，但工作效率更高 。

但是还有另一个领域-当没有函数的一般定义时，我想为某些类型添加功能。 然后，您可以轻松地添加它。

第三个选项-您只想拥有相同的函数名，但对于不同的数据类型却具有不同的行为-例如，要使函数在使用字典和数组时表现不同。

如何在单一调度语言中获得类似的行为？ 可能，但是困难。 问题：重载函数*必须在第二个参数上分派，而不是在第一个参数上分派。 您可以执行双重调度：首先，通过第一个参数调度并调用AbstractMatrix.*(v)方法。 然后，此方法调用类似v.__rmul__(A) ，即 现在，原始调用中的第二个参数已成为实际调用其方法的对象。 __rmul__取自Python，这种行为是一种标准模式，但它似乎仅适用于加法和乘法。 即 如果我们要调用一个名为+或*的函数，则可以解决双重调度的问题，否则-,，不是我们今天的事情。 使用C ++和其他语言-您需要制造自己的自行车。

好的， inner()呢？ 现在有三个参数，调度在第一个和第三个上进行。 单次使用语言处理语言尚不清楚。 我从未见过“三重派遣”。 没有好的解决方案。 通常，当出现类似的需求时（并且在数字代码中经常出现），人们最终会实施他们的多重调度系统。 如果您在Python中查看大型项目进行数值计算，您会惊奇地发现其中有很多这样的项目。 自然地，这样的实现会因地制宜，设计欠佳，漏洞百出且运行缓慢（请参阅Greenspan的第十条规则 -大约Transl。 ），因为Jeff Besancon并未从事任何这些项目的工作（ Julia中类型调度系统的作者和首席开发人员-大约翻译 ）。

第2部分。常规类型

我将传递到Julia范式的反面-常规类型。 在我看来，这是该语言的主要“主力军”，因为我在该领域中观察到了高水平的代码重用。

例如，假设您具有RGB类型，例如ColorTypes.jl所具有的类型。 它没有什么复杂的，只有三个值组合在一起。 为了简单起见，我们假定类型不是参数化的（但可以是），并且作者为他定义了一些他认为有用的基本操作。 您采用这种类型，然后思考：“嗯，我想对此类型添加更多操作。” 例如，将RGB想象为一个向量空间（严格来说，这是不正确的，但将归结为一阶近似值）。 在Julia中，您只需将所有缺少的操作添加到您的代码中。

问题出现了-cho？ 我为什么这么集中精力呢？ 事实证明，在基于类的面向对象的语言中，这种方法难以实现。 由于这些语言中的方法定义位于类定义的内部，因此只有两种添加方法的方法：编辑类代码以添加所需的行为，或者使用必需的方法创建继承者类。

第一个选项扩大了基类的定义，并且还迫使基类的开发人员在更改代码时要注意支持所有添加的方法。 有一天有什么可能使此类课程不被支持。

继承是经典的“推荐”选项，但也并非没有缺陷。 首先，您需要更改类名称-现在让它不是RGB ，而是MyRGB 。 此外，新方法将不再适用于原始RGB类； 如果我想将新方法应用于通过他人代码创建的RGB对象，则需要将其转换或包装在MyRGB 。 但这不是最坏的情况。 如果我使用一些附加功能制作了MyRGB类，则其他OurRGB ，等等。 -那么，如果有人想要一个具有所有新功能的类，则需要使用多重继承（并且仅在编程语言允许的情况下才这样做！）。

因此，这两种选择都是马马虎虎。 但是，还有其他解决方案：

• 将函数放在外部函数而不是类方法中-转到f(x, y)而不是xf(y) 。 但是，随后的通用行为就丢失了。
• 重复使用代码（在我看来，在许多情况下，这种情况会发生）。 只需复制自己的外星人RGB类并添加缺少的内容即可。

在重用代码方面，Julia的关键功能几乎完全简化为该方法在类型之外定义的事实。 仅此而已。 使用单调度语言执行相同操作-类型可以轻松重复使用。 实际上，“让我们的制作方法成为课程的一部分”的整个故事是一个马马虎虎的想法。 的确，有一个好处-将类用作名称空间。 如果我写xf(y) f()不需要在当前名称空间中，则必须在名称空间x进行搜索。 是的，这是一件好事-值得所有其他麻烦吗？ 我不知道 我认为没有（尽管您的猜测是我的观点有些偏颇）。

结语。 表达问题

在20世纪70年代就注意到了这样的编程问题。 它在很大程度上与静态类型检查有关，因为它以这种语言出现。 是的，我认为这与静态类型检查无关。 问题的实质如下：是否可以在不借助可疑技术的情况下同时更改数据模型和对数据的操作集。

该问题或多或少可以归结为以下内容：

1. 是否可以轻松且无错误地添加适用于现有方法的 新数据类型 ，以及
2. 是否可以在现有类型上添加新操作 。

（1）容易用面向对象的语言完成，而功能上则困难，（2）-反之亦然。 从这个意义上讲，我们可以谈论OOP和FP方法的二元论。

在多调度语言中，两种操作都很容易。 (1) , (2) — . , . ( https://en.wikipedia.org/wiki/Expression_problem ), . ? , , . , " , " — " " . " , " , , .

, . , , — .

, Julia ( ), . .