К началу

7 Ответы на частые вопросы

7.1 Что такое эзотерический язык программирования?

Разработка таких языков производится в качестве эксперимента, реализации нестандартных подходов к разработке ПО, ну или просто для смеха. Для решения серьезных задач эзотерические языки, как правило, не подходят.

7.1.1 Является ли таковым Brainfuck?

Разумеется. Вряд ли вы когда-либо в практических целях станете использовать программу на Brainfuck. Даже при создании простых алгоритмов, проще использовать С, куда легко портировать команды языка. Сложностей при разработке добавляет плохая читаемость исходного кода, который неминуемо превращается в кашу при попытке написать что-либо полезное, а также ограниченные возможности ввода-вывода.

7.2 Это самый маленький язык программирования?

7.2.1 И да...

Взглянув на набор команд кажется, что больше из языка при сохранении функциональности вырезать ничего нельзя. Мы имеем
  Присвоения: + и -
  Ввод-вывод: , и .
  Цикл и ветвление: [ и ]
  Перемещение по памяти < и >
Мы можем представить себе и более компактные языки, часто являющиеся наследниками Brainfuck, например
  с ограниченной функциональностью (к примеру, входные данные уже должны содержаться в памяти);
  с урезанным набором значений (Bitfuck работает с битами вместо байтов)
Все это делает программу еще более громоздкой.

7.2.2 И нет...

