Miserie to DownRight translation

Note: This translation is difficult to explain even on the best of days, and the author (User:Keymaker) is absolutely exhausted by this project and all the detail involved. There might be factual errors in the text and it may be confusing. This article would benefit greatly from images and animations. I hope to make this clearer one day.

Miserie was created to be a language that could be easily translated into DownRight. But my (User:Keymaker) thinking was riddled with errors, as I almost immediately found out, and the task was not easy at all. I kept at it from 2019 onwards, and eventually arrived at a solution in 2025. Also, most of my work was on a different tangent. While it did not become part of this translation, it may yield, in time, something different.

Miserie has just one instruction type. When executing an instruction, the queue is read and the first bit removed. (If there is no data, the program halts.) According to that bit, data associated with is appended (or not, as the data may be zero-length), then the next instruction is selected (or not, if the program halts instead).

The translation requires there to be, at the beginning of an instruction simulation, at least two bits of memory in the queue. Otherwise the translation does not work properly. If the queue gets below two bits after an instruction has been executed, it cannot continue working properly any longer. The memory will get down to one bit if an instruction simulation begins with two bits, but in that case new data needs to be appended (to make the queue have at least two bits) or the program to halt immediately. (The two bit requirement is a property of this translation, not of Miserie itself. The reader is encouraged to create a translation that works with one-bit queue...)

The queue is implemented using a method I have not seen before, which I call the widening queue in this context. A widening queue has every consequent bit using more storage space (with the next-to-be-read bit taking the smallest amount of storage). In this translation, each bit uses 2^(3*n+2) memory. This is a lot, yes. The lengths of successive bits are 4, 32, 256, 2048, 16384... In addition, the size of each unit, of which a value consists of, is proportional to the size of the matrix, so for a larger program the size of a bit is even larger.

I invented the widening queue before I could actually use it. Eventually I got it working when I had the simplest realization: there is nothing stopping me from having a counter and a queue within the DownRight queue. The counter will keep the value of the current highest bit, and when adding a new bit, the counter will be replicated and fused into the end of the queue. I did realize, after I had gotten my queue working, that I could do stacks using the same techniques (or nearly so), but since all this time my goal has been to have a queue in DownRight, I wanted to use that despite it being (possibly) more difficult to implement.

The queue, such as it is within the larger queue, is a continuous string of arrows consisting of 0 and 1 units. When reading the queue, the queue is halved until the smallest bit is erased and the larger bits are a magnitude smaller. The reason the queue uses 2^(3*n+2) values is closely tied with the 'read bit' code, to keep already complex things simpler.

The height of the program is always 8. I'm not saying it's impossible to do in less, but I was not able. Consider what is required (in the context of this translation): Two different types of values. The smallest bit-length is 4 units and every larger bit-length is dividable by 4. When moving an even number of times (and more than zero), both encodings reach the same position (when wrapping at 8). When moving just once, a 0-bit moves 2 cells, and a 1-bit moves 4 cells. This difference is used to determine the smallest bit as it is being removed. Because there needs to be a way to halve a value (by adding just half of it back), such an action needs to be, per unit, done in one cycle of the height. For 1-bits this is two moves until wrapping (the other adding two units), for 0-bits this is four moves until wrapping (and adding one unit at two locations).

The get the system working, I had to build some tools. Invaluable to the design was the grid paper + pen approach, but because there were so many details to constantly see and change, I expanded on my older visual interpreter code with some improvements. Because I knew I was going to, finally, also publish my Minsky Machine to DownRight translations, I made a simple file format that the different translators use (which is more readable and easier to inspect than the normal DownRight format), and a tool (drintgen) that reads that input and creates a visual interpreter encoded with the given program. The visual interpreter may be loaded in a browser (it being HTML + Javascript), presenting a table-based solution for visualizing the process. The visual interpreter was used in designing all the components, and I doubt I could have designed them without having been able to constantly iterate and observe how the code actually behaved. With DownRight programs there is constant delay: what is being executed has to have been set earlier, based on earlier decisions. Decisions made at present will not come to cause effect until all of the memory has been processed.

Program components

I designed the different parts of the translator in smaller pieces, corresponding closely to the atomization of the Miserie instruction. (Remove bit and inspect it, append different data based on the bit's value, then branch based on the bit's value.) The parts are: mloader, mremovebit, mcreatecounters, mcopycounters, mfusecounter, and mhalt.

mloader

