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

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

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

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

Функции

Какие функции у нас есть?
Во-первых, это интерпретатор: он берёт текст программы, компилирует, запускает, — и возвращает текст со стандартного вывода.
Назовём эту функцию просто: 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 s1nprint "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", "hellonhabr"); 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.

Автор: nickolaym

Источник