,[>.]<, czyli rzecz o bezlitosnym minimalizmie

Krótki wstęp do Brainfucka – trudnego, lecz intuicyjnego języka programowania, który odstrasza swoją składnią, ale można się z nią zaprzyjaźnić. 

Wstęp 

Zaczynając przygodę z kodowaniem wybieramy raczej “ludzkie” (o wysokim poziomie abstrakcji) języki programowania. Niezależnie czy jest to Python czy np. Scratch, w każdym z nich posługujemy się komendami zrozumiałymi przez człowieka. Zupełną tego odwrotność stanowią technologie niskopoziomowe (pod względem wspomnianej abstrakcji), które składają się z zestawów najprostszych możliwych instrukcji. 

Oprócz powyższej klasyfikacji, można również rozróżnić języki konwencjonalne i ezoteryczne. Te pierwsze są projektowane tak, aby umożliwić twórcom oprogramowania jak najlepsze jego przygotowanie, zarówno pod względem czytelności oraz złożoności kodu źródłowego czy szybkości wykonania końcowego programu. Ezoteryczne natomiast zupełnie się na tym nie skupiają, ich celem jest stworzenie warunków do ciekawej, umysłowej zabawy. Nie mają żadnego zastosowania w biznesie, a służą jedynie bezcelowemu intelektualnemu rozwojowi. 

W tym artykule omówię technologię łączącą mniej popularne elementy obu klasyfikacji, czyli język zarówno niskopoziomowy, jak i ezoteryczny.  

Historia powstania 

Brainfuck powstał prawie 30 lat temu z inicjatywy Urbana Müllera, celem poszerzenia zwartości portalu Aminet, który wcześniej wszedł w jego posiadanie. Celem twórcy BF było stworzenie języka z możliwie najmniejszym kompilatorem. Pierwsza jego wersja ważąca po skompilowaniu 296 bajty, została zaprojektowana w Assembly. Do programu została dołączona krótka specyfikacja technologii, można ją przeczytać tutaj

Budowa języka 

Składnia BF opiera się na ośmiu prostych instrukcjach: 

Znak  Działanie 
>  Zwiększ wskaźnik o 1 
<  Zmniejsz wskaźnik o 1 
+  Zwiększ wartość komórki pod wskaźnikiem o 1 
  Zmniejsz wartość komórki pod wskaźnikiem o 1 
