Квайны

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

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

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

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

Интроны

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

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

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

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

Би-квайном (англ. 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())

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

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