字数
1885 字
阅读时间
12 分钟
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];贡献者
jiechen