clojure中的定点组合子

Question

我最喜欢的测试语言能力的方法之一是尝试并实现各种固定点组合器。因为我正在学习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))。

现在我的问题来了:我无法让使用或图灵组合器(theta-v)正确工作。我怀疑U是语言限制，而对于to 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和of v的实现不起作用；
2. 如何修复它们？

Answer 1

你对θ-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需要更多的括号来表示在lambda演算符号中隐含的函数调用。但是，您错过了一组:正如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)).