Brainfuck

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

Brainfuck^[a] – ezoteryczny język programowania stworzony w 1993 roku przez Urbana Müllera^[1], 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^[2]. Oryginalny kompilator, napisany na Amigę, ma rozmiar 240 bajtów^[2].

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^[2].

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

Uwagi

↑ Często można spotkać się z eufemistyczną pisownią brainf*ck, brainf*** lub zwykłym skrótem BF

Przypisy

↑ Brandee Easter. Fully Human, Fully Machine: Rhetorics of Digital Disembodiment in Programming. „Rhetoric Review”. 39 (2), s. 202–215, 2020-04-02. DOI: 10.1080/07350198.2020.1727096. ISSN 0735-0198.
↑ ^a ^b ^c The Brainfuck Programming Language. [dostęp 2020-11-22]. (ang.).

Linki zewnętrzne

Brainfuck w archiwum katalogu DMOZ

[uwaga1-1] Często można spotkać się z eufemistyczną pisownią brainf*ck, brainf*** lub zwykłym skrótem BF

[Easter-2] Brandee Easter. Fully Human, Fully Machine: Rhetorics of Digital Disembodiment in Programming. „Rhetoric Review”. 39 (2), s. 202–215, 2020-04-02. DOI: 10.1080/07350198.2020.1727096. ISSN 0735-0198.

[bf-3] The Brainfuck Programming Language. [dostęp 2020-11-22]. (ang.).

[a]

[1]

[2]