Liệu F # làm TCO (đuôi gọi tối ưu hóa) với |> Option.bind

Question

Đây là chức năng của tôi:

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) 

Phải mất một bộ quy tắc và áp dụng chúng cho đến khi biểu thức đầu vào giảm càng nhiều càng tốt. Tôi có thể viết lại các Option.bind là một biểu thức match và nó rõ ràng sẽ tận dụng tối ưu hóa cuộc gọi đuôi. Tuy nhiên, điều này là thanh lịch hơn với tôi, vì vậy tôi muốn giữ nó như là trừ khi nó sẽ được tiêu thụ stack không cần thiết. F # có làm TCO với mã này không?

CHỈNH SỬA: Mã này luôn trả về Không có; Tôi sẽ sửa chữa điều đó, nhưng tôi nghĩ câu hỏi vẫn có ý nghĩa.

Answer 1

Tôi đã dán mã của bạn vào một tệp tco.fs. Tôi đã thêm một hàm applyRule để làm cho nó có thể biên dịch được.

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) 

Sau đó, tôi đã thực hiện một tập tin batch để phân tích 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 

Là một đầu ra chúng tôi tìm ra tco.il chứa IL. Chức năng liên quan là ở đây.

.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 

Chúng tôi thấy ở đây rằng mã opcode đuôi được tạo. Đây là một gợi ý từ trình biên dịch IL tới trình biên dịch JIT (mà thực sự tạo ra mã máy thực thi), rằng một cuộc gọi đuôi có thể được thực hiện ở đây.

Cho dù cuộc gọi đuôi thực sự được thực hiện như vậy là tùy thuộc vào trình biên dịch JIT, có thể đọc được here.

Answer 2

Câu trả lời là "không".

Như bạn đã nói, cuộc gọi sẽ được tối ưu hóa bằng cách "mở rộng" Option.Bind thành biểu thức match. Làm như vậy sẽ đặt cuộc gọi đệ quy đến applyAll đúng cách ở vị trí đuôi.

Với Option.Bind ở vị trí đuôi, ngăn xếp sẽ tăng trưởng như

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

và F # biên dịch sẽ không tối ưu hóa này.