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

Это из Радости 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)))

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

  • mm-cps генерирует функцию, которая принимает n, fn [n]
  • функция внутри, fn [n k], изначально вызывается с n и kend
  • функция продолжения cont [v] определяется как (вызов k с частичным применением kont с v) в качестве первого параметра и n в качестве второго параметра. Почему это будет написано с помощью partial вместо простого (k (cont v n))?
  • если функция accept? проходит, затем завершите рекурсию, применяя k к 1.
  • в противном случае recur возвращается к fn [n k] с уменьшенным n и с функцией продолжения.
  • kont не изменяется.

Правильно ли, что k фактически не выполняется до окончательного (k 1)? Таким образом, (fac 3) сначала раскрывается до (* 1 (* 2 3)).

Ответы

Ответ 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 in является последним. В конечном итоге здесь мы просто хотим вернуть вычисленное значение, поэтому первая 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