.  Wypisz wartość komórki pod wskaźnikiem znakiem z tabeli ASCII 
,  Nadpisz wartość komórki pod wskaźnikiem zamieniając pierwszy znak z wejścia na liczbę z tabeli ASCII, po czym usuń ten znak z wejścia 
[  Rozpoczęcie pętli. Skocz do pasującego ], jeśli wartość pod wskaźnikiem to zero 
]  Zakończenie pętli. Skocz do pasującego [, jeśli wartość pod wskaźnikiem nie jest zerem 

Każdy inny znak za wyjątkiem wymienionych traktowany jest jako komentarz. 

W przedstawionej tabelce przedstawiłem takie rzeczy jak wskaźnik czy wartości pod nim. Projekt Brainfucka zakłada tworzenie za każdym uruchomieniem interpretera długiej, jednowymiarowej tablicy – ja ją będę nazywał taśmą

Do wykonania programu potrzebny nam jest także wskaźnik, który wskazywał będzie na dowolny element tablicy oraz przechowywał wyłącznie liczbę naturalną (z zerem włącznie). Indeks tablicy jest zawsze liczbą nieujemną, więc próba zmniejszenia wskaźnika do -1 zakończy program z błędem. 

Uwaga! Trzeba pamiętać, że każdy składnik taśmy to jeden bajt, co oznacza, że jego przedział wartości wynosi od 0 do 255. Jeśli przekroczymy limit z którejkolwiek strony, to wartość komórki przekręci się na początek (0 – 1 = 255) lub koniec zakresu (255 + 1 = 0). 

Do przyjmowania i wypisywania znaków Brainfuck wykorzystuje tablicę ASCII. 

Tablica znaków ASCII

Przykłady 

Jak można zauważyć, w samej budowie BF jest bardzo prosty. Mamy do dyspozycji wszystkie podstawowe operacje, dzięki czemu (zakładając nieograniczoną przestrzeń komputera) w Brainfucku można w skończonym czasie wykonać dowolny algorytm. W informatyce nazywamy to kompletnością Turinga, o której naprawdę warto poczytać. 

Każdy z poniższych przykładów możesz przetestować na stronie https://fatiherikli.github.io/brainfuck-visualizer/ wraz z wizualizacją taśmy i wskaźnika. 

Program 1.

Omówmy prosty program: +++++[-] 
Początkowy stan taśmy: [0][0][0][0][0][0]... 
Końcowy stan taśmy: [0][0][0][0][0][0]... 
–– 
Powyższe instrukcje zwiększą pięć razy pierwszy element taśmy (+++++), po czym zostanie wykonana pętla ([-]) zmniejszająca wartość pod wskaźnikiem. Pętla wykona się 5 razy z uwagi na wcześniej ustaloną wartość elementu. 

Program 2.

Inny program: >>>>++ 
Końcowy stan taśmy: [0][0][0][2][0][0]... 
–– 
Tutaj rozpoczynamy od zwiększenia wartości wskaźnika o 4 (przejścia do czwartej komórki). Później zwiększamy wartość o 2 (++). 

Program 3.

Przykładowy program wypisujący frazę “Hello World”: 

 +++++ +++++             zwiększ wartość komórki #0 na 10 (iterator pętli) 
[                       pętla. ustaw komórki od #1 do #4 na 70/100/30/10 
    > +++++ ++              dodaj 7 do #1 |7*10 = 70| 
    > +++++ +++++           dodaj 10 do #2 |10*10 = 100| 
    > +++                   dodaj 3 do #3 |3*10 = 30| 
    > +                     dodaj 1 do #4 |1*10 = 10| 
<<<< -                  wróć do pozycji iteratora (4-4=#0) i zmniejsz go 
] 
> ++ .                  przejdź do (0+1 = #1) wypisz 'H' (70+2 = 72) 
> + .                   przejdź do (1+1 = #2) wypisz 'e' (100+1 = 101) 
+++++ ++ .              wypisz 'l' (101+7 = 108) 
.                       wypisz 'l' 
+++ .                   wypisz 'o' (108+3 = 111) 
> ++ .                  przejdź do (2+1 = #3) wypisz ' ' (30+2 = 32) 
<< +++++ +++++ +++++ .  przejdź do (3-2 = #1) wypisz 'W' (72+15 = 87) 
> .                     przejdź do (1+1 = #2) wypisz 'o' 
+++ .                   wypisz 'r' (111+3 = 114) 
----- - .               wypisz 'l' (114-6 = 108) 
----- --- .             wypisz 'd' (108-8 = 100)  

Uwaga! Nie uruchomisz powyższego programu, ponieważ w komentarzach zawarte są znaki + i -. 
Poniżej skrócona wersja: 

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

Więcej przykładowych algorytmów znajdziesz na tej stronie: 
https://esolangs.org/wiki/Brainfuck_algorithms 

Podsumowanie 

Brainfuck jest językiem tak skrajnie prostym, że przez to niesamowicie trudnym. Wykonanie prostych algorytmów wydaje się w nim możliwe do napisania, ale wraz ze zwiększaniem złożoności problemów, przekonujemy się o wykładniczej specyfice jego trudności. To jest właśnie to co nazwałem “bezlitosnym minimalizmem” – systemem, który poprzez radykalny minimalizm staje się dla użytkownika zupełnym przeciwieństwem pierwotnie przyjętej idei. 

Źródła

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *