When I look up "stack machine" I often get stuff like the JVM that uses a stack for data, but it still uses an array to store its instructions.
I would like to find out more about machines whose programs are stacks. For example, executing the command at the top of the stack by default removes the element at the top of the stack, and the program execution ends when the instruction stack is empty.
I'm afraid that this might be a silly question, but I have no idea what else these may be called.
I would like to know what the implementation of such a machine would look like (for example, how control flow might be handled on such a machine, how expressive the instruction set might be, etc.). A link to a Wikipedia page or some other reference would be really cool too.
While Forth, JVM bytecode, and others are heavily "stack-based", their program memory is not because the executable is always "there" like in a constant array, and if you want to branch to a different location you simply adjust the program counter.
On the other hand, in the hypothetical machine with a stack-instruction set you always execute the next instruction on the top of the stack. As Winston suggests, conditionals could be implemented by pushing various instructions onto the instruction stack.
For instance, you could have a PRINTFOR instruction that takes the number from the top of the data stack and puts that many PRINT instructions at the top of the execution stack.
For instance, if your original program was (in Forth style):
1 3 2 PRINTFOR
At some point you will have:
Program Stack: PRINTFOR
Data Stack: 2 3 1
Then you will have:
Program Stack: PRINT PRINT
Data Stack: 3 1
And you will see
3
1
on stdout.
I was curious as to what a "fully featured language" that takes on this kind of approach might look like.
@Mark Booth, I might just be asking an impractical question, and I might only have thought of this because of my inexperience. I'll try to explain why I wanted such an architecture.
I had worked through the Lex and Yacc tutorial Lex & Yacc Tutorial by Tom Niemann.
When I got to the part where he implements the calculator on a hypothetical stack-based machine, I spent some time implementing a VM myself.
However, I felt that at a couple of points the design could be easier for me to implement. In order to manage control flow, the machine uses some form of goto, and label. However, this would mean that in order to run an instruction, my machine would have to be aware of all the goto's all over the place. In some sense each instruction wouldn't be "context-free", and I was afraid this was bound to be more work than the alternative.
Instead of using a label, I could have goto take an instruction location (or an offset) so that I could simply set the pc to goto's operand. But this still seemed kind of messy to me. It still felt like the goto had to "know" stuff about the other instructions (and where they were) and the implementation could be cleaner.
I thought putting the operands on a stack was really cool, because it took away a lot of choices I didn't really care about when I dealt with registers. I figured maybe somebody has done something similar for instruction memory.
The benefit of such a system might be that each instruction is in some sense, "context-free", that is, when I implement the individual instructions, I don't have to worry about how many instructions there are, all I have to worry about are what the previous instructions have done (that is, the result of the data stack(s)), and what the instructions in the future are going to do (that is, the stuff left on the instruction stack). An interesting consequence would be that even in the middle of a while loop, all instructions you are going to perform in the future is considered an instruction "down the stack". i.e.
If I have:
int x = 0;
while (True) {
x++;
if (x > 100) break;
print(x);
}
The "print" statement is physically placed below the "x++" statement, and it gets executed after the "x++" statement. However, when we reach the "print" statement, it can't forget about all the instruction that came before it. We still have to remember that the while loop closes the ending brace.
Furthermore, we don't know exactly which of the previous statements we are going to execute. In a stack-based instruction set, we can forget any instruction that has come before, and simply claim "We're going to do everything that's left in the instruction stack." This way it also becomes easier to see a program as the composition of other programs.
I'm afraid that some experienced coders might find that this really silly, because the design might end up imposing severe limitations that can only be overcome by doing things the old way, or I'm just making the classic way of implementing a VM harder than it is. However if this is the case, it would be cool if you could leave some comments to help me understand. On the other hand, I'm having trouble on how the idea might blow into a full instruction set, so even if it were possible, I'm not sure how it might be done.
