Hanoiing
A language made by User:Beefster based on the Towers of Hanoi puzzle.
The language architecture consists of a single unbounded integer register and three unbounded stacks of unbounded integers. The catch is that the top value of every stack must be smaller than the number immediately below it (and by extension, every other number in the stack), just like in the Towers of Hanoi puzzle. All programs begin with the register set to 0 and all stacks empty.
Instructions are unicode-based using the following opcodes:
- a, b, c: pop the top value from the corresponding stack into the register and branch if empty
- A, B, C: push the register value onto the corresponding stack and branch if invalid
- Branching executes the next character and skips it otherwise
- =: set the register to the value represented by the following decimal digits
- +, -: increment/decrement the register
- ~: negate the register
- j: jump to the byte index, ignoring the instruction if invalid
- J: ditto, but using the register's value
- l: jump to beginning line number, ignoring the instruction if invalid
- L: ditto, but using the register's value
- z: execute the next character if the register == 0 (otherwise, skip it)
- p: ditto for positive numbers
- n: ditto for negative numbers
- i: read the next unicode point of stdin into the register
- o: output the register's unicode value to stdout
- all other characters are no-op
The language is Turing complete, as it can simulate a 3-counter machine which is Turing complete. This can be done by using only one entry in an otherwise empty stack to represent the three registers. All counter machine operations are simple sequences of a few operations:
- To copy, pop the destination, pop the source, push to source, push to destination
- To increment or decrement, pop, increment/decrement, then push
- To clear, pop, set register to 0, push
- To jump if zero, pop, push, then branch if zero "zj___"
An implementation in Python with two sample programs (a simple Hello World and a (broken) Towers of Hanoi solver) can be found here.