Recursive functions in computation expressions

Question

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

score 6 · Accepted Answer · edited Jun 29 '10 at 18:29

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.

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

score 2 · Answer 2 · edited May 23 '17 at 11:53

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.

edited May 23 '17 at 11:53

Community

1
1

answered Jun 29 '10 at 14:41

Mau

14,234
2
31
52

Recursive functions in computation expressions

2 Answers2

Linked