Turns out this is one of the programs where a great deal of
simplification is possible.
The first thing to note is that the second call in the original program
is "tail recursive;" it is followed immediately by a return. For such
calls, saving params on the stack is unnecessary because they are
merely popped later with no other action. (In fact, good compilers do
an optimization called "tail recursion removal" for this reason.) You
can verify in the code above that all stack elements where .rtn==2 are
popped in this manner.
So instead of the second PUSH, we can just SET the stack top to new
param values. This means that the .rtn field doesn't serve any
purpose. All returns must be to the label return_from_move_1. With
this the structure of the program gets quite simple, and gotos are easy
to remove. Here is a result:
int main(void)
{
struct stack_elt_t {
int n;
char from, hold, to;
} stk[1000];
int p = 0; // stack pointer
// names for stack top
#define N stk[p].n
#define FROM stk[p].from
#define TO stk[p].to
#define HOLD stk[p].hold
// set stack top
#define SET(N_, FROM_, TO_, HOLD_) \
do { struct stack_elt_t e = { N_, FROM_, HOLD_, TO_ }; stk[p] = e; }
while (0)
// push onto stack
#define PUSH(N_, FROM_, TO_, HOLD_) \
do { struct stack_elt_t e = { N_, FROM_, HOLD_, TO_ }; stk[++p] = e;
} while (0)
SET(4, 'a', 'c', 'b');
for (;;) {
if (N > 0)
PUSH(N - 1, FROM, HOLD, TO);
else if (--p >= 0) {
printf("move top of %c to %c\n", FROM, TO);
SET(N - 1, HOLD, TO, FROM);
}
else break;
}
return 0;
}
Pretty short and sweet!
