Квайны

Материал из Викиконспекты
Версия от 16:17, 6 января 2015; Xottab (обсуждение | вклад) (→‎Источники информации)
Перейти к: навигация, поиск
Определение:
Квайном (англ. quine)[1] называется программа, которая выводит свой исходный код. При этом, программа не должна использовать внешние данные (например, читать файл со своим исходным кодом).

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

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

Интроны

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

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

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


Определение:
[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]
[math]P_2(p,arg)[/math]
 
if (arg == "print second!")
    print(p)
else
    print(getSrc()) 

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

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

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

if (arg == "print first!")
    print(p1_intron)
elseif (arg == "print third!")
    print(p3_intron)
else
    print(getSrc())

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=43488»