Brainfuck

Brainfuck

Класс языка:	эзотерический
Появился в:	1993
Автор(ы):	Урбан Мюллер
Диалекты:	BrainSub, Brainfork, Brainloller, COW, Ook, Pbrain, Smallfuck, Spoon, LOLCODE, Whitespace,DoubleFuck, Feckfeck
Испытал влияние:	FALSE

Brainfuck (англ. brain мозг + fuck) — один из известнейших эзотерических языков программирования, придуман Урбаном Мюллером (нем. Urban Müller) в 1993 году для забавы. Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.

Одним из мотивов Урбана Мюллера было создание языка с как можно меньшим компилятором. Отчасти он был вдохновлён языком FALSE, для которого существовал компилятор размера 1024 байта. Существуют компиляторы языка Brainfuck размера меньше 200 байт.^[1] Программы на языке Brainfuck писать сложно, за что его иногда называют языком для мазохистов. Но при этом важно отметить, что Brainfuck является вполне естественным, полным и простым языком и может использоваться при определении понятия вычислимости.

Машина, которой управляют команды Brainfuck, состоит из упорядоченного набора ячеек и указателя текущей ячейки, напоминая ленту и головку машины Тьюринга. Кроме того, подразумевается устройство общения с внешним миром (см. команды . и ,) через поток ввода и поток вывода.

Язык Brainfuck можно описать с помощью эквивалентов языка Си (предполагается, что переменная p объявлена как указатель на байт):

Команда Brainfuck	Эквивалент на Си	Описание команды
>	++p;	перейти к следующей ячейке
<	--p;	перейти к предыдущей ячейке
+	++(*p);	увеличить значение в текущей ячейке на 1
-	--(*p);	уменьшить значение в текущей ячейке на 1
.	putchar(*p);	напечатать значение из текущей ячейки
,	*p = getchar();	ввести извне значение и сохранить в текущей ячейке
[	while (*p) {	если значение текущей ячейки нуль, перейти вперёд по тексту программы на ячейку, следующую за соответствующей ] (с учётом вложенности)
]	}	если значение текущей ячейки не нуль, перейти назад по тексту программы на символ [ (с учётом вложенности)

Несмотря на внешнюю примитивность, Brainfuck с бесконечным набором ячеек имеет тьюринговскую полноту, а, следовательно, по потенциальным возможностям не уступает «настоящим» языкам, подобным Си, Паскалю или Java.

Brainfuck подходит для экспериментов по генетическому программированию из-за простоты синтаксиса, и, соответственно, генерации исходного кода.

В «классическом» Brainfuck, описанном Мюллером, размер ячейки — один байт, количество ячеек 30 000. В начальном состоянии указатель находится в крайней левой позиции, а все ячейки заполнены нулями. Увеличение/уменьшение значений ячеек происходит по модулю 256. Ввод/вывод также происходит побайтно, с учётом кодировки ASCII (то есть в результате операции ввода (,) символ 1 будет записан в текущую ячейку как число 0x31 (49), а операция вывода (.), совершённая над ячейкой, содержащей 0x41 (65), напечатает латинскую А). В других вариантах языка размер и количество ячеек может быть другим (бо́льшим). Есть версии, где значение ячеек не целочисленно (с плавающей точкой).

Пример программы

Программа на языке Brainfuck, печатающая «Hello World!»:

 ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
 .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
 ------.--------.>+.>.

Разбор программы:

Подготовка в памяти (с ячейки 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

Ниже приведён код интерпретатора 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

Каждый начинающий программировать на 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

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	отсутствует

См. также

• Тьюринговская трясина

Диалекты и реализации

• Spoon
• LOLCODE
• Whitespace
• Feckfeck

Ещё описание множества диалектов этого языка можно найти в вики-энциклопедии эзотерических языков^[2]

Другие абстрактные исполнители и формальные системы вычислений

• Алгоритм Маркова (продукционное программирование)
• Машина Тьюринга (автоматное программирование)
• Машина Поста (автоматное программирование)
• Рекурсивная функция (теория вычислимости)
• Лямбда-исчисление (функциональное программирование)

Примечания

1. ↑ например, исходник компилятора размером 166 байт. Архивировано из первоисточника 25 августа 2011. Проверено 18 августа 2010.
2. ↑ Category:Brainfuck_derivatives, esolangs.org

Ссылки

• Немного о brainfuck на русском языке и пара инструментов для работы с ним
• Оригинальное описание BF на английском языке и ссылки на BF-ресурсы
• Brainfuck interpreter with integrated debugger (IDE) for Windows
• ru_brainfucker — русское ЖЖ-сообщество любителей эзотерических языков
• статья на rsdn.ru об эзотерических языках программирования
• Processing_BF — оптимизирующий интерпретатор и транслятор в PHP, написанный на языке PHP
• BrainfuckInterpreter — кроссплатформенный оптимизирующий интерпретатор на Java, переехал на Brainfuck Interpreter bfrun
• esco — универсальный интерпретатор эзотерических языков
• Интерпретатор brainfuck на JavaScript с открытым исходным кодом
• Переводчик с brainfuck на Perl и обратно с открытым исходным кодом
• Интерпретатор brainfuck с открытым исходным кодом
• Статья о создании транслятора brainfuck в C
• The Brainfuck Archive
• Brainfuck on the Esolang (Esoteric Languages) wiki
• Visual brainfuck, a brainfuck IDE compatible with Windows 7 x86 and x64.
• Brainfuck Developer, Brainfuck IDE for Windows (also works with WINE under Linux)
• Brainfuck в каталоге ссылок Open Directory Project (dmoz).
• bf2c, a Brainfuck to C translator.
• ookie, a Brainfuck and Ook! language interpreter
• Ook.jar, another Ook! and Brainfuck language interpreter, this time written in Java.
• BrainForce, compiler (wrap gcc) and C translator (has lots of options to control wrapping values, cell sizes, etc.)
• esolang, a Brainfuck interpreter for iPhone written in objective c.
• Le Brainfuck, a Javascript based optimizing interpreter. Also has many options, including memory dumping.
• Brainfuck C, a lightweight Brainfuck interpreter written in C.
• Brainfuck Java, an interpreter for the Brainfuck language and its dialects written in the Java programming language.
• lex/yacc-based Brainfuck interpreter in C and Python
• Bfck, open-source Brainfuck interpreter written in C.

Для улучшения этой статьи по информационным технологиям желательно?: Переработать оформление в соответствии с правилами написания статей. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Проставив сноски, внести более точные указания на источники.