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

Читая "Закаленный интриган", я начал узнавать о 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 помог бы!

Источник

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

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

Источник

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

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

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

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

Источник
Другие вопросы по тегам