2

我已经查看了我能找到的关于 letrec 的所有内容，但我仍然不明白它给语言带来了什么特性。似乎所有可以用 letrec 表达的东西都可以很容易地写成递归函数。但是，如果语言已经支持递归函数，是否有任何理由将letrec 公开为编程语言的一个特性？为什么几种语言都暴露了两者？

我知道 letrec 可能用于实现其他功能，包括递归函数，但这与为什么它本身应该是一个功能无关。我还读到有些人发现它比某些 lisps 中的递归函数更具可读性，但这又无关紧要，因为语言的设计者可以努力使递归函数具有足够的可读性，不需要其他功能。最后，有人告诉我 letrec 可以更简洁地表达某些递归值，但我还没有找到一个激励的例子。

4

2 回答 2

1

TL；DR：define 是 letrec。这就是使我们能够首先编写递归定义的原因。

考虑

let fact = fun (n => (n==0 -> 1 ; n * fact (n-1)))

这个定义主体内的名称指的是什么实体fact？With let foo = val,val是根据已知实体定义的，因此它不能引用foo尚未定义的实体。就范围而言，可以说（并且通常是）let等式的 RHS 是在外部范围内定义的。

fact内部实际指向正在定义的实体的唯一方法是使用letrec，其中允许定义的实体引用定义它的范围。因此，虽然在定义正在进行时对实体进行评估是一个错误，但存储对其（未来，在这个时间点）值的引用letrec是可以的——在使用它的情况下。

你提到的define，只是letrec另一个名字。在计划中也是如此。

如果没有定义实体引用自身的能力，即在具有非递归的语言中let，则必须使用诸如之类的神秘设备。这很麻烦而且通常效率低下。另一种方式是定义如

let fact = (fun (f => f f)) (fun (r => n => (n==0 -> 1 ; n * r r (n-1))))

因此letrec，为程序员带来了实现的效率和便利。

那么问题就变成了，为什么要公开非递归let？Haskell 确实没有。Scheme 同时具有letrec和let。一个原因可能是为了完整性。另一个可能是一个更简单的实现let，内存中的自引用运行时结构较少，这使得垃圾收集器更容易。

你要一个励志的例子。考虑将斐波那契数定义为自引用惰性列表：

letrec fibs = {0} + {1} + add fibs (tail fibs)

对于非递归，将定义let列表的另一个副本，fibs用作逐元素加法函数的输入add。这将导致在其术语中定义另一个副本的定义。等等; 访问第n个斐波那契数将导致在运行时创建和维护n-1 个列表链！不是一张漂亮的照片。fibs

这是假设fibs也使用了相同的方法tail fibs。如果没有，所有赌注都取消。

需要的是fibs使用它自己，引用它自己，所以只维护一个列表的副本。

于 2017-12-10T16:36:04.487 回答
0

注意：虽然这不是特定于方案的问题，但我使用方案来演示差异。希望你能读懂一点 lisp 代码

Aletrec只是一种特殊let情况，其中绑定本身是在评估表示其值的表达式之前定义的。想象一下：

(define (fib n)
  (let ((fib (lambda (n a b) 
               (if (zero? n) 
                   a 
                   (fib (- n 1) b (+ a b))))))
    (fib n))

此代码失败，因为 whilefib确实存在于它的主体中，let它确实存在于它定义的闭包中，因为在评估 lambda 时绑定不存在。要解决此问题letrec，可以进行救援：

(define (fib n)
  (letrec ((fib (lambda (n a b) 
                  (if (zero? n) 
                      a 
                      (fib (- n 1) b (+ a b))))))
    (fib n))

这letrec只是执行以下操作的语法：

(define (fib n)
  (let ((fib 'undefined))
    (let ((tmp (lambda (n a b) 
                 (if (zero? n) 
                     a 
                     (fib (- n 1) b (+ a b))))))
      (set! fib tmp))
    (fib n)))

所以在这里你清楚地看到fib当 lambda 被评估并且绑定稍后设置为闭包本身时存在。绑定是一样的，只是它的指针发生了变化。这是循环引用 101..

那么当你创建一个全局函数时会发生什么？显然，如果要递归，它需要在评估 lambda 之前存在，或者必须改变环境。它也需要在这里解决同样的问题。

在不能进行变异的函数式语言实现中，您可以使用 Y（或 Z）组合器来解决此问题。

如果您对语言的实现方式感兴趣，我建议您从Matt Mights 文章开始。

于 2017-12-10T17:40:47.587 回答