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

Question

Читая «Бывалого интригана», я начал узнавать о letrec.Я понимаю, что он делает (можно продублировать с помощью Y-комбинатора), но в книге он используется вместо повторения уже 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.Есть ли повышение скорости при повторении статической переменной таким образом, потому что вы не продолжаете ее передавать??

Является ли это стандартной практикой для функций с аргументами, которые остаются статическими, но с одним аргументом, который сокращается (например, повторение элементов списка)?

Информация от более опытных комбинаторов/LISPеров могла бы помочь!

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

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

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

В целом, одно из основных преимуществ 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
    ))

Я считаю, что так более читабельно.ЮММВ.