Emulating a 4-Bit Virtual Machine in (TypeScript\JavaScript) (just Types no Script)

README.md

A compile-time 4-Bit Virtual Machine implemented in TypeScript's type system. Capable of running a sample 'FizzBuzz' program.

Syntax emits zero JavaScript.

type RESULT = VM<
  [
    ["push", N_1],         // 1
    ["push", False],       // 2
    ["peek", _],           // 3
    ["mod", N_3],          // 4
    ["ifNZero", Line<8>],  // 5
    ["replace", True],     // 6
    ["print", "fizz"],     // 7
    ["peek", _],           // 8
    ["mod", N_5],          // 9
    ["ifNZero", Line<13>], // 10
    ["replace", True],     // 11
    ["print", "buzz"],     // 12
    ["ifNZero", Line<15>], // 13
    ["printHead", _],      // 14
    ["eq", N_15],          // 15
    ["ifNZero", Line<19>], // 16
    ["inc", _],            // 17
    ["jump", Line<2>],     // 18
    ["pop", _],            // 19
    ["stop", _]            // 20
  ]
>;
// RESULT['stdOut'] ==
// [1, 2, "fizz", 4, "buzz", "fizz", 7, 8, "fizz", "buzz", 11, "fizz", 13, 14, "fizz", "buzz"];

Demo

Inspired by

• TypeScripts Type System is Turing Complete
• How to master advanced TypeScript patterns

Notes:

• requires Typescript v3.3.3 - v3.6.3
• requires "strict": true in tsconfig.json

bytecode-reference.txt

int i = 1;
while (true) {
    boolean b = false;
    if (i % 3 == 0) {
        b = true;
        print("fizz");
    }
    if (i % 5 == 0) {
        b = true;
        print("buzz");
    }
    if (!b) {
        print(i);
    }
    if (b == 15) {
        break;
    }
    i = i + 1;
}

        push (1)       [i=1]
@start [i]
        push (0)       [i, false]
        peek           [i, false, i]
        imod (3)       [i, false, rem]
        ifNZero (@5)   [i, false]
        replace (1)    [i, true]
        print ('fizz') [i, true]
@5: [i, b]
        peek           [i, b, i]
        imod (5)       [i, b, rem]
        ifNZero (@num) [i, b]
        replace (1)    [i, true]
        print ('buzz') [i, true]
@num: [i, b]
        ifNZero (@inc) [i]
        printHead      [i]
@inc: [i]
        eq (15)        [i, i==15]
        ifNZero (@end) [i]
        inc            [i++]
        jump (@start)  [i]
@end: [i]
        pop            []
        stop

tsconfig.json

{
  "files": ["vm.ts"],
  "compilerOptions": {
    "strict": true,
    "removeComments": true,
    "alwaysStrict": false
  }
}

vm.ts

type No_Arg = any;
type _ = "";
type Instruction_Address = any[]; // use array['length'] to index into Program's instructions
type B = 1 | 0;
type BITS_4 = [B, B, B, B];
type Num = BITS_4;

type Instructions =
  | ["push", Num]                    // [h, ...t]     ->  [arg, h, ...t]
  | ["pop", No_Arg]                  // [h, ...t]     ->  [...t]
  | ["dup", No_Arg]                  // [h, ...t]     ->  [h, h, ...t]
  | ["peek", No_Arg]                 // [h, hh, ...t] ->  [hh, h, hh, ...t]
  | ["replace", Num]                 // [h, ...t]     ->  [arg, ...t]
  | ["inc", No_Arg]                  // [h, ...t]     ->  [++h, ...t]
  | ["mod", Num]                     // [h, ...t]     ->  [h % arg, ...t]
  | ["eq", Num]                      // [h, ...t]     ->  [h == arg, h, ...t]
  | ["jump", Instruction_Address]    // jump program to instruction at arg
  | ["ifNZero", Instruction_Address] // pop head, if != 0 jump program to instruction at arg
  | ["printHead", No_Arg]            // copy head, covert to string then add to stdout
  | ["print", string]                // add arg to stdout
  | ["stop", No_Arg];                // halt! returns contents of stdout


// Test the machine with a sample program
// (hover mouse over RESULT to see type) 

type RESULT = VM<
  [
    ["push", N_1],         // 1
    ["push", False],       // 2
    ["peek", _],           // 3
    ["mod", N_3],          // 4
    ["ifNZero", Line<8>],  // 5
    ["replace", True],     // 6
    ["print", "fizz"],     // 7
    ["peek", _],           // 8
    ["mod", N_5],          // 9
    ["ifNZero", Line<13>], // 10
    ["replace", True],     // 11
    ["print", "buzz"],     // 12
    ["ifNZero", Line<15>], // 13
    ["printHead", _],      // 14
    ["eq", N_15],          // 15
    ["ifNZero", Line<19>], // 16
    ["inc", _],            // 17
    ["jump", Line<2>],     // 18
    ["pop", _],            // 19
    ["stop", _]            // 20
  ]
