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

Question

Читая «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 поможет!

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

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