代码之家  ›  专栏  ›  技术社区  ›  PetPaulsen

计算表达式中的递归函数

  •  5
  • PetPaulsen  · 技术社区  · 15 年前

    先了解一些背景。我目前正在学习一些关于单语法分析器组合器的知识。当我试图从 this paper (第16-17页)我想出了这个解决方案:

    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)))
    
    2 回复  |  直到 15 年前
        1
  •  6
  •   Brian    15 年前

    在您的代码中,下面的函数不是尾部递归的,因为在每次迭代中,它在 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) }
    

    正如您可以检查的那样,新版本与此模式匹配,但原始版本不匹配。

        2
  •  2
  •   Community CDub    8 年前

    一般来说,可以编写尾部递归计算表达式(请参见 1 2 ,即使有多个 let! 通过“延迟”机制进行绑定。

    在这种情况下, chainl1 我想是什么让你陷入困境。