>;
// Expected output:
// [1, 2, "fizz", 4, "buzz", "fizz", 7, 8, "fizz", "buzz", 11, "fizz", 13, 14, "fizz", "buzz"];


/**
 * This is the main entry point to run the Virtual Machine
 * @param Program - The array of instructions to execute
 * @returns { stdOut: string[] }
 */
type VM<
  Program extends Instructions[],
  /* variables: */
  Result extends any = InnerVM<Program>
> = {
  // Use a trampoline to extend TypeScript's Type Instantiation depth limit of 50
  1: VM<Program, InnerVM<Program, [], Result>>;
  0: Result["state"];
}[Result["tag"] extends "bounce" ? 1 : 0];

type InnerVM<
  Program extends Instructions[],
  Bounces extends any[] = [],
  Result extends any = Tick<Program>
> = {
  // Use two trampolines to further increase limit...
  1: InnerVM<Program, Prepend<any, Bounces>,
       Tick<Result["state"][0], Result["state"][1], Result["state"][2], Result["state"][3]>
     >;
  0: Result;
}[Result["tag"] extends "bounce" 
  ? (Bounces['length'] extends 5
    ? 0
    : 1)
  : 0];

// Execute the next instruction
type Tick<
  Program extends Instructions[],
  PC extends any[] = [], // program-counter - length of array indexes into Instructions
  Stack extends Num[] = [],
  StdOut extends string[] = []
> = {
  // Define all the VM instructions
  'push': Tick<Program, Prepend<any, PC>, Prepend<Program[PC["length"]][1], Stack>, StdOut>;
  'pop': Tick<Program, Prepend<any, PC>, Tail<Stack>, StdOut>;
  'dup': Tick<Program, Prepend<any, PC>, Prepend<Head<Stack>, Stack>, StdOut>;
  'peek': Tick<Program, Prepend<any, PC>, Prepend<Head<Tail<Stack>>, Stack>, StdOut>;
  'replace': Tick<Program, Prepend<any, PC>, Prepend<Program[PC["length"]][1], Tail<Stack>>, StdOut>;
  'inc': Tick<Program, Prepend<any, PC>, Prepend<ADD_4<Head<Stack>, N_1>, Tail<Stack>>, StdOut>;
  // @ts-ignore - convince TypeScript that division is not infinite
  'mod': Tick<Program, Prepend<any, PC>, Prepend<MOD_4<Head<Stack>, Program[PC["length"]][1]>, Tail<Stack>>, StdOut>;
  'eq': Tick<Program, Prepend<any, PC>, Prepend<EQ_4<Head<Stack>, Program[PC["length"]][1]>, Stack>, StdOut>;
  // 'jump' seems as good a natural time to bounce on the trampoline
  'jump': { tag: "bounce"; state: [Program, Program[PC["length"]][1], Stack, StdOut] };
  'ifNZero': Head<Stack> extends N_0
    ? Tick<Program, Prepend<any, PC>, Tail<Stack>, StdOut>
    : Tick<Program, Program[PC["length"]][1], Tail<Stack>, StdOut>;
  'printHead': Tick<Program, Prepend<any, PC>, Stack, Prepend<N_ToString<Head<Stack>>, StdOut>>;
  'print': Tick<Program, Prepend<any, PC>, Stack, Prepend<Program[PC["length"]][1], StdOut>>;
  'stop': { tag: "result"; state: { stdOut: Reverse<StdOut> } };
  // Then index into the correct instruction based on the current program-counter (PC)
}[Program[PC["length"]][0]];

// 4-Bit Arithmetic Logic Unit (ALU)
// - handle numbers 0 to 15
// - everything constructed from 1-bit logic gates

type N_0 = [0, 0, 0, 0];
type N_1 = [1, 0, 0, 0];
type N_2 = [0, 1, 0, 0];
type N_3 = [1, 1, 0, 0];
type N_4 = [0, 0, 1, 0];
type N_5 = [1, 0, 1, 0];
type N_6 = [0, 1, 1, 0];
type N_7 = [1, 1, 1, 0];
type N_8 = [0, 0, 0, 1];
type N_9 = [1, 0, 0, 1];
type N_10 = [0, 1, 0, 1];
type N_11 = [1, 1, 0, 1];
type N_12 = [0, 0, 1, 1];
type N_13 = [1, 0, 1, 1];
type N_14 = [0, 1, 1, 1];
type N_15 = [1, 1, 1, 1];
type False = N_0;
type True = N_1;

type MOD_4<
  numerator extends Num,
  divisor extends Num,
  /* variables: */
  result extends any = DIV_4<numerator, divisor>
