Brainfuck

Brainfuck (někdy je také eufemisticky nazýván Brainf*ck nebo dokonce Brainf***) je extrémně minimalistický ezoterický programovací jazyk. Byl vytvořen pro pobavení a jako výzva programátorům, pro praktické účely není vhodný.

Popis jazyka

Jazyk Brainfuck vymyslel v roce 1993 švýcarský programátor Urban Müller. Překladač pro počítače Amiga s OS 2.0 má velikost pouhých 240 bajtů, některé další překladače jsou dokonce menší než 200 bajtů. Klasická Müllerova distribuce verze 2 obsahuje překladač pro počítače Amiga, interpret jazyka, zdrojové kódy ukázkových programů a soubor README se základními informacemi o této distribuci.

Jazyk obsahuje pouze osm příkazů (viz seznam dále). Interpretace příkazů se v Brainfucku provádí sekvenčně, všechny neznámé znaky jsou ignorovány – zdrojový kód lze tedy opatřit komentářem v libovolném místě (komentář pouze nesmí obsahovat klíčové znaky).

Provádění kódu si lze představit jako operace nad polem buněk o velikosti jednoho bajtu. Standardně se používá pole o velikosti 30 000 buněk. Hodnoty buněk jsou před spuštěním programu nastaveny na 0. Každá buňka může obsahovat hodnoty v intervalu 8 bitů (tedy 0-255). Nad těmito buňkami se „pohybuje“ ukazatel, který označuje aktuální buňku, se kterou jsou prováděny operace. Tento ukazatel je při spuštění programu nastaven nad první buňku a lze ho posouvat doleva či doprava.

Příkazy

Příkaz	Popis	Ekvivalent v C[1]	Ekvivalent v Delphi[2]
>	posun datového ukazatele o jednu buňku doprava	++ptr;	Inc(Ptr);
<	posun datového ukazatele o jednu buňku doleva	--ptr;	Dec(Ptr);
+	zvýšení hodnoty aktivní buňky o 1 (buňky, nad kterou je ukazatel)	++*ptr;	Inc(Ptr^);
-	snížení hodnoty aktivní buňky o 1	--*ptr	Dec(Ptr^);
.	výpis hodnoty aktivní buňky na standardní výstup (v drtivé většině případů na obrazovku). Pro výpis se používá hodnota aktivní buňky převedená dle kódování ASCII na znak.	putchar(*ptr);	Write(Char(Ptr^));
,	uložení hodnoty ze vstupu do aktivní buňky	*ptr=getchar();	Read(Char(Ptr^));
[	pokud je hodnota aktivní buňky rovna nule, provede přesun instrukčního ukazatele doprava za odpovídající ]	while (*ptr) {	while Ptr^ <> 0 do begin
]	pokud je hodnota aktivní buňky různá od nuly, provede přesun instrukčního ukazatele doleva na odpovídající [	}	end;

Předchůdce Brainfucku

Za formálního předchůdce Brainfucku lze považovat jazyk ${\displaystyle {\mathcal {P}}^{\prime \prime }}$ vytvořený Corradem Böhmem v roce 1964. Brainfuck je, kromě dvou vstupních a výstupních (I/O) příkazů, menší obměnou tohoto jazyka.

Příklady

Ve všech následujících příkladech jsou ve vysvětlení buňky označovány jako b[Index], kde Index je pořadí buňky. První buňka má index 0.

Hello World!

Jako při popisu každého jazyka, i zde se začíná typickou ukázkou – následující program vypíše Hello World! a skončí.

Kód bez komentáře

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

Kód s komentářem

Protože Brainfuck interpretuje pouze klíčové znaky, je v tomto příkladu komentář vložen přímo do zdrojového kódu a pro snadnější orientaci jsou očíslovány řádky.

  1 ++++++++++
  2 [
  3  >+++++++
  4  >++++++++++
  5  >+++
  6  >+
  7  <<<<-
  8 ] inicializační cyklus nastaví potřebné hodnoty buněk
  9 >++. výpis 'H'
 10 >+. výpis 'e'
 11 +++++++. 'l'
 12 . 'l'
 13 +++. 'o'
 14 >++. mezera
 15 <<+++++++++++++++. 'W'
 16 >. 'o'
 17 +++. 'r'
 18 ------. 'l'
 19 --------. 'd'
 20 >+. '!'
 21 >. nová řádka
 

