Opasarkisto: Brainfuck

Brainfuck on yksinkertainen, rajoittunut ja tehoton ohjelmointikieli, jolla on turha odottaa saavansa aikaan oikeastaan mitään hyödyllistä. Sillä voi kaikesta huolimatta hämmästyttää muita ja viihdyttää aivojaan: koodi ei juuri koskaan ole selkeää, ja pienetkin asiat vaativat suuren määrän koodia, josta ei voi nopealla vilkaisulla ymmärtää käytännössä mitään.

Mistä kääntäjä?

Brainfuck-tietoa sekä kunnollisia tulkkeja ja kääntäjiä löytyy Internetistä suhteellisen niukasti. Ohjelmointiputkassa on kuitenkin JavaScriptilla toteutettu Brainfuck-tulkki, jolla kaikkia oppaan koodeja voi helposti testata. Koodivinkkeihin on päätynyt myös eräs C-kielinen toteutus. Tulkki on helppo tehdä itsekin, jos osaa jotain toista ohjelmointikieltä: kaikki tarvittava Brainfuckista kerrotaan tässä oppaassa.

Perusteet

Brainfuck-ohjelman käytössä on yleensä 30000 muistipaikkaa, jotka ovat kooltaan yleensä yhden tavun; joissain toteutuksissa määrä tai koko voi kuitenkin poiketa tästä. Kussakin muistipaikassa on yksi kokonaisluku, ohjelman alussa aina nolla. Kielen perusoperaatiot ovat käsiteltävän muistipaikan vaihtaminen (merkit < ja >), arvon muuttaminen yhdellä (merkit + ja -), paikassa olevan arvon tulostaminen ASCII-merkkinä (.) ja merkin lukeminen muistipaikkaan (,) sekä silmukka ([]), jota toistetaan niin kauan, kuin silmukan alussa valittuna olevan muistipaikan arvo on nollasta poikkeava. Kieli koostuu ainoastaan näistä kahdeksasta merkistä, ja kaikki muut merkit jätetään huomiotta. Kommentteja voi siis vapaasti kirjoittaa koodin sekaan, kunhan ne eivät vahingossa sotke oikeaa koodia.

Muistipaikan vaihto: merkit < ja >

Suurempi kuin ja pienempi kuin -merkit on hyvä käsittää nuolina vasemmalle ja oikealle. Ne vaihtavat valittua muistipaikkaa yhden jompaankumpaan suuntaan. Jos näin päädytään 30000 tavun muistitaulun ulkopuolelle, ohjelma voi toteutuksesta riippuen kaatua tai hypätä taulukon vastakkaiseen reunaan. Aluksi on valittuna vasemmanpuoleisin muistipaikka. Jokainen voi itse päättää, onko se ensimmäinen vai nollas muistipaikka, mutta tässä oppaassa sitä kutsutaan nollanneksi.

Tämä yksinkertainen ohjelma siirtyy ensin kolme muistipaikkaa eteenpäin ja sitten kolme taaksepäin eli takaisin lähtöpisteeseensä.

>>> <<<

Arvon muuttaminen: merkit + ja -

Plus- ja miinus-merkit korottavat tai vastaavasti laskevat valitun muistipaikan arvoa yhdellä. Koska muistipaikka on tavun kokoinen, se sisältää arvon väliltä [-128, 127] tai vaihtoehtoisesti [0, 255], miten kukin sen haluaa tulkita. Arvoalueen ylittyessä muistipaikka pyörähtää ympäri. Ohjelman aluksi kaikki muistipaikat on asetettu nollaan.

Tämä ohjelma asettaa ohjelman ensimmäisiin muistipaikkoihin arvot 0, 1, 2 ja 3. Arvoa 0 ei toki tarvitse erikseen asettaa.

> + > ++ > +++

Tiedonsiirto: merkit . ja ,

Piste tulostaa muistipaikan arvon, ja pilkku lukee sen. Muistipaikat ovat tavun kokoisia, joten yksi muistipaikka on yksi merkki. Arvo tulostuukin vastaavana merkkinä, joka voi riippua käytettävästä merkistöstä. Tyypillisesti A-kirjain on lukuarvoltaan 65, numero 0 puolestaan on 48.

Näin pyydetään käyttäjältä neljä merkkiä ja tulostetaan ne takaisin käänteisessä järjestyksessä:

,>,>,>,
.<.<.<.

Silmukka: merkit [ ja ]

Hakasulut määrittävät silmukan. Alun hakasulun kohdalla tarkistetaan aina, onko valittu muistipaikka nolla. Jos se on, hypätään silmukan yli. Jos ei, suoritetaan silmukka. Silmukan lopettavasta hakasulusta hypätään takaisin alun hakasulkuun. Usein on tarkoituksenmukaista palata silmukan lopuksi samaan muistipaikkaan, josta lähdettiin; silmukka ei tee sitä omin avuin.

Tämä esimerkkiohjelma tulostaa luvut nollasta yhdeksään. Ensin asetetaan nollapaikan arvoksi kymmenen: silmukka pitää suorittaa kymmenen kertaa. Sitten asetetaan ykköspaikan arvoksi numeron nolla ASCII-koodi eli 48. Silmukassa vähennetään aina nollapaikkaa, tulostetaan ykköspaikan arvo ja korotetaan sitä. Kymmenennen kerran jälkeen nollapaikassa on nolla, joten silmukka loppuu.

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

Lukujen yhteenlasku

