Квайны — различия между версиями
Xottab (обсуждение | вклад) |
|||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
− | |definition='''Квайном''' (англ. <i>quine</i>)<ref name= | + | |definition='''Квайном''' (англ. <i>quine</i>)<ref name=quineName/> называется программа, которая выводит свой исходный код. При этом, программа не должна использовать внешние данные (например, читать файл со своим исходным кодом)<ref name=quineExists/>. |
}} | }} | ||
==Доказательство существования== | ==Доказательство существования== | ||
Строка 104: | Строка 104: | ||
== Примечания == | == Примечания == | ||
<references> | <references> | ||
− | <ref name= | + | <ref name=quineName>Название "квайн" было предложено [http://ru.wikipedia.org/wiki/Хофштадтер,_Дуглас Дугласом Хофштадтером], в его известной книге "Гёдель, Эшер, Бах: Эта бесконечная гирлянда" в честь американского логика и философа [http://ru.wikipedia.org/wiki/Куайн,_Уиллард_Ван_Орман Уилларда Ван Ормана Квайна], который углублённо изучал явление [http://en.wikipedia.org/wiki/Indirect_self-reference косвенного самоупоминания].</ref> |
+ | <ref name=quineExists>Из [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B8#.D0.A2.D0.B5.D0.BE.D1.80.D0.B5.D0.BC.D0.B0_.D0.BE_.D1.80.D0.B5.D0.BA.D1.83.D1.80.D1.81.D0.B8.D0.B8 теоремы Клини о рекурсии] очевидно следует, что квайн можно написать на любом Тьюринг-полном языке.</ref> | ||
</references> | </references> | ||
Версия 12:41, 4 января 2015
Определение: |
Квайном (англ. quine)[1] называется программа, которая выводит свой исходный код. При этом, программа не должна использовать внешние данные (например, читать файл со своим исходным кодом)[2]. |
Содержание
Доказательство существования
Теорема (о существовании квайнов): |
На любом языке программирования можно написать квайн |
Доказательство: |
Рассмотрим функцию теореме о неподвижной точке существует такая программа , что и ведут себя одинаково, то есть печатают свой код. Таким образом, печатает код , т.е. является квайном. | , которая по данной программе печатает её исходный код. Очевидно, она вычислима. По
Общий принцип написания квайнов
Квайн состоит из двух сегментов: кода и данных. Данные представляют собой текстовую версию кода, и, как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код(содержащийся в них), а затем, просто выводит данные. Чтобы написать простой квайн на C, мы положим в данные текстовое представление кода и при выводе данных будем экранировать знаки табуляции и переносов:
const char data [] = "#include <stdio.h>\n\nint\nmain (void)\n{\n unsigned int i;\n\n p" "rintf (\"const char data [] =\");\n for ( i=0 ; data[i] ; i++ " ")\n {\n if ( i%60 == 0 )\n\tprintf (\"\\n\\\"\");\n switc" "h ( data[i] )\n\t{\n\tcase '\\\\':\n\tcase '\"':\n\t printf (\"\\\\%c\", d" "ata[i]);\n\t break;\n\tcase '\\n':\n\t printf (\"\\\\n\");\n\t break;\n" "\tcase '\\t':\n\t printf (\"\\\\t\");\n\t break;\n\tdefault:\n\t printf" " (\"%c\", data[i]);\n\t}\n if ( i%60 == 59 || !data[i+1] )\n\t" "printf (\"\\\"\");\n }\n printf (\";\\n\\n\");\n for ( i=0 ; data[" "i] ; i++ )\n putchar (data[i]);\n return 0;\n}\n"; #include <stdio.h> int main (void) { unsigned int i; printf ("const char data [] ="); for ( i=0 ; data[i] ; i++ ) { if ( i%60 == 0 ) printf ("\n\""); switch ( data[i] ) { case '\\': case '"': printf ("\\%c", data[i]); break; case '\n': printf ("\\n"); break; case '\t': printf ("\\t"); break; default: printf ("%c", data[i]); } if ( i%60 == 59 || !data[i+1] ) printf ("\""); } printf (";\n\n"); for ( i=0 ; data[i] ; i++ ) putchar (data[i]); return 0; }
Можно представить сегмент данных как некий шифр, который можно расшифровать двумя способами. В результате расшифровки первым способом получится строковое представление собственно сегмента данных, при расшифровке вторым способом получится строковое представление сегмента кода. Объединив результаты этих расшифровок, мы получим строку, в которой содержится весь исходный код программы. Таким образом, изменяя способ шифровки-расшифровки, можно получать сложные конструкции, например, цикл из 50 программ, каждая из которых выводит код на новом языке программирования, который является следующей программой в цикле
Связанные определения
Интроны
Определение: |
Интроном (intron) называется часть сегмента данных, которая не используется для вывода кода, но сохраняющаяся в процессе саморепликации квайна. |
Название пришло из биологии, где интронами называются части ДНК, не участвующие в синтезе протеинов. В вышеприведённый квайн можно легко добавить интрон, написав перед объявлением функции
const unsigned char intron[] = "--Hello! I am an intron!---";
и добавив в код (а значит, и модифицировав данные) строчки для вывода интрона. Интроны активно используются при создании мульти-квайнов.
Мульти-квайны
Определение: |
Би-квайном (bi-quine) называется программа, которая делает одно из двух:
|
Определение: |
-квайном называется программа, способная вывести исходный код программ на других языках программирования в зависимости от переданного ей аргумента, а так же свой исходный код при вызове без аргументов. |
Заметим, что требование, чтобы программы были на разных языках программирования важно, т.к. иначе все программы смогут иметь один и тот же код.
Теорема (о существовании мульти-квайнов): |
На любом языке программирования можно написать мульти-квайн |
Доказательство: |
Докажем утверждение для би-квайна, для большего количества языков доказательство будет выглядеть аналогично. Рассмотрим программу с двумя параметрами на языке , которая выводит первый параметр при обычном запуске и второй - при запуске со спец. аргументом. По теореме о неподвижной точке мы можем зафиксировать первый параметр и сказать, что он будет равен исходному коду нашей программы. Таким образом, мы получим программу с одним параметром, которая выводит свой код при запуске без аргументов и выводит параметр при запуске со спец. аргументом. Проделаем то же самое для программы на языке . И наконец, зафиксируем как аргумент первой исходник второй и наоборот. |
Таким образом, следуя нашему доказательству, чтобы написать мульти-квайн мы будем использовать интроны. У нас есть
программ, т.е. сегментов кода (на каждом языке); кроме того, каждая из программ имеет в дополнение к сегменту кода сегментов данных, каждая из которых представляет собой код на определённом языке (т.е. интрон + сегмент данных программы). Когда программу (имеющую сегмент кода под номером на языке ) просят вывести исходный код программы , она использует один из своих интронов, чтобы вывести сегмент кода программы , а затем использует все интроны и свой сегмент данных для вывода сегмента данных программы .Источники информации
- Madore.org - Quines (self-replicating programs)
- Хабрахабр - Эстафета из 50 квайнов
- Хабрахабр - Мультиязыковые квайны
- Хабрахабр - Как писать квайны
Примечания
- ↑ Название "квайн" было предложено Дугласом Хофштадтером, в его известной книге "Гёдель, Эшер, Бах: Эта бесконечная гирлянда" в честь американского логика и философа Уилларда Ван Ормана Квайна, который углублённо изучал явление косвенного самоупоминания.
- ↑ Из теоремы Клини о рекурсии очевидно следует, что квайн можно написать на любом Тьюринг-полном языке.