Malbolge

Malbolge on avoimen lähdekoodin periaatteella toimiva esoteerinen ohjelmointikieli. Sen kehitti Ben Olmstead vuonna 1998. Malbolge on saanut nimensä Danten "Jumalaisen näytelmän" kahdeksannen Helvetin kerroksen mukaan.

Malbolgen lähtökohtana on, että se on mahdollisimman vaikeasti ohjelmoitava. Kuitenkin muutamilla tempuilla sen saa ymmärrettäväksi.

Malbolge-ohjelmointi

Malbolge on niin vaikeasti ymmärrettävä, että sen suunnittelusta kului kaksi vuotta ennen kuin ensimmäinen järkevä Malbolge-ohjelma tehtiin. Tosin tällöinkään ohjelmaa ei koodannut ihminen, vaan se generoitiin Andrew Cooken ohjelmoimalla sädehakualgoritmilla (beam search).

Vuonna 2000 Anthony Youhas esitti blogissaan (Arkistoitu – Internet Archive) päihittäneensä Malbolgen vaikeudet ja osaavansa käyttää sitä. Hän osoitti tämän tekemillään kolmella ohjelmalla. Hän ei kuitenkaan paljastanut ohjelmointimetodiaan.

Malbolgen toiminta

Malbolge on konekieli, joka toimii kolmikantaisessa (ternary) järjestelmässä, ei binäärissä.

Malbolgessa on kolme rekisteriä, a, c ja d, jotka ovat kuin muuttujia muissa kielissä. Kun ohjelma alkaa, kaikkien kolmen arvo on 0.

  • c:llä on erityinen merkitys: Se osoittaa nykyiseen osoitteeseen.

Osoitinnotaatio

d-rekisterissä voi olla muistiosoite; tällöin [d] on kyseisen osoitteen sisältämä arvo. [c] toimii vastaavasti.

Muisti

Malbolgen virtuaalikoneessa on 59049 muistisanaa, joista kussakin voi olla 10 merkkiä pitkä kolmikantainen luku. Jokaisella muistipaikalla on osoite väliltä 0 - 59048, ja ne voivat kukin sisältää luvun väliltä 0 - 59048 (desimaalinen). Jos sanan arvo saavuttaa 59049:n, se korvataan 0:lla.

Ennen kuin Malbolge-ohjelman suoritus aloitetaan, ohjelma ladataan tulkin muistin alkuun. Välilyöntimerkit unohdetaan, ja jotta ohjelmoinnista tulisi vaikeampaa, koko muun ohjelman tulee koostua alla mainituista merkeistä. Loppuosa muistista täytetään "crazy operation"ia käyttäen kaavalla [m] = crz [m - 2], [m - 1].

Käskyt

Malbolge päättää suoritettavan käskyn kaavalla ([c]+c) mod 94. Lopputulos kertoo, mitä tulkki tekee:

Kuvaus
([c] + c) % 94:n arvo Esitetty käsky Selitys
4 jmp [d] + 1 Ohjelman suoritus hyppää osoitteeseen [d] +1.
5 out a Tulostaa a:n ASCII-koodia vastaavan merkin ruudulle.
23 in a Lukee merkin ja sijoittaa sen ASCII-koodin a:han. Rivinvaihtomerkit (sekä CR että LF) ovat 10. Tiedostonlopetusarvo on 59048.
39 rotr [d]
mov a, [d]		 Pyörittää [d]:n arvoa oikealle yhdellä kolmikantaisella numerolla (0002111112 muuttuu 2000211111:ksi). Tallettaa tuloksen sekä [d]:hen että a:han.
40 mov d, [d] Kopioi arvon [d]:stä d:hen.
62 crz [d], a
mov a, [d]		 Tekee "crazy operationin" arvoilla [d] ja a. Tallettaa tulokset sekä [d]:hen että a:han.
68 nop Ei tee mitään.
81 end Lopettaa ohjelman.
Muut arvot eivät tee mitään. Niitä ei hyväksytä varsinaisessa ohjelmassa, mutta ne toimivat jos tulos syntyy ohjelman sisällä.

Kunkin käskyn suorituksen jälkeen käsky kryptataan (ks. alla), jotta se ei tee samaa ensi kerralla, ellei juuri ole suoritettu hyppyä. Heti hypyn jälkeen kryptataan sen sijaan hypyn kohdetta edeltävä käsky. Kryptauksen jälkeen rekisterien c ja d arvoa kasvatetaan yhdellä ja seuraava käsky suoritetaan.

Kryptaus

Jokaisen konekäskyn suorittamisen jälkeen [c]:hen sijoitetaan arvo enc(c mod 94), missä enc(x) on seuraava funktio (valitse x taulukosta, enc(x) on sen alla olevan merkin ASCII-koodi): 

0000000000111111111122222222223333333333444444444455555555556666666666777777777788888888889999
0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123
----------------------------------------------------------------------------------------------
9m<.TVac`uY*MK'X~xDl}REokN:#?G"i@5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1CB6v^=I_0/8|jsb

Crazy operation

Jokaiselle syötteiden numeroparille suoritetaan seuraava kuvaus tuloksen ternaarinumeron saamiseksi. Esimerkiksi crz 0001112220, 0120120120 = 1001022211.

Crazy operation
crz Syöte 2
0 1 2
Syöte 1 0 1 0 0
1 1 0 2
2 2 2 1

Vaikeus

  • Malbolge perustuu ternaariseen koodiin.
  • Kaikki ohjelmat koostuvat pelkästään numerosekvenssistä.
  • Opkoodien käyttö lähdekoodissa on kielletty.
  • Malbolgen tulkissa on kolme rekisteriä, joiden nimet ovat "c" (code, koodi), "d" (data), ja "a" (akkumulaattori).
  • Tulkissa on myös muisti, jokainen muistin sana voi säilyttää 10 trinaarinumeroa pitkän arvon.

Esimerkkiohjelma

Tämä Malbolge-ohjelma kirjoittaa "Hello world": 

 (=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
 hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<

Aiheesta muualla

  • http://www.antwon.com/other/malbolge/malbolge.txt (Arkistoitu – Internet Archive)
  • http://www.lscheffer.com/malbolge_interp.html
  • Kuvaus Andrew Cooken algoritmista, jolla luotiin ensimmäinen Malbolge -ohjelma (Arkistoitu – Internet Archive)
  • Lou Schefferin Malbolge -analyysi
  • http://scienceblogs.com/goodmath/2007/01/hellish_programming_malbolge.php (Arkistoitu – Internet Archive)
  • Malbolgeohjelmointi[vanhentunut linkki]
  • Anthony Youhanin blogi (Arkistoitu – Internet Archive)
  • "99 bottles" -sanat Malbolgeohjelmoituna