这种延续传递方式Clojure函数发生器如何工作？

Question

这是来自Clojure的Joy,第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]被定义为(主叫ķ用的局部应用KONT与v作为第一个参数和)Ñ作为第二个参数.为什么要用partial而不是简单地写(k (cont v n))？
• 如果accept?函数通过,则完成递归,应用于k1.
• 否则,使用递减的n recur重复返回fn [nk],并使用continuation函数.
• 从始至终,kont都不会改变.

我是对的,k直到决赛才真正执行(k 1)？因此,在评估之前(fac 3)首先进行扩展(* 1 (* 2 3)).

Answer 1

我没有这本书,但我认为这是一个激励人心的例子

(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向factorial 添加一个额外的参数,这个函数执行在递归调用返回后我们将要做的事情.

(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

我们使这个更灵活一点,我们可以分解出zero?和*并使其可变参数来代替.

第一种方法是

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

但是,既然accept?并且c没有改变,我们可以提升然后重新开始内部匿名功能.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