VM from Martin's site.

gistfile1.as

function VMCheney (instructionArray, heapSlot)
{
	this.instructionArray = instructionArray;
	this.heapSlot = heapSlot;
}

VMCheney.prototype.HEAP_SIZE = 400;
VMCheney.prototype.SPACE_SIZE = 200;

VMCheney.prototype.peek = function (address, size)
{
	trace ("peek");
	for (var i = address;i < address + size;++i)
	{
		trace ("at " + i + ": " + this.heap[i]);
	}
};

VMCheney.prototype.INTVALUE = 1;
VMCheney.prototype.newInt = function (i)
{
	var address = this.newNode (2);
	this.heap[address] = TAGS.INT;
	this.heap[address + VMCheney.INTVALUE] = i;
	this.update (address);
	return address;
};

VMCheney.prototype.BOOLVALUE = 1;
VMCheney.prototype.TRUE = 1;
VMCheney.prototype.FALSE = 0;
VMCheney.prototype.newBool = function (i)
{
	var address = this.newNode (2);
	this.heap[address] = TAGS.BOOL;
	this.heap[address + VMCheney.BOOLVALUE] = i;
	this.update (address);
	return address;
};

VMCheney.prototype.newError = function ()
{
	var address = this.newNode (2);
	this.heap[address] = TAGS.ERROR;
	this.update (address);
	return address;
};

VMCheney.prototype.CLOSUREENVIRONMENT = 1;
VMCheney.prototype.CLOSUREADDRESS = 2;
VMCheney.prototype.CLOSURESTACKSIZE = 3;
VMCheney.prototype.newClosure = function (e, a, s)
{
	var address = this.newNode (4);
	
	if (this.heap[e] == TAGS.COPIED) e = this.heap[e + VMCheney.FORWARDING_ADDRESS];

	this.heap[address] = TAGS.CLOSURE;
	this.heap[address + VMCheney.CLOSUREENVIRONMENT] = e;
	this.heap[address + VMCheney.CLOSUREADDRESS] = a;
	this.heap[address + VMCheney.CLOSURESTACKSIZE] = s;
	this.update (address);
	return address;
};

VMCheney.prototype.STACKFRAMEPROGRAMCOUNTER = 1;
VMCheney.prototype.STACKFRAMEENVIRONMENT = 2;
VMCheney.prototype.STACKFRAMEOPERANDSTACK = 3;

VMCheney.prototype.newStackFrame = function (pc, e, os)
{
	var address = this.newNode (4);
	
	if (this.heap[e] == TAGS.COPIED) e = this.heap[e + VMCheney.FORWARDING_ADDRESS];
	if (this.heap[os] == TAGS.COPIED) os = this.heap[os + VMCheney.FORWARDING_ADDRESS];
	
	this.heap[address] = TAGS.STACKFRAME;
	this.heap[address + VMCheney.STACKFRAMEPROGRAMCOUNTER] = pc;
	this.heap[address + VMCheney.STACKFRAMEENVIRONMENT] = e;
	this.heap[address + VMCheney.STACKFRAMEOPERANDSTACK] = os;
	
	this.update (address);

	return address;
};

VMCheney.prototype.OPERANDSTACKSIZE = 1;
VMCheney.prototype.OPERANDSTACKTOPOFSTACK = 2;

VMCheney.prototype.newOperandStack = function (size)
{
	var address = this.newNode (size + 3);
	this.heap[address] = TAGS.OPERANDSTACK;
	this.heap[address + VMCheney.OPERANDSTACKSIZE] = size;
	this.heap[address + VMCheney.OPERANDSTACKTOPOFSTACK] = address + VMCheney.OPERANDSTACKTOPOFSTACK;
	this.update (address);
	return address;
};

VMCheney.prototype.push = function (x)
{
	this.heap[this.os + VMCheney.OPERANDSTACKTOPOFSTACK] = this.heap[this.os + VMCheney.OPERANDSTACKTOPOFSTACK] + 1;
	this.heap[this.heap[this.os + VMCheney.OPERANDSTACKTOPOFSTACK]] = x;
};

