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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎Принцип написания)
Строка 2: Строка 2:
 
|definition='''Квайном''' (англ. ''quine'')<ref name=quineName/> называется программа, которая выводит свой исходный код. При этом, программа не должна использовать внешние данные (например, читать файл со своим исходным кодом).
 
|definition='''Квайном''' (англ. ''quine'')<ref name=quineName/> называется программа, которая выводит свой исходный код. При этом, программа не должна использовать внешние данные (например, читать файл со своим исходным кодом).
 
}}
 
}}
 +
Стоит отметить, что программы, использующие для чтения своего кода файловую систему, квайнами не считаются. Например, программа на BASIC вида
 +
<code><font size = "2em">
 +
10 LIST
 +
</font></code>
 +
выводит на экран свой исходный код, поскольку команда <tex>\mathtt{LIST}</tex> просит среду исполнения вывести в консоль текущую программу (эта функция была необходима для программистов, т.к. код программы зачастую не мог поместиться на консоль 80x25 символов)
 +
 
Квайн состоит из двух сегментов: <b>кода</b> и <b>данных</b>. Данные представляют собой текстовую версию кода, и, как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код(содержащийся в них), а затем, просто выводит данные.
 
Квайн состоит из двух сегментов: <b>кода</b> и <b>данных</b>. Данные представляют собой текстовую версию кода, и, как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код(содержащийся в них), а затем, просто выводит данные.
  
 
Формально общий принцип написания квайнов содержится в доказательстве [[Теорема о рекурсии|теоремы о рекурсии]]. Далее будет рассмотрено понятие мульти-квайна.
 
Формально общий принцип написания квайнов содержится в доказательстве [[Теорема о рекурсии|теоремы о рекурсии]]. Далее будет рассмотрено понятие мульти-квайна.
  
−
==Интроны==
 
−
{{Определение
 
−
|definition='''Интроном''' (англ. ''intron'')<ref name=intronName/> называется часть сегмента данных, которая не используется для вывода кода, но сохраняющаяся в процессе саморепликации квайна.
 
−
}}
 
 
==Мульти-квайны==
 
==Мульти-квайны==
 
{{Определение
 
{{Определение
Строка 21: Строка 23:
 
}}
 
}}
 
Заметим, что требование, чтобы программы были на разных языках программирования важно, т.к. иначе все программы смогут иметь один и тот же код.
 
Заметим, что требование, чтобы программы были на разных языках программирования важно, т.к. иначе все программы смогут иметь один и тот же код.
−
 
+
===Связанные определения===
 +
{{Определение
 +
|definition='''Интроном''' (англ. ''intron'')<ref name=intronName/> называется часть сегмента данных, которая не используется для вывода кода, но сохраняющаяся в процессе саморепликации квайна.
 +
}}
 +
===Принцип написания===
 
