(defn fac-cps [n k]
(letfn [(cont [v] (k (* v n)))] ;; #1_fac-cps: Next continuation
(if (zero? n) ;; #2_fac-cps: Accept continuation
(k 1) ;; #3_fac-cps: Return continuation
(recur (dec n) cont))))
Btw., for the meaning of "Continuation Passing Style", see the book, or Wikipedia. This post is only about understanding how this code sample works, without worrying too much about the theoretical background ;)
My first thought was: how can this even work? When we call cont for the last time, then n is zero, and thus the whole product will be zero. (Why did I think this? Because, we check if n is zero, and if so, we call cont with 1. So n=0 and v=1. At least that's what I thought at the beginning.)
However, trying out the function demonstrates the opposite:
(fac-cps 5 identity)will return 120.
So let's add some debug code, to understand what is going on:
(defn fac-cps [n k]
(letfn [(cont [v]
(do
(println (str "v=" v "n=" n))
(k (* v n)))
)
]
(if (zero? n)
(k 1)
(recur (dec n) cont))))
Invoking again the function in the same way as above, yields the following result:
v=1n=1 v=1n=2 v=2n=3 v=6n=4 v=24n=5
So we can see, that in the last step, n is 1. But how is that possible? We just said that it was zero.
Well, the reason is, that when (k 1) is called, then k is the cont instance from the previous call of fac-pos (where n=1). I.e., in the closure of that instance of cont, n=1. And v=1 parameter is the one we just passed to it. And at this point, k is the cont instance from n=2. Thus we go back through the whole chain, and get the desired result at the end.
No comments:
Post a Comment