Can the F # compiler optimize these mutually recursive functions?

Question

I wrote the following function that validates parenthesized 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 replace the matchClosing implementation with matched' , we get a tail recursive function. Can the F # compiler recognize this and optimize recursive calls?

Answer 1

AFAICT your example is incomplete, which makes verification difficult. I supplemented it somewhat and was able to compile it.

Using ILSpy , we see that 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, although it is technically possible to unpack two mutually tail recursive functions into a loop, this is not done.

When checking the IL code, we see that calls are marked .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) 

.NET jitter is in release mode to view .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 is not growing. Unfortunately, when looking at clr!JIT_TailCall it does a lot of work, while it does not consume the stack, it consumes clock cycles rather than as indicated here: How to eliminate the time spent on JIT_TailCall for functions that are genuinely non-recursive

However, in debug mode (and at least older versions of Mono), the .tail flag .tail 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 is growing.

So, the answer to your question should be:

• No, the F # compiler cannot convert mutually tail recursive calls into a loop.
• However, the F # compiler tags calls with the .tail attribute
• JIT: er release mode kindly considers .tail attributes and generates tail calls that do not grow on the stack (but are inefficient)
• In debug mode (and possibly mono) .tail attributes are ignored and no tail calls are generated by JIT: er, and the stack will grow.