Brainf*ck Implementation on TypeScript Types

bf-in-type.ts

// deno-fmt-ignore
type AsciiTable = { 32: " ", 33: "!", 34: "\"", 35: "#", 36: "$", 37: "%", 38: "&", 39: "'", 40: "(", 41: ")", 42: "*", 43: "+", 44: ",", 45: "-", 46: ".", 47: "/", 48: "0", 49: "1", 50: "2", 51: "3", 52: "4", 53: "5", 54: "6", 55: "7", 56: "8", 57: "9", 58: ":", 59: ";", 60: "<", 61: "=", 62: ">", 63: "?", 64: "@", 65: "A", 66: "B", 67: "C", 68: "D", 69: "E", 70: "F", 71: "G", 72: "H", 73: "I", 74: "J", 75: "K", 76: "L", 77: "M", 78: "N", 79: "O", 80: "P", 81: "Q", 82: "R", 83: "S", 84: "T", 85: "U", 86: "V", 87: "W", 88: "X", 89: "Y", 90: "Z", 91: "[", 92: "\\", 93: "]", 94: "^", 95: "_", 96: "`", 97: "a", 98: "b", 99: "c", 100: "d", 101: "e", 102: "f", 103: "g", 104: "h", 105: "i", 106: "j", 107: "k", 108: "l", 109: "m", 110: "n", 111: "o", 112: "p", 113: "q", 114: "r", 115: "s", 116: "t", 117: "u", 118: "v", 119: "w", 120: "x", 121: "y", 122: "z", 123: "{", 124: "|", 125: "}" 126: "~" }
type Decoded<T extends number[]> = T extends [infer V, ...infer A] ? A extends number[] ? (V extends keyof AsciiTable ? `${AsciiTable[V]}${Decoded<A>}` : `?${Decoded<A>}`) : never : '';

type Length<T extends unknown[]> = T extends { length: infer N } ? N extends number ? N : never
  : never;
type AtoN<Arr extends unknown[]> = Length<Arr>;
type NtoA<Num extends number, Arr extends unknown[] = []> = Length<Arr> extends Num ? Arr
  : NtoA<Num, [...Arr, unknown]>;

type Add<N extends number, M extends number> = AtoN<[...NtoA<N>, ...NtoA<M>]>;
type Sub<N extends number, M extends number> = NtoA<N> extends [...NtoA<M>, ...infer A] ? AtoN<A> : never;

type Tail<Arr extends unknown[]> = Arr extends [infer _, ...infer A] ? A : never;
type TakeN<Arr extends unknown[], N extends number> = Arr extends [...infer A, ...NtoA<Sub<Length<Arr>, N>>] ? A
  : never;
type DropN<Arr extends unknown[], N extends number> = Arr extends [...NtoA<N>, ...infer A] ? A
  : never;
type ZeroArr<N extends number, Arr extends 0[] = []> = Length<Arr> extends N ? Arr : ZeroArr<N, [...Arr, 0]>;

type MemWrite<Mem extends number[], Ind extends number, Val extends number> = [
  ...TakeN<Mem, Ind>,
  Val,
  ...DropN<Mem, Add<Ind, 1>>,
];

type JumpForward<Prg extends Operation[], PC extends number, Depth extends number = 0> = PC extends never ? never
  : PC extends Length<Prg> ? never
  : Prg[PC] extends "]" ? (Depth extends 1 ? PC : JumpForward<Prg, Add<PC, 1>, Sub<Depth, 1>>)
  : Prg[PC] extends "[" ? JumpForward<Prg, Add<PC, 1>, Add<Depth, 1>>
  : JumpForward<Prg, Add<PC, 1>, Depth>;

type JumpBackwards<Prg extends Operation[], PC extends number, Depth extends number = 0> = PC extends never ? never
  : Prg[PC] extends "[" ? (Depth extends 1 ? PC : JumpBackwards<Prg, Sub<PC, 1>, Sub<Depth, 1>>)
  : Prg[PC] extends "]" ? JumpBackwards<Prg, Sub<PC, 1>, Add<Depth, 1>>
  : JumpBackwards<Prg, Sub<PC, 1>, Depth>;

type Operation = "+" | "-" | ">" | "<" | "." | "," | "[" | "]";
type Lex<Str extends string> = Str extends `${infer R}${infer S}` ? (R extends Operation ? [R, ...Lex<S>] : Lex<S>)
  : [];
type Evaluate<
  Prg extends Operation[],
  PC extends number,
  Mem extends number[],
  Ptr extends number,
  Out extends number[],
  In extends number[],
> = PC extends Length<Prg> ? Out
  : Prg[PC] extends "+" ? Evaluate<Prg, Add<PC, 1>, MemWrite<Mem, Ptr, Add<Mem[Ptr], 1>>, Ptr, Out, In>
  : Prg[PC] extends "-" ? Evaluate<Prg, Add<PC, 1>, MemWrite<Mem, Ptr, Sub<Mem[Ptr], 1>>, Ptr, Out, In>
  : Prg[PC] extends ">" ? Evaluate<Prg, Add<PC, 1>, Mem, Add<Ptr, 1>, Out, In>
  : Prg[PC] extends "<" ? Evaluate<Prg, Add<PC, 1>, Mem, Sub<Ptr, 1>, Out, In>
  : Prg[PC] extends "." ? Evaluate<Prg, Add<PC, 1>, Mem, Ptr, [...Out, Mem[Ptr]], In>
  : Prg[PC] extends "," ? Evaluate<Prg, Add<PC, 1>, MemWrite<Mem, Ptr, In[0]>, Ptr, Out, Tail<In>>
  : Prg[PC] extends "[" ? (Mem[Ptr] extends 0 ? Evaluate<Prg, Add<JumpForward<Prg, PC>, 1>, Mem, Ptr, Out, In>
      : Evaluate<Prg, Add<PC, 1>, Mem, Ptr, Out, In>)
  : Prg[PC] extends "]" ? (Mem[Ptr] extends 0 ? Evaluate<Prg, Add<PC, 1>, Mem, Ptr, Out, In>
      : Evaluate<Prg, Add<JumpBackwards<Prg, PC>, 1>, Mem, Ptr, Out, In>)
  : never;
type Executed<Prg extends string, Input extends number[] = []> = Decoded<Evaluate<Lex<Prg>, 0, ZeroArr<10>, 0, [], Input>>;

// Prints input binary number as string with format `=${num}`
export type Result = Executed<"++++++[>++++++++++<-]>+.,<++++++[>++++++++<-]>.", [3]>;