VMCheney.prototype.pop = function ()
{
	var value = this.heap[this.heap[this.os + VMCheney.OPERANDSTACKTOPOFSTACK]];
	this.heap[this.os + VMCheney.OPERANDSTACKTOPOFSTACK] = this.heap[this.os + VMCheney.OPERANDSTACKTOPOFSTACK] - 1;
	return value;
};

VMCheney.prototype.ENVIRONMENTSIZE = 1;
VMCheney.prototype.ENVIRONMENTFIRSTENTRY = 2;

VMCheney.prototype.newEnvironment = function (size)
{
	var address = this.newNode (size + 2);
	this.heap[address] = TAGS.ENVIRONMENT;
	this.heap[address + VMCheney.ENVIRONMENTSIZE] = size;
	this.update (address);
	return address;
};

VMCheney.prototype.extend = function (env, byHowMany)
{
	var address = this.newNode (this.heap[env + VMCheney.ENVIRONMENTSIZE] + byHowMany + 2);
	
	if (this.heap[env] == TAGS.COPIED) env = this.heap[env + VMCheney.FORWARDING_ADDRESS];

	this.heap[address] = TAGS.ENVIRONMENT;
	this.heap[address + VMCheney.ENVIRONMENTSIZE] = this.heap[env + VMCheney.ENVIRONMENTSIZE] + byHowMany;
	for (var i = 0;i < this.heap[env + VMCheney.ENVIRONMENTSIZE];++i)
	{
		this.heap[address + VMCheney.ENVIRONMENTFIRSTENTRY + i]
			= this.heap[env + VMCheney.ENVIRONMENTFIRSTENTRY + i];
	}
	this.update (address);
	return address;
};

VMCheney.prototype.heapAddressToString = function (address)
{
	switch (this.heap[address])
	{
		case TAGS.INT:
			return this.heap[address + VMCheney.INTVALUE];
			
		case TAGS.BOOL:
			return (this.heap[address + VMCheney.BOOLVALUE] == 1) ? "true" : "false";
			
		case TAGS.ENVIRONMENT:
			return "env";
			
		case TAGS.CLOSURE:
			return "fun..->..";
			
		case TAGS.STACKFRAME:
			return "stackframe";
			
		case TAGS.OPERANDSTACK:
			return "operandstack";
			
		case TAGS.ERROR:
			return "error";
			
		default:
			return "TAG not known";
	}
};

VMCheney.prototype.initialize = function ()
{
	// program counter initially 0
	this.pc = 0;
	
	// runtime stack initially empty
	this.rts = new RuntimeStack ();
	
	// initialize heap to 10000;
	this.heap = new Array (VMCheney.HEAP_SIZE);

	// initialize the current spaces
	this.fromSpace = 0;
	this.topOfSpace = this.fromSpace + VMCheney.SPACE_SIZE;
	this.toSpace = this.topOfSpace;
	
	// initial top-of-heap is 0
	this.hp = this.fromSpace;
	
	// start with empty environment
	this.e = this.newEnvironment (0);
	
	this.os = -1;
};

