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

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

Общее описание языка

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

Язык Brainfuck можно описать с помощью эквивалентов языка Си :

Несмотря на внешнюю примитивность, 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 , досуммирование происходит перед печатанием, второе слово конструируется из остатков первого:

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

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

Интерпретатор 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. Отсутствие команды обозначается отс.

См. также

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

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

• Spoon
• LOLCODE
• Whitespace
• Feckfeck

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

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

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

Примечания

Ссылки

• — русское ЖЖ-сообщество любителей эзотерических языков
• на «Esoteric Languages wiki»
• в каталоге ссылок Curlie (dmoz)

Реализации языка

• ( C++ )
• (рус.) . procool.ru . Архивировано из 1 декабря 2012 года.
• , оптимизирующий интерпретатор и транслятор в PHP (написан на PHP)
• , интерпретатор для BF и его диалектов (Java)
• (Java)
• (рус.) . brainfuck.progopedia.ru . Архивировано из 5 ноября 2012 года.
• , оптимизирующий интерпретатор ( JavaScript )
• (Си и Python )
• (Python)
• , Brainfuck и Ook! интерпретатор
• , интерпретатор ( язык Си )
• , open-source интерпретатор (язык Си)
• , транслятор с Brainfuck на Cи
• (англ.) . beco.cc . Архивировано из 7 мая 2017 года. , компилятор ( враппер GCC ) и транслятор в Си
• , интерпретатор для iPhone ( Objective-C )

IDE

• , IDE совместимая с Windows 7
• , IDE для Windows (также запускается под WINE )

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