Brainfuck

Z Wikipedii

Brainfuck to ezoteryczny język programowania stworzony przez Urbana Müllera około roku 1993. Nazywany też czasem Brainf*ck, Brainf***, lub po prostu BF.

Spis treści 1 Budowa języka 1.1 Instrukcje 2 Przykłady 2.1 Hello World! 2.2 Trywialne 2.2.1 Czyszczenie komórki 2.2.2 Prosta pętla 2.2.3 Poruszanie wskaźnikiem 2.2.4 Dodawanie 2.2.5 Wyrażenie warunkowe w pętli 2.2.6 Kopiowanie wartości z komórki 2.3 Nietrywialne 2.3.1 Dodawanie 2.3.2 Mnożenie 2.3.3 Dzielenie 3 Zobacz też 4 Linki zewnętrzne

[edytuj] Budowa języka

Celem Müllera było stworzenie języka z jak najmniejszą ilością instrukcji, oraz jak najmniejszego kompilatora. Oryginalny kompilator, napisany na Amigę ma rozmiar 240 bajtów.

Jak sugeruje nazwa, programowanie w tym języku jest dosyć trudne. Bez względu na to, w Brainfucku można zaimplementowac dowolny algorytm, ponieważ jest on zupełny w sensie Turinga.

Język opiera się 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.

[edytuj] 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 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.

[edytuj] Przykłady

[edytuj] 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

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

[edytuj] Trywialne

[edytuj] 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

[edytuj] 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:

,+[-.,+]

[edytuj] Poruszanie wskaźnikiem

>,[.>,]

Ciekawsza wersja poprzedniego programu, tym razem dodatkowo zapisujemy wejście do kolejnych komórek

[edytuj] 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

[edytuj] 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.

[edytuj] 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

[->+<]

Niestety, 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]

[edytuj] 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ą

[edytuj] Dodawanie

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

Program wczytuje dwie jednocyfrowe liczby i drukuje rezultat dodawania. Niestety, 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]

[edytuj] Mnożenie

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

Podobnie jak poprzednio, jednak tym razem mnożymy zamiast dodawać.

Pierwsza cyfrę przechowujemy w [0], drugą w [1]. Obie zmiejszamy 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

[edytuj] 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) tak długo jak (2) jest niezerowe
[>]>>>[<[>>>-<<<[-]]>>]<<] jeżeli dzielna jest zerem wyjdź z pętli
>>>+ dodaj jeden do ilorazu w (5)
<<[-<<+>>] kopiuj zapisany dzielnik z (3) do (2)
<<<] 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

[edytuj] Zobacz też

Lista podobnych języków:

• Doublefuck, odmiana Brainfucka z dwoma buforami pamięci.
• Brainfork
• BrainQuack, odmiana Brainfucka z możliwością przeciążania operatorów
• PATH, połączenie Brainfucka i Befunge.
• SNUSP, podobnie, lecz ze stosem wywołań.
• L33t
• L00P
• Ook!
• QUOTE
• Aura (język programowania)
• Moo
• ETA
• Befunge
• Whitespace
• Malbolge

[edytuj] Linki zewnętrzne

• Brainfuck w katalogu DMOZ