为什么不用letrec来修复呢？

Question

在本文中，http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf由Dybvig等人提出。据说(强调我的)：

理论上解决这些问题的方法之一是限制letrec，使其左侧为未赋值，右侧为lambda表达式。我们将这种形式的letrec称为fix，因为它相当于一种广义的不动点算子。编译器可以有效地处理fix表达式，并且不会违反letrec对fix的限制。不幸的是，以这种方式限制letrec并不是实现者的一种选择，而且在任何情况下都会降低构造的通用性和便利性。

我没有仔细看过R5RS的报告，但我在计划中使用了letrec和相应的“命名let”，文件中提到的不幸后果对我来说还不清楚，有人能告诉我吗？

Answer 1

用等式语法，

letrec x = init-x
       y = init-y
  body....

限制是，没有RHS init...表达式可以导致计算(或分配给)任何LHS变量，因为所有init...s都是在所有变量仍未赋值的情况下进行计算的。IOW没有init...应该直接和立即引用任何变量。当然，任何init...都可以包含lambda表达式，这些表达式确实可以引用任何变量(毕竟，这就是letrec的目的)。当计算这些lambda-表达式时，变量将已经被分配给计算出的init...表达式的值。

作者说，要求所有的RHSes都是lambda-expressions将简化实现，因为错误的代码不可能导致在某些RHS中过早地评估LHS变量。但不幸的是，这改变了letrec的语义，因此不是一种选择，它还将禁止在RHSes中简单地使用外部变量，因此这种新的压缩letrec也就不那么一般了，也不太方便。

您还提到了名为let，但它并不等同于letrec：它的变量被绑定为-如果通过let，则只有循环函数本身通过letrec绑定。

(let ((x 1)(y 2))
  (let g ((x x) (y x))
    (if (> x 0) (g (- x y) y) (display x)))
  (display x))
01
;Unspecified return value

(let ((x 1)(y 2))
  (letrec ((g (lambda (x y) 
                (if (> x 0) (g (- x y) y) (display x)))))
     (g x x))  ; no 'x' in letrec's frame, so refer to outer frame
  (display x))
01
;Unspecified return value

Answer 2

R5RS letrec限制说像这样的东西是违反的：

(let ((x 10))
  (letrec ((x x))
    x))

(letrec ((y (+ x 5)) 
         (x 5)) 
  (list x y))

因此，它没有具体说明会发生什么，也肯定不会是可移植方案。它可以计算为10和(5 10)，实现可能会发出错误信号，或者您得到一个未定义的值，该值可能会导致发出信号的错误。我已经测试了球拍，甘比特，鸡和伊卡鲁斯，其中没有一个在第一个案例中任何信号，他们都评估到一个不详的价值。在后者中，Ikarus是唯一返回(5 10)的，而其他所有的都得到了契约错误，因为一个未指定的值作为参数违反了+的契约。(Ikarus总是从右向左计算操作数)

如果所有表达式都是lambda表达式，那么您就没有什么可担心的了，我认为这就是线索。另一个是，你不应该试图像你会做的那样(命名)让。

有一个后续的原始论文，题为固定letrec (重装)，它有实现“修复”的宏。