Quine

A quine is a com­puter pro­gram that ‘knows’ its own en­tire source code via in­di­rect self-refer­ence, rather than by get­ting it as in­put. The clas­sic ex­er­cise in this do­main is writ­ing a (non-empty) pro­gram that takes no in­put and which out­puts its own en­tire source code. But the same trick can be used to do more than that; for any pro­gram that takes a string as in­put and performs some op­er­a­tions on it, we can write a quin­ing pro­gram that takes no in­put and performs the same op­er­a­tions on the pro­gram’s own source code.

The trick to write a quin­ing pro­gram is to take a recipe for sub­sti­tut­ing a string into var­i­ous places in a pro­gram, and then to ap­ply this recipe to it­self. If you’ve not en­coun­tered this idea be­fore, but you know a pro­gram­ming lan­guage, it is a nice ex­er­cise to try and write a quine which prints its own source code.

An ex­am­ple of a quine in Python (due to Nate Soares) which prints its own source code:

tem­plate = ‘tem­plate = {hole}\nprint(tem­plate.for­mat(hole=repr(tem­plate)))’
print(tem­plate.for­mat(hole=repr(tem­plate)))

Wikipe­dia has a list of ex­am­ples of quin­ing pro­grams in var­i­ous lan­guages.

Named af­ter the lo­gi­cian W.V.O. Quine, as coined by Dou­glas Hofs­tadter in Gödel, Escher, Bach, in the in­for­mal con­text of English phrases like

“Yields false­hood when pre­ceded by its quo­ta­tion” yields false­hood when pre­ceded by its quo­ta­tion.

Quin­ing has been used for prac­ti­cal pur­poses and even seen in the wild, most fa­mously in Ken Thomp­son’s illus­tra­tion of a C com­piler Tro­jan back­door.

Parents:

  • Gödel encoding and self-reference

    The for­mal­ism that math­e­mat­i­ci­ans use to talk about ar­ith­metic turns out to be able to talk about it­self.

  • Diagonal lemma

    Con­struct­ing self-refer­en­tial sentences

    • Mathematics

      Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.