Значение letrec в схеме / ракетке - PullRequest
Новая
       73

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

0 голосов
/ 31 мая 2018

Насколько я понимаю, следующее: 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*?

Ответы [ 2 ]

0 голосов
/ 02 июня 2018

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

(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 об исправлении обратно совместим, а некоторые адаптировали его.Если вы пишете совместимый код, вы не должны поддаваться искушению предполагать это.

0 голосов
/ 31 мая 2018

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

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

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

...