F# Continuation Style Programming

The more I do F#, the more I use recursive function. Consequently, I run into more stack overflow problem. :-(. The continuation CSP seems the only way I can use to avoid stack overflow. the following code is normal recursive version of function and CSP version. The key point is that the function won't return, so it does not create element on the call stack. The computation is delayed to continuation function so it does not need to keep the stack element any more.

 module FunctionReturnModule =   
   let l = [1..1000000]  
   let rec sum l =   
     match l with  
     | [] -> 0  
     | h::t -> h + sum t  
   sum l  

 module CPSModule =   
   let l = [1..1000000]  
   let rec sum l cont =   
     match l with  
     | [] -> cont 0  
     | h::t ->   
       let afterSum v =   
         cont (h+v)  
       sum t afterSum  
   sum l id  

Ok, the next problem is how to get the CSP version from the recursive version? Ok, here is the step I follow. Please keep in mind that some intermediate step codes won't compile.

Step 0

 module FunctionReturnModule =   
   let l = [1..1000000]  
   let rec sum l =   
     match l with  
     | [] -> 0  
     | h::t ->   
       let r = sum t  
       h + r  
   sum l  

Step1, introduce the continuation function.

 module FunctionReturnModule =   
   let l = [1..1000000]  
   let rec sum l cont =   
     match l with  
     | [] -> 0  
     | h::t ->   
       let r = sum t  
       cont (h + r)  
   sum l  

Step2: resolve the recursive function sum. The cont is move inside the afterSum. The afterSum function takes value (v) and pass it to cont (h+v).

 module CPSModule =   
   let l = [1..1000000]  
   let rec sum l cont =   
     match l with  
     | [] -> cont 0  
     | h::t ->   
       let afterSum v =   
         cont (h+v)  
       sum t afterSum  
   sum l id  

Well, let us use the same approach for tree traversal. The tree definition is listed below:

 type NodeType = int  
 type BinaryTree =  
   | Nil  
   | Node of NodeType * BinaryTree * BinaryTree  

the final result is

 module TreeModule =   
   let rec sum tree =   
     match tree with  
     | Nil -> 0  
     | Node(v, l, r) ->  
       let sumL = sum l  
       let sumR = sum r  
       v + sumL + sumR  
   sum deepTree  
 module TreeCSPModule =   
   let rec sum tree cont =   
     match tree with  
     | Nil -> cont 0  
     | Node(v, l, r) ->  
       let afterLeft lValue =   
         let afterRight rValue =   
           cont (v+lValue+rValue)  
         sum r afterRight  
       sum l afterLeft  
   sum deepTree id  

Let us follow the same step.
Step0: introduce the continuation function first

 module TreeModule =   
   let rec sum tree cont =   
     match tree with  
     | Nil -> 0  
     | Node(v, l, r) ->  
       let sumL = sum l  
       let sumR = sum r  
       cont (v + sumL + sumR)  
   sum deepTree  

Step1: resolve the sumR. Move the cont function to afterRight and pass afterRight to sum r as continuation function.

 module TreeModule =   
   let rec sum tree cont =   
     match tree with  
     | Nil -> 0  
     | Node(v, l, r) ->  
       let sumL = sum l  
       // let sumR = sum r  
       let afterRight rValue =    
         cont (v + sumL + rValue)  
       sum r afterRight  
   sum deepTree  

Step2: resolve the sumL.

 module TreeModule =   
   let rec sum tree cont =   
     match tree with  
     | Nil -> 0  
     | Node(v, l, r) ->  
       //let sumL = sum l  
       let afterLeft lValue =  
         let afterRight rValue =    
           cont (v + lValue + rValue)  
         sum r afterRight  
       sum l afterLeft  
   sum deepTree  

Ok, we can use the following code to test the code.

 let tree n =   
   let mutable subTree = Node(1, Nil, Nil)  
   for i=0 to n do  
     subTree <- Node(1, subTree, Nil)  
   subTree  
 let deepTree = tree 1000000  

Tweet to fsharp