Forth is one of the few non-esoteric stack-based languages. For this challenge, we will use a small subset of Forth, which simply executes a sequence of words in a linear fashion — without any definitions or loops.
In good Forth code, each word definition includes a stack effect comment, which explains the layout of the stack before and after the word's execution. For example,
+ has the stack effect
a b -- sum,
swap has the stack effect
a b -- b a, and
ptr len byte --. Both before and after the
--, the top of the stack is to the right, and thus the stack elements are written in the order in which you'd have to push them.
Note that, if the word only manipulates the order of elements on stack, the stack effect is a complete specification of its behavior. Your task is to write a program or function that takes such a stack effect as input, and emits an implementation of it in the subset of Forth described below.
The Forth subset
Your output may make use of the words
r>. Three of those are fully specified by their stack effect:
drop ( a -- ) dup ( a -- a a ) swap ( a b -- b a )
The last two make use of the return stack. Apart from the main data stack, Forth also has another stack, which is used to save return addresses while calling user-defined words. However, since Forth implementers are trusting people, the programmer may also store their own data on the return stack within one procedure, as long as they clean it up before returning.
To use the return stack, we have the last two words:
>r ( x -- ; R: -- x )moves an item from the data stack to the return stack
r> ( -- x ; R: x -- )moves an item from the return stack back to the data stack
Your code must use the return stack on in a balanced manner.
Let's take a close look at one of the programs you could output given the input
c a b -- b a b.
Data stack Return stack c a b swap c b a >r c b a swap b c a drop b a dup b b a r> b b a swap b a b
swap >r swap drop dup r> swap would be your output.
Input and output
Your input will consist of two lists of names, describing the before and after states of the stack. The names in the first list will all be unique. The names in the second list all occur in the first one.
The output list may contain duplicates, and it does not need to include every name from the input list.
Parsing is not a part of the challenge, so you may use any reasonable format for these lists. Some examples of the input formats you can choose:
"a b -- b a" "a b", "b a" "ab:ba" ["a", "b"], ["b", "a"] [2, 7], [7, 2]
In particular, you are allowed to reverse the ordering, taking the top of the stack to be the beginning of each list.
Your output, which represents a Forth program, can also use any way of encoding a sequence of instructions. For example:
"drop swap dup >r swap r>" "xsd>s<" "earwax" [3, 2, 1, 0, 2, 4]
Each test consists of two lines. The first is the input, but since the solution isn't unique, the second line is merely an example of what the output can look like. You can use this Python program to check that the programs you are generating are correct.
If you'd like to generate some larger test cases, use this script.
a b -- a b a >r dup r> swap a b -- b a b swap >r dup r> swap c a b -- b a b swap >r swap drop dup r> swap a b c -- c b a swap >r swap r> swap a b c -- b c a >r swap r> swap a b c d -- d a c swap >r swap drop swap r> a b c d -- d c b a swap >r swap >r swap r> swap r> swap >r swap r>