Как реализовать "letrec" ​​без использования "set!"?

Question

Как может letrec быть реализованным без использования set!?

Мне кажется, что set! является императивной программной конструкцией, и при ее использовании теряются преимущества функционального программирования.

Answer 1

Обычно я знаю, что мы просим скопировать контент, но нет короткого ответа на ваш вопрос. http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf

Answer 2

Нет. Только потому, что функциональная функция реализована с императивным кодом за кулисами, это не делает функцию обязательной. Наши вычислительные машины являются обязательными; поэтому в какой-то момент весь функциональный код должен быть реализован путем перевода в императивный код!

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

В случае letrecздесь есть небольшая загвоздка: результат не определен, если оценка любого из связываний в letrec приводит к тому, что другой лишается защиты. Итак, результат этого кода не определен:

(letrec ((foo bar)
         (bar 7))
  (cons foo bar))

Значение foo в теле летрека не определено. Результат следующего, с другой стороны, определен:

(letrec ((foo (lambda () bar))
         (bar 7))
  (cons (foo) bar))

Это потому, что оценка lambda захватывает ссылку на bar, но фактическое значение не ищется, пока замыкание не будет выполнено в теле.