1. Buňka b[0] je inicializována na hodnotu 10, aby následující cyklus (řádky 2 až 8) proběhl právě desetkrát.
2. Začátek cyklu, ve kterém se inicializují buňky pro výpis jednotlivých písmen.
3. Přesun ukazatele na b[1]. Hodnota v b[1] je v každém kroku cyklu zvýšena o 7. Hodnota b[1] je po skončení cyklu 70 - příprava na výpis písmene 'H' (v kódování ASCII má hodnotu 72).
4. Přesun ukazatele na b[2]. Hodnota v b[2] je v každém kroku cyklu zvýšena o 10. Hodnota b[2] po skončení cyklu je 100 ('e' je v kódování ASCII 101).
5. Přesun ukazatele na b[3]. Hodnota v b[3] je v každém kroku cyklu zvýšena o 3. Hodnota b[3] po skončení cyklu je 30 (mezera je v kódování ASCII 32).
6. Přesun ukazatele na b[4]. Hodnota v b[4] je v každém kroku cyklu zvýšena o 1. Hodnota b[4] po skončení cyklu je 10 (konec řádky v ASCII).
7. Přesun na b[0], snížení hodnoty v této buňce o 1.
8. Cyklus je ukončen po deseti krocích, když klesla hodnota v b[0] na nulu.
9. Přesun na b[1]. Zvýšení hodnoty b[1] o 2 na 72 a výpis 'H'.
10. Přesun na b[2]. Zvýšení hodnoty b[2] o 1 na 101 a výpis 'e'.
11. Zvýšení hodnoty b[2] o 7 na 108 a výpis 'l'.
12. Druhý výpis hodnoty b[2] - 'l'.
13. Zvýšení hodnoty b[2] o 3 na 111 a výpis 'o'.
14. Přesun na b[3]. Zvýšení hodnoty b[3] o 2 na 32 a výpis mezery.
15. Přesun na b[1]. Zvýšení hodnoty b[1] o 15 na 87 a výpis 'W'.
16. Přesun na b[2]. a výpis 'o'.
17. Zvýšení hodnoty b[2] o 3 na 114 a výpis 'r'.
18. Snížení hodnoty b[2] o 6 na 108 a výpis 'l'.
19. Snížení hodnoty b[2] o 8 na 100 a výpis 'd'.
20. Přesun na b[3] Zvýšení hodnoty b[3] o 1 na 33 a výpis '!'.
21. Přesun na b[4] a přechod na novou řádku (v ASCII kódování znak 'LF' s hodnotou 10). Takto implementovaný přechod na novou řádku je ve formátu Unix, kde jsou řádky oddělovány znakem 'LF'. Pro výpis ve formátu Mac by musel být použit znak 'CR' (ASCII hodnota 13), ve formátu DOS by pak musela být použita sekvence těchto znaků ('CR'/'LF').

Nastavení buňky na nulu

[-]

Tento fragment programu nastaví aktivní obsah buňky na 0 – hodnota buňky je v každém kroku cyklu snižována o jednu dokud není 0. Pak se cyklus ukončí.

Jednoduchý cyklus

,[.,]

Tento program dokola vypisuje na obrazovku vstup z klávesnice. V prvním příkazu je do b[0] načtena hodnota na vstupu. V následujícím cyklu je tato hodnota vypsána na obrazovku a znovu je načtena hodnota na vstupu. Tento cyklus je v podstatě nekonečný, protože z klávesnice nelze vložit znak s ASCII hodnotou 0. Jednoduchou modifikací lze zaručit, že program bude ukončen, když je z klávesnice vložena mezera:

+[,.--------------------------------]

V prvním kroku je hodnota b[0] nastavena na 1 pouze z důvodu, aby se následující cyklus ihned neukončil. V cyklu je pak do b[0] uložen vstup z klávesnice a následně je hodnota b[0] vypsána na obrazovku. Po výpisu je hodnota b[0] snížena o 32. Cyklus skončí, pokud je b[0] - 32 = 0 - na vstupu byla mezera, která ma ASCII hodnotu 32. (Program není ošetřen pro vstup menší než 32 - například pro tabulátor s ACSII hodnotou 9.)

Přesun hodnoty z buňky do buňky

[->+<]

