enricopolanski/README.md

## README.md

      
    Raw
  

              README.md
            
          
    A 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
Inspried by

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

Notes:

requires Typescript >= v3.3.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];
	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
	{
	"files": ["vm.ts"],
	"compilerOptions": {
	"strict": true,
	"removeComments": true,
	"alwaysStrict": false
	}
	}
	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];