Re: Мультиквайн - вынос мозга в избранное  новое ответить всё   подписка   модер. 
От: Кодт модератор 
Дата: 16.11.09 20: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>>
Перекуём баги на фичи!