Как работает этот генератор функции Clojure для продолжения прохождения?

Question

Это из Радости Clojure, 2nd Edition. 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))) 

Мое понимание:

• мм сП генерирует функцию, которая принимает в п, п [п]
• функция внутри, fn [nk], изначально ca заполненный с п и Kend
• функции продолжения прода [v] определяются как (вызов K с частичным применением Конт с об) в качестве первого параметра и п как второй параметр. Почему это должно быть написано с использованием partial вместо простого (k (cont v n))?
• если функция accept? проходит, а затем закончить рекурсию, применяя k к 1.
• В противном случае, recur рецидивирует обратно к Fn [N K] с декрементируется п, и с функцией продолжения.
• все время, 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 к нашей факториалу, которая выполняет то, что мы сделали бы после возврата рекурсивного вызова.

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

Первый k в последний один из. В конечном итоге здесь мы просто хотим вернуть рассчитанное значение, поэтому первая k in должна быть функцией идентификации.

Вот базовый случай:

(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