Need assistance understanding continuation function

Question

This is from a teaching example to illustrate CPS and tail recursion:

fun sum [] k = k 0
  | sum (x::xs) k = sum xs (fn y=>k(x+y));

I have problems understanding how the anonymous function fn y=>k(x+y) would sum up the elements of the input list correctly.

From what I understand, that anonymous function means a new function with one argument y where the function body calls the original function k with argument y+x.

If I invoke sum [1,2,3,4,5] (fn x=>x); I get 15. If I have sum [1,2,3,4,5] (fn x=>3x); the answer is 45. The user of the sum function hence would have to first understand the exact gory details of sum as only an appropriate version of k will produce the sum of the given list. What is the real-world purpose of having a user supplied function in such a manner?

If I am the writer of the sum function, I cannot control what the user will pass in for k. In other words, how do I even specify what the function would do precisely?

Answer 1

The user of the sum function hence would have to first understand the exact gory details of sum as only an appropriate version of k will produce the sum of the given list.

No. As always, reading the docs should be enough, no need to peek at the implementation details. Your k is given the exact sum of the list - that's all what is important. You should understand k to be like an output parameter (though without mutation); it is basically a callback

If I am the writer of the sum function, I cannot control what the user will pass in for k. In other words, how do I even specify what the function would do precisely?

You don't need to care what the user passes. You just document what the function does: it calls the supplied k with the sum of the supplied xs list. The return value of that is not important.

What is the real-world purpose of having a user supplied function in such a manner?

If taken to an extreme, you don't need ever to return any value in continuation-passing style - you just pass it to the callback. This makes a call stack superfluous. From another perspective, every function does end in a tail call which can be optimized away instead of returning.

Answer 2

I have problems understanding how [...] would sum up the elements of the input list correctly.

Try and evaluate your function by hand:

sum [1,2,3] id
sum [2,3] (fn y1=>id(1+y1))
sum [3] (fn y2=>(fn y1=>id(1+y1))(2+y2))
sum [] (fn y3=>(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+y3))
(fn y3=>(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+y3)) 0
(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+0)
(fn y2=>(fn y1=>id(1+y1))(2+y2)) 3
(fn y1=>id(1+y1))(2+3)
(fn y1=>id(1+y1)) 5
id(1+5)
id(6)
6

So as you can see, this function builds up a chain of anonymous functions in heap memory that eventually call one another. A normal recursive function would instead use stack space for the equivalent.

The user of the sum function hence would have to first understand the exact gory details of sum as only an appropriate version of k will produce the sum of the given list. What is the real-world purpose of having a user supplied function in such a manner?

As Bergi writes, the user does not need to understand how the sum function works, only that it takes a continuation as argument and resolves it at its base case. As Bergi also writes, it does not have to evaluate k at its base case. An alternative to this function would be:

fun sum [] k = k
  | sum (x::xs) k = sum xs (fn y=>k(x+y));

One application here, and a justification for exporting the sum function both with a callback as argument and return value, is that you can lazily chain functions together this way. For example, with the above function you could sum a list of lists;

fun sumMany [] k = k
  | sumMany (xs::xss) k = sumMany xss (sum xs k)

And you might evaluate it like

val result = sumMany [[1,2,3],[4,5,6],[7,8,9]] (fn x=>x) 0