Пользователь
0,1
рейтинг
4 августа 2013 в 21:11

Разработка → Мультиквайногенератор из песочницы

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

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

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

Функции


Какие функции у нас есть?
Во-первых, это интерпретатор: он берёт текст программы, компилирует, запускает, — и возвращает текст со стандартного вывода.
Назовём эту функцию просто: 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} на неизвестно каких языках (всё, что нам нужно — это только табличные реализации функций Sk);
  • шаблон понга {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
карма
35,0
рейтинг 0,1
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (13)

  • 0
    А Вы случайно не причастны к курсу «Языки программирования и компиляторы» с Лекториума? Стиль изложения очень похож на тот. Статья интересная)
    • 0
      К сожалению, не только не причастен, но даже и не подозревал о нём. Спасибо за наводку.
  • 0
    Простите за офтопик, но прочитал как «мультикавайногенератор», и очень удивился :).
    • +3
      Дваждую. Минусуйте сколько угодно, но оно действительно так читается =)
    • НЛО прилетело и опубликовало эту надпись здесь
    • +2
      Кто о чем больше осведомлен, тот так и прочитал :)
      Я сразу прочитал правильно, а вот ваше слово не с первой попытки.
  • +2
    >> ассоциативность по операции сложения (конкатенации) строк: E (x+y) = Ex + Ey.
    По-моему, это свойство называется линейность. Один из критериев линейности функции, оператора…
    Ассоциативность — это скобки расставлять.
    • +5
      Это свойство называется аддитивность. Для линейности еще надо умножение на константу.
      • +1
        Если считать умножением строки на число её повторение соответствующее количество раз (в контексте питона это особенно логично), то вот и линейность получаем :)
      • 0
        Большое спасибо, поправил.
  • +1
    Хабр торт.

    По существу, хотя, может, это бред: а можно ли как-нибудь упростить себе задачу, если рассмотреть все языки, которые мы хотим использовать в цепочке квайнов, как алгорифмы Маркова или машины Тьюринга?
    • 0
      Ну, у меня были похожие думки, но они слишком далеки от реализации.
      Конечно, удобнее всего использовать языки с мощной обработкой строк, идейно близкие к алгорифмам Маркова и машине Поста — рефал, perl, а может быть, даже awk и sed.

      Но как максимально обобщить задачу о мультиквайне, я пока не придумал.
      Решение вида принтер-принтер-принтер-...-квайн — вот оно, пожалуйста. Причём таких решений может быть много разных.
      В статье указаны два: с двумя строками и двойным декорированием и с тремя строками и одинарным декорированием.

      Интересно, что добавление каждой ступени к мультипринтеру линейно (а в плохом случае — экспоненциально) увеличивает размер программы.
      text = «hello \» world"
      P text = «main(){printf(»%s", «hello \\\» world");}
      PP text = «main(){printf(»%s",«main(){printf(\»%s\", «hello \\\\\\\» world\");}");}
      видите, что там творится с бэкслешами? Они, заразы, удваиваются! (Квайн 30 порядка просто не поместился в память).
      Именно поэтому приходится писать окт-код "\134" вместо "\\".

      Квайнер же подходит радикально: будучи длиной len(a+b+c) + len(Ex+Ey+Ez), он порождает текст длиной len(Fx+Fy+Fz)+len(x+y+z). То есть, длина квайнера сравнима или меньше длины его результата.

      Поэтому следует поискать, как встроить несколько квайнеров в цепочку: принтер1-квайнер2-принтер3-квайнер4…
      Ладно, это, пожалуй, тема для статьи.
      • 0
        Ждем статью :) Безумству храбрых поем мы песню…

        А по поводу алгорифмов Маркова и т.д., я так понимаю, сложность в том, что у каждого языка свои грамматика и синтаксис, поэтому заставить их читать один текст нельзя. Но можно для каждого написать какой-то минимальный интерпретатор алгорифмов Маркова например, с простой спецификацией. Правда, это уже не задача о квайнах :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.