Functions in a Stack based Virtual Machine

Question

I'm creating a stack-based Virtual Machine for a programming language. Things are going well so far, I have these operations.

1. EOP - End of Program
2. EOI - End of Instruction
3. PUSH - Push onto the stack
4. POP - Pop the stack
5. PRINT - Print the top of the stack
6. ADD - Add the top number to the number directly below it
7. MUL - Multiply
8. SUB - Subtract

But my question is, what kind of instructions would I need to add to use things like, conditionals, loops and functions?

Answer 1

At the least you'd need a conditional GOTO. Depending on how your language works with data, that instruction might just pop the last element off the stack, check whether it's 0 or 1 and then either jump by a fixed number of bytes/instructions, or do nothing (usually the jump location is encoded in the instruction itself).

But usually you also add a few testing instructions or comparison instructions that usually pop the last two elements off the stack, compare them in some way, then push 0 or 1 on the stack instead to indicate whether they're equal. Usually the comparison expressions are equivalent to the common comparison operators, i.e. <, >, <=, >=, =, !=.

You'd also need an unconditional GOTO, which is often a separate instruction, but could also be achieved by pushing 1 on the stack before you hit the GOTO.

BTW, I've blogged about the details of creating a compiler and bytecode interpreter in a blog post: http://orangejuiceliberationfront.com/how-to-write-a-compiler/

Answer 2

For conditionals you need

• relational operators (eq ne lt not etc)
• Jump true/false

For loops you have enough, but a FOR loop might have its own

• FOR
• NEXT

For functions you need

• CALL (args on stack)
• RETURN (value on stack)

For variables and arrays:

• LOAD
• STORE
• DIM array
• Index [] versions of LOAD and STORE

For expressions, most things will be library functions called as needed. There is a lot to be said for keeping the VM small and putting most of the code in the library.

You can implement most non-object oriented languages with just these instructions. OOPS needs a few more.

The JVM and CLR are well documented, so read what they do and consider what to use. There are lots of other VMs out there and lots of ideas.