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

Question

如何letrec在不使用的情况下实施set!？

在我看来,这set!是一个命令式的编程结构,通过使用它,一个人失去了函数式编程的好处.

Answer 1

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

Answer 2

不.仅仅因为功能特性是在幕后使用命令式代码实现的,这并不能使该功能成为必要.我们的计算机器势在必行; 所以在某些时候所有功能代码必须通过翻译成命令式代码来实现!

这里要理解的关键是:函数式编程属于接口,而不是实现.如果代码本身无法观察到任何副作用,即使副作用实际上发生在幕后,一段代码也是有用的.也就是说,如果你多次检查同一个变量的相同绑定的值,你将获得相同的值 - 即使这个值在幕后被使用放在那里set!.

在这种情况下letrec,这里有一点点捕获:如果对任何绑定的评估letrec导致另一个绑定被解除,则结果是未定义的.所以,这段代码的结果是未定义的:

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

fooletrec体中的值是未定义的.另一方面,定义了以下结果:

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

这是因为评估lambda捕获对bar的引用,但是直到在正文中执行闭包时才查找实际值.