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

Asked 18/4, 2015 at 18:2 Answered 18/4, 2015 at 22:31

Solved f#tail-recursion tail-call-optimization fixpoint-combinators f#-3.1

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.

Meisel answered 18/4, 2015 at 18:2 Comment(6)

if you look at fix you will see that the recursive call of fix is not in tail-call position (as it is followed by f) ... so no surprise here - btw: it's not the lambda that messes up the fixpointcombinator - it's the definition of fix itself – Despiteful 18/4, 2015 at 18:21

what you can do is (although the theory behind fix is nice) not to use fix but use the given optimized functions like Seq.iter or List.iter in this case (or even just use a for loop) - recursion is nice and you should understand it but after you understand it you should use common abstractions instead) – Despiteful 18/4, 2015 at 18:22

@CarstenKönig, there is no recursive call in fix, it's a partial function application passed to f. The call happens in the lambda f. You can check the IL code for fix if you don't believe me ;) I added another example that work fine with the same fix function. – Meisel 18/4, 2015 at 18:29

@CarstenKönig, I added the IL code of fix to show that this is not a recursive call, just a indirect recursive call. – Meisel 18/4, 2015 at 18:38

@CarstenKönig, sorry, but you are mixing things up. The tail in fix is preceding the call to f. The recursive call to fix (and I apologise, of course it's a recursive call) is stored away inside a closure (the argument body of the lambda) and called inside the lambda. And this is not a tailcall in the first case, but it is a tailcall in the second case. – Meisel 18/4, 2015 at 18:51

Let us continue this discussion in chat. – Meisel 18/4, 2015 at 19:7

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.

Natal answered 18/4, 2015 at 22:31 Comment(1)

Thank you for the linkt to the blog post! – Meisel 19/4, 2015 at 12:13

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.

Please:

Recommended topics

Hot tags