Brainfuck

См. также: BF

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

Brainfuck
Класс языка	Эзотерический, Императивный, Структурный
Появился в	1993
Автор	Урбан Мюллер
Разработчик	Урбан Мюллер[вд]
Расширение файлов	.b или .bf
Диалекты	Brains*b, Brainfork, Brainloller, COW, Ook, Pbrain, Smallfuck, Spoon, LOLCODE, Whitespace, DoubleFuck, Feckfeck
Испытал влияние	FALSE
Сайт	brainfuck.org (англ.)
Медиафайлы на Викискладе

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

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

Синтаксис

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

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

Команда Brainfuck	Эквивалент на Си	Описание команды
Начало программы	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, описанном Мюллером, размер ячейки — один байт, количество ячеек 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:

#!/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++:

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