Esoteeriset ohjelmointikielet ja reaalilukutuki

(1)

Niko Järvinen

ESOTEERISET OHJELMOINTIKIELET JA REAALILUKUTUKI

Informaatioteknologian ja viestinnän tiedekunta

Kandidaattitutkielma

Tammikuu 2021

(2)

Tiivistelmä

Niko Järvinen: Esoteeriset ohjelmointikielet ja reaalilukutuki Kandidaattitutkielma

Tampereen yliopisto

Tietojenkäsittelytieteiden tutkinto-ohjelma Tammikuu 2021

Esoteeriset kielet ovat jo pitkään tarjonneet moninaisia haasteita ohjelmoijien rat- kaistavaksi. Perinteisistä ohjelmointikielistä poiketen, monet esoteeriset kielet pyr- kivät olemaan haastavia tai jopa mahdottomia käyttää toimivien ohjelmien toteuttamiseen. Tämän takia kielistä on usein jätetty pois Turingin koneen tavoin lähes kaikki tarpeeton, kuten tuki reaaliluvuille ja monimutkaisille aritmeettisille operaatioille. Esoteeriset kielet ovat kasvattaneet suosiotaan erityisesti koodigolfaajien jou- kossa, jonka vuoksi tarve entistä monimutkaisemmille yleiskäyttöisille algoritmeille on kasvanut. Tällaisia algoritmeja ovat muun muassa tässä tutkielmassa käsiteltävät reaalilukujen aritmeettiset operaatiot.

Tutkielman tavoitteena on teorian ja käytännönläheisten toteutusten avulla selvittää, mikä on intuitiivisuuden kannalta paras lähestymistapa reaalilukujen aritmeettisten operaatioiden toteuttamiselle tutkielmassa esitellyillä esoteerisilla kielil- lä. Tämän lisäksi työ pyrkii luomaan käsityksen siitä, millaiset kielten ominaisuudet parantavat tai huonontavat erinäisten lähestymistapojen intuitiivisuutta ja miten kielten asettamia rajoituksia voi helpottaa.

Tutkielmassa perehdytään kahteen yleisesti käytössä olevaan reaalilukuesi- tykseen; kiinteän pisteen numeroihin ja IEEE 754 -standardin mukaisiin perustarkkuuden liukulukuihin. Tutkielmassa pohditaan eri reaalilukuesitysten aritmeettisten operaatioiden toteutusten käytännöllisyyttä erityisesti toteutuksen muistinhallin- nan, intuitiivisuuden ja helppouden näkökulmista. Eri reaalilukuesityksistä kiinteän pisteen numerot osoitetaan liukulukuja intuitiivisemmiksi Brainfuckissa ja Befunge- 93:ssa, toisin kuin Jellyssä, jossa on sisäänrakennettu tuki liukuluvuille ja niiden aritmeettisille operaatioille.

Tutkielmaa varten Brainfuckilla toteutettiin kiinteän pisteen numeroiden yhteen- ja kertolaskualgoritmi, jotka osoittavat ehdotetun konseptin toimivuuden. Tämän li- säksi operaatioista haastavampi, kertolasku, toteutettiin Befunge-93:lla kiinteän pisteen numeroille osoittamaan kielten erilaiset tarpeet ongelmanratkaisussa käytetyille lähestymistavoille.

Avainsanat: Brainfuck, Befunge-93, esoteeriset ohjelmointikielet, IEEE 754, liukuluvut, kiinteän pisteen numero, aritmeettiset operaatiot

Tämän julkaisun alkuperäisyys on tarkastettu Turnitin OriginalityCheck -ohjelmalla.

(3)

Sisällysluettelo

1 Johdanto 1

2 Tutkimusmenetelmä 3

3 Reaaliluvut- ja aritmetiikka 3

3.1 Reaalilukujen esitysmuotoja . . . 4

3.1.1 Liukuluvut - IEEE 754 . . . 4

3.1.2 Kiinteän pisteen numerot . . . 5

3.2 Aritmeettiset operaatiot kiinteän pisteen numeroille . . . 6

4 Esoteeriset ohjelmointikielet 8 4.1 Turing-täydellisyys . . . 9

4.2 Brainfuck . . . 9

4.3 Befunge-93 . . . 10

4.4 Jelly . . . 11

4.5 Makrokielet ja BFIMDM . . . 12

5 Reaaliluvut esoteerisilla kielillä 14 6 Keskustelu 15 7 Yhteenveto 16 8 Liitteet 21 8.1 Kahden kiinteän pisteen numeron yhteenlasku Brainfuckilla . . . 21

8.2 Kahden kiinteän pisteen numeron kertolasku Brainfuckilla . . . 22

8.3 Kahden kiinteän pisteen numeron kertolasku Befunge-93:lla . . . 25

(4)

1. Johdanto

Tässä tutkielmassa perehdytään yleisesti esoteerisiin ohjelmointikieliin, reaalilukujen esitystapoihin muistin ja prosessoinnin näkökulmasta sekä alkeellisten aritmeettisten operaatioiden toteutukseen. Tutkielmassa pohditaan myös parasta lähesty- mistapaa reaalilukujen aritmeettisten operaatioiden toteutukselle tarkoituksellisesti haastavissa kielissä.

"Sanaesoteerinen on johdettu muinaiskreikan sanastaesoterikos, joka tarkoittaa sisäpiiriin kuulumista ja alunperin sillä viitattiin Pythagoraan salaisiin opetuksiin"

(Etymologyonline Esoteric, 2020). Kielen määrittely esoteeriseksi tapahtuu arvioi- malla kielen käytännöllisyyttä ja semantiikkaa. Kielen epäkäytännöllisyys ja seman- tiikan liiallinen monimutkaisuus ovat kuitenkin jääneet määrittelemättä (Anureev et al., 2008). Esoteerisuus ei myöskään rajoitu pelkästään tarkoituksellisesti esoteeri- siksi tehtyihin ohjelmointikieliin tai teknologioihin, vaan myös liukulukuaritmetiikka on monen mielestä esoteerinen aihe (Goldberg, 1991).

Yksi tunnetuista esoteeristen kielten käyttökohteista on koodigolfaus (engl. code golfing). "Koodigolfaus viittaa ongelmanratkaisuun, jossa pyritään käyttämään mahdollisimman vähän merkkejä, esimerkiksi kirjoittamalla lyhin mahdollinen koo- di."^[1] Koodigolfaus parantaa kehittäjän kykyä sekä ajatella laatikon ulkopuolelta että oppia ja käyttää kielten harvemmin käytettyjä ominaisuuksia. (Ahire, 2020).

Kasurisen (2016) mukaan esoteeriset ohjelmointikielet voidaan jakaa viiteen pää- luokkaan; syntaksisesti minimaalisiin, uusiin konsepteihin, omituisuuksiin, teemalli- siin ja vitseihin. Syntaksisesti minimaaliset kielet pyrkivät minimoimaan käskyjen tai toteutetun ohjelman sisältämien merkkien määrän (vrt. Nasyrova & Molodovs- kiy, 2017).Uusissa konsepteissa kieli itsessään on toteutettu jollain uudella menetel- mällä.Omituisuudet on toteutettu tavallisuudesta poikkeaviksi tai erityisen vaikeiksi käyttää. Teemalliset on rakennettu jonkin tietyn teeman ympärille, kuten näytel- män käsikirjoituksen tai fiktiivisen kielen muotoon. Vitsit eivät välttämättä toteuta toimintoja yhtä käskyä enempää. Esimerkiksi täysinihilistinen kieli nih kieltäytyy minkä tahansa käskyn suorittamisesta. (Kasurinen, 2016).

Nasyrova & Molodovskiy (2017) puolestaan tarkentavat jaottelua viittaamalla syntaksisella minimalismilla minimaaliseen komentojoukkoon, josta he irroittavat merkkimäärällisesti minimaaliset (engl. brevity) omaksi luokakseen. Näin ensim- mäiseen luokkaan kuuluu muun muassa Brainfuck. Merkkimäärällisesti minimaalisiin puolestaan kuuluvat Jellyn, GolfScriptin ja Pythin kaltaiset koodigolfauspai- notteiset kielet. Näissä kielissä voi olla jopa 256 yksimerkkistä komentoa, mutta

