Квайн (quine) произвольного порядка на языке Brainfuck

Когда-то решал занятное упражнение для любителей сломать мозг: как написать квайн n-го порядка на чудесном языке Brainfuck. Результат этих упражнений я и публикую в своем унылом бложике. Кто хочет сам порешать, можете дальше пока не читать, а то будет не интересно.

Основные понятия

Brainfuck
Эзотерический язык программирования, отличающийся крайней простотой. Программы, написанные на этом языке, оперируют с некоей лентой посредством считывающе-записывающей головки. Всего в языке восемь операторов (для записи/чтения символа, смещения головки, инкремента/декремента значения в ячейке и двух оператора для организации циклов). Как видно, эта конструкция очень напоминает реализацию машины Тьюринга. За подробностями можно невозбранно обращаться в википедию или другие интернеты.
Квайн (quine)
Непустая программа, выдающая на выходе свой исходный текст. При этом запрещены всякие трюки вроде чтения текста программы из файла и тому подобное.
Квайн n-го порядка
Программа, которая выводит код другой программы, которая вывовит код третьей программы, ... , которая выводит код n-й программы, которая выводит код первой программы. Определение придумал я сам, поэтому ссылки на википедию нету.

Исходный код

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

Структура программы:

  1. Секция кода, где хранится информамция о порядке квайна. Этот код заносит в ячейки ленты 2 числа: I и N. N — это порядок квайна, I — это номер квайна в цикле квайнов порядка N. После выполнения кода этой секции лента имеет следующий вид:
    0 I N 0 0 -1 ...

    Здесь и далее, если клетка выделена, значит на ней стоит считывающая/записывающая головка.

    Код
    >>+++>>>-
  2. Секция, в которой содержится код, записывающий в память данные об коде секций c третьей по шестую. Данные хранятся в следующем формате: каждому из восьми символов (точнее семи, потому что операция ввода в данной программе не используется), ставятся в соответствие два числа X и Y, которые и сохраняются на ленте. Укажем, по какому правилу.

    Пусть C — ascii-код символа, который нужно закодировать. Тогда X := (C-43)%16; Y := (C-43)/16. Значит, C = X + Y*16 + 43. Цель такого кодирования — как можно наименьшей сделать длину кода этой секции. Выгода такого кодирования видна из таблицы: для записи информации о любом символе нужно выполнить не более шести операций.

    Символ ASCII X Y Код
    + 43 0 0 >>
    - 45 2 0 >++>
    . 46 3 0 >+++>
    > 60 1 1 >+>+
    < 62 3 1 >+++>+
    [ 91 0 3 >>+++
    ] 93 2 3 >+>+++

    Внимание: здесь и далее данные о коде программы будут записываться на ленту в виде пар чисел X Y в ОБРАТНОМ ПОРЯДКЕ. То есть пара чисел, поставленная в соответствие последнему символу кода выводимой программы, будет находится на ленте почти в самом ее начале.

    После выполнения кода этой секции лента будет иметь следующий вид:

    0 I N 0 0 -1 X1 Y1 ... Xm Ym ...

    Здесь m — число символов кода программы в секциях с третьей по шестую. Так как последний символ программы — это ], то, учитывая тот факт, что данные на ленту заносились в обратном порядке, X1 будет равным двум, а Y1 — трём.

    Код
    >++>+++ >+>+ >++> >+>+ >+++> >+>+ >++>+++ >+++>+ >> >> >> >> >> >> >> >> >> >>
    >> >> >> >> >> >> >+>+ >++> >>+++ >> >> >+++>+ >> >> >> >> >> >> >> >> >> >>
    >>+++ >+>+ >> >+++>+ >> >> >> >> >++>+++ >+++>+ >>+++ >+++>+ >+++>+ >+++>+
    >+++>+ >+++>+ >+++>+ >++>+++ >+>+ >+>+ >+>+ >+>+ >+>+ >++>+++ >+>+ >>+++ >+>+
    >> >+++>+ >> >++>+++ >+++>+ >>+++ >+++>+ >+++>+ >+++>+ >+++>+ >+++>+ >+++>+
    >++> >>+++ >+>+ >+>+ >+>+ >+>+ >+>+ >++>+++ >+>+ >>+++ >> >> >+++>+ >> >> >> >>
    >++>+++ >+++>+ >>+++ >+++>+ >+++>+ >+++>+ >+++>+ >++>+++ >+>+ >+>+ >+>+ >++>+++
    >+>+ >>+++ >+>+ >> >+++>+ >> >++>+++ >+++>+ >>+++ >+++>+ >+++>+ >+++>+ >+++>+
    >++> >>+++ >+>+ >+>+ >+>+ >++>+++ >+>+ >>+++ >> >> >+++>+ >> >> >> >> >+++>+ >>
    >> >+++>+ >> >> >> >> >+++>+ >> >> >+++>+ >> >> >> >> >+++>+ >> >+++>+ >> >> >>
    >++>+++ >+++>+ >>+++ >+++>+ >+++>+ >+++>+ >+++>+ >+++>+ >++>+++ >++> >>+++
    >+++>+ >+++>+ >+++>+ >++>+++ >+>+ >++>+++ >+>+ >> >+++>+ >++> >>+++ >>+++ >+>+
    >+>+ >++>+++ >+++>+ >+++>+ >> >+>+ >+>+ >++> >>+++ >+++>+ >++>+++ >+++>+ >>+++
    >+>+ >++>+++ >+++>+ >++> >+>+ >++> >+>+ >+>+ >> >+++>+ >> >+++>+ >>+++ >+++>+
    >> >+>+ >+>+ >+>+ >+>+ >++>+++ >> >+>+ >+>+ >++>+++ >+>+ >>+++ >> >> >> >+>+ >>
    >+>+ >++>+++ >+++>+ >>+++ >+++>+ >+++>+ >++>+++ >++> >+>+ >++>+++ >+>+ >>+++ >>
    >+++>+ >> >++>+++ >+++>+ >>+++ >> >+++>+ >+++>+ >>+++ >>+++ >>
  3. Код этой секции отвечает за запись на ленту данных о коде программы, содержащемся во второй секции. Информацию о коде, содержащемся во второй секции можно получить из данных, УЖЕ записанных на ленту кодом предыдущей секции.

    Действительно, пусть последние записанные числа на ленту — это Xm Ym. Значит, код, который имеет записал их на ленту, имеет вид: больше, Xm плюсов, больше, Ym плюсов. Следовательно, на ленту нам надо записать (Ym + 1 + Xm + 1) новых пар чисел, соответствующих плюсу и знаку больше.

    Далее переходим к паре Xm-1 Ym-1 и опять в конец последовательности дописываем новые пары чисел. Повторяем операцию до тех пор, пока не дойдем до X1 Y1. Теперь у нас на ленте содержится информация о коде секций со ВТОРОЙ по шестую.

    Среди побочных действий кода этой секции важны следующие:

    • Головка переходит почти к началу ленты.
    • Терминальное число −1 в начале ленты заменяется на 0.
    • Все данные, начиная с X1 Y1, сдвигаются на две клетки вправо.
    • К каждому Xi и Yi, как старому, так и новому, добавляется единица. То есть, минус, например, теперь кодируется не парой 2 0, а парой 3 1. Это делается в двух целях. Первое: чтобы уменьшить константу 43 в приведенной выше формуле. Значит, C теперь можно вычислить по формуле C = X + Y*16 + 4326. Второе: чтобы нули на ленте не помешали нам вернуться назад, в конец записанной нами последовательности, простым циклом [>]

    После выполнения кода этой секции лента будет иметь следующий вид:

    0 I N 0 0 0 0 0 X1 Y1 ... Xm Ym Xm+1 Ym+1 ... Xk Yk ...
    Код
    +[
    [
    >>+[>]+>+[<]<-
    ]
    >>[>]<+<+++[<]<
    <
    +]
  4. Код этой секции прибавляет по модулю N к I единицу. Именно из-за этого кода мы не записали в начале программы числа I и N в первых двух клетках ленты и оставили свободное место после этих чисел.
    Теперь лента будет иметь следующий вид:

    0 0 (I+1)%N 0 N 0 0 0 X1 Y1 ... Xk Yk ...
    Код
    <<<< +>[>+>+<<-<->]
    <[>]>[-<<+>>]
    <<[[->+<]<]
    >>>[-]
  5. Код этой секции записывает в память оставшуюся часть данных о первой секции кода выводимой программы. Первая секция — единственная, которая отличается у данной программы и той, код которой данная программа выводит.
    После Xk и Yk, необходимо записать пару чисел, соответствующую минусу, три пары чисел, соответствующих знаку больше, N пар чисел, соответсвующих плюсу, пару чисел, соответствующую знаку больше, (I+1)%N пар чисел, соответсвующих плюсу, и, наконец, пару чисел, соответствующую знаку больше.

    После выполнения кода этой секции лента будет такой:

    0 0 0 0 0 0 0 0 X1 Y1 ... Xk Yk Xk+1 Yk+1 ... Xk+1+3+N+1+(I+1)%N+1 Yk+1+3+N+1+(I+1)%N+1 ...

    Теперь на ленте содержится ВСЕ данные для вывода на экран кода следующей в цикле квайнов N-го порядка программы.

    Код
    >>>>>[>]+++ >+ >++++ >++ >++++ >++ >++++ >++
    [<]<<< [->>>>[>]+>+<[<]<<<]
    >>>>[>]++++ >++
    [<]<<<<< [->>>>>>[>]+>+<[<]<<<<<]
    >>>>>>[>]++++ >+ <
  6. Код этой секции для каждой пары Xi Yi, начиная с последней, находит Ci по формуле Ci = (Xi+10) + (Yi+1)*16 и выводит Ci на экран.
    После выполнения кода этой секции лента примет такой вид:

    0 0 0 0 0 0 0 -1 С1 0 ... Сk 0 Сk+1 0 ... Сk+1+3+N+1+(I+1)%N+1 0 ...

    а также будет выведен код следующей в цикле квайнов программы.

    Код
    [
    ++++++++++>++
    [-<++++++++++++++++>]
    <.<-<
    ]

Заключение

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

Программизм, , Январь 13, 2009

Leave a Reply

Name (required)


Mail (required)


Website