views:

130

answers:

2

Some background first. I am currently learning some stuff about monadic parser combinators. While I tried to transfer the 'chainl1' function from this paper (p. 16-17), I came up with this solution:

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
}

I tested the function with some large input and got a StackOverflowException. Now I am wondering, is it posible to rewrite a recursive function, that uses some computation expression, in a way so it is using tail recursion?

When I expand the computation expression, I can not see how it would be generally possible.

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  A: 

In general it is possible to write tail-recursive computation expressions (see 1 and 2), even with multiple let! bindings thanks to the 'delay' mechanism.

In this case the last statement of chainl1 is what gets you into a corner I think.

Mau
+4  A: 

In your code, the following function isn't tail-recursive, because - in every iteration - it makes a choice between either p' or 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 

Depending on your implementation of parser combinators, the following rewrite could work (I'm not an expert here, but it may be worth trying this):

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

In general, the pattern for writing tail-recursive functions inside computation expressions works. Something like this will work (for computation expressions that are implemented in a way that allows tail-recursion):

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

As you can check, the new version matches this pattern, but the original one did not.

Tomas Petricek
This gets rid of the recursion through the user code, but in my implementation here http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!1772.entry it still StackOverflows through the parser implementation itself. I'll now be motivated to investigate 'parsers with continuations'...
Brian
Does FParsec http://www.quanttec.com/fparsec/ handle this?
Brian
Brian, I also used your blog series as a learning source. It helped alot. Meanwhile I compared Mau's answer ('seq') with my parser. And I guess the Delay method in the monad is import. But I realy dont know. FParsec uses 'while' ... but I want to use a functional solution :D
PetPaulsen
Yes, my hunch is you'd need to refactor the underlying parser implementation to take a continuation parameter, and the `<|>` combinator would use continuations to make tail calls to its arguments, a bit like http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!250.entry versus http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!174.entry ... but at some point (a long time from now, with my current backlog) I hope to work through all of the details myself and blog about it :)
Brian
Would be great, if you get managed to do so. I'm looking forward it and keep an eye on your blog.
PetPaulsen