Пользователь
0,0
рейтинг
30 июля 2013 в 18:30

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

Прочитал статью «Эстафета из 50-ти квайнов». Действительно, человек написал потрясающую штуку, колоссальный труд, настоящее произведение искусства. Но по комментам судя, многие не понимают, как подобные вещи делаются и полагают их чем-то на грани, если не за гранью, человеческих возможностей, особенно много эмоций было по поводу эзотерических языков (Brainfuck, Unlambda, Whitespace) в списке.
В этой статье я попытаюсь объяснить, как подобные квайны пишутся.

Вот код на питоне, который генерирует код на брейнфаке, который генерирует код на анлямбде, который генерирует первоначальный код на питоне:

data = 'def brainfuck(st): return "".join(["+"*ord(c)+".>" for c in st])\ndef unlambda(st): return "`r"+"`"*len(st)+"".join(["."+e for e in st])+"i"\nprint brainfuck(unlambda(\'data = %s\'%`data`+chr(10)+data))'
def brainfuck(st): return "".join(["+"*ord(c)+".>" for c in st])
def unlambda(st): return "`r"+"`"*len(st)+"".join(["."+e for e in st])+"i"
print brainfuck(unlambda('data = %s'%`data`+chr(10)+data))


Я попытался сделать код максимально понятным, тем не менее, на всякий случай, пройдусь по нему построчно.
В первой строчке закодированы все следующие строки в питоновском представлении. эта строчка пишется последней, после того как весь програмный код написан, он кодируется.

>>> data = 'def brainfuck(st): return "".join(["+"*ord(c)+".>" for c in st])\ndef unlambda(st): return "`r"+"`"*len(st)+"".join(["."+e for e in st])+"i"\nprint brainfuck(unlambda(\'data = %s\'%`data`+chr(10)+data))'
>>> print data
def brainfuck(st): return "".join(["+"*ord(c)+".>" for c in st])
def unlambda(st): return "`r"+"`"*len(st)+"".join(["."+e for e in st])+"i"
print brainfuck(unlambda('data = %s'%`data`+chr(10)+data))


Соответственно, текст программы целиком можно представить следующей строкой:

'data = %s'%`data`+chr(10)+data


Функция unlambda получает текст и возвращает программу на unlambda его печатающую.
Функция brainfuck — то же самое для brainfuck.

Ну и соответственно

brainfuck(unlambda('data = %s'%`data`+chr(10)+data))


это строка, представляющая из себя программу на Brainfuck, выводящую программу на Unlambda, выводящую исходную программу на
Питоне.
В цепочку легко добавлять новые языки, для каждого языка пишется функция, которая получает строчку и возвращает программу на этом языке, которая эту строчку печатает, затем эта функция добавляется к строчке вывода, ну и соответственно data вычисляется заново.

Апдейт.

Посмотрел на дискуссию в комментах и понял, что нужно объяснить получше.
Квайноподобную конструкцию (здесь и далее речь только о языках, где можно разделить данные и код) можно поделить на две части:
1) сегмент данных (важный момент, эта часть остаётся незаполненной до того момента, когда код будет завершён, после этого он кодируется).
2) сегмент кода
Сегмент данных — это некий шифр, который можно расшифровать двумя способами, в результате расшифровки первым способом получится строковое представление собственно сегмента данных, при расшифровке вторым способом получится строковое представление сегмента кода. Объединив результаты этих расшифровок, мы получим строку, в которой содержится весь исходный код программы.
В вышеприведённом примере, такая строка это - 'data = %s'%`data`+chr(10)+data.
'data = %s'%`data` — расшифровка дающая сегмент данных, data — расшифровка дающая сегмент кода, ну и chr(10) — переход строки между ними.
А дальше, после того, как у нас в руках есть эта волшебная строчка, мы можем сделать с ней всё что захотим. Если мы её просто распечатаем, получим обычный квайн:

data = "l = 'data = %s'%`data`+chr(10)+data\nprint l"
l = 'data = %s'%`data`+chr(10)+data
print l


Если перевернём, получим программу, которая печатает свой текст задом-наперёд:

data = "l = 'data = %s'%`data`+chr(10)+data\nprint l[-1::-1]"
l = 'data = %s'%`data`+chr(10)+data
print l[-1::-1]


Можем написать программу, которая печатает своё шестнадцатеричное представление:

data = "l = 'data = %s'%`data`+chr(10)+data\nprint ' '.join([hex(ord(e)) for e in l])"
l = 'data = %s'%`data`+chr(10)+data
print ' '.join([hex(ord(e)) for e in l])


В общем можем написать программу, которая печатает свой код после любой трансформации (ну или цепочки трансформаций, как в нашем случае). «Шифр» не обязан быть именно внутренним питоновским представлением строк, можно зашифровать например в виде ascii-кодов или ещё как-нибудь и соответствующем образом изменить процедуру расшифровки:

data = [108, 32, 61, 32, 39, 100, 97, 116, 97, 32, 61, 32, 37, 115, 39, 37, 100, 97, 116, 97, 43, 99, 104, 114, 40, 49, 48, 41, 43, 39, 39, 46, 106, 111, 105, 110, 40, 91, 99, 104, 114, 40, 101, 41, 32, 102, 111, 114, 32, 101, 32, 105, 110, 32, 100, 97, 116, 97, 93, 41, 10, 112, 114, 105, 110, 116, 32, 108]
l = 'data = %s'%data+chr(10)+''.join([chr(e) for e in data])
print l

