6

我是定点组合器世界的新手，我猜它们习惯于在匿名 lambda 上递归，但我还没有真正使用它们，甚至无法完全理解它们。

我已经在 J​​avascript 中看到了Y 组合器的示例，但无法成功运行它。

这里的问题是，有人可以给出一个直观的答案：

  • 什么是定点组合器（不仅在理论上，而且在某些示例的上下文中，以揭示该上下文中的定点究竟是什么）？
  • 除了 Y 组合器之外，还有哪些其他类型的定点组合器？

加分项：如果示例不只是使用一种语言，最好也使用Clojure。

更新：

我已经能够在Clojure中找到一个简单的示例，但仍然很难理解 Y-Combinator 本身：

(defn Y [r]
  ((fn [f] (f f))
   (fn [f]
     (r (fn [x] ((f f) x))))))

虽然这个例子很简洁，但我发现很难理解函数中发生了什么。提供的任何帮助都会很有用。

4

2 回答 2

11

假设您想编写阶乘函数。通常，你会把它写成类似

function fact(n) = if n=0 then 1 else n * fact(n-1)

但这使用显式递归。如果您想改用 Y 组合器，您可以首先将事实抽象为类似

function factMaker(myFact) = lamba n. if n=0 then 1 else n * myFact(n-1)

这需要一个参数（myFact），它称之为“真实”事实本身。我把这种风格的函数称为“Y-ready”，意思是它已经准备好被输入到 Y-combinator。

Y 组合器使用 factMaker 构建与“真实”事实等效的东西。

newFact = Y(factMaker)

何苦？两个原因。第一个是理论上的：如果我们可以使用 Y 组合器“模拟”它，我们真的不需要递归。

二是更务实。有时我们想用一些额外的代码来包装每个函数调用，以进行日志记录或分析或记忆或许多其他事情。如果我们尝试对“真实”事实执行此操作，则只会为对事实的原始调用调用额外代码，而不是所有递归调用。但是如果我们想对每个调用都这样做，包括所有的递归调用，我们可以做类似的事情

loggingFact = LoggingY(factMaker)

其中 LoggingY 是引入日志记录的 Y 组合器的修改版本。请注意，我们根本不需要更改 factMaker！

所有这些都是 Y 组合器重要的动机，而不是对 Y 的特定实现如何工作的详细解释（因为有许多不同的方式来实现 Y）。

于 2013-04-09T15:44:48.367 回答
3

要回答关于 Y 以外的定点组合器的第二个问题。标准定点组合器有无数个，fix即满足等式的组合器

fix f = f (fix f)

还有很多非标准的定点组合器，它们满足等式

fix f = f (f (fix f))

等等。标准定点组合器是递归可枚举的，但非标准的不是。有关示例、参考和讨论，请参阅以下网页。 http://okmij.org/ftp/Computation/fixed-point-combinators.html#many-fixes

于 2013-08-23T23:54:03.230 回答