Значение letrec в схеме / ракетке

Question

Насколько я понимаю, следующее: let, let*, letrec и letrec* - синтетические сахара, используемые в схеме / ракетке.

Теперь, если у меня есть простая программа:

(let ((x 1)
      (y 2))
     (+ x y))

Она переводится в:

((lambda (x y) (+ x y)) 1 2)

Если у меня есть:

(let* ((x 1)
      (y 2))
     (+ x y))

Это переведено на:

((lambda (x) ((lambda (y) (+ x y))) 2) 1)

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

Например, на что

(letrec ((x 1)
      (y 2))
     (+ x y)) 

будет переведено?

Второй вопрос похож на letrec* - Но для letrec* Я не понимаю, какчем именно он отличается от letrec?А также, во что будет переведено выражение letrec*?

Answer 1

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

(let ((x 1) (y 2))
  (+ x y)) 

Но для поддержки намерения формы базовая реализация может сделать что-то вроде этого:

(let ((x 'undefined) (y 'undefined))
  (let ((tmpx 1) (tmpy 2))
    (set! x tmpx)
    (set! y tmpy))
  (+ x y))

Сейчас.letrec для того, чтобы лямбды могли называть себя по имени.Итак, представьте себе:

(let ((fib (lambda (n) 
             (if (< n 2) n 
                 (+ (fib (- n 1)) (fib (- n 2)))))))
      (fib 10))

Важно понимать, что это не работает и почему.Преобразование его в вызов lambda упрощает просмотр:

((lambda (fib)
   (fib 10))
 (lambda (n) 
   (if (< n 2) n 
       (+ (fib (- n 1)) (fib (- n 2))))))

Каким-то образом вам нужно оценить лямбду после создания fib.Давайте представим, что мы делаем это:

(let ((fib 'undefined))
  (set! fib (lambda (n) 
              (if (< n 2) n 
                  (+ (fib (- n 1)) (fib (- n 2))))))
  (fib 10))

В качестве альтернативы вы можете сделать это с помощью Z комбинатора , чтобы сделать его чистым:

(let ((fib (Z (lambda (fib)
                (lambda (n) 
                  (if (< n 2) n 
                      (+ (fib (- n 1)) (fib (- n 2)))))))))  
  (fib 10))

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

Это единственный способ сделать это правильно.Я знаю, что clojure имеет recur, который имитирует рекурсию, но на самом деле это goto.

Для переменных, которые не делают замыкания из привязок letrec, они работают как let и более поздние, например let*, поскольку ответ Soegaards об исправлении обратно совместим, а некоторые адаптировали его.Если вы пишете совместимый код, вы не должны поддаваться искушению предполагать это.

Answer 2

См. Статью «Исправление Летрека: верное, но эффективное внедрение рекурсивной связывающей конструкции схемы» Оскара Уодделла, Дипанвиты Саркара и Р. Кента Дибвиг.

Статья начинается с простой версии и объясняет более сложное расширение:

https://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf