Hello, Brainfuck!

Brainfuck — Тьюринг полный язык, то есть на нем можно написать любую программу, которую вообще можно написать :) А напишем мы «Hello World», вернее несколько ;)

Введение

Brainfuck состоит всего лишь из 8 команд:

• > — переход к следующей ячейке памяти
• < — переход к предыдущей ячейке памяти
• + — увеличение значения в текущей ячейке памяти
• — — уменьшение значения в текущей ячейке памяти
• [ — если значение текущей ячейки нуль, перейти вперёд по тексту программы на ячейку, следующую за соответствующей ] (с учётом вложенности)
• ] — если значение текущей ячейки не нуль, перейти назад по тексту программы на ячейку, следующую за соответствующей [ (с учётом вложенности)
• . — вывод значения текущей ячейки
• , — ввод значения и сохранение в текущей ячейке

Интепретаторы

Для исполнения программ, написанных на Brainfuck, можно использовать:

• bolk.exler.ru/files/bf
• bfrun.berlios.de
• esco.sourceforge.net
• brainfuck.progopedia.ru

Hello, Brainfuck!

Давайте напишем свою первую программу на Brainfuck, которая будет выводить текст “Hello World!”. Алгоритм прост:
1. Увеличиваем значение в ячейке до тех пор, пока оно не будет равно нужному символу
2. Выводим значение в ячейке (наш символ)
3. Переходим к следующей ячейке
4. Повторяем, пока все символы не будут выведены

Результат:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++.>++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++.>+++++++++++++++++++++++++++++++++.

Реализуем алгоритм и на php — скрипт будет генерировать исходный код на Brainfuck, который выводит нужный текст:

$text = “Hello, world!”;
$length = strlen($text);
for ($i=0;$i<$length;$i++){
$curr = ord($text[$i]);
for ($j=1;$j<=$curr;$j++){
echo "+";
if ($j == $curr & $i != $length-1){
echo ".>";
}elseif ($j == $curr){
echo ".";
}
}

“Hello World!” вышел довольно таки большим по размеру, попробуем его оптимизировать. Необязательно каждый раз переходить в новую ячейку и начинать «путь» к нужному символу с нуля — мы можем использовать текущее значение ячейки. Новый алгоритм:
1. Увеличиваем значение в ячейке до тех пор, пока оно не будет равно нужному символу
2. Выводим значение в ячейке (наш символ)
3. Если следующий нужный символ больше текущего, то увеличиваем значение в ячейке, если меньше – уменьшаем, пока не получим нужное
4. Выводим значение в ячейке (наш символ)
5. Повторяем, начиная с п. 3, пока все символы не будут вывдены

Результат:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++
+++++++++++++++++++++.+++++++..+++.----------------------------------------------
---------------------------------.+++++++++++++++++++++++++++++++++++++++++++++++
++++++++.++++++++++++++++++++++++.+++.------.--------.---------------------------
----------------------------------------.

Уже меньше :) Вот код на php, генерирующий подобный исходник:

$text = “Hello, world!”;
$length = strlen($text);
$curr = 0;
for ($i=0;$i<$length;$i++){
$delta = ord($text[$i])-$curr;
$curr = ord($text[$i]);
if ($delta<0){
$op = "-";
$delta = abs($delta);
}else{
$op = "+";
}
for ($j=1;$j<=$delta;$j++){
echo $op;
}
echo ".";
}

Можно ли еще оптимизировать получившийся код на Brainfuck? Можно! Теперь мы опять будем использовать несколько ячеек, но реализуем и используем умножение. А помогут в этом ранее неиспользованные нами команды [ и ]. Умножение — с помощью суммы, 5*10=10+10+10+10+10. Тоесть, нам надо повторить прибавление 10 к ячейке 5 раз. Алгоритм программы:
1. Увеличиваем значение в ячейке до тех пор, пока оно не будет равно 10 – счетчик для цикла, множитель
2. Цикл начинается [
3. Увеличиваем значение в ячейке до тех пор, пока оно не будет равно n – результату целочисленного деления кода нужного символа на 10
4. Переходим к следующей ячейке
5. Повторяем п.3-4 для всех символов
6. Уменьшаем счетчик цикла (первую ячейку)
7. Цикл окончен ]
8. Переходим к следующей после счетчика ячейке
9. Прибавляем к ячейке остаток целочисленного деления кода нужного символа на 10 (для «H» в ячейке у нас будет 70, надо прибавить 2 = 72 % 10. Тоесть в итоге получим «H»=(72 / 10)+(72 % 10))
11. Выводим значение в ячейке (наш символ) и переходим к следующей ячейке
12. Повторяем п.9-11 для всех символов

Результат:

++++++++++[>+++++++>++++++++++>++++++++++>++++++++++>+++++++++++>+++>++++++++>+++
++++++++>+++++++++++>++++++++++>++++++++++>+++<<<<<<<<<<<< — ]>++.>+.>++++++++.>++++++++.>+.>++.>+++++++.>+.>++++.>++++++++.>.>+++.

Вуаля! Код php-генератора:

$text = “Hello, world!”;
$length = strlen($text);
echo "++++++++++[";
for ($i=0;$i<$length;$i++){
echo ">";
$ops = floor(ord($text[$i])/10);
for ($j=1;$j<=$ops;$j++){
echo "+";
}
}
for ($i=0;$i<$length;$i++){
echo "<";
}
echo "-]";
for ($i=0;$i<$length;$i++){
echo ">";
$ops = ord($text[$i]) % 10;
for ($j=1;$j<=$ops;$j++){
echo "+";
}
echo ".";
}

Итог

Вот такой вот интересный и замечательный язык Brainfuck :) В заключение, приведу генератор, написанный мной на самом Brainfuck. Эта програма считывает введенный текст и генерирует код на Brainfuck (оптимизированный), который этот текст выведет.

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