lauantai 12. joulukuuta 2015

Functional Programming in Scala

Paul Chiusano ja Rúnar Bjarnason, Functional Programming in Scala. Esipuheen kirjoittanut Martin Odersky. Manning, Shelter Island, NY, USA, 2015.

Vanhan viisauden mukaan iterointi on inhimillistä, mutta rekursio on jumalaista. Iterointia käytetään tietokoneohjelmoinnissa, matemaattisessa approksimoinnissa ja suomalaisessa hallitustyöskentelyssä. Se on tehtävien prosessointia ikään kuin silmukassa: suoritetaan työvaiheita, kunnes tulee lupa lopettaa. Rekursio on matemaattisempi: siinä työvaiheen tulos riippuu saman operaation edellisistä arvoista. Esimerkiksi Richard Stallmanin avoimen lähdekoodin hanke GNU on rekursiivinen akronyymi—se tulee sanoista GNU's Not Unix. Hah hah.

Jos Hartwall-areenan yleisö pitäisi järjestää nousevaan aakkosjärjestykseen sukunimen mukaan, iteratiivinen lähestymistapa aloittaisi lavalta katsottuna vasemmasta yläkatsomosta ja alkaisi yksitellen siirrellä ihmisiä sopivaan järjestykseen. Rekursiivinen lähestymistapa voisi järjestää ihmiset kussakin katsomossa ensin istuimittain (helppo), istuinriveittäin ja sitten katsomoittain lopulta yhdistäen tulokset koko areenan tulokset. Esimerkki on ontuva, mutta rekursio on  yksinkertaisesti maallisen yläpuolella.

Mikä sitten tekee rekursiosta jumalaista? Ensinnäkin sisäkkäisten operaatioiden hahmottaminen on ensinnäkin ihmiselle vaikeaa. Operaatio, joka selvittää, mikä on esimerkiksi yhdeksäs fibonacciluku, nojaa siihen, mitkä ovat kahdeksas ja seitsemäs fibonacciluku, mikä nojaa kuudenten ja viidenteen fibonaccilukuun jne. Tällainen päässälasku on vaikeaa vähänkään suurempien lukujen kohdalla. Rekursiiviset lukujonot eivät ole tietenkään arkipäivää, mutta rekursio on hyödyllinen sisäkkäisten,  keskenään samanlaisten tietorakenteiden käsittelyssä. Tietojenkäsittelijä puhuu puista, verkoista ja linkitetyistä listoista, eli erilaisista tavoista järjestää tietoa nopeasti ja tehokkaasti käsiteltäväksi.

Toiseksi rekursio tuottaa elegantteja ratkaisuita. Hyvin vähäeleisesti tai ytimekkäästi se ratkaisee mahdollisesti hyvin monimutkaisia ongelmia. Tämä vähäeleisyys tai ytimekkyys on läheistä sukua matematiikan estetiikalle. Rekursiota esiintyy myös luonnossa, suunnittelussa ja muotoilussa: Fibonaccilukujonon peräkkäisten lukujen suhde lähestyy kultaista leikkausta. Fraktaalit ovat rekursiivisia, itsesimilaarisia joukkoja, joita luodaan keinotekoisesti, mutta esimerkiksi kukka- ja parsakaali ovat rekursiivisia fraktaaleja rakenteita.

Vuosien varrella olen käyttänyt rekursiota säästeliäästi soveltaen sitä hyvin rajattuihin ongelmiin, koska rekursiolla on hintansa. Pitkät ketjut sisäkkäisiä funktiokutsuja edellyttävät raskasta  kirjanpitoa. Kun aloitin opintoni 1990-luvun puolivälissä, rekursiota pidettiin tapana rampauttaa tietokoneen suorituskyky. Verkkojen ja puiden läpikäyntiin "tosielämässä" suositeltiin iteraatiota. Tämä rekursioon liittyvä raskaus on kuitenkin ns. imperatiivisten tai deklaratiivisten ohjelmointikielten ongelma. On olemassa näille rinnakkainen, funktionaalinen ohjelmointiparadigma.
 
Paul Chiusanon ja Rúnar Bjarnasonin teos Functional Programming in Scala (2015) on tuore johdanto funktionaaliseen ohjelmointiin. Se pysyy paradigmana lähempänä matemaattista lambdakalkyylin mallia, jossa iteroinnin sijaan ikään kuin sievennetään operaatiota, kuin imperatiivinen paradigma. Keskeinen ero on tilamuuttujien käytössä: puhtaasti funktionaalisissa kielissä niitä ei ole tai, kuten todellisissa funktionaalisissa kielissä tehdään, niitä ei suosita. Näin Hartwall-areenan katsojalukumäärää ei koottaisi minkään juoksevan laskurin vaan pitkän, rekursiivisen funktion evaluoinnin kautta hieman fibonaccilukuesimerkin tapaan.

Tilamuuttujien hylkäämisellä saadaan aikaan viitteellinen läpinäkyvyys (referential transparency). Tällöin funktion eli suoritettavan operaation palautusarvo sisältää kaiken sen, mitä funktio tekee, eikä funktiolla ole sivuvaikutuksia.
An expression e is referentially transparent if, for all programs p, all occurrences of e in p can be replaced by the result of evaluating e without affecting the meaning of p. A function f is pure if the expression f(x) is referentially transparent for all referentially transparent x.
Tilamuuttujia voi käyttää funktion sisällä (joissain syheröisissä algoritmeissa se voi olla miltei pakko), mutta ne eivät koskaan näy ulos. Näin muodoin funktionaalinen ohjelmointi on ohjelmointia ilman sivuvaikutuksia. Inside every function with side effects is a pure function waiting to get out. Funktionaaliset kielet suosivat myös rekursiota. Esimerkiksi Scalan—siis ohjelmointikielen—kääntäjä osaa kirjoittaa ns. häntärekursion auki silmukaksi ilman yhtäältä tilamuuttujia ja ja toisaalta kallista kirjanpitoa.

Chiusano ja Bjarnason esittelevät esimerkkien kautta sivuvaikutusten eliminointia, mutta kaikki esimerkit poikkeuskäsittelystä rinnakkaisohjelmointiin, kirjastorajapinnoista jäsentämiseen pyörivät monadien ympärillä. Niitä käytetään ketjuttamaan operaatiota ja kommunikoimaan sitä, mitä operaatiot tekevät. Tuloksena on vaikuttavan kaunista jälkeä—osin tietysti rekursion takia. Scalassa on lisäksi paljon kaikenlaista, mitä kirjoittajat eivät käsittele.

Ohjelmointikielet muistuttavat toisiaan kapealta sanastoltaan ja syntaksiltaan, mutta niiden taustalla oleva filosofiat, joiden ohjaamana ongelmia puretaan ohjelmakoodiksi, voivat olla hyvin erilaisia. Functional Programming in Scala havainnollistaa erinomaisesti Scalan ja laajemmin funktionaalisen ohjelmoinnin taustalla olevan idean. Kirja ei ole kuitenkaan helppo, enkä pysty soveltamaan monadeja ja niiden tarjoamaa tyylikästä ilmaisuvoimaa rutiininomaisesti het' kirjan luettuani.

Ei kommentteja:

Lähetä kommentti

O niin kuin oikeus

Kun entisen aviomiehen (so., ensimmäisen entisen aviomiehen) pienvaraston sisältö päätyy huutokaupattavaksi maksamattomien laskujen vuoksi,...