> = {
  1: result["remainder"];
  0: N_0;
}[result["tag"] extends "result" ? 1 : 0];

type DIV_4<
  numerator extends BITS_4,
  divisor extends BITS_4,
  /* variables: */
  count extends BITS_4 = N_0,
  remainder extends BITS_4 = numerator
> = {
  // remainder < divisor
  1: { tag: "result"; count: count; remainder: remainder };
  // remainder >= divisor
  0: DIV_4<numerator, divisor, ADD_4<count, N_1>, SUB_4<remainder, divisor>>;
}[COMP_4<remainder, divisor>["less"] extends 1 ? 1 : 0];

type MUL_4<
  regA extends BITS_4,
  regB extends BITS_4,
  /* variables: */
  sum0 extends BITS_4 = BITWISE_AND<[regA[0], regA[0], regA[0], regA[0]], regB>,
  sum1 extends BITS_4 = ADD_4<
    [0, AND<regA[1], regB[0]>, AND<regA[1], regB[1]>, AND<regA[1], regB[2]>],
    sum0
  >,
  sum2 extends BITS_4 = ADD_4<
    [0, 0, AND<regA[2], regB[0]>, AND<regA[2], regB[1]>],
    sum1
  >,
  sum3 extends BITS_4 = ADD_4<[0, 0, 0, AND<regA[3], regB[0]>], sum2>
> = sum3;

type SUB_4<
  regA extends BITS_4,
  regB extends BITS_4,
  /* variables: */
  a extends SUBTRACT_RESULT = FULL_SUBTRACTOR<0, regA[0], regB[0]>,
  b extends SUBTRACT_RESULT = FULL_SUBTRACTOR<a["borrow"], regA[1], regB[1]>,
  c extends SUBTRACT_RESULT = FULL_SUBTRACTOR<b["borrow"], regA[2], regB[2]>,
  d extends SUBTRACT_RESULT = FULL_SUBTRACTOR<c["borrow"], regA[3], regB[3]>
> = [a["diff"], b["diff"], c["diff"], d["diff"]];

type ADD_4<
  regA extends BITS_4,
  regB extends BITS_4,
  /* variables: */
  a extends ADDER_RESULT = FULL_ADDER<0, regA[0], regB[0]>,
  b extends ADDER_RESULT = FULL_ADDER<a["carry"], regA[1], regB[1]>,
  c extends ADDER_RESULT = FULL_ADDER<b["carry"], regA[2], regB[2]>,
  d extends ADDER_RESULT = FULL_ADDER<c["carry"], regA[3], regB[3]>
> = [a["sum"], b["sum"], c["sum"], d["sum"]];

type FULL_SUBTRACTOR<
  borrow extends B,
  a extends B,
  b extends B,
  /* variables: */
  subtractor1 extends SUBTRACT_RESULT = HALF_SUBTRACTOR<a, b>,
  subtractor2 extends SUBTRACT_RESULT = HALF_SUBTRACTOR<
    subtractor1["diff"],
    borrow
  >
> = {
  diff: subtractor2["diff"];
  borrow: OR<subtractor1["borrow"], subtractor2["borrow"]>;
};

type FULL_ADDER<
  carry extends B,
  a extends B,
  b extends B,
  /* variables: */
  adder1 extends ADDER_RESULT = HALF_ADDER<a, b>,
  adder2 extends ADDER_RESULT = HALF_ADDER<carry, adder1["sum"]>
> = {
  sum: adder2["sum"];
  carry: OR<adder2["carry"], adder1["carry"]>;
};

type SUBTRACT_RESULT = { diff: B; borrow: B };
type ADDER_RESULT = { sum: B; carry: B };

type HALF_SUBTRACTOR<a extends B, b extends B> = {
  diff: XOR<a, b>;
  borrow: AND<NOT<a>, b>;
};

type HALF_ADDER<a extends B, b extends B> = {
  sum: XOR<a, b>;
  carry: AND<a, b>;
};

type BITWISE_AND<a extends BITS_4, b extends BITS_4> = [
  AND<a[0], b[0]>,
  AND<a[1], b[1]>,
  AND<a[2], b[2]>,
  AND<a[3], b[3]>
];

type COMP_4<
  a extends BITS_4,
  b extends BITS_4,
  /* variables: */
  c0 extends COMP_RESULT = COMP<a[0], b[0]>,
  c1 extends COMP_RESULT = COMP<a[1], b[1]>,
  c2 extends COMP_RESULT = COMP<a[2], b[2]>,
  c3 extends COMP_RESULT = COMP<a[3], b[3]>
