Brainfuck to ezoteryczny język programowania zbudowany przez Urbana Müllera około roku 1993. Nazywany też czasem Brainf*ck, Brainf*** albo po prostu BF.
Budowa języka
Celem Müllera było stworzenie języka z jak najmniejszą liczbą instrukcji oraz jak najmniejszego kompilatora. Oryginalny kompilator, napisany na Amigę ma rozmiar 240 bajtów.
Jak sugeruje nazwa, programowanie w tym języku jest trudne. Bez względu na to w Brainfucku da się zaimplementować dowolny algorytm, albowiem język ten jest zupełny w sensie Maszyny Turinga.
Język ma za podstawę o prosty model maszyny, składający się, oprócz programu, z tablicy bajtów (zazwyczaj 30000) zainicjalizowanych zerami oraz wskaźnika do tej tablicy, zainicjalizowanego tak, aby wskazywał na jej pierwszy element.
Instrukcje
Brainfuck zawiera 8 następujących jednoznakowych instrukcji:
| Znak |
Znaczenie |
Odpowiednik w C |
> |
zwiększa wskaźnik o 1 |
++p |
< |
zmniejsza wskaźnik o 1 |
--p |
+ |
zwiększa o 1 w bieżącej pozycji |
++(*p) |
- |
zmniejsza o 1 w bieżącej pozycji |
--(*p) |
. |
wyświetla znak w bieżącej pozycji (ASCII) |
putchar(*p) |
, |
pobiera znak oraz wstawia go w bieżącej pozycji (ASCII) |
*p=getchar() |
|
skacze bezpośrednio za odpowiadający mu |
while(*p){ |
|
skacze do odpowiadającego mu |
} |
Przy czym "bieżąca pozycja" oznacza element w tablicy wskazywany przez wskaźnik (w odpowiednikach w C p oznacza wskaźnik!).
Wszystkie inne znaki są ignorowane, co jest przydatne przy pisaniu komentarzy.
Przykłady
Hello World!
Następujący program drukuje napis "Hello World!" na ekranie oraz przechodzi do nowej linii:
++++++++++
[
>+++++++>++++++++++>+++>+<<<<-
] Na początek ustawiamy parę przydatnych później wartości
>++. drukuje 'H'
>+. drukuje 'e'
+++++++. drukuje 'l'
. drukuje 'l'
+++. drukuje 'o'
>++. spacja
<<+++++++++++++++. drukuje 'W'
>. drukuje 'o'
+++. drukuje 'r'
------. drukuje 'l'
--------. drukuje 'd'
>+. drukuje '!'
>. nowa linia
Dla względów czytelności kod programu stał się podzielony na parę linii oraz zostały dodane komentarze. Brainfuck traktuje wszystkie znaki poza +-<>[],. jako komentarz. Równie dobrze powyższy program da się by zapisać jako:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.
Trywialne
Czyszczenie komórki
Prosty program, który ustawia wartość w aktualnej komórce na 0. Mówiąc ściślej, tak długo dekrementuje wartość w aktualnej komórce, jak długo jest ona większa od 0.
Prosta pętla
Pętla, która pobiera z wejścia kolejne znaki oraz drukuje je na ekranie tak długo, aż wczytany zostanie znak końca pliku (EOF). W pewnych implementacjach znak EOF ma wartość -1, wtedy odpowiadający program wygląda następująco:
Poruszanie wskaźnikiem
Ciekawsza wersja poprzedniego programu, tym razem dodatkowo zapisujemy wejście do kolejnych komórek.
Dodawanie
Powyższy kod dodaje wartość w aktualnej komórce do następnej komórki. Warto zauważyć, że zeruje to wartość w aktualnej komórce.
Wyrażenie warunkowe w pętli
,----------[----------------------.,----------]
Powyższy program pobiera wejście (małe litery alfabetu angielskiego) zakończone znakiem nowej linii (czyli wciśnięciem entera) oraz drukuje je, wcześniej zwiększając litery na wielkie.
Na początku wczytujemy pierwszy znak oraz odejmujemy od niego 10 (wartość znaku liczona jest w kodzie ASCII, znak nowej linii ma wartość ASCII 10). Gdyby wczytano znak nowej linii program zakończyłby się, w innym wypadku odejmujemy od niego 22 (razem z poprzednimi 10 odjęliśmy już 32, czyli różnicę pomiędzy odpowiednimi małymi oraz wielkimi literami), drukujemy na ekranie, po czym znowu wczytujemy znak, odejmujemy 10 oraz wracamy do początku pętli.
Kopiowanie wartości z komórki
(Jako że przykłady robią się coraz bardziej skomplikowane przyjmijmy dla ułatwienia, że [0], [1], [2] oraz tak dalej odnoszą się do kolejnych komórek)
Powiedzmy, że chcemy skopiować wartość z [0] do [1]. Najprostszym sposobem jest intuicyjne:
Niestety, takie wywołanie ustawi wartość w [0] na 0. Aby odzyskać początkową wartość [0] możemy przekopiować [0] do [1] oraz [2] równocześnie, a następnie kopiując wartość z [2] do [0]. Program realizujący to zadanie wygląda tak:
[->+>+<<] kopiujemy z (0) do (1) oraz (2)
>>[-<<+>>]<< kopiujemy z (2) do (0)
Nietrywialne
Poniżej widać proste implementacje podstawowych operacji arytmetycznych. Są one bardzo uproszczone, tzn. wejściem są dwie cyfry, także wynik musi być cyfrą.
Dodawanie
,>++++++[<-------->-],[<+>-]<.
Program wczytuje dwie jednocyfrowe liczby oraz drukuje rezultat dodawania. Niestety, program zadziała poprawnie tylko wtedy, kiedy rezultat jest cyfrą.
Wczytujemy do [0] pierwszą cyfrę oraz odejmujemy od niej 48 (kody ASCII dla cyfr 0-9 to 48-57). Odejmowanie to jest zrobione za pomocą prostej pętli: najpierw wstawiamy 6 do [1], a następnie tak długo, jak [1] jest różna od zera odejmujemy 8 od [0], oraz w końcu odejmujemy 1 od [1]. Następnie wczytujemy drugą cyfrę do [1]. Następna pętla [<+>-] dodaje drugą liczbę do pierwszej oraz zeruje [1]. Na końcu drukujemy wartość z [0].
Mnożenie
,>,>++++++++[<------<------>>-]
<<[>[>+>+<<-]>>[<<+>>-]<<<-]
>>>++++++[<++++++++>-]<.
Podobnie jak poprzednio, jednak tym razem mnożymy zamiast dodawać.
Pierwszą cyfrę przechowujemy w [0], drugą w [1]. Obie zmniejszamy o 48.
Tutaj zaczyna się pętla główna programu. Działamy wedle zasady: odejmij 1 od [0] po czym dodaj wartość z [1] do [2].
Na końcu dodajemy 48 do [2] oraz drukujemy rezultat na ekranie.
Dzielenie
,>,>++++++[-<--------<-------->>] przechowuje dwie cyfry w (0) oraz (1) od obu odejmujemy 48
<<[ powtarzaj dopóki dzielna jest niezerowa
>[->+>+<<] kopiuj dzielnik z (1) do (2) oraz (3) (1) się zeruje
>[-<<- odejmujemy 1 od dzielnej (0) oraz dzielnika (2) dopóki (2) nie jest 0
[>]>>>[<[>>>-<<<[-]]>>]<<] jeżeli dzielna jest zerem wyjdź z pętli
>>>+ dodaj jeden do ilorazu w (5)
<<[-<<+>>] kopiuj zapisany dzielnik z (3) do (1)
<<<] przesuń wskaźnik na (0) oraz powtórz pętlę
>[-]>>>>[-<<<<<+>>>>>] kopiuj iloraz z (5) do (0)
<<<<++++++[-<++++++++>]<. dodaj 48 oraz drukuj wynik
Po wczytaniu dwóch cyfr powyższy program oblicza ich iloraz (ignorując resztę) oraz drukuje go na ekranie.
Sprawdź też
Lista podobnych języków:
Linki zewnętrzne