Kangaroo
Kangaroo is an esoteric programming language created by User:ais523 in 2015, in which the only thing instructions can do is temporarily disable other instructions. (This technically makes it an OISC, because it only has one sort of instruction, but it does not behave in a very similar way to other OISCs, because that instruction takes a multiset as an argument.)
Syntax
A Kangaroo program consists of a sequence of statements. Each statement contains the following parts, in the following order:
- A label, which is a sequence of letters, digits, and underscores;
- A colon, possibly with horizontal whitespace surrounding it;
- The keyword skip, followed by horizontal whitespace;
- and a multiset of labels (i.e. a set in which elements can appear multiple times), represented by writing their names separated by commas, possibly with horizontal whitespace on either side of the commas.
Statements are separated via vertical whitespace, and can have horizontal whitespace preceding or following them. All statement labels must be distinct.
Here's an example of what the syntax looks like:
foo: skip bar bar: skip foo, foo
Semantics
A Kangaroo program runs in an implicit loop; when the end of the program is reached, it starts back at the start again. Each command is stored with a nonnegative integral skip count, which is initially zero. In order to execute a command:
- If its skip count is zero, then the skip count of each statement is increased by the number of times it appears in the executing statement's multiset;
- If its skip count is nonzero, then its skip count is decremented (decreased by 1) and nothing else happens.
If a command skips itself, this doesn't have any effect until the next cycle.
Computational class
Kangaroo can be proved Turing complete via compiling level 1 of The Amnesiac From Minsk into it.
First, the The Amnesiac From Minsk program is modified via inlining increment triggers: whenever an increment command appears within a trigger, that trigger should be replaced with the increment command followed by the increment trigger for the incremented counter. (This can leave triggers containing more than one command, i.e. the resulting program is not a The Amnesiac From Minsk program.) Then delete all increment triggers, to leave a resulting program with nothing but failed-decrement and successful-decrement triggers, each of which consists of a (possibly empty) list of increments, followed by one decrement.
Each counter then translates into two Kangaroo commands:
- The first command skips: all commands (including the second command and itself) except those translated from the decremented counter for the failed-decrement trigger of this counter; all the first commands translated from counters that are incremented by the failed-decrement trigger of this counter one additional time; and the second command one additional time (i.e. twice total, unless the counter decrements itself).
- The second command skips: all commands (including the first command and itself) except those translated from the decremented counter for the successful-decrement trigger of this counter; and all the first commands translated from counters that are incremented by the successful-decrement trigger of this counter one additional time.
Finally, we write one additional command at the start of the program. This skips the first command of each counter a number of times equal to its initial value (minus one for the first counter); and the second command of each counter (except the first counter) once. It's skipped once by each other command (meaining that it only runs on the first cycle), and its purpose is to initialize all the skip values appropriately.
The basic invariant for the construction is that, at the end of each cycle (which corresponds to the moment in time in The Amnesiac From Minsk after a counter was decremented but before its decrement trigger has run), the skip count of the second command of each counter tracks whether it was just decremented (0 if it was, 1 if it wasn't); the skip count of the first command of each counter is normally the counter's value, but is 0 if the counter was just failed-decremented; and the skip count of the additional command is 1. To prove that the invariant holds (and thus that the construction is correct), first note that a command can only run if it has a skip count of 0 at the start of the cycle; thus the only commands that can even potentially run are the first and second commands of the counter that was just decremented. We have two cases:
- If the counter was decremented from 1, then its first command will run. This means that the second command won't run (because it skips it), and thus no other commands will run this cycle. Each other command's change in skip count over the cycle will thus be the number of skips requested by the first command minus 1. For first commands (emulating values), this means that the newly incremented counters will have their values increased by 1 (as they're skipped twice); the newly decremented counter's value will decrease by 1 (its first command isn't skipped), to 0 if it was decremented from 1; and other counters will have their value stay the same. As for second commands, they all have a net change of 0 apart from the second command of the newly decremented counter (which has a net change of -1, changing from 1 to 0), and the second command of the counter that just decremented (which, being skipped twice, has a net change of 1, changing it from 0 to 1). The counter skips itself once, changing its value from 0 up to 1, which is what we expect from a failed decrement. And it skips the additional command once, keeping its skip count steady at 1.
- If the counter wasn't decremented from 1, then its first command won't run (because its skip count wasn't 0), and so its second command will. (As in the other case, no other commands run this cycle.) The behaviour is analogous to the other case: first commands increment/decrement/leave unchanged each counter based on whether it's incremented, decremented, or left unchanged by the trigger; and second commands are left at the same value apart from the newly decremented counter (net change -1) and the previously decremented counter (i.e. the command that runs; it sets its own skip count from 0 to 1). The additional command has its skip count held steady at 1.
Relationship to C-INTERCAL
C-INTERCAL has an ABSTAIN #1 FROM command that works analogously to Kangaroo's skip command; it increases an abstention count of a multiset of commands by 1 for each command in it, and commands with a positive abstention count don't run. It also has a TRY AGAIN command that can be used to place a program in an implicit loop. This makes it possible to compile Kangaroo almost directly into it; the only difference is that running a command in C-INTERCAL does not automatically reduce its abstention count (like running a command in Kangaroo does), but this can be easily fixed via adding a REINSTATE statement (that reduces the abstention count by 1) directly after it (and getting the command to ABSTAIN itself one extra time, because the REINSTATE command runs unconditionally, as opposed to the skip count decrease in Kangaroo which is conditional on the command not running).