#reverse polish notation | Explore Tumblr posts and blogs

skyeqt · 8 months ago

Text

I wrote a quine, without strings, in a calculator

Okay so I should probably clarify some things, the calculator in question (dc) is more of a "calculating tool", it is built into most linux distributions, and it is a command line tool. I should also clarify "without strings", because dc itself does support strings, and I do actually use strings, however, I do not use string literals (I'll explain that more later), and I only use strings that are 1 character long at most.

So first of all, why did I decide to do this, well, this all started when I found a neat quine for dc:

[91Pn[dx]93Pn]dx

If you're curious about how this works, and what I turned it into, it'll be under the cut, for more technical people, you can skip or skim the first text block, after that is when it gets interesting.

So first of all, what is a quine, a quine is a computer program that outputs its own source code, this is easier said than done, the major problem is one of information, the process of executing source code normally means a lot of code, for a little output, but for a quine you want the exact same amount of code and output. First of all, let's explain dc "code" itself, and then this example. Dc uses reverse polish notation, and is stack-based and arbitrary precision. Now for the nerds reading this, you already understand this, for everybody else's benefit, let's start at the beginning, reverse polish notation means what you'd write as 1+1 normally (infix notation), would instead be written as 1 1 +, this seems weird, but for computers, makes a lot of sense, you need to tell it the numbers first, and then what you want to do with them. Arbitrary precision is quite easy to explain, this means it can handle numbers as big, or as small, or with as many decimal points as you want, it will just get slower the more complex it gets, most calculators are fixed precision, have you ever done a calculation so large you get "Infinity" out the other end? That just means it can't handle a bigger number, and wants to tell you that in an easy to understand way, big number=infinity. Now as for stack based, you can think of a stack a bit pile a pile of stuff, if you take something off, you're probably taking it off the top, and if you put something on, you're probably also putting it ontop. So here you can imagine a tower of numbers, when I write 1 1 +, what I'm actually doing is throwing 1 onto the tower, twice, and then the + symbol says "hey take 2 numbers of the top, add them, and throw the result back on", and so the stack will look like: 1 then 1, 1, then during the add it has nothing, then it has a 2. I'm going to start speeding up a bit here, most of dc works this way: you have commands that deal with the stack itself, commands that do maths, and commands that do "side things". Most* of these are 1 letter long, for example, what if I want to write the 1+1 example a little differently, I could do 1d+, this puts 1 on the stack (the pile of numbers), then duplicates it, so you have two 1s now, and then adds those, simple enough. Lets move onto something a little more complex, let's multiply, what if I take 10 10 * well I get 100 on the stack, like you may expect, but this isn't output yet, we can print it with p, and sure enough we see the 100, I can print the entire stack with f, which is just 100 too for now, I can print it slightly differently with n, I'll get into that later, or I can print with P which uhhhh "d", what happened there? Well you see d is character 100 in ASCII, what exactly ASCII is, if you don't know, don't worry, just think of it as a big list of letters, with corresponding numbers. And final piece of knowledge here will be, what is a string, well it's basically just some text, like this post! Although normally a lot shorter, and without all the fancy formatting. Now with all that out of the way, how does the quine I started with actually work?

From here it's going to get more technical, if you're lost, don't worry, it will get even more technical later :). So in dc, you make a string with [text], so if we look at the example again, pasted here for your convenience

[91Pn[dx]93Pn]dx

it makes one long string at the start, this string goes onto the stack, and then gets duplicated, so it's on the stack twice, then it's executed as a macro. In technical language, this is just an eval really, in less technical language, it just means take that text, and treat it like more commands, so you may see, it starts with 91P, 91 is the ASCII character code for [, which then gets printed out, not coincidentally, this is the start of the program itself. Now the "n" that comes afterwards, as I said earlier, this is a special type of print, this means print without newline (P doesn't use newlines either), which means we can keep printing without having to worry about everything being on separate lines, now what is it printing? Well what's on top of the stack, oh look, it's the copy of the entire string, which once again not coincidentally, is the entire inside of the brackets, so now we've already printed out the majority of the program, now dx is thrown on the stack, which as you may notice is the ending of the program, but we won't print it yet, we'll first print 93 as a character, which is "]", and then print dx, and this completes the quine, the output is now exactly the same as the input. Now, I found this some time ago, and uncovered it again in my command history, it's interesting, sure, but you may notice it's not very... complicated, the majority of the program is just stored as a string, so it already has access to 90% of itself from the start, and just has to do some extra odd jobs to become a full quine, I wanted to make this worse. I started modifying it, doing some odd things, which I won't go into, I wanted to remove the numbers, replacing it entirely with calculations from numbers I already have access to, like the length of a string, this wasn't so hard, but then I hit on what this post is about "can I make this without using string literals"

Can I make this without using string literals?

Yes, I can! And it took a whole day. I'll start by explaining what a string literal is, but this will largely be the end of my explaining, from here it's about to get so technical and I don't want to spend all day explaining things and make this post even longer than it's already going to be. A string literal is basically just the [text] you saw earlier, it's making a string by just, writing out the string. In dc there's only 1 other way to make a string, the "a" command, which converts a number, into a 1 character string, using the number as an ASCII character code. Strings in dc are immutable, you can only print, execute, and move them around with the usual stack operations, you cannot concatenate, you cannot modify in any way, the only other things you can do with a string, is grab the first character, or count the characters, but as I just explained, our only way to make strings creates a 1 character string, which cannot be extended, so the first character is just, the entire thing, and the length is always 1, so neither of these are useful to us. So, now we understand what the restriction of no string literals really is (there are more knock on restrictions I'll bring up later), let's get into the meat of it, how I did it.

So I've just discussed the way I'll be outputting the text (this quine will need text, since all the outputting commands are text!), with the "a" command and the single character strings it produces, let's now figure out some more restrictions. So any programmers reading this are going to be horrified by what I'm about to say. If I remove string literals, dc is no longer Turing Complete, I am trying to write a quine in a language (subset) that is not Turing Complete, and can only output 1 character at a time**. You can't loop in dc, but you can recurse, with macros, which are effectively just evaling a string, you can recurse, since these still operate on the main stack, registers, arrays, etc, they can't be passed or return anything, but this doesn't matter. Now I cannot do this, because if I only have 1 character strings via "a" then I can't create a macro that does useful work, and executes something, since that would require more than 1 command in it. So I am limited to only linear execution***. Now lets get into the architecture of this quine, and finally address all these asterisks, since they're finally about to be relevant, I started with a lot of ideas for how I'd architect these, I call these very creatively by their command structure, dScax/dSax, rotate-based execution, all-at-once stack flipping, or the worst of them all, LdzRz1-RSax (this one is just an extension of rotate-based execution), I won't bother explaining these, since these are all failed ideas, although if anybody is really curious, I might explain some other time, for now, I'll focus on the one that worked, K1+dk: ; ;ax, or if you really want to try to shoehorn a name, Kdkax execution, now, anybody intimately familiar with dc, will probably be going "what the fuck are you doing", and rightly so, so now, let's finally address the asterisks, and get into what Kdkax execution actually means, and how I used it.

*"Most commands are 1 character long, but there are exceptions, S, L, s, l, :, ; and comparisons, only : and ; are relevant here, so I won't bother with the rest, although some of the previous architectures used S and L as you may have seen. : and ; are the array operations, there are 256 arrays in dc, each one named after a character, if I want to store into array "a" I will write :a, a 2 character sequence, same for loading from array "a" ;a, I'll get into exactly how these work later **I can only output 1 character at a time with p, P, and n, but f can output multiple characters, the only catch being it puts a newline between each element of the stack, and because I can only put 1 character into each stack element, it's a newline between each character for me (except for numbers). I'll get into what this means exactly later ***I can do non-linear execution, and in fact, it was required to make this work, but I can only do this via single character macros, which is, quite the restriction to put it lightly

So I feel like I've been dancing around it now, what does my quine actually look like, well, I wanted to keep things similar to the original, where I write a program, I store it, then I output it verbatim, with some cleanup work. However, I can't store the program as strings, or even characters, I instead need to store it as numbers, and the easiest way to do this, is to store it as the char codes for dc commands, so if I want to execute my 1d+ example from before, I instead store it as 49 100 43, which when you convert them back to characters, and then execute them in sequence, to do the same thing, except I can store them, which means I can output them again, without needing to re-create them, this will come in handy later. So, well how do I execute them, well, ax is the sequence that really matters here, and it's something all my architectures have in common, it converts them to a character, then executes them, in that order, not so hard, except, I'm not storing them anymore, well then if you're familiar with dc, you might come across my first idea, dScax, which, for reasons you will understand later, became dSax, this comes close to working, it does store the numbers in a register, and execute them, but this didn't really end up working so well. I think the next most important thing to discuss though, is how I'm outputting, as I mentioned earlier "f" will be my best friend, this outputs the entire stack, this is basically the whole reason this quine is possible, it's my only way of outputting more characters from the program, than the program itself takes up, since I can't loop or recurse, and f is the only character that outputs more than 1 stack element at once, it is my ticket to outputting more than I'm inputting, and thereby "catching up" with all the characters "wasted" on setup work. So now, as I explained earlier, f prints a newline between each stack element, and I can only create 1 character stack elements, and because in a quine the output must equal the input, this also means the input must equal the output. And because I just discovered an outputting quirk, this means my input must also match this quirk, if I want this to be a quine, so, my input is limited to 1 character, or 1 number, per line, since this is the layout my stack will take, and therefore will be the layout of my output. So what does this actually mean, I originally thought I couldn't use arrays at all, but, this isn't true, the array operations are multiple character sequences yes, but turns out, there actually are multiple characters per line, there's also a linefeed character. And since there is an array per ASCII character, I am simply going to be storing everything in "array linefeed"! So now, with all of this in mind, what does the program actually look like.

Let's take a really simple example, even simpler than earlier, let's simply store 1 and then print it, this seems simple enough, 1p does it fine, but, lets convert it to my format, and it's going to get quite long already, in order to prevent it getting even longer, I'll use spaces instead of newlines, just keep in mind, they're newlines in the actual program

112 49 0 k K 1 + d k : K 1 + d k : 0 k K 1 + d k ; K 1 + d k ; 0 k K 1 + d k ; a x K 1 + d k ; a x

now, what the fuck is going on here, first of all, I took "1p" and converted both characters into their character codes "49 112" and then flipped them backwards (dw about it), then, I run them through the Kdkax architecture. What happens is I initialise the decimal points of precision to 0, then, I increment it, put it back, but keep a copy, and then run the array store, keep in mind, this is storing in array linefeed, but what and where is it storing? Its index is the copy of the decimal points of precision I just made, and the data it's storing at that index, is whatever comes before that on the stack, which, not coincidentally, is 49, the character code for the digit "1", then I do the same process again, but this time, the decimal points of precision is 1, not 0, and the stack is 1 shorter. So now, I store 112 (the character code for p), in index 2 of array linefeed, now you may notice, the array is looking the exact same as the original program I wanted to run, but, in character code form, it is effectively storing "1p", but as numbers in an array, instead of characters in a string. I then reset the precision with 0k, and start again, this time with the load command, which loads everything back out, except, now flipped, the stack originally read 49 112, since that's the order I put them on, the top is 49, the last thing I put on, but after putting them into the array, and taking them back out, now I'm putting on 112 last instead, so now the stack reads 112 49, which happens to be the exact start of the code, this will be important later. For now, the important part is, the numbers are still in the array, taking them out just makes a copy, so, this time I take them out again, but rather than just storing them, I convert them to a character, and then execute them, 49 -> 1 -> 1 on the stack, 112 -> p -> print the stack, and I get 1 printed out with the final x. Now this may not seem very significant, but this is how everything is going to be done from here on out.

So, what do I do next? Well now's time to start on the quine itself, you may have noticed in the last example, I mentioned how at one point, the stack exactly resembles the program itself, or at least the start of it, this is hopefully suspicious to you, so now you may wonder, what if my program starts with "f" to print out the entire stack? Well, I get all the numbers back, i.e. I get the start of the file printed out, and this will happen, no matter how many numbers (commands) I include, now we're getting somewhere, so if I write fc at the start of my program (converted into character codes and then newline separated) then I include enough copies of the whole Kdkax stuff to actually store, load, and execute it, then I can execute whatever I want, and I'll get back everything except the Kdkax stuff itself, awesome! So now we come onto, how do I get back the "Kdkax stuff", and more importantly, what are my limitations executing things like this, can I just do anything?

Well, put simply, no, I cannot use multicharacter sequences, and I actually can't this time, because it's being executed as a single character macro, I don't have a newline to save me, and I just get an error back, so okay that's disappointing. This multicharacter sequence rule means I also can't input numbers bigger than 1 digit, because remember, the numbers get converted into characters and then executed, and luckily, executing a number, just means throwing it on the stack, so I'm good for single digit numbers. Then in terms of math (I know, this is a post about a calculator and only now is the maths starting), I can't do anything that produces decimals, since the digits of precision is constantly being toyed with, and I also can't use the digits of precision as a storage method either, because it's in use. I can actually use the main stack though! It's thankfully left untouched (through a lot of effort), so I'm fine on that front. Other multicharacter sequences include negative numbers, strings (so I can't cheese it, even here), and conditionals.

So it was somewhere around here, I started to rely on a python script I wrote for some of the earlier testing, and I modified it to this new Kdkax architecture when I was confident this was the way forwards. It converts each character into a character code, throws that at the start, and then throws as many copies of the store, load, and execute logic as I need to execute the entire thing afterwards. This allows me to input (mostly) normal dc into the input, just keeping in mind that any multicharacter sequences will be split up. So now I can start really going, and I'll speed up from here, effectively, what I need to do, is write a dc program, that can output "0 k", then "K 1 + d k :" repeated as many times as there are characters in my program, then "0 k" again, then "K 1 + d k ;" repeated just as many times, then "0 k" again, then "K 1 + d k ; a x" also repeated just as many times, without using strings, multicharacter sequences, loops, branches, recursion, any non-integer maths, with a newline instead of a space in every sequence above. Doable. The program starts with fc, like I mentioned, this prints out all the numbers at the start, and leaves us with a clean stack, I'll explain in detail how I output the "0 k" at the start, and leave the rest as an exercise to to the reader. I want to do this by printing the entire stack, so I want to put it on backwards, k first, k is character code 107 in decimal, and I can't input this directly, because I can't do anything other than single digit numbers, so maths it is, here I abuse the O command, which loads the output base, which is 10 by default, and I then write "OO*7+a", which is effectively character((10*10)+7) written in a more normal syntax, this creates "k" on the stack, and then I can move onto 0, for which I write "0", since a number just puts itself on the stack, no need to create it via a character code, I can just throw it on there, keep in mind this will all get converted to 79 79 42 55 43 97 48, but the python script handles this for me, and I don't need to think about it. The stack now reads "0 k" and I can output this with f, and clear the stack, I then do the same deal for "K 1 + d k :", the next "0 k", "K 1 + d k ;" but here I do something a little different, because I want to output "K 1 + d k ; a x" next (after the "0 k" again), I don't clear the stack after outputting "K 1 + d k ;", and instead, I put "a x" on the stack, and then use the rotate stack commands to "slot it into place" at the end, this is a neat trick that saves some extra effort, it makes printing the "0 k" in between more difficult, but I won't get into that. For now the important part, is the output of my program now looks something like this "(copy of input numbers) 0 k K 1 + d k : 0 k K 1 + d k ; 0 k K 1 + d k ; a x" this is amazing, this would be the correct output, if my program was only 1 character long at this point, now keep in mind I'm writing non-chronologically, so my program never actually looked like this, but if you're following along at home you should have this at this point:

fcOO*7+a0fcaO5*8+aOO*7+aOO*aO4*3+aO4*9+a355**afcOO*7+aOO*aO4*3+aO4*9+a355**af0nOanOO*7+anOanOO*2O*+aOO*3-a08-R08-Rf

definitely longer than 1 character, you might think at this point, it's just a matter of spamming "f" until you get there, but unfortunately, you'll never get there, every extra "f" you add, requires an extra copy of the store, load, execute block in the program, so you're outpaced 3 to 1, so what do you do about this? You print 4 at once! I want the stack to look like "K 1 + d k : K 1 + d k : K 1 + d k : K 1 + d k :" and similarly for the other steps, and then I can spam f with greater efficiency! This was somewhat trivial for the first 2, but for the ax, because I'm using the rotate to push it at the end, I need to do this 4 times too, with different rotate widths, not too hard. And now, I can finally get there, but how many times do I spam f? Until my program is exactly 3/4s printing on repeat, which makes sense if you think about it, and below, is finally the program I ended up with

fcOO*7+a0fcO5*8+aOO*7+aOO*aO4*3+aO4*9+a355**aO5*8+aOO*7+aOO*aO4*3+aO4*9+a355**aO5*8+aOO*7+aOO*aO4*3+aO4*9+a355**aO5*8+aOO*7+aOO*aO4*3+aO4*9+a355**affffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffcOO7+a0fcO5*9+aOO*7+aOO*aO4*3+aO4*9+a355**aO5*9+aOO*7+aOO*aO4*3+aO4*9+a355**aO5*9+aOO*7+aOO*aO4*3+aO4*9+a355**aO5*9+aOO*7+aOO*aO4*3+aO4*9+a355**affffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff0nOanOO*7+anOanOO*2O*+aOO*3-a08-R08-ROO*2O*+aOO*3-a082-R082-ROO*2O*+aOO*3-a083-R083-ROO*2O*+aOO*3-a084-R084*-Rffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

I say finally, but this is actually pre-python script! The final program I actually ended up with will instead be included in a reblog, because it really needs its own cut. But anyway, this was how I wrote a quine, for a calculator, without using string literals.

#programming #quine #linux #dc calculator #computing #linux utils #program #quine programming #coding #python #there was only brief use of python in here #and I didn't even include the code for that #but whatever #this took me a whole day to make #and I am so so proud of it

4 notes · View notes