bytecode.ts

type If = {
  kind: 'if'
  condition: Expression
  then: Expression
  else: Expression
}

type Literal = {
  kind: 'boolean'
  value: boolean
}

type Not = {
  kind: 'not'
  operand: Expression
}

type And = {
  kind: 'and'
  operands: Expression[]
}

type Or = {
  kind: 'or'
  operands: Expression[]
}

type Xor = {
  kind: 'xor'
  operands: Expression[]
}

type Output = {
  kind: 'output'
  text: string
}

type Expression = Literal | If | Not | And | Or | Xor | Output


enum Instruction {
  False,
  True,
  Over,
  Rotate,
  Jump,
  JumpWhenFalse,
  Not,
  And,
  Or,
  Output,
}

type Bytecode = (Instruction | number & {})[];
function compile(expression: Expression): Bytecode {
  switch(expression.kind) {
    case "if":
      const Condition = compile(expression.condition);
      const Then = compile(expression.then);
      const Else = compile(expression.else);
      const Break = [Instruction.Jump, Else.length];
      const If = [Instruction.JumpWhenFalse, Then.length + Break.length];
      return Condition.concat(If, Then, Break, Else);
    case "not": return compile(expression.operand).concat([Instruction.Not])
    case "and": return [Instruction.True].concat(expression.operands.map(compile).flatMap((b) => [...b, Instruction.And]));
    case "or": return [Instruction.False].concat(expression.operands.map(compile).flatMap((b) => [...b, Instruction.Or]));   
    case "xor": return [Instruction.False].concat(expression.operands.map(compile).flatMap((b) => [...b, Instruction.Over, 1, Instruction.Over, 1, Instruction.Not, Instruction.And, Instruction.Rotate, 2, Instruction.Rotate, 1, Instruction.Not, Instruction.And, Instruction.Or]))
    case "boolean": return expression.value ? [Instruction.True] : [Instruction.False];
    case "output": return [Instruction.Output, expression.text as never];
  }
  // @ts-expect-error
  throw new Error("unreachable");
}

function print(bytecode: Bytecode) {
  const result: string[] = [];
  for(let i = 0; i < bytecode.length; i++) {
    const instruction = bytecode[i];
    switch(instruction) {
      case Instruction.Over:
      case Instruction.Rotate:
      case Instruction.Jump:
      case Instruction.JumpWhenFalse:
      case Instruction.Output:
        result.push(Instruction[instruction] + "(" + bytecode[++i] + ")");
        break;
      default:
        result.push(Instruction[instruction]);
    }
  }
  return result;
}

function Throw(message: string): never {
  throw new Error(message);
}

function interpret(bytecode: Bytecode, stack: (Instruction.True | Instruction.False)[]) {
  var a: typeof stack[number];
  var b: typeof stack[number];
  var d: number;
  for(let i = 0; i < bytecode.length; i++) {
    const instruction = bytecode[i];
    switch(instruction) {
      case Instruction.False:
        stack.push(Instruction.False);
        break;
      case Instruction.True:
        stack.push(Instruction.True);
        break;
      case Instruction.Over:
        d = bytecode[++i];
        stack.push(stack[stack.length - 1 - d]);
        break;
      case Instruction.Rotate:
        d = bytecode[++i] + 1;
        var start = stack.length - d;
        stack.splice(start, d, stack[start + d - 1], ...stack.slice(start, start + d - 1));
        break;
      case Instruction.Jump:
        d = bytecode[++i];
        i += d;
        break;
      case Instruction.JumpWhenFalse:
        d = bytecode[++i];
        a = stack.pop() ?? Throw("stack was empty");
        if(!a) i += d;
        break;
      case Instruction.Not:
        a = stack.pop() ?? Throw("stack was empty")
        stack.push(a ? Instruction.False : Instruction.True);
        break;
      case Instruction.And:
        a = stack.pop() ?? Throw("stack was empty");
        b = stack.pop() ?? Throw("stack was empty");
        stack.push(a && b ? Instruction.True : Instruction.False);
        break;
      case Instruction.Or:
        a = stack.pop() ?? Throw("stack was empty");
        b = stack.pop() ?? Throw("stack was empty");
        stack.push(a || b ? Instruction.True : Instruction.False);
        break;
      case Instruction.Output:
        console.log(bytecode[++i]);
        break;
    }
    //console.log(`${Instruction[instruction]} -->`, print(stack));
  }
}

const code = compile({ 
  kind: "if",
  condition: { kind: "xor", operands: [
    { kind: "boolean", value: true },
    { kind: "boolean", value: true },
    { kind: "boolean", value: true },
  ] },
  then: { kind: "output", text: "resolved true!" },
  else: { kind: "output", text: "invalid solution" }
});
//console.log(code, print(code))
interpret(code, []);