[1]Vapaa suomennos: "Code Golfing refers to solving a problem by making use of the least number of characters i.e. by writing the shortest code as possible" (Ahire, 2020).

(5)

toteutettu ohjelma on melko usein alle 10 merkkiä pitkä.

Brainfuck kuuluu yllämainituista pääluokista syntaksisesti minimaalisiin sup- pean komentojoukon vuoksi sekä omituisuuksiin hyödyllisten ohjelmien toteutuksen haasteellisuuden vuoksi. Tutkielmassa esitellään myös Befunge-93 sekä Jelly.

Befunge-93:lla ohjelmoidaan käyttäen kaksiulotteista syntaksia, jonka uskotaan ol- leen kielen julkaisuvuonnauusi konsepti (Morr, 2015). Jelly puolestaan soveltuu erityisen hyvin koodigolfaukseen sen merkkimäärällisesti tehokkaan syntaksin vuoksi.

Vaikka koodigolfaukseen hyvin soveltuvat tai siihen ensisijaisesti suunnitellut kielet ovat usein hankalasti lähestyttäviä aloittelijoille, ei haasteellisuus kuitenkaan yleen- sä ole itseisarvo syntaksia ja ominaisuuksia suunniteltaessa. Tämän vuoksi Jelly kuulunee vain merkkimäärällisesti minimaalisiin.

Tutkielman tavoitteena on selvittää, miten reaalilukujen aritmeettisten operaatioiden toteutusta kannattaa lähestyä esoteerisilla kielillä, miten kielten asettamia rajoitteita voidaan kiertää ja mitkä reaalilukuesitykset soveltuvat parhaiten yksin- kertaistetun ohjelmointiympäristön liukulukutoteutuksiin. Pohjatyötä tehdessä ai- hepiiristä ei löytynyt vastaavanlaisia tieteellisiä artikkeleita eikä kilpailevia toteu- tuksia. Tutkielman aihe on tärkeä, sillä se täydentää teoreettisen tutkimuksen auk- koa sekä tarjoaa oletettavasti ensimmäisenä Brainfuck-algoritmit kiinteän pisteen numeroiden kahdelle aritmeettiselle operaatiolle.

Tutkielmassa esitetään lähestymistavat kiinteän pisteen reaalilukujen aritmeettisten operaatioiden toteutukselle Brainfuckilla, Befunge-93:lla sekä Jellyllä ja osoitetaan ehdotettujen lähestymistapojen toimivuus. Befunge-93:n osalta vain kertolasku on toteutettu. Kielten merkittävien erojen johdosta tutkimuskysymykseen ei ole yhtä yleistettävissä olevaa ratkaisua, minkä vuoksi ongelmaa lähestytään hyvin käytännönläheisesti ja kielikohtaisesti. Tutkielma pyrkii ensisijaisesti etsimään intuitiivista ratkaisuehdotusta ongelmaan jättäen tehokkuuden toissijaiseksi tavoitteek- si. Intuitiivisuuden osoittamisen vuoksi tutkielmassa esitellään myös niin kutsuttu makrokieli, BFIMDM. Sen avulla koodin toiminnan visualisointi kaksiulotteisessa matriisissa onnistuu tutkielmaa varten toteutetulla BFIMDM-tulkilla^[2]. Toteutuk- sen kannalta triviaaliksi ongelmaksi katsottiin myös reaalilukuesitysten etumerkilli- syys, minkä vuoksi toteutukset käsittelevät binäärisyötteitä etumerkittöminä kiin- teän pisteen lukuina.

Brainfuckilla hyväksi lähestymistavaksi osoitetaan kiinteän pisteen binääriluku- jen laskeminen allekkain, Befunge-93:lla kokonaislukupinon hyödyntäminen ja Jel- lyllä triviaali sisäänrakennettujen liukulukuoperaatioiden käyttö. Lähestymistapo- jen erojen perusteena on kielten suuret eroavaisuudet. Brainfuckilla muistipaikko-

[2]https://github.com/b10011/BFIMDM

(6)

jen maksimiarvo rajoittaa logiikkaporttiratkaisua toisin kuin allekkain laskettaessa, jolloin kyetään kertomaan keskenään jopa 128-bittisiä kokonaislukuja tai kiinteän pisteen numeroita. Befunge-93:lla välimuistina voi käyttää joko kokonaislukupinoa tai suoritettavaa ohjelmakoodia, sillä kieli mahdollistaa ajonaikaisen lähdekoodin muokkaamisen. Näistä jälkimmäinen ei kuitenkaan ole käytännöllinen, eikä helposti toteutettavissa, jonka vuoksi pino todetaan parhaaksi ratkaisuksi. Jellyssä puolestaan reaalilukutuki on toteutettu Jellyn tulkkia tulkkaavan CPython-tulkin tieto- tyyppejä apuna käyttäen, jonka liukulukutyyppi "float" tyypillisesti käärii sisäänsä 64-bittisen kaksoistarkkuuden liukuluvun. Jellyn osalta päädytään esittämään vain triviaalit ratkaisut yhteen- ja kertolaskun osalta.

Tulevissa luvuissa perehdytään reaalilukujen esitysmuotoihin (luku 5), niiden aritmeettisiin operaatioihin (luku 3) ja käydään läpi yllä mainituista esoteerisistä ohjelmointikielistä Brainfuck (luku 4.2), Befunge-93 (luku 4.3) ja Jelly (luku 4.4).

Tämän jälkeen pohditaan kielikohtaisia yksityiskohtia, jotka vaikuttivat toteutuseh- dotuksen valintoihin (luku 6) sekä esitetään tutkielmasta yhteenveto (luku 7).

2. Tutkimusmenetelmä

Tutkielma on toteutettu pohjautuen käytännön toteutukseen, jonka kehityksen tu- kena käytettiin tässä tutkielmassa esiteltyjä lähteitä. Lähteistä koottiin kirjallisuus- katsaus, johon yhdistettiin pohdintaa käytännön toteutukseen liittyneistä valinnois- ta.

Lähteitä haettiin Andor-hakupalvelun, Google Scholarin sekä Googlen hakuko- neen avulla. Andor-hakupalvelussa hakutermeinä käytettiin muun muassa"esoteric programming language", "brainfuck", "floating point arithmetic", "processor logic gate binary multiplier" ja "binary n-bit multiplication". Google Scholarista oleelli- simmat artikkelit löytyivät hakusanalla "esoteric programming languages". Lisäksi lähteitä haettiin artikkelien ja kirjojen lähdeluetteloista.

Tutkielman teknisen luonteen johdosta lähteitä etsittiin tarpeen vaatiessa erinäi- siltä epätieteellisiltä verkkosivustoilta. Näistä merkittävimpänä GitHubin ohella oli esoteeristen kielten ohjelmoijien ja niillä ohjelmoivien yhteisö, esolangs.org. Muiden muassa Temkinin (2017) mukaan esolangs.org on suurin esoteeristen kielten wiki- ja arkistosivusto.

3. Reaaliluvut- ja aritmetiikka

Tässä kappaleessa käsitellään reaalilukujen esitysmuodoista liukulukuja (engl. floating- point number) sekä kiinteän pisteen numeroita (engl. fixed-point number) (luku 3.1).

(7)

Reaalilukuesitysten jälkeen kappaleessa käsitellään aritmeettisten operaatioiden to- teutuksia kiinteän pisteen numeroille (luku 3.2). Kappaleen tavoitteena on havainnollistaa sekä eri liukulukuesitysten että niiden aritmeettisten toteutusten intuitiivisuus.

3.1. Reaalilukujen esitysmuotoja

