Brainfuck

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:17, 1 июня 2016.
Brainfuck
Парадигма эзотерический
Спроектировано Урбан Мюллер
Первый   появившийся 1993
OS кроссплатформенный
Расширение файла .b, .bf
Под влиянием
FALSE

Brainfuck (название примерно соответствует русскому изнасилование мозга) — один из известнейших эзотерических языков программирования, придуман Урбаном Мюллером для забавы. Язык имеет восемь команд, каждая из которых записывается одним символом.

История

Язык Brainfuck придумал Урбан Мюллер в 1993 году. Одним из мотивов Урбана Мюллера было создание языка с как можно меньшим компилятором. Отчасти он был вдохновлён языком FALSE, для которого существовал компилятор размера 1024 байта. Существуют компиляторы языка Brainfuck размера меньше 200 байт[1], Программы на языке Brainfuck писать сложно, за что его иногда называют языком для мазохистов. Но при этом важно отметить, что Brainfuck является вполне естественным, полным и простым языком и может использоваться при определении понятия вычислимости.

Машина, которой управляют команды Brainfuck, состоит из упорядоченного набора ячеек и указателя текущей ячейки, напоминая ленту и головку машины Тьюринга. Кроме того, подразумевается устройство общения с внешним миром (см. команды . и ,) через поток ввода и поток вывода.

Описание команд языка

Язык Brainfuck можно описать с помощью эквивалентов языка Си:

