避免 Clojure 中的递归导致堆栈溢出

Question

我是 Clojure 的新手，无法弄清楚如何在某些情况下避免堆栈溢出。在尝试使用我发现的名为kern 的解析器组合器库将解析项目移植到 Clojure 时，出现了一种这样的情况。

Kern 定义了“many-till”解析器的递归实现：source

这对于小输入来说效果很好：

(def input-text "The blue {cat} and the red {dog} became best friends with the white {wolf} END {not included}")

(def  between-brackets "parser that grabs all text between brackets"
  (between (sym* \{) (sym* \}) (<+> (many (none-of* "}")))))

(def parse-enclosed-words "parser that attempts to grab text between brackets, 
skips a character when it can't, and halts when it hits the string END"
  (many-till (<|> between-brackets (skip any-char)) (token* "END")))

(filter #(some? %) (value parse-enclosed-words input-text)) ;; => ("cat" "dog" "wolf")

不幸的是，随着输入字符串的增长，解析器会遇到堆栈溢出：

(def file-input-text (slurp (io/resource "[input-text-20x-repeated.txt][2]") ))
(filter #(some? %) (value parse-enclosed-words file-input-text)) ;; => Unhandled java.lang.StackOverflowError

据我通过在线阅读得知，这可能是由于该函数使用了堆栈消耗递归。我尝试使用“recur”关键字重写函数，但由于递归调用不在尾部位置，这似乎不起作用。

如何修改 Many-Till 以避免堆栈溢出？

Answer 1

我认为你不能用图书馆提供的抽象来做到这一点。这是 的一个非常自然的定义many-till，并且在 Parsec 中可以很好地工作，Kern 显然受到了这个库的启发。但 Clojure 没有 Haskell 的惰性求值和自动蹦床，因此many-till构建的嵌套 lambda 不可避免地会消耗无界堆栈。您需要一个更像其实现的实现many，它从函数中手动构建解析器。我将在下面包含其来源，但我不拥有它，因此我认为我无权向 Stack Overflow 授予它的 CC BY-SA 4.0 许可证，就像发布它一样。相反，这里是其来源的链接。