Brainfuck

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу
Ed NL icon.png
Овај чланак је део пројекта семинарских радова на Математичком факултету у Београду.
Датум уноса: октобар—новембар 2018.
Википедијанци: Ова група студената ће уређивати у ГИП-у и молимо вас да не пребацујете овај чланак у друге именске просторе Википедије.
Позивамо вас да помогнете студентима при уређивању и допринесете да њихови уноси буду што квалитетнији.
brainfuck
Model ezoterični
Pojavio se 1993.
Autor(i) Urban Miler
Tipovi promenljivih netipiziran
Implementacije bf core, bfc, awib, pibfi, mnoge druge
Uticaji P'', FALSE
Uticao na Ook!, SNUSP, cbrain, mnoge druge
Operativni sistemi Amiga, Majkrosoft vindouz, GNU/Linuks, OS X, mnogi drugi

Brainfuck je ezoteričan programski jezik koji je 1993. godine napravio Urban Miler (nem. Urban Müller), a poznat je po svom minimalizmu. Ime jezika potiče od engleske fraze "brainfuck", koja se odnosi na stvar toliko komplikovanu i neobičnu da prevazilazi granice razumevanja. Ime ovog programskog jezika se često za potrebe pravopisa ne tretira kao vlastita imenica, već je običaj da se piše velikim početnim slovom samo u slučajevima gde bi se i zajednička imenica pisala na taj način (na primer, na početku rečenice).

Jezik se sastoji od samo 8 jednostavnih komandi i instrukcionog pokazivača. On ne razlikuje tipove podataka, već sve posmatra kao cele brojeve i podržava samo dve aritmetičke operacije, i to dodavanje jedinice i oduzimanje jedinice. Ovakve instrukcije u velikoj meri oslikavaju komande Tjuringove mašine, te se lako dokazuje da je brainfuck Tjuring-potpun i da može izračunati sve što i klasičniji programski jezici. Međutim, brainfuck od programera zahteva da podeli komande na mikroskopski sitne korake i nije namenjen praktičnoj upotrebi, već kao izazov za programere.

Istorija[уреди]

1992. je švajcarski student fizike, Urban Miler, preuzeo malu online arhivu Amiga softvera.[1] Arhiva je ubrzo postala popularna i počela je da se širi svuda po svetu. Danas je to najveća Amiga arhiva poznata pod imenom Aminet. U ovoj arhivi se pojavila prva implementacija brainfuck jezika.

Miler je dizajnirao brainfuck sa ciljem da ga implementira u obliku najmanjeg mogućeg kompajlera,[2] inspirisan 1024-bitnim kompajlerom za FALSE programski jezik.[3] Milerov originalni kompajler je implementiran u mašinskom jeziku i preveden je u binarni fajl veličine 296 bajta. Okačio je prvi brainfuck kompajler na Aminet 1993. godine. Program je dolazio sa 'readme' datotekom, koja je ukratko opisivala jezik i izazivala čitaoca porukom: "Ko može isprogramirati bilo šta korisno ovime? :)". Miler je takođe uključio i prevodioca i neke kompleksnije primere. Druga verzija kompajlera je bila još kraća i zauzimala je samo 240 bajta.[4]

Kako je Aminet rastao, tako je kompajler postajao popularan širom Amiga zajednice i vremenom je implementiran i na drugim platformama. Vremenom je i pisanje najkraćeg[5], ali i najobimnijeg[6] interpretera postalo izazov za sebe, tako da danas postoje brojne imenovane i neimenovane implementacije ovog jezika.

P", brainfuck-ov zvanični "roditeljski" jezik[уреди]

Izuzev svoje dve ulazno-izlazne komande, brainfuck je mala varijacija programskog jezika P'', koji je napravio Korado Bom (ita. Corrado Böhm) 1964. godine i koji je eksplicitno zasnovan na Tjuringovoj mašini. U stvari, koristeći 6 simbola ekvivalentnih brainfuck naredbama +, -, <, >, [, ], Bom je pružio eksplicitan program za svaku od osnovnih funkcija koje zajedno služe za izračunavanje bilo koje izračunljive funkcije. Prvi programi u jeziku koji se može smatrati brainfuck-ovim roditeljskim jezikom su se pojavili u Bomovom radu iz 1964. godine i oni su bili dovoljni za dokazivanje Tjuringove potpunosti.[7]

The Infinite Abacus: Brainfuck-ov "pra-roditeljski" jezik[уреди]

Joakim Lambek (eng. Joachim Lambek) je 1961. godine predstavio "beskonačni abakus"[8], matematičku i računarsku alatku sa eksplicitnim memorijskim adresiranjem, bez steka i bez uslovnog skoka. Ova alatka se sastoji od beskonačnog broja ćelija i dve instrukcije:

  • X+ = uvećanje ćelije X;
  • X- else jump T = smanjenje X ako je tačno, inače skoči na T.

Dokazao je da beskonačni abakus može izračunati bilo koju izračunljivu rekurzivnu funkciju, programiranjem Klinijevih osnovnih μ-rekurzivnih funkcija.

Njegovu mašinu simulirala je Melzakova mašina[9] za izračunavanje modela pomoću aritmetike, a ne logike koja imitira operatera koji pomera oblutke po abakusu. Ovakav model nije mogao da podrži rad sa označenim brojevima, te otuda uslov da svaki broj mora biti pozitivan. Melzak, čiji jednoinstrukcijski računar je očigledno ekvivalentan beskonačnom abakusu, daje programe za množenje, pronalaženje najvećeg zajedničkog delioca, n-tog prostog broja, predstavljanje u bazi b i sortiranje po veličini. Na ovaj način je pokazano da i ovakva mašina može da simulira proizvoljnu Tjuringovu mašinu.

