Chức năng đệ quy trong biểu thức tính toán

Question

Một số nền trước tiên. Tôi hiện đang học một số thứ về bộ phối hợp phân tích cú pháp đơn thuần. Trong khi tôi cố gắng để chuyển chức năng 'chainl1' từ this paper (. P 16-17), tôi đã đưa ra giải pháp này:

let chainl1 p op = parser { 
    let! x = p 
    let rec chainl1' (acc : 'a) : Parser<'a> = 
     let p' = parser { 
      let! f = op 
      let! y = p 
      return! chainl1' (f acc y) 
      } 
     p' <|> succeed acc 
    return! chainl1' x 
} 

Tôi đã thử nghiệm chức năng với một số đầu vào lớn và có một StackOverflowException. Bây giờ tôi tự hỏi, là nó posible để viết lại một chức năng đệ quy, mà sử dụng một số biểu thức tính toán, trong một cách để nó được sử dụng đệ quy đuôi?

Khi tôi mở rộng biểu thức tính toán, tôi không thể nhìn thấy cách nói chung có thể.

let chainl1 p op = 
    let b = parser 
    b.Bind(p, (fun x -> 
    let rec chainl1' (acc : 'a) : Parser<'a> = 
     let p' = 
      let b = parser 
      b.Bind(op, (fun f -> 
      b.Bind(p, (fun y -> 
      b.ReturnFrom(chainl1' (f acc y)))))) 
     p' <|> succeed acc 
    b.ReturnFrom(chainl1' x))) 

Answer 1

Trong code của bạn, chức năng sau đây không phải là đuôi-đệ quy, bởi vì - trong mỗi lần lặp - nó làm cho một sự lựa chọn giữa một trong hai p' hoặc succeed:

// Renamed a few symbols to avoid breaking SO code formatter 
let rec chainl1Util (acc : 'a) : Parser<'a> = 
    let pOp = parser { 
    let! f = op 
    let! y = p 
    return! chainl1Util (f acc y) } 
    // This is done 'after' the call using 'return!', which means 
    // that the 'cahinl1Util' function isn't really tail-recursive! 
    pOp <|> succeed acc 

Tùy thuộc vào thực hiện lại combinators phân tích cú pháp, các viết lại sau đây có thể làm việc (tôi không phải là một chuyên gia ở đây, nhưng nó có thể là giá trị cố gắng này):

let rec chainl1Util (acc : 'a) : Parser<'a> = 
    // Succeeds always returning the accumulated value (?) 
    let pSuc = parser { 
    let! r = succeed acc 
    return Choice1Of2(r) } 
    // Parses the next operator (if it is available) 
    let pOp = parser { 
    let! f = op 
    return Choice2Of2(f) } 

    // The main parsing code is tail-recursive now... 
    parser { 
    // We can continue using one of the previous two options 
    let! cont = pOp <|> pSuc 
    match cont with 
    // In case of 'succeed acc', we call this branch and finish... 
    | Choice1Of2(r) -> return r 
    // In case of 'op', we need to read the next sub-expression.. 
    | Choice2Of2(f) -> 
     let! y = p 
     // ..and then continue (this is tail-call now, because there are 
     // no operations left - e.g. this isn't used as a parameter to <|>) 
     return! chainl1Util (f acc y) } 

Nhìn chung, mô hình cho các văn bản chức năng đuôi-đệ quy bên trong biểu thức tính toán hoạt động. Một cái gì đó như thế này sẽ hoạt động (đối với các biểu thức tính toán được thực hiện theo cách cho phép đệ quy đuôi):

let rec foo(arg) = id { 
    // some computation here 
    return! foo(expr) } 

Như bạn có thể kiểm tra, phiên bản mới khớp với mẫu này, nhưng phiên bản gốc không khớp.

Answer 2

Nói chung người ta có thể viết các biểu thức tính toán đuôi-đệ quy (xem 1 và 2), thậm chí với nhiều let! bindings nhờ vào cơ chế 'chậm trễ'.

Trong trường hợp này, tuyên bố cuối cùng của chainl1 là điều giúp bạn vào một góc tôi nghĩ.