Archive

Posts Tagged ‘self reproducing code’

Paradoxes, self reproducing code, and bash

April 26th, 2010 3 comments

I was always fascinated by paradoxes. They are just shamelessly out there, messing with our minds, sending us one message: we’re logically irresolvable, don’t f*ck with us. As a child I really liked this one:

The statement below is true.
The statement above is false.

This is classical liar’s paradox. Each statement alone can be either true or false but when putting together they can’t be neither of them. The root cause for the paradox is it’s self-referencing. Many philosophers believed that these kind of paradoxes can be eliminated once we take all self-referencing expressions out of the language such as the word “this” or in our case “below” and “above” which reference each other, each indirectly references itself.

Then came Quine. Now, I’m not talking about ’93 shaolin monk, Kwai Chang Caine from “Kung Fu: The Legend Continues” (am I the only one to see the resemblance??). I’m talking about Willard Van Orman Quine. He studied indirect self-referencing and came up with a famous paradox known today as (surprise, surprise) Quine’s paradox. The paradox demonstrated that it’s impossible to eliminate all those kind of expressions, unless “severely crippling” the language.

As a tribute to Quine’s work, a special group of computer programs were named after him. Those programs do one thing: print their own source code, hence “self reproducing”. What are they good for ? nothing practically (unless you are a virus/worm maker), but they are fun and challenging. Quines can be written (for a fact) in any language that has the ability to output any computable string. If you ever studied computability, you suppose to understand what it means. Otherwise, it basically means all computer languages you’ve ever heard of.

So, before you see how it can be done, if you consider yourself a programmer, I’d advise to take a moment and try writing one. Just write the simplest program you can, in your favorite language, no restrictions whatsoever that takes no input and prints out it’s exact source code (without reading it’s source file upon execution).

In this page, there are examples for quines in many different languages. Some of them use special language/compiler commands, some just do the basic method of storing the source code as a string and print it in a way it would print the string along the commands used for it’s printing (if it still sounds mysterious, you can find relatively readable C quine on wikipedia).

Being unix/linux system engineer the time I found about quine, I chose bash. My first bash quine attempt was:

cat $0

Put this into a file and run it with bash. The output would be exactly it’s source: “cat $0”. This is however, cheating. I exploited the fact bash is a scripting language (source isn’t compiled). So here is another one which is fine by me:

echo $BASH_COMMAND

A lot of somewhat tedious shell quines I’m not going to explain can be found here. After checking them out, it wasn’t that exciting anymore.

Then I though to myself, why just printing it’s source ? why not modifying/executing it’s source ? and so I came with a new challenge: “The pid changer”. The challenge is to write a script that changes it’s own process id (re-executes itself), without reading it’s source file. To make the restriction a little more effective and prevent cheating: the script takes no input and MUST not read or open any file (except executing operating system commands). If you find loophole in my definition that allows you to cheat, I still won’t accept it.

It took me some time, but eventually I came up with a solution. It’s based on a really neat bash feature called function exporting. Here is my solution, notice: it’s not the quine itself, it’s the quine loader. The quine itself is the quine() function:

#!/bin/bash

quine()
{
kill -9 $PPID
echo Quine, my process id is $$
[ $num -gt 0 ] && num=$(( num-1 )) && bash -c quine
}

export num=10
export -f quine
bash -c quine

Let’s analyze. First, I define a function called quine. It kills it’s parent process, output it’s own process id, and then checks the value of $num (which wasn’t defined yet). If it’s greater than 0 it decreases it by one and executes a new shell with “quine” command string. Note that quine is not a name of file.

Then, the loader assigns the value 10 to “num” variable and exports it. The exporting means, that if a new shell is spawned, it would also know variable $num and export it too. Then, the loader exports the function quine (that’s the trick here) so the new shell would also know quine(). Finally it executes new shell with “quine” as a command string, the shell would determine it’s a function name and call it.

The parent killing isn’t necessary for the quine, but otherwise it would act as a fork bomb. Well, a linear one, but still fork bomb. The num variable as you probably figured out, works as a stop timer and it is not necessary as well.

I hope you enjoyed this post and learned something new. I sure did :)