@gromozeka1980
карма
88,5
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

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

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

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

  • +22
    Перечитал два раза, так и не понял «как подобные квайны пишутся». Я один такой? =)
    • +3
      Нет, я тоже не понял, какой метод здесь предлагается. Программа для каждого языка должна напечатать программу на следующем языке, учитывая все особенности представления строк на этом языке. Если взять строку, содержащую такие программы на всех используемых языках, то что-нибудь может получиться (каждая программа вырезает из строки фрагмент, который будет программой на следующем языке плюс вставляет в него генератор всей строки — опять же в терминах следующего языка). Но как здесь это делается за 3 функции? И без единого фрагмента на BF?
      • +1
        Ну почему без единого? Вот это
        "+"*ord(c)+".>"
        генерирует brainfuck на сколько я понимаю. Но все равно не дает понимания как такое можно написать, с чего вообще начинать то надо?
        • +3
          Кажется, понял. На языке 1 пишется программа P1, содержащая свой текст в двух экземплярах (один раз — внутри текстовой строки). На языке N — программа PN, способная написать программу на языке 1, но содержащая эту строку S только один раз. На языке 1 пишем функцию FN, которая по строке S создаёт программу PN. Дальше — проще: для каждого языка K из цепочки генерируется программа PK, которая печатает уже вычисленную строку P(K+1) (всё это происходит на языке 1). В конце программа P1 распечатывает вычисленную строку P2 — и квайн готов. Но для него нужно, чтобы в цепочке были два достаточно мощных языка подряд. Хотя напечатать два экземпляра строки может и Brainfuck…
          • +5
            Боюсь что без графического объяснения попытка донести суть метода так же обречена на провал. Я уже на 3-й строке начал тупить.
            • +1
              обновил пост
            • 0
              Проще говоря, в какой-то момент сложность добавления нового языка в цепочку, сводится к задаче «Hello, World».
              • 0
                Да, именно так. Но не обязательно весь «настоящий» код писать только на одном языке. У меня в коде все преобразования вида «получи текст, сгенерируй код на языке X, выводящий этот текст». Но в принципе ничего не мешает писать также преобразования вида «получи текст, сгенерируй код на языке X, генерирующий код на языке Y, выводящий этот текст». У товарища из Японии такие преобразования в коде есть.
              • 0
                Если посмотреть шаги тех 50 квайнов, то большинство из них просто выводит строку на другом языке, а какая-то хитрая магическая магия происходит в меньшем количестве шагов.

                Что-то вроде (здесь PHP->Python->Ruby)

                echo 'print "puts \'код очередного магического и мистического шага\'"';
                

                Главное правильно экранировать строки, и видимо лучше автогенератором.
      • 0
        обновил пост
    • 0
      обновил пост
  • +1
    После смакования статьи понял, что здесь, собственно, предлагается.
    'data = %s'%`data`+chr(10)+data
    В результате получается код на питоне, который при выполнении печатает себя же.
    unlambda('data = %s'%`data`+chr(10)+data)
    В результате получается код на unlambda, который при выполнении печатает код на питоне.
    brainfuck(unlambda('data = %s'%`data`+chr(10)+data))
    В результате получается код на BF, который при выполнении печатает код на unlambda, который в свою очередь при выполнении печатает оригинальный текст программы.

    Это означает, что после запуска кода на brainfuck на выходе будет не оригинальный код, а «предыдущий», в данном случае на unlambda.
    В результате имеем не уробороса, а некого змея, сложенного вдвое.

    Еще при просмотре quine-relay создается впечатление, что квайн основан на чем-то посложнее, чем
    data = "..." ...
    • +2
      хм… а почему не уробороса? питон->брейнфак->анлямбда->питон. diffом конечную и начальную программы сравнивал, всё честно :)
      а quine-relay конечно сложнее, там кроме этого базового принципа ещё до фига всяких фишек. так я и не ставил целью создать потрясающее произведение искусства, просто хотел показать, как такие уроборосы пишутся.
      • 0
        Верно, я был неправ. Вначале почему-то подумал, что квайн должен работать в обратном порядке.
    • 0
      Ну да, в цепочке есть одна программа, содержащая два одинаковых куска, и одна (перед ней), умеющая писать строку два раза. Все остальные программы просто печатают строку.

      Я это вижу так:
      P1:
        s="хвост"
        хвост
      
      PN: 
        s="хвост"
        print_N "s="
        print_N string(s)
        print_N s
      
      P_{N-1}: print_{N-1} PN
      ...
      P2: print_2 P3
      
      хвост:
        print_1(G2(G3(...(GN(s))...)))
        G2(s){ return print_2 s}
        G3(s){ return print_3 s}
         ...
        GN(s){ return PN(s) }
      


      Здесь P1 — программа на основном языке, PN — программа на предыдущем. string(s), который встречается в PN — строка в том виде, в котором её хочет видеть P1 в качестве строковой переменной (с правильно размеченными спецсимволами).

      Боюсь, что понятнее не стало. Но если будет больше интерпретаций, то, глядишь, и полная картина получится :)
  • 0
    Понять бы ещё как он, автор 50ти, ASCII-art туда засунул.
  • +1
    Спасибо ^_^. Написал свой квайн. (Object Pascal -> PHP -> Object Pascal).

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