Incremental reverse computation

comp.ts

export {}

// pull-bashed output-directed (incremental)
interface Var {
  lastVal?: number;
  inputs(): Var[];
}

class Input implements Var {
  lastVal?: number;
  val?: number;
  set(x: number) {
    this.lastVal = this.val;
    this.val = x;
  }
  inputs(): Var[] {
    return [];
  }
}

class SingleInputCmp implements Var {
  lastVal?: number;
  constructor(readonly cmp: (x: number) => number,
              readonly input: Var) {}
  inputs(): Var[] {
    return [this.input];
  }
}

class DoubleInputCmp implements Var {
  lastVal?: number;
  constructor(readonly cmp: (x: number, y: number) => number,
              readonly input1: Var, readonly input2: Var) {}
  inputs(): Var[] {
    return [this.input1, this.input2];
  }
}

function nextAncestor(s: Var): Var {
  if (s instanceof SingleInputCmp) return nextAncestor(s.input);
  return s;
}

class Exec {
  skip = new Map<Var, Var|null>();
  vars: Var[] = [];

  assign(v: Var, next: Var|null) {
    this.skip.set(v, next);
    if (v instanceof DoubleInputCmp) {
      const ins = v.inputs();
      for (let i = 0; i < ins.length; i++) {
        if (i == ins.length - 1) {
          this.assign(ins[i], v);
        } else {
          this.assign(ins[i], nextAncestor(ins[i + 1]));
        }
      }
    } else {
      for (const input of v.inputs()) {
        this.assign(input, next);
      }
    }
    this.vars.push(v);
  }

  constructor(private readonly start: Var) {
    this.assign(start, null);
  }

  exec() {
    for (let i = 0; i < this.vars.length; ) {
      const v = this.vars[i];
      let newVal: number = 0;
      if (v instanceof Input) {
        newVal = v.val!;
      }
      if (v instanceof SingleInputCmp) {
        newVal = v.cmp(v.input.lastVal!);
      }
      if (v instanceof DoubleInputCmp) {
        newVal = v.cmp(v.input1.lastVal!, v.input2.lastVal!);
      }
      if (v.lastVal === newVal) {
        i = this.skipAhead(v, i);
      } else {
        v.lastVal = newVal;
        i += 1;
      }
    }
    return this.start.lastVal;
  }

  skipAhead(v: Var, i: number) {
    while (this.vars[i] != this.skip.get(v) && i < this.vars.length) i++;
    return i;
  }
}


const x = new Input();
const y = new Input();
const op1 = new SingleInputCmp(square, x);
const op2 = new SingleInputCmp(square, y);
const op3 = new DoubleInputCmp(add, op1, op2);
const op4 = new SingleInputCmp(Math.sqrt, op3);

function square(x: number) {
  return x * x;
}

function add(x: number, y: number) {
  return x + y;
}

console.log('comp');
// computation
x.set(1);
y.set(2);
const e = new Exec(op4);
console.log(e.exec());

console.log('recomp');
// re-computation
y.set(3);
console.log(e.exec());