Kann der F # -Compiler diese gegenseitig rekursiven Funktionen optimieren?

Question

schrieb ich die folgende Funktion, die die Gültigkeit der Klammerausdrücke prüft:

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 

Wenn wir die Umsetzung von matchClosing in matched' ersetzen wir einen Schwanz rekursive Funktion erhalten. Kann der F # -Compiler dies erkennen und die rekursiven Aufrufe optimieren?

Answer 1

AFAICT Ihr Beispiel ist nicht vollständig, was es schwieriger zu überprüfen macht. Ich habe es etwas ergänzt und konnte es kompilieren.

Mit ILSpy man sieht, dass die gegenseitige Rekursion ist noch an seinem Platz:

// F#: | ')' -> matchClosing '(' stack str 
case ')': 
    return Program.matchClosing@39('(', stack, str); 

// F#: | matched' t (tail s) 
return Program.matched'@28(t, s.Tail); 

So, während es technisch möglich sein sollte, zwei sich gegenseitig Schwanz rekursive Funktion in einer Schleife entpacken Sie es nicht getan hat.

Wenn Sie den Code IL Überprüfung wir sehen, dass die die Anrufe mit .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 im Release-Modus ist so freundlich, markiert sind .tail Flagge zu betrachten

// As you can see when debugging the code in WinDbg 
02410bdf e8fbd3176b  call clr!JIT_TailCall (6d58dfdf) 

Wir auch sehen wenn wir in WinDbg debuggen, dass der Stapel nicht wächst. Leider, wenn sie bei clr!JIT_TailCall suchen Sinn macht es eine Menge Arbeit, während sie nicht verbrauchen stackt es verbraucht Taktzyklen statt wie hier angemerkt: How to eliminate time spent in JIT_TailCall for functions that are genuinely non-recursive

jedoch im Debug-Modus (und zumindest ältere Versionen von Mono) .tail Flag ignoriert

Wir sehen auch, wenn wir in WinDbg debuggen, dass der Stapel wächst.

So sollte die Antwort auf Ihre Frage:

1. Nein, die F # -Compiler nicht in der Lage ist, die für beide Seiten Schwanz rekursive Aufrufe zu einer Schleife zu verwandeln.
2. jedoch Tags der F # -Compiler die Anrufe mit einem .tail Attribute
3. Der Release-Modus JIT: er freundlich betrachtet die .tail Attribute und erzeugt Schwanz Anrufe, die den Stapel nicht wachsen (aber effizient ist)
4. In Debug Modus (und möglicherweise Mono) .tail Attribute werden ignoriert und keine Tailaufrufe werden vom JIT generiert: er und der Stack wird wachsen.