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

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

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

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

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

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

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

Интерпретатор 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> #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

Каждый, кто начинает программировать на 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. Отсутствие команды обозначается отс.

См. также

• Тьюринговская трясина

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

• Spoon
• LOLCODE
• Whitespace
• Feckfeck

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

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

• Алгоритм Маркова ()
• Машина Тьюринга ( автоматное программирование )
• Машина Поста ( автоматное программирование )
• Рекурсивная функция (теория вычислимости)
• Лямбда-исчисление ( функциональное программирование )

Примечания

Ссылки

• — русское ЖЖ-сообщество любителей эзотерических языков
• — оптимизирующий интерпретатор и транслятор в PHP , написанный на языке PHP
• — кроссплатформенный оптимизирующий интерпретатор на Java , переехал на
• от 29 сентября 2007 на Wayback Machine
• on the
• , a brainfuck IDE compatible with Windows 7 x86 and x64.
• , Brainfuck IDE for Windows (also works with WINE under Linux)
• в каталоге ссылок Curlie (dmoz)
• , a Brainfuck to C translator.
• , a Brainfuck and Ook! language interpreter
• , another Ook! and Brainfuck language interpreter, this time written in Java.
• от 31 марта 2012 на Wayback Machine , compiler (wrap gcc) and C translator (has lots of options to control wrapping values, cell sizes, etc.)
• , a Brainfuck interpreter for iPhone written in objective c.
• , a Javascript based optimizing interpreter. Also has many options, including memory dumping.
• , a lightweight Brainfuck interpreter written in C.
• , an interpreter for the Brainfuck language and its dialects written in the Java programming language.
• , open-source Brainfuck interpreter written in C.