将Lua单子模仿中的递归消除

2015-8-13 19:31:13
收藏：0
阅读：58
评论：1

我试图用 Lua 粗略地复制 Parsec，但在绑定函数时遇到了些问题，这会生成递归的 runParser。

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

我使用了一种自定义的 ADT 系统，因此返回值上有 cons() 和 get() 函数。Haskell 的等效代码可能是这样的。

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

Parser 构造函数（Lua 中的 new 函数）的参数是 runParser 函数。因此，在 runParser 中调用另一个 runParser 会非尾递归地生成非常深的调用栈，导致堆栈溢出。有没有关于如何消除递归或将其转换为尾递归的提示？

点赞
用户904219
用户904219

使用 Continuation passing 方法使解决这个问题变得非常容易。

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

这样，它可以一路实现尾调用！不可否认，f 可能会因为自身而溢出，但这将是用户编程糟糕的情况，因为 f 不应该很深。

2015-08-15 21:32:42

作者:

用户904219

用户904219
推荐文章