Czy F # zrobić TCO (tail optymalizacji call) z |> Option.bind

Question

Tu jest mój funkcji:

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) 

trwa zbiór zasad i stosuje je do momentu wejścia ekspresja ulega zmniejszeniu w miarę możliwości. Mógłbym przepisać wyrażenie Option.bind na wyrażenie match i wyraźnie skorzystałoby z optymalizacji połączeń końcowych. Jednak jest to dla mnie bardziej eleganckie, więc chciałbym zachować go tak, jak jest, chyba że będzie niepotrzebnie zużywał stos. Czy F # robi TCO z tym kodem?

EDYCJA: Ten kod zawsze zwraca Brak; Naprawię to, ale myślę, że pytanie nadal ma sens.

Answer 1

Wkleiłem twój kod do pliku tco.fs. Dodałem funkcję applyRule, aby umożliwić jej kompilację.

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) 

Potem zrobiłem plik wsadowy do analizy 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 

Jako wyjście znajdziemy tco.il zawierającej IL. Odpowiednia funkcja jest tutaj.

.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 

Widzimy tutaj, że generowany jest kod końca ogona. Jest to wskazówka od kompilatora IL do kompilatora JIT (który faktycznie generuje wykonywalny kod maszynowy), że wywołanie ogona powinno być tutaj możliwe.

To, czy wywołanie ogona faktycznie jest wykonywane, należy do kompilatora JIT, jak można przeczytać here.

Answer 2

Odpowiedź brzmi "nie".

Tak jak powiedziałeś, połączenie zostanie zoptymalizowane poprzez "rozszerzenie" Option.Bind do wyrażenia match. Spowoduje to prawidłowe ustawienie wywołania rekurencyjnego na applyAll w pozycji ogonowej.

z Option.Bind w położenie tylne, stos będzie rozwijać się jak

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

i F # kompilator nie zoptymalizować.