|
Brainfuck
Brainf*ck — один из эзотерических языков программирования, придуман Урбаном Мюллером (нем. Urban Müller) в 1993 году, известен своим минимализмом. Название языка можно перевести на русский как вынос мозга, оно напрямую образовано от английского выражения brainf*ck (brain — мозг, fuck — вынос), т. е. заниматься ерундой. Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainf*ck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса. Одним из мотивов Урбана Мюллера было создание языка с как можно меньшим компилятором. Отчасти он был вдохновлён языком FALSE, для которого существовал компилятор размером 2044 байта. Существуют компиляторы языка Brainf*ck размером меньше 200 байт[1]. Программы на языке Brainfuck писать сложно, за что его иногда называют языком для мазохистов. Но при этом Brainf*ck является вполне естественным, полным и простым языком и может использоваться при определении понятия вычислимости. Общее описание языкаМашина, которой управляют команды Brainfuck, состоит из упорядоченного набора ячеек и указателя текущей ячейки, напоминая ленту и головку машины Тьюринга. Кроме того, подразумевается устройство общения с внешним миром (см. команды . и ,) через поток ввода и поток вывода. Язык Brainfuck можно описать с помощью эквивалентов языка Си:
Несмотря на внешнюю примитивность, Brainfuck с бесконечным набором ячеек имеет тьюринговскую полноту, а, следовательно, по потенциальным возможностям не уступает «настоящим» языкам, подобным Си, Паскалю или Java. Brainfuck подходит для экспериментов по генетическому программированию из-за простоты синтаксиса, и, соответственно, генерации исходного кода. В «классическом» Brainfuck, описанном Мюллером, размер ячейки — один байт, количество ячеек 30 000. В начальном состоянии указатель находится в крайней левой позиции, а все ячейки заполнены нулями. Увеличение или уменьшение значений ячеек происходит по модулю 256. Ввод-вывод также происходит побайтно, с учётом кодировки ASCII (то есть в результате операции ввода (,) символ 1 будет записан в текущую ячейку как число 0x31 (49), а операция вывода (.), совершённая над ячейкой, содержащей 0x41 (65), напечатает латинскую А). В других вариантах языка размер и количество ячеек может быть другим (бо́льшим). Есть версии, где значение ячеек не целочисленно (с плавающей точкой). Пример программы
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.>>>++++++++[<++++>-]
<.>>>++++++++++[<+++++++++>-]<---.<<<<.+++.------.--------.>>+.>++++++++++.
Итого 389 операторов и использована 1 ячейка памяти. Оптимизированная программа заметно короче - всего 111 операторов, но 5 ячеек памяти. Первая ячейка используется как обратный счётчик цикла на 10 итераций, в последующих ячейках находятся числа 7, 10, 3 и 1, наращиваемые этим циклом до 70, 100, 30 и 10, досуммирование происходит перед печатанием, второе слово конструируется из остатков первого: ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
------.--------.>+.>.
Разбор программы:
Интерпретатор BrainfuckPerlПример интерпретатора 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 раз…< Brainfuck почти не используется для практического программирования (за исключением работ отдельных энтузиастов), а используется преимущественно для головоломок и задач для соревнований. Языки на основе BrainfuckПримечания: 1. Специально для функционала команды mOO в язык COW введены внутренние коды его команд[2], в таблице они указаны в отдельном столбце. 2. Отсутствие команды обозначается отс.
См. такжеДиалекты и реализацииЕщё описание множества диалектов этого языка можно найти в вики-энциклопедии эзотерических языков[3] Другие абстрактные исполнители и формальные системы вычислений
Примечания
Ссылки
Реализации языка
IDE
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