Yhteenlasku on työlästä puuhaa. Koska muistipaikan arvoa ei saa mitenkään kokonaisuudessaan siirrettyä kerralla, se pitää siirtää toiseen paikkaan ykkönen kerrallaan. Yhteenlasku onnistuu siirtämällä näin kahden muistipaikan arvot samaan muistipaikkaan. Tässä pienessä esimerkissä lasketaan yhteen kolmonen ja nelonen. Ensin siis laitetaan nollapaikkaan kolme ja ykköspaikkaan neljä. Sitten silmukassa vähennetään nollapaikasta ja lisätään kakkos- ja nelospaikkoihin, kunnes nollapaikka on nolla. Näin alkuperäinen arvo on yhä muistissa mutta nollapaikan sijaan kahdessa muussa. Seuraavaksi siirretään ykköspaikan arvo kakkos- ja kolmospaikkoihin, minkä jälkeen kakkospaikan arvo on seitsemän, kolmospaikan neljä ja nelospaikan kolme. Lopuksi jokaiseen näistä lisätään nollan ASCII-arvo 48, jotta saadaan aikaan tulostuskelpoista materiaalia, nimittäin Pikku Kakkosen postilokeron numero.

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

Mutkikkaampi esimerkki

Tässä on yksinkertainen ohjelma, joka laskee Fibonaccin lukuja ja tulostaa ne oktaalimuodossa. Ohjelmassa on C++-tyylisiä kommentteja. Koska Brainfuck käsittelee koodista kaikki tuntemansa merkit, kaikki plussat ja miinukset on täytynyt ilmaista kommenteissa muulla tavalla.

// Tulostetaan 1 ja 1
// Ykkönen nollapaikkaan ja välilyönti paikkaan m13
// Tulostetaan "1 1"
++++++++++++++++ ++++++++++++++++ ++++++++++++++++ + .
>>>>>>>>>>>>> ++++++++++++++++ ++++++++++++++++ .
<<<<<<<<<<<<< .

[-]                 // Nollapaikkaan nolla
+++++               // Montako kertaa lasketaan kaksi lukua?
>+ >+ <<            // m1 = 1   ja   m2 = 1

[->                 // while (m0)   valitaan m1

// Lukujen liikkeet; & tarkoittaa plussaa
// m1     m2     m3
// a      b
// a&b           b
//        a&b    a & 2b
// a&b           a & 2b
// a&b    a & 2b

>[-<+>>+<]          // m1 &= m2   ja   m3 &= m2   ja   m2 = 0
<[->+>>+<<<]        // m2 &= m1   ja   m4 &= m1   ja   m1 = 0
>>>[-<<<+>>>]       // m1 &= m4   ja   m4 = 0
<[-<+>]>            // m2 &= m3   ja   m3 = 0

// Siirretään luvut sopivasti oktaalimuotoon muuttamista varten
>[-]>[-]>[-]>[-]             // m5 m6 m7 m8 = 0
>[-]>[-]>[-]>[-]             // m9 m10 m11 m12 = 0
<<<<<<<<<<<[->>>>+>+<<<<<]   // m5 = m6 = m1   ja   m1 = 0
>>>>>[-<<<<<+>>>>>]          // m1 = m6   ja   m6 = 0
<<<<[->>>>>>>+>+<<<<<<<<]    // m9 = m10 = m2   ja   m2 = 0
>>>>>>>>[-<<<<<<<<+>>>>>>>>] // m2 = m10   ja   m10 = 0
<<<<<                        // valitaan m5

// Muunnetaan m5 oktaaleiksi paikkoihin m6 m7 m8 ja tulostetaan
// (m6 = m5)   ja   (m7 = 4 * m5)   ja   (m8 = 32 * m5)   ja   (m5 = 0)
// Eli (m8 / 32 = m5 mod 8)   ja   (m7 / 4 = m5 mod 64)
[->+>++++>++++++++++++++++++++++++++++++++<<<]
// (m5 = m7 / 4)   ja   (m6 = m6 miinus m7 / 4)   ja   (m7 = 0)
>>[----<<+>->]
// (m7 = m8 / 32)   ja   (m8 = 0)
>[--------------------------------<+>]
// (m8 = m7)   ja   (m5 = m5 miinus m7)   ja   (m7 = 0)
<[->+<<<->>]
// (m7 = m6 / 8)   ja   (m6 = 0)
<[-------->+<]
// (m6 = m5 / 8)   ja   (m5 = 0)
<[-------->+<]
// (m5 = m7 / 8)   ja   (m7 = 0)
>>[--------<<+>>]
// tulostettavaan muotoon
++++++++++++++++++++++++++++++++++++++++++++++++
[-<<+>+>>+<]
// Tulostetaan väli m13:stä ja sitten oktaaliluku
>>>>>>.<<<<<<
<<.>.>>.

// Sama toiselle luvulle paikoissa m9 m10 m11 m12
>[->+>++++>++++++++++++++++++++++++++++++++<<<]
>>[----<<+>->]
>[--------------------------------<+>]
<[->+<<<->>]
<[-------->+<]
<[-------->+<]
>>[--------<<+>>]
++++++++++++++++++++++++++++++++++++++++++++++++
[-<<+>+>>+<]
>>.<<
<<.>.>>.

// Takaisin paikkaan m0 ja silmukan alkuun
<<<<<<<<<<<
<]

Tässä on vielä sama koodi tiiviimmässä muodossa:

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

Koodivinkki Fibonaccin sarja sisältää yksinkertaisemmin vain lukujen laskennan ilman muunnosta oktaalimuotoon.

Loppusanat

Siinä oli Brainfuck. Se on erittäin vaikea kieli, jos sillä haluaa todella saada jotakin aikaan. Erityisen hyvin se soveltuu aivojumppaan, koska yksinkertaisiakin asioita joutuu pähkäilemään melkoisesti.

Lisätietoa sekä runsaasti linkkejä löytyy mm. esoteerisiin kieliin erikoistuneelta sivustolta esolangs.org.

Lauri Kenttä, 26.8.2006