Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   подписка   модер. 
От: kochetkov.vladimir rsdnhttp://vkochetkov.blogspot.com
Дата: 09.11.09 11:12
Оценка:190 (25) :))) :))) :))) :))) :))) :))) :))) :))) :)))
Сабж:

# 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.: Я всегда с подозрением относился к японцам, а теперь я их просто боюсь...
"Не станет он искать побед. Он ждет, чтоб высшее начало его все чаще побеждало, чтобы расти ему в ответ" (с) Р. Рильке.
Re: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: Muxa
printf("%s", "|---D");
Дата: 09.11.09 15:07
Оценка: :))) :))) :))
показал этот код своей девушке:

Muxa [09/11/2009_5:21 PM] < http://rsdn.ru/forum/etude/3595862.1.aspx


Alinka [09/11/2009_6:05 PM] > баян )

Ищешь программиста CUDA?
Ищу интересные проекты.
Jacket: GPU плагин для Матлаба
Re[2]: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: Кодт модератор 
Дата: 16.11.09 13:33
Оценка:82 (7)
Мультиквайн, кстати, может быть построен и ещё проще.
Поскольку основа квайна — это текст, выводящийся дважды (один раз как есть, другой раз в кавычках), можно построить такую схему

(Пусть это будет Си в 4 степени)
/* prog1 */
#include <stdio.h>
int main() {
    puts("prog2");
}

/* prog2 */
#include <stdio.h>
int main() {
    puts("prog3");
}

/* prog3 */
#include <stdio.h>
int main() {
    puts("prog4");
}

/* prog4 */
#include <stdio.h>
define_magic();
int main() {
    magic_puts("prog1");
}

И именно magic_puts будет отвечать за логику квайна.
Но пока что выполним подстановку...
// подставляем prog1
/* prog4 */
#include <stdio.h>
define_magic();
int main() {
    magic_puts(
        "/* prog1 */\n"
        "#include <stdio.h>\n"
        "int main() {\n"
        "puts(\"prog2\");\n" // появились экранированные кавычки!
        "}\n"
    );
}

// подставляем prog2
/* prog4 */
#include <stdio.h>
define_magic();
int main() {
    magic_puts(
        "/* prog1 */\n"
        "#include <stdio.h>\n"
        "int main() {\n"
        "puts(\""
            "/* prog2 */\n"
            "#include <stdio.h>\n"
            "int main() {\n"
            "    puts(\"prog3\");\n" // в недрах - кавычки экранированы ровно один раз
            "}\n"
        "\");\n"
        "}\n"
    );
}

// подставляем prog3
/* prog4 */
#include <stdio.h>
define_magic();
int main() {
    magic_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\");\n"
                "}\n"
            "\");\n"
            "}\n"
        "\");\n"
        "}\n"
    );
}


