什么是letrec的好处是什么？

Question

在阅读“经验丰富的策士”我开始了解letrec。我明白它（可以用的Y Combinator的复制），但是这本书代替重复上已经defined功能上保持静态的参数进行操作使用。

使用defined功能重复在自身上的旧的函数的一个例子（没有什么特别）：

(define (substitute new old l)
  (cond
    ((null? l) '())
    ((eq? (car l) old)
      (cons new (substitute new old (cdr l))))
    (else
      (cons (car l) (substitute new old (cdr l))))))

现在该相同功能的一个例子，但使用letrec：

(define (substitute new old l)
  (letrec
    ((replace
      (lambda (l)
        (cond
          ((null? l) '())
          ((eq? (car l) old)
           (cons new (replace (cdr l))))
          (else
           (cons (car l) (replace (cdr l))))))))
(replace lat)))

除了稍微更长，更难以阅读，我不知道他们为什么要重写功能在书中使用letrec。是否有过一个静态变量重复这样的时候，因为你不保持它传递??速度提升

这是标准的做法对于功能与保持静态被还原的参数，但一个参数（如重复向下列表的元素）？

从有经验的有计划的一些输入/ LISPers将帮助！

Answer 1

所以，你必须覆盖可读性问题的几个答案，这应该罚款。但是有一个问题就是不清楚是是否有任何性能问题。在一个浅浅的样子，似乎letrec版本，如命名let一个（这是真的一样）应该是因为有较少的参数在循环以绕过更快。然而，在实际的编译器可以做各种优化你的背后，像搞清楚的是，在普通版的循环经过前两个参数不变，并把它与第一个单参数循环。而不是显示你特定系统上的数字，这里是你可以运行四个不同版本PLT模块，您可以轻松地添加更多尝试其他变化。的简短摘要是我的机器上，则命名let版本是稍快，并使其尾递归具有更大的总体益处。

#lang scheme

;; original version
(define (substitute1 new old l)
  (cond [(null? l) '()]
        [(eq? (car l) old) (cons new (substitute1 new old (cdr l)))]
        [else (cons (car l) (substitute1 new old (cdr l)))]))

;; letrec version (implicitly through a named-let)
(define (substitute2 new old l)
  (let loop ([l l])
    (cond [(null? l) '()]
          [(eq? (car l) old) (cons new (loop (cdr l)))]
          [else (cons (car l) (loop (cdr l)))])))

;; making the code a little more compact
(define (substitute3 new old l)
  (let loop ([l l])
    (if (null? l)
      '()
      (cons (let ([fst (car l)]) (if (eq? fst old) new fst))
            (loop (cdr l))))))

;; a tail recursive version
(define (substitute4 new old l)
  (let loop ([l l] [r '()])
    (if (null? l)
      (reverse r)
      (loop (cdr l)
            (cons (let ([fst (car l)]) (if (eq? fst old) new fst)) r)))))

;; tests and timings

(define (rand-list n)
  (if (zero? n) '() (cons (random 10) (rand-list (sub1 n)))))

(for ([i (in-range 5)])
  (define l   (rand-list 10000000))
  (define new (random 10))
  (define old (random 10))
  (define-syntax-rule (run fun)
    (begin (printf "~a: " 'fun)
           (collect-garbage)
           (time (fun new old l))))
  ;; don't time the first one, since it allocates a new list to use later
  (define new-list (substitute1 new old l))
  (unless (and (equal? (run substitute1) new-list)
               (equal? (run substitute2) new-list)
               (equal? (run substitute3) new-list)
               (equal? (run substitute4) new-list))
    (error "poof"))
  (newline))

Answer 2

对于你具体的例子：我个人认为letrec版本更易于阅读：您定义的递归辅助函数，并调用它的顶层函数的主体。这两种形式之间的主要区别是，在letrec形式不必一遍又一遍在递归调用，我觉得这是更清洁再次指定静态的参数。

如果在编译代码，从而避免在每个递归函数调用的静态参数的通过将可能也提供在此情况下，由于呼叫者避免了必须的参数复制到新的堆栈帧小的性能益处。如果递归函数调用在尾部位置，编译器可能是足够聪明来避免一遍一遍堆栈上复制参数。

类似地，如果代码解释，其在递归调用更少参数会更快。

更一般的letrec的主要好处，我不认为你上面提到的一个，是一个事实，即它允许相互递归函数的定义。我与方案很缺乏经验，但据我了解，这是比较的letrec形式的主要特点之一例如define。

Answer 3

有关一方面，letrec版本允许你使用该功能，即使它的全局名称被重置到别的东西，e.g。

(define substitute
  ; stuff involving letrec
  )

(define sub substitute)
(set! substitute #f)

然后sub仍然可以工作，而它不会与非letrec版本。

至于性能和可读性，后者可能是一个品味的问题，而前者不应该观察地不同（虽然我不是很胜任坚持既然如此，还它的实现依赖反正）。

另外，其实我使用一个名为let个人：

(define (substitute new old lat) ; edit: fixed this line
  (let loop (
             ; whatever iteration variables are needed + initial values
            )
    ; whatever it is that substitute should do at each iteration
    ))

我觉得这种方式更具有可读性。 YMMV。