Интерпретатор Brainfuck на Brainfuck

После нахождения на Хабре ряда постов имеющих отношение к Brainfuck'у в том числе его интерпретации у меня возникло какое-то желание написать и свой интерпретатор Brainfuck'а. Но для удовлетворение тех необходимых ощущений, которые нам приносит сам язык, нужно это было написать именно на Brainfuck. И у меня это частично получилось. Сразу оговорюсь о том чего нету: этот интерпретатор на данный момент не поддерживает циклы и ввод входных данных (в случае входных данных — нет откуда их считывать, так как на вход подается Brainfuck программа) — если кратко — то не работают комманды "[", "]" и ",".

Ограничения


Из ограничений (помимо того, чего интерпретатор не поддерживает) есть только два следующих:
  • Минимальный индекс ячейки должен быть не меньше чем (-1) (иначе есть риск неправильной работы интерпретатора). Другими словами — писать "<<" в начале программы не стоит.
  • Максимальное количество используемых ячеек — 255.


Скорость


Я думаю вы уже предположили, но я всё-таки уточню, что на Brainfuck не стоит писать интерпретаторы скорость работы оставляет желать лучшего.

Обфускатный исходный код интерпретатора


Если у вас всеравно осталось желание испытать то, что у меня получилось, то вот и сам исходный код:
,[>,]>>>>++<<<<<[<]>[[[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-]>++++++++++[<++++>-]<+++<[>-<-]+>[<->[-]]<[->>>[<+<<+>>>-]<[>+<-]<<[>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-]>>>>>>>>>>>[>>>>]<+<[-]<<<<[<<<<]<<[<+<<+>>>-]<[>+<-]<<[>>>>>>>>>>>[>>>>]<<+<<<<[<<<<]<<<<<-]>>>>>>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>]<<<<[<<<<]<<<<<]<<[<]>[[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-]>+++++++++[<+++++>-]<<[>-<-]+>[<->[-]]<[->>>[<+<<+>>>-]<[>+<-]<<[>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-]>>>>>>>>>>>[>>>>]<-<[-]<<<<[<<<<]<<[<+<<+>>>-]<[>+<-]<<[>>>>>>>>>>>[>>>>]<<+<<<<[<<<<]<<<<<-]>>>>>>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>]<<<<[<<<<]<<<<<]<<[<]>[[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-]>+++++++++[<+++++>-]<+<[>-<-]+>[<->[-]]<[->>>[<+<<+>>>-]<[>+<-]<<[>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-]>>>>>>>>>>>[>>>>]<.<<<<<[<<<<]>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>]<<<<[<<<<]<<<<<]<<[<]>[[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-]>++++++++++[<++++++>-]<<[>-<-]+>[<->[-]]<[->>>-<<<]<<[<]>[[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-]>++++++++++[<++++++>-]<++<[>-<-]+>[<->[-]]<[->>>+<<<]<<[<]>[-]>]

Я еще раз оговорюсь о том, что циклов или loop'ов этот интерпретатор не поддерживает, чтобы вам не пришлось испытывать этот интерпретатор на правильную работу данных возможностей.

Код Brainfuck вы можете исполнить на сайте brainfuck.tk, а в качестве примера входных данных использовать следующий код:
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+.+.>++++++++++.<.-.-.
который должен вывести следущих две строки:
ABC
CBA


Исходный код


Перед исходным кодом уточню некоторый моменты:
  • N — так я позначаю длину входной строки. В нашем случае это должна быть программа на Brainfuck.
  • Осчет ячеек начинается с 0.
  • Код входной программы размещается в ячейках начиная с нулевой.
  • Ячейка (N + 4) — указатель на текущую ячейку. Значение по умолчанию — 2 (для входной программы это ячейка с индексом 0). Значение — 1 — для входной программы доступно как ячейка с индексом (-1).
  • Данные входной программы начинаются с ячейки (N + 10).
  • Структура данных имеет вид: 1-ая ячейка — номер ячейки, 2-ая ячейка — значение, 3-ая и 4-ая ячейки — ячейки для хранения промежуточных результатов.

ASCII коды используемых символов:
  • + — 43
  • - — 45
  • . — 46
  • < — 60
  • > — 62

Исходный код:
,[>,] считывание brainfuck программы
>>>>++<<<< установка значения по умолчанию для ячейки (N плюс 4)
<[<]> переход в начало программы: из позиции N в позицию 0

[
    плюс
    [[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-] копирование текущей команды на позицию (N плюс 1)
    >++++++++++[<++++>-]<+++ запись значения 43 в (N плюс 2) ячейку
    <[>-<-] вычитание кода символа команды из числа 43
    +>[<->[-]]<[- если команда это символ "плюс"; текущая ячейка: (N плюс 1)
        >>>[<+<<+>>>-]<[>+<-]<< копирование ячейки (N плюс 4) в текущую ячейку (N плюс 1)
        [>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-] вычитание индекса текущей ячейки из индексов каждой ячейки
        >>>>>>>>>>>[>>>>]<+<[-] изменение значения ячейки
        <<<<[<<<<]<<[<+<<+>>>-]<[>+<-]<< копирование ячейки (N плюс 4) в ячейку (N плюс 1)
        [>>>>>>>>>>>[>>>>]<<+<<<<[<<<<]<<<<<-] обновление индекса ячейки
        >>>>>>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>] восстановление индексов ячеек
        <<<<[<<<<]<<<<< возвращаемся на ячейку (N плюс 1)
    ]
    
    <<[<]> переход в начало программы: из позиции (N плюс 1) в позицию 0
    
    минус
    [[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-] копирование текущей команды на позицию (N плюс 1)
    >+++++++++[<+++++>-]< запись значения 45 в (N плюс 2) ячейку
    <[>-<-] вычитание кода символа команды из числа 45
    +>[<->[-]]<[- если команда это символ "минус"; текущая ячейка: (N плюс 1)
        >>>[<+<<+>>>-]<[>+<-]<< копирование ячейки (N плюс 4) в текущую ячейку (N плюс 1)
        [>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-] вычитание индекса текущей ячейки из индексов каждой ячейки
        >>>>>>>>>>>[>>>>]<-<[-] изменение значения ячейки
        <<<<[<<<<]<<[<+<<+>>>-]<[>+<-]<< копирование ячейки (N плюс 4) в ячейку (N плюс 1)
        [>>>>>>>>>>>[>>>>]<<+<<<<[<<<<]<<<<<-] обновление индекса ячейки
        >>>>>>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>] восстановление индексов ячеек
        <<<<[<<<<]<<<<< возвращаемся на ячейку (N плюс 1)
    ]
    
    <<[<]> переход в начало программы: из позиции (N плюс 1) в позицию 0
    
    точка
    [[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-] копирование текущей команды на позицию (N плюс 1)
    >+++++++++[<+++++>-]<+ запись значения 46 в (N плюс 2) ячейку
    <[>-<-] вычитание кода символа команды из числа 46
    +>[<->[-]]<[- если команда это символ "точка"; текущая ячейка: (N плюс 1)
        >>>[<+<<+>>>-]<[>+<-]<< копирование ячейки (N плюс 4) в текущую ячейку (N плюс 1)
        [>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-] вычитание индекса текущей ячейки из индексов каждой ячейки
        >>>>>>>>>>>[>>>>]<.< вывод значения ячейки
		<<<<[<<<<]>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>] восстановление индексов ячеек
        <<<<[<<<<]<<<<< возвращаемся на ячейку (N плюс 1)
    ]
    
    <<[<]> переход в начало программы: из позиции (N плюс 1) в позицию 0
    
    меньше
    [[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-] копирование текущей команды на позицию (N плюс 1)
    >++++++++++[<++++++>-]< запись значения 60 в (N плюс 2) ячейку
    <[>-<-] вычитание кода символа команды из числа 60
    +>[<->[-]]<[- если команда это символ "меньше"; текущая ячейка: (N плюс 1)
        >>>-<<< изменение указазателя на минус 1
    ]
    
    <<[<]> переход в начало программы: из позиции (N плюс 1) в позицию 0
    
    больше
    [[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-] копирование текущей команды на позицию (N плюс 1)
    >++++++++++[<++++++>-]<++ запись значения 62 в (N плюс 2) ячейку
    <[>-<-] вычитание кода символа команды из числа 62
    +>[<->[-]]<[- если команда это символ "больше"; текущая ячейка: (N плюс 1)
        >>>+<<< изменение указазателя на плюс 1
    ]
    
    <<[<]>[-]> переход в начало программы но уже на следующую команду (предыдущая позиция обнуляется)
]

Вместо заключения


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

P.S.
Спасибо хабрачеловеку iSage за предоставленные ссылки на интерпретаторы Brainfuck на Brainfuck.
Поделиться публикацией

Похожие публикации

Комментарии 51
    +5
    Насчет циклов: pastebin.com/f6cca4886
    Ну и в целом, имело наверное смысл изучить прежде шесть имеющихся интерпретаторов.
      0
      Спасибо за информацию. Сейчас пересмотрю существующие реализации, и, думаю найду для себя полезные мысли для реализации циклов. Я, по-видимому, плохо искал информацию, так как не нашел существующих интерпретаторов Brainfuck на Brainfuck.
        +1
        esolangs.org/wiki/DBFI
        «possibly the shortest self-interpreter amongst all imperative languagеs»...
        Мозг взорван, чего, собственно, следовало ожидать…
          0
          Мда… Сказать что мне пока что к этому далеко, это ничего не сказать… У меня без поддержки циклов размер — 1061 байт, а у них полнофункциональный — 423 байта (ну это если убрать
          ASCII decoding, comment handling, and avoiding undefined behaviour
          , чего у меня нету)
        +12
        Please stop fuck my brains on brainfuck!!! STOP!!! I can`t get more!!!
          0
          It only flowers. Your death is close: (
          +8
          Что вы там в песочнице курите?
          0
          Во делать нефиг людям.
            +2
            Да нет. Просто время от времени возникает желание удовлетворить те потребности, на которые намекает название языка.
            +3
            Это замечательный пост, он обязательно должен был появится, я его очень ждал!
              0
              Спасибо за отзыв!
              +4
              Я ждал этого. Цепочка замкнулась. Всем спасибо, все свободны.
                +2
                Yo dawg so i heard you like Brainfuck so we put Brainfuck in your Brainfuck so you can interpret Brainfuck while you interpret Brainfuck

                Простите.
                +3
                Следующая статья будет «Интерпретатор Brainfuck на Brainfuck на Brainfuck».
                  +1
                  меня бы устроил и «Рейтрейсер на Brainfuck» на самом деле…
                    0
                    Думаю, такими темпами, следующий релиз PHP будет на брейнфаке вместо Си. о_0
                        +6
                        путь к сердцу хабра лежит через брейнфак
                          +2
                          Как пишут в таких случаях зарубежные журналисты, so meta it hurts.
                            0
                            свой бордель, с блэкджэком и шлюхами
                            • НЛО прилетело и опубликовало эту надпись здесь
                                0
                                Это потому что этот интерпретатор (swapped.cc/bf/) не умеет ходить в минусовые ячейки. Например, данный код на нем не исполняется <+++.
                                • НЛО прилетело и опубликовало эту надпись здесь
                                    0
                                    Я, честно говоря, спецификации не читал, и никаких других моментов связанных именно с тем, что можно или не можно ходить в минус, не находил. Я просто руководствовался той логикой, что если можно ходить по ячейках, то какая разница в какую сторону.
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                        0
                                        Вы сможете выложить Вашу версию интерпретатора куда-то в общий доступ?
                                        Я тестировал свой код на brainfuck.tk, Brainfuck Developer, Linux'овом bf — на этих интерпретаторах он работает.
                                        И кстати, если на ячейке из значением ноль выполнить команду декремента, то каким будет новое значение ячейки?
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                            0
                                            Уже работает! Убрал одно лишнее условие… изменения (pastebin.com/e8juzAFW)
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                0
                                                Условие теперь также исполняется, только теперь в другом месте. Проблема была в том, что код:
                                                m_stack.pop();
                                                должен в любом случае исполнятся, независимо от условия:
                                                m_field[pos_in_field] != 0

                                                const уже был в объявлении. Убрал, потому что были ошибки компиляции "invalid conversion from ‘const char*’ to ‘char*’". Компилятор — gcc version 4.4.4 (Gentoo Hardened 4.4.4-r2 p1.2, pie-0.4.5).
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                    0
                                    А нет. Я ошибся. Интерпретатор от swapped.cc не работает по каким-то другим причинам, неизвестным мне на данный момент.
                                    +3
                                    наконец-таки написали на хабре статью об интепретации brainfuck на brainfuck, может теперь не будет статей типа «Интерпретация brainfuck на XXX» :)
                                      +4
                                      Не знаю как другим в мне статьи про brainfuck немного поднадоели.
                                        +4
                                        я б даже сказал подзаебали
                                          +1
                                          Что вам мешает не читать их?
                                          +1
                                          И что, Вы думаете написали интерпретатор? Если у Вас нет циклов, то в этом нет смысла — ведь именно они придают полноту и красоту языку, они — основная сложность. Более того — у Вас нет ввода. То есть то, что Вы сделали, очевидно и бессмысленно, в этом нет особой сложности. Не вижу смысла выкладывать такие недоделанные работы.
                                            0
                                            А как Вы думаете — какая должна быть практическая польза из интерпретатора Brainfuck'а на Brainfuck? Он может быстрее работать, или использовать меньше памяти (хотя этот вариант возможно еще и допустимый), чем его аналоги написанные на других языках программирования? Я этот код писал ради спортивного интереса, и не больше. Почему я это выложил? Мне показалось интересным поделиться с данным сообществом этой информацией. Возможно некоторым эта информация показалась интересной, другим нет. И поэтому, если есть информация, которая никому не навредит и окажеться полезной для других, то почему бы этой информацией не поделиться?
                                              0
                                              Ну, Вы меня простите, это я так, «разгорячился».

                                              В общем, интересно было бы посмотреть на Вашу реализацию циклов и ввода.
                                              А ещё можно реализовать некоторый расширенный (к примеру, процедурный) bf на bf.
                                                0
                                                Спасибо за понимание.
                                                Интересная мысль с реализацией процедурного bf, и как я предполагаю на данный момент, идея реализации будет чем-то близка к реализации циклов. Я доработаю данный код до полной реализации BF (или, возможно, Pbrain), и, если конечно Вы не против, сообщу Вам об этом.
                                                  0
                                                  А ещё можно реализовать такую вещь, как восклицательные знаки (типа константы, подающиеся на чтение).

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

                                                  Удачи Вам!
                                                    0
                                                    Спасибо!
                                            0
                                            Господа. Не подскажете, как правильно кириллицу вывести, если кодировка на странице UTF-8?
                                              +1
                                              Выводить строку, закодированную в UTF8, побайтно.
                                              Вот пример:
                                              # Letter «У» byte 1
                                              >++++++++++[>++++++++++[<<++>>-]<-]<++++++++.
                                              # Letter «У» byte 2
                                              >+++++++++[<----->-]<.
                                              # Letter «р» byte 1
                                              >+++++++++[<+++++>-]<+.
                                              # Letter «р» byte 2
                                              >+++++++++[<--------->-]<.
                                              # Letter «а» byte 1
                                              >++++++++++[<++++++++>-]<.
                                              # Letter «а» byte 2
                                              >++++++[<----->-]<--.
                                              # Symbol "!"
                                              >++++++++++++[<------------>-]<+.
                                              # End.


                                              Проверял работоспособность на brainfuck.tk/
                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                0
                                                Интересно, что будет дальше, неделя LOLCODE? =)
                                                  0
                                                  Теперь бы еще интерпретатор Brainfuck на Brainfart написать…
                                                    0
                                                    Не очень Вас понял. Что значит Brainfart в данном контексте?

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

                                                  Самое читаемое