गणना अभिव्यक्तियों में रिकर्सिव फ़ंक्शन

Question

कुछ पृष्ठभूमि पहले। मैं वर्तमान में मोनैडिक पार्सर संयोजकों के बारे में कुछ सामान सीख रहा हूं। मैं से this paper (पी। 16-17) 'chainl1' समारोह हस्तांतरण करने के लिए कोशिश की, मैं इस समाधान के साथ आया था:

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 
} 

मैं कुछ बड़े निवेश के साथ समारोह का परीक्षण किया और एक StackOverflowException मिला है। अब मैं सोच रहा हूं, क्या यह एक रिकर्सिव फ़ंक्शन को फिर से लिखना उचित है, जो कुछ गणना अभिव्यक्ति का उपयोग करता है, इस तरह से यह पूंछ रिकर्सन का उपयोग कर रहा है?

जब मैं गणना अभिव्यक्ति का विस्तार करता हूं, तो मैं नहीं देख सकता कि यह आम तौर पर कैसे संभव होगा।

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

अपने कोड में, निम्न समारोह, पूंछ पुनरावर्ती नहीं है क्योंकि - हर चरण में है - यह एक विकल्प या तो p' या 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 

पार्सर combinators के अपने कार्यान्वयन के आधार पर पूंछ पुनरावर्ती कार्यों लेखन अंदर गणना भाव से काम करता है के लिए

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) } 

सामान्य में, पैटर्न: निम्नलिखित पुनर्लेखन काम कर सकता था (मैं यहाँ एक विशेषज्ञ नहीं हूँ, लेकिन यह इस कोशिश कर रहा लायक हो सकता है)। कुछ इस तरह (संगणना भाव है कि एक तरीका है कि पूंछ-प्रत्यावर्तन की अनुमति देता है में लागू किया जाता है के लिए) काम करेगा:

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

आप जाँच कर सकते हैं के रूप में, नए संस्करण के इस पैटर्न से मेल खाता है, लेकिन मूल एक ऐसा नहीं किया।

Answer 2

सामान्य तौर पर यह देरी 'तंत्र को let! बाइंडिंग धन्यवाद यहां तक ​​कि कई के साथ पूंछ पुनरावर्ती गणना भाव लिखने के लिए (1 और 2 देखें), संभव है।

इस मामले में chainl1 का अंतिम विवरण आपको लगता है कि एक कोने में आपको क्या मिलता है।