Funktionaalinen ohjelmointi

Funktionaalinen ohjelmointi on ohjelmointiparadigma, joka perustuu täysin matemaattisen funktion käsitteeseen. Toisin kuin imperatiivisessa ohjelmoinnissa, funktiolla ei ole sivuvaikutuksia eli sen arvo on aina sama samoilla parametreilla. Puhtaasti funktionaalisissa ohjelmissa ei ole lainkaan tilaa eikä siten myöskään sijoituslausetta tai silmukoita: muuttujaan ei voida sijoittaa uutta arvoa, ja suuret tietomäärät käsitellään rekursion avulla.

Monet funktionaaliset ohjelmointikielet (mukaanlukien useimmat Lisp-johdannaiset) eivät ole puhtaasti funktionaalisia, vaan tukevat myös tilamuuttujia ja sivuvaikutuksia. Puhtaasti funktionaalisilla kielillä on joitain ongelmallisia kohtia, kuten monimutkainen syötön ja tulostuksen toteutus, joka vastaavasti on helppo toteuttaa jos sivuvaikutukset sallitaan.

Historia

Vuonna 1936, siis ennen tietokoneita, toisistaan erillään julkaistiin kaksi tietojenkäsittelytieteen matemaattisen pohjan muodostavaa laskennan mallia: Turingin kone ja lambda-laskenta. Turingin kone on tietokoneen matemaattinen malli: ohjelman suoritus etenee koneen tilaa muuttamalla. Lambda-laskenta mallintaa funktion laskentaa: sieventämällä lauseketta säännöllisesti yksinkertaisemmaksi saadaan selville funktion arvo.

Pian Turingin koneen ja lambda-laskennan huomattiin olevan sama asia eri tavalla määriteltynä: toisin sanoen Turingin koneen ja lambda-laskennan ohjelmat voidaan kääntää toisikseen. Kummatkin mallit ovat olleet hyödyllisiä: Turingin koneen pohjalta kehittyi aikanaan tietokone, mutta ohjelmointikielet perustuvat lambda-laskentaan. Funktionaaliset ohjelmointikielet ovat hyvin lähellä alkuperäistä lambda-laskentaa.

Vuonna 1958 John McCarthy kehitti lambda-laskennan pohjalta Lisp-kielen (List Processing) tekoälyohjelmien määrittelyä varten, esimerkkinä siitä kuinka yksinkertainen Turing-täydellinen kieli voi olla. Se perustui vahvasti lambda-laskentaan mutta salli myös perinteisen imperatiivisen ohjelmoinnin.

Lispin ei ollut tarkoitus olla oikea ohjelmointikieli. Siitä huolimatta McCarthyn kollega Steve Russell ohjelmoi Lisp-tulkin tietokoneelle. Erilaiset Lispin muunnelmat yleistyivät nopeasti ohjelmointikäytössä. Vaikka Lisp on toiseksi vanhin yleisesti käytetty ohjelmointikieli, se on säilynyt tunnetuinpana ja käytetyinpänä funktionaalisena ohjelmointikielenä. Iästään huolimatta se ei ole muuttunut merkittävästi toisenlaiseksi kuten Fortran.

Funktionaalisen ohjelmoinnin etuja

• Selkeä yhteys matematiikkaan, jolloin ohjelma voidaan helposti kirjoittaa vastaamaan määritelmää ja todistaa oikeaksi induktiolla.
• Parempi tuki funktioiden käsittelylle (funktio parametrina, nimetön lambda-funktio, funktioiden kompositio, currying), jolloin ohjelma usein voidaan jakaa pienempiin ja yleiskäyttöisempiin osiin.
• Koska sivuvaikutuksia ei ole, funktioiden suoritusjärjestys on vapaa.
• Rinnakkaisuus ei aiheuta lainkaan vaikeuksia, koska jaettavaa tilaa ei ole. Periaattessa jokainen funktiokutsu voitaisiin suorittaa eri säikeessä.
• Kääntäjä voi optimoida samanlaiset funktiokutsut yhdeksi.
• Ohjelmoijaa oppii määrittelemään ohjelmia täsmällisesti, soveltamaan rekursiota ja käyttämään geneerisyyttä.
• Ohjelmointikielen kielioppi on yksinkertaisempi suunnitella ja toteuttaa.

Esimerkkejä

Esimerkeissä käytetään matematiikan tapaista pseudokoodia. Funktion parametreja ei kuitenkaan eroteta sulkeilla tai pilkuilla juuri missään funktionaalisessa kielessä, joten func(x) = 2x ilmaistaan seuraavasti:

func x = 2*x

Fibonaccin luvut

Funktionaalisissa ohjelmointikielissä ”Hello, world”-ohjelman vastine on funktio, joka laskee Fibonaccin lukuja:

fib n = 0, kun n = 0
        1, kun n = 1
        fib (n−1) + fib (n−2), kun n > 1

Ylläolevasta käy heti ilmi, että fib ei ole määritelty, jos n < 0.

Funktion määritteleminen toisten funktioiden avulla

Leikitään, että voidaan käyttää vain kahta funktiota:

plusyksi x = x + 1
miinusyksi x = x - 1

Niinpä funktio, joka lisää parametriinsa kaksi, voidaan määritellä edellisen avulla:

pluskaksi x = plusyksi (plusyksi x)

Funktio, joka lisää yhteen parametrit x ja y, onnistuu rekursion avulla:

plus x y = x, kun y = 0
           plus (plusyksi x) (miinusyksi y), kun y > 0

Funktionaalinen ohjelmointi opetuksessa

Melko usein tietojenkäsittelytieteen perusteet opetetaan Scheme-kielellä, joka on Lispin yksinkertainen murre. Tällöin oppikirja on lähes poikkeuksetta Structure and Interpretation of Computer Programs, jota pidetään erinomaisena teoksena. Kirjan verkkoversio ja videoluennot ovat saatavilla verkosta.

Lähteet

• Matti Nykänen: Johdatus funktionaaliseen ohjelmointiin -luentokalvot
• Structure and Interpretation of Computer Programs – 2nd ed.
• Hal Abelsonin ja Gerald Jay Sussmanin videoluennot
• John Hughes: Why Functional Programming Matters