V cyklu je snižována hodnota aktivní buňky o 1 a o 1 je zvyšována hodnota následující buňky - po ukončení cyklu (když hodnota aktivní buňky klesne na 0) je v následující buňce hodnota stejná jako byla před započetím cyklu v aktivní buňce. Tento cyklus nefunguje když je hodnota aktivní buňky rovna 0.

Kopírování hodnot v buňkách

[->+>+<<]

Hodnota v aktivní buňce b[0] je pomocí cyklu zkopírována do buněk b[1] a b[2]. Hodnota v b[0] je po skončení cyklu nastavena na 0. Kopírovat hodnotu z buňky do buňky lze také beze ztráty hodnoty v původní buňce:

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

V tomto příkladu je buňka b[2] použita pouze pro dočasné uložení hodnoty. Cyklus probíhá jako v předcházejícím příkladu a po jeho skončení je hodnota z b[2] opět cyklem vrácena do b[0].

Sčítání

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

Tento program sečte číslice na vstupu a vypíše jejich součet pokud je výsledek jednociferný. V případě dvouciferného výsledku vypisuje znak, který má ASCII hodnotu výsledku.

Jazyky založené na Brainfucku

Protože je jazyk Brainfuck jednoduchý, bylo vytvořeno několik dalších programovacích jazyků založených právě na něm.

Doublefuck

Doublefuck je modifikací Brainfucku, který pracuje na dvou páskách. Kromě běžných příkazů Brainfucku zde existuje i druhá sada příkazů pro práci s druhou páskou a je možnost využít i ukazatele. Pro tento jazyk byla přijata zkratka DBF.

Vlastnosti jazyka

DBF pracuje se dvěma poli, z nichž každé disponuje svým ukazatelem. Oba ukazatelé jsou po spuštění programu nastaveny na prvním buňku ve svém poli. Hlavní příkazy jazyka jsou:

