Brainfuck Interpreter with the TypeScript Compiler.md

Brainfuck Interpreter in the TypeScript Compiler

This is a brainfuck interpreter written using the new template string literals upcoming in TypeScript 4.1.

Since brainfuck is turing complete, this means that the TS type system is also turing complete, although the compiler does impose stringent limits on how many types you can instantiate at once. As such, these brainfuck programs have to be kept short and sweet.

Play around with it yourself

Features

• Generic type Brainfuck<Code, [Input], [Memory]> evaluates to a string literal type with the printed output of your program.
• Supports all brainfuck operations (,.+-<>[]).
• Uses a stack (with underflow protection!) to track loops.
• Supports memory values from 0 to 255. Integer overflows will wrap around.
• Can read and print ASCII characters from 0 to 127, with safe handling of out-of-bounds output or unparseable input.
  • Out-of-bounds output characters are replaced with ?, and invalid input (as well as the end of input) is read as 0.
• Comments are fully supported. Any unrecognized characters will be skipped by the parser.
• Basic debugging: a ! character will stop execution and return the state of execution at that point.

Limitations

• TypeScript limits how far you can recurse when instantiating types. Even relatively small programs like the hello world on Wikipedia are too complex for the compiler.
• Memory is limited to 256 bytes in length. This is only because pointer traversal (<>) is implemented using the same logic as regular math (+-), and thus shares the same bounds of 0-255.

brainfuck.d.ts

// Examples
type Multiply2And6 = Brainfuck<"+ ++[>++++++<-]>."> // "\u0012"
type Echo = Brainfuck<",[.,]", "Hello"> // "Hello"
type Reverse = Brainfuck<",[>,]<[.<]", "dog"> // "god"

// Breakpoints ("!") stop execution and return a tuple of [<remaining code>, <unused input>, <printed output>, <pointer location>, <stack>, <memory dump>]
type Breakpoint = Brainfuck<",[.>,]!", "Hello"> // ["", "", "Hello", 5, undefined, [72, 101, 108, 108, 111, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... 215 more ..., 0]]
type Stack = Brainfuck<"+[-[] oh comments work too btw +[!-]]"> // ["-]]", "", "", 0, Push<Push<undefined, "-[] oh comments work too btw +[!-]]">, "!-]]">, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... 235 more ..., 0]]


    /////////////////////////////
   // Brainfuck in TypeScript //
  /////////////////////////////


// Main wrapper type, accepts a parameter for the code, as well as optional parameters to provide input and pre-fill memory (memory must be 256 bytes long).
export type Brainfuck<Code extends string, Input extends string = "", Memory extends number[] = DefaultMemory> =
  string extends Code ? "Error: Code must be a string literal" :
  string extends Input ? "Error: Input must be a string literal" :
  Memory[0] extends undefined ? "Error: Must have at least one byte of memory" :
  number extends Memory["length"] ? "Error: Memory must be a tuple with a fixed size, not an array" :
  Memory["length"] extends 256 ?
  {[K in Exclude<keyof DefaultMemory, keyof number[]> as DefaultMemory[K] extends Increment<number> ? never : "error"]: "error"} extends {"error": "error"} ? "Error: Memory value out of bounds" :
  BF<Code, Input, "", Memory, 0, undefined> :
  "Error: Memory must have a length of 256"

// Internal implementation
type BF<Code extends string, Input extends string, Output extends string, Memory extends number[], Pointer extends number, Stack extends StackType> = Code extends "" ? Output :
  // Custom breakpoint/debug command
  Code extends `!${infer Code}` ?
    [Code, Input, Output, Pointer, Stack, Memory] :

  // Note: "pointee" refers to the memory value that the pointer is referencing (Memory[Pointer]).
  // Increment and decrement the pointee. Values outside of 0-255 will wrap around.
  Code extends `+${infer Code}` ?
    BF<Code, Input, Output, {
      [K in keyof Memory]: K extends `${Pointer}` ? Increment<Memory[K] & number> : Memory[K]
    }, Pointer, Stack> :
  Code extends `-${infer Code}` ?
    BF<Code, Input, Output, {
      [K in keyof Memory]: K extends `${Pointer}` ? Decrement<Memory[K] & number> : Memory[K]
    }, Pointer, Stack> :

  // Increment/decrement the pointer. Addresses outside of 0-255 will wrap around.
  // I could modify this to support greater than 256 bytes of memory, but TS won't let you do anything very complicated anyway.
  Code extends `>${infer Code}` ?
    BF<Code, Input, Output, Memory, Increment<Pointer>, Stack> :
  Code extends `<${infer Code}` ?
    BF<Code, Input, Output, Memory, Decrement<Pointer>, Stack> :

  // Output a byte to the screen as an ASCII character.
  Code extends `.${infer Code}` ?
    BF<Code, Input, `${Output}${ToASCII<Memory[Pointer]>}`, Memory, Pointer, Stack> :
  // Read a byte from the input string.
  Code extends `,${infer Code}` ?
    BF<Code, StripFirstCharacter<Input>, Output, {
      [K in keyof Memory]: K extends `${Pointer}` ? FromASCII<Input> : Memory[K]
    }, Pointer, Stack> :

  // Note: "pointee" refers to the memory value that the pointer is referencing (Memory[Pointer]).
  // If the pointee not 0, push the code to the stack and keep running as normal. If it's zero, we need to scan ahead to find the closing bracket and skip past it.
  Code extends `[${infer Code}` ?
    BF<Memory[Pointer] extends 0 ? FindEndingBracket<Code> : Code, Input, Output, Memory, Pointer, Memory[Pointer] extends 0 ? Stack : Push<Stack, Code>> :
  // If the pointee is 0, pop the stack to exit the loop and keep going. If it's not zero, replace the code with the stack value to return execution to the opening brace.
  Code extends `]${infer Code}` ?
    Stack extends undefined ? "Error: Stack underflow" : BF<Memory[Pointer] extends 0 ? Code : Peek<Stack>, Input, Output, Memory, Pointer, Memory[Pointer] extends 0 ? Pop<Stack> : Stack> :

  // We don't recognize this character, so let's skip it and move on.
  BF<StripFirstCharacter<Code>, Input, Output, Memory, Pointer, Stack>

