Does julia perform code monomorphization for recursively polymorphic types?

Question

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

Answer 1

This question appears very similar to Reducing JIT time with recursive calls in Julia

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

First some definitions:

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.

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

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

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

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.