5

最初にいくつかの背景。私は現在、モナディックパーサーコンビネーターについていくつかのことを学んでいます。この論文（p。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)))
4

2 に答える 2

6

コードでは、次の関数は末尾再帰ではありません。これは、すべての反復で、次のいずれかを選択するため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

パーサーコンビネーターの実装によっては、次の書き直しが機能する可能性があります（私はここでは専門家ではありませんが、これを試す価値があるかもしれません）。

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

確認できるように、新しいバージョンはこのパターンに一致しますが、元のバージョンは一致しませんでした。

于 2010-06-29T14:44:12.207 に答える
2

一般に、「遅延」メカニズムのおかげで、複数のバインディングを使用している場合でも、末尾再帰の計算式（1および2を参照）を記述できます。let!

この場合、の最後のステートメントはchainl1、私が思うに、あなたを追い詰めるものです。

于 2010-06-29T14:41:58.413 に答える