Квайны

Эта статья находится в разработке!

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

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

Происхождение названия

Название "квайн" было предложено Дугласом Хофштадтером, в его известной книге "Гёдель, Эшер, Бах: Эта бесконечная гирлянда" в честь американского логика и философа Уилларда Ван Ормана Квайна, который углублённо изучал явление косвенного самоупоминания. в частности, это явление можно проиллюстрировать следующим парадоксальным утверждением, известном как парадокс Квайна:

Теорема (парадокс Квайна):

"Становится ложным, когда добавляется к собственной цитате" становится ложным, когда добавляется к собственной цитате.

Доказательство существования

Теорема (о существовании квайнов):

На любом языке программирования можно написать квайн

Доказательство:

[math]\triangleright[/math]

Рассмотрим функцию [math]h(t)[/math], которая по данной программе [math]t[/math] печатает её исходный код. Очевидно, она вычислима. По теореме о неподвижной точкесуществует такая программа [math]n[/math], что [math]h(n)[/math] и [math]n[/math] ведут себя одинаково, то есть печатают свой код. Таким образом, [math]n[/math] печатает код [math]n[/math], т.е. является квайном.

[math]\triangleleft[/math]

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

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

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

Ссылки

• Quines (self-replicating programs)