VMCheney.prototype.step = function ()
{
	flipping = false;

	var i = this.instructionArray[this.pc];
	
	switch (i.OPCODE)
	{
		case OPCODES.START:
		{
			this.os = this.newOperandStack (i.MAXSTACKSIZE);
			this.pc++;
			break;
		}
		
		// pushing constants
		
		case OPCODES.LDCI:
		{
			this.push (this.newInt (i.VALUE));
			this.pc++;
			break;
		}
		
		case OPCODES.LDCB:
		{
			this.push (this.newBool ((i.VALUE) ? VMCheney.TRUE : VMCheney.FALSE));
			this.pc++;
			break;
		}
		
		// primitive operations:
		// watch out, the non-commutative operations have to consider
		// that the arguments appear on the stack in reverse order!
		
		case OPCODES.PLUS:
		{
			this.push (this.newInt (this.heap[this.pop () + VMCheney.INTVALUE]
						+ this.heap[this.pop () + VMCheney.INTVALUE]));
			this.pc++;
			break;
		}
		
		case OPCODES.TIMES:
		{
			this.push (this.newInt (this.heap[this.pop () + VMCheney.INTVALUE]
			*
			this.heap[this.pop () + VMCheney.INTVALUE]));
			this.pc++;
			break;
		}
		
		case OPCODES.MINUS:
		{
			this.push (this.newInt (- this.heap[this.pop () + VMCheney.INTVALUE]
				+
				this.heap[this.pop () + VMCheney.INTVALUE]));
			this.pc++;
			break;
		}
		
		case OPCODES.DIV:
		{
			var divisor = this.heap[this.pop () + VMCheney.INTVALUE];
			var dividend = this.heap[this.pop () + VMCheney.INTVALUE];
			if (divisor == 0)
			{
				this.push (this.newError());
				return;
			}
			else
			{
				this.push (this.newInt (Math.floor(dividend
					/
					divisor)));
				this.pc++;
				break;
			}
		}
		
		case OPCODES.UMINUS:
		{
			this.push (this.newInt (- this.heap[this.pop () + VMCheney.INTVALUE]));
			this.pc++;
			break;
		}
		
		case OPCODES.OR:
		{
			var i1 = this.heap[this.pop () + VMCheney.BOOLVALUE];
			var i2 = this.heap[this.pop () + VMCheney.BOOLVALUE];
			this.push (this.newBool ((i1==VMCheney.TRUE)
			? VMCheney.TRUE : i2));
			this.pc++;
			break;
		}
		
		case OPCODES.AND:
		{
			var i1 = this.heap[this.pop () + VMCheney.BOOLVALUE];
			var i2 = this.heap[this.pop () + VMCheney.BOOLVALUE];
			this.push (this.newBool ((i1==VMCheney.FALSE)
			? VMCheney.FALSE : i2));
			this.pc++;
			break;
		}
		
		case OPCODES.NOT:
		{
			var i1 = this.heap[this.pop () + VMCheney.BOOLVALUE];
			this.push (this.newBool ((i1==VMCheney.TRUE)
			? VMCheney.FALSE : VMCheney.TRUE));
			this.pc++;
			break;
		}
		
		case OPCODES.GREATER:
		{
			this.push (this.newBool ((this.heap[this.pop () + VMCheney.INTVALUE]
			<
			this.heap[this.pop () + VMCheney.INTVALUE])
			? VMCheney.TRUE : VMCheney.FALSE));
			this.pc++;
			break;
		}
		
		case OPCODES.LESS:
		{
			this.push (this.newBool ((this.heap[this.pop () + VMCheney.INTVALUE]
			>
			this.heap[this.pop () + VMCheney.INTVALUE])
			? VMCheney.TRUE : VMCheney.FALSE));
			this.pc++;
			break;
		}
		
		case OPCODES.EQUAL:
		{
			this.push (this.newBool ((this.heap[this.pop () + VMCheney.INTVALUE]
			==
			this.heap[this.pop () + VMCheney.INTVALUE])
			? VMCheney.TRUE : VMCheney.FALSE));
			this.pc++;
			break;
		}
		
		// jump by setting pc.
		
		case OPCODES.GOTO:
		{
			this.pc = i.ADDRESS;
			break;
		}
		
		case OPCODES.JOF:
		{
			this.pc = ( this.heap[this.pop () + VMCheney.BOOLVALUE] == VMCheney.TRUE
			? this.pc + 1
			: i.ADDRESS );
			break;
		}
		
		// load function by pushing closure.
		// environment in closure has space for arguments.
		// CALL actually fills these new slots.
		
		case OPCODES.LDF:
		{
			this.push (this.newClosure (this.e,
				i.ADDRESS,
				i.MAXSTACKSIZE));
			this.pc++;
			break;
		}
		
		case OPCODES.LDRF:
		{
			var enr = this.extend (this.e, 1);
			
			//$P
			// same trick as in the CALL instruction
			this.rts.push (enr);
			//$-->
			
			var fv = this.newClosure (enr,
				i.ADDRESS,
				i.MAXSTACKSIZE);

			//$P
			enr = this.rts.pop ();
			this.heap[fv + VMCheney.CLOSUREENVIRONMENT] = enr;
			//$-->

			this.heap[enr + 1 + this.heap[enr + VMCheney.ENVIRONMENTSIZE]] = fv;
			this.push (fv);
			this.pc++;
			break;
		}
		
		// CALL finds a closure on top of the stack.
		// the closure environment is filled up with
		// actual parameters that are popped from the stack.
		// the registers are saved in stack frame and
		// the stack frame pushed on runtime stack.
		// new registers are initialized in the obvious way.
		
		case OPCODES.CALL:
		{
			var n = i.NUMBEROFARGUMENTS;
			var closure = this.heap[this.heap[this.os + VMCheney.OPERANDSTACKTOPOFSTACK] - n];
			
			var bodyEnv = this.extend (this.heap[closure + VMCheney.CLOSUREENVIRONMENT], n);

			//$P
			if (this.heap[closure] == TAGS.COPIED) closure = this.heap[closure + VMCheney.FORWARDING_ADDRESS];
			//$-->
			
			var s = this.heap[bodyEnv + VMCheney.ENVIRONMENTSIZE];
			var k = s - n;
			var j = s - 1;
			while (j >= k)
				this.heap[bodyEnv + VMCheney.ENVIRONMENTFIRSTENTRY + j--] = this.pop ();
			this.pop ();

			// this is a walk-around
			// because the newly created environment bodyEnv
			// is not linked from any roots
			// so when the memory is flipped during the creation
			// of the new stack frame
			// the bodyEnv will still be left in the old memory space
			// this trick puts the bodyEnv temporarily in the runtime stack
			// so that it will be copied when the memory is flipped
			// this is one of the 2 walk-around methods
			// another method is do as normal, and manually copy the
			// bodyEnv over when we see that the memory has been flipped
			// but this required recursive copying, which i do not like
			// since recursion poses the threat of stack overflow
			this.rts.push (bodyEnv);

			var stackFrame = this.newStackFrame (this.pc + 1, this.e, this.os);

			bodyEnv = this.rts.pop ();

			this.rts.push (stackFrame);
			
			//$P
			if (this.heap[closure] == TAGS.COPIED) closure = this.heap[closure + VMCheney.FORWARDING_ADDRESS];
			//$-->
			
			this.pc = this.heap[closure + VMCheney.CLOSUREADDRESS];
			this.e = bodyEnv;
			this.os = this.newOperandStack (this.heap[closure + VMCheney.CLOSURESTACKSIZE]);
			
			break;
		}
		
		// TAILCALL: no need to create new environment
		// no need to push stack frame
		
		case OPCODES.TAILCALL:
		{
			var n = i.NUMBEROFARGUMENTS;
			var closure = this.heap[this.heap[this.os + VMCheney.OPERANDSTACKTOPOFSTACK] - n];
			var s = this.heap[this.e + VMCheney.ENVIRONMENTSIZE];
			var k = s - n;
			var j = s - 1;
			while (j >= k)
				this.heap[this.e + VMCheney.ENVIRONMENTFIRSTENTRY + j--] = this.pop ();
			this.pop ();
			this.pc = this.heap[closure + VMCheney.CLOSUREADDRESS];
			break;
		}
		
		// address for LD is calculated by compiler and
		// put in the INDEX field of the instruction.
		// LD only needs to push the environment value under INDEX
		
		case OPCODES.LD:
		{
			this.push (this.heap[this.e + VMCheney.ENVIRONMENTFIRSTENTRY + i.INDEX]);
			this.pc++;
			break;
		}
		
		// RTN reinstalls the top frame of the runtime stack,
		// and pushes the return value on the operand stack.
		
		case OPCODES.RTN:
		{
			var f = this.rts.pop ();
			this.pc = this.heap[f + VMCheney.STACKFRAMEPROGRAMCOUNTER];
			this.e = this.heap[f + VMCheney.STACKFRAMEENVIRONMENT];
			var returnValue = this.pop ();
			this.os = this.heap[f + VMCheney.STACKFRAMEOPERANDSTACK];
			this.push (returnValue);
			break;
		}
		
		case OPCODES.DONE:
		{
			return true;
		}
		
		default:
		{
			trace (" unknown opcode: " + i.OPCODE + " at pc=" + this.pc + ": " + i);
			this.pc++;
			break;
		}
	}
	
	return false;
};

