letrec有什么好处？

在阅读“The Seasoned Schemer”时，我开始了解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。通过这种方式在静态变量上重复出现时是否有速度增强，因为你没有继续传递它？对于具有参数的函数，这种标准实践是保持静态还是减少了一个参数（例如重复列表的元素）？来自更有经验的Schemers / LISPers的一些意见会有所帮助！

已邀请:

3 个回复

晤默报

所以你有几个答案涵盖了可读性问题，这应该没问题。但一个尚不清楚的问题是，是否存在任何性能问题。从浅层看，似乎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))

辰炔诚薯

关于你的具体例子：我个人觉得letrec版本更容易阅读：你定义了一个递归的辅助函数，你在顶级函数体中调用它。两种形式之间的主要区别在于，在letrec形式中，您不必在递归调用中反复指定静态参数，我发现它更清晰。如果编译代码，在这种情况下避免在每个递归函数调用上传递静态参数可能也会提供一个小的性能优势，因为调用者避免必须将参数复制到新的堆栈帧中。如果递归函数调用处于尾部位置，则编译器可能足够聪明以避免一遍又一遍地复制堆栈上的参数。类似地，如果解释代码，递归调用中具有较少的参数将更快。更一般地说，do0ѭ的一个主要好处，我认为你上面没有提到过，它是允许相互递归的函数定义的事实。我对计划缺乏经验，但就我所知，这是letrec形式的一个主要特征，与例如define。

锹缄

首先，letrec版本允许您使用该功能，即使其全局名称被重置为其他名称，例如

(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
    ))

我发现这种方式更具可读性。因人而异。

要回复问题请先登录或注册

letrec有什么好处？

3 个回复

发起人

letrec

问题状态

letrec有什么好处？

与内容相关的链接

3 个回复

发起人

letrec

问题状态