Loading AI tools
Brainf*ck — один из эзотерических языков программирования, придуман Урбаном Мюллером (нем. Urban Müller) в 1993 году, известен своим минимализмом. Название языка можно перевести на русский как вынос мозга, оно напрямую образовано от английского выражения brainf*ck (brain — мозг, fuck — вынос), т. е. заниматься ерундой. Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainf*ck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.
| Brainf*ck | |
|---|---|
| Класс языка | Эзотерический, Императивный, Структурный |
| Появился в | 1993 |
| Автор | Урбан Мюллер |
| Разработчик | Урбан Мюллер[вд] |
| Расширение файлов |
.b или .bf |
| Диалекты | Brains*b, Brainfork, Brainloller, COW, Ook, Pbrain, Smallf*ck, Spoon, LOLCODE, Whitespace, DoubleFuck, Feckfeck |
| Испытал влияние | FALSE |
| Сайт | brainfuck.org (англ.) |
 Медиафайлы на Викискладе | |
Одним из мотивов Урбана Мюллера было создание языка с как можно меньшим компилятором. Отчасти он был вдохновлён языком FALSE, для которого существовал компилятор размером 2044 байта. Существуют компиляторы языка Brainf*ck размером меньше 200 байт[1]. Программы на языке Brainfuck писать сложно, за что его иногда называют языком для мазохистов. Но при этом Brainf*ck является вполне естественным, полным и простым языком и может использоваться при определении понятия вычислимости.
Машина, которой управляют команды Brainfuck, состоит из упорядоченного набора ячеек и указателя текущей ячейки, напоминая ленту и головку машины Тьюринга. Кроме того, подразумевается устройство общения с внешним миром (см. команды . и ,) через поток ввода и поток вывода.
Язык Brainfuck можно описать с помощью эквивалентов языка Си:
| Команда Brainfuck | Эквивалент на Си | Описание команды |
|---|---|---|
| Начало программы | int i = 0; | выделяется память под 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, сразу печать перевода строки |
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>
#include <iterator>
int main(int argc, char **argv) {
std::fstream file(argv[1], std::ios::in);
std::istreambuf_iterator<char> fstart(file), fend;
std::vector<unsigned char> itape(fstart, fend);
file.close();
std::vector<unsigned char> mtape(30000, 0);
std::vector<unsigned char>::iterator m = mtape.begin();
std::vector<unsigned char>::iterator i = itape.begin();
int b = 0;
for(; i != itape.end(); ++i) {
switch(*i){
case '>':
if(++m == mtape.end()) {
mtape.push_back(0);
m = --mtape.end();
}
break;
case '<': --m; break;
case '+': ++*m; break;
case '-': --*m; break;
case '.': std::cout << *m; break;
case ',': std::cin >> *m; break;
case '[':
if (*m) continue;
++b;
while(b)
switch(*++i){
case '[': ++b; break;
case ']': --b; break;
}
break;
case ']':
if(!*m) continue;
++b;
while(b)
switch(*--i){
case '[': --b; break;
case ']': ++b; break;
}
--i;
break;
}
}
}
Каждый, кто начинает программировать на 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 почти не используется для практического программирования (за исключением работ отдельных энтузиастов), а используется преимущественно для головоломок и задач для соревнований.
Примечания: 1. Специально для функционала команды mOO в язык COW введены внутренние коды его команд[2], в таблице они указаны в отдельном столбце. 2. Отсутствие команды обозначается отс.
| Brainfuck | Ook! | COW | код COW | Описание |
| ] | Ook? Ook! | moo | 0 | Конец цикла |
| < | Ook? Ook. | mOo | 1 | Предыдущая ячейка |
| > | Ook. Ook? | moO | 2 | Следующая ячейка |
| отс. | отс. | mOO | 3 | Выполнить значение в текущей ячейке как команду с соответствующим кодом из диапазона 0 - 11; код 3 вызывает зацикливание |
| отс. | отс. | Moo | 4 | Если значение текущей ячейки равно нулю, то ввести его с клавиатуры; если же значение текущей ячейки — не ноль, то вывести его на экран |
| - | Ook! Ook! | MOo | 5 | Значение текущей ячейки уменьшается на 1 |
| + | Ook. Ook. | MoO | 6 | Значение текущей ячейки увеличивается на 1 |
| [ | Ook! Ook? | MOO | 7 | Начало цикла (у COW есть особенность - пропускается первая команда цикла) |
| [-] | отс. | OOO | 8 | Обнуляет значение в текущей ячейке |
| отс. | отс. | MMM | 9 | Если регистр пуст, скопировать в него значение текущей ячейки, иначе скопировать в ячейку содержимое регистра и очистить регистр |
| . | Ook! Ook. | OOM | 10 | Вывод значения текущей ячейки |
| , | Ook. Ook! | oom | 11 | Запрос значения текущей ячейки |
Диалекты и реализации
Ещё описание множества диалектов этого языка можно найти в вики-энциклопедии эзотерических языков[3]
Другие абстрактные исполнители и формальные системы вычислений
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