Ne bi bilo teško zameniti direktno adresiranu memoriju stekom i dvema instrukcijama < i > i tako dobiti jezik koji naliči brainfuck-u.

Dizajn jezika[уреди]

Brainfuck se sastoji od osam komandi, prikazanih u tabeli ispod. Jedan program čini niz ovih komandi, koje mogu biti razdvojene proizvoljnim karakterima. Proizvoljni karakteri se ignorišu, dok se komande izvršavaju sekvencijalno uz izuzetke poput skokova koji preskaču neki deo koda ili vraćaju instrukcijski pokazivač unazad. Instrukcijski pokazivač inicijalno pokazuje na prvu komandu, a svaka komanda na koju ona ukazuje se izvršava, nakon čega se, osim u slučaju skokova, program pomera na sledeću komandu. Program se prekida kada se pokazivač pomeri iza poslednje komande.

Brainfuck koristi jednostavan mašinski model koji se sastoji od programa i instrukcijskog pokazivača, kao i niza od najmanje 30000 jednobajtnih ćelija inicijalizovanih na nulu i pokretnog pokazivača podataka inicijalizovanog da pokazuje na prvi (najlevlji) bajt niza. Ovakav memorijski model je koristila originalna implementacija, i dan danas je najčešće u upotrebi. Niz jednobajtnih ćelija je ekvivalent traci u Tjuringovoj mašini, pri čemu je najveća razlika to što Tjuringova mašina ima neograničen broj ćelija na raspolaganju. Za ulaz i izlaz se koriste dva toka bajtova (najčešće povezanih sa tastaturom i monitorom, pri čemu se karakteri kodiraju u ASCII kodiranju).

Komande[уреди]

Osam komandi brainfuck jezika se sastoje od po jednog karaktera:

Karakter Značenje
> povećaj pokazivač podataka (tako da pokazuje na sledeću ćeliju, za jedno mesto desno od trenutne).
< umanji pokazivač podataka (tako da pokazuje na prethodnu ćeliju, za jedno mesto levo od trenutne).
+ uvećaj za jedan bajt na poziciji pokazivača podatka.
- smanji za jedan bajt na poziciji pokazivača podatka.
. ispiši bajt na poziciji pokazivača podataka.
, primi jedan bajt sa ulaza i sačuvaj ga u bajtu na poziciji pokazivača podataka.
[ ako je bajt na poziciji pokazivača podataka nula, onda umesto da pomeriš instrukcijski pokazivač unapred na sledeću komandu, pomeri ga unapred do komand posle ] koja odgovara ovoj [.
] ako bajt na poziciji pokazivača nije nula, onda umesto da pomeriš instrukcijski pokazivač unapred na sledeću komandu, pomeri ga unazad do komande posle [ koja odgovara ovoj ].

(Alternativno, ] naredba može biti prevedena kao bezuslovni skok na odgovarajuću [ naredbu i obrnuto; programi će imati istu funkciju i ponašati se identično, ali sporije, zbog nepotrebnog dvostrukog pretraživanja.)

[ i ] se ponašaju kao zagrade: svaki [ odgovara tačno jednom ] i obrnuto. [ je uvek prva i ne može postojati neuparena [ ili ] između nje i odgovarajuće ].

Brainfuck programi mogu biti prevedeni u C korišćenjem sledećih zamena, pod pretpostavkom da je ptr (od eng. pointer, u značenju pokazivač) tipa char* i inicijalno ukazuje na niz anuliranih bajtova:

brainfuck komanda C ekvivalent
(Početak programa)
char array[INFINITELY_LARGE_SIZE] = {0};
char *ptr=array;
>
++ptr;
<
--ptr;
+
++*ptr;
-
--*ptr;
.
putchar(*ptr);
,
*ptr=getchar();
[
while (*ptr) {
]
}

Kao što samo ime sugeriše, brainfuck programi su teško razumljivi. Ovo je delom zato što svaki malo kompleksniji zadatak zahteva dugačak niz komandi, a delom zato što tekst programa ne daje direktne indikacije stanja programa. Ovi razlozi, kao i neefikasnost brainfuck jezika i ograničene ulazno-izlazne mogućnosti su su glavni razlog zašto se jezik ne koristi za ozbiljnije i kompleksnije programe. Bez obzira na to, kao i svaki Tjuring-potpun jezik, brainfuck u teoriji može izračunati bilo koju izračunljivu funkciju ili simulirati bilo koji računarski model, ako mu je dat pristup neograničenoj količini memorije.[10] Napisani su raznovrsni brainfuck programi.[11] Iako su programi u ovom jeziku teški i za pisanje, posebno oni kompleksniji, trivijalno je napisati interpreter ili kompajler za ovaj jezik u nekom tipičnijem jeziku, poput jezika C, zbog jednostavnosti samog jezika. Postoje čak i prevodioci za ovaj jezik koji su pisani u samom brainfuck jeziku.[12]

Brainfuck je pravi primer takozvanog Tjuring tarpita: može se koristiti za pisanje bilo kojeg programa, ali nije praktično to učiniti zbog toga što jezik pruža samo minimum mogućnosti koje su neophodne za Tjuring-potpunost, ali ne i mnogo prostora za apstraktno razmišljanje i stoga programi umeju biti izuzetno dugački i komplikovani.

Primeri[уреди]

Hello World![уреди]

