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

Question

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

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

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

Answer 1

这个问题看起来非常类似于Reducing JIT time with recursive calls in Julia

为了回答这个问题，我将修改、修正和详细说明给出的代码。

首先是一些定义：

abstract type BiTree{T} end

struct Branch{T} <: BiTree{T} 
    left::BiTree{T}
    right::BiTree{T}
end

struct Leaf{T} <: BiTree{T}
    value::T
end

Base.foldl(f, b::Branch) = f(foldl(f, b.left), foldl(f, b.right))
Base.foldl(f, l::Leaf) = f(l.value)


# fancy and concise constructor operations
(⊕)(l::Branch, r::Branch) = Branch(l, r) # just for illustration
(⊕)(l, r::Branch) = Branch(Leaf(l), r)
(⊕)(l::Branch, r) = Branch(l, Leaf(r))
(⊕)(l, r) = Branch(Leaf(l), Leaf(r))

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

如果我们定义了my_tree，然后将它与加法折叠起来，我们将得到以下内容：

julia> my_tree = ((((6 ⊕ 7) ⊕ (6 ⊕ 7)) ⊕ ((7 ⊕ 7) ⊕ (0 ⊕ 7))) ⊕ (((8 ⊕ 7) ⊕ (7 ⊕ 7)) ⊕ ((8 ⊕ 8) ⊕ (8 ⊕ 0)))) ⊕ ((((2 ⊕ 4) ⊕ 7) ⊕ (6 ⊕ (0 ⊕ 5))) ⊕ (((6 ⊕ 8) ⊕ (2 ⊕ 8)) ⊕ ((2 ⊕ 1) ⊕ (4 ⊕ 5))));

julia> typeof(my_tree)
Branch{Int64}

julia> foldl(+, my_tree)
160

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

julia> isa(my_tree, BiTree{Int64})
true

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

如果我们看一下到目前为止作为我们工作的副作用而产生的方法，我们就会看到

julia> using MethodAnalysis

julia> methodinstances(⊕)
4-element Vector{Core.MethodInstance}:
 MethodInstance for ⊕(::Branch{Int64}, ::Branch{Int64})
 MethodInstance for ⊕(::Int64, ::Branch{Int64})
 MethodInstance for ⊕(::Branch{Int64}, ::Int64)
 MethodInstance for ⊕(::Int64, ::Int64)

julia> methodinstances(foldl)
3-element Vector{Core.MethodInstance}:
 MethodInstance for foldl(::typeof(+), ::Branch{Int64})
 MethodInstance for foldl(::typeof(+), ::Leaf{Int64})
 MethodInstance for foldl(::typeof(+), ::BiTree{Int64})

无论我们试图构造一个由32位整数组成的树，这就是我们所需要的。不管我们试图用+来减少哪棵树，这就是我们所需要的。

如果我们尝试用不同的操作符折叠，我们可以得到更多的方法。

julia> foldl(max, my_tree)
8

julia> methodinstances(foldl)
6-element Vector{Core.MethodInstance}:
 MethodInstance for foldl(::typeof(+), ::Branch{Int64})
 MethodInstance for foldl(::typeof(max), ::Branch{Int64})
 MethodInstance for foldl(::typeof(+), ::Leaf{Int64})
 MethodInstance for foldl(::typeof(max), ::Leaf{Int64})
 MethodInstance for foldl(::typeof(+), ::BiTree{Int64})
 MethodInstance for foldl(::typeof(max), ::BiTree{Int64})

有趣的是，方法的数量在增加，但不会爆炸。