Keskustelu: Koodit: Befunge: Fibonaccin lukujono

Brainfuck nosti täällä vähän aikaa sitten päätään, kun water_flea ja Metabolix lähettivät kaksi eri Brainfuck-toteutusta Fibonaccin lukujonon laskemiseen. No, kuten kaikki tiedämme, Brainfuck ei suinkaan ole ainoa nk. esoteerinen ohjelmointikieli. Kolmesta kanonisesta ensimmäinen on vuoden 1972 INTERCAL, toinen on vuonna 1993 laadittu Brainfuck, ja kolmas on samana vuonna kehitetty Befunge. Brainfuck on kuitenkin se kieli, joka on useimmiten ohjelmoijien huulilla, kun tahdotaan vitsailla ohjelmointikieliin liittyen.

Se historiasta. Tämän koodivinkin tarkoituksena on tuoda esille paljolti ikätoverinsa Brainfuckin varjoon jäänyt Befunge.

Befungen kenties mielenkiintoisin ja ainutlaatuisin ominaisuus on se, että komentoja ei ajeta koko ajan samassa järjestyksessä, vaan ajosuunta määräytyy eri komentojen avulla. Lähdekoodi jakautuu kaksiulotteiselle (Funge-98-standardi sallii oikeastaan kaikki yksi-tai-useampiulotteiset, mutta yleensä käytetään vain kaksiulotteista, Befungea) ruudukolle, jota pitkin liikkuu yksi (Concurrent Funge-98 -standardi sallii useammankin) instruction pointer eli IP. IP aloittaa kohdasta (0, 0) eli tiedoston alusta ja oletusarvoisesti liikkuu ruudun kerrallaan oikealle. Ennen IP:n liikuttamista sen kohdalla oleva komento ajetaan.

Alunperin komentoja oli 36; uudemman Funge-98-standardin myötä niitä on useampia. En siis listaa niitä tässä, enkä myöskään selitä niitä, joita käytetään allaolevassa ohjelmassa, vaan selitän vain ohjelman toiminnan sekä IP:n käyttäytymisen. Komennoista, ja Befungesta muutenkin, voi ottaa selvää Funge-98-spesifikaatiosta.

Vielä eräs tärkeä asia, joka kannattaa tietää Befungesta ohjelman ymmärtämiseksi: kaikkea dataa käsitellään pinossa. Pinohan on LIFO (Last In, First Out) -tietorakenne, mikä tarkoittaa sitä, että siihen viimeksi laitettu alkio tulee sieltä ensimmäisenä ulos. Funge-98-standardi sallii useamman pinon käytön, mutta helpompi tapa on useimmiten käyttää vain yhtä pinoa ja tarvittaessa kirjoittaa dataa suoraan lähdekoodiin p- ja g-komentojen avulla.

