Last ReSort

Last ReSort is an esoteric programming language created by User:ais523 in 2015. It was originally discovered while trying to design an extremely short language main loop, along the lines of MiniMAX but even simpler. The particular approach taken here was a consequence of trying to optimize a Three Star Programmer implementation, thinking "wouldn't it be nice if this were a ZISC", and then trying to find the simplest possible reduction of Three Star Programmer into ZISC form that wasn't obviously Turing incomplete; the particular construction used was also distantly inspired by Malbolge (specifically, in the fact that "commands" change when run). The resulting ZISC turned out to implement a pretty elegant language; both the language and the ZISC itself are described here.

Semantics

A Last ReSort program consists of a list of integers, and a pointer into that list.

Execution proceeds via, repeatedly and indefinitely:

• incrementing the pointed-to integer;
• retargeting the pointer to point to the nth integer of the list, where the currently pointed-to integer is the nth highest integer in the list.

For example, if after incrementing the pointer is pointing to the highest (i.e. first-highest) element of the list, it'll be retargeted to point to the first element of the list. Likewise for the second-highest element and the second element, and so on.

In the case that two elements are tied, the element under consideration is considered to be the highest of the tied elements. So for example, in the list [2, 4, 5, 4], each of the 4s is considered to be the second-highest element of the list (the 2 is the highest and the 5 is the fourth-highest). This is the same tiebreak used by many sporting events (give all the tied competitors the highest of the ranks they tie for).

ZISC implementation

As defined above, Last ReSort is not a ZISC, but it has a (perhaps surprisingly) very simple implementation of this form.

First, note that a Last ReSort program is invariant under adding the same integer to each list element. So without loss of generality, we can assume that each integer is higher than the number of integers in the list. Then we represent the program as a memory array, that starts with the list, and sets each other element of memory to the number of integers in the list that are greater than the address of that memory location.

Adjusting our example of [2, 4, 5, 4] to [5, 7, 8, 7], the memory array thus looks like this:

Address  0  1  2  3  4  5  6  7  8  9
Value    5  7  8  7  4  3  3  1  0  0  (and 0s forever from then on)
         list------  counts----------

We use a pointer p into memory (which originally starts pointing to the memory location that corresponds to the initially pointed-to integer from the initial list). Execution progresses as follows:

while (true)
  p = (*p)++;

(This is a true, and very simple, ZISC because there's only one command used, which takes no arguments, i.e. the behaviour is entirely defined via the initial contents of memory and the initial pointer, there is no separate program.)

To see how this implements Last ReSort, consider what happens after two ZISC steps:

• First, the pointed-to memory location (corresponding to the pointed-to integer) is incremented (an exact match);
• Then, the pointer moves to the address equalling the value before it was incremented;
• Then, the newly pointed-to location is incremented (maintaining the invariant that its value is equal to the number of integers from the list that are greater than its address; the increment means that one more integer is now greater than the address than previously);
• Then, the pointer moves to the address equalling the value before it was incremented. If the originally pointed-to location had the highest value, then no integers from the list would be higher than it, so we'd have had a 0 there, and thus will end up pointing to the first memory location. Likewise, if it had the second highest value, then 1 integer from the list would be higher than it, so we'd have had a 1 there, and thus will end up pointing to the second memory location.

In other words, two ZISC steps correspond exactly to one Last ReSort step.

On a side note, this ZISC version has a very simple interpreter in the I/D machine, ID (the address numbering is off by 1 from the example above, so you'll need to add a dummy entry at the start of the data array, but this clearly makes no real change to the language).

Example

This example (probably) doesn't do anything useful; it's just an example.

Address  0  1  2  3  4  5  6  7  8  9
Value   [5] 7  8  7  4  3  3  1  0  0
Value    6  7  8  7  4 [3] 3  1  0  0
Value    6  7  8 [7] 4  4  3  1  0  0
Value    6  7  8  8  4  4  3 [1] 0  0
Value    6 [7] 8  8  4  4  3  2  0  0
Value    6  8  8  8  4  4  3 [2] 0  0
Value    6  8 [8] 8  4  4  3  3  0  0
Value    6  8  9  8  4  4  3  3 [0] 0
Value   [6] 8  9  8  4  4  3  3  1  0
Value    7  8  9  8  4  4 [3] 3  1  0
Value    7  8  9 [8] 4  4  4  3  1  0

and so on.

Computational class

Last ReSort is known to be able to implement The Amnesiac From Minsk level 4 (see that page for the construction), but the computational class of that language is currently unknown, and thus does not yet determine anything about the computational class of this language.