VMCheney.prototype.newNode = function (nodeSize)
{
	// if run out of memory
	// try to do garbage collecting
	if (this.hp + nodeSize > this.topOfSpace)
	{
		this.flip ();
	}
	
	// after garbage collecting
	// still don't have enough memory
	// then just quit
	
	if (this.hp + nodeSize > this.topOfSpace)
	{
		trace (this.hp + " " + nodeSize + " " + this.topOfSpace);
		trace ("Out of memory");
	}

	var newNode = this.hp;
	this.hp += nodeSize;
	return newNode;

};

VMCheney.prototype.flip = function ()
{
	if (chkShowCheneyAlgo.getValue ())
	{
		mirror.initialize (vmcheney);
		flipping = true;
	}

	// first copy the roots
	// roots are:
	//	+ stack frames
	//	+ current operand stack
	//	+ current environment
	this.hp = this.toSpace;

	// copy the stack frame
	var runtimeStackSize = this.rts.size();
	for (var i = 0;i < runtimeStackSize;++i)
	{
		this.rts.setElementAt (i, this.copy (this.rts.elementAt (i)));
	}
	// copy the current operand stack and environment
	if (this.os >= 0) this.os = this.copy (this.os);
	this.e = this.copy (this.e);

	var scan = this.toSpace;
	while (scan < this.hp)
	{
		switch (this.heap[scan])
		{
			case TAGS.CLOSURE:
			{
				this.heap[scan + VMCheney.CLOSUREENVIRONMENT] = this.copy (this.heap[scan + VMCheney.CLOSUREENVIRONMENT]);
				break;
			}

			case TAGS.STACKFRAME:
			{
				this.heap[scan + VMCheney.STACKFRAMEENVIRONMENT] =
					this.copy (this.heap[scan + VMCheney.STACKFRAMEENVIRONMENT]);
				this.heap[scan + VMCheney.STACKFRAMEOPERANDSTACK] = 
					this.copy (this.heap[scan + VMCheney.STACKFRAMEOPERANDSTACK]);
				break;
			}
			
			case TAGS.OPERANDSTACK:
			{
				for (var i = scan + 3;i <= this.heap[scan + VMCheney.OPERANDSTACKTOPOFSTACK];++i)
				{
					this.heap[i] = this.copy (this.heap[i]);
				}
				break;
			}

			case TAGS.ENVIRONMENT:
			{
				for (var i = 0;i < this.heap[scan + VMCheney.ENVIRONMENTSIZE];++i)
				{
					this.heap[scan + VMCheney.ENVIRONMENTFIRSTENTRY + i] =
						this.copy (this.heap[scan + VMCheney.ENVIRONMENTFIRSTENTRY + i]);
				}
				break;
			}

			case TAGS.INT:
			case TAGS.BOOL:
			case TAGS.ERROR:
				break;

		} // switch

		scan += this.nodeSize (scan);
	}

	// switch the roles of from-space and to-space
	var temp = this.fromSpace;
	this.fromSpace = this.toSpace;
	this.toSpace = temp;
	this.topOfSpace = this.fromSpace + VMCheney.SPACE_SIZE;
	
	// display
	if (!chkShowCheneyAlgo.getValue ())
	{
		for (var i = this.hp;i < this.topOfSpace;++i)
		{
			this.clear (i);
		}
		for (var i = this.toSpace;i < this.toSpace + VMCheney.SPACE_SIZE;++i)
		{
			if (this.heapSlot[i].getAlpha() == 100) this.heapSlot[i].setColor (0xC0C0C0);
		}
	}
	
}; // method flip

