Optimal stack reordering in Forth
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.
A program made to try all possible combinations of words to find the optimal results once and for all is not very complicated to make and takes about 30 minutes to run on a modern PC even when it is not optimized for speed.
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 the optimal code that is listed next to it is "-rot". So our original code was very bad.