Вдохновившись Brainfuck энтузиасты делают относительно успешные попытки создания языков с еще меньшим набором команд.
Boolfuck использует однобитные ячейки памяти, что позволяет сократить команды присвоения с двух до одной - достаточно только инверсии бита (команда *).
Аналогичный ему Bitfuck также состоит из семи команд, однако, четыре из них записываются двумя символами. Всего для записи программы требуется 4 символа, чем авторы и гордятся.
Можно также избавиться от ввода-вывода, объединить по две команды в одну и оставить всего четыре реальных команды:
  [ начать цикл
  ] завершить цикл
  ( передвинуться влево и инвертировать бит
  > передвинуться вправо

Для дальнейшего упрощения предлагается не разделять данные и инструкции в памяти. В абстрактной машине с архитектурой URISC (Ultimate Reduced Instruction Set Computer) используется одна команда, чье поведение определяется состоянием битов под указателем. Вариантом такой команды является BitBitJump. Инструкция работает с тремя адресами - копирует бит по первому адресу во второй адрес и перемещает указатель к третьему адресу, который становится “первым” и так далее.

7.3 Как выучить Brainfuck?

Также, как и любой другой язык - чтением документации (благо, ее можно целиком усвоить за считанные минуты), примеров и программ, и практикуясь самостоятельно.

Можно прислушаться к экспертному мнению

[Оригинал]
[Текущее состояние перевода]

Final version 2012-08-11
Начало перевода 2014-07-18

Дословного перевода у меня не получилось, кое-где имеются отступления от текста. Также потребовалось изменить ряд примеров и исправить ошибки в них.

Содержание:
Введение. История создания языка.
Команды. Абстрактная модель.
Пример программы - ввод-вывод.
Hello World!
Простые конструкции. Арифметика.
Условный переход.
Сравнение.
Ответы на частые вопросы.

Мой интерпретатор Brainfuck на js
Я намеренно не стал добавлять выход из цикла по инструкции "]" при нулевой текущей ячейке, по-моему, эта проверка лишняя, ведь мы все равно вывалимся из цикла в его начале.

К началу

6.7 If

В Brainfuck отсутствует условный оператор if, однако, для ветвления можно использовать особенность цикла [ ] и запускать его только один раз. Примеры в основном основаны на http://esolangs.org/wiki/brainfuck_algorithms

6.7.1 If (x != 0)

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

Если значение #0 не равно нулю, увеличить #0, перейти на #1

6.7.2 If (x != 1)

Для сравнения с числом необходимо вспомнить пример с поиском искомого значения в цикле. Перед началом цикла отнимем данное число из проверяемого, а затем восстановим его значение.

К началу

6 Простые конструкции

6.1 Поиск нуля

Алгоритм нахождения первой нулевой ячейки справа от текущей:
6.1.1 Описание

Как было показано ранее, цикл [ ] выполняется до тех пор, пока значение текущей ячейки при начале цикла не равно нулю. При выполнении команды > мы перемещяемся вправо до тех пор, пока не достигнем ячейки, содержащей ноль.

6.1.2 Поиск других значений

Аналогично можно искать что-либо еще:

1: -[+>-]+
2: --[++>--]++

6.1.2.1 Описание
До начала цикла мы уменьшаем значение текущей ячейки на искомое число. Если мы достигли нуля, считаем, что нашли необходимую ячейку, цикл пропускается и мы восстанавливаем значение текущей ячейки. Иначе, уже в цикле, восстанавливаем значение, продвигаемся вправо, уменьшаем значение и т.д.
Подобной конструкцией очень легко запустить бесконечный цикл, если искомого значения в памяти не найдется.

6.2  Перемещение содержимого одной ячейки в другую

Поскольку ячейки памяти в Brainfuck имеют непосредственное влияние на алгоритм, перемещение значения в другую ячейку может оказаться полезным. Так можно просто размножить значение, получить сумму текущей ячейки и соседней, а также управлять поведением цикла [ ].
Следующая программа переместит значение текущей ячейки в последующую:
1. Вычтем единицу из значения первой ячейки
2. Переместимся ко второй
3. Добавим единицу
4. Вернемся к первой ячейке
Цикл будет продолжаться, пока значение первой ячейки не станет нулем.
Путем небольших изменений можно изменить направление переноса или разнести значение по нескольким ячейкам.

6.3  Сложение

Описанный выше процесс перемещения деструктивен, поскольку он обнуляет значение первой ячейки. Чтобы его восстановить, сохраним даное значение во временной ячейке памяти, а затем разнесем его по первым двум.
Следующая программа добавит значение текущей ячейки к последующей, используя третью ячейку для временного хранения:
Сперва переместим значение первой ячейки в третью. Затем значение третьей ячейки в первую и вторую.

6.4 Копирование

Копирование значения одной ячейки в другую можно разложить на две операции - очистку целевой ячейки, присвоение ей значения исходной ячейки:
6.5 Вычитание

Вычитание, как можно было предположить, от сложения отличается только знаком:
6.6 Умножение

Умножение - это повторяющееся сложение, а значит, можно воспользоваться приобретенным опытом. Поскольку первый множитель будет уменьшаться при каждом проходе, необходимо сохранить его значение во временной ячейке.
Умножим число 2 в ячейке #0 на 3 в ячейке #1 (пример взят отсюда)

Далее - Условный переход

К началу

5.2 Hello World

Из множества книг по языкам программирования вам хорошо известна программа “Hello World”. Как правило, это простейшая программа, производящая видимый результат - вывод символов на экран. Однако, для Brainfuck это задача не из легких, т.к. для вывода каждого символа мы должны присвоить его ASCII-код текущей ячейке используя только имеющиеся операторы.
В отступление от текста, реализуем задачу в простейшем виде, используя единственную ячейку памяти, меняя ее значение и выводя результат:


Можно удовлетвориться данным вариантом, однако, вспомним, что в языке существуют циклы, позволяющие сократить количество кода в однообразных операциях. Ниже приведен один из оптимизированных вариантов той же самой программы.


Код отформатирован для удобства чтения и снабжен комментариями. При выполнении переносы и лишние символы будут проигнорированы. Итоговая программа представляет собой строку:
5.3  Описание программы Hello World

Разберем отформатированную команду построчно.
Первые 7 строк подготавливают память, присваивая соседним ячейкам значения, близкие к кодам символов выводимой фразы.
Присвоим ячейке #0 значение “10”, увеличивая ее на единицу 10 раз.
Начало цикла. Значение текущей ячейки - 10, поэтому содержимое цикла будет выполнено
Каждую итерацию цикла производится ряд действий над ячейками:
  #1 увеличивается на 7
  #2 увеличивается на 10
  #3 увеличивается на 3
  #4 увеличивается на 1
  #0 уменьшается на 1
Перед каждой итерацией мы возвращаемся в ячейку #0, значение которой последовательно изменяется с 10 до 0, поэтому цикл будет выполнен 10 раз
В результате в ячейках ##1-4 содержатся значения: 70, 100, 30, 10. Теперь нам потребуется гораздо меньше действий, чем в первом примере, для получения кодов символов “Hello World!”

5.4 Упражнения

1.     Измените пример с вводом-выводом так, чтобы переданные значения не перезаписывали предыдущие, а сохранялись в памяти
2.     Измените программу Hello World, чтобы вывести на экран ваше имя

Далее - Простые конструкции

К началу

5 Первые программы на Brainfuck

5.1 Чтение и запись

Чтение символов с клавиатуры и вывод их на экран, пока не будет введено нулевое значение:
Результатом кода:
будет то же самое, однако, выход производится по коду 255. В некоторых средах исполнения невозможно передать на вход ASCII-код 000.

5.1.1 Описание

Программа состоит из пяти символов: , [ . , ]
Запятая считывает ASCII-код символа с клавиатуры.
Открывающая скобка является началом цикла While - если значение текущей ячейки больше нуля, выполняются команды внутри скобок. Если же введен ноль, программа продолжится за закрывающей скобкой и, поскольку, инструкций больше нет, завершится.
Точка выводит значение текущей ячейки на экран. Заметьте, что первый символ мы ввели за пределами цикла, иначе значение текущей ячейки было бы равно нулю и программа бы ничего не напечатала.
Снова запятая - ввод символа пользователем.
Закрывающая скобка завершает цикл While, перемещаемся к началу цикла.

Обратите внимание на порядок операций внутри цикла - мы сперва выводим значение, а затем считываем. Этим мы предотвращаем выход из цикла - текущая ячейка не должна быть пустой.

Далее - Hello World

К началу

3 Основы языка: 8 команд Brainfuck

Язык состоит всего из восьми перечисленных ниже команд.
3.1 Программирование на Brainfuck

Программа на Brainfuck может представлять собой последовательность приведеных команд, перемешанных с любыми другими символами, игнорируемыми при компиляции. За исключением цикла [ ], команды выполняются последовательно, друг за другом. После выполнения последней команды программа завершается.

3.2 Упражнения

  1. Приведите примеры команд, аналогичных приведенным, в знакомых вам языках
  2. Изучите работу цикла [ ] применительно к различным значениям текущей ячейки памяти

4 Модель языка Brainfuck

Абстрактная машина, исполняющая Brainfuck содержит:
  программу с указателем текущей инструкции
  одномерный массив из 30000 однобайтных ячеек, заполненный нулями
  перемещаемый указатель данных, изначально находящийся в крайней левой ячейке
  потоки ввода-вывода, обычно соединенные с клавиатурой и монитором, и использующие кодировку ASCII.

В отличие от других небольших языков, память с данными отделена от памяти инструкций, и содержимое ячеек с данными не может оказать влияние на ячейки программы.

Далее - Первые программы на Brainfuck

К началу

1 Введение

Представьте себе одномерную полосу с данными, например, магнитную ленту (классические машины Тьюринга работают с лентой) или компьютерную память. Для обозначения текущей ячейки используется указатель данных (магнитная головка). Каждая такая ячейка хранит один байт (значение от 0 до 255), слово (16 бит) или 24 бита данных. Автор предпочитает называть указатель курсором, однако, я своевольно оставлю его привычное название (прим. пер.)

Brainfuck - это минималистичный язык программирования, работающий с такой “лентой” в памяти, и состоящий лишь из восьми операндов. Несмотря на это он является Тьюринг-полным, что теоретически позволяет производить любые вычисления как, например, в языках Basic или C. Автор составил данное руководство из найденных им материалов по Brainfuck. Большинство текстов и кода позаимствовано у разных людей с указанием источников.

1.1.1 Авторские права

При цитировании были сохранены лицензии на распространение использованных текстов. Данный документ опубликован под лицензией GFDL.

2 Краткая история Brainfuck[wikipedia]

Исключая две команды ввода-вывода, Brainfuck является полным преемником языка P′′, созданного Коррадо Бомом  в 1964 году. Он также использовал шесть символов, эквивалентных соответствующим командам Brainfuck: +, -, <, >, [ и ]. Бом описал ряд программ, реализующих основные математические функции, поэтому, формально, первые программы на Brainfuck были написаны Бомом на бумаге в 1964 году, и уже тогда была доказана полнота языка по Тьюрингу.

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

Далее: Основы языка: 8 команд Brainfuck