Talk:Malbolge programming

I thought of writing my techniques used to implement the quine to this article, but I did not really know how to do this. I am not very familar with the way this article describes malbolge programming at the moment. So I don't know if I should write everything to a new section and/or how to change the existing text of the article. Some sections of this article are ery unclear to me, so I don't know how to fit my description into it. An other reason is that I feel more free to write it in rough to the discussion page. And I'm not willing to write this very long text very carefully (so I hope someone of you is willing to do so ;-) ). Also I'm afraid that my English is not the best. And the last (but not least) reason: This text is very long, maybe it can be shortend and be more generalized before writing it to the article page. so I decided to put it to the discussion page. I hope you forgive me that I'm ignoring the policy of this wiki to be bold in editing pages.

So, here we go:

(The fist part is almost copied from an email I wrote earlier. But my talk about initialization is exclusive for this wiki. ;-) )

I'll call the encryption method for executed commands "xlat2" as in the original interpreter (and in the paper of that Japanese guys http://www.sakabe.i.is.nagoya-u.ac.jp/~nishida/DB/pdf/iizawa05ss2005-22.pdf - I am not able to understand a single symbol of Japanese, but Google and a penfriend helped me a bit). the problem by filling instructions with NOPs would be, that the code would become very large and there are VERY MUCH immutable NOPs that have to be created during the initialization. The quine currently has about 250 cells that are modified during initialization and that took about 24k Bytes of Malbolge code. (About 5k Bytes are unused in the released version - That will become 10k, because they appear again in the data section) The 99 bottles of beer program initialized about 400 cells and needs 22k instructions for that. One reason for their smaller initialization could be that they were able to set the cells that have to be initialized to 0t1111101111 and 0t0000010000 alternately, because they used the uninitialized memory. That is very good, because 0t0000010000 is always the same return address for the data pointer during initialization and 0t1111101111 is very good to put data there. (Only 0t1111111111 would be better - I'll call 0t1111111111 C1 in the feature, as the Japanese guys did in their paper. C0 and C2 appropriate). But quine is to big to use uninitialized memory, so that may be a reason that my initialization code becomes larger. An other reason may be that I had to initialize 95 cells in very low memory regions (If I won't forget it, I'll describe the reason for that later in this email). But I'm getting off the point. The malbolge code that uses arbitrary words not limited by the restrictions of malbolge to use only ASCII code that correspondends to an instruction (instructions are decrypted by xlat1 in the original interpreter, so I will call this the limits by xlat1) has to be as short as possible, so immutable NOPs are no option here. The trick is to use the data register to control program flow while the program does only consists of single commands followed by i (JMP/BRANCH instruction) for each of the other commands once. So we have somewhere ji (modify data register (I may call this operation "DATA" later) and JMP) and somewhere else pi (perform CRAZY operation and JMP) and so on. This principle will be softed a bit, but thats the general strategy. The JMP won't get modified during execution and the DATA/CRAZY/... commands will be restored immediately after each execution - I'll describe this a little bit later. I put the DATA/CRAZY/... commands at a position with a short cycle in xlat2 so the effort for restoring the commands will be slight. I haven't used a name for these command-JMP-pairs yet and can't remember that I saw one in the Japanese paper (which is quinte general - code analysis of 99 bottles was much more helpful than trying to translate the paper.) but I think I could call these command-JMP-pairs just CMDs.

So, how do we write a program? Well, I wrote the address of the CMD that has to be executed, followed by the data that has to be modified (I'll call it operand), followed by the (address of the CMD)+1 alternately. (When I write "adreess", I'll always substract the number 1 from the real offset in the code, because the code and data register are moved after each operation, so after modifying one of these registers they are at the address I want at the next execution step). What happens: We assume that the code pointer points to any JMP that will be executed. The destination of the JMP is the address of CMD we wrote at the memory. Then the code pointer is moved there and the data register is incremented. Then the operation at this position will be executed with the data register at the operand. Then the code pointer moves to the JMP command and jumps to (CMD+1). This will evoke another execution of the JMP command. But this is not senseless because xlat2 will be used to decrypt the command before the JMP - so the executed command will be decrypted and can be executed again later.

