   Construction of VMs
  How does someone go about designing and building a VM? Has anyone here done so? If so, can you impart some information on any tips and tricks you may have picked up, and any pitfalls to avoid? There seems to be plenty of information on writing languages for already existing VMs, but not much on the VMs themselves.   
  Well, that depends..First of all, what's the purpose of the VM? Do you need a persistent machine-independent assembly language, an instruction set to speed up script code execution without going for all-out compilation/JITing, an intermediate representation used for optimizations in a compiler, or what?Secondly, and perhaps more importantly, what paradigm are you compiling for? Domain-specific languages used in games and the like often have interesting high-level features which need a great deal of support from the VM and runtime environment.At the end of the day if all you want to do is to get something simple up and running to play with a scripting language of your own then you're probably better off not bothering and executing straight from the syntax tree.   ;  I'm about 85% done on the VM element for my port of the GameMonkey Script scripting language to C#. My design is based on the original, so I can offer some comments on that.As this is a dynamically typed language we have the base type of Variable (or Value) which is effectively a TypeId identifier for an internal VM type and a data item to hold the data for the item. In C++ this is implemented as a union of float/int/void*, in C# I used Value/Object.This type forms the basis of the Stack; the stack itself is a huge list of Variable objects that is pushed to/popped from for everything from function calls to variable operations (ADD,SUB,MUL,DIV, etc). Lua has a register-based system; I won't go into that here for sake of complexity.As GameMonkey has cooperative threads, we actually have several stacks - one in each thread that runs on the VM. The Thread consists of a Function (effectively an Instruction list) and a Stack (amongst other things). An Instruction consists of an OpCode (ByteCode Instruction) and possibly an Operand (which is implemented as Variable).Now that the basic structures are defined, I can talk about how it all ties together. The thread holds a couple of important operating variables; the stack pointer to the "Top" and the Instruction pointer - the place in the instruction list of the currently running bytecode. Running byte code is as 'simple' as defining a list of machine instructions (ADD,SUB,DIV,MUL,PUSH,POP,ASSIGN,CALL,RET), defining how they operate on the machine and then performing that operating when it's executed. Execution is a case of looping over the instruction list until the Thread is killed, yields or is told to return.A basic example:- Imagine you want to do the sum "4 + 5" and leave the result on the stack. The ADD/SUB/MUL/DIV instructions in the machine will need two items on the stack, will perform the operation and then push the value back. You end up with the byte code:PUSH 5  // StackTop++PUSH 4  // StackTop++ADD// StackTop--PUSH will effectively take the value in the operand and set the current stack top and move on... Stack[top++] = currentInstruction.Operand;ADD will pop two values and push the result of the addition...Variable v2 = Stack[top--]; Variable v1 = Stack[top--];Stack[top++] = v1 + v2;This leaves the top of stack (TOS) with a value of "9"...There's lots more I could talk about - function calls, stack frames, local variables, string tables, type operators, etc... If you have any questions, I'd be happy to help.;  OK, I know absolutely nothing aobut GameMonkey Script, but I have a couple of questions about the implementation.1. If the script is bytecode, how is the operand stored? A 4-byte value that is interpreted (via the union) as the user wills?2. How do you deal with return values? My impression of the stack was that (I'm getting most of this from JVM, so bare with me if this is different to the way GameMonkey does things) a new "frame" is created on the stack, which houses the local variables and a "working" section for the intermediate results of operations (as you defined in your post above). Where do you store the return value while you're unwinding to the previous frame? I assume there is some sort of register for this?[Edited by - webwraith on May 15, 2009 7:54:03 AM];  As I've not written the parser/compiler yet, I've written it so that it can load an run bytecode that has been run through the original C++ implementation and saved to a file.My Bytecode in C# is basically:public enum OpCode : byte{  Nop = 0,  OpAdd,  OpSub,  ... etc}public struct Instruction{  public OpCode opcode;  public Variable [] operands;}In the original C++ version it was as you described; a single int for the opcode and then another (optional) 4 bytes for the operand. The operand was generally be a numeric (int/float) and is either an offset into the function table, string table or the literal value that gets passed. These 'reference' objects are resolved to pointers at runtime and are pushed with special opcodes PUSHSTR, PUSHFN, that basically put the pointer into the Variable at the top of the stack and set the type to being that of string,function,table, etc. A similar thing happens to ints/floats, but these are values and are pushed using PUSHINT, PUSHFLOAT.So, to cut a long story short, you have effectively a set of opcodes that tell the machine the type when it's being pushed and then the operand data itself is copied as-is into the variable in the stack.switch(instruction.OpCode){  case OpCode.PushInt:    stack[top++] = instruction.Operand;    break;}In C++ it'd be mush the same, except you'd be doing something like:  stack[top].m_value.m_int = (int)(*instrptr[1]);  stack[top].m_type = GM_INT;  instrptr += 2; // advance past instruction plus operandFunction calls need stack frames. Stack frames are basically structures that hold the following information - the location of the 'base' of the function before the call, the current instruction pointer and the previous stackframe.In C#, my Stackframe is:    internal class StackFrame    {   public int ReturnBase;   public int InstructionPtr;   public StackFrame PreviousFrame;    }InstructionPointer is simple enough, it's the offset into the currently executing bytecode - the point in which the code should return to after the function call.To understand ReturnBase, let's look at how a function is actually called. In GM the following bytecode calls a function:PUSH <variable>  // Push a value for 'this' - null if nonePUSHFN <FUNCTIONOBJECT> // Push the function to callPUSH blah1 // push the first parameterPUSH blah2 // push the second parameterCALL 2 // 2 means 2 parameters passedWhen the 'CALL' instruction is hit, it knows you're wanting to do a function call - I launch immediately into PushStackFrame. At the time of this, the stack looks like this:top:  top-1:blah2top-2:blah1top-3:functiontocalltop-3:'this'PushStackFrame first calculates the 'base' of the function - effectively the location of the actual function itself, so it's Top - NumParameters; in this case Base is -2. This is important as anything between base and top are the parameters we've passed, so users can access them in the code. At this point you construct your new stack frame - you need to restore 'base' of the current function as when you return, this gives you access to your parameter variables again; you store your current instruction pointer so you can return back where you were and then you store your current stackframe so that you can get back to it:In my code it looks like this:StackFrame frame = new StackFrame();frame.ReturnBase = currentBase; // current base locationframe.InstructionPtr = instructionPtr; // current instruction ptrframe.PreviousFrame = currentFrame; // current frame becomes previouscurrentFrame = frame;With all this stored, you're then free to move around the code and change the base - I jump into a new script function by setting the instruction pointer to the start instruction in my new list (all my functions' instructions are held in separate lists), I set currentBase to my new base, set the top of the stack to the new base + the number of local parameter/variable slots and then the script is set up so that the next code to be executed in the new function and all the parameters are available for you.So the stack again, this time with 'base' markedtop: <nothing> top-1:blah2  // basetop-2:blah1  // basetop-3:functiontocall   // base - 1top-4:'this' // base - 2To return back to where you were, you have to restore your previous stackframe. This is done in PopStackFrame and is fairly straight forward. You grab the previous stackframe info from currentFrame.PreviousFrame and start resetting everything back - the instruction list, the instruction pointer, the top of stack and then the currentFrame is removed.You asked how a function returns a value - in GM you can have ONE return value per function (unlike Lua). This value is deemed to be the last value pushed to the stack at the time of the function exiting - this value is copied to the location in the stack[base-2], which is where we stored 'this' previously. The final act of restoring the stack frame is to change the top of the stack to point to stack[base-1], so that when we pop the return value we receive back the correct value.Here's some code to finish the pop:instructionPtr = currentFrame.InstructionPtr;stack[base- 2] = stack[top- 1];top= currentBase- 1;currentBase= currentFrame .ReturnBase;currentFrame = frame;Imagine your function returns a value of 666999, your bytecode inside the function would look like:PUSHINT 666999RETV   // pops the stackframeThe stack, after the call would then becometop:  functiontocall   // now top, this will be overwritten on next push, effectively nulltop-1:666999    In GM, the function will always push a NULL if no value is returned - this keeps the stack frame handling consistent.I hope this is useful?   ;  An important part of the design for a VM is its use and what language features it must support.An example on a VM I was designing/writing recently :For resume/yield functioality for multiple persistant objects running using a VM(each object runs as a 'fiber' and yields control after a typical behavior processing pass (running a FSM))How to have the initializer run on object creation but then the instruction path that never goes there again but will resume execution after returning from a yield point in the code.1) Yield has no address set in object state, and resume reenteres 'The Big Switch'  (probably with 'common' code run befor dispatching to the current object state)which is controlled by a standard 'state' global variable.  Initialization starts with state=0.   (state may actually be a address of the 'state' code block)2) Yield sets address at current position (requiring jump instruction  back to start of current state..)   Resume executes starting the current address (past the yield instruction)   Initialization starts at address 0000 which will transition to a proper running state.With that particular implementation it is understood that yield will be done at the end completed  behavior processing and the object will be woken up next time to run the next 'turns' behavior.   All data is on a stack with stackframes for function calls (which generally are resolve/returned before yield is called)-------------Data for objects processing will pull from a central data set, requiring various specialized data structures to be returned.   The VM would have to service all these via standard functions or a flexible call mechanism (variable parameters,  element access to return structures, possibly link list traversals).-----------------Most of the compilers for the VMs Ive written have built in equation simplification to minimize the amount of VM bytecode that needs to be emitted.-------------------To simplify on one VM - I eliminated INTEGER types and merged their use into a FLOAT type  to simplify the VMs instructions  (eliminated duplication of all operations and conversion scenarios).-----------------------VM design issue -- to support arrays/structure elements  with specialized (optimized) bytecodes   (or to do equivalent with link lists for iterationprocessing  -- either way mechanism to support FOREACH type operations)------------------------------------------The things I mention above show that VMs can get fairly complex if you want efficiency handling specific language features.   