3

我最喜欢的测试我正在学习的语言能力的方法之一是尝试并实现各种定点组合器。因为我正在学习 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或 Turing 组合器 (theta-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. 如何修复它们？
4

1 回答 1

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)，记住 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)).

于 2020-01-16T00:20:21.617 回答