Trying to figure out which instructions a stack machine has, and wanted to clarify / reassure that these are in fact all of them.

  • push onto stack
  • pop off stack
  • call a system function like add

Then you can implement jump, for example, by pushing the address of the instruction in memory, and calling call. You can implement add by pushing twice and popping twice, etc. You can implement everything from just these 3 instructions. Wondering if this is correct, or if there is anything I am missing.

  • $\begingroup$ There is no single canonical stack machine. $\endgroup$ – Yuval Filmus Mar 7 '19 at 13:45

There are dozens and dozens of stack machines out there in the wild, and they all have different instruction sets. So there's no single correct answer.

Some people might consider using CALL like that cheating: after all, it relies on things like ADD and CMP and JMP and DUP and such all being implemented in the machine, so why don't you call them instructions? But if you're going that route, you can get rid of POP too, and implement that with CALL. The only reason you can't get rid of PUSH too is you need some way to get opcodes and arguments onto the stack.

If you don't want to use CALL like that, the minimum for Turing-completeness would be something like PUSH, ROT (rotate the stack in some controllable way), DUP (duplicate the top of the stack), CMP (compare two values), JMP (some sort of conditional GOTO), and SUB (subtract one number from another). An actually useful machine would have more, things like ADD and AND and such.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.