Tässä aliluvussa käsitellään kahta yleistä tapaa esittää reaalilukuja binäärimuodos- sa. Ensin esitellään perustarkkuuden (engl. single-precision) 32-bittisiä IEEE 754 -standardin mukaisia liukulukuja (luku 3.1.1), jonka jälkeen käsitellään 32-bittisiä etumerkittömiä kiinteän pisteen numeroita (luku 3.1.2).

3.1.1. Liukuluvut - IEEE 754

m·β^e (1)

(Muller et al., 2010)

Liukulukujen toimintaperiaate muistuttaa tieteellistä notaatiota. Liukulukujen tapaan, tieteellisessä notaatiossa arvo esitetään reaalilukuisena mantissana m, joka kerrotaan eksponenttiin e korotetulla kantaluvulla β (ks. kaava 1). 10-kantaisessa järjestelmässä mantissa on välille [1, 10) tai (-10, -1] eksponentin avulla skaalattu arvo. Arvoa 0 esitettäessä mantissa saa kuitenkin poikkeuksellisesti arvon 0 (Muller et al., 2010).

Liukulukujen etuna kiinteän pisteen numeroihin verrattuna on kyky säilöä sekä erittäin suuria, että erittäin pieniä lukuja. Aritmeettisten operaatioiden toteuttaminen liukuluvuille on kuitenkin kiinteän pisteen lukuja työläämpää, sillä mantissojen välisten operaatioiden suorittamisen lisäksi tulee myös erot lukujen eksponenteissa ottaa huomioon.

IEEE 754 standardin aiemmissa versioissa ei ole määritelty hyväksyttyjä kanta- lukuja. Uudempi IEEE 754-2008 tiukensi aiempia versioita asettamalla kantaluvulle hyväksytyiksi arvoiksi 2 ja 10 (Muller et al., 2010).

Kantaluvun 2 32-bittinen perustarkkuuden versio koostuu etumerkistä, ekspo- nentista sekä mantissasta. Etumerkki on kokonaislukujen tavoin yksibittinen, eksponentti 8-bittinen ja mantissa 23-bittinen. Mantissassa voidaan kuitenkin säilöä 24- bitin verran informaatiota, sillä kaksikantaisessa järjestelmässä normalisoidun mantissan merkitsevin bitti (engl. most significant bit) on lähes aina 1, jonka vuoksi se jätetään säilömättä. Ainoat luvut, joissa mantissan merkitsevin bitti ei ole 1, ovat +0.0 ja -0.0. Nämä poikkeukset tunnistaa siitä, että ne sisältävät etumerkin lisäksi pelkkiä nollia sisältävän eksponentin ja mantissan. (Muller et al., 2010).

(8)

Perustarkkuuden liukuluvun binääriesitys saadaan muunnettua reaalilukumuotoon lukemalla yksibittinen etumerkki (ks. taulukko 1), 8-bittinen eksponentti (ks.

taulukko 2) ja 23-bittinen mantissa (ks. taulukko 3). Etumerkin arvo 0 merkitsee positiivista ja 1 puolestaan negatiivista lukua. Eksponentin arvo luetaan etumer- kittömänä kokonaislukuna, josta vähennetään eksponentin epäkeskisyysarvo (engl.

bias), 127. Mantissa luetaan etumerkittömänä 23-bittisenä kiinteän pisteen numero- na, jonka kaikki bitit ovat binääripisteen oikealla puolella. Tämän jälkeen mantissaan lisätään aiemmin bittijonon edestä poistettu 1. Lopullinen reaalilukuarvo saadaan kertomalla mantissa m ja eksponenttiin e korotetulla kantaluvulla β (ks. kaava 1) ja tekemällä luvusta positiivinen tai negatiivinen etumerkin arvon mukaan.

Taulukoissa 1, 2 ja 3 esitetyn bittijonon reaalilukuesitys on positiivinen (ks. taulukko 1), sen eksponenttiosan arvo on 2^137−127 = 2¹⁰ (ks. taulukko 2) ja mantissan arvo on noin 1.20563185214996338 (ks. taulukko 3). Edellä mainituissa taulukoissa esitetyn bittijonon absoluuttinen reaalilukuarvo on noin 1.20563185214996338·2¹⁰ (ks. kaava 1), eli noin 1234.5670166015625. Arvoa ei muuteta negatiiviseksi etumerkin bitin ollessa nolla.

Taulukko 1. Luvun 1234.567 etumerkki.

0

Taulukko 2.Luvun 1234.567 eksponentti.

1 0 0 0 1 0 0 1

Taulukko 3. Luvun 1234.567 mantissa.

0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1

3.1.2. Kiinteän pisteen numerot

Kiinteän pisteen numeroissa pisteen sijaintiin ei voi vaikuttaa eksponentilla. Pisteen sijainnin muuttumattomuus helpottaa aritmeettisten operaatioiden toteuttamista, mutta aiheuttaa myös sen, ettei liukulukuihin verrattuna yhtä suurten ja pienten lukujen esittäminen samalla bittimäärällä ole välttämättä mahdollista.

Tässä kappaleessa käsitellään 32-bittistä kiinteän pisteen numeroa, jossa sekä kokonaislukuosa, että murto-osa koostuu 16:n bitin sarjoista. Etumerkki on sisällytetty

(9)

kokonaislukuosan alkuun, jolloin kokonaisluvun suuruutta kuvaavat vain jälkimmäi- set 15 bittiä. Formaatti kokonaislukuosassa on sama kuin 16-bittisessä etumerkilli- sessä kokonaisluvussa (ks. taulukko 4). Murto-osa koostuu 16:sta bitistä, jonka voi muuntaa reaalilukumuotoon jakamalla arvolla 2^N, jossa N on bittien määrä murto- osassa. Tällöin taulukoissa 6 ja 7 esitetty kiinteän pisteen numeron arvo on noin 1234 + 0.5670013427734375, eli noin 1234.567. Kiinteän pisteen numeroiden muuntaminen onnistuu kokonaislukuja murto-osan luonteen vuoksi myös käsittelemällä koko bittijonoa etumerkillisenä kokonaislukuna ja jakamalla se arvolla 2^N, jossa N on bittien määrä murto-osassa. Tämä on seurausta siitä, että arvon jakaminen2^N:llä siirtää pilkkua N paikkaa vasemmalle.

Taulukko 4.Kokonaislukuosan formaatti. n₁₆ kuvaa vähiten merkitsevää bittiä.

etumerkki₃₁ n₃₀ n₂₉ ... n₁₇ n₁₆

Taulukko 5. Murto-osan formaatti. n₀ kuvaa vähiten merkitsevää bittiä.

n₁₅ n₁₄ ... n₁ n₀

Taulukko 6. Kokonaislukuosa luvulle 1234.567. Bittijonon 16-bittinen etumerkillinen kokonaislukuarvo on 1234.

0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0

Taulukko 7. Murto-osa luvulle 1234.567. Bittijonon 16-bittinen etumerkitön kokonaislukuarvo on 37159, joka on muunnettavissa reaalilukumuotoon jakamalla arvolla 2^N, jossa N on bittijonon bittien määrä. Murto-osan arvo reaalilukuna on 37159/2¹⁶≈0.5670013427734375.

1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1

3.2. Aritmeettiset operaatiot kiinteän pisteen numeroille

Tässä luvussa käsitellään kahta yksinkertaista aritmeettista operaatiota; plus- ja kertolaskua. Näiden käänteisoperaatiot, miinus- ja jakolasku, jätetään huomioimatta. Lähestymistavoista käsitellään logiikkaporttitoteutuksen ja allekkain laskemisen eroja. Tutkielman ja toteutuksen kannalta triviaaliksi katsotaan myös negatiiviset

(10)

arvot, joten luku käsittelee vain positiivisten kiinteän pisteen numeroiden operaatioita. Luettavuuden vuoksi lukujen bittisyys esimerkeissä on laskettu 12 bittiin, joissa sekä kokonaislukuosa että murto-osa esitetään kuudella bitillä.

Yhteenlasku

