28 the virtual machine

28.js

// Basic instructions
const NOP = 0;
const MOVE = 5;
const MOVE_2_1 = 6;
const STORE_TO_M0 = 10;
const STORE_TO_M1 = 11;
const STORE_TO_C1 = 12;
const SET_MC1_ROOT = 15;
const SET_C1_ROOT = 16;
const RESOLVE = 20;
const JUMP_P = 50; // P = iP
const JUMP_C = 51; // C = Code
const JUMP_HOC = 52; // HOC = Head Of Code
const SET_TO_CODE = 99;
const ADD_MC1 = 100;
const ADD_M1 = 101;
const ADD_1 = 102;
const SUB_1 = 107;
const NOT = 109;
const EQ_M1 = 110;
const EQ_MC1 = 111;
const EQ_C1 = 112;
const NEQ_M1 = 115;
const IF_JUMP_P = 120;
const IF_JUMP_C = 121;
const ALLOC = 160;
const STOP = 255;

class Context {
  constructor(code) {
    this.code = code;
    this.ip = 0;
    this.current = l(); // TODO
    this.memory = this.current;
  }

  step() {
    const inst = this.code[this.ip];
    if (Array.isArray(inst)) // ... or implicit jump?
      throw new Error("Array is not valid instruction");
    if (typeof inst === "function") {
      inst(this);
      return;
    }
    switch (inst) {
    case NOP: // nop
      this.ip += 1;
      break;
    case MOVE: // move
      {
        const value = resolve(this.code[this.ip + 1], this.memory);
        set(this.code[this.ip + 2], this.memory, value);
        this.ip += 3;
      }
      break;
    case MOVE_2_1:
      {
        const addr = resolve(this.code[this.ip + 1], this.memory);
        const value = resolve(addr, this.memory);
        set(this.code[this.ip + 2], this.memory, value);
        this.ip += 3;
      }
      break;
    case STORE_TO_M0: // store to m[0]
      {
        set(0, this.memory, this.code[this.ip + 1]);
        this.ip += 2;
      }
      break;
    case STORE_TO_M1: // store to m[1]
      {
        set(1, this.memory, this.code[this.ip + 1]);
        this.ip += 2;
      }
      break;
    case STORE_TO_C1: // store to any addr
      {
        set(this.code[this.ip + 1], this.memory, this.code[this.ip + 2]);
        this.ip += 3;
      }
      break;
    case SET_MC1_ROOT: // set m[c[ip+1]] to root
      this.memory = resolve(this.code[this.ip + 1], this.memory);
      this.ip += 2;
      break;
    case SET_C1_ROOT: // set c[ip+1] to root
      this.memory = this.code[this.ip += 1];
      this.ip += 2;
      break;
    case RESOLVE: // resolve
      this.memory[0] = resolve(this.memory[0], this.memory);
      this.ip += 1;
      break;
    case JUMP_P: // jump in local
      this.ip = this.code[this.ip + 1];
      break;
    case JUMP_C: // jump to code
      this.code = this.code[this.ip + 1];
      this.ip = 0;
      break;
    case JUMP_HOC: // jump to local head
      this.ip = 0;
      break;
    case SET_TO_CODE: // set to code (Warning!)
      this.code = resolve(this.code[this.ip + 1], this.memory);
      this.ip = 0;
      break;
    case ADD_MC1: // add any addr
      {
        const x = resolve(this.memory, this.code[this.ip + 1]);
        this.memory[0] = (this.memory[0] + x) % 256;
        //this.memory[1] = +(this.memory[0] < x);
        this.ip += 2;
      }
      break;
    case ADD_M1: // add m[1]
      {
        const x = this.memory[1];
        this.memory[0] = (this.memory[0] + x) % 256;
        //this.memory[1] = +(this.memory[0] < x);
        this.ip += 1;
      }
      break;
    case ADD_1: // add 1
      {
        this.memory[0] = (this.memory[0] + 1) % 256;
        //this.memory[1] = +(this.memory[0] < 1);
        this.ip += 1;
      }
      break;
    case SUB_1: // sub 1
      {
        this.memory[0] = (this.memory[0] + 255) % 256;
        this.ip += 1;
      }
      break;
    case NOT: // not
      this.memory[0] = +!this.memory[0];
      this.ip += 1;
      break;
    case EQ_M1: // eq
      this.memory[0] = +(this.memory[0] === this.memory[1]);
      this.ip += 1;
      break;
    case EQ_MC1: // eq any addr
      {
        const value = resolve(this.code[this.ip + 1], this.memory);
        this.memory[0] = +(this.memory[0] === value);
        this.ip += 2;
      }
      break;
    case EQ_C1: // eq c[ip+1]
      this.memory[0] = +(this.memory[0] === this.code[this.ip + 1]);
      this.ip += 2;
      break;
    case NEQ_M1: // neq
      this.memory[0] = +(this.memory[0] !== this.memory[1]);
      this.ip += 1;
      break;
    case IF_JUMP_P: // if not zero then jump in local
      if (this.memory[0]) {
        this.ip = this.code[this.ip + 1];
      } else {
        this.ip += 2;
      }
      break;
    case IF_JUMP_C: // if not zero then jump to any code
      if (this.memory[0]) {
        this.code = this.code[this.ip + 1];
        this.ip = 0;
      } else {
        this.ip += 2;
      }
      break;
    case ALLOC: // new list to m[0]
      this.memory[0] = l();
      this.ip += 1;
      break;
    case STOP: // stop ?
      this.stop = true;
      this.ip += 1; // ?
      break;
    default:
      throw new Error(`Invalid instruction: ${inst}`);
    }
  }

