Просмотр кода страницы Brainfuck

{{Также|BF}}
{{Карточка языка программирования
 | name = Brainfuck
 | logo =
 | semantics =
 | paradigm = [[Эзотерический язык программирования|Эзотерический]], [[Императивное программирование|Императивный]], [[Структурное программирование|Структурный]]
 | class=
 | year = 1993
 | designer = Урбан Мюллер
 | extension =
 | latest_release_version =
 | latest_release_date =
 | latest_preview_version =
 | latest_preview_date =
 | typing =
 | implementations =
 | dialects = Brains*b, Brainfork, Brainloller, COW, Ook, Pbrain, Smallfuck, [[Spoon]], [[LOLCODE]], [[Whitespace]], [[DoubleFuck]], [[Feckfeck]]
 | influenced_by = [[FALSE]]
 | influenced =
}}
'''Brainfuck''' — один из [[Эзотерические языки программирования|эзотерических языков программирования]], придуман [[Мюллер, Урбан|Урбаном Мюллером]] ({{lang-de|Urban Müller}}) в [[1993 год]]у, известен своим минимализмом. Название языка можно перевести на русский как ''вынос мозга'' ({{lang-en|brainfuck}}). Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.

Одним из мотивов Урбана Мюллера было создание языка с как можно меньшим компилятором. Отчасти он был вдохновлён языком [[FALSE]], для которого существовал компилятор размером 2044 байта. Существуют компиляторы языка Brainfuck размером меньше 200 байт<ref>{{cite web|url=https://www.muppetlabs.com/~breadbox/software/tiny/bf.asm.txt|title=Исходник компилятора размером в 166 байт|accessdate=2023-11-27|archiveurl=https://web.archive.org/web/20231021113315/http://www.muppetlabs.com:80/~breadbox/software/tiny/bf.asm.txt|archivedate=2023-10-21|url-status=live}}</ref>.

Программы на языке писать сложно, часто приводится как один их ярких примеров «[[Тьюринговская трясина|тьюринговской трясины]]» — [[Полнота по Тьюрингу|тьюринг-полного]] языка, непрактичного в связи с примитивностью. Но при этом является вполне естественным, полным и простым языком и может использоваться при определении понятия [[Вычислимые функции|вычислимости]]. Почти не используется для практического программирования (за исключением работ отдельных энтузиастов), а используется преимущественно для головоломок и задач для соревнований. Существует ряд диалектов языка, среди них — [[Spoon]], [[LOLCODE]], [[Whitespace]], [[Feckfeck]].

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

Язык Brainfuck можно описать с помощью эквивалентов [[Си (язык программирования)|языка Си]]:
{|class="wikitable"
! Команда Brainfuck
! Эквивалент на Си
! Описание команды
|-
|style="text-align:center"|Начало программы|| <code>char arr[30000];<br>memset(arr, 0, sizeof(arr));</code> || выделяется память под 30 000 ячеек с нулевыми начальными значениями
|-
|style="text-align:center"|<code>></code> || <code>i++;</code> || перейти к следующей ячейке
|-
|style="text-align:center"|<code><</code> || <code>i--;</code> || перейти к предыдущей ячейке
|-
|style="text-align:center"|<code>+</code> || <code>arr[i]++;</code> || увеличить значение в текущей ячейке на 1
|-
|style="text-align:center"|<code>-</code> || <code>arr[i]--;</code> || уменьшить значение в текущей ячейке на 1
|-
|style="text-align:center"|<code>.</code> || <code>putchar(arr[i]);</code> || напечатать значение из текущей ячейки
|-
|style="text-align:center"|<code>,</code> || <code>arr[i]&nbsp;=&nbsp;getchar();</code> || ввести извне значение и сохранить в текущей ячейке
|-
|style="text-align:center"|<code>[</code> || <code>while(arr[i]){</code> || если значение текущей ячейки ноль, перейти вперёд по тексту программы на символ, следующий за соответствующей <tt>]</tt> (с учётом вложенности)
|-
|style="text-align:center"|<code>]</code> || <code>}</code> || если значение текущей ячейки не ноль, перейти назад по тексту программы на символ <tt>[</tt> (с учётом вложенности)
|}

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

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

В «классическом» 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):
<source lang="bf">
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.>>>++++++++[<++++>-]
<.>>>++++++++++[<+++++++++>-]<---.<<<<.+++.------.--------.>>+.>++++++++++.</source>
Итого 389 операторов и использована 1 ячейка памяти. Оптимизированная программа заметно короче — всего 111 операторов, но 5 ячеек памяти. Первая ячейка используется как обратный счётчик цикла на 10 итераций, в последующих ячейках находятся числа ''7, 10, 3 и 1'', наращиваемые этим циклом до ''70, 100, 30 и 10'', досуммирование происходит перед печатанием, второе слово конструируется из остатков первого:
<source lang="bf">
 ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
 .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
 ------.--------.>+.>.</source>

Разбор программы:
{{-}}
{|frame style="padding-left: 10px"
 | colspan = 2 style = "text-align: center" | '''Цикл формирования основных чисел'''
 |-
 | '''<code>++++++++++</code>''' || присваивание ''ячейке 0'' значения 10
 |-
 | '''<code>[</code>''' || повторять описанные этой скобкой команды, пока значение текущей ''ячейки 0'' не равно нулю
 |-
 | '''<code>>+++++++</code>''' || приращение ''ячейки 1'' на 7
 |-
 | '''<code>>++++++++++</code>''' || приращение ''ячейки 2'' на 10
 |-
 | '''<code>>+++</code>''' || приращение ''ячейки 3'' на 3
 |-
 | '''<code>>+</code>''' || приращение ''ячейки 4'' на 1
 |-
 | '''<code><<<<-</code>''' || декремент ''ячейки 0'' на 1
 |-
 | '''<code>]</code>''' || проверка, не равна ли ''ячейка 0'' нулю
 |-
 | colspan = 2 style = "text-align: center" | '''Вывод первого слова'''
 |-
 | '''<code>>++.</code>''' || в ''ячейке 1'' добавление 2 к 70 и вывод на печать ASCII-кода 72, т.е. буквы «''Н''».
 |-
 | '''<code>>+.</code>''' || в ''ячейке 2'' добавление 1 к 100 = 101, печать буквы «''e''»
 |-
 | '''<code>+++++++..</code>''' || в этой же ячейке добавление 7 к 101 = 108, печать «''l''» дважды
 |-
 | '''<code>+++.</code>''' || в этой же ячейке добавление 3 к 108 = 111, печать «''o''»
 |-
 | '''<code>>++.</code>''' || в ''ячейке 3'' добавление 2 к 30 = 32, печать пробела
 |-
 | colspan = 2 style = "text-align: center" | '''Вывод второго слова с повторным использованием ячеек'''
 |-
 | '''<code><<+++++++++++++++.</code>''' || в ''ячейке 1'' добавление 15 к 72 = 87, печать «''W''»
 |-
 | '''<code>>.</code>''' || в ''ячейке 2'' уже есть 111, сразу печать «''o''»
 |-
 | '''<code>+++.</code>''' || в этой же ячейке добавление 3 к 111 = 114, печать «''r''»
 |-
 | '''<code>------.</code>''' || в этой же ячейке вычитание 6 из 114 = 108, печать «''l''»
 |-
 | '''<code>--------.</code>''' || в этой же ячейке вычитание 8 из 108 = 100, печать «''d''»
 |-
 | '''<code>>+.</code>''' || в ''ячейке 3'' добавление 1 к 32 = 33, печать «''!''»
 |-
 | '''<code>>.</code>''' || в ''ячейке 4'' уже есть 10, сразу печать перевода строки
|}

== Интерпретаторы ==
Пример интерпретатора Brainfuck, написанный на языке [[Perl]]:

<source lang="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 ']';
      }
    --$_;
    }
  }
}
</source>

Пример интерпретатора на [[C++]]:
<source lang="cpp">
#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;
		}
	}
}
</source>

== Примечания ==
{{примечания}}

== Ссылки ==
{{Чистить ссылки|дата=2023-11-19}}
* [http://www.muppetlabs.com/~breadbox/bf Оригинальное описание на английском языке и ссылки на BF-ресурсы]
* [http://esolangs.org/wiki/Brainfuck Brainfuck] на «Esoteric Languages wiki»
* [http://rsdn.ru/article/philosophy/languages.xml Статья на rsdn.ru об эзотерических языках программирования]
* [https://web.archive.org/web/20031206060451/http://esoteric.sange.fi/brainfuck/ The Brainfuck Archive (утилиты)]

{{нет источников|дата=2008-12-26}}

[[Категория:Эзотерические языки программирования]]
[[Категория:Модели вычислений]]