# fact CPS Trace

## Note

factCPS Trace

Hey everyone, just for your reference, here is an evaluation trace of `factCPS 3 s`, in all it’s gory detail. Please read and understand what’s happening here (it’ll be useful for your homework!).

Here’s the implementation of `factCPS`:

``````(* factCPS : int -> (int -> 'a) -> 'a
* REQUIRES: n>=0
* ENSURES: factCPS n s == s(n!)
*)
fun factCPS 0 s = s 1
| factCPS n s = factCPS (n-1) (fn res => s(n*res))
``````

and here’s a trace of it:

``````factCPS 3 s
==> factCPS 2 (fn res => s(3*res))
==> factCPS 1 (fn res' => (fn res => s(3*res)) (2 * res'))
==> factCPS 0 (fn res'' => (fn res' => (fn res => s(3*res)) (2 * res')) (1 * res''))
==> (fn res'' => (fn res' => (fn res => s(3*res)) (2 * res')) (1 * res'')) (1)
==> (fn res' => (fn res => s(3*res)) (2 * res')) (1 * 1)
==> (fn res' => (fn res => s(3*res)) (2 * res')) 1
==> (fn res => s(3*res)) (2 * 1)
==> (fn res => s(3*res)) 2
==> s(3*2)
==> s(6)
``````

Hope this helps!

## Followup

In a similar “renaming to make life easier” spirit, I usually do

``````factCPS 3 s					s0 = s
==> factCPS 2 (fn res => s0 (3*res))		s1 = (fn res => s0 (3*res))
==> factCPS 1 (fn res => s1 (2*res))		s2 = (fn res => s1 (2*res))
==> factCPS 0 (fn res => s2 (1*res))		s3 = (fn res => s2 (1*res))
==> s3 1
==  (fn res => s2 (1*res)) 1
==> s2 (1*1)
==> s2 1
==  (fn res => s1 (2*res)) 1
==> s1 (2*1)
==> s1 2
==  (fn res => s0 (3*res)) 2
==> s0 (3*2)
==> s0 6
==  s 6
``````

if I have to trace CPS code by hand. The main advantage is that you write less, your modified continuations are easy to keep track of, and you tend to have a pattern (like my s0 s1 s2 above) to guide you.

Jacob’s original trace is still the correct way of going about it, though.

19/02/27: fixed typo, thanks for bringing it up!