  print() {
    console.log("c: " + print(this.code));
    console.log("p: " + print(this.ip));
    console.log("m: " + print(this.memory));
  }
}

function resolve(addr, memory) {
  if (!Array.isArray(addr))
    return memory[addr];
  for (let i of addr) {
    if (!i) break;
    if (Array.isArray(i))
      throw new Error('Bad address');
    if (!Array.isArray(memory))
      throw new Error('Resolve failed');
    memory = memory[i];
  }
  return memory;
}

function set(addr, memory, value) {
  if (!Array.isArray(addr))
    return memory[addr] = value;
  let prev = null;
  let idx = 0;
  for (let i of addr) {
    if (!i) break;
    if (Array.isArray(i))
      throw new Error('Bad address');
    if (!Array.isArray(memory))
      throw new Error('Resolve failed');
    prev = memory;
    idx = i;
    memory = memory[i];
  }
  prev[idx] = value;
}

function l(...xs) {
  return [...xs, ...Array(256 - xs.length).fill(0)];
}

function print(d) {
  const arrays = [];
  const circle = [];
  function mark(d) {
    if (!Array.isArray(d)) return;
    const i = arrays.indexOf(d);
    if (i === -1) {
      arrays.push(d);
      circle.push(0);
      d.forEach(mark);
    } else {
      circle[i] = 1;
    }
  };
  mark(d);
  function stringify(d) {
    if (Array.isArray(d)) {
      const i = arrays.indexOf(d);
      if (circle[i] === 2)
        return `#${i}`;
      circle[i] *= 2;
      let l = 0;
      for (let j in d)
        if (d[j]) l = +j + 1;
      return (circle[i] ? `#${i}=` : '') + '[' + d.slice(0, l).map(stringify).join(',') + (l === 256 ? "" : ",") + ']';
    } else if (typeof d === "function") {
      return "#f:" + d.name;
    } else {
      return d.toString();
    }
  }
  return stringify(d);
}

 // functions as instruction (impure feature!)

function debug(ctx) {
  console.log('== debug print ==');
  ctx.print();
  ctx.ip += 1;
}

function prn(mes) {
  return function prn(ctx) {
    ctx.ip += 1;
    console.log(mes);
  };
}

const ctx = new Context(
  l(
    STORE_TO_M0, 250,
    STORE_TO_C1, 1, 124,
    ADD_1,
    debug,
    IF_JUMP_P, 5,
    prn("end!")
  )
);


// 実行！
console.log("== initial context ==");
ctx.print();
for (let i = 0; i < 100; ++i) {
  ctx.step();
}

/*
console.log('===');
const d = l(0, l(1, 1));
console.log(print(d));
set(l(1, 1), d, 3);
console.log(print(d));
*/