|
// 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 |
|
] |