Funciton/Brainfuckiton
Jump to navigation
Jump to search
╔╤═══╤═╤════════════════════════════════════════════════════════════════════════════╤═╤═══╤╗
║│ + ├─┘ └─┤ , │║
║├─┬─┘ ╥─╖ ╥──╖ ╓──╖ ╥ ╥╖ ╥ ╥── ╥ ╥ ╓── ╥ ╓ ┬ ┌─┬─┐ ┌──┐ ┬┐ ┬ └─┬─┤║
║├─┤ ╟─╨╖ ╟─╥╜ ╟──╢ ║ ║╙╖║ ╟─ ║ ║ ║ ╟─╥╜ │ │ │ │ │└┐│ ├─┤║
║├─┴─┐ ╨──╜ ╨ ╙─ ╨ ╨ ╨ ╨ ╙╜ ╨ ╙──╜ ╙── ╨ ╙─ ┴ ┴ └──┘ ┴ └┘ ┌─┴─┤║
║│ . ├─┐ ┌─┤ - │║
║└──┬┴─┴┬──────────────────────────────────────────────────────────────────────────┬┴─┴┬──┘║
╟───┤ < │ B R A I N F U C K I N T E R P R E T E R I N F U N C I T O N │ > ├───╢
║ [ ├───┴──────────┬─────────────────────────────────┬─────────────────────────────┴───┤ ] ║
╟───┘ USAGE │ FEATURES │ LIMITATIONS └───╢
║ ────────────── │ ───────────────────────────── │ ───────────────────────────────── ║
║ │ │ ║
║ The input is │ ► Supports infinite tape in │ ► Infinite loop if the input ║
║ expected to be │ both directions. │ does not contain '\r' or '\n'. ║
║ a space- │ ► Each cell is an arbitrary- │ ► Undefined behaviour if the ║
║ separated list │ size signed integer. │ square brackets in the program ║
║ of integers, │ ► Inputs can be arbitrary- │ don’t match up. ║
║ followed by │ size signed integers. │ ► A double-space in the list of ║
║ either a │ ► Negative numbers can start │ integers is interpreted as an ║
║ CR ('\r') or a │ with '−' (minus, U+2212) │ extra zero. ║
║ LF ('\n'), │ or '-' (hyphen, U+002D). │ ► Undefined behaviour if the BF ║
║ followed by │ ► All non-BF characters in │ program outputs a number that ║
║ the brainfuck │ the program are ignored. │ is not a valid Unicode ║
║ program. │ │ codepoint. ║
║ │ │ ║
╚══════════════════╧═════════════════════════════════╧═════════════════════════════════════╝
╔═══════════════════════════════════════════════════════════════════╗
║ BRAINFUCKiton (main program) ║
╟───────────────────────────────────────────────────────────────────╢
║ BF(s) = let (p, i) = BF↕(s, 1); ║
║ BF◊(›(›(›(›(BF■(›(p, 0), 0, BF0(p)), i), p), ℓ(p)), 0), 0, 0) ║
╟───────────────────────────────────────────────────────────────────╢
║ Exercise to the reader: Why are we passing 1 into BF↕? ║
╚═══════════════════════════════════════════════════════════════════╝
┌───────────────────────────────┐
│ ╔═══╗ ╔═══╗ │ ╓┬────╖
│ ║ 1 ║ ║ ║ │ ┌──╫┘ ›! ╟──┐
│ ╚═╤═╝ ╚═╤═╝ │ │ ╙─────╜ │
│ ┌──┴──╖ │ │ │ ┌───╖ │
├────────────────┤ BF↕ ╟───┘ │ └───┤ › ╟───┘
│ ╔═══╗ ╘══╤══╝ ┌──┴──╖ ╘═╤═╝
│ ┌───╢ 0 ╟─────┐ │ │ BF0 ║ │
│ │ ╚═╤═╝ │ │ ╘══╤══╝
│ │ ┌──┴──╖ ┌─┴─╖ │ ┌───╖ ┌──┴──╖ ╔═══╗
│ └──┤ BF◊ ╟──┤ › ║ └─┤ › ╟──┤ BF■ ╟──╢ 0 ║
│ ╘══╤══╝ ╘═╤═╝ ╘═╤═╝ ╘══╤══╝ ╚═╤═╝
│ ┌───╖ ┌─┴──╖ ┌─┴──╖ │ │
│ ┌───┤ ℓ ╟──┤ ›! ╟──┤ ›! ║ │ │
└──┤ ╘═══╝ ╘════╝ ╘═╤══╝ ┌─┴─╖ │
│ └──┬──┤ › ╟─────┘
└───────────────────────┘ ╘═══╝
╔═════════════════════════════════════════════════════════════════════════════════════════════════════════╗
║ MAIN BRAINFUCK INTERPRETER FUNCTION ║
╟───────────────────────────────────────────────────┬─────────────────────────────────────────────────────╢
║ BF◊(z, l, r) = │ a = length of the program ║
║ let (d, y) = ‹(z); │ b = value of cell left of current cell ║
║ let (a, x) = ‹(y); │ c = value of current cell ║
║ let (p, w) = ‹(x); │ d = current position in program ║
║ let (i, t) = ‹(w); │ e = current position in program plus one ║
║ let (c, q) = ‹;(r); │ f = position in program after current instruction ║
║ let n = (p >> (21 × d)) & ¬(−1 << 21); │ g = next input value to be read ║
║ let (g, h) = ‹;(i); │ h = input list with one value removed ║
║ let j = n = ',' ? h : i; │ i = input list (input to the BF program) ║
║ let (b, k) = ‹;(l); │ j = input list after current instruction ║
║ let u = ɛ(t, d); │ k = left tape with first cell removed ║
║ let e = ♯(d); │ l = left tape ║
║ let v = n = '>'; │ m = left tape after current instruction ║
║ let w = n = '<'; │ n = current instruction ║
║ let m = v ? ›(l, c) : │ o = output generated by rest of the program ║
║ w ? k : l; │ p = program ║
║ let s = v ? q : │ q = right tape (not including current cell) ║
║ w ? ›(r, b) : │ r = right tape (including current cell) ║
║ n = '+' ? ›(q, ♯(c)) : │ s = right tape after current instruction ║
║ n = '-' ? ›(q, ᴥ(c)) : │ t = jump table (for square brackets) ║
║ n = ',' ? ›(q, g) : r; │ u = program position to jump to ║
║ let f = n = '[' ? c ? e : u : │ v = current instruction is '>' ║
║ n = ']' ? c ? u : e : e; │ w = current instruction is '<' ║
║ let o = BF◊(›(›(›(›(t, j), p), a), f), m, s); │ x = temporary variable for unsquishing data ║
║ d = a ? −1 : │ y = temporary variable for unsquishing data ║
║ n = '.' ? c | (o << 21) : o │ z = squished data (everything but the tape) ║
╚═══════════════════════════════════════════════════╧═════════════════════════════════════════════════════╝
╓┬────╖
┌─────────────────────────────────────────────────╫┘BF◊ ╟┐
┌─┴─╖ ╙──┬──╜│
┌─────────────────────────────────────────────────────────────────────┤ · ╟───────────┐ │ │
│ ╘═╤═╝ │ │ │
┌─┴─╖ ┌─┴─╖ ┌─┴─╖ │ │
┌──┤ · ╟───────────────────────────────────────────────────────────────────┤ · ╟──────┬──┤ · ╟─────────────────────────────────┐ │ │
│ ╘═╤═╝ ╘═╤═╝ │ ╘═╤═╝ │ │ │
│ │ ┌─┴─╖ │ │ │ │ │
│ │ ┌────┤ ‹ ╟──────┘ │ │ │ │
│ │ ┌─┴─╖ ╘═══╝ ┌─┴─╖ │ │ │
│ │ ┌────┤ ‹ ╟────────────────┤ · ╟─────────────────────┐ │ │ │
│ │ ┌─┴─╖ ╘═══╝ ╘═╤═╝ │ │ │ │
│ │ ┌────┤ ‹ ╟─────────────────────────┤ │ │ │ │
│ │ ┌─┴─╖ ╘═══╝ │ │ ┌───╖ │ │ │
│ │ ┌──────────────────┤ ‹ ╟───────────────────┐ │ ┌─────────────────┴─────┤ = ╟─┘ │ │
│ │ │ ╘═══╝ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖ ╘═╤═╝ │ │
│ │ │ ┌─────────────────────┐ ┌───────┤ · ╟────────┤ · ╟─┤ · ╟──────┐ │ │ │
│ │ ┌───────────────┐ │ ┌─┴─╖ ╔════╗ ┌───╖ │ │ ┌──┐╘═╤═╝┌──┐ ╘═╤═╝ ╘═╤═╝ │ ╔════╗ │ │ │
│ ┌──┴─╖ ┌─┴─╖ └──────┴────┤ · ╟──┐ ║ 44 ╟──┤ = ╟─┴───┘ ┌─┴─╖└──┴──┘┌─┴──╖ ┌─┴─╖ ┌─┴─╖ │ ║ −1 ║ │ │ │
│ │ >> ╟──┤ · ╟──────┬───┐ ╔═════════╗ ╘═╤═╝ │ ╚════╝ ╘═╤═╝ ┌────┤ ? ╟───────┤ ‹; ╟─┤ · ╟─┤ · ╟──┐ │ ╚══╤═╝ │ │ │
│ ╘══╤═╝ ╘═╤═╝ ┌┴┐ └──╢ 2097151 ║ │ │ │ ┌─┴─╖ ╘═╤═╝ ╘════╝ ╘═╤═╝ ╘═╤═╝ │ │ ╔════╗ │ │ │ │
│ ┌─┴─╖ │ └┬┘ ╚═════════╝ │ │ └──┤ · ╟────┘ ┌───────┘ │ │ │ ║ 46 ╟──┐ │ │ │ │
┌─┴──┤ × ╟──┐ │ ┌────┴────────────────────┤ └────────────┐ ╘═╤═╝ ┌─┴─╖ │ │ │ ╚════╝ │ │ │ │ │
│ ╘═══╝ │ │ │ ╔════╗ ┌───╖ │ ┌───╖ ╔════╗ │ ┌─┴─╖ ┌─┤ · ╟───────────┘ │ │ ┌───╖ │ │ │ │ │
│ ╔════╗ │ │ │ ║ 93 ╟──┤ ≠ ╟─┴─┤ ≠ ╟───╢ 91 ║ └──┤ · ╟────┐ │ ╘═╤═╝ │ └──┤ = ╟──┘ │ │ │ │
│ ║ 21 ╟──┘ │ │ ╚════╝ ╘═╤═╝ ╘═╤═╝ ╚════╝ ╘═╤═╝ │ │ │ │ ╘═╤═╝ │ │ │ │
│ ╚════╝ ┌──┴╖┌─┴─╖ ┌─┴─╖ ┌─┴─╖ ┌───╖ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖ │ ┌────────┐ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖ │ │ │
└──────────┤ · ╟┤ · ╟────┐ ┌───╖ ┌────┤ ? ╟───┤ ? ╟───┤ › ╟──────┤ · ╟──┤ · ╟──┤ › ║ │ │ ├─────┤ · ╟────┤ ? ╟───┤ ? ╟─┘ │ │
╘══╤╝╘═╤═╝ ┌─┴─┤ ♯ ╟─┤ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ │┌┴┐ ┌┴┐ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ │ │
│ │ │ ╘═══╝ │ ┌─┴─╖ ┌─┴─╖ │ └┐ ┌─┴─╖ ┌─┴─╖ │└┬┘ └┬┘ └───┐ │ │ │ │
│ │ │ │ ┌─┤ · ╟───┤ ? ╟──┐ │ └─┐ │ › ╟──┤ › ╟─┘ │ ┌──┴─╖ ╔════╗ │ ┌─┴─╖ │ │ │
│ │ │ ┌─┴─╖│ ╘═╤═╝ ╘═╤═╝ │ └──────────┐ └┐╘═╤═╝ ╘═══╝ ┌─┴─╖ ┌─┤ << ╟──╢ 21 ║ └──┤ · ╟──┐ │ │ │
│ │ │ ┌──┤ · ╟┤ ┌─┴─╖ │ │ ┌──┴──╖└──┘ ┌────────┤ · ╟─┤ ╘════╝ ╚════╝ ╘═╤═╝ │ │ │ │
│ │ │ │ ╘═╤═╝└─┤ ? ╟───┬─┘ │ ┌───────┤ BF◊ ╟─────┘ ╘═╤═╝ └─────────────────────┘ │ │ │
│ │ │ │ │ ╘═╤═╝ │ │ │ ╔════╗╘══╤══╝ │ │ │ │
│ │ │ │ │ ┌─┴─╖ │ │ │ ║ 43 ║ │ ┌───╖ ├──────────┐ │ │ │
│ ┌─┴─╖┌─┴─╖┌─┴─╖ └────┤ · ╟───┘ │ │ ╚═╤══╝ │ ┌───┤ ᴥ ╟─────┘ ┌───╖ ├──┐ │ │ │
└─┤ · ╟┤ · ╟┤ · ╟─────┐ ╘═╤═╝ │ │ ┌─┴─╖ │ │ ╘═══╝ ┌───┤ ♯ ╟──┘ │ │ │ │
╘═╤═╝╘═╤═╝╘═╤═╝ ┌─┴─╖ └─┬──────────┘ │ │ ≠ ╟─┐┌─┴─╖ ┌─┴─╖ ┌─┴─╖ ╘═══╝ ┌─┴─╖ │ │ │
│ │ │ │ ɛ ╟───┘ ┌───────────┘ ╘═╤═╝ └┤ ? ╟─┤ · ╟─────────┤ › ║ ┌───┤ · ╟───────┐ │ │ │
│ │ ┌─┴─╖ ╘═╤═╝ │ ┌──────────┤ ╘═╤═╝ ╘═╤═╝ ┌───┐ ╘═╤═╝ ┌──┴─╖ ╘═╤═╝ │ │ │ │
│ └──┤ · ╟─────┘ │ │ ╔════╗ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖ │ ├────┤ ‹; ╟───┤ │ │ │ │
│ ╘═╤═╝ ┌─┴─╖ │ ║ 44 ║ │ ≠ ╟──┤ ? ╟─┤ · ╟─┤ › ║ │ ┌─┴─╖ ╘════╝ ┌─┴─╖ ┌─┴─╖ │ │ │
│ ┌─┴─╖ ┌──────┤ · ╟──┤ ╚══╤═╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ └─┤ · ╟─────────┤ · ╟─────┤ · ╟────┘ │ │
└───────┤ · ╟────┤ ╘═╤═╝┌─┴─╖ └─────┘ ┌─┴─╖ ┌─┴─╖ │ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ │ │
╘═╤═╝ │ │ │ ≠ ╟─────────────┤ ? ╟─┤ › ║ ├───────┘ │ │ ┌─┴─╖ │
│ │ ┌─┴─╖╘═╤═╝ ╔════╗ ╘═╤═╝ ╘═╤═╝ │ │ ├──────────────────┤ · ╟─┘
│ │ ┌────┤ · ╟─┐└────╢ 45 ║ ┌─┴─╖ ├─────┘ │ │ ╘═╤═╝
│ │ │ ╘═╤═╝ │ ╚════╝ ┌───┤ ? ╟───┘ ┌────────┐ │ │ │
│ │ │ ┌─┴─╖ │ ┌────────┘ ╘═╤═╝ ┌──┘ ┌─┴─╖ ┌─┴─╖ │ │
│ │ │ ┌──┤ ? ╟─┘ │ ┌─┴─╖ ┌─┴─╖ ┌─────┤ · ╟───────────┤ · ╟───────┘ │
│ │ │ │ ╘═╤═╝ ┌─┴─╖ ┌────┤ ? ╟─┤ › ║ │ ╘═╤═╝ ╘═╤═╝ │
│ │ │ │ ┌─┴─╖ ┌─┤ · ╟─┐ │ ╘═╤═╝ ╘═╤═╝ │ ┌─┴─╖ │ │
│ │ │ │ ┌┤ ? ╟─┘ ╘═╤═╝ │ ┌─┴─╖ └──┬──┘ │ ┌──┤ · ╟───┐ │ │
│ │ │ │ │╘═╤═╝ ┌─┴─╖ └─┤ · ╟─┐ └──────┘┌─┴─╖╘═╤═╝ ├─────────┘ │
│ │ │ │ │ └─────┤ · ╟─┐ ╘═╤═╝ └─────────────┤ › ║ │ │ │
│ │ │ │ │ ╘═╤═╝ │ ┌─┴─╖ ╘═╤═╝ │ │ │
│ │ │ │ └───────┬──┘ └─┤ · ╟──────────────┬──┘ ┌─┴──╖ │ │
│ │ │ │ ┌─┴─╖ ╘═╤═╝ └──┬──┤ ‹; ║ │ │
│ │ │ └───────┤ · ╟─────┬──┘ │ ╘═╤══╝ │ │
│ │ │ ╘═╤═╝ │ │ ┌─┴─╖ ┌─┴─╖ │
│ │ │ ╔════╗ ┌─┴─╖ ┌─┴─╖ ╔════╗ └──┤ · ╟─┤ · ╟──────────────────────────────────────┘
│ │ │ ║ 62 ╟──┤ ≠ ╟─┬─┤ ≠ ╟───╢ 60 ║ ╘═╤═╝ ╘═╤═╝
│ │ │ ╚════╝ ╘═══╝ │ ╘═══╝ ╚════╝ │ │
│ │ │ ┌─┴─╖ │ │
│ │ └─────────────┤ · ╟─────────────────────────────┘ │
│ │ ╘═╤═╝ │
│ └─────────────────┘ │
└──────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────┬──────────────────────────────┐ ╔═════════════════════════════════════════╗
│ ╓┬────╖ │ │ ║ Split input at the first newline and ║
│ ╟┘BF↕ ╟─────┤ ┌───╖ ╔═══╗ ┌─────┴─────────────────────┐ ║ convert the first part into a list of ║
│ ╙──┬──╜ └────┤ > ╟──╢ 0 ║ ┌─┴─╖ │ ║ integers. The integers represent the ║
│ ┌─┴─╖ ╘═╤═╝ ╚═══╝ ┌──┤ · ╟─────┐ │ ║ input to the brainfuck program, the ║
│ ┌────────────────────────┤ · ╟─────────────┴────────────┘ ╘═╤═╝ │ │ ║ rest is the brainfuck code. ║
│ │ ╔═════════╗ ╘═╤═╝ ┌────┴─┐ │ │ ╟─────────────────────────────────────────╢
│ │ ║ 2097151 ╟────┬───┴───────────┐ │ ┌┐ ┌─┴─╖ │ ┌┴┐ ║ BF↕(b, a) = ║
│ │ ╚═════════╝ ┌┴┐ ┌─┴─╖ └─┤├─┤ ? ╟───┴────┐ └┬┘ ║ let g = ¬a; ║
│ │ └┬┘ ┌─────────┤ · ╟────────────┐ └┘ ╘═╤═╝ │ │ ║ let s = a < 0; ║
│ │ ┌───┴───┘ ╘═╤═╝ │ ┌─┴─╖ ┌─┴─╖ │ ║ let c = b & ((1 << 21) − 1); ║
│ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖ │ ┌────┤ · ╟──────┤ · ╟───────┐ │ ║ let (h, u) = ‹(s ? g : a); ║
│ ┌────┤ · ╟──────────────┤ · ╟───────────────┤ · ╟─────────┐ └─┤ ╘═╤═╝ ╘═╤═╝ │ │ ║ let d = ›(u, (h × 10) + c − '0'); ║
│ │ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ │ ┌─┴─╖ ┌─┴─╖ │ │ │ ║ let f = s ? ›(u, ~h) : a; ║
│ │ │ ╔════╗ ┌───╖ │ ┌───╖ ╔════╗ ┌─┴─╖ ┌───╖ ├──┤ · ╟──┤ · ╟──┐ │ │ │ ║ let n = c = ' ' ? ›(f, 0) : ║
│ │ │ ║ 13 ╟──┤ ≠ ╟──┴──┤ ≠ ╟──╢ 10 ╟──┤ · ╟──┤ × ╟──┘ ╘═╤═╝ ╘═╤═╝ │ │ │ │ ║ c = '-' | c = '−' ? g : ║
│ │ │ ╚════╝ ╘═╤═╝ ╘═╤═╝ ╚════╝ ╘═╤═╝ ╘═╤═╝ ┌───╖ │ ┌┴┐ ┌─┴─╖ │ │ │ ║ s ? ¬d : d; ║
│ │ │ └────┬────┘ ┌─┴─╖ └───┤ + ╟─┘ │ ├─┤ ‹ ║ │ │ │ ║ let t = b >> 21; ║
│ │ │ ┌───┴─────────────────┤ · ╟──┐ ╘═╤═╝ └─┘ ╘═╤═╝ │ │ │ ║ let (p, i) = BF↕(t, n); ║
│ ┌────┐ │ │ ┌───╖ ┌─┴─╖ ╘═╤═╝ │ ┌─┴─╖ ┌───╖ │ ┌─┴─╖ │ │ ║ let e = c = '\r' | c = '\n'; ║
│ │ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖ ┌─┤ ᴙ ╟──┤ ? ╟── ╔════╗ ┌────╖ │ │ │ − ╟──┤ › ╟──────┴───┤ · ╟──┐ │ │ ║ [program: e ? t : p, ║
│ │ │ › ╟──┤ · ╟──┤ ? ╟─┤ ╘═══╝ ╘═╤═╝ ║ 21 ╟──┤ >> ╟────┘ │ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ │ │ │ ║ inputs: e ? ᴙ(f) : i] ║
│ │ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ │ ┌─┴─╖ ╚════╝ ╘═╤══╝ │ ╔══╧═╗ ┌─┴─┐ │ │ │ │ ╟─────────────────────────────────────────╢
│ │ ┌─┴─╖ │ │ │ ┌──┤ · ╟─────────────┴──┐ │ ║ 48 ║ │ ┌┴┐ │ │ │ │ ║ input ║
│ │ │ ~ ║ │ ┌───┘ └───┐ │ ╘═╤═╝ │ │ ╚════╝ │ └┬┘ │ │ │ │ ║ ↓ ║
│ │ ╘═╤═╝ │ │ ╔════╗ │ │ ┌──┴──╖ ┌─┴─╖ │ │ ┌─┴─╖ │ │ │ │ ║ ┌──┴──╖ ║
│┌─┴─╖ └──────┘ │ ║ 32 ║ │ └─┤ BF↕ ╟─────────────┤ ? ╟───────┘ └─┤ ? ╟──────────┘ │ │ │ ║ accumulator → ─┤ BF↕ ╟─ → BF inputs ║
└┤ · ╟────────────┘ ╚═╤══╝ │ ╘══╤══╝ ╘═╤═╝ ╘═╤═╝ │ │ │ ║ ╘══╤══╝ (list) ║
╘═╤═╝ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖ │ ┌─┴─╖ ┌─┴─╖┌─┴─╖ │ ║ ↓ ║
│ │ = ╟──┤ · ╟──┤ ? ╟─────────────────────────────────────────┤ ? ╟─────────────┤ · ╟┤ · ╟──┘ ║ BF program ║
│ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝╘═╤═╝ ╟─────────────────────────────────────────╢
│ │ │ ┌─┴─╖ ╔═══╗ ┌────┴────┐ │ │ ║ Exercise to the reader: This function ║
│ │ └────┤ › ╟──╢ 0 ║ ╔══════╗ ┌─┴─╖ ┌─┴─╖ ╔════╗ │ │ ║ uses a trick to encode both a list of ║
│ │ ╘═══╝ ╚═══╝ ║ 8722 ╟──┤ ≠ ╟──┬──┤ ≠ ╟──╢ 45 ║ │ │ ║ integers and an additional boolean in ║
│ ┌─┴─╖ ╚══════╝ ╘═══╝┌─┴─╖╘═══╝ ╚════╝ │ │ ║ a single value (the accumulator). ║
└─────────────────┤ · ╟───────────────────────────────────────────────────────┤ · ╟───────────────┘ │ ║ How does it encode the extra boolean, ║
╘═╤═╝ ╘═╤═╝ │ ║ and what is its purpose? ║
└────────────────────────────────────────────────────────┬──┘ │ ╚═════════════════════════════════════════╝
└─────────────────────────┘
┌─────────────────────────────────────────────────────────────────────┐
│ ╓┬────╖ │
┌─┴─╖ ┌─────────────────────╫┘BF■ ╟────┤ ╔══════════════════════════════════════╗
┌───────────────┤ · ╟───────────────────────────┐ ┌─┴─╖ ╙──┬──╜ │ ║ Computes the jump table of the ║
│ ╘═╤═╝ ╔═════════╗ ├────┤ ‹ ╟───┐ │ │ ║ brainfuck program: for every ║
│ │ ║ 2097151 ╟──┬──┘ ╘═══╝ │ │ │ ║ square-bracket character in the ║
│ │ ╚═════════╝ ┌┴┐ ┌──────────┴─────────────┐ │ │ ║ brainfuck program, the resulting ║
│ │ ╔════╗ ┌───╖ └┬┘ ┌─┴─╖ ┌───╖ ╔════╗ │ │ │ ║ list contains the index of the ║
│ │ ║ 93 ╟──┤ = ╟──────┴──┤ · ╟─┤ = ╟──╢ 91 ║ │ │ │ ║ matching other square bracket. ║
│ │ ╚════╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ ╚════╝ │ │ │ ╟──────────────────────────────────────╢
│ ┌─┴─╖ │ ┌───┘ │ ┌─┴─╖ │ │ ║ BF■(q, s, a) = ║
│ ┌─┤ · ╟┐ │ │ ┌───╖ ┌─┴─╖ ┌─────────┤ · ╟──┴────┐ │ ║ let (i, p) = ‹(q); ║
│ │ ╘═╤═╝│ ┌───────┴─────┐ └─┤ › ╟─┤ · ╟────┘ ╘═╤═╝ │ │ ║ let (m, t) = ‹(s); ║
│ │ │ │ ┌─┴─╖ ┌───╖ ┌─┴─╖ ╘═╤═╝ ╘═╤═╝ ┌──────┴──────┐ │ │ ║ let c = p & ((1 << 21) − 1); ║
│ ┌───╖ ┌─┴─╖ │ ├────┤ · ╟──┤ ‹ ╟──┤ ? ╟─┐ ┌─┴─╖ │ ┌─┴─╖ │ │ │ ║ let l = c = ']'; ║
│ ┌─┤ ♯ ╟──┤ ↨ ╟─┘ │ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ └─┤ ? ╟───┘ │ ♯ ║ │ │ │ ║ let x = l ? t : s; ║
│ │ ╘═══╝ ╘═╤═╝ │ │ └───┬──┘ ╘═╤═╝ ╘═╤═╝ │ │ │ ║ let y = ↨(a, m, ♯(i)); ║
│ │ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖ ┌──┴──╖ ┌─┴─╖ │ │ │ ║ let z = ↨(y, i, ♯(m)); ║
│ └─────┬──┤ ↨ ╟──┤ · ╟──┤ ? ╟──────┤ · ╟─────┤ BF■ ╟────────────┤ › ║ │ │ │ ║ p ? BF■(›(p >> 21, ♯(i)), ║
│ │ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ ╘══╤══╝ ╘═╤═╝ │ │ │ ║ c = '[' ? ›(s, i) : x, ║
│ │ ┌─┴─╖ │ │ ┌─┴─╖ ┌─┴─╖ ┌─┴──╖ ╔════╗ │ │ │ ║ l ? z : a) ║
│ │ │ ♯ ║ │ └──┬─────┤ · ╟──────┤ ? ╟──────┬──────┤ >> ╟──╢ 21 ║ │ │ │ ║ : a ║
│ │ ╘═╤═╝ │ │ ╘═╤═╝ ╘═╤═╝ │ ╘════╝ ╚════╝ │ │ │ ╟──────────────────────────────────────╢
│ │ └──────┘ ┌─┴─╖ ┌─┴─╖ │ ┌─┴─╖ │ │ │ ║ Exercise to the reader: How does ║
│ └───────────────────┤ · ╟───┤ · ╟───────────────┤ · ╟────────────────────┘ │ │ ║ this algorithm find all matching ║
│ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ │ │ ║ brackets in just a single pass ║
│ ┌─┴─╖ ┌─┴─╖ │ │ │ ║ of the brainfuck program? ║
└────────────────────────────┤ · ╟───┤ · ╟─────────────────┘ │ │ ╚══════════════════════════════════════╝
╘═╤═╝ ╘═╤═╝ │ │
│ └─────────────────────────────────────────────┘ │
└────────────────────────────────────────────────────────┘
╓┬────╖
╟┘BF0 ║ ╔══════════════════════════════╗
╓┬───╖ ╔═════════════════════════════╗ ╔════╗ ┌────╖ ╙──┬──╜ ║ zeroed list ║
╟┘‹; ║ ║ safe shift ║ ║ 21 ╟──┤ >> ╟───────────┴──────────────┐ ╟──────────────────────────────╢
╙─┬──╜ ╟─────────────────────────────╢ ╚════╝ ╘══╤═╝ │ ║ (returns a list containing ║
┌────────┴─────┐ ║ (returns 0 and an empty ║ ┌──┴──╖ │ ║ all zeros of the same ║
┌────┴────┐ │ ║ list when input is empty) ║ │ BF0 ║ ╔═══╗ ┌───╖ │ ║ length as the BF program) ║
┌──┴──┐ │ ┌──┴──┐ ╟─────────────────────────────╢ ╘══╤══╝ ┌────╢ 0 ╟──┤ ≠ ╟──┐ │ ╟──────────────────────────────╢
│ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖ │ ║ ‹;(l) = ║ ┌─┴─╖ ┌─┴─╖ ╚═══╝ ╘═╤═╝ │ │ ║ BF0(p) = ║
│ ─┤ ? ╟──┤ ‹ ╟──┤ ? ╟─ │ ║ let (h, t) = ‹(l); ║ │ › ╟──┤ ? ╟───────────┤ ├──┘ ║ (p = 0) | (p = −1) ║
│ ╘═╤═╝ ╘═══╝ ╘═╤═╝ │ ║ [l ? h : l, l ? t : l] ║ ╘═╤═╝ ╘═╤═╝ ╔════╗ ┌─┴─╖ │ ║ ? 0 ║
└─────┘ └─────┘ ╚═════════════════════════════╝ ╔═╧═╗ │ ║ −1 ╟──┤ ≠ ╟──┘ ║ : ›(BF0(p >> 21), 0) ║
║ 0 ║ │ ╚════╝ ╘═══╝ ╚══════════════════════════════╝
╚═══╝