Мультиквайногенератор

На хабре месячник квайнов, поэтому хочу поделиться своими разработками, которые проделывал ещё четыре года назад.

Хороший мультиквайн — это произведение инженерного искусства, но…
При взгляде на очередную порцию «помех на телеграфной линии», у обычного программиста возникает лишь изумление: «как такое вообще возможно», и «кем был тот сумрачный тевтонский гений».
Я хочу сорвать покровы и показать, как легко писать мультиквайн любой степени сложности на любом наборе языков программирования, включая вайтспейс и брейнфак.

Поскольку мы имеем дело с текстами программ и результатами их исполнения, то было бы естественно взглянуть на это дело как на функции над строками.

Функции

Какие функции у нас есть?
Во-первых, это интерпретатор: он берёт текст программы, компилирует, запускает, — и возвращает текст со стандартного вывода.
Назовём эту функцию просто: RUN.
Поскольку мы не будем ограничиваться одним языком, то, на самом деле, у нас есть целое семейство: RUNpython, RUNc, RUNbrainfuck…
Понятно, что функции эти реализованы по-разному, но как именно — нас это не должно волновать. Ведь мы не пишем свой интерпретатор языка, а тем более, на этом же языке.
Вообще, главная реализация сейчас будет у нас в голове, потому что мы будем решать строковые уравнения.

Во-вторых, важное семейство функций — это декораторы и литераторы. Декоратор берёт произвольную строку и заменяет в ней спецсимволы, а потом литератор обрамляет строку кавычками.
L x = qopen + D x + qclose
Важное свойство декораторов — ассоциативность по операции сложения (конкатенации) строк: E (x+y) = Ex + Ey.

Кстати, сразу договоримся: для компактности записи, функции будут большими буквами, строки маленькими, Fx — применение функции F к x, FGx — применение F к Gx, или, что то же самое, применение композиции FG к x.

Квайны

Если взглянуть на самый маленький квайн на Си,

char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";main(){printf(f,34,f,34,10);} 

то увидим характерный паттерн. Здесь два фрагмента программы повторяются два раза — один раз как текст верхнего уровня, другой раз — как строковый литерал.

Так и запишем: quine = a + b + Ea + c + Ee + d + e

Точно по такой же схеме можем сделать и квайн на питоне:

s1,s2 = 's1,s2 = ', "\nprint s1+repr(s1)+', '+repr(s2)+s2" print s1+repr(s1)+', '+repr(s2)+s2 

Или, чуть более наглядно и многословно:

# this is quine s1 = '# this is quine' s2 = 'print s1\nprint "s1="+repr(s1)\nprint "s2="+repr(s2)\nprint s2' print s1 print "s1="+repr(s1) print "s2="+repr(s2) print s2 

Подстроки a и e — содержательные, большие тексты, которые нереально сгенерировать программно; подстроки b,c,d — клей, обычно состоящий из кавычек, переводов каретки и т. п.

Кстати о наглядности. Текст программы бывает удобно считать не монолитной строкой, а списком строк. В другой статье я обязательно вернусь к этому, и покажу пару способов, как работать со списками.
А пока что вернёмся к квайну.
Функция RUN определена для квайна: RUN quine = quine.
То есть, квайн — это неподвижная точка функции RUN.
Давайте чуть-чуть обобщим квайн. Что, если мы научимся выводить произвольные строки произвольными способами?

Q(F,f,g,h,i,j) = a + b + Ef + c + Ej + d + e -- где a,b,c,d,e как-то зависят (реализуют) F и g,h,i. RUN Q(F,f,g,h,i,j) = f + g + Ff + h + Fj + i + j 

На том же питоне:

# this is Q def F(s) :     ''' подставьте сюда код реализации F на питоне ''' s1 = 'Ef' s2 = 'Ej' print s1 + 'Eg' + F(s1) + 'Eh' + F(s2) + 'Ei' + s2 # где Ef, Eg, Eh, Ei, Ej — экранированные строки-аргументы 

