## Sunday, October 28, 2012

### 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
``````