Brainfuck

Brainfuck

Pojawienie się	wrzesień 1993
Paradygmat	ezoteryczny, imperatywny, strukturalny
Twórca	Urban Müller
Platforma sprzętowa	wieloplatformowy
Strona internetowa

Brainfuck – ezoteryczny język programowania stworzony w 1993 roku przez Urbana Müllera, znany ze swojego skrajnego minimalizmu. Język ten składa się z zaledwie ośmiu prostych komend oraz wskaźnika instrukcji. Pomimo tego, że jest on zupełny w sensie maszyny Turinga, nie został zaprojektowany do praktycznego użycia, a do zachęcania programistów do pisania prostych programów.

Nazwa języka brainfuck jest angielskim złożeniem składającym się z wyrazów brain (mózg) oraz fuck (pieprzyć) co na polski można tłumaczyć jako „mózgojeb”.

Budowa języka

Celem Müllera było stworzenie 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 można zaimplementować dowolny algorytm, ponieważ język ten jest zupełny w sensie maszyny Turinga.

Język opiera się na prostym modelu maszyny, składającym się, oprócz programu, z tablicy bajtów (zazwyczaj 30000) zainicjowanych zerami oraz wskaźnika do tej tablicy, zainicjowanego tak, aby wskazywał na jej pierwszy element.

Instrukcje

Brainfuck zawiera 8 następujących jednoznakowych instrukcji:

Znak	Znaczenie	Odpowiednik w C
(Rozpoczęcie programu)	inicjacja tablicy bajtów i wskaźnika do jej pierwszego elementu	char array[30000] = {0}; char *p=array;
>	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 i wstawia go w bieżącej pozycji (ASCII)	*p=getchar();
[	skacze bezpośrednio za odpowiadający mu ], jeśli w bieżącej pozycji znajduje się 0	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 i przechodzi do nowej linii:

++++++++++
[
>+++++++>++++++++++>+++>+<<<<-
] Na początek ustawiamy kilka 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 został podzielony na kilka linii i zostały dodane komentarze. Brainfuck traktuje wszystkie znaki poza +-<>[],. jako komentarz. Równie dobrze powyższy program można 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 i drukuje je na ekranie tak długo, aż wczytany zostanie znak końca pliku (EOF). W niektórych 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) i drukuje je, wcześniej zwiększając litery na wielkie.

Na początku wczytujemy pierwszy znak i 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ę między odpowiednimi małymi i wielkimi literami), drukujemy na ekranie, po czym znowu wczytujemy znak, odejmujemy 10 i 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] i tak dalej odnoszą się do kolejnych komórek)

Powiedzmy, że chcemy skopiować wartość z [0] do [1]. Najprostszym sposobem jest intuicyjne:

[->+<]

Takie wywołanie ustawi wartość w [0] na 0. Aby odzyskać początkową wartość [0], możemy przekopiować [0] do [1] i [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) i (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 i drukuje rezultat dodawania. Program zadziała poprawnie tylko wtedy, gdy rezultat jest cyfrą.

43

7

Wczytujemy do [0] pierwszą cyfrę i 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], i w końcu odejmujemy 1 od [1]. Następnie wczytujemy drugą cyfrę do [1]. Następna pętla [<+>-] dodaje drugą liczbę do pierwszej i 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 według zasady: odejmij 1 od [0], po czym dodaj wartość z [1] do [2].

Na końcu dodajemy 48 do [2] i drukujemy rezultat na ekranie.

Dzielenie

,>,>++++++[-<--------<-------->>] przechowuje dwie cyfry w (0) i (1) od obu odejmujemy 48
<<[                               powtarzaj dopóki dzielna jest niezerowa
>[->+>+<<]                        kopiuj dzielnik z (1) do (2) i (3) (1) się zeruje
>[-<<-                            odejmujemy 1 od dzielnej (0) i 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) i powtórz pętlę
>[-]>>>>[-<<<<<+>>>>>]            kopiuj iloraz z (5) do (0)
<<<<++++++[-<++++++++>]<.         dodaj 48 i drukuj wynik

Po wczytaniu dwóch cyfr powyższy program oblicza ich iloraz (ignorując resztę) i drukuje go na ekranie.

Zobacz też

• Brainfork, odmiana Brainfucka z wielowątkowością
• Befunge
• Whitespace
• Malbolge

Linki zewnętrzne

• Brainfuck w archiwum katalogu DMOZ