ChaitinFuck

ChaitinFuck is a brainfuck derivative language designed to make all syntax valid, for the purposes of simplifying automated code generation. It uses a somewhat convoluted method of rolling loops, such as to allow loop closes (the only part of brainfuck that has any requirement of the surrounding code) to be randomly placed.

Changes

ChaitinFuck is just like brainfuck, but the way that loops are implemented is slightly different and more specific and overflows to the left of the tape are fixed. A standard brainfuck interpreter tends to work with loops by making [ PUSH the current location in the code onto a stack, and ] POP a location off the stack and go to it. This means that, when a ] is called without a matching [, the program will crash from lack of information on the stack. ChaitinFuck resolves this by changing the behavior of POP.

When POP is called on a Chaitin Stack, it first removes the top value from the stack and stores it in a variable ToS. It then INJECTs ToS, inserting it at the bottom of the stack, then returns the variable. In the event that the stack is empty, the POP instruction returns 0, so the code reverts to the start.

The other change, tape right overflows, is also fixed. In ChaitinFuck, the tape is right-infinite in that when you > at the end of the tape, a new cell is added to prevent overflow. When you use < at the left end of the tape, the tape rolls around to the end of the tape (the last created cell). This has the interesting property that <> is not always a NOP, because if called at the left end of the tape it causes the pointer to be moved to a new cell one past the previous right extremity of the tape. >< is still a NOP.

All other instructions are exactly the same as in brainfuck, making ChaitinFuck fully backwards-compatible with valid brainfuck programs, assuming a right-infinite tape that crashes on left overflow. Unlike other languages which claim to be brainfuck-compatible, ChaitinFuck actually is, as it allows