Квайны — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
м (rollbackEdits.php mass rollback)
 
(не показано 37 промежуточных версий 5 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition='''Квайном''' ('''куайном, quine''') называется программа, которая выводит свой исходный код. При этом, программа не должна использовать внешние данные (например, читать файл со своим исходным кодом).
+
|definition='''Квайном''' (англ. ''quine'')<ref name=quineName/> называется программа, которая выводит свой исходный код. При этом программа не должна использовать внешние данные (например, читать файл со своим исходным кодом).
 
}}
 
}}
==Происхождение названия==
+
Стоит отметить, что программы, использующие для чтения своего кода файловую систему, квайнами не считаются. Например, программа на BASIC вида
Название "квайн" было предложено [http://ru.wikipedia.org/wiki/Хофштадтер,_Дуглас Дугласом Хофштадтером], в его известной книге "Гёдель, Эшер, Бах: Эта бесконечная гирлянда" в честь американского логика и философа  [http://ru.wikipedia.org/wiki/Куайн,_Уиллард_Ван_Орман Уилларда Ван Ормана Квайна], который углублённо изучал явление [http://en.wikipedia.org/wiki/Indirect_self-reference косвенного самоупоминания]. в частности, это явление можно проиллюстрировать следующим парадоксальным утверждением, известном как парадокс Квайна:
+
<font size = "2em">
{{
+
10 LIST
Теорема
+
</font>
|about=парадокс Квайна
+
выводит на экран свой исходный код, поскольку команда <tex>\mathtt{LIST}</tex> просит среду исполнения вывести в консоль текущую программу (эта функция была необходима для программистов, так как код программы зачастую не мог поместиться на консоль 80x25 символов).
|statement=
 
"Становится ложным, когда добавляется к собственной цитате" становится ложным, когда добавляется к собственной цитате.
 
}}
 
==Доказательство существования==
 
{{
 
Теорема
 
|about=о существовании квайнов
 
|statement= На любом языке программирования можно написать квайн
 
|proof= Рассмотрим функцию <tex>h(t)</tex>, которая по данной программе <tex>t</tex> печатает её исходный код. Очевидно, она вычислима. По  [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_.D0.BD.D0.B5.D0.BF.D0.BE.D0.B4.D0.B2.D0.B8.D0.B6.D0.BD.D0.BE.D0.B9_.D1.82.D0.BE.D1.87.D0.BA.D0.B5 теореме о неподвижной точке] существует такая программа <tex>n</tex>, что <tex>h(n)</tex> и <tex>n</tex> ведут себя одинаково, то есть печатают свой код. Таким образом, <tex>n</tex> печатает код <tex>n</tex>, т.е. является квайном.
 
}}
 
 
 
==Общий принцип написания квайнов==
 
Квайн состоит из двух сегментов: <b>кода</b> и <b>данных</b>. Данные представляют собой текстовую версию кода, и, как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код(содержащийся в них), а затем, просто выводит данные.
 
Чтобы написать простой квайн на C, мы положим в данные текстовое представление кода и при выводе данных будем экранировать знаки табуляции и переносов:
 
<nowiki>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;
 
}</nowiki>
 
  
Можно представить сегмент данных как некий шифр, который можно расшифровать двумя способами. В результате расшифровки первым способом получится строковое представление собственно сегмента данных, при расшифровке вторым способом получится строковое представление сегмента кода. Объединив результаты этих расшифровок, мы получим строку, в которой содержится весь исходный код программы.
+
Формально общий принцип написания квайнов содержится в доказательстве [[Теорема о рекурсии|теоремы о рекурсии]]. Далее будет рассмотрено понятие мультиквайна.
Таким образом, изменяя способ шифровки-расшифровки, можно получать сложные конструкции, например, [http://habrahabr.ru/post/186782/ цикл из 50 программ, каждая из которых выводит код на новом языке программирования, который является следующей программой в цикле]
 
  
==Связанные определения==
+
==Мультиквайны==
===Интроны===
+
===Связанные определения===
 
{{Определение
 
{{Определение
|definition='''Интроном''' (intron) называется часть сегмента данных, которая не используется для вывода кода, но сохраняющаяся в процессе саморепликации квайна.
+
|definition='''Интроном''' (англ. ''intron'')<ref name=intronName/> называется часть сегмента данных, которая не используется для вывода кода, но сохраняется в процессе саморепликации квайна.
 
}}
 
}}
Название пришло из биологии, где интронами называются части ДНК, не участвующие в синтезе протеинов.
 
В вышеприведённый квайн можно легко добавить интрон, написав перед объявлением функции
 
<nowiki>const unsigned char intron[] = "--Hello! I am an intron!---";</nowiki>
 
и добавив в код (а значит, и модифицировав данные) строчки для вывода интрона.
 
Интроны активно используются при создании мульти-квайнов.
 
 
===Мульти-квайны===
 
 
{{Определение
 
{{Определение
|definition='''Би-квайном''' (bi-quine) называется программа, которая делает одно из двух:
+
|definition='''Биквайном''' (англ. ''biquine'') называется программа, которая делает одно из двух:
*при обычном запуске она выводит свой исходный код
+
*при обычном запуске она выводит свой исходный код,
 
*при запуске с особым аргументом она выводит исходный код своего "брата" на другом языке программирования.
 
*при запуске с особым аргументом она выводит исходный код своего "брата" на другом языке программирования.
Её брат делает то же самое: выводит свой код при запуске без аргументов и выводит код оригинальной программы при запуске с переданным спец. аргументом.
+
Её "брат" делает то же самое: выводит свой код при запуске без аргументов и выводит код оригинальной программы при запуске с переданным специальным аргументом.
 
}}
 
}}
 
{{Определение
 
{{Определение
|definition='''<tex>R</tex>-квайном''' называется программа, способная вывести исходный код <tex>R-1</tex> программ на других языках программирования в зависимости от переданного ей аргумента, а так же свой исходный код при вызове без аргументов.
+
|definition='''<tex>R</tex>-квайном''' (англ. <tex>R</tex>-''quine'') называется программа, способная вывести исходный код <tex>R-1</tex> программ на других языках программирования в зависимости от переданного ей аргумента, а также свой исходный код при вызове без аргументов.
 
}}
 
}}
Заметим, что требование, чтобы программы были на разных языках программирования важно, т.к. иначе все программы смогут иметь один и тот же код.
+
Заметим, что требование, чтобы программы были на разных языках программирования, важно, иначе все программы смогут иметь один и тот же код.
 
 
 
{{
 
{{
 
Теорема
 
Теорема
|about=о существовании мульти-квайнов
+
|about=о существовании мультиквайнов
|statement= На любом языке программирования можно написать мульти-квайн
+
|statement= На любом языке программирования можно написать мультиквайн.
|proof= Докажем утверждение для би-квайна, для большего количества языков доказательство будет выглядеть аналогично.
+
|proof= Докажем утверждение для биквайна. Для большего количества языков доказательство будет выглядеть аналогично.
  
Рассмотрим программу с двумя параметрами на языке <tex>L_1</tex>, которая выводит первый параметр при обычном запуске и второй - при запуске со спец. аргументом. По [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_.D0.BD.D0.B5.D0.BF.D0.BE.D0.B4.D0.B2.D0.B8.D0.B6.D0.BD.D0.BE.D0.B9_.D1.82.D0.BE.D1.87.D0.BA.D0.B5 теореме о неподвижной точке] мы можем зафиксировать первый параметр и сказать, что он будет равен исходному коду нашей программы. Таким образом, мы получим программу с одним параметром, которая выводит свой код при запуске без аргументов и выводит параметр при запуске со спец. аргументом. Проделаем то же самое для программы на языке <tex>L_2</tex>. И наконец, зафиксируем как аргумент первой исходник второй и наоборот.  
+
Рассмотрим программу с двумя параметрами на языке <tex>L_1</tex>, которая выводит первый параметр при обычном запуске и второй {{---}} при запуске со спец. аргументом. По [[Теорема о рекурсии|теореме о рекурсии]] мы можем зафиксировать первый параметр и сказать, что он будет равен исходному коду нашей программы. Таким образом, мы получим программу с одним параметром, которая выводит свой код при запуске без аргументов и выводит параметр при запуске со спец. аргументом. Проделаем то же самое для программы на языке <tex>L_2</tex>. И, наконец, зафиксируем как параметр первой программы исходный код второй и наоборот.  
 
}}
 
}}
Таким образом, следуя нашему доказательству, чтобы написать мульти-квайн мы будем использовать интроны. У нас есть <tex>r</tex> программ, т.е. <tex>r</tex> сегментов кода (на каждом языке); кроме того, каждая из <tex>r</tex> программ имеет в дополнение к сегменту кода <tex>r</tex> сегментов данных, каждая из которых представляет собой код на определённом языке (т.е. <tex>r-1</tex> интрон + сегмент данных программы). Когда программу <tex>i</tex> (имеющую сегмент кода под номером <tex>i</tex> на языке <tex>L_i</tex>) просят вывести исходный код программы <tex>j</tex>, она использует один из своих интронов, чтобы вывести сегмент кода программы <tex>j</tex>, а затем использует все интроны и свой сегмент данных для вывода сегмента данных программы <tex>j</tex>.
+
 
== Ссылки ==
+
===Принцип написания===
* [http://www.madore.org/~david/computers/quine.html Quines (self-replicating programs)]
+
Будем следовать доказательству и напишем мультиквайн для двух языков. Далее покажем, как добавить новый язык.
* [http://habrahabr.ru/post/186782/ Эстафета из 50 квайнов]
+
* напишем для каждого языка "полуквайн":
* [http://habrahabr.ru/post/188378/ Мультиязыковые квайны]
+
<table>
* [http://habrahabr.ru/post/128191/ Как писать квайны]
+
<tr>
 +
<td><font size = "2em">
 +
<tex>P_1(p,arg)</tex>:
 +
    '''if''' (arg == "print second!")
 +
        '''print'''(p)
 +
    '''else'''
 +
        '''print'''(getSrc())
 +
</font></td>
 +
<td><font size = "2em">
 +
<tex>P_2(p,arg)</tex>:
 +
    '''if''' (arg == "print first!")
 +
        '''print'''(p)
 +
    '''else'''
 +
        '''print'''(getSrc())
 +
</font></td>
 +
</tr>
 +
</table>
 +
* подставим код второй программы в первую:
 +
<font size = "2em">
 +
<tex>P_1(p,arg)</tex>:
 +
    '''if''' (arg == "print second!")
 +
        '''print'''(<tex>P_2</tex>(p, arg).getSrc())
 +
    '''else'''
 +
        '''print'''(getSrc())
 +
</font>
 +
* применим [[Теорема о рекурсии|теорему о рекурсии]] и заменим параметр на исходный код программы:
 +
<font size = "2em">
 +
<tex>P_1(arg)</tex>:
 +
    '''if''' (arg == "print second!")
 +
        '''print'''(<tex>P_2</tex>(getSrc(), arg).getSrc())
 +
    '''else'''
 +
        '''print'''(getSrc())  
 +
</font>
 +
Вторая программа может быть получена запуском первой с нужным аргументом.
 +
 
 +
Теперь добавим третий язык:
 +
* напишем для него "полуквайн", но уже с двумя параметрами и тремя возможными выводами:
 +
<font size = "2em">
 +
<tex>P_3(p1,p2,arg)</tex>:
 +
    '''if''' (arg == "print first!")
 +
        '''print'''(p1)
 +
    '''elseif''' (arg == "print second!")
 +
        '''print'''(p2)
 +
    '''else'''
 +
        '''print'''(getSrc())
 +
</font>
 +
* добавим параметр в два уже существующих квайна:
 +
<table>
 +
<tr>
 +
<td><font size = "2em">
 +
<tex>P_1(p,arg)</tex>:
 +
    '''if''' (arg == "print second!")
 +
        '''print'''(<tex>P_2</tex>(p, getSrc(), arg).getSrc())
 +
    '''elseif''' (arg == "print third!")
 +
        '''print'''(p)
 +
    '''else'''
 +
        '''print'''(getSrc())
 +
</font></td>
 +
<td><font size = "2em">
 +
<tex>P_2(p,arg)</tex>:
 +
    '''if''' (arg == "print first!")
 +
        '''print'''(<tex>P_1</tex>(p, getSrc(), arg).getSrc())
 +
    '''elseif''' (arg == "print third!")
 +
        '''print'''(p)
 +
    '''else'''
 +
        '''print'''(getSrc())
 +
</font></td>
 +
</tr>
 +
</table>
 +
 
 +
* подставим код первых двух в третью:
 +
<font size = "2em">
 +
<tex>P_3(p1,p2,arg)</tex>:
 +
    '''if''' (arg == "print first!")
 +
        '''print'''(<tex>P_1</tex>(p1, arg).getSrc())
 +
    '''elseif''' (arg == "print second!")
 +
        '''print'''(<tex>P_2</tex>(p2, arg).getSrc())
 +
    '''else'''
 +
        '''print'''(getSrc())
 +
</font>
 +
 
 +
* применим [[Теорема о рекурсии|теорему о рекурсии]] и заменим оба параметра на исходный код программы:
 +
<font size = "2em">
 +
<tex>P_3(arg)</tex>:
 +
    '''if''' (arg == "print first!")
 +
        '''print'''(<tex>P_1</tex>(getSrc(), arg).getSrc())
 +
    '''elseif''' (arg == "print second!")
 +
        '''print'''(<tex>P_2</tex>(getSrc(), arg).getSrc())
 +
    '''else'''
 +
        '''print'''(getSrc())
 +
</font>
 +
Две оставшиеся программы будут выглядеть аналогично и смогут быть получены путём запуска третьей с каждым из возможных аргументов.
 +
 
 +
== Примечания ==
 +
<references>
 +
<ref name=quineName>Название "квайн" было предложено [http://ru.wikipedia.org/wiki/Хофштадтер,_Дуглас Дугласом Хофштадтером], в его известной книге "Гёдель, Эшер, Бах: Эта бесконечная гирлянда" в честь американского логика и философа  [http://ru.wikipedia.org/wiki/Куайн,_Уиллард_Ван_Орман Уилларда Ван Ормана Квайна], который углублённо изучал явление [http://en.wikipedia.org/wiki/Indirect_self-reference косвенного самоупоминания].</ref>
 +
<ref name=intronName>Название пришло из биологии, где интронами называются части ДНК, не участвующие в синтезе протеинов.</ref>
 +
</references>
 +
 
 +
== Источники информации ==
 +
* [http://www.madore.org/~david/computers/quine.html Madore.org &mdash; Quines (self-replicating programs)]
 +
* [http://habrahabr.ru/post/186782/ Хабрахабр &mdash; Эстафета из 50 квайнов]
 +
* [http://habrahabr.ru/post/188378/ Хабрахабр &mdash; Мультиязыковые квайны]
 +
* [http://habrahabr.ru/post/128191/ Хабрахабр &mdash; Как писать квайны]
 +
* [http://en.wikipedia.org/wiki/Quine_(computing)#Multiquines Wikipedia &mdash; Multi-quines]
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Теория вычислимости]]

Текущая версия на 19:38, 4 сентября 2022

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

Стоит отметить, что программы, использующие для чтения своего кода файловую систему, квайнами не считаются. Например, программа на BASIC вида

10 LIST

выводит на экран свой исходный код, поскольку команда [math]\mathtt{LIST}[/math] просит среду исполнения вывести в консоль текущую программу (эта функция была необходима для программистов, так как код программы зачастую не мог поместиться на консоль 80x25 символов).

Квайн состоит из двух сегментов: кода и данных. Данные представляют собой текстовую версию кода, и, как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код, содержащийся в них, а затем просто выводит данные.

Формально общий принцип написания квайнов содержится в доказательстве теоремы о рекурсии. Далее будет рассмотрено понятие мультиквайна.

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

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

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


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


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

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

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

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

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

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

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

  • напишем для каждого языка "полуквайн":
[math]P_1(p,arg)[/math]:
    if (arg == "print second!")
        print(p)
    else
        print(getSrc()) 
[math]P_2(p,arg)[/math]: 
    if (arg == "print first!")
        print(p)
    else
        print(getSrc()) 
  • подставим код второй программы в первую:

[math]P_1(p,arg)[/math]:
    if (arg == "print second!")
        print([math]P_2[/math](p, arg).getSrc())
    else
        print(getSrc()) 

[math]P_1(arg)[/math]:
    if (arg == "print second!")
        print([math]P_2[/math](getSrc(), arg).getSrc())
    else
        print(getSrc()) 

Вторая программа может быть получена запуском первой с нужным аргументом.

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

  • напишем для него "полуквайн", но уже с двумя параметрами и тремя возможными выводами:

[math]P_3(p1,p2,arg)[/math]:
    if (arg == "print first!")
        print(p1)
    elseif (arg == "print second!")
        print(p2)
    else
        print(getSrc()) 

  • добавим параметр в два уже существующих квайна:
[math]P_1(p,arg)[/math]:
    if (arg == "print second!")
        print([math]P_2[/math](p, getSrc(), arg).getSrc())
    elseif (arg == "print third!")
        print(p)
    else
        print(getSrc()) 
[math]P_2(p,arg)[/math]:
    if (arg == "print first!")
        print([math]P_1[/math](p, getSrc(), arg).getSrc())
    elseif (arg == "print third!")
        print(p)
    else
        print(getSrc()) 
  • подставим код первых двух в третью:

[math]P_3(p1,p2,arg)[/math]:
    if (arg == "print first!")
        print([math]P_1[/math](p1, arg).getSrc())
    elseif (arg == "print second!")
        print([math]P_2[/math](p2, arg).getSrc())
    else
        print(getSrc()) 

[math]P_3(arg)[/math]:
    if (arg == "print first!")
        print([math]P_1[/math](getSrc(), arg).getSrc())
    elseif (arg == "print second!")
        print([math]P_2[/math](getSrc(), arg).getSrc())
    else
        print(getSrc()) 

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

Примечания

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

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