пʼятниця, 16 січня 2009 р.

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. Остаточно, програма буде виглядати наступним чином:
+++++[>+++<-]>++[>+++++<-]>.
+++++++++++++.>+++++[<++++>-]<-.
-------.++++++.+.>++++++++++.

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

1 коментар:

  1. Тепер, для того, щоб прославитись більше, чим той Мюллєр, треба написати конвертор з скажімо c++ в брейнфак...

    ВідповістиВидалити