Quine (computing)

Aquineis a special kind ofcomputer program,which accepts no inputs and outputs its ownsource code.They are named after the philosopherWillard Van Orman Quine.

Quine's Paradox

Quine was very interested in the "liar paradox", "this statement is false", which can't be either true or false. This paradox appears in lots of other places. In the mathematics ofset theoryit is calledRussell's paradox,it is a set which contains sets which don't contain themselves.

All of those examples before Quine were 'self-referential'. This means that they define an object in terms of itself, like the liar paradox starting with the words "this statement". Lots of people thought that you could ignore the liar paradox if you just decided to ignore all self-referential statements. Quine saw that you would also have to ignorequotation,which is the process that happens when you put a phrase in quote marks. When yousaya phrase, you are talking about its meaning; but when youquotea phrase, you are talking about that phrase, and not what it means.

Quine's paradox was, ' "Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.' This is a more complicated liar paradox which is not self-referential. It is a simple statement about some phrase, telling you what happens when you write a statement where you write the phrase in quote marks and then write the phrase again outside of them.

Quines as programs

Mostprogramming languageshave quotation too: you can put quotes around some code and then the computer does notrunthat code, but instead juststoresit as astring.

The trick to writing a quine involves writing a string which somehow has a "hole" in it, then outputting that string, with the "hole" filled in with its own quotation. For example in Python the function which quotes a string is calledrepr,and the%operator fills in a hole which is written as%sin the string, while converting%%to%:

defquine():
"Returns its own source code"
s='def quine():\n"Returns its own source code"\ns =%s\nreturn s%%repr(s)\n'
returns%repr(s)

Or in JavaScript, we can useJSON.stringifyto quote an array, and the "hole" can be the space between the two array elements:

functionquine(){
vara=["function quine() {\n var a =",";\n return a[0] + JSON.stringify(a) + a[1];\n}"];
returna[0]+JSON.stringify(a)+a[1];
}

InCoffeeScriptyou can write a quine as a phrase followed by its own quotation, which looks a lot like Quine's paradox:

quine=->((t) ->t+JSON.stringifyt)"quine = -> ((t) -> t + JSON.stringify t)"