| 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 своего собственного текста, а также принтера. Шаблон принтера очень простой
Наложение шаблона printer — это escape во время генерации и unescape во время исполнения. Сначала мы возводим фиктивную строку с маркером /*QUINE*/ в N-ную степень наложения шаблона printer. Если на этой стадии мы скомпилируем-исполним полученную программу, её вывод будет — (N-1)-я степень. Проделав эту операцию N раз, снова получим /*QUINE*/ Таким образом, наш N-printer — это программа, представляющая собой строку P1+"/*QUINE*/"+P2 Её легко разбить относительно маркера на P1 и P2 (голову и хвост принтера). Следующий шаг: рожаем квайн, печатающий себя в окружении принтера! Его структура такова
Назовём наши программы 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>> Перекуём баги на фичи! |