Каковы преимущества letrec?

Question

Читая «Закаленный интриган», я начал изучать letrec. Я понимаю, что он делает (может быть продублирован с помощью Y-Combinator), но книга использует его вместо повторения функции уже define d, работающей с аргументами, которые остаются статическими.

Пример старой функции, использующей функцию define d, повторяющуюся сама по себе (ничего особенного):

(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 поможет!

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 позволяет использовать функцию, даже если ее глобальное имя сброшено на что-то другое, например,

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

Answer 3

Относительно вашего конкретного примера: лично я считаю, что версию letrec легче читать: вы определяете рекурсивную вспомогательную функцию и вызываете ее в теле функции верхнего уровня. Основное различие между этими двумя формами заключается в том, что в форме letrec вам не нужно указывать статические аргументы снова и снова в рекурсивных вызовах, которые я считаю более чистыми.

Если код скомпилирован, исключение передачи статических аргументов при каждом вызове рекурсивной функции, вероятно, также обеспечит небольшое повышение производительности в этом случае, поскольку вызывающая сторона избегает необходимости копировать аргументы в новый кадр стека. Если бы рекурсивный вызов функции был в хвостовой позиции, компилятор мог бы быть достаточно умным, чтобы избежать многократного копирования аргументов в стеке.

Точно так же, если код интерпретируется, меньшее количество аргументов в рекурсивных вызовах будет быстрее.

В целом, одним из основных преимуществ letrec, о котором я не упомянул выше, является то, что он допускает взаимно рекурсивные определения функций. Я не очень разбираюсь в схеме, но, насколько я понимаю, это одна из основных особенностей формы letrec по сравнению, например, с. define.