Allaoleva Fibonacci-ohjelma käyttää Funge-98-komentoja k ja [, joten sen pyörittämiseen tarvitaan Befunge-98-yhteensopiva tulkki tai kääntäjä. (Paras on tietenkin omani, jonka kirjoitin, koska kunnollista Concurrent Funge-98 -tulkkia ei netistä tuntunut löytyvän.)

Itse ohjelmaan. Ensin laitetaan tekstiä pinoon; vasemmalta oikealle mentäessä tekstin pitää olla oikealta vasemmalle kirjoitettua ja päinvastoin, jos sen haluaa tulostuvan oikein päin. Teksti tulostetaan iteroimalla k-komennolla merkintulostusta, minkä jälkeen pyydetään käyttäjältä &-komennolla luku. Virheentarkistus on sisällytetty ohjelmaan: jos käyttäjä antaa EOF:n (End Of File) tai syöte ei muuten vain toimi, & kääntää IP:n suunnan, minkä jälkeen se ohjautuu tulostamaan tekstin "Ei sitten." ja ohjelma pysäytetään. Samoin käy, jos käyttäjä antaa nollan, joskin eri tavalla: käytetään _-komentoa tarkistukseen. Jos kaikki kävi hyvin, saatu luku laitetaan kohtaan (0, 0) --- eli oikeastaan siellä jo olevan lainausmerkin päälle, mutta sillä ei ole väliä, koska emme sitä enää tarvitse.

Tämän jälkeen päästäänkin varsinaiseen Fibonacci-lukujen laskemiseen. Sarjahan alkaa ykkösestä, joten se laitetaan pinoon. Seuraa silmukka, jossa:

1. Vaihdetaan pinon kahden päällimmäisen luvun paikkaa. Otettaessa lukua tyhjästä pinosta sieltä tulee nolla, joten ensimmäisellä kierroksella tämä tarkoittaa vain, että laitetaan nolla pinon päälle.
2. Laitetaan pinon päällimmäinen luku muistiin kohtaan (3, 5), mutta pidetään se myös pinossa. Tämä on "kaksi kertaa sitten laskettu luku", minkä takia sen pitää olla ensimmäisellä kahdella kerralla nolla. Ihan ensimmäisellä kierroksella se ilmestyi jo Swap-komennon myötä (yhtä hyvin olisi voitu kirjoittaa "01" ennen silmukkaa eikä vain "1"), tavallisesti se haetaan silmukan lopussa.
3. Summataan pinon kaksi päällimmäistä lukua. Ensimmäisellä iteraatiolla nämä ovat 1 ja 0, seuraavalla 0 ja 1, ja sitä seuraavalla 1 ja 1.
4. Tulostetaan saatu summa: seuraava Fibonaccin luku.
5. Otetaan luku kohdasta (0, 0) --- eli laskettavien lukujen määrä --- pinon päälle.
6. Miinustetaan siitä luvusta ykkönen, ja jos se on nolla, lopetetaan ohjelma.
7. Laitetaan kierrosluku takaisin kohtaan (0, 0).
8. Haetaan luku kohdasta (3, 5) pinon päälle.

Venyipäs teksti pitkäksi... toivottavasti tästä on jollekulle hyötyä ja/tai hupia.

" ?naateksal aukul niccanob"v   Copyleft Matti "Deewiant" Niemenmaa
v p00 :&v#,k*57 "Montako Fi"<   2006-06-12 - 2006-06-13
v       <
[_a".nettis iE"ak,@   Joku kuitenkin luulee olevansa fiksu ja
                      antaa nollan tai EOF:n.
> 1 >\:35p +:. 00g1-:#v_a,@
    ^   g53       p00 <

Vihdoinkin joku käyttää Befungea! Brainfuck on tylsää, sehän muistuttaa ihan asmia. Befungessa on sen sijaan jotain kekseliästä.

Musta tuntuu siltä, että tällaset kielet on kehitetty sellasten ihmisten toimesta, jotka ovat olleet niin rutinoituneita kirjottamaan ohjelmansa naputtelemalla pelkkiä nollia ja ykkösiä, että ovat halunneet hieman lisää haastetta o_O.

"Pah Pöh! Minäpäs kirjoitan oman BeFunge-98 -tulkkini!" sanoi Hän.

lainaus:

Musta tuntuu siltä, että tällaset kielet on kehitetty sellasten ihmisten toimesta, jotka ovat olleet niin rutinoituneita kirjottamaan ohjelmansa naputtelemalla pelkkiä nollia ja ykkösiä, että ovat halunneet hieman lisää haastetta o_O.

Tai sit ne on vaan halunnu jotain kivaa tekemistä ja on päättäny tehdä vitsinä ihan tyhmän ohjelmointikielen.
Joo, pitäs kokeilla varmaan tätäkin. Brainfuckia oon kokeillu jo, mut en paljo muita tämmösiä kieliä.

Tehkää Fibonaccin lukusarja seuraavaksi Malbolgella. ;)

Malbolge on tylsä; kielenä se on loppujen lopuksi aika simppeli, siitä on vain tehty hemmetin vaikeakäyttöinen. Kun dekryptaa ohjelmat ns. normalisoituun muotoon, näkee, että ei se oikeastaan kovin kummoinen ole. Käsittääkseni Malbolgea onkin helpointa koodata kirjoittamalla ensin normalisoitua koodia ja sitten pistää joku softa kryptaamaan se tulkin ymmärtämään muotoon.

Funget ovat kivempia, niissä on sentään jotain uutta ideaa. Befunge on kenties käyttökelpoisin esoteerinen kieli, johon olen törmännyt. Harvalla sellaisella on kirjoitettu esim. Hunt the Wumpus -peli.

Jos joku muuten jaksaa pelleillä tuon tekemäni tulkin kanssa, bugeista ym. saa ilmoittaa minulle.

Gwaur kirjoitti:

Tehkää Fibonaccin lukusarja seuraavaksi Malbolgella. ;)

tai Headachella

Törmännytkään pitkään aikaan Befunge-koodeihin. Noh, aattelin tehä Befunge-93 version tästä. Ei yhtä nätti, mutta failsafe perus EW-ehoilla.

p110p" :iF ynam woH">,#$:_&1-: v
v+p00.::g01g00_@#<,.0,:+91`0p02<
>10p20g1-:20p91+,^