# Why doesn't the compiler infer the type of this function?

**URL:** <https://discourse.julialang.org/t/why-doesnt-the-compiler-infer-the-type-of-this-function/35005>\
**Category:** General Usage\
**Tags:** inference\
**Created:** [February 22, 2020, 5:26am UTC](https://discourse.julialang.org/t/why-doesnt-the-compiler-infer-the-type-of-this-function/35005 "2020-02-22T05:26:55Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![benninkrs](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/benninkrs/32/3191_2.png) [@benninkrs](https://discourse.julialang.org/u/benninkrs)\
**Post date:** [February 22, 2020, 5:26am UTC](https://discourse.julialang.org/t/why-doesnt-the-compiler-infer-the-type-of-this-function/35005/1 "2020-02-22T05:26:55Z")

</div>

On Julia v1.2.0:

```julia
fib1(n::Int64) = n<=1 ? (1,) : (n, fib1(n-1)...)
run1() = fib1(5)

fib2(::Type{Val{n}}) where {n} = n<=1 ? (1,) : (n, fib2(Val{n-1})...)
run2() = fib2(Val{5})

julia> @code_warntype run1()
Variables
  #self#::Core.Compiler.Const(run1, false)

Body::Tuple{Int64,Vararg{Int64,N} where N}
1 ─ %1 = Main.fib1(5)::Core.Compiler.PartialStruct(Tuple{Int64,Vararg{Int64,N} where N}, Any[Core.Compiler.Const(5, false), Vararg{Int64,N} where N])
└── return %1

julia> @code_warntype run2()
Variables
  #self#::Core.Compiler.Const(run2, false)

Body::NTuple{5,Int64}
1 ─ %1 = Core.apply_type(Main.Val, 5)::Core.Compiler.Const(Val{5}, false)
│ %2 = Main.fib2(%1)::Core.Compiler.Const((5, 4, 3, 2, 1), false)
└── return %2

```

I had gotten the impression that the `Val{n}` idiom is no longer necessary since the compiler can now do constant propagation. So I am surprised that the return type of `fib1(5)` is not inferred, especially since 5 is (AFAIK) well below the tuple length limit for inference.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [February 22, 2020, 10:09am UTC](https://discourse.julialang.org/t/why-doesnt-the-compiler-infer-the-type-of-this-function/35005/2 "2020-02-22T10:09:28Z")

</div>

Constant propagation doesn’t happen on recursion I think.

---

<div class="post-metadata">

**Author:** ![tim.holy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tim.holy/32/52_2.png) [@tim.holy](https://discourse.julialang.org/u/tim.holy)\
**Post date:** [February 23, 2020, 11:01am UTC](https://discourse.julialang.org/t/why-doesnt-the-compiler-infer-the-type-of-this-function/35005/3 "2020-02-23T11:01:31Z")

</div>

I think it’s more that this is a case of a growing tuple. Inference is willing to do it if you have a shrinking or constant-length tuple:

```julia
fib1a(::Tuple{Int}) = (1,)
fib1a(t::TT) where TT<:Tuple = (length(t), fib1a(Base.tail(t))...)
run1a() = fib1a(ntuple(i->1, 5))

```

This is all part of the heuristics used to avoid getting stuck in an infinite inference loop, which I think look something like this:

- if inference can prove that it will converge, then do it. (Even when it would converge, its attempt to prove so works only some of the time due to the [halting problem](https://en.wikipedia.org/wiki/Halting_problem).) The case of a shrinking tuple or one that has one operation per element is a case where it can be certain that it will converge.
- if inference can’t prove it, go a little ways down the rabbit hole (e.g., up to tuples of length 2 or so)
- bail

@benninkrs, hopefully you’re doing this only on small tuples; if not, it’s pretty murderous on the compiler and will lead to long inference times (aka, “time to first [whatever]” will be unpleasant).

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [February 23, 2020, 2:20pm UTC](https://discourse.julialang.org/t/why-doesnt-the-compiler-infer-the-type-of-this-function/35005/4 "2020-02-23T14:20:00Z")

</div>

> [@tim.holy](#):
>
> I think it’s more that this is a case of a growing tuple. Inference is willing to do it if you have a shrinking or constant-length tuple:

While true, I think what I said is still correct. You are writing

```julia
function run1a()
    tmp = ntuple(i->1, 5)
    fib1a(tmp)
end

```

and the constant propagation on the 5 does not need to recurse here. From the tuple you are then back to “type” recursion where your example does apply. Just to make a super simple example:

```julia
julia> f(n) = n == 0 ? 1 : 1 + f(n-1);

julia> g() = f(5)
g (generic function with 1 method)

```

If constant propagation would go through recursion this should give `g() = 6` (but it doesn’t). But perhaps the argument there is that going from `n` to `n-1` is not a simplification so constant propagation stops.

---

<div class="post-metadata">

**Author:** ![benninkrs](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/benninkrs/32/3191_2.png) [@benninkrs](https://discourse.julialang.org/u/benninkrs)\
**Post date:** [February 23, 2020, 9:40pm UTC](https://discourse.julialang.org/t/why-doesnt-the-compiler-infer-the-type-of-this-function/35005/5 "2020-02-23T21:40:27Z")

</div>

Thanks for the explanation. I understand that inference has its limitations, but I thought my example would be pretty easy for the compiler to infer.

This issue came up as part of a module I’m writing for high-dimensional array manipulation. The problem I ran into is that `size` and the functions I need to use from [TensorOperations](https://github.com/Jutho/TensorOperations.jl) use tuples, but to do the dimension mangling I need either (1) a mutable data structure, such as a `Vector` or `MVector`, in which case the cost of converting between tuples and vectors becomes significant; or (2) to dissect and reassemble multiple tuples, in which case the cost of constructing tuples becomes significant. This led me to explore how quickly tuples can be constructed and how much inference can help, and then to the example above.

It would be a topic for another thread (such as [this one](https://github.com/JuliaLang/julia/issues/17115)), but I find myself wishing there was such a thing as super fast mutable tuples.

---

<div class="post-metadata">

**Author:** ![tim.holy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tim.holy/32/52_2.png) [@tim.holy](https://discourse.julialang.org/u/tim.holy)\
**Post date:** [February 24, 2020, 10:00am UTC](https://discourse.julialang.org/t/why-doesnt-the-compiler-infer-the-type-of-this-function/35005/6 "2020-02-24T10:00:52Z")

</div>

```julia
julia> Base.setindex((1, 2, 6), 2, 3)
(1, 2, 2)

```

---

<div class="post-metadata">

**Author:** ![benninkrs](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/benninkrs/32/3191_2.png) [@benninkrs](https://discourse.julialang.org/u/benninkrs)\
**Post date:** [February 25, 2020, 3:23am UTC](https://discourse.julialang.org/t/why-doesnt-the-compiler-infer-the-type-of-this-function/35005/7 "2020-02-25T03:23:52Z")

</div>

Very interesting. I was not aware of `base.setindex`. It appears to be very fast for small tuples at least; I need to do a little more experimenting.

Since my previous post, I learned that for my use case it is actually quite expedient to make an `MVector` out of the tuple, do the manipulations, then convert the result back to a tuple. It turns out the extra cost I was seeing had little to do with creating tuples per se or converting to and from `MVector`, but was mainly associated with returning tuples whose length could not be inferred. I’ve found some curious behavior regarding that, but that’s probably a topic for another thread.

I thank both of you for your thoughtful replies.