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

Во время чтения "The Seasoned Schemer" я начал узнавать о 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 помогут!

Ответ 1

Итак, у вас есть несколько ответов, которые охватывают проблему читаемости, и это должно быть хорошо. Но один вопрос, который неясен, заключается в том, есть ли какие-либо проблемы с производительностью. По неглубокому взгляду кажется, что версия letrec, такая как named-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))

Ответ 2

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

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

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

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

Ответ 3

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

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