Continuations are a powerful construct in functional programming that allow for control flow manipulation. In the context of tail call optimization, continuations can be used to implement tail recursive functions that would otherwise not be tail recursive, or to implement functions that are more efficient than their tail recursive counterparts.

Here’s an example of the append function without continuations:

let rec append (l1: 'a list) (l2: 'a list) : 'a list =
  match l1 with
  | [] -> l2
  | x :: xs -> x :: (append xs l2)

This append function is a simple, straightforward implementation of list concatenation. However, it is not tail recursive because the result of each recursive call to append is immediately used as the head of the result list. This means that the function must keep the entire result list on the stack until the recursion is complete, which can lead to stack overflow for very long lists.

Here’s an example of the append function using continuations:

let rec append (l1: 'a list) (l2: 'a list) (return: 'a list -> 'r) : 'r =
  match l1 with
  | [] -> return l2
  | x :: xs -> append xs l2 (fun l -> return (x :: l))

Here’s a trace of the append function with continuations, showing the flow of the closures as the function is executed:

Call: append [1; 2; 3] [4; 5; 6] (fun x -> x)

(* 1. *) append [2; 3] [4; 5; 6] (fun l -> (fun x -> x) (1 :: l))
(* 2. *) append [3] [4; 5; 6] (fun l -> (fun x -> x) (2 :: (1 :: l)))
(* 3. *) append [] [4; 5; 6] (fun l -> (fun x -> x) (3 :: (2 :: (1 :: l))))
(* 4. *) (fun x -> x) [4; 5; 6] (3 :: (2 :: (1 :: l)))
(* 5. *) [3; 2; 1; 4; 5; 6]

The non-tail call recursive version of append is simpler and runs faster on small lists, as it relies solely on the stack for its recursive calls. However, on large lists, this version may run into a stack overflow error as the stack is not large enough to handle the recursion. Both versions use O(n) memory, but the type of memory used is different. The non-tail call version uses the stack for its recursive calls, which is limited in size but faster to access, while the tail call version uses the heap to store its intermediate results, which is not limited in size but slower to access.

Here is a second example of a sum function with and without tail-call optimization:

let rec sum (l : int list) : int = 
  match l with
  | [] -> 0
  | x :: xs -> x + (sum xs)

let rec sum_cps (l : int list) (return: int -> 'r) : 'r = 
  match l with
  | [] -> return 0
  | x :: xs -> sum_cps xs (fun l -> return x + l)