Sledeći program ispisuje "Hello World!" i novu liniju na ekranu:

[ Ovaj program ispisuje "Hello World!" i novu liniju na ekran. Njegova
  dužina je 106 (izvršenih) karaktera koji čine program. [Nije najkraći.]

  Ova petlja je "inicijalna petlja za komentare", jednostavan način za 
  dodavanje komentara BF programu tako da ne mora da se vodi računa o 
  komandnim karakterima. Svi ".", ",", "+", "-", "<" i ">" karakteri su 
  jednostavno ignorisani, a "[" i"]" karakteri samo treba da budu balansirani.
  Ova petlja i komande u njoj su ignorisane pošto je podrazumevana vrednost
  prve ćelije na koju pokazuje pokazivač podataka iznosi 0; 0 vrednost
  znači da se nikad ne ulazi u ovu petlju.
]
++++++++                Postavi Ćeliju #0 na 8
[
    >++++               Dodaj 4 na Ćeliju #1; ovo će uvek postaviti Ćeliju #1 na 4
    [                   pošto se u petlji ova ćelija anulira
        >++             Dodaj 2 na Ćeliju #2
        >+++            Dodaj 3 na Ćeliju #3
        >+++            Dodaj 3 na Ćeliju #4
        >+              Dodaj 1 na Ćeliju #5
        <<<<-           Umanji za jedan brojač petlje u Ćeliji #1
    ]                   Vrti petlju dok Ćelija #1 nije 0; broj iteracija je 4
    >+                  Dodaj 1 u Ćeliju #2
    >+                  Dodaj 1 u Ćeliju #3
    >-                  Oduzmi 1 od Ćelije #4
    >>+                 Dodaj 1 u Ćeliju #6
    [<]                 Vrati se u prvu ćeliju koja je 0 na koju naiđeš; ovo
                        će biti Ćelija #1 koja je anulirana u prethodnoj petlji
    <-                  Umanji za jedan brojač petlje u Ćeliji #0
]                       Vrti petlji dok god Ćelija #0 nije 0; Broj iteracija je 8

Rezultat ovoga je:
Br Ćelije:   0   1   2   3   4   5   6
Sadržaj  :   0   0  72 104  88  32   8
Pokazivač:   ^

>>.                     Ćelija #2 ima vrednost 72 što je 'H'
>---.                   Oduzmi 3 od Ćelije #3 kako bi se dobilo 101 što je 'e'
+++++++..+++.           Slično za 'llo' iz Ćelije #3
>>.                     Ćelija #5 je 32 što odgovara razmaku
<-.                     Oduzmi 1 od ćelije #4 kako bi se dobilo 87 što je 'W'
<.                      Ćelija #3 je bila postavljena na 'o' od poslednjeg slova 'Hello'
+++.------.--------.    Ćeliju #3 koristimo za 'rl' i 'd'
>>+.                    Dodavanje 1 u Ćeliju #5 nam daje uzvičnik
>++.                    I konačno novi red iz Ćelije #6

Zbog čitljivosti, ovaj kod je raširen na više linija i dodate su praznine i komentari koji objašnjavaju proces izvršavanja programa. Brainfuck ignoriše sve znakove, osim osam komandi +, -, <, >, [, ], ., , tako da nije potrebna posebna sintaksa za komentare, sve dok sami komentari ne sadrže komandne znakove. Kao što je gore pokazano, i ovo ograničenje se može zaobići uvođenjem petlje koja se nikad ne izvršava. Identičan kod se može zapisati i kao:

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

Najkraći poznat program koji štampa "Hello, World!" broji 72 karaktera i glasi:[13]

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

ROT13[уреди]

Ovaj program šifrira svoj ulaz pomoću ROT13 šifre. Da bi to uradio, mora mapirati karaktere A-M (ASCII 65-77) do N-Z (78-90) i obrnuto. Takođe mora da mapira i a-m (97-109) do (110-122) i obrnuto. Mora mapirati sve ostale karaktere same u sebe; program čita karaktere jednog po jednog i ispisuje njihove šifrovane ekvivalente dok ne pročita kraj datoteke, i tada se završava.

