12

这是来自 Clojure 的喜悦，第 2 版。http://www.manning.com/fogus2/

 (defn mk-cps [accept? kend kont] 
   (fn [n] 
     ((fn [n k] 
        (let [cont (fn [v] (k ((partial kont v) n)))] 
          (if (accept? n) 
            (k 1) 
            (recur (dec n) cont)))) 
      n kend)))

然后做一个阶乘：

(def fac (mk-cps zero? identity #(* %1 %2)))

我的理解：

  • mm-cps 生成一个接收 n 的函数，即fn [n]
  • 内部的函数fn [nk]最初是用n和kend调用的
  • 延续函数cont [v]被定义为（调用k并使用kont和v的部分应用）作为第一个参数，n作为第二个参数。为什么要使用partial而不是简单地编写它(k (cont v n))？
  • 如果accept?函数通过，则结束递归，适用k于 1。
  • 否则，以递减的 n 和延续函数recur递归回fn [nk] 。
  • 自始至终，kont没有改变。

我说得对吗，k直到决赛才真正执行(k 1)？所以，在被评估之前(fac 3)首先被扩展。(* 1 (* 2 3))

4

1 回答 1

15

我没有这本书，但我认为激励的例子是

(defn fact-n [n]
  (if (zero? n)
      1
      (* n (recur (dec n)))))

;=> CompilerException: Can only recur from tail position

最后一种形式必须改为编写(* n (fact-n (dec n)))，而不是尾递归。问题是在递归之后还有一些事情要做，即乘以n。

延续传球风格所做的就是把它翻过来。在递归调用返回后，不要应用当前上下文/延续的剩余部分，而是将上下文/延续传递给递归调用以在完成时应用。我们不是在堆栈中隐式地将延续存储为调用帧，而是通过函数组合显式地累积它们。

在这种情况下，我们向阶乘添加了一个额外的参数k，该函数执行我们在递归调用返回后会执行的操作。

(defn fact-nk [n k]
  (if (zero? n)
      (k 1)
      (recur (dec n) (comp k (partial * n)))))

第一个k进是最后一个出。最终这里我们只想返回计算出来的值，所以第一个k应该是恒等函数。

这是基本情况：

(fact-nk 0 identity)
;== (identity 1)
;=> 1

这是n = 3：

(fact-nk 3 identity)
;== (fact-nk 2 (comp identity (partial * 3)))
;== (fact-nk 1 (comp identity (partial * 3) (partial * 2)))
;== (fact-nk 0 (comp identity (partial * 3) (partial * 2) (partial * 1)))
;== ((comp identity (partial * 3) (partial * 2) (partial * 1)) 1)
;== ((comp identity (partial * 3) (partial * 2)) 1)
;== ((comp identity (partial * 3)) 2)
;== ((comp identity) 6)
;== (identity 6)
;=> 6

与非尾递归版本比较

(fact-n 3)
;== (* 3 (fact-n 2))
;== (* 3 (* 2 (fact-n 1)))
;== (* 3 (* 2 (* 1 (fact-n 0))))
;== (* 3 (* 2 (* 1 1)))
;== (* 3 (* 2 1))
;== (* 3 2)
;=> 6

现在为了让它更灵活一点，我们可以分解出 thezero?和 the*并让它们变成可变参数。

第一种方法是

(defn cps-anck [accept? n c k]
  (if (accept? n)
      (k 1)
      (recur accept?, (dec n), c, (comp k (partial c n)))))

但是由于accept?andc没有改变，我们可以将 then 取出并递归到一个内部匿名函数。Clojure 对此有一个特殊的形式，loop.

(defn cps-anckl [accept? n c k]
  (loop [n n, k k]
    (if (accept? n)
        (k 1)
        (recur (dec n) (comp k (partial c n))))))

最后我们可能想把它变成一个函数生成器来拉入n.

(defn gen-cps [accept? c k]
  (fn [n]
    (loop [n n, k k]
      (if (accept? n)
          (k 1)
          (recur (dec n) (comp k (partial c n)))))))

这就是我的写作方式mk-cps（注意：最后两个论点颠倒了）。

(def factorial (gen-cps zero? * identity))
(factorial 5)
;=> 120

(def triangular-number (gen-cps #{1} + identity))    
(triangular-number 5)
;=> 15
于 2014-02-01T06:04:33.473 回答