комбинаторы с фиксированной запятой в clojure - PullRequest
Новая
       62

комбинаторы с фиксированной запятой в clojure

2 голосов
/ 16 января 2020

Один из моих любимых способов проверить силу языка, который я изучаю, - это попытаться реализовать различные комбинаторы с фиксированной запятой. Так как я изучаю Clojure (хотя я не новичок в lisps), я сделал то же самое для него.

Сначала немного "тестируемого" кода, факториал: 

(def !'
  "un-fixed factorial function"
  (fn [f]
    (fn [n]
      (if (zero? n)
        1
        (* n (f (dec n)))))))

(defn !
  "factorial"
  [n]
  (if (zero? n)
    1
    (apply * (map inc (range n)))))

Для любого комбинатора c, который я реализую, я хочу убедиться, что ((c !') n) равен (! n).

Мы начнем с традиционного Y: 

(defn Y
  "pure lazy Y combinator => stack overflow"
  [f]
  (let [A (fn [x] (f (x x)))]
   (A A)))

Но, конечно, Clojure не настолько ленив, как этот, поэтому мы поворачиваемся к Z: 

(defn Z
  "strict fixed-point combinator"
  [f]
  (let [A (fn [x] (f (fn [v] ((x x) v))))]
   (A A)))

И действительно, он утверждает, что (= ((Z !') n) (! n)).

Теперь приходит моя проблема: я не могу получить ни одного из U или комбинатор Тьюринга (тэта-v) для правильной работы. Я подозреваю, что с U это ограничение по языку, в то время как с theta-v я более склонен полагать, что это неверное прочтение нотации Википедии : 

(defn U
  "the U combinator => broken???"
  [f]
  (f f))

(defn theta-v
  "Turing fixed-point combinator by-value"
  [f]
  (let [A (fn [x] (fn [y] (y (fn [z] ((x x) y) z))))]
    (A A)))

Пример опыта REPL: 

((U !') 5)
;=> Execution error (ClassCastException) at fix/!'$fn (fix.clj:55).
;=> fix$_BANG__SINGLEQUOTE_$fn__180 cannot be cast to java.lang.Number
((theta-v !') 5)
;=> Execution error (ClassCastException) at fix/theta-v$A$fn (fix.clj:36).
;=> java.lang.Long cannot be cast to clojure.lang.IFn

Может кто-нибудь объяснить

  1. Почему эти реализации U и theta-v не работают; и
  2. как их исправить?

1 Ответ

0 голосов
/ 16 января 2020

Ваше определение тэта-v неверно по двум причинам. Первое довольно очевидно: вы принимаете f в качестве параметра, а затем игнорируете его. Более точным переводом будет использование стиля def, как и для других ваших функций: 

(def theta-v
  "Turing fixed-point combinator by-value"
  (let [A (fn [x] (fn [y] (y (fn [z] ((x x) y) z))))]
    (A A)))

Вторая причина немного хитрее: вы перевели λz.xxyz на (fn [z] ((x x) y) z), помня, что lisps нужно больше скобок для обозначения вызовов функций, которые неявно присутствуют в лямбда-исчислении. Однако вы пропустили один набор: точно так же, как x x y z означало бы «оценить x дважды, затем y один раз, а затем, наконец, вернуть z», то, что вы написали, означает «оценить ((x x) y), а затем выбросить это». результат и возврат z ". Добавление дополнительного набора скобок дает рабочий theta-v: 

(def theta-v
  "Turing fixed-point combinator by-value"
  (let [A (fn [x] (fn [y] (y (fn [z] (((x x) y) z)))))]
    (A A)))

, и мы можем продемонстрировать, что он работает, вычисляя некоторые факториалы: 

user> (map (theta-v !') (range 10))
(1 1 2 6 24 120 720 5040 40320 362880)

Что касается U: использовать U комбинатор, объединяемые функции должны изменить способ их самостоятельного вызова, то есть вам также нужно переписать !': 

(def U [f] (f f))

(def ! (U (fn [f]
            (fn [n]
              (if (zero? n)
                1
                (* n ((f f) (dec n))))))))

Обратите внимание, что я изменил (f (dec n)) на ((f f) (dec n)).

...