parsing - 定点组合器如何使递归构造终止？

Question

Fixed-point combinators为匿名函数提供一种引用自身或构建相互递归结构的方法。虽然它们在 lambda 演算中很有用，但在现代编程语言中本质上是多余的，因为大多数(如果不是全部)都支持递归、lambda 和闭包。

此外，定点组合器可以使递归结构(如左递归语法解析器)终止。考虑Lickman 1995 ，他证明了他的实现的终止，但从未真正提到它是如何工作的(这只是从格理论到 haskell 实现的逐步推导)以及他为什么需要定点组合器采用已经原生支持递归的语言。

它是如何工作的以及为什么他需要定点组合器？

Answer 1

通过快速扫描，Lickman 在 5.3 结尾写道“正如上面所定义的，fixS 确保在所有连续输入上都具有足够的生产力。”

关键是让定点运算符产生足够的输出，以便解析可以继续。您不能对一般的 fix::(a -> a) -> a 执行此操作，而是将 a 专门用于 Set a，或者后来的解析器a给出了足够的结构(即格子的结构)来使用。

同样，我只是粗略地浏览了这篇论文，但我认为“h::Parser a -> Parser a”语句的证明(在第 5.5 节)保持了生产力的属性==> fixP h 富有成效”是关键。