Jednostavan pristup koji se koristi je sledeći: učitavanje ulaznog karaktera , deljenje sa 32, zadržavajući količnik i ostatak. Osim ako je količnik 2 ili 3, izlaz je , zadržavajući kopiju u toku podele. Ako je količnik 2 ili 3, ostatak (() se deli sa 13. Ako je količnik 0, izlaz je ; ako je 1, izlaz je ; ako je 2, izlaz je .

Što se tiče algoritma podele, kada se deli sa da se dobije količnik i ostatak , postoji spoljna petlja koja prvo postavlja i na količnik i ostatak od , zatim na količnik i ostatak od i tako dalje. Nakon izvršavanja petlje puta, spoljna petlja se završava i ostavlja i postavljene na količnik i ostatak od . Deljenik se koristi kao brojač koji se umanjuje i kontroliše koliko puta se petlja izvršava. U okviru petlje, postoji kod za povećanje i smanjenje , što je uglavnom dovoljno. Međutim, svaki -ti put u spoljnoj petlji, neophodno je da se anulira i uveća . To se postiže smanjenjem brojača tako da bude deljiv sa . Svaki put kad prođe kroz spoljnu petlju, brojač se smanjuje, a kada dostigne nulu, popunjava se premeštanjem vrednosti nazad.

 
-,+[                         Pročitaj prvi karakter i počni spoljnu petlju za čitanje karaktera
    -[                       Skoči unapred ako je karakter 0
        >>++++[>++++++++<-]  Postavi delilac (32) za petlju za deljenje
                               (IZGLED MEMORIJE: deljenik kopija ostatak delilac količnik nula nula)
        <+<-[                Postavi deljenik (x minus 1) i uđi u petlju za deljenje
            >+>+>-[>>>]      Uvećaj kopiju i ostatak / umanji delilac / Normalan slučaj: skoči unapred
            <[[>+<-]>>+>]    Specijalan slučaj: pomeri ostatak nazad do delioca i uvećaj količnik
            <<<<<-           Umanji deljenik
        ]                    Zavši petlju za deljenje
    ]>>>[-]+                 Završi petlju za preskakanje; anuliraj mesto delioca i upotrebi mesto za zastavicu
    >--[-[<->+++[-]]]<[      Anuliraj zastavicu osim ako je količnik bio 2 ili 3; anuliraj količnik; proveri zastavicu
        ++++++++++++<[       Ako je zastavica postavljena onda postavi delialc (13) za drugu petlju za deljenje
                               (IZGLED MEMORIJE: nula kopija deljenik delilac ostatak količnik nula nula)
            >-[>+>>]         Umanji delilac; Normalan slučaj: uvećaj ostatak
            >[+[<+>-]>+>>]   Specijalan slučaj: uvećaj ostatak / pomeri ga nazad do delioca / uvećaj količnik
            <<<<<-           Umanji deljenik
        ]                    Završi petlju za deljenje
        >>[<+>-]             Dodaj ostatak nazad na deljenik da dobiješ korisnu 13-icu
        >[                   Skoči unapred ako je količnik bio 0
            -[               Smanji količnik i skoči unapred ako je količnik bio 1
                -<<[-]>>     Anuliraj količnik i delilac ako je količnik bio 2
            ]<<[<<->>-]>>    Anuliraj delilac i oduzmi 13 od kopije ako je količnik bio 1
        ]<<[<<+>>-]          Anuliraj delilac i dodaj 13 na kopiju ako je količnik bio 0
    ]                        Završi spoljašnji niz za preskakanje (skoči ovde ako ((karakter minus 1)/32) nije 2 ili 3)
    <[-]                     Anuliraj ostatak iz prvog deljenja ako je drugo deljenje bilo preskočeno
    <.[-]                    Ispiši ROT13-ovan karakter iz kopije i anuliraj je
    <-,+                     Čitaj sledeći karakter
]                            Završi petlju za čitanje karaktera

Aritmetičke operacije[уреди]

Dodavanje dve vrednosti[уреди]

Kao jednostavan primer, sledeći deo koda ce dodati vrednost trenutne ćelije sledećoj ćeliji. Svaki put kada se petlja izvrši, trenutna ćelija se smanjuje, pokazivač se pomera u desnu stranu, a sledeća ćelija se uvećava i pokazivač se pomera levo. Ova sekvenca se ponavlja dok početna ćelija ne bude 0.

[->+<]

Ovo se može pripojiti jednostavnom programu za dodavanje na sledeći način:

++       Ćelija c0 = 2
> +++++  Ćelija c1 = 5

[        Počni petlju sa pokazivačem podataka na brojaču petlje (c1 u našem slučaju)
< +      Dodaj 1 na c0
> -      Oduzmi 1 sa c1
]        Završi petlju sa pokazivačem podataka na brojaču petlje
Primetimo da je petlja iznad ekvivalentna onoj datoj u prethodnom bloku koda

U ovom trenutku program je dodao 5 na 2 ostavljajući 7 u c0 i 0 u c1
ali ovu vrednost ne možemo ispisati na terminal pošto nije kodirana u ASCII-ju

Kako bismo prikazali ASCII karakter "7" moramo da dodamo vrednost 48 na vrednost 7
48 = 6 * 8 tako da koristimo još jednu petlju za množenje kako bismo skratili program

++++ ++++  c1 = 8 i ovo će biti naš brojač u petlji 
[
< +++ +++  Dodaj 6 na c0
> -        Oduzmi 1 od c1
]
< .        Ispiši c0 u kojoj je vrednost 55 što odgovara ASCII karakteru "7"!

Ovaj pristup štampanja funkcioniše samo za jednocifrene brojeve a 
generalizovan algoritam je dat ispod

Oduzimanje dve vrednosti[уреди]

Oduzimanje dva broja se može implementirati na sličan način kao i sabiranje, samo što se umesto povećavanja polja rezultata ono smanjuje. Na primer, kod koji oduzima trojku od petice može izgledati ovako:

+++++                Postavi ćeliju 1 na 5 (umanjenik)
>+++                 Postavi ćeliju 2 na 3 (umanjilac)
[                    U petlju se ulazi na pokazivačem na drugu ćeliju
    -<               Smanji drugu ćeliju i pomeri pokazivač na prvu
    ->               Smanji prvu ćeliju i vrati pokazivač na drugu
]                    Ponavljaj sve dok druga ćelija nije 0
<                    Vrati pokazivač na prvu ćeliju (u kojoj je rezultat)

Množenje dve vrednosti[уреди]

Množenje dva broja se može izvršiti kao višestruko sabiranje. U svakoj iteraciji petlje, jedan činilac se smanjuje, a drugi povećava za konstantnu vrednost.

+++++                Postavi prvu ćeliju na 5 (činilac)
[
    ->               Smanji prvu ćeliju, prebaci pokazivač na drugu
    +++              Dodaj tri na drugu ćeliju (drugi činilac)
    <                Vrati pokazivač na prvu ćeliju 
]                    Ponavljaj sve dok prva ćelija nije 0
>                    Postavi pokazivač na drugu ćeliju (u kojoj je rezultat)

Pošto brainfuck ne podržava numeričke literale, svaku netrivijalno malu vrednosti nije praktično dobiti kao uzastopno dodavanje jedinice. Umesto toga, najčešće se koristi algoritam za množenje sličan ovom kako bi se od manjih vrednosti došlo do većih, na koje se zatim dodaje neka mala vrednost. [14]

Deljenje dve vrednosti[уреди]

Logika iza deljenja dva broja je slična onoj za množenje. U svakoj iteraciji petlje, od jednog broja se oduzima konstantna vrednost, dok se druga povećava za jedan, sve dok je prva vrednost različita od nule. Ova bazična implementacija ispravno radi samo u implementacijama čija je minimalna vrednost nula i ne dolazi do potkoračenja, ili u slučaju da je deljenik deljiv deliocem.

++++++++++++         Postavi prvu ćeliju na 12 (deljenik)
[
    ---              Oduzmi 3 od prve ćelije (delilac)
    >+               Pomeri pokazivač na drugu ćeliju i uvećaj je za jedan (količnik)
    <                Vrati pokazivač na prvu ćeliju
]                    Ponavljaj sve dok prva ćelija nije 0
>                    Pomeri pokazivač na drugu ćeliju (u kojoj je rezultat)

Štampanje vrednosti[уреди]

Brainfuck ne razlikuje tipove podataka, i pri štampanju većina implementacija štampa ASCII karakter koji odgovara datoj vrednosti. Za jednocifrene brojeve, dodavanje konstantne vrednosti 48 (što je razlika između numeričke vrednosti i ASCII koda za tu cifru) kao što je to urađeno u primeru za sabiranje je dovoljno. Međutim, kada se štampaju veći brojevi, ovo nije adekvatno rešenje, već se višecifren broj mora deliti sa 10 i ostatak pri tom deljenju čuvati u zasebnim ćelijama, koje se na kraju ispisuju. Algoritam koji ispisuje broj u ćeliji na koji pokazuje pokazivač i koristi ćelije desno od njega kao "radnu površinu" je dat ispod. Ovaj algoritam funkcioniše za sve vrednosti, nezavisno od veličine ćelije.

[>>+>+<<<-]>>>                     Prvo kopiraj vrednost u radnu površinu i nazad
[<<<+>>>-]<<+>
[<->[                              Dok god vrednost nije nula
   >++++++++++<                    Napravi 10
   [->-[>+>>]>[+[-<+>]>+>>]<<<<<]  Podeli vrednost sa 10
   >[-]                            Ova ćelija nam ne treba i postavljamo je na 0
   ++++++++[<++++++>-]             Dodaj 48 na ostatak kako bi se dobila ASCII vrednost
   >[<<+>>-]                       Sačuvaj ostatak
   >[<<+>>-]                       Uzmi sledeću vrednost
   <<
]>]
<[-                                Ako je ćelija prazna (nula) onda pravimo ASCII nulu (tj vrednost 48)
   >>++++++++[<++++++>-]
]
<[.[-]<]<                          Odštampaj i anuliraj vrednosti ostataka (radnu površinu) u obrnutom redosledu

Problemi sa prenosivošću[уреди]

Do ovih problema dolazi delimično zato što Urban Miler nije napisao temeljnu specifikaciju jezika, a delimično zato što mnogi kasniji prevodioci i kompilatori koriste nešto drugačije dijalekte programskog jezika brainfuck.

Veličina ćelije[уреди]

U klasičnoj verziji programskog jezika, ćelije su široke 8 bitova (ćelije su bajtovi), što je i dalje najčešća veličina. Međutim, da bi se pročitali ne-tekstualni podaci, brainfuck treba da pravi razliku između kraja fajla (EOF karaktera) od ostalih upisanih vrednosti, zbog čega se koriste 16-bitne ćelije. Neke implementacije jezika su koristile i 32-bitne ili 64-bitne ćelije ili ćelije arbitrarne veličine (bignum). Programi koji koriste bignum ćelije su dosta sporiji, jer se čuvanje neke vrednosti u ćeliji vrši u Ω(n) vremenu, što se brzo nagomila s obzirom na često izvršavanje + i - komandi.

U svim ovim varijantama, komande , i . i dalje čitaju i pišu vrednosti u bajtove. U većini slučajeva ćelije mogu da obuhvate te vrednosti, a kada se ćelija koja ima maksimalnu vrednost poveća (+ komandom), u ćeliju se smešta minimalna vrednost, i obratno. Izuzeci su slučajevi kada se program izvršava na procesorima koji interno ne koriste potpuni komplement što je u današnje vreme redak slučaj, implementacije koje su odvojene od hardvera, implementacije koje koriste bignume i implementacije koje akcenat stavljaju na prenosivosti.

U većini slučajeva, prekoračenje ne predstavlja veliki problem za brainfuck programere. Međutim, pošto nema operatora poređenja, program ne može napraviti razliku između označenih i neoznačenih potpunih komplementata fiksne veličine ćelije, niti na bilo koji način detektovati prekoračenje. Takođe, negativnost broja može zavisiti od interpretacije bajta, što je često definisano implementacijom.

Veličina niza[уреди]

U klasičnoj distribuciji, niz se sastoji od 30000 ćelija i pokazivač počinje na prvoj ćeliji na levoj strani niza. Više ćelija je potrebno za upisivanje stvari poput milionitog broja Fibonačijevog niza, a najlakši način da se ovo postigne i da jezik ostane Tjuring-potpun je da se napravi niz koji je neograničen sa desne strane.

Nekoliko implementacija[15] proširuju niz i sa leve strane, ali je ovo ređa situacija, stoga prenosivi brainfuck programi ne zavise od toga.

Kada se pokazivač pomeri izvan granica niza, neke implementacije prikazuju poruku greške, neke pokušavaju da dinamički prošire niz, neke ne primećuju prekoračenje i proizvode nedefinisano ponašanje, dok neke pomeraju pokazivač na suprotnu stranu niza. Kompromis može biti proširenje niza dinamički u desnu stranu, kao najlakši način proširenja niza i dobro je za programe kojima je potrebna velika količina memorije, ali ova opcija vuče sa sobom kaznu u vidu smanjene brzine. Ako je korišćen niz fiksne veličine, poželjno je izabrati vrlo veliku veličinu niza.

Kraj linije[уреди]

Različiti operativni sistemi (a ponekad i programska okruženja) drugačije tumače ASCII kodove. Najvažnija razlika je u kodu koji se koristi za kraj reda i početak nove linije teksta. MS-DOS i Microsoft Windows koriste CRLF, tj. 13 praćeno sa 10, u većini slučajeva. Unix i njegovi naslednici (uključujući GNU/Linux i Mac OS X) i Amiga koriste samo 10, a stariji Mac-ovi koriste samo 13. Bilo bi komplikovano ako bi brainfuck programi morali biti ponovo ispisani na svakom od ovih operativnih sistema. Međutim, lako je napraviti zajednički standard za brainfuck programe. Urban Milerov kompajler i njegovi primeri programa koriste 10 za ulaz, kao i za izlaz. To prati i velika većina brainfuck programa, jer je 10 pogodnije za korišćenje od CRLF-a. Dakle, brainfuck implementacije treba da se uvere da brainfuck programi podrazumevaju da nova linija ima vrednost 10 i da to ispravno radi, što mnoge i čine.

Ova pretpostavka je prisutna u većini uzoraka C koda kao i drugih jezika, gde se koristi "\n" ili 10 za novi red. Na sistemima koji koriste CRLF kraj linije, standard je da se zameni "\n" sa "\r\n" na izlazu i "\r\n" sa "\n" na ulazu za tokove koji nisu otvoreni u binarnom modu.

Kraj datoteke[уреди]

Ponašanje komande , na kraju datoteke varira. Neke implementacije postavljaju vrednost ćelije i pokazivač na 0, neke postavljaju na vrednost EOF konstante u C-u (u praksi je to uglavnom -1), neke ostave vrednost nepromenjenu. Nema saglasnosti oko korišćenja datih opcija, pa postoje argumenti za svaku od njih:

Stavljanje vrednosti na 0 izbegava kosrišćenje negativnih brojeva i sažetije je napraviti petlja koja se izvršava dok ne dođe do kraja datoteke. Ovo proširenje u jeziku je osmislio Panu Kaliokoski (eng. Panu Kalliokoski).

Stavljanje vrednosti na -1 dozvoljava kraju datoteke da bude različit od bilo koje vrednosti bajta (ako su ćelije veće od bajtova), što je neophodno za čitanje ne-tekstualnih podataka. Takođe, to je ponašanje C prevoda , komande, date u Milerovoj readme datoteci. Ipak, nije očigledno da se ovi C prevodi uzmu kao norma.

Nemenjanje vrednosti ćelije je ponašanje Milerovog kompajlera. Ovo ponašanje može postojati uz bilo koje drugo ponašanje. Na primer, program koji podrazumeva da je kraj datoteke jednak nuli može da stavi vrednost ćelije na 0 pre svake , komande i to će ispravno raditi na implementacijama koje podrazumevaju da je kraj datoteke jednak nuli ili da je kraj datoteke nepromenjen. Lako je prilagoditi se nepromenjenom kraju datoteke i svaki brainfuck programer zainteresovan za prenosivost programa bi trebalo to da radi.

Implementacije[уреди]

Jednostavnost brainfuck-a ga čini popularnom metom za mnoge različite implementacije.[16] Sem originalne implementacije za Amigu koju je napisao Urban Miler, postoji preko sto različitih kompajlera i interpretera.[17] Implementacije se kreću od izuzetno malih kao što su BF6502A2, interpreter dugačak 135 bajtova za Apple ][ //e,[18] i bf core, koji se sastoji od 69 bajtova x86 asemblerskog koda,[19] pa do optimizujućih kompajlera kao što su bfc, koji se oslanja na LLVM i podržava optimizacije kao što su spajanje naredbi, pojednostavljavanje petlji, eliminisanje mrtvog koda, spekulativno izvršavanje i dr,[20] i awib, koji podržava prevođenje do više različitih jezika, i sam je pisan u brainfuck-u.[21]

Postoje i implementacije pisane za platforme koje nisu u široj upotrebi. Tako je iHeadAche brainfuck interpreter za Palm OS,[22], zxBrainfuck pisan u Z80 asembleru sa ZX Spectrum [23] ili BrainfuckCE koji je namenjen TI 84+ CE kalkulatorima.[24] Hardverske implementacije ovog jezika uključuju The Brainf*ck CPU Project, VHDL implementacija brainfuck CPU-a,[25], TinyDumbCPU, SystemVerilog brainfuck jezgro [26] i The Brainfuck Computer, koji predstavlja mali brainfuck interpreter narezan na ROM PIC16F84A mikrokontrolera.[27]

Derivati i proširenja[уреди]

Stvaranje jezika sličnih ili u velikoj meri inspirisanih brainfuck-om se pokazalo kao interesantan izazov programerima. I dok je nekima cilj isključivo zabava, drugi ovaj jezik nadograđuju brojnim mehanizmima pozajmljenim od klasičnijih programskih jezika.

Ekvivalenti[уреди]

Postoji širok spektar brainfuck ekvivalenata, koji imaju identične komande kao brainfuck, ali se različito kodiraju, sa ili bez ulazno-izlaznih komandi koje ovaj jezik poseduje. Ova familija broji preko 50 različitih programskih jezika.[28][29] Neki od popularnijih su:

  • Ook!, koji mapira osam komandi brainfuck-a u permutacije dužine dva reči "Ook.", "Ook?" i "Ook!". Po rečima autora, dizajniran je tako da mogu da ga "pišu i čitaju orangutani".[30] Jedan je od najstarijih u nizu sličnih brainfuck ekvivalenata.[31]
  • Ternary i Triplet koji brainfuck komande kodiraju, redom, u parove ternarnih[32] i triplete binarnih[33] cifara.
  • VerboseFuck koji izgleda kao tradicionalan programski jezik, ali se u stvari sastoji od osam dugačkih komandi koje liče na pozive metodama i ne mogu se menjati, i zahteva nepromenljiv blok koda na početku i na kraju programa. [34]
  • BodyFuck, brainfuck implementacija bazirana na sistemu kontrolisanom pokretima, tako da kamera snima pokrete programera i snimak se kodira u osam mogućih karaktera.[35]

Proširenja[уреди]

Sa svojih skromnih osam instrukcija, iako je Tjuring-potpun, brainfuck ne implementira mnoge mogućnosti koje programeri mogu poželeti. Stoga, postoje varijacije ovog jezika koje koriste izvornih osam instrukcija, i dodaju još neke.

  • pbrain dodaje mogućnost pisanja procedura koje se mogu pozivati iz brainfuck koda.[36]
  • cbrain je ekstenzija pbrain-a koja dodaje numeričke literale i brojne operatore.[37]
  • Brainfork podržava kreiranje novih niti i konkurentno programiranje.[38]
  • Hq9eFuck kombinuje instrukcije brainfuck-a i HQ9+-a u jedan jezik, i dodaje komandu Duboka misao koja računa i ispisuje odgovor na Pitanje o životu, vaseljeni i svemu ostalom, što je referenca na Autostoperski vodič kroz galaksiju. [39]

Derivati[уреди]

Brainfuck je takođe inspirisao mnoge da naprave svoje jezike koji ga na neki način unapređuju ili ga menjaju po uzoru na mogućnosti drugih jezika. Za razliku od jednostavnih proširenja koje na osam postojećih dodaju nove komande, programski jezici iz ove grupe pozajmljuju ideje i koncepte, ali ne nužno i sintaksu i leksiku od brainfuck-a. Postoji preko 200 različitih derivata ovog jezika.[40] Neki od njih su:

  • PATH[41], SNUSP[42] i Wierd[43] kombinuju komande brainfuck-a sa dvodimenzionom prirodom Befunge-a.
  • Mice in a maze kombinuje instrukcije brainfuck-a sa teorijom ćelijskih automata, i u njemu program se sastoji od lavirinta kroz koji prolaze (hipotetički) miševi, izvršavajući komande koje im se nađu na putu.[44]
  • Smallfuck[45], Boolfuck[46] i Bitter [47] su varijacije brainfuck-a koje kao ćelije umesto bajtova koriste bitove. Bitter takođe definiše i dve opcione komande za interpreter, koje pomažu pri debagovanju programa.

Izuzetna nepraktičnost implementacije ili neistražena priroda fizičke realnosti nisu sprečile programere da napišu specifikacije najrazličitijih derivata ovog jezika. Tako postoji i Quantum brainfuck koji umesto bajtova koristi kubite,[48] i Wigner's Fuckbuddy Is A (|Top⟩ + |Bottom⟩)/√2 koji pretpostavlja da je interpretacija kvantne mehanike Hjua Evereta (tzv. interpretacija više svetova ili teorija multiverzuma) tačna i da se univerzumi mogu manipulisati.[49] Kako je i sam brainfuck nastao kao oblik zabave među programerima, tako ove praktično nemoguće specifikacije odlaze korak dalje i kroz humor uvode nove, fiktivne, programske jezike kroz naizgled ozbiljne i komplikovane fizičke koncepte.

Vidi još[уреди]

  • Ezoterični programski jezici – primeri drugih ezoteričnih jezika i same paradigme
  • Tjuringova mašina – teorijski koncept centralan za računarstvo od koga brainfuck pozajmljuje neke koncepte (najznačajnije, pojam trake koja čini memoriju brainfuck programa)

Reference[уреди]

  1. ^ „Aminet hits 5000 files”. Urban Müller. 24. 9. 1993. Приступљено 24. 10. 2018. 
  2. ^ „The Brainfuck Programming Language”. Muppetlabs.com. Приступљено 30. 10. 2013. 
  3. ^ „Wouter's Wiki : False Language”. Strlen.com. 3. 8. 2013. Приступљено 24. 10. 2018. 
  4. ^ „dev/lang/brainfuck-2.lha”. Aminet. Архивирано из оригинала на датум 06. 11. 2005. Приступљено 24. 10. 2018. 
  5. ^ „Interpret brainf***”. Programming Puzzles & Code Golf Stack Exchange. Приступљено 24. 10. 2018. 
  6. ^ „The Platonic Ideal BrainFuck Interpreter”. Cat's Eye Technologies. Приступљено 24. 10. 2018. 
  7. ^ Böhm, C., 1964. On a family of Turing machines and the related programming language. ICC Bulletin, 3(3), pp.187-194.
  8. ^ J. Lambek (1961). „How to program an infinite abacus”. Canadian Mathematical Bulletin. 
  9. ^ Z. A. Melzak (1961). „An informal arithmetical approach to computability and computation”. Canadian Mathematical Bulletin. 
  10. ^ „BF is Turing-complete”. Iwriteiam.nl. Приступљено 24. 10. 2018. 
  11. ^ „Index of /brainfuck/bf-source/prog”. Esoteric.sange.fi. 22. 1. 2002. Приступљено 24. 10. 2018. 
  12. ^ „BF interpreter written in BF”. Iwriteiam.nl. Приступљено 24. 10. 2018. 
  13. ^ „Hello, World! - brainfuck”. Programming Puzzles & Code Golf Stack Exchange. Приступљено 24. 10. 2018. 
  14. ^ „Brainfuck constants”. Esolangs. Приступљено 24. 10. 2018. 
  15. ^ Bolognani, Andrea. „Beef - a flexible interpreter for the Brainfuck programming language.”. Kiyuko.org. Приступљено 24. 10. 2018. 
  16. ^ „Interpret brainf***”. Programming Puzzles & Code Golf Stack Exchange. Приступљено 24. 10. 2018. 
  17. ^ „Brainfuck implementations”. Esolangs. Приступљено 24. 10. 2018. 
  18. ^ „BrainFuck 6502 Interpreter in 135 bytes for the Apple ][”. comp.emulators.apple2 - Gugl grupe. Приступљено 24. 10. 2018. 
  19. ^ „bf core”. Esolangs. Приступљено 24. 10. 2018. 
  20. ^ „bfc - An industrial-grade brainfuck compiler”. Wilfred/bfc (GitHub repozitorijum). Приступљено 24. 10. 2018. 
  21. ^ „awib - a brainfuck compiler written in brainfuck”. matslina/awib (GitHub repozitorijum). Приступљено 24. 10. 2018. 
  22. ^ „iHeadAche”. aldweb. Приступљено 24. 10. 2018. 
  23. ^ „zxbrainfuck”. falsovsky/z80 (GitHub repozitorijum). Приступљено 24. 10. 2018. 
  24. ^ „BrainfuckCE - A Brainfuck interpreter and native compiler written in C for TI 84+ CE calculators.”. nathanfarlow/BrainfuckCE (GitHub repozitorijum). Приступљено 24. 10. 2018. 
  25. ^ „The Brainf*ck CPU Project”. Clifford Wolf. Приступљено 24. 10. 2018. 
  26. ^ „tinydumbcpu”. asumagic/tinydumbcpu (GitHub repozitorijum). Приступљено 24. 10. 2018. 
  27. ^ „The Brainfuck Computer”. Robert Östling. Приступљено 24. 10. 2018. 
  28. ^ „Category: Brainfuck equivalents”. Esolangs. Приступљено 24. 10. 2018. 
  29. ^ „Joke language list - Brainfuck derivatives”. Esolangs. Приступљено 24. 10. 2018. 
  30. ^ Morgan-Mar, David (21. 3. 2009). „Ook!”. DM's Esoteric Programming Languages. Приступљено 24. 10. 2018. 
  31. ^ „Ook!”. Esolangs. Приступљено 24. 10. 2018. 
  32. ^ „ternary - Ternary Programming Language”. zerosum0x0/ternary (GitHub repozitorijum). Приступљено 24. 10. 2018. 
  33. ^ „Triplet”. Esolangs. Приступљено 24. 10. 2018. 
  34. ^ „VerboseFuck”. Esolangs. Приступљено 24. 10. 2018. 
  35. ^ Hanselmann, Nik. „There is no hardware.”. Приступљено 24. 10. 2018. 
  36. ^ „pbrain Language Compiler”. Parks Computing. Приступљено 24. 10. 2018. 
  37. ^ „cbrain”. Esolangs. Приступљено 24. 10. 2018. 
  38. ^ „Brainfork”. Esolangs. Приступљено 24. 10. 2018. 
  39. ^ „Hq9eFuck”. Esolangs. Приступљено 24. 10. 2018. 
  40. ^ „Category: Brainfuck derivatives”. Esolangs. Приступљено 24. 10. 2018. 
  41. ^ „About PATH”. PATH homepage. Приступљено 24. 10. 2018. 
  42. ^ „SnuspLanguage”. C2 - SnuspLanguage. Приступљено 24. 10. 2018. 
  43. ^ „wierd spec”. graue/esofiles (GitHub repozitorijum). Приступљено 24. 10. 2018. 
  44. ^ „Mice in a maze”. Esolangs. Приступљено 24. 10. 2018. 
  45. ^ „Smallfuck”. Esolangs. Приступљено 24. 10. 2018. 
  46. ^ „Boolfuck homepage”. Samuel Hughes. Приступљено 24. 10. 2018. 
  47. ^ „Bitter”. Esolangs. Приступљено 24. 10. 2018. 
  48. ^ „Quantum brainfuck”. Esolangs. Приступљено 24. 10. 2018. 
  49. ^ „Wigner's Fuckbuddy Is A Superposition of Top And Bottom”. Esolangs. Приступљено 24. 10. 2018. 

Spoljašnje veze[уреди]