7

定点组合器为匿名函数提供了一种引用自身或构建相互递归结构的方法。尽管在 lambda 演算中很有用，但它们在现代编程语言中基本上是多余的，因为大多数（如果不是全部）都支持递归、lambda 和闭包。

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

它是如何工作的，为什么他需要一个定点组合器？

4

2 回答 2

4

在 5.3 结束时快速浏览，Lickman 写道：“如上所定义，fixS 确保在所有连续输入上都具有足够的生产力。”

关键是要让定点运算符产生足够的输出，以便解析可以继续。fix :: (a -> a) -> a对于一般但专门a针对的Set a，或稍后Parser a提供足够的结构（即格的结构）来使用，您不能这样做。

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

于 2014-11-05T17:42:42.673 回答
3

肯定的事。这是一个简单的右递归语法，包含三个规则：

S -> b T
T -> a S
T -> a

这三个规则让我们构建了一个解析器来识别这些字符串：

type Parser = String -> (Bool, String)
s :: Parser
s "" = (False, "")
s (c : cs) = if c == 'b' then t cs else (False, cs)

t :: Parser
t "" = (False, "")
t (c : cs) 
  | c == 'a' && cs == "" = (True, "") 
  | c /= 'a' = (False, cs)
  | otherwise = s cs

如果您想进行更一般的解析，只需专门化Bool以代替具有一些数据结构，也许存储在 aMaybe中以指示失败。(False, ___)如果 S 也有一些其他规则，例如S -> T T和，则返回失败的解析会有所帮助T -> b b。然后，当我们得到一个 'b' 后跟 (False, ___) 时，我们倒回 try S -> T T。这些类型的语法可以通过一些肘部润滑和递归来完成。

上面的三个规则将成功匹配“ba”、“baba”等​​字符串。我们也可以将这些字符串左递归写成：

S -> T a
T -> S b
T -> b

如果您尝试编写与上面相同的解析器会发生什么？如果您正在查看字符串的前面，则为无限循环。问题是函数 S 会先调用函数 T，然后 T 会先调用 S，它们会相互递归直到无限。计算机不够聪明，无法知道后置条件（“后接 a”、“后接 a b”）使进一步的解决方案变得不可能；它只是下降到您的功能并相信您知道自己在做什么。

一个好的定点组合器有什么帮助？好吧，将这些规则想象成描述一棵树：然后函数评估首先遍历该树，并且这棵特定的树在该方向上是无限的。另一方面，广度优先遍历可以基于这些规则，并且可以获取使用这些函数中可能最少的结果，即基于此语法的某个函数的“最小固定点”。所以这就是为什么正确的定点组合器（基于diag论文中的或格理论组合器）可以在描述这些规则时终止，而朴素的递归则不会。

于 2014-11-05T18:01:38.553 回答