F# continuation-based tail recursion

Question

Can someone clarify the need for acc "" when terminating a continuation-based tail-recursive function like in the following example:

let rec repeat_cont i s acc = 
if i = 0 then acc ""
else repeat_cont (i-1) s (fun x -> acc(s + x))

repeat_cont 4 "xo" id
val it : string = "abababab"

If the result is a list, it'd be acc [], and acc 0 for integer.

Answer 1

While the other answers give a good background of writing functions in continuation-passing style, they miss one important point that in my mind also makes it easier to understand how CPS works:

You do not need to call the continuation in the base case. That is, there is no need for acc "" when terminating recursion.

I'm sure you understand the idiom of passing an accumulator through a series a recursive calls and gradually building up a data structure that way - let's say a list or a tree. CPS is no different, except the structure you build up in the accumulator is a function. And since we're in a functional language, that's as good of a value to return in the base case as any other.

Compare the following example:

let inline repeat_cont i s =
    let rec inner i s acc = 
        if i = 0 
            then acc
            else inner (i-1) s (fun x -> acc(s + x))
    inner i s id

let res1: string -> string = repeat_cont 4 "xo"  
res1 ""   // "xoxoxoxo"
res1 "ab" // "xoxoxoxoab"

let res2: int -> int = repeat_cont 4 1 
res2 0 // 4 
res2 5 // 9

I've rewritten repeat_cont to use an inner recursive function in order to make it work with inlining in fsi, otherwise its very much the same code. You'll see its type is int -> 'a -> ('b -> 'b), i.e. you get back a function as the result. Which in a sense is no different from returning a list or an int (usual types used for accumulators), except you can call this one giving it the initial value.

Answer 2

edit: this is known as continuation-passing style. Each recursive call builds its continuation function and passes it along to the next recursive call, to be used as that call chooses (depending on whether it is the base case or not).

---

Just write down the reduction steps:

repeat_cont 4 "xo" id
repeat_cont 3 "xo" k1     where   k1 x = id ("xo" + x)
repeat_cont 2 "xo" k2     where   k2 x = k1 ("xo" + x)
repeat_cont 1 "xo" k3     where   k3 x = k2 ("xo" + x)
repeat_cont 0 "xo" k4     where   k4 x = k3 ("xo" + x)
k4 ""
k3 ("xo" + "")
k2 ("xo" + ("xo" + ""))
k1 ("xo" + ("xo" + ("xo" + "")))
id ("xo" + ("xo" + ("xo" + ("xo" + ""))))
"xoxoxoxo"

Each continuation function ki is "what to do with the result that will be received from the recursive call".

The recursive case ones, ki, say "whatever recursive result x I'm given, prepend s to it and pass the enlarged string up the chain as the new, modified result".

The outermost one, id, just says "return the (final) result as is".

When the base case of 0 is reached, k4 continuation function has been built and is ready to receive its argument, to do its job. It will add the "xo" string to its argument, and pass the result along up the chain of continuation functions, to k3. The argument will be used in "xo" + x, so it must be a string.

Adding "" to a string is an identity operation, so the base case says "just let the chain of continuation functions do their job, without further interference from me".

NB: I've been cautious to always say "continuation function", to avoid confusion with the first-class continuations which are altogether different and much more powerful beasts (not sure if F# has them, though).

Answer 3

When you are building up the list, the elements have the same type as the result of acc.

To terminate the recursion, you need a base case, so you call acc with a known value to generate something with the correct type.

Given that in your example, acc = id, you could replace acc "" with ""