> = {
  less: OR_4<
    c3["grt"],
    AND<c3["eq"], c2["grt"]>,
    AND_4<1, c3["eq"], c2["eq"], c1["grt"]>,
    AND_4<c3["eq"], c2["eq"], c1["eq"], c0["grt"]>
  >;
  eq: AND_4<c0["eq"], c1["eq"], c2["eq"], c3["eq"]>;
  grt: OR_4<
    c3["less"],
    AND<c3["eq"], c2["less"]>,
    AND_4<1, c3["eq"], c2["eq"], c1["less"]>,
    AND_4<c3["eq"], c2["eq"], c1["eq"], c0["less"]>
  >;
};

type COMP_RESULT = { less: B; eq: B; grt: B };

type COMP<
  a extends B,
  b extends B,
  /* variables */
  aLessThanB extends B = AND<NOT<b>, a>,
  aGreaterThanB extends B = AND<b, NOT<a>>,
  equal extends B = NOR<aLessThanB, aGreaterThanB>
> = { less: aLessThanB; eq: equal; grt: aGreaterThanB };

type EQ_4<
  a extends BITS_4,
  b extends BITS_4,
  /* variables */
  eq0 extends B = NXOR<a[0], b[0]>,
  eq1 extends B = NXOR<a[1], b[1]>,
  eq2 extends B = NXOR<a[2], b[2]>,
  eq3 extends B = NXOR<a[3], b[3]>,
> = [AND_4<eq0, eq1, eq2, eq3>, 0, 0, 0];

type NXOR<a extends B, b extends B> = {
  1: {
    1: 1;
    0: 0;
  };
  0: {
    1: 0;
    0: 1
  }
}[a][b];

type XOR<a extends B, b extends B> = {
  1: {
    1: 0;
    0: 1;
  };
  0: {
    1: 1;
    0: 0
  }
}[a][b];

type AND_4<a extends B, b extends B, c extends B, d extends B> = AND<
  AND<a, b>,
  AND<c, d>
>;

type AND<a extends B, b extends B> = {
  1: {
    1: 1;
    0: 0;
  };
  0: {
    1: 0;
    0: 0
  }
}[a][b];

type NOR<a extends B, b extends B> = {
  1: {
    1: 0;
    0: 0;
  };
  0: {
    1: 0;
    0: 1;
  }
}[a][b];

type OR_4<a extends B, b extends B, c extends B, d extends B> = OR<
  OR<a, b>,
  OR<c, d>
>;

type OR<a extends B, b extends B> = {
  1: {
    1: 1;
    0: 1;
  };
  0: {
    1: 1;
    0: 0;
  }
}[a][b];

type NOT<a extends B> = {
  1: 0;
  0: 1
}[a];

// Ideally all other gates would be built by composing NANDs,
// however this creates a TypeScript 'possible infinite loop' error
type NAND<a extends B, b extends B> = {
  1: {
    1: 0;
    0: 1;
  };
  0: {
    1: 1;
    0: 1;
  };
}[a][b];

// Utils - because all programs need a 'utils' area

// Covert 4-bit number to a string for printing
type N_ToString<n extends Num>
  = n extends N_0 ? "0"
  : n extends N_1 ? "1"
  : n extends N_2 ? "2"
  : n extends N_3 ? "3"
  : n extends N_4 ? "4"
  : n extends N_5 ? "5"
  : n extends N_6 ? "6"
  : n extends N_7 ? "7"
  : n extends N_8 ? "8"
  : n extends N_9 ? "9"
  : n extends N_10 ? "10"
  : n extends N_11 ? "11"
  : n extends N_12 ? "12"
  : n extends N_13 ? "13"
  : n extends N_14 ? "14"
  : n extends N_15 ? "15"
  : "nan";

/** Given a line number return an Instruction_Address  */
type Line<line extends number, __address extends Instruction_Address = []> = {
  0: Line<line, Prepend<any, __address>>;
  1: Tail<__address>;
}[__address["length"] extends line ? 1 : 0];

// prepend & head & tail & reverse taken from
// https://github.com/pirix-gh/medium/blob/master/types-curry-ramda/src/index.ts

type Prepend<V extends any, Arr extends any[]> = ((
  v: V,
  ...a: Arr
) => any) extends (...a: infer Args) => any
  ? Args
  : [];

type Head<T extends any[]> = T extends [any, ...any[]] ? T[0] : never;

type Tail<T extends any[]> = ((...t: T) => any) extends ((
  _: any,
  ...tail: infer TT
) => any)
  ? TT
  : [];

type Reverse<T extends any[], R extends any[] = [], I extends any[] = []> = {
  0: Reverse<T, Prepend<T[I["length"]], R>, Prepend<any, I>>;
  1: R;
}[I["length"] extends T["length"] ? 1 : 0];

Советую почитать microsoft/TypeScript#14833 там еще много такого. А еще там строго доказано, что система типов TypeScript – Тьюринг полная, что означает, что можно написать любую возможную программу, используя только типы.