vm.js

class Stack {
  constructor() {
    this.items = [];
  }

  // Add an element to the stack
  push(element) {
    this.items.push(element);
  }

  // Remove and return the top element from the stack
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

  // Check if the stack is empty
  isEmpty() {
    return this.items.length === 0;
  }

  // Return the size of the stack
  size() {
    return this.items.length;
  }

  // Empty the stack
  clear() {
    this.items = [];
  }
}

const stack = new Stack();

//

const num = (value) => ({
  type: 'num',
  value
})

const op = (value, ...nodes) => ({
  type: 'op',
  value,
  nodes
})

//

const ast = op('print', op('+', op('+', num(2), num(3)), op('+', num(4), op('+', op('d', num(5)), num(6)))))

function evalSimple(node) {
  if (node.type === 'num') {
    return node.value
  } else if (node.type === 'op') {
    const { value, nodes } = node
    const [a, b] = nodes.map(evalSimple)
    if (value === '+') {
      // TODO recursion depth limit (JS stack)
      return a + b
    } else if (value === 'print') {
      return a
    } else if (value === 'd') {
      const v = a
      console.log('d', v)
      return v
    }
  }
}

function flatAST(node) {
  const p = ({ type, value }) => ({ type, value })
  if (node.type === 'num') {
    return [p(node)];
  } else if (node.type === 'op') {
    return [].concat(node.nodes.flatMap(flatAST), [p(node)])
  }
}

function evalFlatAST(ops) {
  const stack = new Stack()
  for (const { type, value } of ops) {
    if (type === 'num') {
      stack.push(value)
    } else if (type === 'op' && value === '+') {
      stack.push(stack.pop() + stack.pop())
    } else if (type === 'op' && value === 'print') {
      // stack.push(stack.pop())
    } else if (type === 'op' && value === 'd') {
      const v = stack.pop();
      console.log('d:', v)
      stack.push(v)
   }
  }
  return stack.pop()
}


// TODO limit stack size -> implement trampoline trick
function evalStack(stack, ast) {
  if (ast.type === 'num') {
    stack.push(ast.value)
  } else if (ast.type === 'op') {
    for (const node of ast.nodes) {
      evalStack(stack, node)
    }
    if (ast.value === '+') {
      stack.push(stack.pop() + stack.pop())
    }
    if (ast.value === 'print') {
      return stack.pop()
    } else if (ast.value === 'd') {
      const v = stack.pop();
      console.log('d', v);
      stack.push(v)
    }
  }
}

console.log(JSON.stringify(ast, null, 2))
console.log('eval (simple):', evalSimple(ast))

//
console.log('flat:', flatAST(ast))
console.log('eval (flat -> stack):', evalFlatAST(flatAST(ast)))

//
console.log('eval (stack):', evalStack(new Stack(), ast))