Квайн — это решение уравнения подстановки: RUN Q(F,f,g,h,i,j) = Q(F,f,g,h,i,j)

RUN Q(F,f,g,h,i,j) = f + b + Ff + c + Fj + d + e     Q(F,f,g,h,i,j) = a + b + Ff + c + Ej + d + e 

Откуда F=E, т. е. программный способ декорирования совпадает с декорированием по правилам языка; фрагменты текста — ясно, что с чем совпадает.

Ещё одно отступление: даже в рамках одного языка декораторы могут быть очень и очень разными. Мы можем представить строки в виде массива чисел, например.
Тогда вывод «строки» 104, 97, 98, 114 — это print ».join(map(chr),xs), а вывод в декорированном виде — это print ‘,’.join(map(str),xs).

Обратите внимание: функции RUN и Q определены над строками (Q — вообще функция высшего порядка, определённая над строками и функцией), но реализация их лежит вне целевого языка программирования, на котором мы пишем квайн. Тогда как функция E должна быть реализована, как текст на целевом языке!

Принтеры

А теперь давайте посмотрим на ещё одну, очень простую программу. Эта программа печатает заданный текст.

printer = p + Sq + r RUN printer = q 

где S — некоторый способ декорированного хранения текста.

Поскольку принтер мы можем написать для совершенно произвольного текста, то сделаем функцию:

P(q) = p + Sq + r 

Разумеется, инвариант: RUN P(q) = q
То есть, принтер является функцией, обратной к интерпретатору!

На Си:

#include <stdio.h> int main() { printf("%s", "hello\nhabr"); return 0; } 

На питоне:

print """ hello RSDN """ 

То есть, функция S здесь совпадает со старой доброй E. (На питоне — так даже попроще, не придётся экранировать перевод строки).
А здесь — не совпадает:

#include <stdio.h> int main() {   putchar(114);putchar(115);putchar(100);putchar(110);   return 0; } 

Принтер P выгодно отличается от квайна Q тем, что его элементы — p и r — не зависят от параметров функции.

Из принтера легко сделать метапринтер: программу, которая печатает программу, которая печатает текст.

Pmeta (q) = PPq = P(p + Sq + r) = p + S(p + Sq + r) + r = p + Sp + SSq + Sr + r pmeta = p + Sp Smeta = SS rmeta = Sr + r  RUN (RUN( Pmeta(q) )) = q 

Никто не мешает нам сделать и многоязычный принтер:

