Does F# do TCO (tail call optimization) with |> Option.bind

Question

Here is my function:

let rec applyAll rules expr =
  rules
  |> List.fold (fun state rule ->
    match state with
    | Some e ->
      match applyRule rule e with
      | Some newE -> Some newE
      | None -> Some e
    | None -> applyRule rule expr) None
  |> Option.bind (applyAll rules)

It takes a set of rules and applies them until the input expression is reduced as far as possible. I could rewrite the Option.bind to be a match expression and it would clearly take advantage of tail call optimization. However, this is more elegant to me, so I would like to keep it as is unless it will be consuming stack unnecessarily. Does F# do TCO with this code?

EDIT: This code always returns None; I'll be fixing that, but I think the question still makes sense.

You could look in the IL and see what is generated? I see a `tail.` :). — DaveShaw, Jan 26 '16 at 21:35
I took the liberty to slightly reformat your code. Putting the `|>` operator anywhere else than directly before the function you are "piping into" is a surefire way to throw off 99.5% of F# programmers. ;-) — TeaDrivenDev, Jan 27 '16 at 00:08
See http://stackoverflow.com/a/40165030/82959 for some more info on tail calls with `(|>)` - your results may vary between debug and release mode. — kvb, Nov 22 '16 at 15:14

score 1 · Answer 1 · answered Apr 29 '16 at 20:53

The answer is "no."

As you said, the call will be optimized by "expanding" Option.Bind into a match expression. Doing so would put the recursive call to applyAll properly in the tail position.

With Option.Bind in the tail position, the stack will grow like

+ …
+ applyAll
+ Option.Bind
+ applyAll
+ Option.Bind
_ applyAll

and the F# compiler will not optimize this.

score 1 · Accepted Answer · edited May 23 '17 at 11:53

I pasted your code into a file tco.fs. I added an applyRule function to make it compilable.

tco.fs

let applyRule rule exp =
    Some ""

let rec applyAll rules expr =
  rules
  |> List.fold (fun state rule ->
    match state with
    | Some e ->
      match applyRule rule e with
      | Some newE -> Some newE
      | None -> Some e
    | None -> applyRule rule expr) None
  |> Option.bind (applyAll rules)

Then I made a batch file to analyze the IL.

compile_and_dasm.bat

SET ILDASM="C:\Program Files (x86)\Microsoft SDKs\Windows\v10.0A\bin\NETFX 4.6 Tools\ildasm.exe"

Fsc tco.fs

%ILDASM% /out=tco.il /NOBAR /tok tco.exe

As an output we find the tco.il containing the IL. The relevant function is here.

.method /*06000002*/ public static class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpOption`1/*01000003*/<!!b> 
      applyAll<a,b>(class [FSharp.Core/*23000002*/]Microsoft.FSharp.Collections.FSharpList`1/*01000008*/<!!a> rules,
                    string expr) cil managed
{
    .custom /*0C000003:0A000003*/ instance void [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute/*01000007*/::.ctor(int32[]) /* 0A000003 */ = ( 01 00 02 00 00 00 01 00 00 00 01 00 00 00 00 00 ) 
    // Code size       26 (0x1a)
    .maxstack  8
    IL_0000:  ldarg.0
    IL_0001:  newobj     instance void class Tco/*02000002*//applyAll@13/*02000003*/<!!b,!!a>/*1B000004*/::.ctor(class [FSharp.Core/*23000002*/]Microsoft.FSharp.Collections.FSharpList`1/*01000008*/<!1>) /* 0A000004 */
    IL_0006:  newobj     instance void class Tco/*02000002*//'applyAll@6-1'/*02000004*/<!!a>/*1B000005*/::.ctor() /* 0A000005 */
    IL_000b:  ldnull
    IL_000c:  ldarg.0
    IL_000d:  call       !!1 [FSharp.Core/*23000002*/]Microsoft.FSharp.Collections.ListModule/*01000009*/::Fold<!!0,class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpOption`1/*01000003*/<string>>(class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpFunc`2/*01000002*/<!!1,class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpFunc`2/*01000002*/<!!0,!!1>>,
                                                                                                                                                                                                             !!1,
                                                                                                                                                                                                             class [FSharp.Core/*23000002*/]Microsoft.FSharp.Collections.FSharpList`1/*01000008*/<!!0>) /* 2B000001 */
    IL_0012:  tail.
    IL_0014:  call       class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpOption`1/*01000003*/<!!1> [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.OptionModule/*0100000A*/::Bind<string,!!1>(class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpFunc`2/*01000002*/<!!0,class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpOption`1/*01000003*/<!!1>>,
                                                                                                                                                                                                        class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpOption`1/*01000003*/<!!0>) /* 2B000002 */
    IL_0019:  ret
} // end of method Tco::applyAll

We see here that the tail opcode is generated. This is a hint from the IL compiler to the JIT compiler (which actually generates the executable machine code), that a tail call should be possible here.

Whether the tail call is actually executed as such is up to the JIT compiler, as can be read here.

Does F# do TCO (tail call optimization) with |> Option.bind

2 Answers2