Quines
I realised that computer science is a cool enough topic that it needs its own category. I spent most of my time making the icon than the actual content this time, and the icon isn't actually that good. I wanted an icon which conveys computer science, and I know that all scientists wear lab coats and have conical flasks full of green liquid, so they had to be there. I also know that drawing people is hard, especially the hands, so I chopped them out. But to convey the computer thing I couldn't think of much more than putting a monitor in there.
However, there is room for a nice segue from the icon to the topic of quines. When I was doing the computer screen, I thought it would be nice to have a real screen on there. At this point, many people go for a cheap shot at windows, or random mess. I thought it would be more fun to put a screenshot of what my screen looked like at the time, while editing the picture. Not a big issue, but suppose I decided that instead of the screenshot containing the half-finished picture, I wanted one containing the finished picture. The finished picture would have to contain a copy of itself, which contains a copy of itself, which contains a copy of itself, etc.
It is a bit like when you point a video camera at a screen which is showing what the camera is seeing, except even in that case, you start with a picture containing whatever the camera was showing before (say a bit of wall next to the tv screen), then the next frame (where there are probably roughly 30 frames per second) we get the picture of a tv with a picture of a wall, then the next frame we get the picture of a tv with a picture of a tv with a picture of a wall. And this continues, but we never quite get the original picture of the wall out completely (it becomes super small, and you can't see it... but you just have to know it is there).
A quine is basically the computer programmers version of this. You write a program, where the only thing the program does is prints out its output. So you might start like this:
my_program = "print my_program"
print my_program
Which when run would say:
print my_program
Which is nearly right, except we were missing the first line, we could then try extending it a bit:
my_program = "my_program = \"print my_program\"\nprint my_program"
print my_program
(for a non-programmer, a "\n" means newline, and a \" is the way of telling the compiler that the next " isn't ending the string, but a real literal inverted comma sign)
This version prints:
my_program = "print my_program"
print my_program
Which has the same problem - it gets most of the program, but doesn't get it all. You can probably see that extending the method this way will never get the desired program, so we need to be a bit tricky about it.
Here is my simple, but readable quine, written in ruby:
my_program = "my_program = REPLACE_ME\nputs my_program.sub('REPLACE_ME', my_program.inspect)"
puts my_program.sub('REPLACE_ME', my_program.inspect)
sub means substitute, and it takes the thing to find, and the thing to replace it with - it only does the first substitution. e.g. "hello".sub("l", "m") will give "hemlo".
inspect will write out a string the way you would write it in a program - so any " in the string are turned into \" and any newlines are turned into \n and it also puts a " at the start and end. e.g. "hello".inspect will give "\"hello\"".
So we first put the text of the program into the "myprogram" variable, except where we give the value of "myprogram" here, instead we set it to "REPLACEME". Then we print out "myprogram" after substituting "REPLACEME" with the inspected form of "myprogram".
So quines are typically just a fun thing that don't do much and aren't useful and you rarely have to consider them. But there is also a class of quines which I think are quite interesting. I didn't make this, but here is a zip file quine (from here). Unzip it, and you will get two files, one of which is a copy of the original zip file (so you can unzip it again and again).
Why is this so interesting? Well, one of the ways of getting around email filters that spammers use is to put the payload of their spam inside a zip file. So then obviously the antivirus/junk mail filter people will try to fight back by searching inside zip files. So as a programmer, if you are writing the search-inside-zip-file function, and you find another zip file inside the zip file, your initial response might be to check inside that zip file too. But being a programmer, you don't want to be duplicating code, so you just run your original search-inside-zip-file function to search inside the current zip file. Now, if you are faced with the zip file quine, your program is stuck inside an infinite loop.
It isn't like it is the end of the world - you just need to set a recursion limit to something reasonable that won't get in peoples way, but also won't crash your system if there is a limit. But the limit shouldn't be on depth, it should be a limit on the number of zip files unzipped (otherwise you might get beaten by an exponentially growing zip file, where each zip has 100 copies of itself, just with different names).
RSS