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)
Nearby terms:
QUIKSCRIPT « QUIKTRAN « QUIN « quine »
Quintec-Objects » quintillion » Quintus Prolog
|
