Why doesn't the F # compiler create a tail call for this function?

Question

I am having problems with a fixed point combinator in F #:

let rec fix fa = 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 to make the generated IL code easy to read.)

This code — if compiled with optimizations and tailcalls enabled — raises a StackOverflowException . I looked at the IL code and was able to trace the lambda problem inside the fix call:

 .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 changed the code a bit to make it easier to read.)

The reason for the StackOverflowException is that the body call is not a tail call (the callvirt statement below). And the reason is that the compiler created a lambda call that actually returns Unit !

So, in C # terms: Func<Int32,Unit> body, when it really should be Action<Int32> . Since the call returns something that needs to be dropped, it cannot be tail. Also note that the f@1 method is compiled as void , not Unit , which is the reason why the result of calling the argument should be discarded.

Is it really intended or can I do something? The way the compiler views this lambda makes the fixed-point collector useless for all the purposes I intended to use.

---

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

It works:

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

And now this is the code generated for 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 shank. And everything is working fine.

---

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

 .method public static !!b fix<a, b> (class FSharpFunc`2<class FSharpFunc`2<!!a, !!b>, class FSharpFunc`2<!!a, !!b>> f, !!aa) { 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 seems to me that (fix f) inside the definition of fix is ​​not a recursive call that occurs at this time, but simply a reference to fix itself, which, together with the argument f - gets stored in closure with the name Program/fix@11 and passed lambda as an argument that actually calls fix through this closure.

Otherwise, it will be infinite recursion from the very beginning, and fix will be useless.

I am using F # version 3.1.2, F # Interactive version 12.0.30815.0

---

You are welcome:

I'm not interested in alternative solutions. I just want to know why the compiler returns a Unit that needs to be thrown when the lambda fails.

Answer 1

In fact, you have already answered your question. Quoting a comment from source,

 // Throw away the unit result 

is a pending operation after a call, not allowing the compiler to use the tail call here.

There's an excellent Keith Battocchi blog entry, “Tail calls in F #” (go to the section “Call Function Limitations / Values ​​Returning Unit”)) that reveals a lot of details.

In a nutshell:
Typically, the F # … -> unit functions are compiled for .NET methods that return void .
However, functions considered as values ​​(for example, passed as arguments to functions of a higher order) are stored in objects of type ('a->'b) , so they actually return Microsoft.FSharp.Core.Unit , not void .
Before returning, the compiler must pop the dummy unit value from the stack.
Therefore, after a recursive call, there is a pending operation, and therefore the compiler cannot optimize it for the tail call.

Good news:

Please note that this problem only occurs when using first-class functions as values. Calling ordinary .NET methods that return void does not present this problem because there is no return value to pop out of the stack.

Answer 2

To intercept the call, optimize your code, the compiler must perform the fix call optimization. With a higher order function in fix, the compiler is confused.

If you want a tail-recursive fix , try defining it differently:

 let rec iter pfx = if px then x else iter pf (fx) iter ((=) 100000000) ((+) 1) 0 

Interesting fact: your fix will not overflow in Haskell due to the way Haskell evaluates expressions: Haskell uses a graph reduction that is different from using call stacks.

 let fix f = f (fix f) fix (\fx -> if x == 100000000 then -1 else f (x + 1)) 0 

Speaking of your second example, a tail call at run time can be optimized on time. Since this is an optimization, it depends on how smart the runtime is: the JIT optimizer can kick the return value or not. For example, Mono on my machine did not optimize your second example.

See also: Create a tail call code