Brainfuck

Brainfuck — один из эзотерических языков программирования, придуман Урбаном Мюллером (нем. Urban Müller) в 1993 году, известен своим минимализмом. Название языка можно перевести на русский как вынос мозга, оно напрямую образовано от английского выражения brainfuck (brain — мозг, fuck — сношать), т. е. заниматься ерундой. Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.

Brainfuck
Класс языка эзотерический
Появился в 1993
Автор Урбан Мюллер
Разработчик Урбан Мюллер[d]
Расширение файлов .b или .bf
Диалекты BrainSub, Brainfork, Brainloller, COW, Ook, Pbrain, Smallfuck, Spoon, LOLCODE, Whitespace, DoubleFuck, Feckfeck
Испытал влияние FALSE

Одним из мотивов Урбана Мюллера было создание языка с как можно меньшим компилятором. Отчасти он был вдохновлён языком 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] = getchar();ввести извне значение и сохранить в текущей ячейке
[while(arr[i]){если значение текущей ячейки ноль, перейти вперёд по тексту программы на ячейку, следующую за соответствующей ] (с учётом вложенности)
]}если значение текущей ячейки не нуль, перейти назад по тексту программы на символ [ (с учётом вложенности)

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

Brainfuck подходит для экспериментов по генетическому программированию из-за простоты синтаксиса, и, соответственно, генерации исходного кода.

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

Пример программы
Пошаговая программа на языке Brainfuck, печатающая «Hello World!» с переносом строки (в виде ASCII-кода - 72 101 108 108 111 32 87 111 114 108 100 33 10):
 +++++++++++++++++++++++++++++++++++++++++++++
 +++++++++++++++++++++++++++.+++++++++++++++++
 ++++++++++++.+++++++..+++.-------------------
 ---------------------------------------------
 ---------------.+++++++++++++++++++++++++++++
 ++++++++++++++++++++++++++.++++++++++++++++++
 ++++++.+++.------.--------.------------------
 ---------------------------------------------
 ----.-----------------------.

Итого 389 операторов и использована 1 ячейка памяти. Оптимизированная программа заметно короче - всего 111 операторов, но 5 ячеек памяти. Первая ячейка используется как обратный счётчик цикла на 10 итераций, в последующих ячейках находятся числа 7, 10, 3 и 1, наращиваемые этим циклом до 70, 100, 30 и 10, досуммирование происходит перед печатанием, второе слово конструируется из остатков первого:

 ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
 .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
 ------.--------.>+.>.

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

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

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

Perl

Пример интерпретатора Brainfuck, написанный на языке Perl:

#!/usr/bin/perl
open F, shift;
@code = grep {/[+-\.,\[\]><]/} split '', <F>;
for (my $_ = 0; $_ < @code; ++$_) {
  ++$cpu[$i] if $code[$_] eq '+';
  --$cpu[$i] if $code[$_] eq '-';
  --$i if $code[$_] eq '<';
  ++$i if $code[$_] eq '>';
  print chr $cpu[$i] if $code[$_] eq '.';
  $cpu[$i] = ord <STDIN> if $code[$_] eq ',';
  if ($code[$_] eq '[') {
    if (!$cpu[$i]) {
      ++$brc;
      while ($brc) {
        ++$_;
        ++$brc if $code[$_] eq '[';
        --$brc if $code[$_] eq ']';
      }
    } else {
      next;
    }
  } elsif ($code[$_] eq ']') {
    if (!$cpu[$i]) {
      next;
    } else {
      ++$brc if $code[$_] eq ']';
      while ($brc) {
        --$_;
        --$brc if $code[$_] eq '[';
        ++$brc if $code[$_] eq ']';
      }
    --$_;
    }
  }
}

C++

Пример интерпретатора 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

Каждый начинающий программировать на 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

Примечания: 1. Специально для функционала команды mOO в язык COW введены внутренние коды его команд[2], в таблице они указаны в отдельном столбце. 2. Отсутствие команды обозначается отс.

Brainfuck Ook! COW код COW Описание
]Ook? Ook!moo0Конец цикла
<Ook? Ook.mOo1Предыдущая ячейка
>Ook. Ook?moO2Следующая ячейка
отс.отс.mOO3Выполнить значение в текущей ячейке как команду с соответствующим кодом из диапазона 0 - 11; код 3 вызывает зацикливание
отс.отс.Moo4Если значение текущей ячейки равно нулю, то ввести его с клавиатуры; если же значение текущей ячейки — не ноль, то вывести его на экран
-Ook! Ook!MOo5Значение текущей ячейки уменьшается на 1
+Ook. Ook.MoO6Значение текущей ячейки увеличивается на 1
[Ook! Ook?MOO7Начало цикла (у COW есть особенность - пропускается первая команда цикла)
[-]отс.OOO8Обнуляет значение в текущей ячейке
отс.отс.MMM9Если регистр пуст, скопировать в него значение текущей ячейки, иначе скопировать в ячейку содержимое регистра и очистить регистр
.Ook! Ook.OOM10Вывод значения текущей ячейки
,Ook. Ook!oom11Запрос значения текущей ячейки

См. также

Диалекты и реализации

Ещё описание множества диалектов этого языка можно найти в вики-энциклопедии эзотерических языков[3]

Другие абстрактные исполнители и формальные системы вычислений

Примечания
  1. Например, исходник компилятора размером 166 байт (недоступная ссылка). Дата обращения: 18 августа 2010. Архивировано 19 августа 2010 года.
  2. COW - диалект языка программирования Brainfuck - Энциклопедия языков программирования
  3. Category:Brainfuck_derivatives, esolangs.org

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.