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

Question

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

10

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

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

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

- Samuel Okechukwu

我认为，单态化对于具体类型的方法专门化和静态分派是等价的，但对于多态递归类型，我有些困惑，因为我无法真正阅读我找到的 Haskell 示例。在 Julia 中，具有多态递归类型的方法是什么样子的？这篇最近的文章是一个例子吗？https://dev59.com/5G0NtIcB2Jgan1znL5pG - BatWannaBe

一个二叉树，其中每个节点都可以是叶子或一对树（可以是叶子或一对树（可以是...）），这是否是一个递归多态类型？如果是的话，Julia只会为它所见过的类型生成代码。如果你有一个树遍历器，Julia会先生成一对情况的代码。它将使用该代码进入树，直到遇到叶子，并在那一点上为叶子情况生成代码。还要记住，多态性在Julia中并不完全是它看起来的样子。它只是对帮助函数分派的类型的约束。 - Ted Dunning

https://dev59.com/5G0NtIcB2Jgan1znL5pG?noredirect=1&lq=1 中的 Branch{T} 答案是否对您有帮助？ - Ted Dunning

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ted Dunning · Accepted Answer

这个问题看起来非常类似于在Julia中用递归调用减少JIT时间

为了回答这个问题，我将会对那里给出的代码进行改编、修正和阐述。

首先是一些定义：

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{... 这样的类型。使用 BiTree{Int64} 可以看出 Branch{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})

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