Команда Brainfuck Эквивалент на Си Описание команды
Начало программы int i = 0;
char arr[30000];
memset(arr, 0, sizeof(arr)); 		выделяется память под 30 000 ячеек
> i++; перейти к следующей ячейке
< i--; перейти к предыдущей ячейке
+ arr[i]++; увеличить значение в текущей ячейке на 1
- arr[i]--; уменьшить значение в текущей ячейке на 1
. putchar(arr[i]); напечатать значение из текущей ячейки
, arr[i]&nbsp;=&nbsp;getchar(); ввести извне значение и сохранить в текущей ячейке
[ while(arr[i]){ если значение текущей ячейки ноль, перейти вперёд по тексту программы на ячейку, следующую за соответствующей ] (с учётом вложенности)
] } если значение текущей ячейки не нуль, перейти назад по тексту программы на символ [ (с учётом вложенности)

Несмотря на внешнюю примитивность, Brainfuck с бесконечным набором ячеек имеет тьюринговскую полноту, а, следовательно, по потенциальным возможностям не уступает языкам общего назначения.

В «классическом» Brainfuck, описанном Мюллером, размер ячейки — один байт, количество ячеек 30 000. В начальном состоянии указатель находится в крайней левой позиции, а все ячейки заполнены нулями. Увеличение/уменьшение значений ячеек происходит по модулю 256. Ввод-вывод также происходит побайтно, с учётом кодировки ASCII (то есть в результате операции ввода (,) символ 1 будет записан в текущую ячейку как число 0x31 (49), а операция вывода (.), совершённая над ячейкой, содержащей 0x41 (65), напечатает латинскую А). В других вариантах языка размер и количество ячеек может быть другим (бо́льшим). Есть версии, где значение ячеек не целочисленно (с плавающей точкой).

Пример программы

Программа на языке Brainfuck, печатающая «Hello World!»:
 ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
 .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
 ------.--------.>+.>.

Разбор программы:

Подготовка в памяти (с ячейки 1) массива значений, близких к ASCII-кодам символов, которые необходимо вывести (70, 100, 30, 10), через повторение 10 раз приращения ячеек на 7, 10, 3 и 1, соответственно
++++++++++ присваивание ячейке 0 (счетчику) значения 10
[ повторять, пока значение текущей ячейки (ячейки 0) больше нуля
>+++++++ приращение ячейки 1 на 7
>++++++++++ приращение ячейки 2 на 10
>+++ приращение ячейки 3 на 3
>+ приращение ячейки 4 на 1
<<<<- возврат к ячейке 0 (счетчику), и его уменьшение на 1
] вернуться к началу цикла
Получение кодов букв и их вывод
>++. Вывод «Н». Получение кода «H» (72) из 70 в ячейке 1 и вывод
>+. Вывод «e». Получение кода «e» (101) из 100 в ячейке 2 и вывод
+++++++.. Вывод «ll». Получение кода «l» (108) из 101 в ячейке 2 и вывод дважды
+++. Вывод «o». Получение кода «o» (111) из 108 в ячейке 2 и вывод
>++. Вывод пробела. Получение кода пробела (32) из 30 в ячейке 3 и вывод
<<+++++++++++++++. Вывод «W». Получение кода «W» (87) из 72 в ячейке 1 и вывод
>. Вывод «o». Код «o» (111) уже находится в ячейке 2, просто его выводим
+++. Вывод «r». Получение кода «r» (114) из 111 в ячейке 2 и вывод
------. Вывод «l». Получение кода «l» (108) из 114 в ячейке 2 и вывод
--------. Вывод «d». Получение кода «d» (100) из 108 в ячейке 2 и вывод
>+. Вывод «!». Получение кода «!» (33) из 32 в ячейке 3 и вывод
>. Вывод кода перевода строки (10) из ячейки 4

В принципе, печать «Hello World!» можно реализовать проще, но программа будет в три с лишним раза больше, чем приведённый выше оптимизированный вариант: 

 +++++++++++++++++++++++++++++++++++++++++++++
 +++++++++++++++++++++++++++.+++++++++++++++++
 ++++++++++++.+++++++..+++.-------------------
 ---------------------------------------------
 ---------------.+++++++++++++++++++++++++++++
 ++++++++++++++++++++++++++.++++++++++++++++++
 ++++++.+++.------.--------.------------------
 ---------------------------------------------
 ----.-----------------------.

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

Пример интерпретатора Brainfuck’а, написанный на языке C++ 

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

static char cpu[30000];

int main(int argc, char **argv)
{

    vector<char> acc;
    char ch;
    ifstream infile(argv[1]);
    while(infile)
    {
        infile.get(ch);
        acc.push_back(ch);
    }
    infile.close();
    unsigned int j = 0;
    int brc = 0;
    for(int i = 0; i < acc.size(); ++i)
    {
        if(acc[i] == '>') j++;
        if(acc[i] == '<') j--;
        if(acc[i] == '+') cpu[j]++;
        if(acc[i] == '-') cpu[j]--;
        if(acc[i] == '.') cout << cpu[j];
        if(acc[i] == ',') cin >> cpu[j];
        if(acc[i] == '[')
        {
            if(!cpu[j])
            {
                ++brc;
                while(brc)
                {
                    ++i;
                    if (acc[i] == '[') ++brc;
                    if (acc[i] == ']') --brc;
                }
            }else continue;
        }
        else if(acc[i] == ']')
        {
            if(!cpu[j])
            {
                continue;
            }
            else
            {
                if(acc[i] == ']') brc++;
                while(brc)
                {
                    --i;
                    if(acc[i] == '[') brc--;
                    if(acc[i] == ']') brc++;
                }
                --i;
            }
        }
    }
}

Программирование на языке Brainfuck

Полнота по Тьюрингу означает, что в языке могут быть реализованы привычные для других языков действия:

  • операция копирования значения
  • использование промежуточной (аккумуляторной) памяти
  • использование условных операторов
  • арифметические операции умножения и деления

Вариант решения: . 

 Обозначим через @(k) сдвиг на k ячеек вправо, если k>0, и влево, если k<0
 Соответственно, @(k) = >…k раз…> либо <…-k раз…<  
 zero(): обнуление текущей ячейки:
   [-]
   =
   [+]
 add(k): прибавление значения ячейки n (текущей) к значению ячейки n+k:
    [ — @(k)  + @(-k)  ]
 при этом значение ячейки n теряется (обнуляется).
 mov(k): копирование значения ячейки n (текущей) в ячейку n+k с потерей (обнулением) значения ячейки n:
   @(k) zero() @(-k) add(k)
   =
   @(k) [-] @(-k) [ — @(k)  + @(-k)  ] 
 copy(k,t): копирование значения ячейки n (текущей) в ячейку n+k 
 c использованием промежуточной ячейки n+k+t, благодаря чему значение ячейки n не теряется (сохраняется).
   @(k) zero() @(t) zero() @(-k-t) [ — @(k) + @(t) + @(-k-t) ] @(k+t) mov(-k-t)
   =
   @(k) [-] @(t) [-] @(-k-t) [ — @(k) + @(t) + @(-k-t) ] @(k+t) [ — @(-k-t) + @(k+t) ]
 ifelse(t): если текущая ячейка>0, то выполняется условие true
            если текущая ячейка=0, то выполняется условие false
            t-относительный номер вспомогательной ячейки:
   @(t)[-]+@(-t) устанавливаем флаг 1 для случая else
   [
    здесь действия ветки true
    @(t)[-]@(-t) устанавливаем флаг 0 для случая else
    [-] выход из цикла
]
   @(t)
   [@(-t)
    здесь действия ветки false
    @(t)[-] выход из цикла
]
   @(-t-1)

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

Языки на основе Brainfuck

Ook! COW Brainfuck Описание
Ook. Ook. MoO + Значение текущей ячейки увеличивает на 1
Ook! Ook! MOo - Значение текущей ячейки уменьшают на 1
Ook. Ook? moO > Следующая ячейка
Ook? Ook. mOo < Предыдущая ячейка
Ook! Ook? moo [ Начало цикла
Ook? Ook! MOO ] Конец цикла
Ook! Ook. OOM . Вывод значения текущей ячейки
Ook. Ook! oom , Запрос значения текущей ячейки
mOO отсутствует Выполняет инструкцию с номером, который берётся из текущей ячейки (если значение в текущей ячейке равно 3, то это приводит к бесконечному циклу).
Moo отсутствует Если значение текущей ячейки равно нулю, то ввести его с клавиатуры; если же значение текущей ячейки — не ноль, то вывести его на экран.
OOO [-] Обнуляет значение в текущей ячейке
MMM отсутствует если регистр пуст, скопировать в него значение текущей ячейки, иначе скопировать в ячейку содержимое регистра и очистить регистр

Примечания

  1. ↑ компилятор весом 166 байт

Ссылки

Источник — «https://ru.bmstu.wiki/index.php?title=Brainfuck&oldid=42683»