// Searches the string to find the closing brace. Uses a "Tracker" stack to keep track of how far nested we are.
type FindEndingBracket<Code extends string, Tracker extends StackType = Push<undefined, "">> = 
  // End of the string, no point in looking further.
  "" extends Code ? Code :
  // "Tracker extends undefined" indicates that the stack is empty and we've already found the closing brace.
  Tracker extends undefined ? Code :
    Code extends `[${infer Code}` ?
      // Push to the stack to count the extra opening brace.
      FindEndingBracket<Code, Push<Tracker, "">> :
    Code extends `]${infer Code}` ?
      // Pop the stack to decrement the "counter".
      FindEndingBracket<Code, Pop<Tracker>> :

      // Skip other characters.
      FindEndingBracket<StripFirstCharacter<Code>, Tracker>

// Types for converting between numeric literal types and ASCII characters. Only supports character codes 0-127.
// Unknown codes are replaced with ?'s when converting to characters, and zeros when converting to bytes.
type ASCII = ["\x00", "\x01", "\x02", "\x03", "\x04", "\x05", "\x06", "\x07", "\x08", "\x09", "\x0a", "\x0b", "\x0c", "\x0d", "\x0e", "\x0f", "\x10", "\x11", "\x12", "\x13", "\x14", "\x15", "\x16", "\x17", "\x18", "\x19", "\x1a", "\x1b", "\x1c", "\x1d", "\x1e", "\x1f", "\x20", "\x21", "\x22", "\x23", "\x24", "\x25", "\x26", "\x27", "\x28", "\x29", "\x2a", "\x2b", "\x2c", "\x2d", "\x2e", "\x2f", "\x30", "\x31", "\x32", "\x33", "\x34", "\x35", "\x36", "\x37", "\x38", "\x39", "\x3a", "\x3b", "\x3c", "\x3d", "\x3e", "\x3f", "\x40", "\x41", "\x42", "\x43", "\x44", "\x45", "\x46", "\x47", "\x48", "\x49", "\x4a", "\x4b", "\x4c", "\x4d", "\x4e", "\x4f", "\x50", "\x51", "\x52", "\x53", "\x54", "\x55", "\x56", "\x57", "\x58", "\x59", "\x5a", "\x5b", "\x5c", "\x5d", "\x5e", "\x5f", "\x60", "\x61", "\x62", "\x63", "\x64", "\x65", "\x66", "\x67", "\x68", "\x69", "\x6a", "\x6b", "\x6c", "\x6d", "\x6e", "\x6f", "\x70", "\x71", "\x72", "\x73", "\x74", "\x75", "\x76", "\x77", "\x78", "\x79", "\x7a", "\x7b", "\x7c", "\x7d", "\x7e", "\x7f"]
type ToASCII<Character extends number> = ASCII[Character] extends infer C ? C extends string ? C : "?" : "?"
type FromASCII<Input extends string> = {[K in Exclude<keyof ASCII & keyof Numbers, keyof string[]> as ASCII[K]]: K} extends infer Table ? FirstCharacter<Input> extends keyof Table ? Table[FirstCharacter<Input>] extends infer N ? N extends keyof Numbers ? Numbers[N] : 0 : 0 : 0 : 0
// TS converts numeric keys to strings, so this hack is needed to get our numeric literal back.
type Numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127]

// Stack of strings implementation using recursive tuples. `undefined` indicates the bottom of the stack.
type StackType = undefined | [string, StackType]
type Peek<Stack extends StackType> = Stack extends [infer Value, any] ? Value : ""
type Pop<Stack extends StackType> = Stack extends [any, infer Stack] ? Stack : Stack
type Push<Stack extends StackType, Value extends string> = [Value, Stack]

type FirstCharacter<Literal extends string> = Literal extends `${infer A}${infer B}` ? A : "\0"
type StripFirstCharacter<Literal extends string> = Literal extends `${infer A}${infer B}` ? B : ""

type Increment<N extends number> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 0][N]
type Decrement<N extends number> = [255, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254][N]

type DefaultMemory = [
  0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0
]