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