Выполняет ли julia мономорфизацию кода для рекурсивно полиморфных типов?

Question

Я заметил, что реализация полиморфных рекурсивных типов в языках, выполняющих мономорфизацию кода (например, C++, Rust и т. д.), очень сложна, если не невозможна. Обычно это происходит потому, что компилятору необходимо генерировать код для каждого возможного экземпляра типа, что обычно приводит к бесконечной рекурсии.

Языки, поддерживающие это, обычно используют стирание типов. Компилятор не будет пытаться создать экземпляр следующего рекурсивного вызова, потому что ему уже известна структура типа.

Julia выполняет мономорфизацию кода, но при этом поддерживает полиморфную рекурсию. Я предполагаю, что он делает это, откладывая создание экземпляра универсального типа или функции до тех пор, пока он не будет фактически вызван. Однако я думаю, что это может привести к использованию большого количества памяти, особенно когда рекурсия очень глубокая. Итак, мой вопрос: будет ли Джулия по-прежнему выполнять мономорфизацию кода для полиморфного рекурсивного типа или она вернется к стиранию типа или какому-то другому методу?

Answer 1

Этот вопрос очень похож на сокращение времени JIT с помощью рекурсивных вызовов в 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))

Здесь у нас есть абстрактный тип и два подтипа, один составной для внутренних узлов дерева и один для листьев. У нас также есть рекурсивная операция в две строки, чтобы определить, как сворачивать или уменьшать значения в дереве, и хороший краткий инфиксный конструктор для деревьев.

Если мы определим, а затем свернем его с добавлением, мы получим это:

      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

Обратите внимание, что тип полностью раскрывает, что это внутренний узел с какими-то дочерними элементами, но мы не можем увидеть, насколько он глубок. У нас нет таких типов, как 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})

Интересно здесь то, что количество методов растет, но не взрывается.