Pbilingua(q) = P'P"q = P'(p" + S"q + r") = p' + S'p" + S'S"q + S'r" + r' RUN"(RUN'(Pbilingua(q))) = RUN"(RUN'(P'P"(q))) = RUN"(P"(q)) = q 

И вообще, сколько угодно языков можно задействовать:

Pmulti(q) = pmulti + Smultiq + rmulti pmulti = p1 + S1p2 + S1S2p3 + S1S2S3p4 Smulti = S1S2S3S4 rmulti = S1S2S3r4 + S1S2r3 + S1r2 + r1 

Всё, что нам нужно — это научиться делать композицию функций декораторов. (Об этом — ниже).

И ещё один принтер, для полноты картины: это нуль-принтер P0(text) = text

p0 = "" r0 = "" S0 = id 

Пинг-понг

Ну а теперь давайте скрестим принтер (или мультипринтер) и квайн.
Вот здесь уже потребуется решение уравнения.
Назовём эти программы пингом и понгом:

RUN ping = pong RUN pong = ping 

И пусть ping — это принтер P(pong), а pong — что-то более затейливое. Если бы это был P(ping), то получилась бы бесконечно раскрывающаяся строка, а нам хочется конечное решение.
Итак, пусть pong = Q(F,f,g,h,i,j).
Подставляем:

ping = P pong   = p + S pong + r                 = p + S(a + b + Ef + c + Ej + d + e) + r                 = p + Sa + Sb + SEf + Sc + SEj + Sd + Se + r                 = (p + Sa + Sb) +    SEf + Sc + SEj +     (Sd + Se + r) ping = RUN pong =       f       + g + Ff +  h +  Fj + i +        j 

Почему именно так, f = p+Sa+Sb, а не g=Sa+Sb, например?
Дело в том, что f и j специально предназначены для рекурсии: мы легко можем упоминать в них фрагменты исходного кода pong’а (подстроки a,b,d,e), тогда как рекурсия в составе g, h, i нежелательна.

Итак, мы получили
pong = a+b + E(p+Sa+Sb) + c + E(Sd+Se+r) + d+e

и где-то в недрах a или e прячутся функция F = SE и строка ESc.
Заметьте: если e содержит ESc, рекурсия не возникает, потому что c не зависит от e.

Давайте теперь избавимся от этих «в недрах прячутся». Возьмём другую функцию.
Пусть

pong = R(F,x,y,z) = a + Ex + b + Ez + c + Ey + d RUN    R(F,x,y,z) = x + Fx + y + Fz + z  P   pong = p+Sa + SEx + Sb + SEz + Sc+SEy+Sd+r RUN pong =  x   +  Fx +  y +  Fz +      z 

Так мы получили:

F = SE x = p+Sa y = Sb z = Sc+SEy+Sd+r = Sc + SESb + Sd + r 

Если же определить понг чуть по-другому,

pong = R(F,x,y,z) = a + Ex + b + Ey + b + Ez + c RUN    R(F,x,y,z) = x + Fx + y + Fy + y + Fz + z 

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

P pong   = p+Sa + SEx + Sb + SEy + Sb + SEz + Sc+r RUN pong =  x   +  Fx +  y +  Fy +  y +  Fz +   z 

Таким образом, если у нас есть заготовки для P = {S, p,r} и для R = {E,a,b,c}, то мы тут же превратим их в пинг-понг. И не забываем, что P может быть мультипринтером. Тогда пинг-понг будет осциллировать с периодом n+1, где n — кратность мультипринтера. А если P — нуль-принтер, то пинг-понг осциллирует с периодом 1 и (кто бы мог подумать?) становится квайном.

Последнее, что нам осталось, — это сделать композицию SE.
Формально задача звучит так.
Дано: язык программирования понга; декораторы E и S, причём E родной для этого языка, а S — любой.
Найти: текст подпрограммы на языке понга, реализующий декоратор SE.
А заодно, реализовать декораторы E и SE на языке среды разработки. Мы ведь хотим автоматизировать порождение мультиквайнов?

Для этого ещё раз посмотрим, как устроены декораторы.
Декоратор дистрибутивен по сложению: F(a+b) = Fa + Fb.
Если разбить строку на элементарные части — односимвольные строки, то получим
F(abcd…) = Fa + Fb + Fc + Fd + …
Декораторы ассоциативны:
FG(abcd…) = FGa + FGb + FGc + FGd + …

Поэтому мы можем представить декоратор в виде таблицы кодирования каждого символа, а композицию пересчитать в таблицу с тем же количеством ключей, но с более длинными значениями.

Таким образом, план работы получился следующий:
Дано:

• — принтеры {Sk,pk,rk}</сode> на неизвестно каких языках (всё, что нам нужно — это только табличные реализации функций Sk);</li> <li>— шаблон понга <code>{E,a(F),b,c(F)}, где a или d резервируют место для произвольной таблицы кодирования F (поэтому a и c — не строки и не функции над строками, а функции высшего порядка)

1. Находим мультипринтер {S,p,r}, вычисляя S1S2... по таблицам.
2. Находим таблицу F = SE.
3. При желании, находим минимальный алфавит — множество символов, составляющих p,r,Sa,Sb,Sc,Sd. Это для того, чтобы не громоздить таблицу кодирования всего ASCII или, не дай бог, юникода.
4. Подвёрстываем таблицу в a или c.
5. Находим x=(p+Sa), y=(Sb), z=(Sc+r).
6. Формируем понг: a+Ex+b+Ey+b+Ey+c.

Всё!

А поскольку все эти шаги слишком трудоёмко делать вручную, то давайте напишем генератор квайнов.
Вот, для затравки, код на питоне, который (на данный момент) делает мультиквайны из питона и си.
Дополнить его любыми другими языками — дело десяти минут.

#-*- coding: utf-8 -*-  # декораторы - функции, переводящие символ в строку  def I(c) : 	''' id-декоратор, переводит символ в символ''' 	return c  def C(c) : 	''' декоратор для си и питона ''' 	if c=='"' or c=='\\' or ord(c)<32 or ord(c)>126 : 		return '\\%03o' % ord(c) 		# сейчас, для простоты, все спецсимволы кодируются восьмеричным номером 		# потому что кавычки и бэкслеши будут удваиваться при каждой композиции декораторов, 		# а шестнадцатеричные коды плохо склеиваются: \x24bad - это код символа chr(0x24BAD), а не строка $bad 	else : 		return c  def decor(F,s) : 	''' применение декоратора к строке ''' 	return ''.join(map(F,s)) # применяем к каждому символу и склеиваем  def compose(F,G) : 	''' композиция декораторов ''' 	return lambda c : decor(F,G(c))  # принтеры - кортежи (S,p,r)  def make_printer(S, tpl, tag = '<-T->') : 	''' создаёт принтер из шаблона программы (метка <-T-> означает, куда подставлять текст) ''' 	p,r = tpl.split(tag) 	return S,p,r  nul_printer = (I,'','')  def show_printer(prn, t) : 	''' выводит исходный код принтера заданного текста t ''' 	S,p,r = prn 	return p + decor(S,t) + r  def meta_printer(prn1, prn2) : 	''' композиция принтеров ''' 	S1,p1,r1 = prn1 	S2,p2,r2 = prn2 	S = compose(S1,S2) 	p = p1 + decor(S1,p2) 	r = decor(S1,r2) + r1 	return S,p,r  # квайнер - то, что выше я называл понгом - кортеж (E, am, b, cm) # где am и cm - функции decorator -> string  def make_quiner(E, M, tpl, tagX = '<-X->', tagF = '<-F->') : 	''' 	создаёт квайнер из шаблона программы 	метка <-X-> встречается трижды и отмечает вхождения строк x,y,z, 	метка <-F-> отмечает, куда подвёрстывать таблицу декоратора F 	функция E - родной декоратор, функция M порождает таблицу для произвольного декоратора 	''' 	a,b,b_,c = tpl.split(tagX) 	assert b==b_ 	am = lambda F : a.replace(tagF, M(F)) if tagF in a else a 	cm = lambda F : c.replace(tagF, M(F)) if tagF in c else c 	return E,am,b,cm  def show_quiner(qnr, F,x,y,z) : 	''' 	выводит исходник квайнера для данного декоратора и строк 	a,Ex,b,Ey,b,Ez,c -- исходник 	x,Fx,y,Fy,y,Fz,z -- то, что он будет выводить (RUN) 	''' 	E,am,b,cm = qnr 	a,c = am(F), cm(F) 	ex,ey,ez = decor(E,x), decor(E,y), decor(E,z) 	return a + ex + b + ey + b + ez + c  def show_quiner_printer(qnr,prn) : 	''' 	решает уравнение и выводит мультиквайн 	p+Sa,SEx,Sb,SEy,Sb,SEz,Sc+r -- исходник принтера 	x   , Fx,  y , Fy,  y , Fz,   z -- результат работы квайнера 	''' 	E,am,b,cm = qnr 	S,p,r = prn 	F = compose(S,E) 	a,c = am(F), cm(F) 	x = p + decor(S,a) 	y = decor(S,b) 	z = decor(S,c) + r 	ex,ey,ez = decor(E,x), decor(E,y), decor(E,z) 	return a + ex + b + ey + b + ez + c  #############################################################  # квайнеры на разных языках :  c_quine_tpl = '''/* C quine */ #include <stdio.h> const char* f[128] = {<-F->}; const char* xyz[3] = {"<-X->", "<-X->", "<-X->"}; void ps(const char* s) { while(*s) putchar(*s++); } void pm(const char* s) { while(*s) ps(f[*s++]); } int main() {   ps(xyz[0]); /*  x */   pm(xyz[0]); /* Fx */   ps(xyz[1]); /*  y */   pm(xyz[1]); /* Fy */   ps(xyz[1]); /*  y */   pm(xyz[2]); /* Fz */   ps(xyz[2]); /*  z */   return 0; } ''' def c_quine_M(F) : 	''' таблица кодов - сишные строки через запятую ''' 	codes = [ '"%s"' % decor(C,decor(F,chr(i))) for i in xrange(128) ] 	return ', '.join(codes)  c_quiner = make_quiner(C, c_quine_M, c_quine_tpl)  # я не стал выдумывать, и сделал квайнер на питоне по образу и подобию сишного py_quine_tpl = '''#!/usr/bin/python import sys m = [ <-F-> ] xyz = [ "<-X->", "<-X->", "<-X->" ] def ps(s) : 	sys.stdout.write(s) def pm(s) : 	for c in s : ps(m[ord(c)]) ps(xyz[0]) pm(xyz[0]) ps(xyz[1]) pm(xyz[1]) ps(xyz[1]) pm(xyz[2]) ps(xyz[2]) '''  py_quiner = make_quiner(C, c_quine_M, py_quine_tpl) # и даже функции позаимствовал  ###################  # принтеры на конкретных языках :  c_printer_tpl = '''#include <stdio.h> int main() { printf("%s", "<-T->"); return 0; } '''  c_printer = make_printer(C, c_printer_tpl)  py_printer_tpl = '''import sys sys.stdout.write("<-T->") '''  py_printer = make_printer(C, py_printer_tpl)  ####################  # поехали! создадим свои мультиквайны  c_c_printer   = meta_printer(c_printer,  c_printer) py_py_printer = meta_printer(py_printer, py_printer)  # квайны 1 порядка c_quine  = show_quiner_printer(c_quiner,  nul_printer) py_quine = show_quiner_printer(py_quiner, nul_printer)  # мультиквайны 2 порядка c_c_quine   = show_quiner_printer(c_quiner,  c_printer) py_py_quine = show_quiner_printer(py_quiner, py_printer)  # мультиквайны 2 порядка - полиглоты c_py_quine = show_quiner_printer(c_quiner, py_printer) py_c_quine = show_quiner_printer(py_quiner, c_printer)  # мультиквайны 3 порядка - одно- и многоязычные c_c_c_quine    = show_quiner_printer(c_quiner,  c_c_printer) py_py_py_quine = show_quiner_printer(py_quiner, py_py_printer) c_py_py_quine  = show_quiner_printer(c_quiner,  py_py_printer) py_c_c_quine   = show_quiner_printer(py_quiner, c_c_printer)  sys.stdout.write(py_py_py_quine) # выведем, для разнообразия, какой-нибудь мультиквайн... 

Исходник и его плоды можно найти на ведробите: bitbucket.org/nickolaym/quines

Конечно, сгенерированный машиной мультиквайн не отличается изяществом. Его размер — 5438 байт, большую часть занимает таблица кодировки.

Как сделать её компактнее (сохранив при этом универсальность подхода и возможность для машинного порождения) — эту задачу предлагаю решить самостоятельно.

Если вам понравится, то напишу ещё по этой теме:

• программы как функции над списками
• особенности тупых языков, таких как брейнфак

Также см. мой поток сознания на RSDN, 4-летней давности. http://rsdn.ru/forum/etude/3604693.