DEV Community: Darshan A S

MultiQuine. Weaving the web of Quines

Darshan A S — Sun, 18 Aug 2024 08:08:56 +0000

Previously, we've seen how to construct QuineRelays by leveraging the existence of Introns. Now, prepare to have your minds blown once again as we unlock the next level of Quine wizardry: MultiQuines.

We start by saying what a Bi-Quine (or more generally a MultiQuine) is. To begin, here is what it is not: a Bi-Quine is not a program that prints a second program, which in turn prints the first again (actually, it's that, but things are a bit more subtle). That would just be a QuineRelay and it is too easy to do (we have proved the existence of such, using Introns).

A Bi-Quine is a very interesting kind of program: when run normally, it is a Quine. But if it is called with a particular command line argument, it will print a different program, its "sibling". Its sibling is also a Quine, but in a different programming language, so its sibling prints its own source code when run normally. But when run with a particular command line argument, the sibling prints the source code of the original program. So in effect, a Bi-Quine is a set of two programs each of which is able to print either of the two.

Essentially, MultiQuines are set of n programs, in n different languages such that:

Each program is a valid Quine and outputs itself when executed with no input.
Each program can output the source of any other program in the set, according to the command line argument it is passed. Think Fully-Connected-Graph here.

All MultiQuines are QuineRelays, but all QuineRelays are not MultiQuines.

Note that cheating is not allowed: the command line arguments must not be too long — passing the full source of a program is considered cheating.

5th-order MultiQuine (PentaQuine)

Here's a 5th-order MultiQuine made up of Python, Perl, F#, newLISP, and C.
GitHub

25th-order MultiQuine

A MultiQuine consisting of 25 languages, from Ruby, Octave, CoffeScript, JavaScript, Python and 20 more.
GitHub

One of the characters in Six Degrees of Separation, a popular play and film by an American playwright John Guare states:

I read somewhere that everybody on this planet is separated by only six other people. Six degrees of separation between us and everyone else on this planet. The President of the United States, a gondolier in Venice, just fill in the names. I find it extremely comforting that we're so close. I also find it like Chinese water torture, that we're so close because you have to find the right six people to make the right connection... I am bound, you are bound, to everyone on this planet by a trail of six people.

This phenomenon is also called The small world theory. Facebook's data team released two papers in November 2011 which document that amongst all Facebook users at the time of research (721 million users with 69 billion friendship links) there was an average distance of 4.74
It had come down from 5.28 in 2008. And by 2016, the separation distance was down to 4.57

Similarly, MultiQuines are a special case of the small world theory. A world where a population of self-sustainable Quines are linked to each other by just one degree of separation.

Writing your own MultiQuine

The secret behind MultiQuines lies in the clever use of, you guessed it, Introns - those non-coding regions we explored earlier. Each MultiQuine program contains n data sets: one for its own code and one for each of its siblings. When executed with a specific argument, a MultiQuine uses the corresponding data set to generate the source code of the requested sibling. It then uses its own data sets to replicate the introns within the sibling's code, ensuring the cycle of transformation continues seamlessly.

Let's take the outline of the QuineRelay we build last time:

Python:

d1 = "code part of Python"
d2 = "code part of JavaScript"
print('d1 =', repr(d1)); print('d2 =', repr(d2)); print(d2)

JavaScript:

d1 = "code part of Python"
d2 = "code part of JavaScript"
console.log(`d1 = ${JSON.stringify(d1)}`); console.log(`d2 = ${JSON.stringify(d2)}`); console.log(d1 + '');

Now, we want to read the command line argument and decide to print d1 or d2

In Python, sys.argv is the array that holds these.
If it says "js" we output the JavaScript MultiQuine
If it says "py" or empty we output the same Python MultiQuine back.
Note. We are choosing to ignore any other values and just output the same Python Quine
Make sure to import sys and also check if sys.argv does have an argument passed in.

Python:

d1 = "code part of Python"
d2 = "code part of JavaScript"
import sys; print('d1 =', repr(d1)); print('d2 =', repr(d2)); print(d2 if len(sys.argv) > 1 and sys.argv[1] == 'js' else d1)

In Javascript, process.argv is the array that holds these.
Use the same conditions to modify the JavaScript MultiQuine as below:

JavaScript:

d1 = "code part of Python"
d2 = "code part of JavaScript"
console.log(`d1 = ${JSON.stringify(d1)}`); console.log(`d2 = ${JSON.stringify(d2)}`); console.log(process.argv.length > 2 && process.argv[2] == 'py' ? d1 : d2);

Now, all we have to do is, copy the final code part to each other's d1 and d2 variables:

Python: Try it online! (Play with argument py or js)

d1 = "import sys; print('d1 =', repr(d1)); print('d2 =', repr(d2)); print(d2 if len(sys.argv) > 1 and sys.argv[1] == 'js' else d1)"
d2 = "console.log(`d1 = ${JSON.stringify(d1)}`); console.log(`d2 = ${JSON.stringify(d2)}`); console.log(process.argv.length > 2 && process.argv[2] == 'py' ? d1 : d2);"
import sys; print('d1 =', repr(d1)); print('d2 =', repr(d2)); print(d2 if len(sys.argv) > 1 and sys.argv[1] == 'js' else d1)

JavaScript: Try it online! (Play with argument py or js)

d1 = "import sys; print('d1 =', repr(d1)); print('d2 =', repr(d2)); print(d2 if len(sys.argv) > 1 and sys.argv[1] == 'js' else d1)"
d2 = "console.log(`d1 = ${JSON.stringify(d1)}`); console.log(`d2 = ${JSON.stringify(d2)}`); console.log(process.argv.length > 2 && process.argv[2] == 'py' ? d1 : d2);"
console.log(`d1 = ${JSON.stringify(d1)}`); console.log(`d2 = ${JSON.stringify(d2)}`); console.log(process.argv.length > 2 && process.argv[2] == 'py' ? d1 : d2);

There you go. It's a valid 2nd-order MultiQuine (Bi-Quine)

If you wanna play around more, David Madore has written a C/Perl Bi-Quine. For fun, only the C version is given out; if you want the Perl version you will have to run the program with the magic word: xyzzy as the argument. In the C version, c_data is the main data set and perl_data is an intron; in the Perl version, of course, things are reversed.

One peculiar thing, you might notice in the above C/Perl example, is that the data section is encoded as an array of numbers. This is a common trick to avoid having to deal with nested quoting problem, while writing Quines. In fact if one wanted to, each data set could use a different coding mechanism, or even an encryption mechanism, although you'd need a key to decrypt it in the code section.

Stay tuned for the next post on Radiation-Hardened-Quine!

Sources and references:

Quines (self-replicating programs), blog by David Madore.
Pentaquine, GitHub repo by Rijnard van Tonder.
Quine Chameleon, GitHub repo by Lu Wang.
The small world theory, wiki page.
Six Degrees of Separation - Quote, Youtube video clip from the movie Six Degrees of Separation.
Quine, Intron, QuineRelay, MultiQuine, set of four self-referencing blogs that link to each other in a fully-connected graph.

QuineRelay: Birth of the Quine serpent

Darshan A S — Wed, 07 Aug 2024 14:13:59 +0000

In the previous adventures of the Quine blog series, we explored how to write our own Quines and Introns. Today we will see what QuineRelays are and how you can leverage Introns to create them.

Imagine a circle of programs, each written in a different language. Each program in this circle has a single purpose: to print the source code of the next program in the sequence. The last program then closes the loop by printing the source code of the very first program.

Essentially, QuineRelays are a set of n programs, in n different languages such that:

Each program outputs the source of the next.
The last program outputs back the source of the first one. Think Circular-Linked-List here. The last example is a mind-blower!

Let's see some examples to grasp the concept better.

2nd-order relay

This 2nd-order QuineRelay features a JavaScript program that prints a Python program, which then prints the original JavaScript program back. It's a dynamic duo of self-replication.
JavaScript → Python ⥀

JavaScript: Try it online!

console.log((q=_=>`print(${JSON.stringify(`console.log((q=${q+[]})())`)})`)())

Python: Try it online!

print("console.log((q=_=>`print(${JSON.stringify(`console.log((q=${q+[]})())`)})`)())")

3rd-order relay

Things get even more interesting with a 3rd-order QuineRelay. This one starts with a Haskell program, which outputs a Python program, which outputs a Ruby program, and finally, the Ruby program loops back to the original Haskell program.
Haskell → Python2 → Ruby ⥀

Haskell: Try it online!

q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']
main=q "q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']" "def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'" "def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end"

Python2: Try it online!

def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'
q("def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'","def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end","q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']")

Ruby: Try it online!

def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end
q("def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end","q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']","def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'")

4th-order relay

Here's a 4th-order QuineRelay: Ruby → Java → C# → Python ⥀
GitHub

Across cultures, there are several shared symbolisms. One of them is the Ouroboros, which has references in Egyptian, Greek, Roman, Hindu, Siberian, Norse, African, and South American mythologies. The Ouroboros is an ancient symbol depicting a serpent or dragon consuming its own tail, representing the eternal cycle of creation and destruction.

In Norse mythology, Jörmungandr is a colossal serpent, the middle child of Loki and the giantess Angrboða. Odin cast Jörmungandr into the ocean surrounding Midgard (the realm of humans), where the serpent grew so immense that it encircled the world and grasped its own tail. As a result of it surrounding Midgard (the Earth) it is referred to as the World Serpent - Ouroboros. Jörmungandr releasing its tail is one of the signs of the beginning of Ragnarök (the final battle of the world).

Quine relays embody this symbolism quite neatly, as each program in the cycle gives rise to the next, only to be reborn in the end, and hence are nicknamed Ouroboros programs.

128th-order Ouroboros relay

Hold on to your seats. Here's a 128th-order Ouroboros QuineRelay. Yes, you read that right. 128 !!!
Ruby → Rust → Scala → ... (120 others) ... → Python → R → Ratfor → rc → REXX ⥀
GitHub

As if this wasn't impressive enough, it includes an easter egg. The original Ruby code when zoomed out contains an Ouroboros dragon!

Writing your own QuineRelay

Let's start the Python intron we wrote earlier and try to turn it into a 2nd-order QuineRelay.

Python Intron: Try it online!

intron = 'wubbalubbadubdub'
data = "print('intron =', repr(intron)); print('data =', repr(data)); print(data)"
print('intron =', repr(intron)); print('data =', repr(data)); print(data)

Using the magic of introns, we can now easily put the code part of a sibling Quine of a different language into the intron. Producing a program of the form:

Python:

intron = "code part of sibling"
data = "code part of self"
print('intron =', repr(intron)); print('data =', repr(data)); print(data)

Since, each variable is just, acting as data of a different Quine. Let's rename data and intron, into d1 and d2 respectively.

Python:

d1 = "code part of self"
d2 = "code part of sibling"
print('d1 =', repr(d1)); print('d2 =', repr(d2)); print(d1)

Now, d2 acts as an intron, but the above program still tried to print code part of self. To have it print source of the next, let's print(d2) instead of print(d1) at the end.

Python:


d1 = "code part of self"
d2 = "code part of sibling"
print('d1 =', repr(d1)); print('d2 =', repr(d2)); print(d2)

We already know that the contents of d1 is just a copy of line 3. But we don't yet have the contents of d2.

Say, we wanted to create a QuineRelay with JavaScript. Let's write a similar intron in JS.

JavaScript:

d1 = "code part of sibling"
d2 = "code part of self"
console.log(`d1 = ${JSON.stringify(d1)}`); console.log(`d2 = ${JSON.stringify(d2)}`); console.log(d1);

Now, line 3 of the above JS intron, is the code of the sibling program we wanted!
Paste each other's code as introns in the other.
Note. We need to add d1 + '' in js to avoid some quoting mismatches

Python: Try it online!

d1 = "print('d1 =', repr(d1)); print('d2 =', repr(d2)); print(d2)"
d2 = "console.log(`d1 = ${JSON.stringify(d1)}`); console.log(`d2 = ${JSON.stringify(d2)}`); console.log(d1 + '');"
print('d1 =', repr(d1)); print('d2 =', repr(d2)); print(d2)

JavaScript: Try it online!

d1 = "print('d1 =', repr(d1)); print('d2 =', repr(d2)); print(d2)"
d2 = "console.log(`d1 = ${JSON.stringify(d1)}`); console.log(`d2 = ${JSON.stringify(d2)}`); console.log(d1 + '');"
console.log(`d1 = ${JSON.stringify(d1)}`); console.log(`d2 = ${JSON.stringify(d2)}`); console.log(d1 + '');

There you go. It's a proper 2nd order QuineRelay! A Python program, that prints a JavaScript program, that prints the original Python program back in a cycle.

Creating a QuineRelay is an exercise in creative coding and understanding how different languages represent and manipulate strings. It involves weaving together introns from various programs, each containing the code to replicate its next neighbour.

At its core, an nth-order relay is a game of n clever ways to escape quotes across n programming languages.

Stay tuned for the next post on MultiQuine!

Sources and references:

Ouroboros programs, wiki page.
A Third Order Quine in Three Languages, blog by sigfpe.
Chain Quine, GitHub repo by Ibragimov Ruslan.
128 Quine Relay, GitHub repo by Yusuke Endoh.
QuineRelay: Birth of the Quine serpent, self-referencing blog where a word in each n-order example hyperlinks to the next, cyclically. (May not work in dev.to; checkout the canonical blog)
Jörmungandr, wiki page.
Ouroboros, wiki page.
Art of Code, talk by Dylan Beattie

Intron: Junk or not Junk, that is the quine-tion

Darshan A S — Thu, 25 Jul 2024 05:18:08 +0000

Last time, we cracked the code of Quines, those clever programs that echo their own source code. We crafted them with surgical precision, including only the bare essentials for self-replication.

But here's a question: Can we sneak in some extra, even useless, bits of data into an existing Quine without breaking it?

Enter the world of Introns, those sneaky bits of data that can hitch a ride within a Quine. Just like the non-coding regions of DNA in biology, these introns are extra passengers that don't directly contribute to the Quine's function, but they get copied along for the ride nonetheless.

In the world of biology, Introns are often called "Junk DNA". Only ~2.5% of the genome encodes sequences that make proteins. The functions for the remaining >90% of our genome is not well understood, but seem to play a crucial role in evolution and gene regulation.

"Introns are the dark matter of the eukaryotic genome."

Similarly, in the world of programming, introns might seem like a useless thing to do, but the possible existence of introns will be the key feature in making QuineRelays and MultiQuines possible. (some things we will talk about in the upcoming posts)

Writing your own Intron

Let's take our Python Quine from last time and see how to inject an intron.

Original Python Quine: Try it online!

data = "print('data =', repr(data)); print(data)"
print('data =', repr(data)); print(data)

Let's introduce a variable called intron and set it to a seemingly junk string, such as 'wubbalubbadubdub'. We'll add it to the data portion of our Quine.

Python:

intron = 'wubbalubbadubdub'
data = "print('data =', repr(data)); print(data)"
print('data =', repr(data)); print(data)

To maintain the Quine's integrity, we need to mirror this addition in the code portion. We'll use the repr(intron) technique to ensure the intron is replicated accurately
Python:

intron = 'wubbalubbadubdub'
data = "print('data =', repr(data)); print(data)"
print('intron =', repr(intron)); print('data =', repr(data)); print(data)

Finally, we update the data variable to hold the latest code section.
Python: Try it online!

intron = 'wubbalubbadubdub'
data = "print('intron =', repr(intron)); print('data =', repr(data)); print(data)"
print('intron =', repr(intron)); print('data =', repr(data)); print(data)

It's still a valid Quine. And now it's an IntronQuine!

Imagine a year with only ten months! That's how the Romans initially rolled, with January and February being late additions to the party. Romans were also the reason we have the seemingly random leap days thrown around every few years. And to top it all off, did you know that in 1752, India skipped 11 whole days from its calendar?

Run the above IntronQuine and notice how the value of the intron variable is faithfully reproduced in the output. Try setting intron = 'your name here' The program will still work flawlessly, replicating itself along with your custom message.

The key takeaway is that, quite obviously, an intron can be modified with great ease without breaking the existing Quine; it is a kind of subliminal information that is reproduced with the Quine, although it is not necessary to the Quine. You can change the value of the variable intron to any arbitrary string (as long as it's syntactically right) and the program continues to be a Quine!

This also means, in principle, you can convert any arbitrary program into a Quine, by just encoding its source code as an intron!

Oh, and why was the above calendar bit relevant, you might ask? It wasn't. (Or was it?) Much like those seemingly "junk" leap days in a calendar, this is a seemingly "junk" paragraph just hitching a ride on this blog. Sounds familiar? One might even call it an Intron of this very blog! To learn more about the fascinating and quirky story behind it, checkout Leap days, and the quest for the perfect Calendar.

Like I said, Introns might seem like a useless thing to do, but the possible existence of them will open the doors to mind-blowing interactions between several Quines.

Stay tuned for the next post on QuineRelays!

Sources and references:

Intron (Biology), wiki page.
Leap days, and the quest for the perfect Calendar, blog about quirky history of calendars.
Self-replicating Python code | Quine, Youtube video by Lex Fridman.
Illuminating the Dark Matter of the Genome, article by McManus Lab.
Intron. Junk or not Junk, that is the quine-tion, self-referencing blog that contains an Intron.

Leap days, and the quest for the perfect Calendar

Darshan A S — Mon, 15 Jul 2024 18:57:29 +0000

The story of calendars is a cosmic interplay between astronomy, religion, and history.
And, if you think your schedule is chaotic, just be glad you weren't around when the Romans were messing with time.

Humans have long relied on the cycle of Day and Night for hunting, gathering, and finding their way home after one too many fermented berries.

But our ancestors needed more than just day and night; they needed to predict the fickle seasons for planting, harvesting, and knowing when to throw those wild solstice parties. In short, they needed a calendar!

Enter the Romans!
After all, we all think about the Roman Empire at least once a day, right? RIGHT?

Lunar calendar

Anywho, conveniently enough, like the cycle of day and night, nature had given us yet another cyclical clock in the sky. The Moon! and its phases. The moon, waxing and waning like clockwork every 29.5 days seemed like a natural way to track time. That's how the word Month (literally "Moon-th") originated.

Their first king, Romulus, established a lunar calendar, based on the same idea. It consisted of 10 months, starting with spring (Martius, now March) and ending with the onset of winter (December). The system is usually said to have left the remaining days before the next Spring as an unorganized "winter" since they were irrelevant to the farming cycle.

They began by naming months after their gods. but by the fifth month, they threw their hands up and just named them after the good old Latin numbers.

No.	Months	Meaning	Length in days
1	Martius	Month of Mars, the Roman god of war.	31
2	Aprilis	Month of goddess Apru. (Aphrodite)	30
3	Maius	Month of Maia, a Roman goddess of growth and fertility.	31
4	Junius	Month of Juno, the Roman goddess of marriage and queen of the gods.	30
5	Quintilis	The Latin word quintus meaning "fifth.	31
6	Sextilis	The Latin word sextus meaning "sixth".	30
7	September	The Latin word septem meaning "seven".	30
8	October	The Latin word octo meaning "eight".	31
9	November	The Latin word novem meaning "nine".	30
10	December	The Latin word decem meaning "ten".	30
		Length of the year	304

Lunisolar calendar

Problem was, predicting the end of that chaotic "winter" period was about as easy as herding cats.

So Numa Pompilius, the second king of Rome, tried something.
He reasoned that roughly 12 moon (lunar) cycles occurred between springs (solar), giving a year 12 * 29.5 = 354 days. But hold on! Even-numbers were considered bad luck in ancient Rome, so Numa tacked an extra day onto the year, making the target length, a peculiar 355 days long. Then, to appease the odd-number-loving gods, he removed a day from the 30-day months, leaving behind 304 - 6 = 298 days.

With 12 moon cycles to cover, Numa still had 355 - 298 = 57 days left over. He split these into two new months: one with 29 days and another with the dreaded even number of 28. The first, named Januarius after Janus, the god of beginnings and transitions, was strategically placed at the start of the year. As for the other month, stuck with its even-numbered fate, it was dedicated to spiritual purification and shoved to the end. They called it Februarius, derived from the Latin word "Februa" meaning "purification."

No.	Months	Length in days
1	Januarius	29
2	Martius	31
3	Aprilis	29
4	Maius	31
5	Junius	29
6	Quintilis	31
7	Sextilis	29
8	September	29
9	October	31
10	November	29
11	December	29
12	Februarius	28
	Length of the year	355

But, each year fell short of a tropical year by a few days, causing the seasons to drift like a ship without a rudder. After some head-scratching and sky-gazing, the Romans realized their calendar was off by a whopping 45 days every four years!

So Numa decided to throw in an extra, intercalary month, called Mercedonius, every other year. This bonus month alternated between 22 and 23 days. To make things tidier, and since Feb 23rd was Terminalia (festival of God Terminus, who presided over boundaries), Numa ended Feb on 23rd and moved the remaining 5 days to the intercalating month to make them 27 and 28 days long. And at the same time, Jan and Feb both were moved to the beginning of the year.

No.	Months	Year 1	Year 2	Year 3	Year 4
1	Januarius	29	29	29	29
2	Februarius	28	23	28	23
	Mercedonius	0	27	0	28
3	Martius	31	31	31	31
4	Aprilis	29	29	29	29
...	...	...	...	...	...
12	December	29	29	29	29
	Length of the year	355	377	355	378

Essentially making the average of all 4 years into (355 + 377 + 355 + 378) / 4 = 366.25
This jumbled mess of intercalary months and shifting start dates became known as the Roman Republican Calendar. It was a far cry from perfect, but hey, it was a start.

This is still too many days, but it could have worked. Every 19 solar years would line up with 235 lunar months. Add enough leap months and eventually, everything will reset itself. The seasons will be back on track.

But the leap months weren't added as planned. Politicians would get them to extend leap month when it's their office and to skip the month when it's their opponents. Also, it was a custom that intercalation had to be personally announced by the chief pontiff in Rome. So, during wars, when the king was out of the city, the leap month was forgotten for years.

Solar calendar

By the time Julius Caesar came to power, things were confusing. He had spent a long time in Egypt, where 365-day calendars were all the rage. So in 46 BC he threw the lunisolar calendar away and ordered his scholars to help design a solar calendar. He got rid of the intercalary month of Mercedonius, leaving the original 355 days long year. Caesar then sprinkled the missing 10 days across various months, reaching a total of 365.

The year 46 BC was the last of the old system and included three intercalary months, the first inserted in February and two more—Intercalaris Prior and Posterior—before December, coincidentally making the year of Caesar's third consulship last for 446 days!

But wait! By now, astronomers knew the tropical year was slightly longer—closer to 365.25 (365 days and 6 hours). So, Caesar added a leap day every four years. However, in a move that would baffle future generations, he inserted it after February 23rd, by doubling 24th, right smack in between the month – there were indeed two days dated 24 February!

No.	Months	Length in days
1	January	31
2	February	28 + (1 every 4 years)
3	March	31
4	April	30
5	May	31
6	June	30
7	July	31
8	August	31
9	September	30
10	October	31
11	November	30
12	December	31
	Length of the year	365 + (1 every 4 years)

Following Caesar's assassination, the priests mistakenly added the bissextile leap day every three years due to their inclusive counting. To bring the calendar back to its proper place, Augustus, the next King, was obliged to suspend intercalation for one or two decades.

As a tribute to their egos (ahem, I mean contributions), the 7th and 8th months were renamed Julius (for Caesar, obviously) and Augustus (for his successor).

A better solar calendar

Unfortunately, the Julian calendar wasn't flawless. It assumed the average solar year was exactly 365.25 days long, overestimating by about 14 minutes. By the year 1582, the excess leap days introduced by the Julian algorithm had caused the calendar to drift such that the March equinox was occurring well before its nominal 21 March date. This date was important to the Christian churches because it is fundamental to the calculation of the date of Easter.

To reinstate the association, the then Pope, Pope Gregory XIII, did something crazy to the year 1582. He skipped 10 whole days from the calendar! Thursday, October 4th was followed immediately by Friday, October 15th! Good luck negotiating the rent, I guess?

To ensure that the drift doesn't happen again, Gregory introduced a new calendar, aptly named the Gregorian calendar.
By this time, it was known that a solar year was close to 365.24 days (That's 365 days, 5 hours, 45 minutes, and 36 seconds; for those still keeping track), while the Julian year was 365.25 days. This meant every 1 / (365.25 - 365.24) = 100 years an extra day has been accumulated. So, the Gregorian calendar chose to skip adding a leap day every centennial year (those divisible by 100)

But, the solar year was a smidge longer, around 365.2425 days long. (365 days, 5 hours, 49 minutes, and 12 seconds) Which meant every 1/ (365.2425 - 365.24) = 400 years a day has been lost. So, the Gregorian calendar chose to add back a leap day every centennial year divisible by 400.

This is the calendar we all know (and love?) today. Every year that is exactly divisible by 4, you add a leap day; except for years that are exactly divisible by 100, then you remove the leap day that you would have otherwise added; except if it is divisible by 400, you add back the leap day!

It took 170 more years, for Britain and its colonies, including India, to follow suit. They skipped 11 days, wherein, Wednesday, 1752, September 2nd was followed by Thursday, September 14.

In fact, the world is still adopting the Gregorian. Saudi Arabia, for instance, jumped on the Gregorian wagon as late as 2016!

Future

So, we finally nailed it right? Close, but not quite.

Turns out, the solar year is even shorter than the Gregorian calendar accounts for. The latest measurements put it at a mind-bogglingly precise 365.2421897 days. (365 days, 5 hours, 48 minutes, 45 seconds, 19.008 mili-seconds). How long does this take to accumulate an extra day? 1 / (365.2425 - 365.2421897) ~= 3223 years!

Following the pattern, it seems logical to add back a leap day every 4,000 years, averaging out to 365.24225 days. This would make the calendar drift by a day only once every 1 / (365.24225 - 365.2421897) ~= 16584 years! So, why aren't we doing it?

Well, for starters, as we saw with Gregorian, getting the entire world to adopt a new calendar is nowhere close to easy. But there's a more fundamental reason: it wouldn't be worth the effort.

The solar year—the time it takes Earth to orbit the sun—is gradually increasing, as is the length of a day. Currently, the length of the year is changing in the sixth decimal place over a person's lifetime. Various cosmic forces are at play here, deserving a blog post in their own right. Any correction based on today's solar year length would become obsolete in a few millennia, requiring yet another adjustment anyway.

So, for now, we're stuck with the Gregorian calendar, a marvel of human ingenuity with its quirks and imperfections. What makes this feat even more remarkable is that telescopes weren't even invented when these calendars were designed! All of this was achieved with the naked eye, by observing the shadows cast by sticks and gazing up at the celestial dance above.

As we navigate the complexities of our modern world, perhaps we can take a cue from the ever-shifting cosmos and embrace the fluidity of time itself. After all, isn't life a little more adventurous when we're not always running on schedule?

Bonus

Use timeanddate.com to look at calendars of any year in any given country.
Try finding the 10-day skip in October of 1582 in Italy!
Try finding the 11-day skip in September of 1752 in India!
Look at the Adoption dates of Gregorian Calendar by Country table, to find when a given country adopted the Gregorian and how many days they skipped to synchronize.
Which country skipped the most days? Check out the same in the timeanddate tool above.

Sources and references:

Roman Calendar, wiki page.
Adoption dates of the Gregorian Calendar by country, wiki page.
How Earth Moves, video by VSauce.
Calendar calculations, by NASA.
Why Does February Only Have 28 Days?, video by "Be Smart".
Neil deGrasse Tyson Explains Why We Have Leap Days, video by StarTalk.

Quine: Self replicating computer programs

Darshan A S — Fri, 12 Jul 2024 04:14:29 +0000

A Quine, (/kwi:n/ pronounced Kwine) is a self-replicating computer program, a digital life if you will. It takes no input and prints a copy of its own source code.

This may sound impossible, trivial, or completely uninteresting, depending on your temper and your knowledge of computer science. Trust me, it is not only not impossible, by the end of this post you'll have written your first Quine in Python.

The name "Quine" was coined by Douglas Hofstadter, in his popular science book Gödel, Escher, Bach, in honour of the philosopher Willard Van Orman Quine (1908-2000), who made an extensive study of indirect self-reference, and in particular for the following paradox-producing expression, known as Quine's paradox:

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

The easiest way to write a Quine, of course, is to read the source file on the disk and print its contents. That may be done, but it is considered cheating; besides, the program might not know where the source file is, it may have access to only the compiled data, or the programming language may simply forbid that sort of operation.

Your first Quine

Before we start,

"If you have never done this, I urge you to try it on your own. The discovery of how to do it is a revelation that far surpasses any benefit obtained by being told how to do it."
– Ken Thompson

That said, below is a step-by-step guide to writing your first Quine in Python:

Let's start with 2 pieces in our program.

A variable to hold the string representation of the source code; call this the Data part.
A print statement to output the variable; call this the Code part.

If we are to take an analogy with cellular biology (thanks to Douglas Hofstadter, again), think of a Quine as a cell with its own DNA. What I have called the data would be the DNA, and the code would be the rest of the cell. The cell is able to create a new cell using the DNA, and this involves, among other things, replicating the DNA itself. So the DNA (the data) contains all the necessary information for the replication, but without the cell (the code), or at least some other code to make the data live, it is a useless, inert, piece of data.

Step 1

Let's have a variable to store the data part. And since we don't know the final source code yet, let's use ??? as a placeholder. Print statements will read the data to replicate itself, thereby acting as the code part.

Python Input: Try it online!

data = "???"
print(data)

Output:

# Output
???

Not quite what we're looking for, is it?

Step 2

We can't just print the contents of the data variable. We need to print the very act of declaring the variable itself. Let's add another print statement to do just that.

Python Input: Try it online!

data = "???"
print('data =', data); print(data)

Output:

data = ???
???

Sweet. It's starting to look structurally similar. But we still have those pesky ??? marks.

Step 3

Notice that the second line of output is ???, which corresponds to the part of the source code we initially didn't know how to fill. This means, we can replace ??? to whatever the second line of source code becomes.

Python Input: Try it online!

data = "print('data =', data); print(data)"
print('data =', data); print(data)

Output:

data = print('data =', data); print(data)
print('data =', data); print(data)

Almost there! But we seem to be missing the double quotes in line 1.

Step 4

In Python

str('hi') outputs hi
repr('hi') outputs "hi", with quotes!

That's exactly what we need. Let's wrap data in the second line with repr to get those quotes.

Python Input: Try it online!

data = "print('data =', data); print(data)"
print('data =', repr(data)); print(data)

Output:

data = "print('data =', data); print(data)"
print('data =', data); print(data)

Yay! Line 1 in the source and output are an exact match.
But in doing so, we altered line 2 of the source!

Step 5

We can fix this by setting the value of the data variable to the updated code part.

Python Input: Try it online!

data = "print('data =', repr(data)); print(data)"
print('data =', repr(data)); print(data)

Output:

data = "print('data =', repr(data)); print(data)"
print('data =', repr(data)); print(data)

Viola! There you have it. A valid Quine!

Although I've picked Python here, it's purely due to personal familiarity and brevity, there's nothing special about it. Quines are a general consequence of the so-called Kleene's Fixed-Point theorem, which essentially means that a Quine (in fact, infinitely many) can be written in any Turing-complete programming language.

Almost all programming languages you've heard or used so far are Turing complete.
No, not HTML and CSS, they are not programming languages, let alone Turing-complete. Get over it.

One word of warning: this code/data distinction in Quines is pleasant and often helpful. It is not, however, completely valid in all circumstances

Shortest Quine

In 1983, Ken Thompson in his Turing Award acceptance speech, Reflections on Trusting Trust, presented the persistent compiler backdoor attack now known as the Thompson hack or Trusting trust attack.
Although the paper itself is widely considered a seminal computer security work in its own right, he also made a peculiar statement about Quines.

”In college, before video games, we would amuse ourselves by posing programming exercises. One of the favorites was to write the shortest self-reproducing program. Since this is an exercise divorced from reality, the usual vehicle was FORTRAN. Actually, FORTRAN was the language of choice for the same reason that three-legged races are popular.“
– Ken Thompson

I claim no knowledge whatsoever of FORTRAN. So, here's the shortest Quine in Python:

Python: Try it online!

_='_=%r;print(_%%_)';print(_%_)

Looks esoteric, doesn't it? But don't let the compactness fool you. Let's decipher how we could have arrived at the shortest one ourselves.

Step 1

Let's start with

Python Input: Try it online!

d = '???'
print(d)

Output:

???

Step 2

Let's add the entire source code from previous step into d.

Python Input: Try it online!

d = 'd = ???\nprint(d)'
print(d)

Output:

d = ???
print(d)

If you noticed the output. We just want to replace ??? with the exact value of variable d and we are done!

Step 3

There's a nifty trick in Python to do this. The str(d) and repr(d) have a shortcut symbol of %s and %r respectively, and can be used like below:

print('Bruce Wayne is %s' % 'Batman') # outputs: Bruce Wayne is Batman
print('Bruce Wayne is %r' % 'Batman') # outputs: Bruce Wayne is 'Batman'

Using that, replace ??? with %r and substitute d onto itself in line 2.

Python Input: Try it online!

d = 'd = %r\nprint(d)'
print(d % d)

Output:

d = 'd = %r\nprint(d)'
print(d)

So close! We are just missing the % d in the second line.

Step 4

Let's add that % d in line 1 of the source.
But hold on % d would make Python look for a second value to be replaced.
To tell Python not to, we have to escape the % symbol. This can be done by adding another % in front.

Python Input: Try it online!

d = 'd = %r\nprint(d %% d)'
print(d % d)

Output:

d = 'd = %r\nprint(d %% d)'
print(d % d)

This is a valid Quine!

Step 5

Now, to make it short. Let's get rid of the newline character and combine both lines using ;

d = 'd = %r;print(d %% d)';print(d % d)

Variables can start with underscores. A single underscore is in and of itself a valid variable. Let's replace d with _

_ = '_ = %r;print(_ %% _)';print(_ % _)

Get rid of all the spaces.

Python: Try it online!

_='_=%r;print(_%%_)';print(_%_)

There you have it. The shortest Quine.

Here's an interesting one: An Error-Quine in Python. The source code is an error-like text that throws the exact error when executed.
The only difference being the output now goes to stderr instead of stdout.

Python: Try it online!

  File "quine.py", line 1
    File "quine.py", line 1
    ^
IndentationError: unexpected indent

Some more Quines

Ruby: Try it online!

s="s=%p;puts s%%s";puts s%s

Lua: Try it online!

s="s=%qprint(s:format(s))"print(s:format(s))

Perl 5: Try it online!

$s=q($s=q(%s);printf($s,$s););printf($s,$s);

JavaScript: Try it online!

s="s=%j;console.log(s,s)";console.log(s,s)

C: Try it online!

main(s){printf(s="main(s){printf(s=%c%s%1$c,34,s);}",34,s);}

Java: Try it online!

class Q{public static void main(String[]a){String s="class Q{public static void main(String[]a){String s=%c%s%1$c;System.out.printf(s,34,s);}}";System.out.printf(s,34,s);}}

Rust: Try it online!

fn main(){print!("fn main(){{print!({0:?},{0:?})}}","fn main(){{print!({0:?},{0:?})}}")}

HQ9+: Try pasting it Online
Wiki page of HQ9+ language

Quines are a fascinating topic and an art in their own right.
We'll go more in-depth and explore topics like Intron, QuineRelay, MultiQuine, and much more in the follow-up posts.

Stay tuned!

Sources and references:

Quine (computing), wiki page.
Quine: Self replicating computer programs, self-referencing blog.
Self-replicating Python code | Quine, Youtube video by Lex Fridman.
Reflections on Trusting Trust, paper by Ken Thompson.
Gödel, Escher, Bach: An Eternal Golden Braid, book by Douglas R. Hofstadter.
Quines (self-replicating programs), blog by David Madore.
The Quine Page, blog by Gary P. Thompson II.
Quine Programs, blog by Ray Toal.