Почему не letrec как починить?

Question

В статье Fixing Letrec: точная, но эффективная реализация рекурсивной связывающей конструкции схемы Dybvig et al. сказано что (выделено мое):

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

Я не исследовал отчет R5RS, но я использовал letrec и эквивалент "по имени let"В программах Схемы и упомянутых в статье печальных последствиях мне непонятно, может кто-то меня просветить?

Answer 1

С эквациональным синтаксисом,

letrec x = init-x
       y = init-y
  body....

ограничение в том, что нет RHS init... Выражение может вызвать оценку (или присваивание) любой из переменных LHS, потому что все init...s оцениваются, пока все переменные еще не назначены. IOW нет init... следует ссылаться на любую из переменных напрямую и немедленно. Это нормально, конечно, для любого из init...s, чтобы содержать лямбда-выражения, которые действительно могут ссылаться на любую из переменных (это цель letrec в конце концов). Когда эти лямбда-выражения будут оценены, переменным уже будут присвоены значения вычисляемых init... выражения.

Авторы говорят, что требовать, чтобы все RHS были lambda-выражения упростили бы реализацию, потому что нет шансов неправильного поведения кода, вызывающего преждевременную оценку переменных LHS внутри некоторой RHS. Но, к сожалению, это меняется letrecСемантика и, следовательно, не вариант. Это также запретило бы простое использование внешних переменных в RHS и, таким образом, это новое сокращение letrec также будет менее общим и менее удобным.

---

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

(let ((x 1)(y 2))
  (let g ((x x) (y x))
    (if (> x 0) (g (- x y) y) (display x)))
  (display x))
01
;Unspecified return value

(let ((x 1)(y 2))
  (letrec ((g (lambda (x y) 
                (if (> x 0) (g (- x y) y) (display x)))))
     (g x x))  ; no 'x' in letrec's frame, so refer to outer frame
  (display x))
01
;Unspecified return value

Answer 2

Ограничение letrec R5RS говорит, что что-то вроде этого нарушает:

(let ((x 10))
  (letrec ((x x))
    x))

(letrec ((y (+ x 5)) 
         (x 5)) 
  (list x y))

Таким образом, не определено, что произойдет, и это определенно не будет переносимой схемой. Это может оценить 10 а также (5 10)реализация может сигнализировать об ошибке, или вы получите неопределенное значение, которое может привести к получению сообщения об ошибке. Я проверил Racket, Gambit, Chicken и Ikarus, и ни один из них ничего не сигнализировал в первом случае, и все они оценивают неопределенное значение. Икарус единственный, кто вернулся (5 10) в последнем, в то время как другие все получили ошибки контракта, так как неопределенное значение в качестве аргумента нарушает контракт +. (Икарус всегда оценивает операнды справа налево)

R[567]RS сообщает всем, что если все выражения являются лямбда-выражениями, вам не о чем беспокоиться, и я думаю, что это ключ. Другая причина заключается в том, что вы не должны пытаться создавать тени, как если бы вы использовали (по имени) let.

Существует оригинальная статья под названием " Исправление letrec (перезагружено)", в которой есть макросы, реализующие "исправление".