{{
 
{{
 
Теорема
 
Теорема
Строка 35: Строка 41:
 
* напишем для каждого языка "полу-квайн":
 
* напишем для каждого языка "полу-квайн":
 
<table>
 
<table>
−
<tr>
 
−
<td><center><tex>P_1(p,arg)</tex></center></td>
 
−
<td><center><tex>P_2(p,arg)</tex></center></td>
 
−
</tr>
 
 
<tr>
 
<tr>
 
<td><code><font size = "2em">  
 
<td><code><font size = "2em">  
−
  if (arg == "print second!")
+
  <tex>P_1(p,arg)</tex>:
−
    print(p)
+
    '''if''' (arg == "print second!")
−
else
+
        '''print'''(p)
−
    print(getSrc())  
+
    '''else'''
 +
        '''print'''(getSrc())  
 
</font></code></td>
 
</font></code></td>
−
<td><code><font size = "2em">  
+
<td><code><font size = "2em">
−
  if (arg == "print first!")
+
  <tex>P_2(p,arg)</tex>:
−
    print(p)
+
    '''if''' (arg == "print first!")
−
else
+
        '''print'''(p)
−
    print(getSrc())  
+
    '''else'''
 +
        '''print'''(getSrc())  
 
</font></code></td>
 
</font></code></td>
 
</tr>
 
</tr>
Строка 57: Строка 61:
 
* модифицируем каждую из программ, чтобы вместо <tex>p</tex> она выводила интрон:  
 
* модифицируем каждую из программ, чтобы вместо <tex>p</tex> она выводила интрон:  
 
<table>
 
<table>
−
<tr>
 
−
<td><center><tex>P_1(arg)</tex></center></td>
 
−
<td><center><tex>P_2(arg)</tex></center></td>
 
−
</tr>
 
 
<tr>
 
<tr>
 
<td><code><font size = "2em">  
 
<td><code><font size = "2em">  
−
  if (arg == "print second!")
+
  <tex>P_1(arg)</tex>:
−
    print(p2_intron)
+
    '''if''' (arg == "print second!")
−
else
+
        '''print'''(p2_intron)
−
    print(getSrc())  
+
    '''else'''
 +
        '''print'''(getSrc())  
 
</font></code></td>
 
</font></code></td>
 
<td><code><font size = "2em">  
 
<td><code><font size = "2em">  
−
  if (arg == "print first!")
+
  <tex>P_2(arg)</tex>:
−
    print(p1_intron)
+
    '''if''' (arg == "print first!")
−
else
+
        '''print'''(p1_intron)
−
    print(getSrc())  
+
    '''else'''
 +
        '''print'''(getSrc())  
 
</font></code></td>
 
</font></code></td>
 
</tr>
 
</tr>
Строка 80: Строка 82:
 
<code><font size = "2em">  
 
<code><font size = "2em">  
 
  <tex>P_3(p1,p2,arg)</tex>:
 
  <tex>P_3(p1,p2,arg)</tex>:
−
     if (arg == "print first!")
+
     '''if''' (arg == "print first!")
−
         print(p1)
+
         '''print'''(p1)
−
     elseif (arg == "print second!")
+
     '''elseif''' (arg == "print second!")
−
         print(p2)
+
         '''print'''(p2)
−
     else
+
     '''else'''
−
         print(getSrc())  
+
         '''print'''(getSrc())  
 
</font></code>
 
</font></code>
 
* добавим третье условие в два уже существующих квайна:  
 
* добавим третье условие в два уже существующих квайна:  
 
<table>
 
<table>
−
<tr>
 
−
<td><center><tex>P_1(p,arg)</tex></center></td>
 
−
<td><center><tex>P_2(p,arg)</tex></center></td>
 
−
</tr>
 
 
<tr>
 
<tr>
 
<td><code><font size = "2em">  
 
<td><code><font size = "2em">  
−
  if (arg == "print second!")
+
  <tex>P_1(p,arg)</tex>:
−
    print(p2_intron)
+
    '''if''' (arg == "print second!")
−
elseif (arg == "print third!")
+
        '''print'''(p2_intron)
−
    print(p)
+
    '''elseif''' (arg == "print third!")
−
else
+
        '''print'''(p)
−
    print(getSrc())
+
    '''else'''
 +
        '''print'''(getSrc())
 
</font></code></td>
 
</font></code></td>
 
<td><code><font size = "2em">  
 
<td><code><font size = "2em">  
−
  if (arg == "print first!")
+
  <tex>P_2(p,arg)</tex>:
−
    print(p1_intron)
+
    '''if''' (arg == "print first!")
−
elseif (arg == "print third!")
+
        '''print'''(p1_intron)
−
    print(p)
+
    '''elseif''' (arg == "print third!")
−
else
+
        '''print'''(p)
−
    print(getSrc())
+
    '''else'''
 +
        '''print'''(getSrc())
 
</font></code></td>
 
</font></code></td>
 
</tr>
 
</tr>
Строка 114: Строка 114:
 
* подставим код первых двух интронами в третью, а код третьей - вторым интроном в каждую из двух первых:
 
* подставим код первых двух интронами в третью, а код третьей - вторым интроном в каждую из двух первых:
 
<table>
 
<table>
−
<tr>
 
−
<td><center><tex>P_1(arg)</tex></center></td>
 
−
<td><center><tex>P_2(arg)</tex></center></td>
 
−
<td><center><tex>P_3(arg)</tex></center></td>
 
−
</tr>
 
 
<tr>
 
<tr>
 
<td><code><font size = "2em">  
 
<td><code><font size = "2em">  
−
  if (arg == "print second!")
+
  <tex>P_1(arg)</tex>:
−
    print(p2_intron)
+
    '''if''' (arg == "print second!")
−
elseif (arg == "print third!")
+
        '''print'''(p2_intron)
−
    print(p3_intron)
+
    '''elseif''' (arg == "print third!")
−
else
+
        '''print'''(p3_intron)
−
    print(getSrc())
+
    '''else'''
 +
        '''print'''(getSrc())
 
</font></code></td>
 
</font></code></td>
 
<td><code><font size = "2em">  
 
<td><code><font size = "2em">  
−
  if (arg == "print first!")
+
  <tex>P_2(arg)</tex>:
−
    print(p1_intron)
+
    '''if''' (arg == "print first!")
−
elseif (arg == "print third!")
+
        '''print'''(p1_intron)
−
    print(p3_intron)
+
    '''elseif''' (arg == "print third!")
−
else
+
        '''print'''(p3_intron)
−
    print(getSrc())
+
    '''else'''
 +
        '''print'''(getSrc())
 
</font></code></td>
 
</font></code></td>
 
<td><code><font size = "2em">  
 
<td><code><font size = "2em">  
−
  if (arg == "print first!")
+
  <tex>P_3(arg)</tex>:
−
    print(p1_intron)
+
    '''if''' (arg == "print first!")
−
elseif (arg == "print second!")
+
        '''print'''(p1_intron)
−
    print(p2_intron)
+
    '''elseif''' (arg == "print second!")
−
else
+
        '''print'''(p2_intron)
−
    print(getSrc())
+
    '''else'''
 +
        '''print'''(getSrc())
 
</font></code></td>
 
</font></code></td>
 
</tr>
 
</tr>

Версия 16:49, 6 января 2015

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

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

10 LIST

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

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

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

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

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


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

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

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

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

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

Теорема (о существовании мульти-квайнов):
На любом языке программирования можно написать мульти-квайн
Доказательство:
[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[/math] она выводила интрон: 
[math]P_1(arg)[/math]:
    if (arg == "print second!")
        print(p2_intron)
    else
        print(getSrc()) 

[math]P_2(arg)[/math]:
    if (arg == "print first!")
        print(p1_intron)
    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(p2_intron)
    elseif (arg == "print third!")
        print(p)
    else
        print(getSrc())

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

[math]P_2(arg)[/math]:
    if (arg == "print first!")
        print(p1_intron)
    elseif (arg == "print third!")
        print(p3_intron)
    else
        print(getSrc())

[math]P_3(arg)[/math]:
    if (arg == "print first!")
        print(p1_intron)
    elseif (arg == "print second!")
        print(p2_intron)
    else
        print(getSrc())

Примечания

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Квайны&oldid=43490»