VMCheney.prototype.FORWARDING_ADDRESS = 1;

VMCheney.prototype.copy = function (node)
{
	if (this.alreadyCopied (node))
		return this.heap[node + VMCheney.FORWARDING_ADDRESS];

	// not yet copied
	// then copy it
	var newNode = this.hp;
	
	var nodeSize = this.nodeSize (node);
	
	// Move
	for (var i = 0;i < nodeSize;++i) 
	{
		this.heap[newNode + i] = this.heap[node + i];		
	}

	// take care of the case of operand stack
	// have to adjust the top-of-stack pointer
	// because the top-of-stack pointer is the absolute address
	// not the relative address in the heap
	if (this.heap[node] == TAGS.OPERANDSTACK)
	{
		this.heap[newNode + VMCheney.OPERANDSTACKTOPOFSTACK] =
			this.heap[node + VMCheney.OPERANDSTACKTOPOFSTACK] - node + newNode;
	}
	
	// update the heap pointer
	this.hp += nodeSize;

	// set the forwarding address
	this.heap[node + VMCheney.FORWARDING_ADDRESS] = newNode;
	this.heap[node] = TAGS.COPIED;
	
	return newNode;

};

VMCheney.prototype.alreadyCopied = function (node)
{
	return (this.heap[node] == TAGS.COPIED);
};

