Advance The Wheel!
Advance The Wheel! is a turning tarpit created by User:ais523 in 2022. Its primary purpose is to create a language in which a self-interpreter can be as small as possible. It also has an unusual form of control flow: when the program reads data from memory, this does not affect the position of the instruction pointer, but rather affects the position of the wheel (thus the two branches of the equivalent of an "if" statement will run the same program commands, but with different meanings because they will correspond to different wheel commands).
Data model
A program in Advance The Wheel! stores data in queues of bits – there are an unbounded number of such queues available, and each can hold an unbounded number of bits. In order to determine which queue memory operations operate on, there is an unbounded integer (which can be positive, negative or zero) that is known as the queue pointer; at the start of the program, this is initially 1. It refers to a queue in the following fashion:
- When the queue pointer is odd (i.e. congruent to 1 mod 2), it refers to queue 1;
- when the queue pointer is congruent to 2 mod 4, it refers to queue 2;
- when the queue pointer is congruent to 4 mod 8, it refers to queue 3;
- when the queue pointer is congruent to 8 mod 16, it refers to queue 4, etc..
- As a special case, when the queue pointer is 0, it refers to queue 0.
Queue 0 is special: enqueuing bits onto it writes to standard output, and dequeuing bits from it reads from standard input (rather than returning bits enqueued earlier). The exact encoding of I/O has not been specified yet, nor has EOF behaviour – this may change in the future.
Attempting to dequeue a bit from an empty queue halts the program.
An Advance The Wheel! interpreter initializes queues 1, 2, 3, etc. in sequence from its command-line arguments; each command-line argument names a file, and the contents of that file provide the initial contents of the queue. Apart from queue 0 (whose contents are inaccessible and thus irrelevant), queues for which no corresponding command-line argument is present start out empty.
In addition to the queues and queue pointer, there is also The Wheel. This is, in effect, a list of nine "wheel commands" plus a pointer that can point to one command (the "current command") on The Wheel; "advancing" The Wheel increments the pointer, causing it to point at the command immediately after the command it was previously pointing to (and it wraps back to the start upon reaching the end).
Commands
Program commands
Advance The Wheel! programs are a sequence of bits, with each bit corresponding to one of two commands, based on its value:
- A 0 bit advances The Wheel.
- A 1 bit runs The Wheel's current command, and then advances The Wheel. (Even if the wheel command advances The Wheel, the program command advances it anyway after running the command, so, e.g. if the current command is "advance The Wheel", running the "1" program command will cause The Wheel to advance twice; once from the wheel command, and once from the program command.)
The program commands that make up the program always run in sequence from start to end; there is no control flow. When the end of the program is reached, the instruction pointer loops back to the start of the program, effectively making the program into the body of a giant infinite loop (with the only way to break out of the loop being to halt the program by trying to dequeue from an empty queue).
A program is not allowed to be entirely empty (the empty program has undefined behaviour).
Wheel commands
The Wheel contains nine commands. (This description of the language names them with letters, "A" to "I" inclusive, in order to make it easier to explain which command is being referred to; they cannot be named directly in a program, so the names are irrelevant from the point of view of implementing or programming in the language.) Here they are, in the order they appear on The Wheel:
| A | Dequeue a bit from the queue that the queue pointer refers to. If the dequeued bit was a 1 bit, advance The Wheel! |
|---|---|
| B | Do nothing. |
| C | Decrement the queue pointer. |
| D | Enqueue a 0 bit onto the queue that the queue pointer refers to. |
| E | Enqueue a 1 bit onto the queue that the queue pointer refers to. |
| F | Do nothing. |
| G | Advance The Wheel! |
| H | Do nothing. |
| I | Increment the queue pointer. |
Advancing The Wheel therefore changes the current command from A to B, from B to C, … from H to I, or from I to A. At the start of program execution, the current command is command A.
Computational class
Every cyclic tag system can be compiled into Advance The Wheel! fairly directly – it's possible to use queue 1 to contain the data string, and to hard-code the production rules into the program. Between two production rules, The Wheel's current command is command A. The Advance The Wheel! code for that implements the start of a production rule is 100001000; this runs command A to dequeue a bit from queue 1, then runs command F if a 0 was dequeued, or G if a 1 was dequeued, with three more 0 commands leaving the current command as A or C based on whether a 0 was dequeued (i.e. skip the production) or a 1 was dequeued (i.e. append the production to the queue). A 0 within the production can then be implemented as 010000000 (which runs command B if the production should be skipped, or D if it should be appended), and a 1 as 001000001 (which runs commands C and I (which cancel each other out) if the production should be skipped, or E and B if it should be appended). At the end of the production, 0000001001000010 will deterministically get the current command back to command A (via running GBG if the current command was A, or ICH if the current command was C – the former has two advancements and a no-op, the latter has two queue pointer adjustments that cancel each other out and a no-op, so The Wheel is advanced 18 or 16 times depending on whether the current command was initially A or C, and thus ends up at A in either case).
The initial state of the data string can be initialized from a file specified via a command-line argument, but if you consider that cheating, it's also possible to initialize it within the program itself, via starting with 00 followed by a "production body" that initializes the data queue (and the 0000001001000010 after it that normalizes The Wheel's current command) – the production body will then run with The Wheel with C as its current command on the first pass through the program (which is where The Wheel starts), and thus initialize the data queue appropriately. Ending the program with 0000000 will cancel out the leading 00 (as nine 0s are a no-op), meaning that on subsequent executions, the initializer's "production body" starts out with A as the current command and thus does nothing.
Programs
Self-interpreter
10010111000000100000010011001001000000010110000000 01010010100100000011000111001000000100010000010001 00100001000100010100100101001010001001001000000010 100001100000011000010010
This self-interpreter is only 174 bits long. It works via using its queue n+1 to model queue n of the interpreted program; queue 1 holds the program being interpreted. The queue pointer is twice the queue pointer of the interpreted program plus a constant (the constant depends on the position within the program and The Wheel's current command, but is normally either -1 or 1). The position of the instruction pointer within the self-interpreter encodes the position of The Wheel within the interpreted program (and the position of the instruction pointer within the interpreted program is always at the head of queue 1 – whenever a command is executed, it is dequeued, then re-enqueued). This way of doing things means that the language is metacircular in terms of I/O and in terms of the queue pointer decoding, but the wheel commands are all implemented explicitly using actual code (thus, it would be easy to alter this program so that it implements a language that was the same in most respects, but used a different Wheel).
Here's a computer-generated explanation of how the program works (each section of code implements either one wheel command or two consecutive wheel commands); each line specifies a possible interpretation of the program commands as wheel commands, together with the queue operations that occur during / produce that interpretation:
Behaviour for AB_dequeue_nop (10010111000000100000010011001001000000010): ADFGIGFIADGG [qptr: 1 -> 3] shift 0 from 1; push 0 to 1; shift 0 from 1; push 0 to 1 ADFGIGFIAEHG [qptr: 1 -> 3] shift 0 from 1; push 0 to 1; shift 1 from 1; push 1 to 1 AEGIAHFIADGG [qptr: 1 -> 3] shift 1 from 1; push 1 to 1; shift 0 from 2; shift 0 from 1; push 0 to 1 AEGIAHFIAEHG [qptr: 1 -> 3] shift 1 from 1; push 1 to 1; shift 0 from 2; shift 1 from 1; push 1 to 1 AEGIAIGBCFIH [qptr: 1 -> 3] shift 1 from 1; push 1 to 1; shift 1 from 2 Behaviour for C_decrement (11000000001010010): ABBDG [qptr: 3 -> 3] shift 0 from 1; push 0 to 1 ACCEH [qptr: 3 -> 1] shift 1 from 1; push 1 to 1 Behaviour for D_enqueue_0 (10010000001100011): ADBCGI [qptr: 3 -> 3] shift 0 from 1; push 0 to 1 AECDHI [qptr: 3 -> 3] shift 1 from 1; push 1 to 1; push 0 to 2 Behaviour for E_enqueue_1 (100100000010001000001000100100001000100010): ADBFCGBGCG [qptr: 3 -> 1] shift 0 from 1; push 0 to 1 AECGEICHCG [qptr: 3 -> 1] shift 1 from 1; push 1 to 1; push 1 to 2 Behaviour for F_no_operation (10010010): ADG [qptr: 1 -> 1] shift 0 from 1; push 0 to 1 AEH [qptr: 1 -> 1] shift 1 from 1; push 1 to 1 Behaviour for GH_advance_nop (1001010001001001000000010): ADFADGG [qptr: 1 -> 1] shift 0 from 1; push 0 to 1; shift 0 from 1; push 0 to 1 ADFAEHG [qptr: 1 -> 1] shift 0 from 1; push 0 to 1; shift 1 from 1; push 1 to 1 AEGCFIH [qptr: 1 -> 1] shift 1 from 1; push 1 to 1 Behaviour for I_increment (100001100000011000010010): AFGFGDG [qptr: 1 -> 1] shift 0 from 1; push 0 to 1 AGIGIEH [qptr: 1 -> 3] shift 1 from 1; push 1 to 1
External resources
- Interpreter
- Some Perl subroutines that ais523 uses to help generate fragments of Advance The Wheel! code