Квайны

Определение:

Квайном (англ. quine) называется программа, которая выводит свой исходный код. При этом, программа не должна использовать внешние данные (например, читать файл со своим исходным кодом).

Общий принцип написания квайнов

Квайн состоит из двух сегментов: кода и данных. Данные представляют собой текстовую версию кода, и, как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код(содержащийся в них), а затем, просто выводит данные. Чтобы написать простой квайн на 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]

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

• Madore.org - Quines (self-replicating programs)
• Хабрахабр - Эстафета из 50 квайнов
• Хабрахабр - Мультиязыковые квайны
• Хабрахабр - Как писать квайны