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. Now that we have the list of optimal programs it is easy to intergrate it into a compiler and the text editor. For example you could just type the 6 digit stack order you want and have a script in the text editor look up the optimal code.
It is easy to extend this search to include any operation that does not depend on the actual content of the stack. For example if we allow deletions and copying of cells we end up with 10 485 possible stack permutations if we limit ourselves to programs that are 8 words or shorter.
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 we want to optimize 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.