VMCheney.prototype.nodeSize = function (node)
{
	if (this.heap[node] == TAGS.INT) return 2;
	if (this.heap[node] == TAGS.BOOL) return 2;
	if (this.heap[node] == TAGS.ENVIRONMENT) return this.heap[node + VMCheney.ENVIRONMENTSIZE] + 2;
	if (this.heap[node] == TAGS.CLOSURE) return 4;
	if (this.heap[node] == TAGS.STACKFRAME) return 4;
	if (this.heap[node] == TAGS.OPERANDSTACK) return this.heap[node + VMCheney.OPERANDSTACKSIZE] + 3;
	if (this.heap[node] == TAGS.ERROR) return 2;

	// safe guard
	trace ("Unknown node: " + node + " " + this.heap[node]);
	return 1;
};

VMCheney.prototype.getColor = function (node)
{
	switch (this.heap[node])
	{
		case TAGS.INT:
			ccolor = 0x0000ff; break;
		case TAGS.BOOL:
			ccolor = 0x00ff00; break;
		case TAGS.ENVIRONMENT:
			ccolor = 0xff0000; break;
		case TAGS.CLOSURE:
			ccolor = 0xffff00; break;
		case TAGS.STACKFRAME:
			ccolor = 0xff00ff; break;
		case TAGS.OPERANDSTACK:
			ccolor = 0x00ffff; break;
		case TAGS.ERROR:
			ccolor = 0x000000; break;
		default:
			ccolor = 0xffffff; break;
	}
	return ccolor;
};

VMCheney.prototype.update = function (node)
{
	if (flipping) return;

	var ccolor = this.getColor (node);
	var nodeSize = this.nodeSize (node);
	
	for (var i = 0;i < nodeSize;++i)
	{
		this.heapSlot[node + i].setColor (ccolor);
		this.heapSlot[node + i].setAlpha (100);
	}
		
	return node;
};

VMCheney.prototype.clear = function (node)
{
	this.heapSlot[node].setColor (0xffffff);
	this.heapSlot[node].setAlpha (100);
		
	return node;
};

VMCheney.prototype.blur = function (node)
{
	var nodeSize = this.nodeSize (node);
	for (var i = 0;i < nodeSize;++i)
	{
		this.heapSlot[node + i].setAlpha (30);
	}
};