Stack Based Machine, Mastering the Stack Data Structure with a real world example

Posted on:February 22, 2024 at 10:00 AM

The stack is the hello world of data structures.

An entire computation process can be built around a stack.

for example Webassembly(wasm) is a stack based virtual machine,

here is a simple wasm program in WAT(webassembly text) format, to add two numbers:

(func (param $p i32)
  (result i32)
  local.get $p
  local.get $p
  i32.add)

local.get pushes the values of variable $p into the stack.

i32.add performs two actions:

Don’t worry if you don’t understand what’s going on, we will cover WAT in the future,

The stack is usually taught in a vanilla approach:

function Stack(type) {
  this.stack = [];

  this.push = val => {
    if (typeof val !== type) throw new Error(`only ${type} supported`);
  };

  this.pop = () => {
    if (stack.length !== 0) return this.stack.pop();
  };
}

const stack = new Stack("number");

in this tutorial we will master the stack by builing a real world example : a stack based arithmetic machine.

Table of contents

Open Table of contents

From the beginning

The plates analogy is a common way to define a stack, where we are only allowed to take the top plate at a time,

In this stack of plates to add(push) and take(pop) a plate, we can only do it from the top.

This is known as a LIFO(last in first out) data structure, the last element to get in, is the first one out.

Stack of plates is a fine analogy, but a bolted down vertical cylinder-esk hard pipe is more like it, the only way to access it is the top, no other way

In JavaScript we can represent this with an array, which already supports push and pop.

// watered down vanilla stack
function Stack(type) {
  this.stack = [];

  this.push = val => {
    if (typeof val !== type) throw new Error(`only ${type} supported`);
  };

  this.pop = () => {
    if (stack.length !== 0) return this.stack.pop();
  };
}

const stack = new Stack("number");
stack.push(1);
console.log(stack.pop()); // 1

We can add more features to make it as close to a virtual machine stack as possible, for example adding the stack pointer(SP), size - memory size to prevent stack overflow.

Here is the new version below:

/**
 *
 * @param {Number} Memsize - memory chunk to allocate the stack
 * @param {string} type - data type allowed on the stack e.g number, string, object
 */
function Stack(Memsize, type) {
  this.stackPointer = 0;
  this.stack = [];

  this.push = val => {
    if (this.stackPointer == Memsize) {
      console.log(this.stackPointer, Memsize);

      throw new Error(`stack overflow`);
    }

    if (typeof val !== type) {
      throw new Error(`only ${type} allowed on the stack`);
    }

    this.stack[this.stackPointer] = val;
    this.stackPointer += 1;
  };

  this.pop = () => {
    if (this.stackPointer == 0) {
      return undefined;
    }
    this.stackPointer -= 1;
    return this.stack.pop();
  };
}

a stack pointer is a value pointing to the next empty space in the stack, on pop we decrease the SP and in push increase the SP

besides the error checks, this new stack uses the SP to add a new element, and we update it to point to the next memory space:

this.stack[this.stackPointer] = val;
this.stackPointer += 1;

we do the opposite with pop:

this.stackPointer -= 1;
return this.stack.pop();

Testing the stack:

const stack = new Stack(5, "number");

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6); // will cause an error(stack overflow)

console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop()); // error, no more value

Let’s add simple helper functions in the stack, simple checks:

function Stack(Memsize, type) {
  this.stackPointer = 0;
  this.stack = [];

  //....

  this.isFull = () => Memsize == this.stackPointer;

  this.hasValues = () => this.stackPointer != 0;

  this.stackLen = () => this.stackPointer;
}

These helpers, will be helpful for the Arithmetic Machine.

Stack Based Arithmetic Machine

We have covered the stack implementation above, and we are familiar with basic arithmetic:

add, multiply, divide and sub.

We are going to combine the two and build a virtual machine, that can perform arithmetic, a Stack Arithmetic Machine,

we already have a stack, we will transpose it to a arithmetic vm:

const ariStack = new Stack(256, "number");

const ari = new arithmeticStackMachine(ariStack);

Implementing the arithmetic stack machine

The function below is the entire stub for our machine, implementation below it:

function arithmeticStackMachine(stack) {
  const quickCheck = op => {};

  this.add = () => {};

  this.sub = () => {};

  this.mult = () => {};

  this.div = () => {};
}

