quine

programming /kwi:n/ (After the logician Willard V. Quine,

via Douglas Hofstadter) A program that generates a copy of its

own source text as its complete output. Devising the shortest

possible quine in some given programming language is a common

hackish amusement.

In most interpreted languages, any constant, e.g. 42, is a

quine because it "evaluates to itself". In certain Lisp

dialects (e.g. Emacs Lisp), the symbols "nil" and "t" are

"self-quoting", i.e. they are both a symbol and also the value

of that symbol. In some dialects, the function-forming

function symbol, "lambda" is self-quoting so that, when

applied to some arguments, it returns itself applied to those

arguments. Here is a quine in Lisp using this idea:

((lambda (x) (list x x)) (lambda (x) (list x x)))

Compare this to the lambda expression:

( x . x x) ( x . x x)

which reproduces itself after one step of beta reduction.

This is simply the result of applying the combinator fix

to the identity function. In fact any quine can be

considered as a fixed point of the language's evaluation

mechanism.

We can write this in Lisp:

((lambda (x) (funcall x x)) (lambda (x) (funcall x x)))

where "funcall" applies its first argument to the rest of its

arguments, but evaluation of this expression will never

terminate so it cannot be called a quine.

Here is a more complex version of the above Lisp quine, which

will work in Scheme and other Lisps where "lambda" is not

self-quoting:

((lambda (x)

(list x (list (quote quote) x)))

(quote

(lambda (x)

(list x (list (quote quote) x)))))

It's relatively easy to write quines in other languages such

as PostScript which readily handle programs as data; much

harder (and thus more challenging!) in languages like C

which do not. Here is a classic C quine for ASCII

machines:

char*f="char*f=%c%s%c;main() printf(f,34,f,34,10);%c";

main()printf(f,34,f,34,10);

For excruciatingly exact quinishness, remove the interior line

break. Some infamous Obfuscated C Contest entries have been

quines that reproduced in exotic ways.

Ken Thompson's back door involved an interesting variant

of a quine - a compiler which reproduced part of itself when

compiling (a version of) itself.

[Jargon File]

(1995-04-25)