Ocaml Implementation

Question

I am having problems for converting following algo in ocaml To implement this algorithm i used Set.Make(String) functor actualy in and out are 2 functions Can any one give me percise code help in ocaml for following

This is actually Algo for Live Variables[PDF] ..Help would be appreciated greatly

for all n, in[n] = out[n] = Ø
w = { set of all nodes }
repeat until w empty
    n = w.pop( )
    out[n] = ∪  n’ ∈ succ [n] in[n’]
    in[n] = use[n] ∪ (out[n] — def [n])
    if change to in[n],
        for all predecessors m of n, w.push(m)
end

Answer 1

for all n, in[n] = out[n] = Ø
    w = { set of all nodes }
    repeat until w empty
    n = w.pop( )
    out[n] = ∪  n’ ∈ succ [n] in[n’]
    in[n] = use[n] ∪ (out[n] — def [n])
    if change to in[n],
    for all predecessors m of n, w.push(m)
end

It's hard for me to tell what is exactly going on here. I think there is some alignment issues with your text --repeat until w empty should be repeating the next 5lines, right? And how are in and out functions, they look like arrays to me? Aside from those deficiencies I'll tackle some general rules I have followed.

I've had to translate a number of numerical methods in C and Fortran algorithms to functional languages and I have some suggestions for you.

0) Define the datatypes being used. This will really help you with the next step (spoiler: looking for functional constructs). Once you know the datatypes you can more accurately define the functional constructs you will eventually apply.

1) Look for functional constructs. fold, recursion, and maps, and when to use them. For example, the for all predecessors m is a fold (unsure if that it would fold over a tree or list, but none-the-less, a fold). While loops are a good place for recursion --but don't worry about making it a tail call, you can modify the parameters later to adhere to those requirements. Don't worry about being 100% pure. Remove enough impure constructs (references or arrays) to get a feel for the algorithm in a functional way.

2) Write any part of the algorithm that you can. Leaving functions blank, add dummy values, and just implement what you know --then you can ask SO better, more informed questions.

3) Re-write it. There is a good chance you missed some functional constructs or used an array or reference where you now realize you can use a list or set or by passing an accumulator. You may have defined a list, but later you realize you cannot randomly access it (well, it would be pretty detrimental to), or it needs to be traversed forward and back (a good place for a zipper). Either way, when you finally get it you'll know, and you should have a huge ear-to-ear grin on your face.