这个连续传递样式Clojure函数生成器是如何工作的?

This is from the Joy of Clojure, 2nd Edition. http://www.manning.com/fogus2/

这是出自《克洛伊尔的喜悦》第二版。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)))

Then to make a factorial:

然后进行阶乘:

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

My understanding:

我的理解:

mm-cps generates a function which takes in n, the fn [n]
mm-cps生成的函数接受n，即fn [n]
the function inside, fn [n k], is initially called with n and kend
内部的函数fn [n k]最初是用n和kend调用的
the continuation function cont [v] is defined as (calling k with the partial application of kont with v) as the first parameter and n as the second parameter. Why would this be written using partial instead of simply (k (cont v n)) ?
连续函数cont [v]定义为(调用k，用kont的部分应用，用v)为第一个参数，n为第二个参数。为什么要用部分而不是简单的(k (cont v n))来写呢?
if the accept? function passes, then finish the recursion, applying k to 1.
如果接受吗?函数传递，然后完成递归，将k应用到1。
otherwise, the recur recurs back to fn [n k] with a decremented n, and with the continuation function.
否则，recur又会以一个递减的n和延续函数返回到fn [n k]。
all throughout, kont does not change.
在整个过程中，kont是不变的。

Am I right that k isn't actually executed until the final (k 1)? So, (fac 3) is expanded first to (* 1 (* 2 3)) before being evaluated.

k直到最后(k 1)才被执行，对吧?因此，(fac 3)在被求值之前先展开为(* 1(* 2 3)。

1 个解决方案

#1

I don't have the book, but I assume the motivating example is

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

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

;=> CompilerException: Can only recur from tail position

And that last form has to be written (* n (fact-n (dec n))) instead, not tail-recursive. The problem is there is something remaining to be done after the recursion, namely multiplication by n.

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

What continuation passing style does is turn this inside out. Instead of applying what remains of the current context/continuation after the recursive call returns, pass the context/continuation into the recursive call to apply when complete. Instead of implicitly storing continuations on the stack as call frames, we explicitly accumulate them via function composition.

延续传递样式所做的就是把这个翻转过来。在递归调用返回后，不要应用当前上下文/延续剩下的内容，而是将上下文/延续传递到递归调用中，以便在完成时应用。我们没有在堆栈中以调用帧的形式隐式地存储连续，而是通过函数组合显式地积累它们。

In this case, we add an additional argument k to our factorial, a function that does what we would have done after the recursive call returns.

在本例中，我们在阶乘中添加了一个额外的参数k，这个函数在递归调用返回后执行。

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

The first k in is the last one out. Ultimately here we just want to return the value calculated, so the first k in should be the identity function.

第一个k是最后一个k。最后，我们要返回计算的值，所以第一个k应该是恒等函数。

Here's the base case:

基本情况是这样的:

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

Here's n = 3:

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

Compare to the non-tail recursive version

与非尾部递归版本相比

(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

Now to make this a bit more flexible, we could factor out the zero? and the * and make them variable arguments instead.

为了让这个更灵活一点，我们可以提出0 ?把*变成变量参数。

A first approach would be

第一种方法是

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

But since accept? and c are not changing, we could lift then out and recur to an inner anonymous function instead. Clojure has a special form for this, loop.

但由于接受吗?c没有变化，我们可以把它提出来然后再回到内部的匿名函数。Clojure有一个特殊的形式，循环。

(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))))))

And finally we might want to turn this into a function generator that pulls in 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)))))))

And that is how I would write mk-cps (note: last two arguments reversed).

这就是我写mk-cps的方式(注意:最后两个参数颠倒了)。

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

(def triangular-number (gen-cps #{1} + identity))    
(triangular-number 5)
;=> 15

#1