Kuten edellisessä kappaleessa osoitettiin, positiiviset kiinteän pisteen numerot ovat kuin 2^N:llä kerrottuja pyöristettyjä reaalilukuja, joissa N on murto-osan bittien määrä. Tästä johtuen myös yhteenlasku käyttäytyy samalla tavalla, sillä se ei siirrä pisteen paikkaa. Taulukossa 8 esitetään allekkain laskeminen luvuilla001011.011101₂ (11.453125₁₀) ja 000110.011100₂ (6.4375₁₀). Summaksi saadaan tarkka arvo,

010001.111001₂ (17.890625₁₀).

Taulukko 8. Yhteenlasku luvuilla 11.453125 ja 6.4375. Yhteenlaskun välivaiheessa kantaluvun maksimiarvon ylittävän osuuden kantaminen jätetään huomiotta.

Luku 1 0 0 1 0 1 1 0 1 1 1 0 1

Luku 2 0 0 0 1 1 0 0 1 1 1 0 0

Välivaihe 0 0 1 1 2 1 0 2 2 2 0 1

Summa 0 1 0 0 0 1 1 1 1 0 0 1

Kertolasku

Kahden luvun allekkain kertominen tapahtuu tyypillisesti ensin kertomalla toinen luku ensimmäisen luvun numerolla paikassa i. Tämä tulo kerrotaan potenssiin i korotetulla kantaluvullaβ, jossai:n indeksointi alkaa nollasta ja lähtee vähiten mer- kitsevästä numerosta. Kaava (2) kuvaa kahden numeron allekkain laskemista mate- maattisesti ja taulukko 9 havainnollistaa prosessia esittämällä kertolaskun123×24 allekkain.

b(log_βx)+1c

X

i=0

y × x

_i

× β

ⁱ (2)

Taulukossa 9 esitetty 10-kantaisten lukujen allekkain kertominen toimii binääri- luvuilla vastaavalla tavalla. Binääriluvuilla ei kuitenkaan ole tarpeellista oikeasti kertoa lukuja keskenään, sillä nollalla kertominen tuottaa nollan ja yhdellä kertominen kerrottavan luvun itsensä. Taulukon 10 esimerkissä kerrotaan allekkain arvot 000011.0111012 (3.45312510) ja 000110.0111002 (6.437510). Näiden kokonaislu- kumuotoiseksi tuloksi saadaan 101100011101011002 (9105210), joka on muunnettavissa reaaliluvuksi jakamalla se arvolla 2^2N jossa N on murto-osien bittien määrä.

Tämä johtuu siitä, että kahden kiinteän pisteen numeron tuloa laskiessa kokonais-

(11)

Taulukko 9. Kertolaskun välivaiheessa kantaluvun maksimiarvon ylittävän osuuden kantaminen jätetään huomiotta.

1 2 3

× 2 4

7 2 24×3×10⁰ = 72 4 8 24×2×10¹ = 480 + 2 4 24×1×10² = 2400

2 8 15 2 Välivaihe

2 9 5 2 Tulo

lukumuodossa, binääripiste siirtyy kaksi kertaa lukujen murto-osan bittien määrän verran vasemalle. Kahdella 12-bittisellä kiinteän pisteen numerolla, joissa 6 bittiä on varattu murto-osille, piste siirtyy 12 bittiä vasemmalle. Pistettä siirtämällä numeroiden tuloksi saadaan91052/2¹²≈22.2294921875.

Taulukko 10. Lukujen 3.453125 ja 6.4375 tulon laskeminen allekkain. Kertolas- kun välivaiheessa kantaluvun maksimiarvon ylittävän osuuden kantaminen jätetään huomiotta. Luettavuuden vuoksi etunollat sekä nollalla kertomiset on jätetty pois taulukosta. Myöskään bittien vasemmalle siirrosta (engl. left [bit] shift) seuranneita lisänollia ei esitetä.

Luku 1 1 1 0 1 1 1 0 1

Luku 2 1 1 0 0 1 1 1 0 0

1 1 0 0 1 1 1 0 0

+ 1 1 0 0 1 1 1 0 0

Välivaihe 1 2 1 1 3 4 3 3 3 3 2 2 1 1 0 0

Tulo 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 0 0

4. Esoteeriset ohjelmointikielet

Tässä kappaleessa esitellään Turing-täydellisyyden käsite (luku 4.1), sekä käsitel- lään esoteerisia ohjelmointikieliä (luvut 4.2, 4.3, 4.4 ja 4.5). Esoteerisistä kielistä keskitytään kuitenkin vain kolmeen, 1990-luvun Brainfuckiin sekä Befunge-93:een ja uudempaan, erityisesti koodigolfaukseen hyvin soveltuvaan Jellyyn. Jellyn triviaa- lin tutkimusongelman ratkaisun vuoksi sitä käsitellään pääasiassa vertailukohtana

(12)

yksinkertaisemmille kielille. Tämän lisäksi perehdytään Brainfuckin tekniseen mää- ritelmään sekä makrokielien käsitteeseen. Makrokielistä esitellään vain tutkimusongelman kannalta oleellinen kieli, BFIMDM (luku 4.5).

Chris Pressey (2013) kuvaili esoteerisia ohjelmointikieliä seuraavasti: "They’re made up of concepts, and these concepts would exist even if our computing equipment wasn’t electronic, or wasn’t digital, or if we didn’t have computing equipment at all. It’s just that having computing equipment makes it a lot easier to design and experience these programming languages."

4.1. Turing-täydellisyys

"Turingin kone on äärellinen automaatti, joka koostuu äärettömän pitkästä nauhas- ta, joka toimii koneen muistina, lukupäästä ja äärellisestä joukosta tiloja. Kone ky- kenee liikkumaan nauhalla oikealle ja vasemmalle, pysähtymään, lukemaan nauhan solun ja tulostamaan sen paikalle jonkin sallitun merkin". (Haataja, 2014).

Tutkimuskysymyksen kannalta oleellisimmista kielistä, Brainfuckista ja Befunge- 93:sta, vain Brainfuck on Turing-täydellinen (Morr, 2015). Edellinen väite sisältää kuitenkin oletuksen kielen tulkin muistinauhan koosta, joka lähteestä ja toteutuk- sesta riippuen on 30 000, vähintään 30 000 tai loputtoman pituinen. Pituudelle asettaa rajoitteen käytännössä tulkkia suorittavan tietokoneen muistin määrä, joka kuitenkin jätetään huomioimatta teoreettista Turing-täydellisyyttä arvioitaes- sa. Befunge-93:sta myöhemmin jatkokehitetty Funge-98 -kieliperheen Befunge-98 poisti ohjelmakomentotaulukon kokorajoituksen tehden kielestä Brainfuckin tavoin Turing-täydellisen (Morr, 2015; Esolangs Funge-98, 2020). Turing-epätäydellisyys ei kuitenkaan estä suorittamasta joitain algoritmeja tietyin rajoittein. Befunge-93:n rajoitteista huolimatta sillä on mahdollista suorittaa muun muassa kiinteän pisteen numeroiden kertolasku (ks. liite 8.3).

4.2. Brainfuck

Kieli tunnetaan virallisen nimen lisäksi muun muassa nimillä brainf***, brainf*ck, brainfsck, b****fuck, brainf**k, branflakes, brainoof, brainfrick sekä bf (Esolangs Brainfuck, 2020). Brainfuck on yksi tunnetuimmista esoteerisista ohjelmointikielistä.

Tämä johtunee kielen äärimmäisyyksiin menevästä yksinkertaisuudesta, jonka vuoksi kielen tulkin toteuttaminen ja muokkaaminen on verrattain triviaalia. (Kasurinen, 2016). Muokkauksen helppouden vuoksi kielelle on olemassa ainakin 261^[3] erilais-

[3]Kasurisen vuonna 2016 julkaistun kirjan mukaan muunnoksia ja johdannaisia kieliä oli 125

(13)

ta muunnosta tai johdosta, joka vastaa noin kuudesosaa^[4] Esolangs-wikisivustolla listatuista esoteerisista ohjelmointikielistä (Esolangs language list, 2020).