This part is executed only once, in the beginning of the program. It creates the initial queue defined in the Miserie program, generating the value in reverse order. The loader allows that the initial cell does not need to hold a massive amount of data, in the program source. Consider the numbers: 4, 32, 256, 2048, 16384, 131072, 1048576... With a relatively small data part, the program in the standard DownRight format might be required to contain a string of arrows requiring several million gigabytes of storage space. (Not feasible.) With a loader, the program creates a large amount of data from short code, leaving the storage of that to the interpreter, which can easily optimize it. The loader part may have empty columns called 'glue', if the co-primality of the matrix demands additional width for the program.

mremovebit

This part is executed at the beginning of each Miserie instruction's simulation. It removes the smallest bit whilst simultaneously decreasing all the larger bits one magnitude. This procedure also explains why I opted to use values 4, 32, 256, for the representation of bits: it makes things so much easier than something like 4, 8, 16. In fact, I don't even know if less can be used for this kind of system with program height of 8. The smallest bit needs to be 4 units. It takes three halve-operations to erase it. 4 into 2, 2 into 1, 1 into nothing. Consider this three-bit queue: (256, 32, 4) -> (128, 16, 2) -> (64, 8, 1) -> (32, 4). The larger values do not cause any additional shifting, which must be measured when removing the bit. By shifting I mean that to know which bit (0 or 1) was removed, the instruction pointer will be at a different location, and earlier bits in the queue cannot be interfering with that (and are not, in this design).

mcreatecounters

This part is the first of three steps when adding a new bit to the queue. It creates two new counters, each with one unit in them. The smallest value for a bit is 4 units, but in in-between calculations smaller values appear. This part also divides the first counter by four, because the next part (mcopycounters) will, due the way it works, do two additional increasing cycles.

mcopycounters

This is the second of three steps when adding a new bit to the queue. The previous step (mcreatecounters) created two new counters and divided the first counter by four. As this step executes, it entirely removes the first counter, and increases the new counters in the process. In the end, there are two counters that contain the value of the highest bit.

mfusecounter

This is the third of three steps when adding a new bit to the queue. The previous step (mcopycounters) copied the value of the first counter into two others. The first counter is multiplied by 8 to make it match the to-be-new largest bit-size of the queue. Then the second counter is fused into the queue, its format is changed into proper encoding of whether a 0-bit or 1-bit is added, and for every 1 unit 8 are added to the queue. This way the queue will have a new bit that is larger than the previous largest. This mcreatecounters -> mcopycounters -> mfusecounter cycle is repeated for every bit in the data string that is added.

mhalt

The program halts. All the data in the program is removed (nothing new is added) and the DownRight program halts. The state of the Miserie queue must be inspected at the start of the halting instruction, before any data is removed.

The memory states

Here is an example showcasing the changes in memory (in abstracted form) when simulating a Miserie instruction. In this example the queue has, initially, three bits. Their actual values (0 or 1) do not matter, and are not represented. Instead, their length in units is told. Here:

[Acounter256] [Aque256][Bque32][Cque4]

When entering mremovebit, there is one counter, and its value matches the value of the largest bit (the end of the queue, in other words). 256 here.

After mremovebit is executed, the counter has been divided by two three times, and one bit has been extracted. Likewise every bit in the queue has been halved three times, as data has been removed. The memory is now:

[Acounter32] [Aque32][Bque4]

If there is no data to be added, branching can happen directly to the next instruction.

If there is data to be added, it's time to execute mcreatecounters. After executing it, the memory is:

[Acounter8][Bcounter1][Ccounter1] [Aque32][Bque4]

Two new counters were added, each with value 1, Bcounter1 and Ccounter1. Acounter32 became Acounter16 which became Acounter8 as the original counter was divided by four.

Next mcopycounters. After executing it, the first counter will have been removed, and the two new counters will have the value of the largest bit, 32 in this example. The values of the two new counters will go 1->2->4->8->16->32. Because mcopycounter executes two additional multiply-by-two operations, the Acounter was divided by four in mcreatecounters to accommodate for that (32->16->8).

The memory, after mcopycounters, is now:

[Bcounter32][Ccounter32] [Aque32][Bque4]

Then it is time to fuse the other counter into the queue (represented as Nque), and during the process multiply the Bcounter by two three times, and while fusing the Ccounter multiply it similarly (multiply by eight, in other words). This way the order of the memory is valid again for either a new round of bit-adding or for the next mremovebit.

After mfusecounter, the memory is now:

[Bcounter256] [Nque256][Aque32][Bque4]

as it should be.

Using visual aid

I think it is worth mentioning that the translation makes so much more sense when one actually watches how the program behaves. I recommend translating a simple program and trying to see how the different parts work.

External resources

• mcompiler.py (the translator program)
• Miserie page (detailed explanations of Miserie, relevant software)