Difference between revisions of "Optimal stack reordering in Forth"

Revision as of 09:51, 8 January 2009

Reordering a stack with the fewest possible operations can be a difficult problem. Some algorithms exist, like Dijkstra's algorithm. Such algorithms may be slow, use a lot of memory and might return with a less than optimal result.

A stack that is 6 levels deep can only be reordered in 6! = 720 different ways. So there exists a set of 720 optimal programs. The problem is that there are billions of possible programs. As an example 11 common Forth words results in about 3.5 billion possible programs that are 10 words or shorter.

The idea behind this is to find the optimal code for every possible way to manipulate the stack for use in a Forth optimizer/compiler to generate optimal code for stack manipulation to a limited depth.

Words used by the search engine: "nop", "drop", "swap", "rot", "-rot", ">r", "r>", "dup", "over", "nip", "tuck". It turns out that only "nop", "swap", "rot", "-rot", ">r", "r>" are actually used since the other words are less efficient in reordering.

After testing all programs only 436 different reorderings were found, the remaining 284 would take more than 10 words to reach.

The attached text file lists all reorderings that are reachable by 10 words or shorter and the shortest possible code to reach them.

Example:

The stack contains:

1 2 3 4 5 6 

The code is: "swap >r swap r> ", the new content of the stack is:

1 2 3 6 4 5

So we search the text file for "123645", near the top of the file we find "123645" and th eoptimal code that is listed next to it is "-rot". So our original code was very bad.

• optimal_stack_programs.txt