2

在论文Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme's Recursive Binding Construct by Dybvig 等人。据说（强调我的）：

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

我没有仔细检查 R5RS 报告，但是我在 Scheme 程序中使用letrec了等效的“命名let”，并且我不清楚论文中提到的不幸后果，有人可以启发我吗？

4

2 回答 2

3

R5RS letrec 限制说这样的事情是违反的：

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

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

因此，它没有具体说明会发生什么，它肯定不会是可移植的 Scheme。它可能评估为10and (5 10)，实现可能会发出错误信号，或者您会得到一个未定义的值，这可能会导致发出错误信号。我已经测试过 Racket、Gambit、Chicken 和 Ikarus，但在第一种情况下，它们都没有发出任何信号，它们都评估为未指定的值。Ikarus 是唯一(5 10)在后者中返回的人，而其他人都得到了合同错误，因为作为参数的未指定值违反了 + 的合同。（Ikarus 总是从右到左计算操作数）

R[567]RS 报告所有状态，如果所有表达式都是 lambda 表达式，您无需担心，我认为这就是线索。另一个是你不应该尝试像使用 (named) let 那样进行遮蔽。

原始论文有一篇后续文章，标题为Fixing letrec (reloaded)，其中包含实现“修复”的宏。

于 2013-07-13T20:24:24.283 回答
1

使用等式语法，

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

限制是没有 RHSinit...表达式可以导致评估（或分配给）任何 LHS 变量，因为所有init...s 都被评估，而所有变量仍未分配。IOW noinit...应该直接和立即引用任何变量。当然，任何init...s 都可以包含确实可以引用任何变量的 lambda 表达式（letrec毕竟这是目的）。当这些 lambda 表达式将被评估时，变量将已经被分配了评估init...表达式的值。

作者说，要求所有 RHS 都是 - 表达式lambda将简化实现，因为行为不端的代码不可能导致对某些 RHS 中的 LHS 变量进行过早评估。但不幸的是，这改变letrec了 的语义，因此不是一个选择。它还将禁止在 RHS 中简单地使用外部变量，因此这种新的缩减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
于 2013-07-14T22:23:30.193 回答