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

Question

不使用set!如何实现letrec

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

Answer 1

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

Answer 2

不是的。仅仅因为一个功能特性是在幕后使用命令式代码实现的，这并不意味着该特性就是命令性的。我们的计算机器都是命令式的；所以在某些时候，所有的功能代码都必须通过翻译成命令式代码来实现！

这里要理解的关键是:函数式编程适用于接口，而不适用于implementation.如果一段代码本身不能观察到任何副作用，那么这段代码就是功能性的--即使副作用实际上是在幕后发生的。也就是说，如果您多次检查同一变量的同一绑定的值，您将得到相同的值-即使该值在幕后是通过使用set!放在那里的。

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

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

letrec正文中的foo值未定义。另一方面，定义以下结果：

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

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