комбинаторы с фиксированной точкой в ​​clojure

Один из моих любимых способов проверить мощь изучаемого языка — попытаться реализовать различные комбинаторы с фиксированной точкой. Поскольку я изучаю 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. Как их исправить?

clojure fixpoint-combinators
person D. Ben Knoble    schedule 15.01.2020    source источник
comment
Включите ссылку на код, который вы пытаетесь перевести.   -  person amalloy    schedule 16.01.2020
comment
Эээ, @amalloy, я больше перевожу математику, чем код, но если это поможет, конечно   -  person D. Ben Knoble    schedule 16.01.2020
comment
FWIW много математики и кода - одно и то же. Конечно, лямбда-исчисление — это и то, и другое.   -  person amalloy    schedule 16.01.2020
comment
Небольшое замечание: поскольку (*) равно 1, вам не нужен 1 как частный случай в функции !. (defn ! [n] (apply * (map inc (range n)))) работает, как и (defn ! [n] (reduce * (range 1 (inc n)))), который я предпочитаю.   -  person Thumbnail    schedule 19.02.2020

Ответы (1)


arrow_upward
0
arrow_downward

Ваше определение тета-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), помня, что лиспы нуждаются в большем количестве круглых скобок для обозначения вызовов функций, неявных в нотации лямбда-исчисления. Однако вы пропустили один набор: точно так же, как 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)).

person amalloy    schedule 16.01.2020
comment
ак! Не могу поверить, что пропустил это... тета начинается с lambda.x, а не lambda.f. Интересно, что U требует этой дополнительной модификации своих аргументов. (PS согласился с кодом/математикой, просто хотел уточнить, что я переводил с лямбда-исчисления, а не с чьего-то кода на Python или что-то в этом роде) - person D. Ben Knoble; 16.01.2020
comment
Спасибо за статью. К сожалению, даже с этой поправкой на тета-v я получаю (map (fix/theta-v fix/fib') (range 10)) ; (0 1 1 3 5 7 9 11 13 15) (map fix/fib (range 10)) ; (0 1 1 2 3 5 8 13 21 34) (map (fix/theta-v fix/!') (range 10)) ; (1 0 2 6 12 20 30 42 56 72) (map fix/! (range 10)) ; (1 1 2 6 24 120 720 5040 40320 362880) (надеюсь, разрывы строк несколько очевидны) - person D. Ben Knoble; 16.01.2020
comment
Действительно, это, безусловно, выглядит неправильно. У меня нет хорошего ответа: похоже, что ваш !' верен, и реализация theta-v соответствует Википедии. Так как это неверно даже для такого маленького значения, как 1, вы можете попробовать вычислить его вручную и посмотреть, где оно идет не так (откуда, черт возьми, может взяться ноль?). - person amalloy; 16.01.2020
comment
согласен, сейчас нет времени. Хорошая тактика. - person D. Ben Knoble; 16.01.2020
comment
Ах я вижу. У вас недостаточно скобок в theta-v. В Haskell, или лямбда-исчислении, ((x x) y) z совпадает с x x y z, или, в сокращенном виде, (((x x) y) z). Однако в большинстве lisp первые средства оценивают ((x x) y), затем отбрасывают его и возвращают z. - person amalloy; 16.01.2020
comment
Фрик... хороший улов. Думаю, это произошло из-за ошибочного рефакторинга. - person D. Ben Knoble; 16.01.2020