5

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)))
PetPaulsen
  • 3,442
  • 2
  • 22
  • 33

2 Answers2

6

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.

Brian
  • 117,631
  • 17
  • 236
  • 300
Tomas Petricek
  • 240,744
  • 19
  • 378
  • 553
  • 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 Jun 29 '10 at 18:31
  • 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 Jun 29 '10 at 18:50
  • 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 Jun 29 '10 at 18:54
  • Would be great, if you get managed to do so. I'm looking forward it and keep an eye on your blog. – PetPaulsen Jun 29 '10 at 19:11
2

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.

Community
  • 1
  • 1
Mau
  • 14,234
  • 2
  • 31
  • 52