Příkaz	Popis příkazu
Příkazy z Brainfucku
>	Posun prvního datového ukazatele o jednu buňku doprava
<	Posun prvního datového ukazatele o jednu buňku doleva
+	Zvýšení hodnoty prvního pole, konkrétně aktivní buňky o 1 (buňky, nad kterou je první ukazatel)
-	Snížení hodnoty prvního pole, konkrétně aktivní buňky o 1 (buňky, nad kterou je první ukazatel)
.	Výpis hodnoty aktivní buňky (buňky, nad kterou je první ukazatel) na standardní výstup (v drtivé většině případů na obrazovku).
,	Uložení hodnoty ze vstupu do aktivní buňky (buňky, nad kterou je první ukazatel)
[	Skok za shodu – Pokud je hodnota aktivní buňky (buňky, nad kterou je první ukazatel) rovna nule, provede přesun instrukčního ukazatele doprava za odpovídající ]
]	Skok před shodu – Pokud je hodnota aktivní buňky (buňky, nad kterou je první ukazatel) různá od nuly, provede přesun instrukčního ukazatele doleva na odpovídající [
Příkazy pro práci s druhou páskou
v	Posun druhého datového ukazatele o jednu buňku doprava
^	Posun druhého datového ukazatele o jednu buňku doleva
/	Zvýšení hodnoty druhého pole, konkrétně aktivní buňky o 1 (buňky, nad kterou je druhý ukazatel)
\	Snížení hodnoty druhého pole, konkrétně aktivní buňky o 1 (buňky, nad kterou je druhý ukazatel)
:	Výpis hodnoty aktivní buňky (buňky, nad kterou je druhý ukazatel) na standardní výstup (v drtivé většině případů na obrazovku).
;	Uložení hodnoty ze vstupu do aktivní buňky (nad kterou je druhý ukazatel)
{	Skok za shodu – Pokud je hodnota aktivní buňky (buňky, nad kterou je druhý ukazatel) rovna nule, provede přesun instrukčního ukazatele doprava za odpovídající }
}	Skok před shodu – Pokud je hodnota aktivní buňky (buňky, nad kterou je druhý ukazatel) různá od nuly, provede přesun instrukčního ukazatele doleva na odpovídající {

Příklad

Hello world v jazyce Doublefuck:

v++++++++++[-///////v//////////v////v///v////////^^^]//:v/:///////::///:v////:v//:
v///////:>+++.+++.------.--------.^/:

Na prvním řádku je vypsáno „Hello, “, na druhém řádku je vypsáno „World!“.

Ostatní modifikace

• PATH kombinuje Brainfuck s jazykem Befunge – obsahuje příkazy pro práci ve dvourozměrném prostoru.
• Brainfork je více vláknová (multi threadová) implementace Brainfucku. Jazyk je rozšířen o příkaz 'Y' pro přepínání mezi jednotlivými vlákny.
• Braintwist je Brainfuck doplněný o možnost modifikace vlastního kódu při jeho běhu.
• THRAT používá pouze dva klíčové znaky (':' a ';'). Pomocí jejich kombinací se provádí příkazy jako v Brainfucku. Množina příkazů je rozšířena o dva – o příkaz na ukončení programu a o příkaz pro číselný výstup.
• L00P nemá příkazy '[' a ']' pro cyklus. Je však doplněn o další příkazy pro cykly a pro manipulaci s hodnotami buněk.
• Ook! používá pro provádění příkazů Brainfucku pouze složeniny z klíčových slov 'Ook.', 'Ook!' a 'Ook?'. Tento jazyk je parodií na Brainfuck inspirovaný vyjadřovacími schopnostmi knihovníka z příběhů Úžasná Zeměplocha spisovatele Terryho Pratchetta.
• COW používá pro provádění příkazů Brainfucku kombinaci klíčových slov Moo. Klíčová slova se rozlišují pouze použitím kapitálek ('Moo', 'MOo', atd.).
• Spoon místo klíčových znaků Brainfucku používá jejich obdobu v Huffmanově kódování.
• BrainDuino port BrainFucku na Arduino I/O desku (Atmel ATMega), je doplněn o příkazy '?', '!' a '_' – tj. zjistit napětí na vstupním pinu (0-255), zapsat hodnotu (0-255) na výstupní pin a poslední slouží k 10 ms busywaitu.

Odkazy

Poznámky

1. Zmíněné ekvivalenty příkazů Brainfucku v jazyce C vycházejí z předpokladu, že proměnná ptr je deklarována jako unsigned char*.
2. Zmíněné ekvivalenty příkazů Brainfucku v Delphi vycházejí z předpokladu, že proměnná ptr je deklarována jako typ ukazatel na Byte (^Byte) a aplikace je překládána jako konzolová (pro funkce Write a Read).

Externí odkazy

• https://sites.google.com/site/visualbf/ Visual brainfuck, jednoduché integrované vývojové prostředí pro Brainfuck
• http://www.muppetlabs.com/~breadbox/bf/ Archivováno 30. 9. 2007 na Wayback Machine. stručný popis jazyka, další odkazy na Brainfuck
• https://web.archive.org/web/20051210061947/http://www.4mhz.de/ interpret jazyka s integrovaným debuggerem (IDE) pro prostředí Windows
• https://web.archive.org/web/20031206060451/http://esoteric.sange.fi/brainfuck/ archiv různých implementací, kompilátorů, zdrojových kódů
• http://www.hevanet.com/cristofd/brainfuck/ podrobný popis jazyka, archiv implementací a zdrojových kódů
• https://web.archive.org/web/20060521223304/http://www.bf-hacks.org/programs.html příklady a další odkazy
• http://www.iwriteiam.nl/Ha_BF.html
• http://home.arcor.de/partusch/html_en/bfd.html Archivováno 3. 3. 2005 na Wayback Machine. kompilátor pro prostředí Windows a DOS
• http://www.robos.org/?bfcomp Brainfuck počítač
• http://www.clifford.at/bfcpu/ Archivováno 18. 12. 2017 na Wayback Machine. Brainfuck procesor
• https://web.archive.org/web/20110807140628/http://kidsquid.99k.org/programs/bf/ Brainfuck OS boot loader
• https://web.archive.org/web/20090102014138/http://stoyan.cz/clanek/jazyk-brainfuck-a-brainfuck-interpret-v-c/ Interpret BrainFucku napsaný v jazyce C
• https://web.archive.org/web/20060504053638/http://justice.loyola.edu/~mcoffey/pr/5k/i.html Interpret BrainFucku napsaný v JavaScriptu
• http://php.vrana.cz/brainfuck.php Interpret BrainFucku napsaný v PHP
• http://github.com/garretraziel/mindfuck Interpret BrainFucku napsaný v Pythonu
• http://esolangs.org/wiki/Brainfuck Detailnější náhled na BrainFuck
• http://esolangs.org/wiki/Brainfuck_algorithms Pokročilejší BF Algoritmy