Как эта функция Clojure расширяется?

Question

От Радости Clojure:

(defn fac-cps [n k]
  (letfn [(cont [v] (k (* v n)))]
   (if (zero? n)
    (k 1)
   (recur (dec n) cont))))

(defn fac [n]
  (fac-cps n identity))

(fac 10)
3628800

Мне интересно узнать, как расширяется вышеуказанная функция.

fac-cps вызывается с 10 и identity ...

но в letfn cont[v] определяется как (k (* v n))

, что соответствует k = identity, n = 10

Ноя не понимаю, к чему равняется v и на что распространяется recur.

Answer 1

Все строки одинаковы.Я только что использовал правила замены:

(fac-cps 10 identity)
(recur 9 (fn [v] (identity (* v 10))))
(recur 8 (fn [v] ((fn [v] (identity (* v 10))) (* v 9))))
(recur 7 (fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8)))) 
(recur 6 (fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))))  
(recur 5 (fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))))  
(recur 4 (fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))) (* v 5))))  
(recur 3 (fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))) (* v 5))) (* v 4))))
(recur 2 (fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))) (* v 5))) (* v 4))) (* v 3))))
(recur 1 (fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))) (* v 5))) (* v 4))) (* v 3))) (* v 2))))
(recur 0 (fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))) (* v 5))) (* v 4))) (* v 3))) (* v 2))) (* v 1))))
((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))) (* v 5))) (* v 4))) (* v 3))) (* v 2))) (* v 1))) 1)
((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))) (* v 5))) (* v 4))) (* v 3))) (* v 2))) (* 1 1))
((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))) (* v 5))) (* v 4))) (* v 3))) (* (* 1 1) 2))
((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))) (* v 5))) (* v 4))) (* (* (* 1 1) 2) 3))
((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))) (* v 5))) (*  (* (* (* 1 1) 2) 3) 4))
((fn [v] ((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* v 6))) (* (* (* (* (* 1 1) 2) 3) 4) 5))
((fn [v] ((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* v 7))) (* (* (* (* (* (* 1 1) 2) 3) 4) 5) 6))
((fn [v] ((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* v 8))) (* (* (* (* (* (* (* 1 1) 2) 3) 4) 5) 6) 7))
((fn [v] ((fn [v] (identity (* v 10))) (* v 9))) (* (* (* (* (* (* (* (* 1 1) 2) 3) 4) 5) 6) 7) 8))
((fn [v] (identity (* v 10))) (* (* (* (* (* (* (* (* (* 1 1) 2) 3) 4) 5) 6) 7) 8) 9))
(identity (* (* (* (* (* (* (* (* (* (* 1 1) 2) 3) 4) 5) 6) 7) 8) 9) 10))
(identity 3628800)
; ==> 3628800

Answer 2

Эта функция оценивает факториал, создавая продолжение (в основном, функцию, которая будет выполнять работу в будущем), а затем оценивая его на (fac-cps 0).

Например, на (fac-cps 3), продолжение - «взять»число, умножьте его на 3, затем передайте его предыдущему продолжению, которое оставит его в покое (identity) ".

В (fac-cps 2), продолжение -" возьмите число, умножьте его на 2, затем передайте его предыдущему продолжению, которое умножит его на 2, и передайте предыдущему продолжению, которое оставит его в покое ".

При (fac-cps 1) продолжение означает" взять число, умножить егос 1, затем передайте его предыдущему продолжению, которое умножит его на 2 и передаст предыдущему продолжению, которое умножит его на 3 и передаст предыдущему продолжению, которое оставит его в покое. "

Затем, наконец, на (fac-cps 0) дается число: 1 * 3 * 2 * 1 - это результат.

Answer 3

При первом вызове fac-cps, k - это функция identity.Форма letfn немедленно создает новую функцию, которая принимает аргумент v и захватывает k (identity) в замыкании.

Затем проверяется, равен ли n ноль, чтобазовый / терминальный регистр для этой рекурсии.

В противном случае, есть еще много работы, которая повторяется при уменьшении n, но теперь передается новая функция cont, которая закрылась над k.Это будет происходить снова и снова, пока n не достигнет нуля, создавая цветущий лук из вложенных замыканий.Это называется стиль передачи продолжения , и это то, что означает cps в fac-cps.Сравните это с чисто рекурсивным подходом, в котором эти значения, которые были захвачены в замыканиях, вместо этого были бы в стеке вызовов.

Обратите внимание, что работает в cont (во всех вложенныхдруг в друга) не делается до самого конца, когда n достигает нуля.Когда k вызывается в случае терминала, это функция, которая может оборачивать многие другие функции.Другими словами, это создание thunk для оценки в конце.Например, (fac-cps 3) в конечном итоге оценит эту функцию:

(fn [v] ((fn [v] ((fn [v] (identity (* v 3))) (* v 2))) (* v 1)))

, но я не понимаю, что v равно

v - аргументдо cont, поэтому она не будет известна, пока не будет вызван cont.

то, что recur расширяется до

recur - это специальная форма, которая-входит в функцию "рекурсивно", но без использования стека.Вы можете заменить recur на fac-cps, но вы получите переполнение стека, если n достаточно большой.