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?

Treenware

I think monomorphization is equivalent to method specialization for concrete types and static dispatch, but I'm lost on what polymorphic recursive types are because I can't really read the Haskell examples I found. What does a method with a polymorphic recursive type look like in Julia? Is this recent post an example? #70409482 – Hayden

Would a binary tree where each node is from a type that can either be a leaf or a pair of trees (which can be leaves or pairs of trees (which can be ...)) be a recursively polymorphic type? If so, Julia just generates code for the types it has seen. If you have a tree walker, Julia would generate the pair case first. It would use that code to descend into the tree until a leaf is encountered and would generate code for the leaf case at that point. Remember also that polymorphism isn't quite what it seems in Julia. It is just a constraint on the types that helps with function dispatch. – Bookrest

Does the answer with Branch{T} in #70409482 help you? – Bookrest

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.

Bookrest

A bit of clarification, BiTree{T} is a parametric abstract type, and the annotation left::BiTree{T} in a struct field does not work the same as it does in a method argument. Methods will by default specialize at compile-time and dispatch (monomorphize?) for each fitting concrete type. Structs however will store a reference that can represent every fitting type, and the field's concrete type would be checked at runtime to do stuff. Runtime checks sound bad, but this means the same concrete type Branch{T} can point to any subtypes of BiTree{T}. – Hayden

To expand that a bit on your (important) clarification, code is generated for specific concrete types and variables declared to hold abstract types will actually hold some concrete type (and we will know that type at runtime). The method dispatch is based on the most specific match at runtime, not what we declared in our code. This symmetry between type specific code generation and type specificity of objects at runtime is key and the benefits are large, but subtle. – Bookrest