# ruby
l=92.chr;eval s="s=s.dump[r=1..-2].gsub(/("+l*4+"){4,}(?!¥")/){|t|'¥"+l*%d+¥"'%(t
.size/2)};5.times{s=s.dump[r]};puts¥"# python¥¥nprint(¥¥¥"# perl¥¥¥¥nprint(¥¥¥¥¥¥
¥"# lua"+l*4+"nprint("+l*7+"¥"(* ocaml *)"+l*8+"nprint_endline"+l*15+"¥"-- haskel
l"+l*16+"nimport Data.List;import Data.Bits;import Data.Char;main=putStrLn("+l*31
+"¥"/* C */"+l*32+"n#include<stdio.h>"+l*32+"nint main(void){char*s[501]={"+l*31+"¥"++intercalate"+l*31+"¥","+l*31+"¥"(c(tail(init(show("+l*31+"¥"/* Java */"+l*32
+"npublic class QuineRelay{public static void main(String[]a){String[]s={"+l*31+"
¥"++intercalate"+l*31+"¥","+l*31+"¥"(c("+l*31+"¥"brainfuck"+l*64+"n++++++++[>++++
<-]+++++++++>>++++++++++"+l*31+"¥"++(concat(snd(mapAccumL h 2("+l*31+"¥"110"+l*31
+"¥"++g(length s)++"+l*31+"¥"22111211100111112021111102011112120012"+l*31+"¥"++co
ncatMap("+l*32+"c->let d=ord c in if d<11then"+l*31+"¥"21002"+l*31+"¥"else"+l*31+
"¥"111"+l*31+"¥"++g d++"+l*31+"¥"22102"+l*31+"¥")s++"+l*31+"¥"2100211101012021122
2211211101000120211021120221102111000110120211202"+l*31+"¥"))))))++"+l*31+"¥","+l
*63+"¥""+l*64+"n"+l*63+"¥"};int i=0;for(;i<94;i++)System.out.print(s[i]);}}"+l*31
+"¥")))))++"+l*31+"¥",0};int i=0;for(;s[i];i++)printf("+l*63+"¥"%s"+l*63+"¥",s[i]
);puts("+l*63+"¥""+l*63+"¥");return 0;}"+l*31+"¥");c s=map("+l*32+"s->"+l*31+"¥""
+l*63+"¥""+l*31+"¥"++s++"+l*31+"¥""+l*63+"¥""+l*31+"¥")(unfoldr t s);t[]=Nothing;
t s=Just(splitAt(if length s>w&&s!!w=='"+l*31+"¥"'then 501else w)s);w=500;f 0=Not
hing;f x=Just((if x`mod`2>0then '0'else'1'),x`div`2);g x= reverse (unfoldr f x);
h p c=let d=ord c-48in(d,replicate(abs(p-d))(if d<p then'<'else'>')++"+l*31+"¥"
."+l*31+"¥");s="+l*31+"¥"# ruby"+l*32+"n"+l*31+"¥"++"+l*31+"¥"l=92.chr;eval s=¥"+
(z=l*31)+¥"¥¥¥"¥"+s+z+¥"¥¥¥""+l*31+"¥"++"+l*31+"¥""+l*32+"n"+l*31+"¥""+l*15+"¥""+
l*7+"¥")"+l*4+"n¥¥¥¥¥¥¥")¥¥¥")¥"########### (c) Yusuke Endoh, 2009 ###########¥n"
Прога представляет собой код на ruby, который выдает на выходе код на питоне, который выдает на выходе код на перле, который выдает на выходе код на луа, который выдает на выходе код на окамле, который выдает на выходе код на хаскелле, который выдает код на си, который выдает код на яве, который выдает код на брейнфаке, который выдает код на вайтспейсе, который выдает код на анлямбде, который выдает код на руби (в доме, который построил Джек, ага).
Собственно, этюд заключается в том, чтобы понять — как оно вообще работает
P.S.: Я всегда с подозрением относился к японцам, а теперь я их просто боюсь...
Еще рекомендую: Tupper's self-referential formula Polyglot quines (особенно интересен квайн, одинаково хорошо работающий в Ruby, Perl и JavaScript и состоящий только из спецсимволов, без букв и цифр)
Формула сперва показалась мне офигительной, а потом я понял, что это фигня!
Пусть h — высота картинки.
Тогда линейный индекс пиксела j(x,y) = h*x+(y`mod`h)
Функция, возвращающая j-й бит в числе m, b(m,j) = floor(m/2**j)`mod`2
Подставляем b(m,x,y) = b(m,j(x,y))
Избавляемся от m: m = floor(y/h), где y = y0*h+dy
Ну и несложно убедиться, что k/17 — это развёртка по столбцам той самой битмапки.
Так что весь квест — в том, чтобы придумать формулу, занимающую как можно меньшую площадь
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, nikov, Вы писали:
N>>Tupper's self-referential formula
К>Формула сперва показалась мне офигительной, а потом я понял, что это фигня!
полностью согласен. Если разобраться... банально, но, как такое придумать, пока до тебя этого никто раньше не делал.
К>Пусть h — высота картинки. К>Тогда линейный индекс пиксела j(x,y) = h*x+(y`mod`h) К>Функция, возвращающая j-й бит в числе m, b(m,j) = floor(m/2**j)`mod`2 К>Подставляем b(m,x,y) = b(m,j(x,y)) К>Избавляемся от m: m = floor(y/h), где y = y0*h+dy
К>Ну и несложно убедиться, что k/17 — это развёртка по столбцам той самой битмапки. К>Так что весь квест — в том, чтобы придумать формулу, занимающую как можно меньшую площадь
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, nikov, Вы писали:
N>>Tupper's self-referential formula
К>Формула сперва показалась мне офигительной, а потом я понял, что это фигня!
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Прога представляет собой код на ruby, который выдает на выходе код на питоне, который выдает на выходе код на перле, который выдает на выходе код на луа, который выдает на выходе код на окамле, который выдает на выходе код на хаскелле, который выдает код на си, который выдает код на яве, который выдает код на брейнфаке, который выдает код на вайтспейсе, который выдает код на анлямбде, который выдает код на руби (в доме, который построил Джек, ага).
KV>Собственно, этюд заключается в том, чтобы понять — как оно вообще работает
Запустить интерпретаторы оных языков и последовательно посмотреть, что там творится.
Общая идея, как сделать квайн первого ранга (из себя в себя) — несложная.
начало
"начало",
"вывод начала (1 строка)",
"вывод строк с кавычками",
"вывод конца (3-5 строки)"
"конец"
вывод начала (1 строка)
вывод строк с кавычками
вывод конца (3-5 строки)
конец
Строки в кавычках составляют словарь операторов языка программы (язык программы является подмножеством языка программирования).
На самом деле, там немножко хитрее, потому что для вывода кавычек внутри строк придётся либо упражняться с подстановками, либо нарезать строку на более мелкие куски.
Для квайна второго ранга нам потребуются два комплекта операторов
начало
"начало", "nachalo"
"вывод nachala", "vyvod начала"
"вывод s kavychkami", "vyvod с кавычками"
"вывод konca", "vyvod конца"
"конец", "konec"
вывод nachala (стр.1б)
вывод s kavychkami (с учётом экранирования на втором языке)
вывод konca (стр.3б,4б,5б)
конец
Ну и так далее, очевидно, для произвольного ранга: "вывод nachala", "vyvod BEGIN", "print начала"...
Здравствуйте, Кодт, Вы писали:
К>случайно наткнулся на хабре про проекции Футурамы
Ты злодей. Я пока до комментов не дочитал, его имя воспринимал именно так
К>http://habrahabr.ru/blogs/crazydev/47418/ К>может, как-то ими воспользоваться для квайнения... надо подумать.
Для квайнения хз, тоже в голове крутится, что как-то можно. Зато можно новые виды квайнов придумать:
Квайн первой проекции Футамуры: программа, печатающая исходный текст своего интерпретатора, специализированного исходным текстом самой программы
Квайн второй проекции Футамуры: программа, печатающая исходный текст компилятора, специализированного квайном первой проекции
Квайн третьей проекции Футамуры: программа, печатающая исходный текст генератора компиляторов, специализированного квайном второй проекции
Мультиквайн питон-С++, ужасно многословный из-за "чистого" подхода.
Константы захардкожены, — лень было заниматься их программной подстановкой.
Питон...
c = [
'#include <iostream>',
'using namespace std;',
'const char* const c[14] = {',
'};',
'const char* const p[9] = {',
'};',
'int main()',
'{',
' for(int i=0; i!= 1; ++i) cout << p[i] << endl;',
' for(int i=0; i!=14; ++i) cout << char(9) << char(39) << c[i] << char(39) << char(44) << endl;',
' for(int i=1; i!= 3; ++i) cout << p[i] << endl;',
' for(int i=0; i!= 9; ++i) cout << char(9) << char(39) << p[i] << char(39) << char(44) << endl;',
' for(int i=3; i!= 9; ++i) cout << p[i] << endl;',
'}',
]
p = [
'c = [',
' ]',
'p = [',
' ]',
'for i in range(0, 3) : print c[i]',
'for i in range(0,14) : print chr(9)+chr(34)+c[i]+chr(34)+chr(44)',
'for i in range(3, 5) : print c[i]',
'for i in range(0, 9) : print chr(9)+chr(34)+p[i]+chr(34)+chr(44)',
'for i in range(5,14) : print c[i]',
]
for i in range(0, 3) : print c[i]
for i in range(0,14) : print chr(9)+chr(34)+c[i]+chr(34)+chr(44)
for i in range(3, 5) : print c[i]
for i in range(0, 9) : print chr(9)+chr(34)+p[i]+chr(34)+chr(44)
for i in range(5,14) : print c[i]
Как видите, ничего сложного нет.
Кавычки специально взял разные (" = 34 и ' = 39), чтобы показать, что нас это не волнует
А если вместо нескольких разных массивов использовать один (многомерный либо просто последовательный — склеить массивы c[] и p[], и брать правильные индексы) — то всё будет ещё короче!
На эзотерических языках, таких, как батфайлы или брейнфак, будет, конечно, мучительнее.
Например, у батфайлов будет много возни с экранированием процентов.
А у брейнфака структура программы, в силу исходной бедности языка, станет кудрявой (с множеством циклов).
Мультиквайн, кстати, может быть построен и ещё проще.
Поскольку основа квайна — это текст, выводящийся дважды (один раз как есть, другой раз в кавычках), можно построить такую схему
/* prog4 */#include <stdio.h>
void putqs(const char* s)
{
for(;*s;++s)
{
switch(*s)
{
case'\n': puts("\\n"); break;
case'\"': puts("\\\""); break;
case '\\': puts("\\\\"); break;
default: putc(*s);
}
}
}
const char* s[] = {
STRINGIZE( /* prog1 */ ..... const char* s [] = { ), // сами руками сделаете
" \"", // начало строки кода, образующей элемент этого массива"\",\n", // соответственно, конец
STRINGIZE( }; int main() { ..... } ) // сами руками сделаете
};
int main()
{
int k;
// выводим первую часть prog1...
puts(
"/* prog1 */\n"
"#include <stdio.h>\n"
"int main() {\n"
"puts(\""
"/* prog2 */\n"
"#include <stdio.h>\n"
"int main() {\n"
" puts(\""
"/* prog3 */\n"
"#include <stdio.h>\n"
"int main() {\n"
"puts(\""
);
// а вот здесь надо вывести текст prog4!
puts(s[0]);
for(k=0; k!=4; ++k) puts(s[1]), putqs(s[k]), puts(s[2]);
puts(s[3]);
// выводим последнюю часть prog1...
puts(
"\");\n"
"}\n"
"\");\n"
"}\n"
"\");\n"
"}\n"
);
}
ВНИМАНИЕ! Это эскиз, который ещё не работает. Где-то я очепятался с кавычками-шмавычками.
Попробую написать генератор сишного мультиквайна, чтобы избежать ручной работы.
В качестве генератора использую питон и два шаблона на си.
Вкратце, идея этой адской машинки:
Квайн состоит из
1) шаблона программы "printer", выполняющей печать текста — т.е. unescape.
2) шаблона программы "quine", творчески выполняющего escape своего собственного текста, а также принтера.
Шаблон принтера очень простой
/* COMMENT */ // сюда мы будем подвёрстывать какой-нибудь комментарий#include <stdio.h>
int main()
{
printf("%s", "CHILD"); // ну а здесь окажется строка, которую надо вывести
}
Наложение шаблона printer — это escape во время генерации и unescape во время исполнения.
Сначала мы возводим фиктивную строку с маркером /*QUINE*/ в N-ную степень наложения шаблона printer.
Если на этой стадии мы скомпилируем-исполним полученную программу, её вывод будет — (N-1)-я степень.
Проделав эту операцию N раз, снова получим /*QUINE*/
Таким образом, наш N-printer — это программа, представляющая собой строку P1+"/*QUINE*/"+P2
Её легко разбить относительно маркера на P1 и P2 (голову и хвост принтера).
Следующий шаг: рожаем квайн, печатающий себя в окружении принтера!
Его структура такова
// начало строки Q1
//всякие полезности, относящиеся к голове программы
show(const char* s) {.....} // вывод строки как есть
escape(const char* s, int n) {.....} // многократное наложение escapeconst char* s[6] = // набор литеральных текстов (на самом деле, можно и поштучно, но будет больше писанины ниже)
{
// конец строки Q1"SH", // начало префикса литерального текста, т.е. "\t\"""ST", // конец префикса литерального текста, т.е. "\",\n""P1", // первая половина принтера (P1)"Q1", // первая половина квайна (Q1)"Q2", // вторая половина квайна (Q2)"P2", // вторая половина принтера (P1)
// начало строки Q2
};
int main()
{
show(s[2]); // выводим первую половину принтера - совершая однократный unescape c "P1", т.е. получая P1
// помним, что принтер обернул /*QUINE*/ в escape^n - поэтому мы сейчас сделаем то же самое
escape(s[3],n);
// и напедалим строкfor(k=0;k!=6;++k) escape(s[0],n-1), escape(s[k],n), escape(s[1],n-1); // у обрамления, естественно, одним уровнем меньше
escape(s[4],n);
show(s[5]); // выводим вторую половину принтера
}
// конец строки Q2
Назовём наши программы alfa (самый внешний принтер), bravo, charlie, ....., juliet (самый внутренний принтер), kilo (квайн).
Генератор мысленно рожает alfa(bravo(charlie(....(juliet("/*QUINE*/"))....)))
и затем рожает __QUINE.c, являющийся, по сути __kilo.c
Чтобы получить __alfa.c, достаточно скомпилировать и выполнить __QUINE.
Самый сок — в способе эскейпа. Как известно, в Си одни и те же символы можно эскейпнуть разными способами.
— \ превращается в \\ либо в \x5C
— " превращается в \" либо в \x22
Если возведём одиночный бэкслеш в N-ную степень эскейпа, то в первом случае получим 2^N слешей, а во втором — один \ и N x5C (итого 3N+1)
Ну а возведение " вообще рожает фрактал — опять-таки, длиной 2^N, либо один \ и N x22 (аналогично)
Поэтому будьте аккуратны с quines-exp.zip — __alfa.c занимает размер 18 Мегабайт! При том, что __kilo.c — всего лишь 19 килобайт. Немудрено: 2^10 ~ 1000.
А после того, как я избавился от экспоненты, __alfa.c стал 20 килобайт, а __kilo.c — 4.5 килобайт. Т.е. примерно 3 раза.
После избавления от всех лишних пробельных символов и комментариев, получается __alfa.c = 7151 байт, __kilo.c = 2451 байт.
Несложно сделать и гетерогенный квайн.
Только придётся немного допилить мой генератор (он сейчас эскейпит строки строго в сишном синтаксисе), сделать шаблоны принтеров на разных языках — и натравить их друг на друга.
К>Несложно сделать и гетерогенный квайн. К>Только придётся немного допилить мой генератор (он сейчас эскейпит строки строго в сишном синтаксисе), сделать шаблоны принтеров на разных языках — и натравить их друг на друга.
Кстати, стало очевидно, как умудрились подверстать брейнфак и вайтспейс в оригинальный мультиквайн.
Это не квайны, а принтеры. Уж что-что, а вывести произвольный текст — можно на любом языке, даже не тьюринг-полном.
Насколько я понял, квайн там то ли на хаскелле, то ли на яве, а всё остальное — генераторы.
Сейчас не могу запустить исходник на руби, чтобы посмотреть точно. Там какая-то творческая беда с кодировками, один раз получилось, потом случайно стёр и забыл.
К>Что мне здесь не нравится: квайн вынужден уметь эскейпить eall(), а не только e0(). К>То есть, квайн вынужден знать про все остальные языки.
Продумал! Идея состоит в том, что экранирование строки дистрибутивно: e(a+b) = e(a)+e(b)
Вообще-то, это необязательно. Скажем, для брейнфака более короткая запись будет инкрементная:
| > | shift
| >++++++++[-<+++++++++++++>] | plusShift(ord('h')) - оказалось, plusShift даёт более короткий код, чем plus (и тем более plus,print)
| +>++++++++++[-<++++++++++>] | plusShift(ord('e'))
| +>++++++++++[-<++++++++++>] | plusShift(ord('l'))
| >+++++++++[-<++++++++++++>] | plusShift(ord('l'))
| +>++++++++++[-<+++++++++++>] | plusShift(ord('o'))
| <[<]> | shift_left_all - поэтому удобнее сначала всё сконструировать, а потом напечатать
| [.>] | print_all
Таким образом:
1) Для языков 1..N определяем функции экранирования e1..eN и порождения принтеров p1..pN
— к функциям экранирования требование дистрибутивности: e(a+b) = e(a)+e(b)
— к функциям принтеров: p(s) = h + e(s) + t
Функцию eall удобно представить таблично: применить её к каждой букве.
А функцию pall => hall,tall — поиском строки eall(TAG) в строке pall(TAG), хотя, конечно, можно и на основе { (pK,tK) } цепным суммированием (чтобы гарантированно не нарваться на случайное вхождение тэга в код принтера).
3) Гетероквайн на языке 0, печатающий код мультипринтера, печатающего код гетероквайна — содержит
— табличную реализацию eall — тем самым, нам нет нужды кодировать алгоритм на языке квайна и тащить туда знания о языках всех принтеров
— алгоритмическую реализацию e0 — это мы можем позволить
— строки hall,tall
— строки — фрагменты кода квайна с дырками вместо определений строк этих фрагментов
— форматный вывод текста: hall + eall( фрагменты и e0(фрагменты) ) + tall
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Перекуём баги на фичи!
Re[5]: Мультиквайн - вынос мозга
От:
Аноним
Дата:
24.11.09 15:08
Оценка:
а дальше? ^_^
p.s. так не долго и мозговой завороткишок получить
Здравствуйте, <Аноним>, Вы писали:
А>а дальше? ^_^
А дальше сами давайте, присоединяйтесь!
Подзадачи:
1) Как видно, дистрибутивность функции экранирования радикально упрощает нам жизнь. Но для брейнфака, вайтспейса и, наверно, унлямбды, это даёт большую избыточность.
Поэтому было бы интересно по возможности обойтись без дистрибутивности
2) Экранировать можно по-всякому. В том числе — представить строку как массив чисел.
3) Попробовать выразить всё одним-махом-семерых-убивахом:
format=".......";
printf(format,escape(format))
и т.д...
А>p.s. так не долго и мозговой завороткишок получить
Заворот котiв уже случился! Всю неделю в фоновом режиме об этом думаю.
Перекуём баги на фичи!
