Brainfuck
Brainfuck | |
---|---|
Класс языка | Эзотерический, Императивный, Структурный |
Появился в | 1993 |
Автор | Урбан Мюллер |
Разработчик | Урбан Мюллер[вд] |
Расширение файлов | .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, для которого существовал компилятор размером 2044 байта. Существуют компиляторы языка 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), напечатает латинскую А). В других вариантах языка размер и количество ячеек может быть другим (бо́льшим). Есть версии, где значение ячеек не целочисленно (с плавающей точкой).
Пример программы
- Пошаговая программа на языке 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)
IDE
- Visual brainfuck, IDE совместимая с Windows 7
- Brainfuck Developer, IDE для Windows (также запускается под WINE)