Brainfuck | |
---|---|
Класс языка | эзотерический |
Появился в | 1993 |
Автор | Урбан Мюллер |
Разработчик | Урбан Мюллер[d] |
Расширение файлов |
.b или .bf |
Диалекты | BrainSub, Brainfork, Brainloller, COW, Ook, Pbrain, Smallfuck, Spoon, LOLCODE, Whitespace, DoubleFuck, Feckfeck |
Испытал влияние | FALSE |
Brainfuck — один из известнейших эзотерических языков программирования, придуман Урбаном Мюллером (нем. Urban Müller) в 1993 году, известен своим минимализмом. Название языка можно перевести на русский как вынос мозга, оно напрямую образовано от английского выражения brainfuck (brain — мозг, fuck — иметь половое сношение), т. е. заниматься ерундой. Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.
Одним из мотивов Урбана Мюллера было создание языка с как можно меньшим компилятором. Отчасти он был вдохновлён языком FALSE, для которого существовал компилятор размером 1024 байта. Существуют компиляторы языка Brainfuck размером меньше 200 байт.[1] Программы на языке Brainfuck писать сложно, за что его иногда называют языком для мазохистов. Но при этом важно отметить, что Brainfuck является вполне естественным, полным и простым языком и может использоваться при определении понятия вычислимости.
Машина, которой управляют команды Brainfuck, состоит из упорядоченного набора ячеек и указателя текущей ячейки, напоминая ленту и головку машины Тьюринга. Кроме того, подразумевается устройство общения с внешним миром (см. команды . и ,) через поток ввода и поток вывода.
Язык Brainfuck можно описать с помощью эквивалентов языка Си:
Команда Brainfuck | Эквивалент на Си | Описание команды |
---|---|---|
Начало программы | int i = 0; | выделяется память под 30 000 ячеек с нулевыми начальными значениями |
> | i++; | перейти к следующей ячейке |
< | i--; | перейти к предыдущей ячейке |
+ | arr[i]++; | увеличить значение в текущей ячейке на 1 |
- | arr[i]--; | уменьшить значение в текущей ячейке на 1 |
. | putchar(arr[i]); | напечатать значение из текущей ячейки |
, | arr[i] = getchar(); | ввести извне значение и сохранить в текущей ячейке |
[ | while(arr[i]){ | если значение текущей ячейки ноль, перейти вперёд по тексту программы на ячейку, следующую за соответствующей ] (с учётом вложенности) |
] | } | если значение текущей ячейки не нуль, перейти назад по тексту программы на символ [ (с учётом вложенности) |
Несмотря на внешнюю примитивность, Brainfuck с бесконечным набором ячеек имеет тьюринговскую полноту, а, следовательно, по потенциальным возможностям не уступает «настоящим» языкам, подобным Си, Паскалю или Java.
Brainfuck подходит для экспериментов по генетическому программированию из-за простоты синтаксиса, и, соответственно, генерации исходного кода.
В «классическом» Brainfuck, описанном Мюллером, размер ячейки — один байт, количество ячеек 30 000. В начальном состоянии указатель находится в крайней левой позиции, а все ячейки заполнены нулями. Увеличение/уменьшение значений ячеек происходит по модулю 256. Ввод-вывод также происходит побайтно, с учётом кодировки ASCII (то есть в результате операции ввода (,) символ 1 будет записан в текущую ячейку как число 0x31 (49), а операция вывода (.), совершённая над ячейкой, содержащей 0x41 (65), напечатает латинскую А). В других вариантах языка размер и количество ячеек может быть другим (бо́льшим). Есть версии, где значение ячеек не целочисленно (с плавающей точкой).
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
------.--------.>+.>.
Разбор программы:
Подготовка в памяти (с ячейки 1) массива значений, близких к ASCII-кодам символов, которые необходимо вывести (70, 100, 30, 10), через повторение 10 раз приращения ячеек на 7, 10, 3 и 1, соответственно | ||
++++++++++ | присваивание ячейке 0 (счетчику) значения 10 | |
[ | повторять, пока значение текущей ячейки (ячейки 0) больше нуля | |
>+++++++ | приращение ячейки 1 на 7 | |
>++++++++++ | приращение ячейки 2 на 10 | |
>+++ | приращение ячейки 3 на 3 | |
>+ | приращение ячейки 4 на 1 | |
<<<<- | возврат к ячейке 0 (счетчику), и его уменьшение на 1 | |
] | вернуться к началу цикла | |
Получение кодов букв и их вывод | ||
>++. | Вывод «Н». Получение кода «H» (72) из 70 в ячейке 1 и вывод | |
>+. | Вывод «e». Получение кода «e» (101) из 100 в ячейке 2 и вывод | |
+++++++.. | Вывод «ll». Получение кода «l» (108) из 101 в ячейке 2 и вывод дважды | |
+++. | Вывод «o». Получение кода «o» (111) из 108 в ячейке 2 и вывод | |
>++. | Вывод пробела. Получение кода пробела (32) из 30 в ячейке 3 и вывод | |
<<+++++++++++++++. | Вывод «W». Получение кода «W» (87) из 72 в ячейке 1 и вывод | |
>. | Вывод «o». Код «o» (111) уже находится в ячейке 2, просто его выводим | |
+++. | Вывод «r». Получение кода «r» (114) из 111 в ячейке 2 и вывод | |
------. | Вывод «l». Получение кода «l» (108) из 114 в ячейке 2 и вывод | |
--------. | Вывод «d». Получение кода «d» (100) из 108 в ячейке 2 и вывод | |
>+. | Вывод «!». Получение кода «!» (33) из 32 в ячейке 3 и вывод | |
>. | Вывод кода перевода строки (10) из ячейки 4 |
В принципе, печать «Hello World!» можно реализовать проще, но программа будет в три с лишним раза больше, чем приведённый выше оптимизированный вариант:
+++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++.+++++++++++++++++
++++++++++++.+++++++..+++.-------------------
---------------------------------------------
---------------.+++++++++++++++++++++++++++++
++++++++++++++++++++++++++.++++++++++++++++++
++++++.+++.------.--------.------------------
---------------------------------------------
----.-----------------------.
Пример интерпретатора 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 ']';
}
--$_;
}
}
}
Пример интерпретатора Brainfuck, написанный на языке C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
static char cpu[30000];
int main(int argc, char **argv) {
vector<char> acc;
char ch;
ifstream infile(argv[1]);
while (infile) {
infile.get(ch);
acc.push_back(ch);
}
infile.close();
unsigned int j = 0;
int brc = 0;
for (int i = 0; i < acc.size(); ++i) {
if (acc[i] == '>')
j++;
if (acc[i] == '<')
j--;
if (acc[i] == '+')
cpu[j]++;
if (acc[i] == '-')
cpu[j]--;
if (acc[i] == '.')
cout << cpu[j];
if (acc[i] == ',')
cin >> cpu[j];
if (acc[i] == '[') {
if (!cpu[j]) {
++brc;
while (brc) {
++i;
if (acc[i] == '[')
++brc;
if (acc[i] == ']')
--brc;
}
} else
continue;
} else if (acc[i] == ']') {
if (!cpu[j])
continue;
else {
if (acc[i] == ']')
brc++;
while (brc) {
--i;
if (acc[i] == '[')
brc--;
if (acc[i] == ']')
brc++;
}
--i;
}
}
}
}
Каждый начинающий программировать на 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 почти не используется для практического программирования (за исключением работ отдельных энтузиастов), а используется преимущественно для головоломок и задач для соревнований.
Ook! | COW | Brainfuck | Описание |
Ook. Ook. | MoO | + | Значение текущей ячейки увеличивает на 1 |
Ook! Ook! | MOo | - | Значение текущей ячейки уменьшают на 1 |
Ook. Ook? | moO | > | Следующая ячейка |
Ook? Ook. | mOo | < | Предыдущая ячейка |
Ook! Ook? | moo | [ | Начало цикла |
Ook? Ook! | MOO | ] | Конец цикла |
Ook! Ook. | OOM | . | Вывод значения текущей ячейки |
Ook. Ook! | oom | , | Запрос значения текущей ячейки |
mOO | отсутствует | Выполняет инструкцию с номером, который берётся из текущей ячейки (если значение в текущей ячейке равно 3, то это приводит к бесконечному циклу). | |
Moo | отсутствует | Если значение текущей ячейки равно нулю, то ввести его с клавиатуры; если же значение текущей ячейки — не ноль, то вывести его на экран. | |
OOO | [-] | Обнуляет значение в текущей ячейке | |
MMM | отсутствует |
Ещё описание множества диалектов этого языка можно найти в вики-энциклопедии эзотерических языков[2]
Для улучшения этой статьи по информационным технологиям желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .