Eliminating recursion in this Lua monad mimicry

Question

I'm trying to crudely replicate Parsec in Lua, and I'm having a bit of trouble with the bind function being recursive generating recursive runParsers.

function Parser:bind(f)
    return new(function(s)
        local result = self.runParser(s)
        if result.cons() == Result.Success then
            return f(result.get()).runParser(result.get(2))
        else
            return result
        end
    end)
end

I'm using a custom system of making ADTs, hence the cons() and get() functions on the return value. The equivalent Haskell code would be something like this.

m >>= f = Parser $ \s -> case result of
                            Success a cs -> runParser (f a) cs
                            _ -> result
                        where
                            result = runParser m s

The argument to the Parser constructor (the new function in Lua) is the runParser function. So calling a different runParser from within runParser non-tail-recursively generates very deep call stacks, which causes a stack overflow. Any tips on removing the recursion or translating it to tail-recursion?

Answer 1

Continuation passing made this very easy to solve.

function Parser:bind(f)
    return new(function(s, cont)
        return self.runParser(s, function(result)
            if result.cons() == Result.Success then
                return f(result.get()).runParser(result.get(2), cont)
            else
                return cont(result)
            end
        end)
    end)
end

This way, it's tail calls all the way down! Admittedly, there's potential for f to overflow all on its own, but that would be a case of bad programming on the user's side, as f shouldn't go very deep at all.