Теперь всё готово для квайнения!
/* 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"
    );
}


ВНИМАНИЕ! Это эскиз, который ещё не работает. Где-то я очепятался с кавычками-шмавычками.
Попробую написать генератор сишного мультиквайна, чтобы избежать ручной работы.

Заодно можете сами попробовать сделать это.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Перекуём баги на фичи!
Re[2]: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: kochetkov.vladimir rsdnhttp://vkochetkov.blogspot.com
Дата: 17.11.09 00:26
Оценка: +3 :))) :)
Здравствуйте, Кодт, Вы писали:

К>Написал генератор одноязычных мультиквайнов (си).


Теперь я понимаю, что японцы — это еще не самое страшное...
"Не станет он искать побед. Он ждет, чтоб высшее начало его все чаще побеждало, чтобы расти ему в ответ" (с) Р. Рильке.
Re: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: Кодт модератор 
Дата: 16.11.09 21:14
Оценка:54 (4)
Написал генератор одноязычных мультиквайнов (си).

http://files.rsdn.ru/4783/quines-exp.zip — самый наглядный
http://files.rsdn.ru/4783/quines-gentle.zip — избавился от экспоненты ( )
http://files.rsdn.ru/4783/quines-tiny.zip — убрал все пробелы и комментарии

В качестве генератора использую питон и два шаблона на си.

Вкратце, идея этой адской машинки:
Квайн состоит из
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) {.....} // многократное наложение escape
    
    const 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 байт.




Несложно сделать и гетерогенный квайн.
Только придётся немного допилить мой генератор (он сейчас эскейпит строки строго в сишном синтаксисе), сделать шаблоны принтеров на разных языках — и натравить их друг на друга.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Перекуём баги на фичи!
Re: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: nikovMy buzz
Дата: 09.11.09 15:38
Оценка:26 (3)
Здравствуйте, kochetkov.vladimir, Вы писали:

Еще рекомендую:
Tupper's self-referential formula
Polyglot quines (особенно интересен квайн, одинаково хорошо работающий в Ruby, Perl и JavaScript и состоящий только из спецсимволов, без букв и цифр)
Microsoft MVP 2010
Re[2]: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: Кодт модератор 
Дата: 09.11.09 16:51
Оценка:5 (1) +2
Здравствуйте, 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 — это развёртка по столбцам той самой битмапки.
Так что весь квест — в том, чтобы придумать формулу, занимающую как можно меньшую площадь
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Перекуём баги на фичи!
Re[3]: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: kochetkov.vladimir rsdnhttp://vkochetkov.blogspot.com
Дата: 15.11.09 12:14
Оценка: :)))
Здравствуйте, Кодт, Вы писали:

К>случайно наткнулся на хабре про проекции Футурамы


Ты злодей. Я пока до комментов не дочитал, его имя воспринимал именно так

К>http://habrahabr.ru/blogs/crazydev/47418/

К>может, как-то ими воспользоваться для квайнения... надо подумать.

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

Квайн первой проекции Футамуры: программа, печатающая исходный текст своего интерпретатора, специализированного исходным текстом самой программы
Квайн второй проекции Футамуры: программа, печатающая исходный текст компилятора, специализированного квайном первой проекции
Квайн третьей проекции Футамуры: программа, печатающая исходный текст генератора компиляторов, специализированного квайном второй проекции

"Не станет он искать побед. Он ждет, чтоб высшее начало его все чаще побеждало, чтобы расти ему в ответ" (с) Р. Рильке.
Re[2]: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: Кодт модератор 
Дата: 14.11.09 22:08
Оценка:20 (2)
случайно наткнулся на хабре про проекции Футурамы
http://habrahabr.ru/blogs/crazydev/47418/
может, как-то ими воспользоваться для квайнения... надо подумать.
Перекуём баги на фичи!
Re[2]: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: McSeem2http://www.antigrain.com
Дата: 19.11.09 19:49
Оценка:1 (1) +1
Здравствуйте, Кодт, Вы писали:

К>Написал генератор одноязычных мультиквайнов (си).


Кодт, ты реально крут! Сиреневенькая мозговыколупывательница с преподвыподвертом.
McSeem
Socrates said "to be is to do". Jean-Paul Sartre said "to do is to be". Frank Sinatra said "to be do be do".
Re[7]: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: Spiceman 
Дата: 24.11.09 16:41
Оценка: +1 :)
Здравствуйте, Кодт, Вы писали:

А>>а дальше? ^_^

К>А дальше сами давайте, присоединяйтесь!

Прочитал всю тему, под конец начался смех, переходящий в истерический Я даже не понял, какую тут задачу решают. Кодт, а ты взглядом быка можешь повалить?
Re: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: Кодт модератор 
Дата: 14.11.09 19:26
Оценка:5 (1)
Здравствуйте, 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 начала"...
Перекуём баги на фичи!
Re[2]: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: Кодт модератор 
Дата: 19.12.09 21:22
Оценка:1 (1)
Здравствуйте, xonixx, Вы писали:

X>Чисто для протокола


X>http://habrahabr.ru/blogs/crazydev/75663/


Чисто для протокола, может, и ссылку на здешнюю дискуссию кинешь на хабр?
Перекуём баги на фичи!
Re[2]: Мультиквайн - вынос мозга в избранное  msdn  новое ответить    Оценить +1123x:) +-   модер. 
От: McSeem2http://www.antigrain.com
Дата: 19.11.09 20:30
Оценка: :)
Здравствуйте, Кодт, Вы писали:

К>Написал генератор одноязычных мультиквайнов (си).


Кстати, вот вам и ответ на главный вопрос о Жизни, Вселенной и всего такого — в оценках получилось 42. Просьба не портить!
McSeem
Socrates said "to be is to do". Jean-Paul Sartre said "to do is to be". Frank Sinatra said "to be do be do".