Does F # tun TCO (Endrekursion Optimierung) mit |> Option.bind

Question

Hier ist meine Funktion:

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) 

Es dauert eine Reihe von Regeln und wendet sie, bis der Eingangsausdruck so weit wie möglich reduziert wird. Ich könnte den umschreiben, um ein match Ausdruck zu sein, und es würde offenbar Vorteil der Endstückanrufoptimierung nehmen. Dies ist jedoch für mich eleganter, daher möchte ich es so behalten, wie es ist, es sei denn es wird unnötigerweise Stapel verbrauchen. Tut F # TCO mit diesem Code?

BEARBEITEN: Dieser Code gibt immer None zurück; Ich werde das beheben, aber ich denke, die Frage macht noch Sinn.

Answer 1

Ich habe Ihren Code in eine Datei eingefügt tco.fs. Ich habe eine applyRule-Funktion hinzugefügt, um es kompilierbar zu machen.

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) 

Dann machte ich eine Batch-Datei, die die IL zu analysieren.

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 

Als Ausgabe finden wir die tco.il die IL enthält. Die relevante Funktion ist hier.

.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 

Wir sehen hier, dass der Schwanz Opcode generiert wird. Dies ist ein Hinweis vom IL-Compiler auf den JIT-Compiler (der eigentlich den ausführbaren Maschinencode erzeugt), dass hier ein Tail-Call möglich sein soll.

Ob der Tail-Aufruf tatsächlich als solcher ausgeführt wird, ist Sache des JIT-Compilers, wie man lesen kann here.

Answer 2

Die Antwort ist "Nein".

Wie Sie bereits gesagt haben, wird der Anruf optimiert, indem "Option.Bind" in einen Ausdruck "match" erweitert wird. Dies würde den rekursiven Aufruf von applyAll in die Endposition bringen.

Mit Option.Bind im Heck Position, wird der Stapel wachsen wie

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

und der F # -Compiler wird dies nicht optimieren.