Thread: Mill's Algorithm

Any of you ever tried implementing Mill's Algorithm before? An instructor of mine suggested that we try it as it would be a highly marketable product seeing as how know one has ever done it before (as far as he knows). Of course when I hear about something so intriguing I want to give it a go. Actually I was considering making that my thesis...
If you are unfamiliar with Mill's Algorithm is, it defines a few steps you can perform on any code to turn it into a program with _only_ D-Structures (Dijkstra Structures are if..else, while, a single statement, and multiple statements).

I have never even heard of Mill's Algorithm before.

It is not on the Dictionary of Algorithms website:

http://www.nist.gov/dads/

Do you have any websites or other sources with information on this algorithm?

Yeah I was actually surprised to find only 2 hits when searching google for any info on it.

The only description I know of for the algorithm is illustratory. I'm attaching a couple drawing I did. One shows how the algorithm works and the other is a homework assignment on it so you can see it in action.

About the diagrams:
The way you're supposed to look at it is, to start with, the entire program is a big bundle of messy wires (a circle) with a single line going in and a single line coming out. You pull on the wire at the top and see what is next in the code. One of four things gets pulled out: Square = statement, diamond = if condition, circle = some unknown code, the arrowhead at the end of an arrow from somewhere else.

D-Structures:
1) a single statement
2) multiple statements
3) if-else statement (NOT just if)
4) while loop (NOT do-while)

Again, the algorithm is supposed to take bad code (defined as code that uses anything other than a D-Structure) and recode it using only D-Structures.

For example, this:

Code:

int main() {
  if (true)
    statement;
  return 0;
}

Turns into this:

Code:

int main() {
  bool v = true;
  while (v) {
    if (true) {
      statement;
      v = false;
    }
    else
      v = false;
  }
  return 0;
}