The quickCheck will make sure we are not operating on a empty stack, invalid variables and so on.

In basic arithmetic we need two values(operands) to perfom an arithmetic operation(op), the function below checks for that:

const quickCheck = op => {
  console.log("operation: ", op);
  if (!stack.hasValues() | (stack.stackLen() == 1))
    throw new Error(
      "stack is empty or not nough values; can't perform operation"
    );
};

From the introduction WAT example, i am sure you can already tell, for all op’s we need to pop the values from the stack,

operate on them and push back the results, this idea powers stack based arithmetic,

I will dump all four ops code below, they will all make sense when we start playing with the arithmetic examples

function arithmeticStackMachine(stack) {
  this.add = () => {
    quickCheck("add");
    const op1 = stack.pop();
    const op2 = stack.pop();
    const res = op1 + op2;
    stack.push(res);
  };

  this.sub = () => {
    quickCheck("sub");
    const op1 = stack.pop();
    const op2 = stack.pop();
    // flipped operand position matter, in FIFO would work
    const res = op2 - op1;
    stack.push(res);
  };

  this.mult = () => {
    quickCheck("mult");
    const op1 = stack.pop();
    const op2 = stack.pop();
    const res = op1 * op2;
    stack.push(res);
  };

  this.div = () => {
    quickCheck("divide");
    const op1 = stack.pop();
    const op2 = stack.pop();
    const res = op2 / op1;
    stack.push(res);
  };
}

The reason I chose to write the operation code imperatively is to stay true to how instructions, are processed and executed in actual machines:

// imperative
quickCheck("add");
const op1 = stack.pop();
const op2 = stack.pop();
const res = op1 + op2;
stack.push(res);

we can do a short-hand there’s no harm

quickCheck("add");
stack.push(stack.pop() + stack.pop());

believe it or not, the stack arithmetic machine is functional, let’s test with a few examples

Stack Based Arithmetic Math

Let’s compute a few calculations

remember to create our Arithmetic Stack Machine:

const ariStack = new Stack(256, "number");

const ari = new arithmeticStackMachine(ariStack);

let’s start with a basic 1 + 1 * 2 - 1

console.log("computing-> 1 + 1 * 2 - 1");
ariStack.push(1);
ariStack.push(1);
ari.add();

ariStack.push(2);
ari.mult();

ariStack.push(1);
ari.sub();

console.log(ariStack.pop(), "result:  (1 + 1) * 2 - 1");
console.log("");

On a whim or common knowledge : 1 + 1 * 2 - 1 = 2, as multiply comes first, but our machine will get 3,

Remember the stack machine can perfom a single operation at a time, imperatively

Therefore it computes from left to right, like reading, so the developer is responible for building a logical expression

for example if we wanted the answer 2, we will structure it like this: 1 * 2 + 1 -1 = 2

Last example to drive the idea home : 400 _ 20 - 300 / 2 - 46 / 7 _ 6

// 400 * 20 - 300 / 2 - 46 / 7 * 6
console.log("computing-> 400 * 20 - 300 / 2 - 46 / 7 * 6");
ariStack.push(400);
ariStack.push(20);
ari.mult();
ariStack.push(300);
ari.sub();
ariStack.push(2);
ari.div();
ariStack.push(46);
ari.sub();
ariStack.push(7);
ari.div();
ariStack.push(6);
ari.mult();
console.log(
  ariStack.pop(),
  "result: (((((400 * 20) - 300) / 2) - 46) / 7) * 6"
);

on a normal calculation 400 * 20 - 300 / 2 - 46 / 7 * 6 = 7810.571428571428

but now we know how the stack processes: (((((400 * 20) - 300) / 2) - 46) / 7) * 6, left to right equaling 3260.5714285714284

Conclusion

The stack is a simple idea, but can abstract to powerful ideas, an entire computer(vm) can be built around the stack, accompanied by other structures such a heap,

Some graph algorithms use the stack to optimize search.

In this article we covered briefly what a stack is, and built on top that idea and abstracted a stack based arithmetic machine out of it, we could take it further

However we will see a more realistic use of the stack soon when we cover webassembly.

On that note, thank you for reading! I hope you enjoyed the article.

If you found this article useful, please share it, or tweet at/dm me that helps a lot and directs the content I will put out in the future.

Looking for more content?, here are my favourite so far: