Julia 是否对递归多态类型执行代码单态化? [英] Does julia perform code monomorphization for recursively polymorphic types?

问题描述

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

I've noticed that implementing polymorphic recursive types in languages that perform code monomorphization (for e.g: C++, Rust, etc.) is very difficult, if not impossible. This is usually because the compiler needs to generate code for every possible instantiation of the type, which usually leads to infinite recursion.

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

Languages which support this usually use type erasure. The compiler will not try to instantiate the next recursive call because it already knows the layout of the type.

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

Julia performs code monomorphization, and yet it supports polymorphic recursion. My guess is that it does this by delaying instantiating a generic type or function until it is actually called. However, I think that this might end up using a lot of memory especially when the recursion is very deep. So my question is, will julia still perform code monomorphization for polymorphic recursive type or does it fall back to type erasure or some other method?

推荐答案

这个问题看起来很像 在 Julia 中通过递归调用减少 JIT 时间

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

To answer the question, I will adapt, correct and elaborate on the code given there.

首先是一些定义:

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))

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

Here we have an abstract type and two sub-types, one composite for interior nodes in the tree and one for the leaves. We also have a recursive operation in two lines to define how to fold or reduce the values in the tree and a nice concise infix constructor for trees.

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

If we define my_tree and then fold it with addition, we get this:

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} 的事实是可见的使用

Note that the type of my_tree completely exposes that it is an interior node with children of some sort, but we can't really see how deep it is. We don't get types like Branch{Branch{Leaf{Int32}, Branch{.... The fact that Branch{Int64} is a BiTree{Int64} is visible using

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

但仅从 my_tree 的值是看不到的，并且深度在类型中是不可见的.

But it isn't visible just from the value of my_tree alone and the depth isn't visible in the type.

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

If we look at the methods generated as a side effect of our work so far, we see this

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 位整数树，这就是我们所需要的.无论我们尝试使用 + 减少什么树，这就是我们所需要的.

No matter what tree of 32-bit integers we try to construct, that's all we will need. And no matter what tree we try to reduce with +, that's all we will need.

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

We can get more methods if we try folding with a different operator

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})

这里有趣的是方法的数量在增加，但并没有爆炸.

The interesting thing here is that the number of methods grows, but doesn't explode.

这篇关于Julia 是否对递归多态类型执行代码单态化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！