Brainfuck

Материал из Википедии — свободной энциклопедии

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

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

8 команд языка Brainfuck:
	>	перейти к следующей ячейке
	<	перейти к предыдущей ячейке
	+	увеличить значение в текущей ячейке на 1
	-	уменьшить значение в текущей ячейке на 1
	.	напечатать значение из текущей ячейки
	,	ввести извне значение и сохранить в текущей ячейке
	[	если значение текущей ячейки нуль, перейти вперёд по тексту программы до ] с учётом вложенности
	]	если значение текущей ячейки не нуль, перейти назад по тексту программы до [ с учётом вложенности

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

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

Шуточный отладочный стенд программиста на brainfuck'е

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

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

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

[править] Программирование на языке Brainfuck

Каждый, начинающий программировать на Brainfuck, немедленно сталкивается со следующими проблемами:

отсутствие операции копирования значения
отсутствие промежуточной (аккумуляторной) памяти
отсутствие условных операторов в их привычном виде
отсутствие привычной арифметики, операций умножения и деления

Эти проблемы могут быть решены.

 Обозначим @(k) сдвиг на k ячеек вправо, если k>0, и влево, если k<0
 Соответственно, @(k) = >…_{k раз}…> либо <…_{-k раз}…<  

 zero(): обнуление текущей ячейки:
   [-]

 add(k): прибавление значения ячейки n (текущей) к значению ячейки n+k:
    [ — @(k)  + @(-k)  ]
 при этом значение ячейки n теряется (обнуляется).

 copy(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) copy (-k-t)
   =
   @(k) [-] @(t) [-] @(-k-t) [ — @(k) + @(t) + @(-k-t) ] @(k+t) [ — @(-k-t) + @(k+t) ]