Can the F# compiler optimize these mutually recursive functions?

Question

I wrote the following function that checks the validity of bracketed expressions:

let matched str =
    let rec matched' stack = function
        | "" -> isEmpty stack
        | str ->
            match first str with
            | '(' | '[' | '{' as p -> matched' (push p stack) (rest str)
            | ')' -> matchClosing '(' stack str
            | ']' -> matchClosing '[' stack str
            | '}' -> matchClosing '{' stack str
            | _ -> matched' stack (rest str)

    and matchClosing expected stack s =
        match peek stack with
        | Some c when c = expected -> matched' (pop stack) (rest s)
        | _ -> false

    matched' [] str

If we substitute the implementation of matchClosing into matched', we get a tail recursive function. Can the F# compiler recognize this and optimize away the recursive calls?

Walhalla

What do you see when you look at the IL that the compiler generates? That's the only way to tell for sure (e.g. a future version of the compiler could always behave differently). – Wordy

But it doesn't really matter that much if the F# compiler detects tail recursion and compiles it in a special way, because the .NET JIT compiler performs tail call elimination anyway. – Zippel

@FyodorSoikin - semantically it doesn't matter, but from a performance perspective it can. – Wordy

Answer 1

AFAICT your example isn't complete which makes it harder to check. I complemented it somewhat and was able to compile it.

Using ILSpy one sees that the mutual recursion is still in place:

// F#: | ')' -> matchClosing '(' stack str
case ')':
    return Program.matchClosing@39('(', stack, str);

// F#: | matched' t (tail s)
return Program.matched'@28(t, s.Tail);

So while it should be technically possible to unpack two mutually tail recursive function into a loop it's not done.

When checking the IL code we see that the the calls are tagged with .tail

// F#: | matchClosing '(' stack str
IL_0083: tail.  // Here
IL_0085: call bool Program::matchClosing@39(char, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<char>, valuetype Program/SubString)

// F#: | matched' t (tail s)
IL_002a: tail.  // Here
IL_002c: call bool Program::'matched\'@28'(class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<char>, valuetype Program/SubString)

The .NET Jitter is in release mode kind enough to consider .tail flag

// As you can see when debugging the code in WinDbg
02410bdf e8fbd3176b      call    clr!JIT_TailCall (6d58dfdf)

We also see when we debug in WinDbg that the stack don't grow. Unfortunately when looking at clr!JIT_TailCall it does a fair amount of work meaning while it doesn't consume stack it consumes clock cycles instead like noted here: How to eliminate time spent in JIT_TailCall for functions that are genuinely non-recursive

However in Debug mode (and at least older versions of Mono) .tail flag is ignored

// As you can see when debugging the code in WinDbg (this is a normal call)
02f619c1 e8c2f4ffff      call    02f60e88

We also see when we debug in WinDbg that the stack grow.

So the answer to your question should be:

1. No, the F# compiler isn't able to transform the mutually tail recursive calls into a loop.
2. However, the F# compiler tags the calls with a .tail attribute
3. The Release mode JIT:er kindly considers the .tail attributes and generates tail calls that don't grow the stack (but are ineffecient)
4. In Debug mode (and possibly mono) .tail attributes are ignored and no tail calls are generated by the JIT:er and the stack will grow.

Vanatta

Thank you for the detailed answer! It's very interesting to see that this optimization is done by the JIT compiler - I would never have thought of that! – Rafaelle

Great answer. Tails call do work on Mono as well since 2.1x. – Emmons