Stack-based code execution

c go java js lua py vbs rkt scm pro

A stack is a list in which the following operations are available.

push or append an element on the stack
pop or remove an element off the stack
empty returns true if the stack is empty
top returns the top element (if not empty, otherwise null)

Note: Each programming language has one or more ways to accomplish these operations.

A stack-based code (is a simple code execution model that) executes by traversing through the code and executing each element of the code using the stack.

Let us use our running logical expression example.

( X & Y ) | ( ( ! X ) & ( ! Y ) )

Note that in a postfix representation, the operator is traversed last. And, in evaluation, both operands are needed before the operator can be applied. So, by an induction argument, a postfix representation can be used as a stack-based code to determine the value of an expression, given the values of the logical variables.

A simple variable environment (without scope) can be implemented using a dictionary.

Suppose that x has the value 0 and that y has the value 1.

Here is a dictionary that could express this idea.

Here is the postfix representation.

x y & x ! y ! & |

Here is a list that can represent the code.

codeList1 = [ ["var", "x"], ["var", "y"], ["op2", "and"], ["var", "x"], ["op1", "not"], ["var", "y"], ["op1", "not"], ["op2", "and"], ["op2", "or"], ]

The environment of the logical variables can be represented as a dictionary. Here is an example for x with the value of 0 and y with the value of 1.

varDict1 = { "x" : 0, "y" : 1, }

An induction argument considers the various cases of the tree.

a leaf node: variable or integer
a binary operator interior node
a unary operator interior node

Each type of node leaves one value on the stack. When a submode is called, it leaves one item on the stack. One item for unary operators. Two items for binary operators. Here is a code example, with print statements interspersed to trace what is happening.

Here is the JavaScript code.

var codeList1 = [
	["var", "x"],
	["var", "y"],
	["op2", "and"],
	["var", "x"],
	["op1", "not"],
	["var", "y"],
	["op1", "not"],
	["op2", "and"],
	["op2", "or"]
	];
var opDict2 = {
	"and" : "&",
	"or" : "|",
	"eqv" : "=",
	"xor" : "^",
	"not" : "!",
	"nand" : "!&"
	};
function execute(codeList1,varDict1) {
	var n1 = codeList1.length;
	console.log("init stack to empty\n");
	var stack1 = [];
	var value1 = 0;
	for (var i1=0; i1 < n1; i1++) {
		var code1 = codeList1[i1];
		var type1 = code1[0];
		if (type1 == "var") {
			var name1 = code1[1];
			value1 = varDict1[name1];
			console.log(name1+"\n");
			console.log("\tpush "+name1+" as "+value1+"\n");
			}
		else if (type1 == "int") {
			value1 = code1[1];
			console.log(value1+"\n");
			console.log("\tpush "+value1+"\n");
			}
		else if (type1 == "op1") {
			var op1 = code1[1];
			var op3 = opDict2[op2];
			var y1 = stack1.pop();
			console.log(op3+"\n");
			console.log("\tpop "+y1+" as reg2\n");
			if (op1 == "not") {
				value1 = 1 - y1;
				}
			console.log("\tpush 1-reg2 as "+value1+"\n");
			}
		else if (type1 == "op2") {
			var op2 = code1[1];
			var op3 = opDict2[op2];
			var y1 = stack1.pop();
			var x1 = stack1.pop();
			console.log(op3+"\n");
			console.log("\tpop "+y1+" as reg2\n");
			console.log("\tpop "+x1+" as reg1\n");
			if (op2 == "and") {
				value1 = x1 * y1;
				console.log("\tpush reg1*reg2 as "+value1+"\n");
				}
			else if (op2 == "or") {
				console.log("\tpush reg1+reg2-reg1*reg2 as "+value1+"\n");
				value1 = x1 + y1 - x1*y1;
				}
			else if (op2 == "xor") {
				console.log("\tpush (reg1+reg2)%2 as "+value1+"\n");
				value1 = (x1 + y1) % 2;
				}
			else if (op2 == "eqv") {
				console.log("\tpush (reg1+reg2+1)%2 as "+value1+"\n");
				value1 = (x1 + y1 + 1) % 2;
				}
			}
		stack1.push(value1);
		}
	value1 = stack1[0];
	console.log("pop "+value1+" as result\n");
	return value1;
	}

console.log("(begin code execution)\n");
varDict1 = {};
for (x1=0; x1<=1; x1++) {
	for (y1=0; y1<=1; y1++) {
		console.log("\n");
		console.log("let x="+x1+" and y="+y1+"\n");
		varDict1["x"] = x1;
		varDict1["y"] = y1;
		var z1 = execute(codeList1,varDict1);
		console.log("then z="+z1+"\n");
		}
	}
console.log("\n");
console.log("(end code execution)\n");

Here is the output of the JavaScript code.

(begin code execution)



let x=0 and y=0

init stack to empty

x

	push x as 0

y

	push y as 0

&

	pop 0 as reg2

	pop 0 as reg1

	push reg1*reg2 as 0

x

	push x as 0

&

	pop 0 as reg2

	push 1-reg2 as 1

y

	push y as 0

&

	pop 0 as reg2

	push 1-reg2 as 1

&

	pop 1 as reg2

	pop 1 as reg1

	push reg1*reg2 as 1

|

	pop 1 as reg2

	pop 0 as reg1

	push reg1+reg2-reg1*reg2 as 1

pop 1 as result

then z=1



let x=0 and y=1

init stack to empty

x

	push x as 0

y

	push y as 1

&

	pop 1 as reg2

	pop 0 as reg1

	push reg1*reg2 as 0

x

	push x as 0

&

	pop 0 as reg2

	push 1-reg2 as 1

y

	push y as 1

&

	pop 1 as reg2

	push 1-reg2 as 0

&

	pop 0 as reg2

	pop 1 as reg1

	push reg1*reg2 as 0

|

	pop 0 as reg2

	pop 0 as reg1

	push reg1+reg2-reg1*reg2 as 0

pop 0 as result

then z=0



let x=1 and y=0

init stack to empty

x

	push x as 1

y

	push y as 0

&

	pop 0 as reg2

	pop 1 as reg1

	push reg1*reg2 as 0

x

	push x as 1

&

	pop 1 as reg2

	push 1-reg2 as 0

y

	push y as 0

&

	pop 0 as reg2

	push 1-reg2 as 1

&

	pop 1 as reg2

	pop 0 as reg1

	push reg1*reg2 as 0

|

	pop 0 as reg2

	pop 0 as reg1

	push reg1+reg2-reg1*reg2 as 0

pop 0 as result

then z=0



let x=1 and y=1

init stack to empty

x

	push x as 1

y

	push y as 1

&

	pop 1 as reg2

	pop 1 as reg1

	push reg1*reg2 as 1

x

	push x as 1

&

	pop 1 as reg2

	push 1-reg2 as 0

y

	push y as 1

&

	pop 1 as reg2

	push 1-reg2 as 0

&

	pop 0 as reg2

	pop 0 as reg1

	push reg1*reg2 as 0

|

	pop 0 as reg2

	pop 1 as reg1

	push reg1+reg2-reg1*reg2 as 0

pop 1 as result

then z=1



(end code execution)

Note: How might we dynamically determine the values for the logical variables given a variable number of variables?