Квайны

Материал из Викиконспекты
Версия от 14:07, 6 января 2015; Xottab (обсуждение | вклад) (→‎Принцип написания)
Перейти к: навигация, поиск
Определение:
Квайном (англ. 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;
}

Можно представить сегмент данных как некий шифр, который можно расшифровать двумя способами. В результате расшифровки первым способом получится строковое представление собственно сегмента данных, при расшифровке вторым способом получится строковое представление сегмента кода. Объединив результаты этих расшифровок, мы получим строку, в которой содержится весь исходный код программы.

Связанные определения

Интроны

Определение:
Интроном (intron) называется часть сегмента данных, которая не используется для вывода кода, но сохраняющаяся в процессе саморепликации квайна.

Название пришло из биологии, где интронами называются части ДНК, не участвующие в синтезе протеинов. В вышеприведённый квайн можно легко добавить интрон, написав перед объявлением функции 

const unsigned char intron[] = "--Hello! I am an intron!---";

и добавив в код (а значит, и модифицировав данные) строчки для вывода интрона. Интроны активно используются при создании мульти-квайнов.

Мульти-квайны

Определение:
Би-квайном (bi-quine) называется программа, которая делает одно из двух:
  • при обычном запуске она выводит свой исходный код
  • при запуске с особым аргументом она выводит исходный код своего "брата" на другом языке программирования.
Её брат делает то же самое: выводит свой код при запуске без аргументов и выводит код оригинальной программы при запуске с переданным спец. аргументом.


Определение:
[math]R[/math]-квайном называется программа, способная вывести исходный код [math]R-1[/math] программ на других языках программирования в зависимости от переданного ей аргумента, а так же свой исходный код при вызове без аргументов.

Заметим, что требование, чтобы программы были на разных языках программирования важно, т.к. иначе все программы смогут иметь один и тот же код.

Теорема (о существовании мульти-квайнов):
На любом языке программирования можно написать мульти-квайн
Доказательство:
[math]\triangleright[/math]

Докажем утверждение для би-квайна, для большего количества языков доказательство будет выглядеть аналогично.

Рассмотрим программу с двумя параметрами на языке [math]L_1[/math], которая выводит первый параметр при обычном запуске и второй - при запуске со спец. аргументом. По теореме о неподвижной точке мы можем зафиксировать первый параметр и сказать, что он будет равен исходному коду нашей программы. Таким образом, мы получим программу с одним параметром, которая выводит свой код при запуске без аргументов и выводит параметр при запуске со спец. аргументом. Проделаем то же самое для программы на языке [math]L_2[/math]. И наконец, зафиксируем как параметр первой исходник второй и наоборот.
[math]\triangleleft[/math]

Таким образом, следуя нашему доказательству, чтобы написать мульти-квайн мы будем использовать интроны. У нас есть [math]r[/math] программ, т.е. [math]r[/math] сегментов кода (на каждом языке); кроме того, каждая из [math]r[/math] программ имеет в дополнение к сегменту кода [math]r[/math] сегментов данных, каждая из которых представляет собой код на определённом языке (т.е. [math]r-1[/math] интрон + сегмент данных программы). Когда программу [math]i[/math] (имеющую сегмент кода под номером [math]i[/math] на языке [math]L_i[/math]) просят вывести исходный код программы [math]j[/math], она использует один из своих интронов, чтобы вывести сегмент кода программы [math]j[/math], а затем использует все интроны и свой сегмент данных для вывода сегмента данных программы [math]j[/math].

Принцип написания

Будем следовать доказательству и напишем мульти-квайн для двух языков. Далее покажем, как добавить новый язык.

  1. напишем для каждого языка "полу-квайн": [math]P(p,arg): \left\{ \begin{array}{l l} P(p,"shazam!") \rightarrow print(p); \\ P(p,null) \rightarrow print(P.getSrc()); \end{array} \right. [/math]
  2. добавим код каждой из программ интроном в код другой
  3. модифицируем каждую из программ, чтобы вместо [math]p[/math] она выводила интрон: [math]P(arg): \left\{ \begin{array}{l l} P("shazam!") \rightarrow print(intron); \\ P(null) \rightarrow print(P.getSrc()); \end{array} \right. [/math]

Теперь добавим третий язык:

  1. напишем для него "полу-квайн", но уже с двумя параметрами и тремя возможными выводами:[math]P_3(p,arg): \left\{ \begin{array}{l l} P(p1,p2,"shazam!") \rightarrow print(p1); \\ P(p1,p2,"cadabra!") \rightarrow print(p2); \\ P(p1,p2,null) \rightarrow print(|P|); \end{array} \right. [/math]
  2. добавим третье условие в два уже существующих квайна: [math]P(p,arg): \left\{ \begin{array}{l l} P(p,"shazam!") \rightarrow print(intron); \\ P(p,"cadabra!") \rightarrow print(p); \\ P(p,null) \rightarrow print(P.getSrc()); \end{array} \right. [/math]
  3. подставим код первых двух интронами в третью, а код третьей - вторым интроном в каждую из двух первых:
[math]P(arg): 
\left\{
	\begin{array}{l l}
		P("shazam!") \rightarrow print(intron1);  \\
                P("cadabra!") \rightarrow print(intron2); \\
                P(null) \rightarrow print(P.getSrc());
	\end{array}
	\right.
[/math]

Источники информации

Примечания

  1. ↑ Название "квайн" было предложено Дугласом Хофштадтером, в его известной книге "Гёдель, Эшер, Бах: Эта бесконечная гирлянда" в честь американского логика и философа Уилларда Ван Ормана Квайна, который углублённо изучал явление косвенного самоупоминания.
  2. ↑ Из теоремы Клини о рекурсии очевидно следует, что квайн можно написать на любом Тьюринг-полном языке.
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Квайны&oldid=43479»