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 resulting stack order 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, code like this can some times result from earlier compilation steps like inlining of short words.
Generalisation
All stack move operations can be considered bitwise logical operations. What defines bitwise operations is that each bit is processed the same way and independently from other bits in the word.
For example a SWAP operation on two cells is logically equivalent to:
a = a EOR b b = a EOR b a = a EOR b
This means that this optimisation method will also work equally well on all bitwise operations with some simple changes.
