fa F # fanno TCO (ottimizzazione chiamata coda) con |> Option.bind

Question

Qui è la mia funzione:

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) 

ci vuole un insieme di regole e le applica fino a quando l'espressione di ingresso si riduce, per quanto possibile. Potrei riscrivere l'espressione Option.bind come un'espressione match e trarrebbe evidentemente vantaggio dall'ottimizzazione delle chiamate tail. Tuttavia, questo è più elegante per me, quindi mi piacerebbe mantenerlo così com'è, a meno che non stia consumando lo stack inutilmente. F # fa TCO con questo codice?

MODIFICA: questo codice restituisce sempre Nessuno; Lo sistemerò, ma penso che la domanda abbia ancora senso.

Answer 1

Ho incollato il codice in un file tco.fs. Ho aggiunto una funzione applyRule per renderla compilabile.

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) 

poi ho fatto un file batch per analizzare l'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 

Come uscita troviamo la tco.il contenente l'IL. La funzione rilevante è qui.

.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 

Vediamo qui che viene generato l'opcode di coda. Questo è un suggerimento dal compilatore IL al compilatore JIT (che in realtà genera il codice della macchina eseguibile), che una chiamata coda dovrebbe essere possibile qui.

Se la coda è effettivamente eseguita come tale è fino al compilatore JIT, come può essere letto here.

Answer 2

La risposta è "no".

Come hai detto, la chiamata verrà ottimizzata "espandendo" Option.Bind in un'espressione match. In questo modo, la chiamata ricorsiva si posizionerà correttamente su applyAll nella posizione di coda.

Con Option.Bind nella posizione di coda, lo stack crescerà come

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

e la F # compilatore non ottimizzare questo.