Brainfuck käyttää tyypillisesti 8-bittisistä kokonaisluvuista koostuvaa, vähintään 30 000 muistipaikkaa sisältävää muistinauhaa, jonka arvojen tulee sekä ali- että yli- vuotaa (engl. underflow, overflow). Vaikka muistinauha voi olla pituudeltaan lopu- ton, ei sen osoitteiden kuitenkaan oleteta menevän negatiivisiksi. (Esolangs Brain- fuck, 2020).

Kielen tekninen määritelmä ei ole kovin tarkkarajainen, sillä 8-bittisten kokonaislukujen lisäksi määritelmä huomioi, että nopeat tulkit saattavat käyttää 32-bittisiä tai suurempia kokonaislukuja (engl. bignum). Liukulukujen lisäksi määritelmä rajaa pois luvut, joiden kantaluku poikkeaa kahdesta. (Esolangs Brainfuck, 2020).

Kielessä on 8 operaatiota, joiden avulla voidaan kirjoittaa muistinauhan arvoja sekä suorittaa suoritusehdon sisältävää silmukkaa tai syöte-tuloste -operaatioita (ks.

taulukko 11). Suoritusehdon sisältävä silmukka on verrattavissa monista kielistä löytyväänwhile-silmukkaan.

Taulukko 11. Brainfuckin komennot (Esolangs Brainfuck, 2020).

Symboli Toiminto

> Siirrä muistiosoitinta yhdellä oikealle.

< Siirrä muistiosoitinta yhdellä vasemmalle.

+ Kasvata nykyisen muistipaikan arvoa yhdellä.

- Pienennä nykyisen muistipaikan arvoa yhdellä.

. Tulosta nykyisen muistipaikan arvo 8-bittisenä ASCII-merkkinä.

, Lue seuraava merkki syötteestä nykyiseen muistipaikkaan.

