Why does the F# compiler not create a tail call for this function?
In fact, you have already answered your own question. Quoting the comment from the source code,
// Throw away the unit result
is the pending operation after the call, preventing the compiler from using a tail call here.
There's a great blog post by Keith Battocchi, "Tail calls in F#" (scroll to section "Limitations / Calling function values returning unit") which discovers a lot of details.
In two words:
Normally, F# functions … -> unit
are compiled to .NET methods returning void
.
However, functions treated as values (e.g., those passed as arguments to higher-order functions) are stored in objects of type ('a->'b)
so they actually return Microsoft.FSharp.Core.Unit
, not void
.
The compiler needs to pop the dummy unit
value off of the stack before returning.
Therefore, there is a pending operation after the recursive call, and therefore the compiler can't optimize it to a tail call.
Good news:
Note that this issue only arises when using first-class functions as values. Calling normal .NET methods which return void doesn’t present this problem, because there is no return value to pop off of the stack.
To tail call optimize your code, the compiler must tail call optimize fix
. With higher-order function in fix, the compiler is confused.
If you want a tail-recursive fix
, try to define it differently:
let rec iter p f x =
if p x then x
else iter p f (f x)
iter ((=) 100000000) ((+) 1) 0
Interesting fact: Your fix
would not stack overflow in Haskell because of how Haskell evaluates expressions: Haskell uses graph reduction, which is different from using call stacks.
let fix f = f (fix f)
fix (\f x -> if x == 100000000 then -1 else f (x + 1)) 0
Speaking of your second example, the .NET just-in-time might be able to optimize tail calls at runtime. Since it's a optimization, it depends on how smart the runtime is: Having return value or not might stump the JIT optimizer. For example, Mono on my machine didn't optimize your second example.
See also: Generate tail call opcode