Brainfuck
| Brainf*ck | |
|---|---|
| Класс языка | Эзотерический, Императивный, Структурный |
| Появился в | 1993 |
| Автор | Урбан Мюллер |
| Разработчик | Урбан Мюллер[вд] |
| Расширение файлов |
.b или .bf |
| Диалекты | Brains*b, Brainfork, Brainloller, COW, Ook, Pbrain, Smallf*ck, Spoon, LOLCODE, Whitespace, DoubleFuck, Feckfeck |
| Испытал влияние | FALSE |
| Сайт | brainfuck.org (англ.) |
 Медиафайлы на Викискладе | |
Brainf*ck — один из эзотерических языков программирования, придуман Урбаном Мюллером (нем. Urban Müller) в 1993 году, известен своим минимализмом. Название языка можно перевести на русский как вынос мозга, оно напрямую образовано от английского выражения brainf*ck (brain — мозг, fuck — вынос), т. е. заниматься ерундой. Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainf*ck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.
Одним из мотивов Урбана Мюллера было создание языка с как можно меньшим компилятором. Отчасти он был вдохновлён языком FALSE, для которого существовал компилятор размером 2044 байта. Существуют компиляторы языка Brainf*ck размером меньше 200 байт[1]. Программы на языке Brainfuck писать сложно, за что его иногда называют языком для мазохистов. Но при этом Brainf*ck является вполне естественным, полным и простым языком и может использоваться при определении понятия вычислимости.
Общее описание языка
[править | править код]Машина, которой управляют команды 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), напечатает латинскую А). В других вариантах языка размер и количество ячеек может быть другим (бо́льшим). Есть версии, где значение ячеек не целочисленно (с плавающей точкой).
Пример программы
[править | править код]- Пошаговая программа на языке 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
[править | править код]Пример интерпретатора 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], в таблице они указаны в отдельном столбце. 2. Отсутствие команды обозначается отс.
| Brainfuck | Ook! | COW | код COW | Описание |
| ] | Ook? Ook! | moo | 0 | Конец цикла |
| < | Ook? Ook. | mOo | 1 | Предыдущая ячейка |
| > | Ook. Ook? | moO | 2 | Следующая ячейка |
| отс. | отс. | mOO | 3 | Выполнить значение в текущей ячейке как команду с соответствующим кодом из диапазона 0 - 11; код 3 вызывает зацикливание |
| отс. | отс. | Moo | 4 | Если значение текущей ячейки равно нулю, то ввести его с клавиатуры; если же значение текущей ячейки — не ноль, то вывести его на экран |
| - | Ook! Ook! | MOo | 5 | Значение текущей ячейки уменьшается на 1 |
| + | Ook. Ook. | MoO | 6 | Значение текущей ячейки увеличивается на 1 |
| [ | Ook! Ook? | MOO | 7 | Начало цикла (у COW есть особенность - пропускается первая команда цикла) |
| [-] | отс. | OOO | 8 | Обнуляет значение в текущей ячейке |
| отс. | отс. | MMM | 9 | Если регистр пуст, скопировать в него значение текущей ячейки, иначе скопировать в ячейку содержимое регистра и очистить регистр |
| . | Ook! Ook. | OOM | 10 | Вывод значения текущей ячейки |
| , | Ook. Ook! | oom | 11 | Запрос значения текущей ячейки |
См. также
[править | править код]Диалекты и реализации
[править | править код]Ещё описание множества диалектов этого языка можно найти в вики-энциклопедии эзотерических языков[3]
Другие абстрактные исполнители и формальные системы вычислений
[править | править код]- Алгоритм Маркова (продукционное программирование)
- Машина Тьюринга (автоматное программирование)
- Машина Поста (автоматное программирование)
- Рекурсивная функция (теория вычислимости)
- Лямбда-исчисление (функциональное программирование)
Примечания
[править | править код]- ↑ Исходник компилятора размером в 166 байт. Дата обращения: 27 ноября 2023. Архивировано 21 октября 2023 года.
- ↑ COW - диалект языка программирования Brainfuck - Энциклопедия языков программирования. Дата обращения: 11 декабря 2020. Архивировано 5 мая 2021 года.
- ↑ Category:Brainfuck_derivatives Архивная копия от 14 апреля 2012 на Wayback Machine, esolangs.org
Ссылки
[править | править код] | Раздел ссылок нуждается в переработке или в нем указано слишком много ссылок. |
- ru_brainfucker — русское ЖЖ-сообщество любителей эзотерических языков
- Оригинальное описание BF на английском языке и ссылки на BF-ресурсы
- Brainfuck на «Esoteric Languages wiki»
- Статья на rsdn.ru об эзотерических языках программирования
- Статья о создании транслятора brainfuck в C на habrahabr
- The Brainfuck Archive (утилиты)
- Brainfuck в каталоге ссылок Curlie (dmoz)
Реализации языка
[править | править код]- esco — универсальный интерпретатор эзотерических языков
- Интерпретатор с открытым исходным кодом (C++)
- Переводчик с brainfuck на Perl и обратно с открытым исходным кодом. procool.ru. Архивировано из оригинала 1 декабря 2012 года.
- Processing_BF, оптимизирующий интерпретатор и транслятор в PHP (написан на PHP)
- Brainfuck Java, интерпретатор для BF и его диалектов (Java)
- Ook! и Brainfuck интерпретатор (Java)
- Интерпретатор на JavaScript с открытым исходным кодом. brainfuck.progopedia.ru. Архивировано из оригинала 5 ноября 2012 года.
- Le Brainfuck, оптимизирующий интерпретатор (JavaScript)
- lex / yacc-based интерпретатор (Си и Python)
- Интерпретатор (Python)
- ookie, Brainfuck и Ook! интерпретатор
- Brainfuck C, интерпретатор (язык Си)
- Bfck, open-source интерпретатор (язык Си)
- bf2c, транслятор с Brainfuck на Cи
- Brain Force Compiler (англ.). beco.cc. Архивировано из оригинала 7 мая 2017 года., компилятор (враппер GCC) и транслятор в Си
- esolang, интерпретатор для iPhone (Objective-C)
- braintractor, интерпретатор и модуль для встраивания (язык Lua)
IDE
[править | править код]- Visual brainfuck, IDE совместимая с Windows 7
- Brainfuck Developer, IDE для Windows (также запускается под WINE)
 | Для улучшения этой статьи по информационным технологиям желательно:
|