The remaining problems: How do we use the same operand (same memory cell) with diffrent commands and: how can we build loops (counting up or down a variable and comparing it to another value is very expensive in malbolge. I first will describe loops:

We use xlat2 to write loops with a constant number of iterations. We use a NOP-command that is followed by a JMP, but the NOP command will turn to a DATA-command after some xlat2 encryptions.

For the data register we first write the address of this NOP-JMP-pair to memory, followed by an address where the data pointer (program flow) should continue if the loop is finished. Followed by a CMD which links to DATA, followed by the begin of the loop. (the restoring of the DATA for xlat2 has to be the first command in that loop. - It generally has to be the first command at DATA-branching-destinations). After some cycles the NOP-JMP-pair will become a DATA-JMP-pair and the branch is taken. In this case the JMP-destination of the loop-exit-point does not start with a restoring-operation for xlat2, because the DATA turned to be a NOP and that was exactly the initial state of the loop. We can use cycles of length 2, 4, 5, 6 and 9 for building loops. They can be nested, so factors of this are possible. By some xlat2-modifications before entering the loop it might be possible to build loops with other numbers of repetitions. If the loops are nested, we will need at least one NOP-JMP-pair for each loop. But this are only one bytes to be initialized (only the NOP that will turn to a DATA, because a JMP can already at the beginning stand everywhere we want it.)

So, how can we use an operand with different commands? We write an address to one CMD direct in front of the operand as usual. Then we write the address of a triple, containing one immutable NOP, the command and the JMP in front of this command. Depending on the address we start with our data register an other operation will be executed with the same operand. Which operation is executed should be stored by using xlat2 to a DATA-command (as for loops) so we can do a conditional branch after executing the command and restore the correct one. If some regions of the memory are used very often (because we need to access THIS damn operand) at very different positions of program flow it could be helpful to have a skip-command for the data-register-program-flow. We can use chain of immutable NOPs, followed by JMP for this.

That's the main thing.

To read a character at the data section I will have to restore the data pointer and cannot leave the command-sequence by a JMP during this, so there will be some more commands and immutable NOPs. 99 bottles of beer had the same problem, so I looked at that code. They found some good positions with acceptable xlat2 cycles. We need DATA to go to the data we want to read, CRAZY to read data, and DATA again to modify the data register to get back. With resprect to xlat2 they got something like DATA NOP NOP CRAZY DATA JMP. But the cycle length of xlat2 is 9 (or 6, I'm not sure at the moment) and CRAZY will turn into ROTATE after a while before it gets a CRAZY again. This ROTATE must not be executed during restoring, so restoring gets a bit complicated with jumping in at the second DATA-instruction (which is a NOP at this moment and modifying that CRAZY-command with xlat2 because of malbolges behavior with xlat2 while jumping.) I extended this by a further DATA command, because the data section of the quine is not a string where each character is followed by the correct back jump position (99 bootles of beer created such a string in memory). So I jump back (with the data register) somewhere to 33 and 126. In this area I wrote the correct back jump locations during initialization so with a second data I can really jump back. The back jump addresses are followed by an other address which will be used if the end of the datasection is reached: My initialization methods writes \127 to the end of the data section so having reached the end will change the program flow.

Here the memory dump of my quine after the initialization:

http://matthias-ernst.eu/malbolge/quine.html (Tooltips may be helpful.) (I also created a memory dump of the 99 bottles of beer program, but I'm not sure about the licence of this program.)

Memory cells, that are used as a destination for the data pointer and that are also modified during execution are used to print out a string - they are incremented by one to get the next character.

NOP DATA NOP NOP CRAZY DATA JMP (99 bottles) or the same with some more NOPs and DATA JMP attatched (quine) is used to read a character. The very long and complicated chain of instructions at the dump of the quine at 29225 is used to reset the pointer at 29342 after the data section has been printed out once and is only executed one time. So these commands are not immutable and needn't be generated in the initialization phase of the program.

At the dump of the quine you'll find one cell that is modified and used as a destination for the JMP command - this is the carry for the increment operation which points to C2 (end of program) or C2-1. It will cause to execute the JMP-command at offset 0, but depending on the carry it takes one or two NOPs so the data pointer will be at a diffrent position depending on the carry. With NOP-chains at these positions the distance between the resulting data pointer position can be increased. (See my description about the initialization of memory to get more details how to increment a value in malbolge.)

How to initialize (many) memory cells to arbitrary values?

To initialize memory we can write a command sequenze in malbolge that can't be reexecuted, because we only need the initialization once. (I suggest to name code that can be reexecuted "loop resistant", as the Japanese guys did; so the initialization code won't be loop resistant.) We'll have create the destination address (minus 1 or more) where we want to write a specific value in a memory cell to jump there with the data register and the value we want to CRAZY into the destination address must be written into the A register. To get it into the A register we just create it in an other memory cell. Maybe we have to set the memory cell to C1 first, because that is the only value which can be CRAZIED to any value with only one operation and the correct value in the A register. We'll need many instructions to create the value in the A register as well as we'll need some instructions to create the destination address. So we have to operate to the same memory cell again and again. To do so, we use a structure that is called "Data module" in the Japanese paper. It contains all the special constants C0, C1, C2, (C20 or C21) (C20 and C21 are 0t2222222220 and 0t2222222221; we will only need one of them in the data module) and maybe some other useful constants, as well as the data we want to read/write (the destination memory address). But the fundamental thing of a data module is that it contains it memory start address (minus one) as its last value. So we can NOP over the data we don't want to modify and ROTR/CRAZY the data we want to modify, never leaving the memory area of the data module by executing DATA at the last memory cell of the data module to jump back to its beginning.

The structure of the data module can be modified a bit: More addresses that point to the data module itself to move the D register faster than by NOPing. We also may change the address at the end of the module so we cannot jump back to the beginning directly if this won't be necessary. Let's have a look at the data module I used in the quine to initialize its memory:

(Well I don't find the file I've saved it to at the moment, so I use my notices from a sheet. The implementation may be changed in details, so don't wounder if you would analyse the code of my quine and it's a bit different there. But I guess/hope there won't be any differences at all.)

Memory address	value
140	C1
141	147
142	TMP (must only contain trits that are 0 or 1)
143	C2-0t222200
144	C2-0t 22200
145	C2-0t 2200
146	C2-0t 200
147	C2
148	DESTINATION
149	139
150	C0
151	C1
152	C21
153	C2
154	VALUE
155	152
156	149
157	146

The malbolge code that uses this data module to initialize the memory of the quine has been written automatically by a C program I wrote. The result were much more than 20k instructions and I didn't want to write this manually.

Note that I got the things I'll explain now from here: http://www.coltech.vnu.edu.vn/~hoangta/jvse2010/Sakai-JVSE2010.pdf

But how do we use this data module? If the current value of a memory cell can't be CRAZIED to the value we want we have to write C1 into the cell first. This can be done by the following instruction sequence: ROTR C1 CRAZY CELL CRAZY CELL

We first load C1 into A. Then we CRAZY this into the cell so it will only contain trits with the value 0 or 2. Then we crazy this value into itself and we'll get C1. So we cann use the data module to load C1, jump to DESTINATION and crazy there, get back to the data module (this could be a little bit tricky) and jump to DESTINATION again, use CRAZY again and the get back to the data module again. After that we use the second part of the data module to generate the VALUE we want to crazy into the cell. (0 and 1 of the generated data are swapped, so we only need to crazy once into the destination memory cell.)

How to create the value? We'll set VALUE to C1 (to save some instructions we may remove this step in the final code, because we assume that two memory cells that are initialized consecutively will contain a similar value, but it's easier to explain the creation of the value we want if the cell is set to C1 at the beginning). We'll create the value trit by trit, starting with the least significant one. After a trit has been generated, we use ROTR and then we'll generate the next trit. We know that our last trit is a 1. If we want to set it to zero (leaving all the other trits unchanged) we have to CRAZY C21, followed by C2 into it. All the other trits will be CRAZIED with 2 twice, so they will remain unchanged. The last trit will be set to 0 by the first CRAZY and stay 0 when the second CRAZY is done. To generate a 1 we don't do anything because we already have a 1 there. To generate a 2 we CRAZY with C20, followed by C2. The first CRAZY will leave the one at the end unchanged (but modify all the other trits so they can be set to their previous value by a CRAZY with C2), the second CRAZY operation will set the last triot to 2. Note that the order of CRAZYING with C20 and C2 doesn't matter. To load C20 into A we do: ROTR C1; CRAZY C20/C21 (it doesn't matter if we CRAZY into C20 or C21). To load C21 into A we do: ROTR C0; CRAZY C20/C21. Because this operations will cause MANY malbolge instructions, we have a link to C2/VALUE for CRAZYING C2 and ROTATING the value with very few NOPs and a link directly to the begin of this part of the data module after that link. If we are done, we use the last link to move to the cell with DESTINATION and then we can directly go to the destination and CRAZY our value there. Then we'll go back to the data module and increase the value of DESTINATION.

How to increase the value of destination? Well, this costs some instructions, so we finally will only increase it after some steps and use NOPs to move to the right distination while DESTINATION has not been increased yet. I found out that it would be the best to increase DESTINATION if it is at least 9 cells behind our real destination. Because we know the exact value of DESTINATION, we know the carry while incrementing the value and don't have to ROTATE it and check for carry 10 times. We simply do a tritwise increment to all the cells that will be affected by the carry. The cells from 142 to 145 determine which trits will be incremented tritwise and which won't. Trits that are set to 2 at these adresses won't be incremented, trits that are set to 0 or 1 will be incremented. The normal incrementation (used in the quine later) starts with C20 or C21 to incrmeent the last cell. After incrementation, it will be set to C20 or C21 depending on the occurrence of an overflow. JMPing to it will cause a diffrent value of NOPs, but thats only for interest in the quine to increment the pointer to the character that has to be printed out. Here we know the value in DESTINATION and the carries that will occur, so we just use this cell to determine the trits that will be incremented: We chose one of the cells 142-145 for the increment depending on the carries that will occur. Incrementation is done this way.

Clear TMP to C0 (by CRAZYING C1 into it). Load C2 into A (by ROTATING C2). CRAZY DESTINATION CRAZY TMP CRAZY CARRY(one of 142-145). CRAZY DESTINATION CRAZY TMP CRAZY CARRY(one of 142-145).

(This has been extracted from the 99 bottles of beer program. The paper and the presentation by the Japanese do not contain the successor in this optimized way, they describe it with more CRAZY instructions which is more expensive of course.)

I don't know how one could create this complicated (and optimized!) set of instructions, but it's really fantastic! After that TMP won't contain a trit with the value 2 and the 2s of the carry remain unchanged, the 0s and/or 1s will contain the value of the carry, which is fine if we only increment the last trit, rotate through the number and have to decide whether to increment the next trit or just rotate the number until the trit positions are correct. But here we can simply ignore if there are 0s or 1s created in our "carry" variable.

To set the destination to a specific start value, we just set it to C1 and generate the constant we need in the second part of the data module.

All we need to do is to create such a data module without having one. (Creating it at Offset 140 is a little bit more complicated / expensive than creating it in the area that can be addressed by preinitialized values (33-126), but in the quine we'll have to initialize this area to some specific values by using the data module which must not be destroyed during this process, so I decided placing it at the address 140. The 99 bottle sof beer program places the data module to a more comfortable area, because the initialized program won't need this memeory area any more.

If you are interested in a more detailed explanation of one of the steps I described here, you can simply write a mail to me. You can find my mail address at the Malbolge Quine page of my homepage, which is linked at the Malbolge article. I'm also inclined to publish the sources of the C programs I used to analyse the 99 bottles of beer program and to create the quine, especially the C code that generated the malbolge code that uses the data module to initialize the memory of the quine. But this is written as use-once-code, containing a mixture of German and English comments and variable names (or containing no comments the most time), not even being indented correctly. It contains many values hard coded and may be hard to understand and or adapt. I'm also inclined to publish the main routine of the quine (the values of the memory after initialization) in the form where I use mnemorics (but I haven't set the quine into public domain yet, so I would just place a link to my webspace here. (Thats the reason I only added a link to it in this Wiki; I may put it into public domain in a few month, but I want to be sure people know that I am the author so no one will be able to copy it and claim he wrote it, so I wait until it is a bit more known. I'm not thinkig about its licence at the moment, but I guess "public domain with attribution" would be something like creative commons or LGPL...)). But also with mnemorics instead of memory addresses (the version with the memory addresses is linked above) is not easy to understand. Honestly, not even I wasn't able to understand the code any more after I just wrote it down. But maybe you want it here however - then just write your wish to this page (or write me an email, I'm not sure when I'll look at this page again. Mail adress can be found at my homepage.)

I hope, that was understandable. 141.83.143.222 13:10, 15 December 2012 (UTC)