Пример, в котором letrec / letrec * лучше, чем let с внутренними определениями или именованными let?

Question

Вот два примера, которые Кент Дибвиг приводит на языке программирования схем для letrec и letrec *:

(letrec ([sum (lambda (x)
             (if (zero? x)
                 0
                 (+ x (sum (- x 1)))))])
   (sum 5))

и

(letrec* ([sum (lambda (x)
            (if (zero? x)
                    0
                (+ x (sum (- x 1)))))]
         [f (lambda () (cons n n-sum))]
         [n 15]
         [n-sum (sum n)])
  (f))

Первый также может быть записан как именованный let:

(let sum ([x 5]) 
  ((lambda (x)
                 (if (zero? x)
                     0
                     (+ x (sum (- x 1))))) x))  

и второй может быть записан как let с внутренними определениями:

(let ()
  (define sum  (lambda (x)
               (if (zero? x)
               0 
                   (+ x (sum (- x 1))))))
  (define f (lambda () (cons n n-sum)))
  (define n 15)
  (define n-sum (sum n))
  (f))

Формы letrec / letrec * не кажутся более краткими или понятными, чем именованные let или let с внутренними определениями форм.

Может кто-нибудь показать мне пример, где letrec / letrec * действительно улучшает код или необходим вместо именованного let или let с внутренними определениями.

Answer 1

Да, первый пример можно переписать с использованием имени let, но учтите, что там нет необходимости в форме lambda:

(let sum ([x 5])
  (if (zero? x)
    0
    (+ x (sum (- x 1)))))

Этот вид преобразования немного вводит в заблуждение - это хорошо делать в случае, если вы определяете одну «функцию зацикливания» (в широком смысле не только хвостовой рекурсии) и сразу используете ее на известном вход. Но обычно, когда вы видите примеры, подобные тому, который вы привели, мы хотим показать определение и использование локальной функции, поэтому это преобразование возможно выполнить только потому, что это игрушечный пример для демонстрации.

Во-вторых, обратите внимание, что именованная let обычно не примитивная форма - стратегия реализации, которую используют практически все реализации Scheme, заключается в том, чтобы эта форма расширялась до letrec. Поэтому все еще хорошая идея понять letrec, если вы хотите понять именованные- let s. (И это фундаментальная особенность: возможность делать самостоятельные ссылки через рекурсивную область.)

Наконец, пример, который вы привели с внутренними определениями, похож на named- let s: это синтаксический сахар, который расширяется до letrec (который может быть либо letrec, либо letrec* с R5RS, и должен быть letrec* в R6RS). Таким образом, чтобы понять, как это работает, вам нужно понять letrec. Также обратите внимание, что некоторые реализации, использующие строгий letrec, также будут раздражать ваш второй пример, и жаловаться, что sum не определено. Именно это синтаксическое объединение стоит за основным аргументом семантики letrec*, принятой в R6RS: многим людям нравится использовать внутренние определения, но возникает проблема, заключающаяся в том, что определения верхнего уровня позволяют использовать предыдущие определения, но внутренние определения менее удобны в неожиданный путь. С letrec* внутренние определения работают как верхние. (Точнее, они работают как переопределения запрета верхнего уровня, что означает, что они на самом деле похожи на определения уровня модуля.)

(Обратите также внимание, что (a) как Racket, так и Chez расширяют внутренние тела, что позволяет смешивать определения и выражения, что означает, что расширение столь же просто.)

Answer 2

Я второй ответ Илии;именованные let и внутренние define определены в терминах letrec.

Я добавлю к этому некоторые эмпирические, числовые анекданные.Я работаю в компании, которая использует схему.У нас есть 981 кодовых файлов схемы, которые в сумме составляют 206 878 строк (с учетом комментариев, пустых строк, всего).Это было написано командой из 8-16 человек за 8 лет.

Итак, сколько вариантов использования letrec в этой кодовой базе?16. Это сравнивается с примерно 7000 использованных let и let* (по оценкам, потому что я не буду пытаться уточнить регулярное выражение, которое я использовал).Похоже, что все варианты использования letrec были написаны одним и тем же человеком.

Так что я не удивлюсь, что вы не найдете много практического использования для letrec.

Answer 3

От некоторых учеников Кента я узнал следующее: letrec реализован в терминах let с использованием макроразложения.Он расширяет letrec до let, который использует set! внутри.Итак, ваш первый пример расширится до следующего:

(let
  ([sum (void)])
  (set! sum (lambda (x) (if (zero? x) 0 (+ x (sum (- x 1))))))
  (sum 5))

Ваш второй аналогично (обратите внимание, что вложенные let s являются результатом let* - также, это может быть не совсем корректное расширение, но это мое лучшее предположение):

(let
  ([sum (void)] 
  (set! sum (lambda (x) (if (zero? x) 0 (+ x (sum (- x 1))))))
  (let
    [f (void)] 
    (set! f (lambda () (cons n n-sum)))
    (let 
      [n (void)]
      (set! n 15)
      (let
        [n-sum (void)])
        (set! n-sum (sum n))
        (f))

Я не уверен на 600%, как расширяется именованный let, но Илай предполагает, что он будет реализован в терминах самого letrec (что имеет смысли должно быть довольно очевидно).Таким образом, ваш именованный let перемещается из именованного let в letrec в неназванный let.И ваша перезапись второй части выглядит почти так же, как и ее расширение.

Если вы интерпретируете ее и ищете хорошую производительность, я бы склонился к letrec, потому что это один более короткий шаг макро-расширения,Кроме того, let превращается в лямбду, поэтому вы используете define s во втором примере вместо set! s (что может быть тяжелее).

Конечно, если вы компилируетев любом случае, все это может выпасть в компиляторе, так что просто используйте то, что, по вашему мнению, выглядит лучше (я неравнодушен к letrec, потому что циклы let напоминают мне об императивном программировании, но ymmv).Тем не менее, это должно быть на ваше усмотрение, стилистически (поскольку они более или менее эквивалентны).

Тем не менее, позвольте мне привести вам пример, который вы можете найти стоящим:

(letrec
 ([even? (lambda (n) (if (zero? n) #t (odd? (- n 1))))]
  [odd? (lambda (n) (if (zero? n) #f (even? (- n 1))))])
  (even? 88))   

Использование вашего внутреннего стиля define даст:

(let ()
  (define even? (lambda (n) (if (zero? n) #t (odd? (- n 1)))))
  (define odd? (lambda (n) (if (zero? n) #f (even? (- n 1)))))
  (even? 88))

Так что здесь код letrec на самом деле короче.И, честно говоря, если вы делаете что-то вроде последнего, почему бы не довольствоваться begin?

(begin
  (define even? (lambda (n) (if (zero? n) #t (odd? (- n 1)))))
  (define odd? (lambda (n) (if (zero? n) #f (even? (- n 1)))))
  (even? 88))

Я подозреваю, что begin является скорее встроенным и, как таковой, не получит макро-расширение (как let will).Наконец, похожая проблема была поднята при переполнении стека Lisp немного назад с более или менее одинаковой точкой.