Why does the F# compiler not create a tail call for this function?

2018-06-28 20:52:10

I'm having trouble with the fixed point combinator in F#:

let rec fix f a = f (fix f) a

fix (fun body num -> 
    if num = 1000000 
    then System.Console.WriteLine "Done!" 
    else body (num + 1)
) 0

(This code is just to demonstrate the problem, it was written specifically so that the generated IL code is easy to read.)

This code - when compiled with optimizations and tailcalls enabled - causes a StackOverflowException . I looked at the IL code and could trace the problem to the lambda inside the call to fix :

.method assembly static void f@1 (class FSharpFunc`2<int32, class Unit> body,int32 num)
{
ldarg.1
ldc.i4 1000000
bne.un.s IL_0014

ldstr "Done!"
call void Console::WriteLine(string)
ret

IL_0014: ldarg.0 // Load the 'body' function onto the stack.
ldarg.1 // Load num onto the stack.
ldc.i4.1
add

// Invoke the 'body' function with num+1 as argument.
callvirt instance !1 class FSharpFunc`2<int32, class Unit>::Invoke(!0)
// Throw away the unit result.
pop
ret
}

(I modified the code a little so it is easier to read.)

The reason for the StackOverflowException is that the call to body is no tail call (the callvirt instruction at the bottom). And the reason for that is because the compiler created a call to the lambda that actually returns Unit !

So in C# terms: Body is Func<Int32,Unit> when it really should be Action<Int32> . Since the call returns something that has to be discarded, it cannot be a tailcall. Also note that the method f@1 is compiled as void , not Unit , that's the reason the result from the call to the argument has to be discarded.

Is this actually intended or can I do something about it? The way the compiler treats this lambda makes the fixed point combinator useless for all purposes I intended to use it.

I just want to add that as long as you return something as a result, it works fine. Only functions that return nothing do not work as expected.

This works:

let rec fix f a = f (fix f) a

fix (fun body num ->
    if num = 1000000
    then System.Console.WriteLine "Done!"; 0
    else body (num + 1)
) 0
|> ignore

And this is now the code generated for the lambda:

.method assembly static int32 f@11 (class FSharpFunc`2<int32, int32> body, int32 num)
{
ldarg.1
ldc.i4 1000000
bne.un.s IL_0015

ldstr "Done!"
call void Console::WriteLine(string)
ldc.i4.0
ret

IL_0015: ldarg.0
ldarg.1
ldc.i4.1
add
tail.
callvirt instance !1 class FSharpFunc`2<int32, int32>::Invoke(!0)
ret
}

Now there is a tailcall. And everything works fine.

The IL code for fix (for discussion in comments):

.method public static !!b fix<a, b> (class FSharpFunc`2<class FSharpFunc`2<!!a, !!b>, class FSharpFunc`2<!!a, !!b>> f, !!a a) 
{    
    ldarg.0
    ldarg.0
    newobj instance void class Program/fix@11<!!a, !!b>::.ctor(class FSharpFunc`2<class FSharpFunc`2<!0, !1>, class FSharpFunc`2<!0, !1>>)
    ldarg.1
    tail.
    call !!0 class FSharpFunc`2<class FSharpFunc`2<!!a, !!b>, !!a>::InvokeFast<!!b>(class FSharpFunc`2<!0, class FSharpFunc`2<!1, !!0>>, !0, !1)
    ret
}

So it would appear to me that the (fix f) inside the definition of fix is not a recursive call that happens at this time, but merely a reference to fix itself that - along with the argument f - gets stored away into a closure called Program/fix@11 and is passed to the lambda as an argument which then actually calls fix via this closure.

Otherwise this would be infinite recursion from the beginning and fix would be useless.

I'm using F# version 3.1.2, F# Interactive version 12.0.30815.0

Please:

I am not interested in alternate solutions. I just want to know why the compiler returns a Unit that needs to be thrown away when the lambda does not produce a result.

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 (eg, 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.