clojure 中的定点组合器

Question

我最喜欢测试我正在学习的语言的能力的方法之一是尝试实现各种定点组合器。因为我正在学习 Clojure（虽然我对 lisp 并不陌生），所以我也做了同样的事情。

首先，一点"testable"代码，阶乘：

(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 or the Turing combinator (theta-v) to work correctly. I suspect with U it's a language limit, while with theta-v I'm more inclined to believe it's a misread of Wikipedia's notation:

(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

谁能解释一下

为什么 U 和 theta-v 的这些实现不起作用；和
如何修复它们？

Answer 1

您对 theta-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)，请记住 lisp 需要更多括号来表示隐含在 lambda 演算符号中的函数调用。但是，您错过了一组：正如 x x y z 的意思是 "evaluate x twice, then y once, then finally return z"，您所写的意思是 "evaluate ((x x) y), then throw away that result and return 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))。

clojure 中的定点组合器

fix-point combinators in clojure

clojure

fixpoint-combinators