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

Question

В статье Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme’s Recursive Binding Construct автор Dybvig et al. он говорит, что (курсив мой):

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

я не всматривался в отчете R5RS, но я использовал letrec и эквивалент «имя let» в программах Scheme и неблагоприятных последствиях, указанных в статье не ясен для меня, кто-то может просветить меня?

Answer 1

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

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

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

Авторы заявляют, что потребовать, чтобы все RHSes были lambda -выражения упростили бы реализацию, потому что нет никаких шансов на неправильный код, вызывающий преждевременную оценку переменных LHS внутри некоторых RHS.Но, к сожалению, это изменяет семантику letrec и, следовательно, это не вариант. Это также запрещало бы простое использование внешних переменных в RHSes, и, таким образом, это новое сокращение 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

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

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

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

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

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

На оригинальной бумаге есть надпись Fixing letrec (reloaded), в которой есть макросы, которые реализуют «исправление».