Julia 是否对递归多态类型执行代码单态化？

Question

我注意到，在执行代码单态化的语言（例如：C++、Rust 等）中实现多态递归类型即使不是不可能，也是非常困难的。这通常是因为编译器需要为该类型的每个可能的实例化生成代码，这通常会导致无限递归。

支持此功能的语言通常使用类型擦除。编译器不会尝试实例化下一个递归调用，因为它已经知道类型的布局。

Julia 执行代码单态化，但它支持多态递归。我的猜测是，它是通过延迟实例化泛型类型或函数直到实际调用它来实现这一点的。但是，我认为这可能最终会使用大量内存，特别是当递归非常深时。所以我的问题是，Julia 是否仍会对多态递归类型执行代码单态化，还是会退回到类型擦除或其他方法？

Answer 1

这个问题看起来与Reducing JIT time with recursive call in Julia非常相似

\n

为了回答这个问题，我将调整、更正和详细说明那里给出的代码。

\n

首先是一些定义：

\n

abstract type BiTree{T} end\n\nstruct Branch{T} <: BiTree{T} \n    left::BiTree{T}\n    right::BiTree{T}\nend\n\nstruct Leaf{T} <: BiTree{T}\n    value::T\nend\n\nBase.foldl(f, b::Branch) = f(foldl(f, b.left), foldl(f, b.right))\nBase.foldl(f, l::Leaf) = f(l.value)\n\n\n# fancy and concise constructor operations\n(\xe2\x8a\x95)(l::Branch, r::Branch) = Branch(l, r) # just for illustration\n(\xe2\x8a\x95)(l, r::Branch) = Branch(Leaf(l), r)\n(\xe2\x8a\x95)(l::Branch, r) = Branch(l, Leaf(r))\n(\xe2\x8a\x95)(l, r) = Branch(Leaf(l), Leaf(r))\n

\n

这里我们有一个抽象类型和两个子类型，一种是树中内部节点的复合类型，另一种是叶子的子类型。我们还有两行递归操作来定义如何折叠或减少树中的值，以及一个简洁的树中缀构造函数。

\n

如果我们定义my_tree然后用加法折叠它，我们会得到：

\n

julia> my_tree = ((((6 \xe2\x8a\x95 7) \xe2\x8a\x95 (6 \xe2\x8a\x95 7)) \xe2\x8a\x95 ((7 \xe2\x8a\x95 7) \xe2\x8a\x95 (0 \xe2\x8a\x95 7))) \xe2\x8a\x95 (((8 \xe2\x8a\x95 7) \xe2\x8a\x95 (7 \xe2\x8a\x95 7)) \xe2\x8a\x95 ((8 \xe2\x8a\x95 8) \xe2\x8a\x95 (8 \xe2\x8a\x95 0)))) \xe2\x8a\x95 ((((2 \xe2\x8a\x95 4) \xe2\x8a\x95 7) \xe2\x8a\x95 (6 \xe2\x8a\x95 (0 \xe2\x8a\x95 5))) \xe2\x8a\x95 (((6 \xe2\x8a\x95 8) \xe2\x8a\x95 (2 \xe2\x8a\x95 8)) \xe2\x8a\x95 ((2 \xe2\x8a\x95 1) \xe2\x8a\x95 (4 \xe2\x8a\x95 5))));\n\njulia> typeof(my_tree)\nBranch{Int64}\n\njulia> foldl(+, my_tree)\n160\n

\n

请注意， 的类型my_tree完全暴露了它是一个带有某种子节点的内部节点，但我们无法真正看到它有多深。我们没有得到像Branch{Branch{Leaf{Int32}, Branch{.... Branch{Int64}a 的事实BiTree{Int64}可以使用

\n

julia> isa(my_tree, BiTree{Int64})\ntrue\n

\n

但仅从 的值来看它是不可见的my_tree，而且深度在类型中也不可见。

\n

如果我们看看迄今为止作为我们工作的副作用生成的方法，我们会看到这一点

\n

julia> using MethodAnalysis\n\njulia> methodinstances(\xe2\x8a\x95)\n4-element Vector{Core.MethodInstance}:\n MethodInstance for \xe2\x8a\x95(::Branch{Int64}, ::Branch{Int64})\n MethodInstance for \xe2\x8a\x95(::Int64, ::Branch{Int64})\n MethodInstance for \xe2\x8a\x95(::Branch{Int64}, ::Int64)\n MethodInstance for \xe2\x8a\x95(::Int64, ::Int64)\n\njulia> methodinstances(foldl)\n3-element Vector{Core.MethodInstance}:\n MethodInstance for foldl(::typeof(+), ::Branch{Int64})\n MethodInstance for foldl(::typeof(+), ::Leaf{Int64})\n MethodInstance for foldl(::typeof(+), ::BiTree{Int64})\n

\n

无论我们尝试构建哪种 32 位整数树，这就是我们所需要的。无论我们尝试用 减少什么树+，这就是我们所需要的。

\n

如果我们尝试使用不同的运算符进行折叠，我们可以获得更多方法

\n

julia> foldl(max, my_tree)\n8\n\njulia> methodinstances(foldl)\n6-element Vector{Core.MethodInstance}:\n MethodInstance for foldl(::typeof(+), ::Branch{Int64})\n MethodInstance for foldl(::typeof(max), ::Branch{Int64})\n MethodInstance for foldl(::typeof(+), ::Leaf{Int64})\n MethodInstance for foldl(::typeof(max), ::Leaf{Int64})\n MethodInstance for foldl(::typeof(+), ::BiTree{Int64})\n MethodInstance for foldl(::typeof(max), ::BiTree{Int64})\n

\n

有趣的是，方法的数量增加了，但并没有爆炸。

\n