Brainfuck: коли програмісту хочеться розважитися

Коли звичайний користувач хоче розважитися - він запускає улюблену гру. Коли ж програміст хоче розважитися - він починає писати всяку фігню. А якщо є час і натхнення, то вивчає нову, нікому не потрібну, мову програмування. Brainfuck є однією з найвідоміших, так званих, езотеричних мов програмування. Езотеричними називають мови, які не призначені для практичного застосування, це більше такий своєрідний гумор, засіб розважитися. Brainfuck був придуманий у 1993 році Урбаном Мюллером, також just for fun. Взагалі, назва мови повністю відображає її сутність. Отже, спробуємо дещо порозминати мозок.

Перш за все, встановимо інтерпретатор Brainfuck. Робиться це дуже просто:

sudo apt-get install bf

ОК, тепер займемося вивченням самої мови. Brainfuck використовує просту модель машини, яка складається з упорядкованого масиву комірок (по байту кожна, за замовчуванням масив ініціалізується нулями) і рухомого вказівника (при ініціалізації вказує на перший байт масиву), а також два потоки байтів - для вводу (input) і виводу (output, використовуються коди ASCII). Фактично, це модель машини Тьюрінга. Brainfuck включає всього вісім операторів, кожен з яких позначається одним символом.

> - перейти до наступної комірки
< - перейти до попередньої комірки
+ - збільшити значення комірки на 1
- - зменшити значення комірки на 1
. - вивести значення поточної комірки
, - ввести значення у поточну комірку
[ - якщо значення комірки нуль, то перейти до відповідної ]
] - якщо значення комірки не нуль, то повернутися до відповідної [

Не дивлячись на такий примітивізм, Brainfuck володіє тьюрінг-повнотою, а отже, теоретично, по своїм можливостям не поступається C, Pascal та ін. Звичайно, ніхто не буде писати на ньому повноцінні програми, але з точки зору теорії, на ньому дійсно можна написати, що завгодно.

Давайте й ми щось напишемо. Почнемо з класичного прикладу - виведення на екран фрази Hello World! Наша програма матиме наступний вигляд:

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

На перший погляд, нічого не зрозуміло. Тому давайте розглянемо нашу програму детальніше.

++++++++++        записуємо у нульову комірку значення 10,
                  це буде наш лічильник
[                 починаємо цикл і продовжуємо, доки у
                  нульовій комірці не з'явиться нуль
>+++++++>++++++++++>+++>+
                  послідовно додаємо 7, 10, 3 та 1 до
                  наступних комірок
<<<<-             повертаємося до нульової комірки і
                  зменшуємо її значення на 1
]                 доки у нульовій комірці не нуль,
                  продовжуємо цикл, оскільки він буде
                  повторюватися 10 разів, то у комірках
                  1-4 з'являться числа 70, 100, 30 та 10
>++.              переходимо у комірку 1 і збільшуємо
                  її значення на 2, що дасть 72, тобто
                  ASCII код літери H, потім виводимо
                  її на екран
>+.               виводимо 'e' (код 101)
+++++++.          виводимо 'l' (код 108)
.                 виводимо 'l' ще раз
+++.              виводимо 'o' (код 111)
>++.              виводимо пробіл (код 32)
<<+++++++++++++++.
                  виводимо 'W' (код 87)
>.                виводимо 'o' (код 111)
+++.              виводимо 'r' (код 114)
------.           виводимо 'l' (код 108)
--------.         виводимо 'd' (код 100)
>+.               виводимо '!' (код 33)
>.                переводимо рядок (код 10)

Щоб пересвідчитися у тому, що дана програма дійсно працює, просто збережіть її текст у файл test.bf і запустіть на виконання

bum@bum-desktop ~/Projects $ bf test.bf
Hello World!

Ваш мозок ще живий? ОК, давайте виведемо слово Ubuntu. Спочатку випишемо ASCII коди відповідних літер

U - 85
b - 98
u - 117
n - 110
t - 116

Давайте глянемо на число 85. Звичайно писати 85 плюсиків буде досить важко, та й легко помилитися. Набагато краще буде спробувати розбити його на два множники, тобто 5*17. У свою чергу, 17=5*3+2. Таким чином, перш за все спробуємо помножити 5 на 3. Код буде таким:

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

Тобто ми збільшуємо значення комірки №0 на 5 (а оскільки раніше там був 0, то таким чином просто присвоюємо це значення комірці), а значення комірки №1 збільшуємо на 3. Потім зменшуємо значення комірки №0 на одиницю і повторюємо цикл, до тих пір, доки у комірці №0 не з'явиться нуль. Тоді у комірці №1 буде число 15. Але після останнього проходу циклу, у нас активна комірка №0, тому зрушимо вказівник на один вправо (>). Тепер додамо число 2. Наш код зміниться.

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

Тепер у комірці №1 знаходиться число 17. Помножимо його на 5 використовуючи аналогічний метод. Не забуваємо в кінці пересунути вказівник на одну комірку праворуч (тобто на №2) і спробуємо вивести результат.

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

Якщо запустити цю програму, то вона виведете на екран літеру "U". Супер! Тепер нам залишилося вивести ще чотири літери. Наступна літера b має код 98. 98-85=13, отже просто 13 раз пишемо +.

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

Зараз наша програма виводить дві літери - "Ub". Щоб тепер вивести u нам потрібно додати ще 19. Тут можна дещо спробувати зоптимізувати, оскільки 19=5*4-1. У якості лічильника оберемо комірку №3, а додавати будемо у нашу робочу №2. Програма, що виводить "Ubu":

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

За рахунок вищенаведеної оптимізації, ми зекономили аж цілих 2 байти! :) Інші літери вивести не важко. Але наприкінці, нам ще непогано було б перевести курсор на новий рядок, для цього потрібно вивести символ з кодом 10. Остаточно, програма буде виглядати наступним чином:

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

Все. Не знаю, як ваш мозок, а мій вже почав плавитись, тому статтю на цьому закінчую. Більше інформації можна знайти на відповідній сторінці Вікіпедії.