Brainfuck

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

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

Программы на языке писать сложно, часто приводится как один их ярких примеров «тьюринговской трясины» — тьюринг-полного языка, непрактичного в связи с примитивностью. Но при этом является вполне естественным, полным и простым языком и может использоваться при определении понятия вычислимости. Почти не используется для практического программирования (за исключением работ отдельных энтузиастов), а используется преимущественно для головоломок и задач для соревнований. Существует ряд диалектов языка, среди них — Spoon, LOLCODE, Whitespace, Feckfeck.

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

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

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

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

В «классическом» 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, досуммирование происходит перед печатанием, второе слово конструируется из остатков первого:

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

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

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

#!/usr/bin/perlopen F, shift;@code = grep {/[+-\.,\[\]><]/} split '', ;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  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++:

#include #include #include #include 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;		}	}}

Раздел ссылок нуждается в переработке или в нём указано слишком много ссылок.

Пожалуйста, удалите возможную рекламу и проверьте, все ли ссылки отвечают правилам.(19 ноября 2023)

• Оригинальное описание на английском языке и ссылки на BF-ресурсы
• Brainfuck на «Esoteric Languages wiki»
• Статья на rsdn.ru об эзотерических языках программирования
• The Brainfuck Archive (утилиты)

В статье не хватает ссылок на источники (см. рекомендации по поиску).

Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок.(26 декабря 2008)