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

Step1, introduce the continuation function.

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

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

the final result is

Let us follow the same step.

Step0: introduce the continuation function first

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

Step2: resolve the sumL.

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

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

## No comments:

Post a Comment