[ Hyppää vastaavaan]-pariin, jos nykyisen muistipaikan arvo on 0.

] Hyppää vastaavaan[-pariin, jos nykyisen muistipaikan arvo on erisuuri kuin 0.

4.3. Befunge-93

Befunge-93 on Brainfuckin tavoin julkaistu vuonna 1993. Brainfuckista poiketen, kielen tavoitteena ei kuitenkaan ole olla äärimmäisen hankalasti luettava tai ohjelmoi- tava, vaan kieli pyrki tarkoilla määrittelyillään tekemään tulkin ja kääntäjän kirjoit- tamisen haastavaksi tai mahdottomaksi (Morr, 2015). Tulkkeja kielelle on Kasurisen (2016) mukaan kuitenkin onnistuttu tekemään alkuperäisen C:llä toteutetun version

[4]Kasurisen vuonna 2016 julkaistun kirjan mukaan 125 muunnosta ja johdannaista vastasi noin viidesosaa Esolangs-wikisivuston listaamista kielistä, nykyään (2020-10-17) kieliä on listattu 1753 ja Brainfuck-muunnoksia listattu 261. (Esolangs language list, 2020).

(14)

lisäksi ainakin VisualBasicilla ja Javalla. Näiden lisäksi kielelle on avoimen lähde- koodin tulkkitoteutuksia ainakin JavaScriptillä (Smith, 2018) ja C#:lla (Schwörer, 2019) sekä ajonaikaisesti ohjelmaa kääntävä toteutus JavaScriptillä (Toncean, 2019).

Kielellä ohjelmointi tapahtuu kirjoittamalla yksimerkkisiä komentoja kaksiulot- teiseen ohjelmakomentotaulukkoon, jotka voivat käyttää pinoa tiedon väliaikaiseen säilömiseen, parametrien antamiseen komennoille tai komentojen paluuarvojen säi- lömiseen. Kieli sisältää 26 komentoa, joita voidaan käyttää 80 merkkiä leveällä ja 25 merkkiä korkealla ohjelmakomentotaulukolla. (Esolangs Befunge, 2021).

Kieli mahdollistaa kaksi vaihtoehtoista tapaa tallentaa arvoja; joko suoraan ohjelmakomentotaulukkoon muokaten lähdekoodia tai pinoon. Ohjelmakomentotaulu- kon hyödyllisyys tiedon säilömiseen riippuu tulkin käyttämästä tietotyypistä. Esi- merkiksi web-pohjaisessa tulkissa käytetty taulukon tietotyyppi määräytyy selaimen Javascript-moottorin käyttämän tietotyypin mukaan ilman tyypin nimenomaista määrittelyä. Muun muassa Xun julkaisema tulkki mahdollistaa yli 8-bittisten arvojen asettamisen ohjelmakomentotaulukkoon (ks. algoritmi 1) (Visual Befunge-93 Interpreter, 2011). Befunge-93:n viitetoteutuksessa taulukon muistipaikkojen tieto- tyypiksi on kuitenkin määritelty C-kielenchar (Befunge-93 Matrix Definition, 2018), joka on tyypillisesti 8-bittinen kokonaislukuarvo. Näin pienen tietotyypin käyttämi- nen reaalilukujen säilömiseen edellyttäisi useimmissa tapauksissa bittijonon pilk- komista useaan muistipaikkaan, joka puolestaan tekisi aritmeettisista operaatioista monimutkaisempia ja epäintuitiivisempia. Viitetoteutuksen pino on kuitenkin toteutettu käyttäen C-kielen signed long -tietotyyppiä, joka on vähintään 32-bittinen etumerkillinen kokonaisluku (Befunge-93 Stack Definition, 2018). 32-bittinen koko- naislukutyyppi mahdollistaa enintään kahden 16-bittisen kiinteän pisteen numeron kertolaskun kokonaislukumuodossa, sillä niiden tulon maksimipituus on 32 bittiä.

Viitetoteutuksen mukaisen tulkin pinon käyttö arvojen säilömiseen on ohjelmako- mentotaulukossa säilömistä käytännöllisempää.

01 -01 p 0 1 g . @

Algoritmi 1: Tulostaa ohjelmakomentotaulukon maksimiarvon.

4.4. Jelly

Jelly poikkeaa merkittävästi sekä Brainfuckista, että Befunge-perheen kielistä. Kieli on tekijänsä mukaan saanut inspiraatiota J-kielestä (Mitchell, 2018). Vaikka kieli on luokiteltu esoteeriseksi, ei se kuitenkaan pyri olemaan millään tavalla vaikea, vaan kehityksen tavoitteena on ollut toteuttaa koodigolfaukseen soveltuva kieli. Tästä

(15)

johtuen Jelly käyttää jokaista 8-bittisen merkistötaulukon merkkiä jonkin toiminnon toteuttamiseen (Esolangs Jelly, 2020).

Erona alkeellisempiin kieliin on myös Jellyn sisältämä tuki reaalilukuesityksil- le kielen tulkin sisäisessä tietotyypissä. Jellyn alkuperäinen tulkki on toteutettu Python 3:lla, jonka alkuperäisen CPython-pohjaisen tulkin liukuluvun arvoa säilö- tään tyypillisesti 64-bittisessä C-kielen kaksoistarkkuuden liukulukutyppisessä (engl.

double) muuttujassa (CPython FloatObject, 2020). Aiemmin mainitut triviaalit esi- merkit liukulukujen yhteen- ja kertolaskusta Jellyllä on esitetty algoritmeissa 2 ja 3.

1.2 + 4.7

Algoritmi 2: Yhteenlasku Jellyllä. Palauttaa arvon 5.9.

1.2 × 4.7

Algoritmi 3: Kertolasku Jellyllä. Palauttaa arvon 5.64.

4.5. Makrokielet ja BFIMDM

Tässä kappaleessa käsitellään makrokieliä yleisesti ja tutkielman käytännön ratkaisua varten kehitettyä BFIMDM:ää. Sen esittely tukee myöhemmin käytettyjen ter- mien ja viittausten ymmärrettävyyttä.

Brainfuckin kaltaisilla syntaksisesti minimaalisilla esoteerisilla ohjelmointikielil- lä ohjelmoidessa on yleistä käyttää niin kutsuttuja makrokieliä helpottamaan ohjel- mointityötä. Perinteisten ohjelmointikielten kääntäjien tavoin makrokielet saattavat automatisoida suurenkin osan ohjelmointikielelle tai konekieliselle käskykannal- le ominaisista haasteista. Tätä tutkielmaa varten toteutettu makrokieli BFIMDM, BrainFuck with Interlaced Multi-Dimensional Memory, pyrkii kuitenkin säilyttä- mään mahdollisimman alkuperäisen syntaksin ja ominaisuudet (ks. taulukot 14 ja 15). Näin toteutusten intuitiivisuus esiintyy myös alkuperäisillä kielillä makrokielen luoman abstraktiokerroksen sijaan. BFIMDM:n sisältämät operaatiomuutokset ja -lisäykset pyrkivät minimoimaan kirjoitusvirheiden yleisyyttä vähentämällä käy- tettyjen syntaksimerkkien määrää. Kieli lisää myös muistiulottuvuuksien alustusko- mennon sekä koko muistin tulostusoperaation helpottaakseen testausta ja kehitys- työtä (ks. taulukko 15).

BFIMDM lisää kieleen kaksi uutta tulkin tilaa muuttavaa operaatiota; "$" mene alas ja "^" mene ylös. $ korvaa > -operaation ja ^ korvaa < -operaation. < ja >

puolestaan korvautuvat itsellään toistettunaN kertaa, jossaN on muistikerrosulot- tuvuuksien kokojen tulo. Tutkielmassa käytetyn kaksiulotteisen muistin tapauksessa

(16)

N on muistikerroksien määrä. Taulukko 13 havainnollistaa muistipaikkojen limittäy- tymisen käytettäessä kolmea muistikerrosta ja taulukko 12 esittää samat arvot ilman limitystä, siten kuin arvot Brainfuck-tulkin muistissa esiintyvät. Taulukossa 14 esi- tetään makrokielen tekemät operaatioiden korvaamiset ja taulukko 15 listaa uudet operaatiot, jotka eivät korvaa vanhaa toiminnallisuutta.

Taulukko 12. Yksiulotteinen muistinauha.

Muisti 1 2 3 4 5 6 7 8 9 10 11 12 ...

Taulukko 13. Kaksiulotteiseksi limitetty muistinauha.

Muistikerros 1 1 4 7 10 ...

Taulukko 14. BFIMDM:n komentojen Brainfuck-vastineet kolmikerroksiseksi limi- tetyllä muistinauhalla.

Kaksiulotteinen siirtymä BFIMDM-komento Brainfuck-vastine

ylös ^ <

alas $ >

vasemmalle < < < <

oikealle > > > >

Taulukko 15. Kehitystyötä helpottavat BFIMDM-komennot, jotka eivät korvaa mi- tään Brainfuckin olemassa olevaa komentoa.

Layer input arvo1 arvo2 ... arvon Määrittelee "input"-nimisen muistikerroksen, joka alustetaan valinnaisilla välilyönneillä erotelluilla arvoilla. Määrittelemättömät arvot alustetaan nollilla.

#result Määrittelee "result"-nimisen muistituloste- otsakkeen, jonka tulostamisen jälkeen tulkki tulostaa koko ajonaikaisen muistiavaruuden.

(17)

5. Reaaliluvut esoteerisilla kielillä

Aiemmissa luvuissa käsiteltiin reaalilukujen aritmeettisten operaatioiden toteutus- vaihtoehtojen asettamia teknisiä vaatimuksia ja niiden toteuttamisen selkeyttä ja yksinkertaisuutta. Tässä luvussa esitellään parhaat lähestymistavat eri kielillä.

Logiikkaporttitoteutuksen etuna on sen modulaarisuus ja logiikkaporttien simu- loinnin yksinkertaisuus (ks. algoritmit 4, 5, 6 ja 7). Intuitiivisuuden kannalta ratkaisun yksittäisten komponenttien modulaarisuuden tuoma hyöty kuitenkin katoaa, mikäli niitä käyttävä järjestelmä ei ole yksinkertainen. Simuloituja logiikkaportteja käytettäessä niiden välisten IO-rajapintojen yhdistäminen vaikeuttaisi merkittävästi kokonaisratkaisun hahmottamista, sillä arvot pitäisi siirtää edellisen portin ulostu- losta seuraavan portin sisäänmenoon. Tämän lisäksi ratkaisu olisi sidottu toteutus- hetkellä valittuihin syötteiden bittisyyksiin, eikä siten olisi triviaalisti skaalattavissa (ks. Marimuthu et al., 2013). Deschamps et al. (2017) puolestaan esittelevät modulaarisen ja helpommin skaalattavissa olevan binäärikertolaskun logiikkaporttitoteutuksen, joka on intuitiivinen moduulien abstraktiotasolla, mutta jonka intuitiivisuus katoaa tarkasteltaessa toteutusta joukkona simuloituja logiikkaportteja.

Logiikkaporttipohjaiset ratkaisut eivät ole intuitiivisia ainakaan Brainfuckin kaltaisilla esoteerisilla kielillä, joiden syntaksista puuttuu bittitason operaatiot. Brain- fuckilla toteutettujen liukulukujen eksponenttien vertailu, mantissasta poistetun bitin huomioiminen ja useat poikkeusarvot olisivat kaikki haasteellisia toteuttaa. To- teutuksen haasteellisuus ei itsessään tee ratkaisusta epäintuitiivista, mutta Brainfuc- kin tapauksessa liukulukuja ulos antavan ratkaisun hyödyllisyys olisi kyseenalainen, sillä arvojen jatkokäsittely olisi merkittävästi kiinteän pisteen numeroita haastavam- paa. Brainfuckin liukulukutoteutuksen tarpeellisuutta kyseenalaistaa myös kielen asettamat rajoitteet. Rajoitteiden seurauksena herää kysymys siitä, kuinka tarpeel- linen 32-bittisen liukuluvun tarkkuus on kielellä, jonka kokonaisluvukin ovat vain 8-bittisiä. Edellä mainituista useista liukulukujen käytön haitoista johtuen Brain- fuckilla kiinteän pisteen numeroiden aritmeettisten operaatioiden toteutus on pe- rustellumpi valinta. Muistinauhan käytön näkökulmasta intuitiivisin tapa suorittaa aritmeettisia operaatioita on aiemmin esitelty allekkain laskeminen. Operaatiota on myös mahdollista optimoida, kuitenkaan haittaamatta prosessin selkeyttä, suorittamalla bittien ylimenevien arvojen kantaminen vain kerran operaation lopussa. Ky- seinen optimointi kuitenkin asettaa rajoitteen syötearvojen bittisyyksille, jonka seurauksena muun muassa kertolasku yli 128-bittisillä syötearvoilla ei ole mahdollinen, sillä väliaikaisia ylivuotosummia säilötään 8-bittisinä kokonaislukuina (ks. taulukko 16).

(18)

Befunge-93:lla logiikkaporttipohjainen lähestymistapa ei olisi täysin poissuljettu vaihtoehto, mikäli kielen välimuistina toimiva pino ei tukisi suuria kokonaislukuja. Sisäänrakennettu tuki suurille kokonaisluvuille mahdollistaa kiinteän pisteen numeroiden esittämisen kokonaislukumuodossa. Näin yhteenlasku onnistuu sisään- rakennettua operaatiota hyödyntämällä ja kertolaskun tapauksessa jälkikäsittelyksi riittää binääripisteen siirtäminen.

Jellyn todettiin monista muista esoteerisista kielistä poiketen tarjoavan sisään- rakennetun tuen liukulukujen aritmeettisille operaatioille (ks. algoritmit 2 ja 3).

Näiden korvaaminen olisi erittäin epätyypillinen ratkaisu koodigolfauskielelle, jolla tyypillisesti pyritään merkkimäärälliseen minimaalisuuteen.

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

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

Algoritmi 4:AND-portti. Lukee syötteen muistipaikoista 0 ja 2, jonka jälkeen kirjoittaa tuloksen muistipaikkaan 4. Algoritmi käsittelee syötearvon 0 epätotena ja muut totena.

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

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

Algoritmi 5: OR-portti. Lukee syötteen muistipaikoista 0 ja 2, jonka jälkeen kirjoittaa tuloksen muistipaikkaan 4. Algoritmi käsittelee syötearvon 0 epätotena ja muut totena.

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

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

Algoritmi 6:XOR-portti. Lukee syötteen muistipaikoista 0 ja 2, jonka jälkeen kirjoittaa tuloksen muistipaikkaan 4. Algoritmi käsittelee syötearvon 0 epätotena ja muut totena.

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

Algoritmi 7:NOT-portti. Lukee syötteen muistipaikasta 0 ja kirjoittaa tuloksen muistipaikkaan 2. Algoritmi käsittelee syötearvon 0 epätotena ja muut totena.

6. Keskustelu

Sekä Brainfuckin, että Befunge-93:n osalta reaalilukuesitysten toteuttaminen kiin- teän pisteen numeroilla osoitettiin perustellummaksi vaihtoehdoksi. Tämä ei ollut kovin yllättävää Brainfuckin osalta, mutta huomio siitä, ettei liukulukutoteutus Befunge-93:lla vaikuta olevan täysin poissuljettu vaihtoehto, oli mielenkiintoista ja vaatisi jatkotutkimusta. Myös Jellyllä tutkimusongelman ratkaisun triviaalisuus

(19)

Taulukko 16.Numeron bittisyyden ja maksimiarvon suhde ennen ylimenevien arvojen kantamista.

Bittisyys Carry-save adderin muistipaikan pahimman tapauksen maksimiarvo

8 14

16 30

32 62

64 126

128 254

256 510

N 2(N −1)

oli odotettavissa kielen kattavuuden vuoksi. Aihepiiristä ei ole ennen tehty vas- taavanlaista tutkimusta tai toteutettu käytännön sovellusta, jonka vuoksi tulokset ovat omassa kategoriassaan merkittäviä. Esoteeriset kielet ovat hyvin erilaisia, jonka vuoksi on vaikeaa arvioida tulosten yleistettävyyttä arvioimatta jokaista kieltä erik- seen. Epävarmuutta käytettyihin metodeihin ei tutkielmaa kirjoittaessa herännyt, sillä ennalta valitut reaalilukuesitykset ja kielet osoittautuivat tutkimuskysymyksen kannalta joko oleellisiksi tai hyviksi vertailukohdiksi toisille kielille. Tämän tutkielman keskittyessä vahvasti ratkaisujen intuitiivisuuteen, nousi usein esiin kysymys intuitiivisuuden hinnasta alentuneen tehokkuuden muodossa. Befunge-93:n liukulukutoteutuksen tutkimisen lisäksi jatkotutkimusta tulisi tehdä myös tehokkaista reaalilukutoteutuksista esoteerisilla kielillä.

7. Yhteenveto

Toteutettaessa reaalilukujen aritmeettisia operaatioita esoteerisilla kielillä kannattaa ensin selvittää kielen mahdollinen sisäinen tuki reaaliluvuille ja niiden aritmeettisille operaatioille. Jellyn kaltaisissa kielissä tämän tuen uudelleen toteuttaminen on työ- lästä, tehotonta ja tarpeetonta, minkä vuoksi kyseiseen kieleen ei tässä tutkielmassa keskitytty kuin vertailukohtana muille kielille. Mikäli kieli ei tarjoa sisäistä tukea reaaliluvuille, kannattaa ratkaisun etsiminen aloittaa välimuistin ominaisuuksien pe- rusteella. Brainfuckille ominainen ratkaisu on kiinteän pisteen numeroiden allekkain laskeminen ja Befunge-93:lle puolestaan kiinteän pisteen bittijonojen muuntaminen kokonaisluvuiksi ja sisäisten aritmeettisten operaatioiden käyttö laskennassa.

Matriisipohjaisissa tai sellaisina käsiteltävissä välimuisteissa, joissa minkä tahansa arvon voi lukea tai kirjoittaa suorituksen missä vaiheessa tahansa, on intuitiivi- sinta pyrkiä laskemaan luvut allekkain. Mikäli välimuisti perustuu pinon kaltaiseen

(20)

rakenteeseen, ei allekkain laskeminen onnistu. Tällöin kannattaa selvittää pinon si- sältämien arvojen tietotyyppi ja kielen tuki sekä isoille kokonaisluvuille, että kertolaskulle. Mikäli pinoa välimuistina käyttävässä kielessä on tuki suurille kokonaisluvuille, mutta tuki kertolaskulle puuttuu, saattaa liukulukutoteutus olla kiinteän pisteen numeroilla toteuttamista intuitiivisempaa. Mikäli tietotyypin koko rajoittaa pinoon pohjautuvaa ratkaisua merkittävästi, ei intuitiivista ratkaisua välttämättä ole olemassa. Tällöin Deschampsin et al. (2017) kaltaisen modulaarisen binäärikertolas- kuoperaation käyttö saattaa olla helpoin ratkaisu, kunhan pinon lisäksi välimuisteja on muitakin tai pinon operaatiot voidaan kohdistaa mihin tahansa kohtaan.

Kuten kaikissa esoteerisiin kieliin liittyvissä ongelmissa, on tärkeää pyrkiä pilk- komaan ongelma pienempiin osaongelmiin. Modulaarisia ratkaisuja osaongelmiin on helpompi toistaa ja korjata. Kielten usein äärimmäisyyksiin menevän yksinker- taistuksen vuoksi intuitiiviset ja helposti visualisoitavat ratkaisut ovat tyypillisesti merkittävästi helpompia kirjoittaa kuin teho-optimoidut ratkaisut. Optimointia ei kuitenkaan tarvitse sulkea kokonaan ratkaisusta pois. Tässä tutkielmassa esitelty Brainfuck-toteutus (ks. liitteet 8.1 ja 8.2) on pohjimmiltaan intuitiivinen ratkaisu, jonka osaongelma, arvojen kantaminen, on optimoitu suorittamalla se vain kerran laskennan lopussa.

(21)

Lähdeluettelo

Ahire, D. (2020). Code Golfing by Gaining and using the Intimate Knowledge of the Language. International Journal of Engineering Research and, 2020-06-02, Vol.9 (5) Anureev, I. S., Bodin, E. V., Gorodnyaya, L. V. E., Marchuk, A. G., Murzin, F.

A., & Shilov, N. V. (2008). On the problem of computer language classification.

Joint NCC&IIS Bulletin, Series Computer Science, 27, 1-20.

Befunge-93 Matrix Definition. (2018). Haettu 2020-12-01.

https://github.com/catseye/Befunge-93/blob/master/src/bef.c#L210 Befunge-93 Stack Definition. (2018). Haettu 2020-12-01.

https://github.com/catseye/Befunge-93/blob/master/src/bef.c#L204 CPython FloatObject. (2020). Haettu 2020-11-23.

https://github.com/python/cpython/blob/master/Include/floatobject.h#L17 Deschamps, J.-P., Valderrama, E., & Terés, L. (2017). Digital systems: From logic gates to processors. Springer International Publishing Imprint : Springer.

http://ezproxy.uniandes.edu.co:8080/login?url=http://dx.doi.org/10.1007/978-3-319- 41198-9

Esolangs Befunge. (2021). Haettu 2021-01-18. https://esolangs.org/wiki/Befunge Esolangs Brainfuck. (2020). Haettu 2020-11-03. https://esolangs.org/wiki/Brainfuck Esolangs Funge-98. (2020). Haettu 2020-11-22. https://esolangs.org/wiki/Funge-98 Esolangs Jelly. (2020). Haettu 2020-11-23. https://esolangs.org/wiki/jelly

Esolangs language list. (2020). Haettu 2020-11-03.

https://esolangs.org/wiki/Language_list

Etymologyonline Esoteric. (2020). Haettu 2020-11-02.

https://www.etymonline.com/word/esoteric

(22)

Goldberg, D. (1991). What Every Computer Scientist Should Know About Floating- Point Arithmetic. Computing Surveys.

Haataja, A. (2014). Haettu 2020-12-06.

https://www.cs.helsinki.fi/u/pklehtol/AHaatajaTuringinKone.pdf

Kasurinen, J. P. (2016). Outoa ohjelmointia: Esoteeriset ohjelmointikielet. Docendo Oy.

Marimuthu. (2013). Design of 8-4 and 9-4 compressors forhigh speed multiplication. American Journal of Applied Sciences, 10(8), 893-900.

https://doi.org/10.3844/ajassp.2013.893.900 Mitchell, D. (2018). Haettu 2020-11-23.

https://github.com/DennisMitchell/jellylanguage Morr, S. (2015). Esoteric Programming Languages.

Muller, J-M. et al. (2010). Handbook of floating-point arithmetic. Birkhäuser Bos- ton.

Nasyrova, S. R., & Molodovskiy, E. A. (2013). Esoteric programming languages.

SCIENCE AND WORLD, 34.

Pressey, C. (2013). The Aesthetics of Esolangs. Haettu 2020-12-07.

https://catseye.tc/view/The-Dossier/article/The%20Aesthetics%20of%20Esolangs.md Schwörer, M. (2019). Haettu 2020-11-22. https://github.com/Mikescher/BefunExec Smith, A. (2018). Haettu 2020-11-22. https://github.com/amicloud/befunge93 Temkin, D. (2017). Language Without Code: Intentionally Unusable, Uncompu- table, or Conceptual Programming Languages (Vol. 9). Universidade Católica Por- tuguesa - Centro de Investigação em Ciência e Tecnologias das Artes.

Toncean, A. (2019). Haettu 2020-11-22. https://github.com/adrianton3/befunjit

(23)

Visual Befunge-93 Interpreter. (2011). Haettu 2020-12-01.

https://github.com/qiao/javascript-playground/blob/master/

visual-befunge93-interpreter/befunge93.js#L323

(24)

8. Liitteet

8.1. Kahden kiinteän pisteen numeron yhteenlasku Brain- fuckilla

Seuraavanlaisella BFIMDM-muistikerrosmäärittelyllä algoritmi laskee lukujen 0100.1100₂ (4.75₁₀) ja 0011.0010₂ (3.125₁₀) summan. Algoritmi käsittelee niitä 8- bittisinä numeroina. Bittisyys määräytyy stepper-kerroksen arvosta, joka määrittää myösinput0 jainput1-kerrosten syötteen vähiten merkitsevän bitin sijainnin. Mikäli stepperin arvoa kasvattaa, tulee muistin arvoja siirtää oikealle, jotta laskutoimitus mahtuu muistiin. Muisti laajenee loputtomasti oikealle, muttei yhtään vasemmalle.

Jos muistia siirretään oikealle, tulee jokaista yhden sarakkeen siirtoa kohden lisätä muistikerrosten määrän verran > -operaatioita algoritmin alkuun.

Layer stepper 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8

Layer input0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0

Layer input1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0

Layer sum 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Layer tmp0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Layer tmp1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Layer tmp2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Layer tmp3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

MIT License

Permission is hereby granted; free of charge; to any person obtaining a copy of this software and associated documentation files (the

"Software"); to deal in the Software without restriction; including without limitation the rights to use; copy; modify; merge; publish;

distribute; sublicense; and/or sell copies of the Software; and to permit persons to whom the Software is furnished to do so; subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software!

Special characters; such as commas; periods; parentheses; etc can be replaced with other characters if and only if any interpretation of

(25)

the license contents is equivalent to the interpretation of the MIT license and the replacement is necessary in order to avoid

interference with the instruction set characters of a Brainfuck variant!

THE SOFTWARE IS PROVIDED "AS IS"; WITHOUT WARRANTY OF ANY KIND;

EXPRESS OR IMPLIED; INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY; FITNESS FOR A PARTICULAR PURPOSE AND

NONINFRINGEMENT! IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM; DAMAGES OR OTHER LIABILITY; WHETHER IN AN ACTION OF CONTRACT; TORT OR OTHERWISE; ARISING FROM; OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE!

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>[-<<<<<<<<

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

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

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

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

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

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

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

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

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

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

8.2. Kahden kiinteän pisteen numeron kertolasku Brainfuc- killa

Seuraavanlaisella BFIMDM-muistikerrosmäärittelyllä algoritmi laskee lukujen 0100.1100₂(4.75₁₀) ja 0011.0010₂(3.125₁₀) tulon. Algoritmi käsittelee niitä 8-bittisinä numeroina. Bittisyys määräytyystepper-kerroksen arvosta, joka määrittää myösin- put0 jainput1-kerrosten syötteen vähiten merkitsevän bitin sijainnin. Mikälisteppe- rin arvoa kasvattaa, tulee muistin arvoja siirtää oikealle, jotta laskutoimitus mahtuu muistiin. Muisti laajenee loputtomasti oikealle, muttei yhtään vasemmalle. Jos muistia siirretään oikealle, tulee jokaista yhden sarakkeen siirtoa kohden lisätä muistikerrosten määrän verran > -operaatioita algoritmin alkuun.

(26)

Layer stepper 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8

Layer input0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0

Layer input1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0

Layer sum 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Layer tmp0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Layer tmp1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Layer tmp2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Layer tmp3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

MIT License

Permission is hereby granted; free of charge; to any person obtaining a copy of this software and associated documentation files (the

"Software"); to deal in the Software without restriction; including without limitation the rights to use; copy; modify; merge; publish;

distribute; sublicense; and/or sell copies of the Software; and to permit persons to whom the Software is furnished to do so; subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software!

Special characters; such as commas; periods; parentheses; etc can be replaced with other characters if and only if any interpretation of the license contents is equivalent to the interpretation of the MIT license and the replacement is necessary in order to avoid

interference with the instruction set characters of a Brainfuck variant!

THE SOFTWARE IS PROVIDED "AS IS"; WITHOUT WARRANTY OF ANY KIND;

EXPRESS OR IMPLIED; INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY; FITNESS FOR A PARTICULAR PURPOSE AND

NONINFRINGEMENT! IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM; DAMAGES OR OTHER LIABILITY; WHETHER IN AN ACTION OF CONTRACT; TORT OR OTHERWISE; ARISING FROM; OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE!

(27)

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>[-<<<<<<<<

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<<<]>>>>>>>>[>>>>>>>>]<<<<]>>>>[>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<

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

<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<]<<<<

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

>>[>>>>>>>>]<<<<]>>>>[>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

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

<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

<<<<<<<]>>>>>>>>[>>>>>>>>]<<<<]>>>>[>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<

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

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>

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

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

>>>>[>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

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

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

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

(28)

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

>>>+<<<<<<<<]>>>>>>>>

8.3. Kahden kiinteän pisteen numeron kertolasku Befunge- 93:lla

Esimerkissä 16-bittiset binäärinumerot on kirjoitettu kovakoodattuna riville 5. Ohjelma kertoo keskenään numerot

00010001.10111000 (17.71875) ja 00001011.00111011 (11.23046875).

Ohjelma tulostaa kertolaskun tuloksen kielen standarditulosteeseen.

Yllä olevilla arvoilla tuloksi saadaan 11000110.11111101 (198.98828125).

v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v 4*:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\++++4*:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\++++*

8*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*++++8*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*++++4

*:/ / / / / / / / / / / / / / / / ++++*:/ / / / / / / / / / / / / / / / ++++4 :\0\0\0\1\0\0\0\1\1\0\1\1\1\0\0\0++++ :\0\0\0\0\1\0\1\1\0\0\1\1\1\0\1\1++++*

>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^:

>:v:< > v * 1 |:/2\%2:<\2/<

. ‘ |:<

@_^#< >$^