How are (mutually) recursive methods inferred correctly?

Internals & Design
1

This is something I took for granted and never really thought of. A C example I pulled from wikipedia will help me explain:

# really inefficient check of evenness or oddness
# "is n even" -> "is n-1 odd" -> "is n-2 even", repeat to 0
is_even(n) = iszero(n) ? true : is_odd(n-1);
is_odd(n) = iszero(n) ? false : is_even(n-1);

When I usually explain Julia’s JAOT compilation, I say that when a function is called is_even(0x8), the compiler infers the call’s possible return types from the input types (UInt8,), and the result depends on inferring the return types of other function calls is_odd(0x7) along the way, one call at a time. However, I can’t explain how inference completes when is_even depends on the return type of is_odd which depends on the yet-to-be-inferred is_even. Now I think about it, I can’t explain how 1 recursive function can be inferred.

Even if I replace true with rand((true, 1)) in is_even, the code_warntype shows that both return types of is_even and is_odd are inferred as Union{Bool, Int64}.

3 Likes
2

Stumbled upon a JuliaHub blogpost Inference Convergence Algorithm in Julia link in the devdocs section How inference works that answers the question to my satisfaction, though I do not know if it is entirely up to date.

3 Likes
3

This is a question I didn’t even know I had :sweat_smile:

We don’t know what we don’t know…

Thanks for the links – very interesting!

4

Since tail recursions, mutual or not, can be trivially rewritten as loops, the type inference result from any reasonable algorithm should be the same as the type inference result for loop-based code.

2 Likes