Brainfuck
Шаблон:Также Шаблон:Карточка языка программирования Brainfuck — один из эзотерических языков программирования, придуман Урбаном Мюллером (нем. Urban Müller) в 1993 году, известен своим минимализмом. Название языка можно перевести на русский как вынос мозга (англ. Шаблон:Lang-en2). Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.
Одним из мотивов Урбана Мюллера было создание языка с как можно меньшим компилятором. Отчасти он был вдохновлён языком FALSE, для которого существовал компилятор размером 2044 байта. Существуют компиляторы языка Brainfuck размером меньше 200 байт<ref>Шаблон:Cite web</ref>.
Программы на языке писать сложно, часто приводится как один их ярких примеров «тьюринговской трясины» — тьюринг-полного языка, непрактичного в связи с примитивностью. Но при этом является вполне естественным, полным и простым языком и может использоваться при определении понятия вычислимости. Почти не используется для практического программирования (за исключением работ отдельных энтузиастов), а используется преимущественно для головоломок и задач для соревнований. Существует ряд диалектов языка, среди них — Spoon, LOLCODE, Whitespace, Feckfeck.
Синтаксис
Машина, которой управляют команды Brainfuck, состоит из упорядоченного набора ячеек и указателя текущей ячейки, напоминая ленту и головку машины Тьюринга. Кроме того, подразумевается устройство общения с внешним миром (см. команды . и ,) через поток ввода и поток вывода.
Язык Brainfuck можно описать с помощью эквивалентов языка Си:
| Команда Brainfuck | Эквивалент на Си | Описание команды |
|---|---|---|
| Начало программы | char arr[30000]; |
выделяется память под 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): <source lang="bf"> >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.>>>++++++++[<++++>-] <.>>>++++++++++[<+++++++++>-]<---.<<<<.+++.------.--------.>>+.>++++++++++.</source> Итого 389 операторов и использована 1 ячейка памяти. Оптимизированная программа заметно короче — всего 111 операторов, но 5 ячеек памяти. Первая ячейка используется как обратный счётчик цикла на 10 итераций, в последующих ячейках находятся числа 7, 10, 3 и 1, наращиваемые этим циклом до 70, 100, 30 и 10, досуммирование происходит перед печатанием, второе слово конструируется из остатков первого: <source lang="bf">
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++ .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++. ------.--------.>+.>.</source>
Разбор программы: Шаблон:-
| Цикл формирования основных чисел | |
++++++++++ |
присваивание ячейке 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:
<source lang="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 ']';
}
--$_;
}
}
} </source>
Пример интерпретатора на C++: <source lang="cpp">
- 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; } } } </source>