Каковы преимущества letrec?
При чтении "Закаленного Интригана" я начал узнавать о 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 версия, как называется - , пусть один (который на самом деле одинаково) должен быть быстрее, так как есть меньшие аргументы в петля. Однако на практике компиляторы могут делать все виды оптимизаций за вашей спиной, например, понять, что петля в простой версии проходит первые два аргумента без изменений, и превратим его в петлю с одним аргументом с первым. Вместо того, чтобы показывать вам числа в конкретной системе, вот модуль PLT, который вы можете пройти от времени четырех разных версий, и вы можете легко добавить больше, чтобы попробовать другие вариации. Краткое резюме заключается в том, что на моей машине названа - пусть , версию , немного быстрее, и делает его рекурсивным хвостом, имеет большую общую выгоду.
#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))
Для одной вещи reletrec версия позволяет использовать функцию, даже если его глобальное имя сбрасывается на что-то еще, например, e.g.
(define substitute
; stuff involving letrec
)
(define sub substitute)
(set! substitute #f)
Тогда Sub все еще будет работать, тогда как он не будет с нерешительными версией LETREC .
Что касается производительности и читаемости, последнее, вероятно, является вопросом вкуса, в то время как первое не должно наблюдаться (хотя я не очень квалифицирован, чтобы настаивать на этом существе, а также в целом зависимостью).
Кроме того, я фактически использовал название , пусть лично:
(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.
На ваш конкретный пример: Лично я считаю, что версия letrec проще для чтения: вы определяете рекурсивную вспомогательную функцию и вызываете ее в теле функции верхнего уровня. Основное различие между этими двумя формами заключается в том, что в форме letrec вам не нужно снова и снова указывать статические аргументы в рекурсивных вызовах, которые я нахожу более чистыми.
Если код скомпилирован, избежание передачи статических аргументов при каждом рекурсивном вызове функции, вероятно, также даст небольшое преимущество в производительности в данном случае, так как вызывающий абонент избегает необходимости копировать аргументы в новый кадр стека. Если бы рекурсивный вызов функции находился в положении хвоста, компилятор мог бы быть достаточно умен, чтобы избежать копирования аргументов в стек снова и снова.
Аналогично, если код интерпретируется, наличие меньшего количества аргументов при рекурсивном вызове будет быстрее.
В более общем плане, одним из основных преимуществ letrec, о котором, как мне кажется, вы не упоминали выше, является то, что он допускает определение рекурсивных функций. Я достаточно мало знаком со схемой, но насколько я понимаю, это одно из главных достоинств формы letrec по сравнению, например, с define.