如何在不使用"set!"的情况下实现"letrec"?

Question

如何在不使用set!的情况下实现letrec?

看起来，set!是一种命令式编程构造，在使用它时，会失去函数式编程的好处。

- user1059449

Answer 1

我知道通常我们要求内容被复制，但是对于你的问题并没有简短的答案。 http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf

（说明：本段内容无需翻译，已经是中文）

- chx

---

Dybvig等人的论文很好。几年前Lambda the Ultimate上有一篇不错的讨论，关于如何用lambda实现letrec。尽管如此，我同意sacundim的评论：“仅仅因为一个函数特性在幕后使用了命令式代码并不意味着该特性是命令式的”。 - Lindsey Kuper

Answer 2

不是的。即使一个函数式特性在幕后是由命令式代码实现的，这也不意味着该特性是命令式的。我们的计算机都是命令式的，因此所有函数式代码在某个时刻都必须通过将其转换为命令式代码来实现！

关键要理解的是：函数式编程与 实现 无关，而与 接口 有关。如果一段代码本身无法 观察到 任何副作用，那么它就是函数式的——即使在幕后存在副作用。例如，如果多次检查同一变量的同一绑定的值，则会获得相同的值，即使该值在幕后是通过使用set！设置的。

在 letrec 的情况下，这里有一个小陷阱：如果 letrec 中的任何一个绑定的求值导致另一个绑定被取消引用，结果是未定义的。因此，此代码的结果是未定义的：

(letrec ((foo bar)
         (bar 7))
  (cons foo bar))

在letrec的主体中，foo的值是未定义的。 另一方面，以下结果是已定义的：

(letrec ((foo (lambda () bar))
         (bar 7))
  (cons (foo) bar))

这是因为评估 lambda 捕获了对 bar 的引用，但实际值直到在主体中执行闭包时才被查找。

- Luis Casillas