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.

Scrope

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.

Galloglass

perhaps also show res1 "ab" => "xoxoxoxoab", i.e. res1 represents a string prefix, re: difference-lists. You do show this for ints. So res2 = (4 +) and res1 = ("xoxoxoxo" +). Nice. – Rockabilly

the structure you build up in the accumulator is a function Ooooooohhhh... see, now I just feel stupid for even asking. Makes perfect sense now. Very well explained! – Scrope

@WillNess: sure, why not. – Galloglass

@KagemandAndersen: You shouldn't be, it's a very good question. CPS is one of those things that you really need to put in the time and effort into before you can fully appreciate it (and I won't claim I'm that comfortable with it myself either). – Galloglass

@KagemandAndersen so now, repeat_cont 4 "xo" is not a string consisting of 4 "xo"s; it is a string prefix consisting of 4 "xo"s. If what you want is a string, you will have to always call this "string prefix" function with the "" argument, and this implementational detail is better hidden in the base case and not be exposed like that. Whether you call it inside the base case or outside, you still do call it, to apply the function chain and get the actual tangible value back. – Rockabilly

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).

Rockabilly

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 ""

Brownedoff

id is not fired at the base, but rather at the top (see my answer for the reduction sequence). Replacing acc "" with just "" means that continuations won't be used at all, and instead "" will always be returned, for any n. – Rockabilly