Monday is President's Day and Cadence is off so, as has become traditional, I write about something off-topic the day before. Today's topic is self-reproducing programs. A self-reproducing program is also known as a Quine.

The term Quine was coined by Doug Hofstadter in his amazing 1979 book Gödel, Escher, Bach. This discusses the philosopher Orman Quine who studied self-reference in the 1930s in the wake of Gödel's incompleteness theorems. These used self-reference to produce a truly unexpected result, disproving Hilbert's second problem that asked for a proof that mathematics was both consistent (no statement could be proved both true and false at the same time) and complete (all true statements could be proved starting from the axioms). Gödel proved that this could not be done: either mathematics is inconsistent, or there are true statements that cannot not be proved. Anyway, that's not today's topic.

A self-reproducing program is a program that takes no input, and produces as output an exact copy of its source code. The requirement for no input stops the obvious solution of simply copying the file containing the source code. When I first heard about this, I thought "that's obviously impossible". If you can program, and have never come across this before, then I encourage you to stop reading and go and try and do it yourself. You will get an immense feeling of satisfaction if you manage to work out how to do it.

According to Wikipedia:

The first-known such program [was] written in Atlas Autocode at Edinburgh in the 1960s by the University of Edinburgh lecturer and researcher Hamish Dewar.

Hamish was my first PhD supervisor, and one of the best programmers I have ever worked with. That's him on the right in this 2017 picture, all of us looking a lot older than back when I was a postgraduate student (the other two are Kathy Humphry and Malcolm Atkinson who were also at the computer science department at Edinburgh in that era).

Quines

The reason self-reproducing programs are called Quines, apart from just being a tribute to one of the most significant philosophers of the last couple of centuries, is due to this paradox invented by him:

"Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.

This is basically the way self-reproducing programs work:

"source code" source code

Of course, it can't be quite that simple since programming requires a little more scaffolding than that. For example, here is a Quine in the C programming language, that is very close to this structure (34 is the decimal representation of the ASCII " character):

main() { char *s="main() { char *s=%c%s%c; printf(s,34,s,34); }"; printf(s,34,s,34); }

and here is one in Python (you can write much shorter Quines in Python, as it happens, but this one shows the basic structure):

x = ['print "x =", x', 'for m in x: print m']
print "x =", x
for m in x: print m

Ouroboros

You can go further. There is a sort of more complex Quine known as an Ouroboros (a snake eating its tail) where a program in one language (say Java) that outputs not its own source code but the source code for a second program in a different language (say C), which when run outputs the first Java source code. This has been taking to a truly amazing extreme at Quine Relay - An uroboros program with 100+ programming languages which presents a chain of (currently) 128 programming languages, each of which outputs the next one when run, with the last looping back to produce the original program. Of course, it doesn't actually matter which language you start with, after 128 you'll be back where you started.

Do you know what a single-event-upset (SEU) is in a chip? It is when a particle, typically a high energy neutron in a cosmic ray, hits the chip and causes a large enough voltage swing as to cause the chip to malfunction. You can read much more in my post Soft Error Rates in Satellites and Cars. This is a really big problem in space vehicles such as satellites. The solution is to build radiation-hardened, or rad-hard, chips, a mixture of a special process that is especially immune to these effects, and circuit design and layout that makes the design robust even in the face of SEUs, ensuring that they can't cause the circuit to malfunction.

So if you think writing a Quine is too easy, try writing a rad-hard quine. This is a Quine that can have any single character removed, and still reproduces its source code, perfectly (including the deleted character). Yes, it's possible.

Obfuscated C

For nearly 30 years there has been a competition known as The International Obfuscated C Code Contest. The goal is to write the most Obscure/Obfuscated C program within the rules. Over the years there have been some truly remarkable programs, such as an unbelievably brief Basic interpreter in about 25 lines ("syntax errors are indicated by 'core dumped'"). To give you a flavor, here is one of last year's winners, a program that counts the number of words in a document and prints the total. This is basically the wc utility on Unix written in a single line of 128 characters.

e,n,j,o,y;main(){for(++o;n=-~getchar();e+=11==n,y++)o=n>0xe^012>n&&'`'^n^65?!n:!o ++j:o;printf("%8d%8d%8d\n",e^n,j+=!o&&y,y);}

In the spirit of the competition, there is often a winner for "best abuse of the rules". In 1994, Szymon Rusinkiewicz submitted the world's smallest Quine. It turns out that an empty file is a valid C program that when compiled does nothing, and so produces no output, thus correctly reproducing its source code exactly. By the way, I thought Szymon Rusinkiewicz might be an "obfuscated" name, in the spirit of the contest, but no, that's his real name—he's a CS prof at Princeton, although he was at MIT when he "wrote" this program.

President's Day

Monday is President's Day. It originally commemorated George Washington's birthday, February 22. It is now always the third Monday in February. Some states call the holiday Washington's and Lincoln's Birthday, since Lincoln was born on nearby February 12. It is often called Presidents' Day (with the apostrophe moved) to commemorate all Presidents.

Anyway, Cadence is closed on Monday in the US, and Breakfast Bytes will return on Tuesday. Enjoy the long weekend.

Sign up for Sunday Brunch, the weekly Breakfast Bytes email.