Интерпретатор 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
          Что вы там в песочнице курите?
            +39
            Песок
            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
                        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 в данном контексте?

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

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