Изменения

Перейти к: навигация, поиск

Квайны

882 байта добавлено, 16:09, 6 января 2015
Нет описания правки
|definition='''Квайном''' (англ. ''quine'')<ref name=quineName/> называется программа, которая выводит свой исходный код. При этом, программа не должна использовать внешние данные (например, читать файл со своим исходным кодом).
}}
 
==Общий принцип написания квайнов==
Квайн состоит из двух сегментов: <b>кода</b> и <b>данных</b>. Данные представляют собой текстовую версию кода, и, как правило, получаются из кода простым добавлением обрамляющих кавычек. Код, в свою очередь, сначала использует данные, чтобы вывести код(содержащийся в них), а затем, просто выводит данные.
==Интроны==
{{Определение
|definition='''Интроном''' (англ. ''intron'') <ref name=intronName/> называется часть сегмента данных, которая не используется для вывода кода, но сохраняющаяся в процессе саморепликации квайна.
}}
Название пришло из биологии, где интронами называются части ДНК, не участвующие в синтезе протеинов.
 
==Мульти-квайны==
{{Определение
*при обычном запуске она выводит свой исходный код,
*при запуске с особым аргументом она выводит исходный код своего "брата" на другом языке программирования.
Её брат делает то же самое: выводит свой код при запуске без аргументов и выводит код оригинальной программы при запуске с переданным спец. специальным аргументом.
}}
{{Определение
|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>. И наконец, зафиксируем как параметр первой исходник исходный код второй и наоборот.
}}
===Принцип написания===
Будем следовать доказательству и напишем мульти-квайн для двух языков. Далее покажем, как добавить новый язык.
# * напишем для каждого языка "полу-квайн": <table><tr><td><center><tex>PP_1(p,arg): </tex></center></td><td><center><tex>P_2(p,arg)</tex></center></td></tr>\left\{<tr> \begin{array}{l l}<td><code><font size = "2em"> P if (p,arg == "shazamprint second!") \rightarrow print(p); else print(getSrc()) </font></code></td><td><code><font size = "2em"> \\if (arg == "print first!") P print(p,null) \rightarrow else print(P.getSrc()); \end{array}</font></code></td> \right.</tr></textable># * добавим код каждой из программ интроном в код другой# * модифицируем каждую из программ, чтобы вместо <tex>p</tex> она выводила интрон: <table><tr><td><center><tex>P_1(arg)</tex></center></td><td><center><tex>PP_2(arg): </tex></center></td></tr>\left\{<tr> \begin{array}{l l}<td><code><font size = "2em"> P if (arg == "shazamprint second!") \rightarrow print(intronp2_intron); else print(getSrc()) </font></code></td><td><code><font size = "2em"> \\if (arg == "print first!") P print(nullp1_intron) \rightarrow else print(P.getSrc()); \end{array}</font></code></td> \right.</tr></textable>
Теперь добавим третий язык:
# * напишем для него "полу-квайн", но уже с двумя параметрами и тремя возможными выводами:<code><font size = "2em"> <tex>P_3(pp1,p2,arg)</tex>: \left\{ \begin{array}{l l} P_3 if (p1,p2,arg == "shazamprint first!") \rightarrow print(p1); \\ P_3 elseif (p1,p2,arg == "cadabraprint second!") \rightarrow print(p2); \\ P_3(p1,p2,null) \rightarrow else print(P_3.getSrc()); \end{array} \right.</texfont></code># * добавим третье условие в два уже существующих квайна: <table><tr><td><center><tex>PP_1(p,arg): </tex></center></td><td><center><tex>P_2(p,arg)</tex></center></td></tr>\left\{<tr> \begin{array}{l l}<td><code><font size = "2em"> P if (p,arg == "shazamprint second!") \rightarrow print(intronp2_intron); \\elseif (arg == "print third!") P print(p,) else print(getSrc())</font></code></td><td><code><font size = "2em"> if (arg == "cadabraprint first!") \rightarrow print(pp1_intron) elseif (arg == "print third!"); \\ P print(p,null) \rightarrow else print(P.getSrc()); \end{array}</font></code></td> \right.</tr></textable># * подставим код первых двух интронами в третью, а код третьей - вторым интроном в каждую из двух первых: <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>P</center></td></tr><tr><td><code><font size = "2em"> if (arg == "print second!") print(p2_intron) elseif (arg== "print third!") print(p3_intron) else print(getSrc(): )</font></code></td><td><code><font size = "2em"> \left\{ if (arg == "print first!") \begin{array}{l l} print(p1_intron) P elseif (arg == "shazamprint third!") \rightarrow print(intron1p3_intron); \\else P print(getSrc())</font></code></td><td><code><font size = "2em"> if (arg == "cadabraprint first!") \rightarrow print(intron2p1_intron); \\ P elseif (nullarg == "print second!") print(p2_intron) \rightarrow else print(P.getSrc()); \end{array}</font></code></td> \right.</tr></textable>
== Примечания ==
<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; Как писать квайны]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
262
правки

Навигация