Home > Uncategorized > Paradoxes, self reproducing code, and bash

Paradoxes, self reproducing code, and bash

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 :)

About these ads
  1. April 28, 2010 at 5:19 pm | #1

    Very cool.

    Now the next step is a script that changes its own code and then runs it. I wonder how far it can get… (but don’t forget http://xkcd.com/534/ !!!)

  2. May 15, 2010 at 2:50 pm | #3

    Just want to say what a great blog you got here!
    I’ve been around for quite a lot of time, but finally decided to show my appreciation of your work!

    Thumbs up, and keep it going!

    Cheers
    Christian, iwspo.net

  1. May 1, 2010 at 2:34 am | #1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: