PDA

View Full Version : Mill's Algorithm



LuckY
03-23-2004, 10:06 AM
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).

DavidP
03-23-2004, 11:01 PM
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?

LuckY
03-24-2004, 11:40 AM
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:
int main() {
if (true)
statement;
return 0;
}Turns into this:
int main() {
bool v = true;
while (v) {
if (true) {
statement;
v = false;
}
else
v = false;
}
return 0;
}