Funktionaalinen ohjelmointi

Vuonna 1936 julkaistiin toisistaan erillään kaksi tietojenkäsittelytieteen matemaattisen pohjan muodostavaa laskennan mallia: Turingin kone ja lambda-kalkyyli. 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 enemmän lambda-kalkyyliin. Funktionaaliset ohjelmointikielet ovat jopa hyvin lähellä alkuperäistä lambda-kalkyyliä.

Vuonna 1958 John McCarthy kehitti lambda-kalkyylin pohjalta Lisp-kielen (List Processing) tekoälyohjelmien määrittelyä varten, esimerkkinä siitä kuinka yksinkertainen Turing-täydellinen kieli voi olla. ^[1] Se perustui vahvasti lambda-kalkyyliin mutta salli myös perinteisen imperatiivisen ohjelmoinnin.^lähde?

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-kieliperhe pohjautuu toiseksi vanhimpaan yleisesti käytettyyn ohjelmointikieleen, se on säilynyt yhtenä tunnetuimmista ja käytetyimmistä funktionaalisista ohjelmointikielistä. Iästään huolimatta se ei ole muuttunut merkittävästi toisenlaiseksi kuten Fortran.

70-luvun lopulla Robin Milner yhdisti tyyppiteorian ja teoreemantodistajien tutkimusta konkreettiseen funktionaaliseen ohjelmointiin. Tuloksena oli ML-ohjelmointikieli, joka esitteli automaattisen tyypinpäättelyn ja käytti matematiikalta näyttävää kielioppia. Siitä kehittyi myöhemmin Standard ML, OCaml ja Haskell, jotka ovat tunnettuja muun muassa vahvasta tyyppijärjestelmästä ja kääntäjien optimointikyvystä. Nykyisin ML-pohjaisten funktionaalisten kielten ja niiden tyyppijärjestelmien sekä optimoinnin tutkimus on hyvin vilkasta.

Funktionaalisen ohjelmoinnin eduiksi sanotaan:

• Selkeä yhteys matematiikkaan, jolloin ohjelma voidaan helposti kirjoittaa vastaamaan määritelmää ja todistaa oikeaksi induktiolla.^lähde?
• Parempi tuki funktioiden käsittelylle (funktio parametrina, lambda-lauseke, funktioiden kompositio, currying eli curry-muunnos tai ”kuritus”), jolloin ohjelma usein voidaan jakaa pienempiin ja yleiskäyttöisempiin osiin.^lähde?
• Koska sivuvaikutuksia ei ole, funktioiden suoritusjärjestys on vapaa ja kääntäjä voi optimoida samanlaiset funktiokutsut yhdeksi.^lähde?
• Rinnakkaisuus ei aiheuta lainkaan vaikeuksia, koska jaettavaa tilaa ei ole. Periaatteessa jokainen funktiokutsu voitaisiin suorittaa eri säikeessä.^lähde?
• Ohjelmoija oppii määrittelemään ohjelmia täsmällisesti, soveltamaan rekursiota ja käyttämään geneerisyyttä.^lähde?
• Ohjelmointikieli on monesti yksinkertaisempi suunnitella ja toteuttaa.^lähde?

Haittoihin kuuluu koodin tehottomuus ellei ohjelmointikielen kääntäjä tee erityistoimenpiteitä.^[2] Tyypillisesti mukana on jotain imperatiivisen ohjelmoinnin piirteitä kuten let-ilmaisu.^[2]

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

Yleisesti ohjelmointikielen esittelyssä käytetyn Hei maailma -ohjelman vastine funktionaalisissa ohjelmointikielissä on funktio, joka laskee Fibonaccin lukuja^{kenen mukaan?}:

 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.

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

Tietojenkäsittelytieteen perusteita opetettiin funktionaalisella Scheme-kielellä noin sadassa oppilaitoksessa vuonna 2007. Tällöin lähes poikkeuksetta oppikirja on kehuttu Structure and Interpretation of Computer Programs^{kenen mukaan?}. Kirjan verkkoversio ja videoluennot ovat saatavilla verkosta.

Yleensä funktionaalisia kieliä ei käytetä perusopetuksessa, mutta tästä on nähtävissä yhä enemmän poikkeuksia, myös Suomessa. Esimerkkinä tästä on Tiina Partasen kirjoittama Racket-ohjelmoinnin oppimateriaali. Yliopistoissa funktionaalista ohjelmointia opetetaan usein syventävällä kurssilla esimerkiksi Haskell- tai Scheme-ohjelmointikielellä. Tästä on kuitenkin poikkeuksia. Imperial College Lontoossa aloittaa ohjelmoinnin opetuksen kuuden viikon mittaisella Haskell-kurssilla, siinä missä esimerkiksi Suomessa Haskell-kieltä opiskellaan yleensä vasta toisena tai kolmantena opiskeluvuonna tai syventävissä opinnoissa.

Koska suomenkielistä oppimateriaalia on hyvin vähän tarjolla, ovat jotkin yksityishenkilöt päätyneet tarjoamaan ilmaista oppimateriaalia Haskell-kielen ideoiden opiskeluun. Haskell-kielen oppiminen tukee hyvin minkä tahansa funktionaalisen tai funktionaalisia piirteitä sisältävän ohjelmointikielen oppimista. Tästä on esimerkkinä Juuso Vuorisen kirjoittama teos Kanaherkun tuoksuinen johdatus funktionaaliseen ohjelmointiin. Teos korostaa tiedon käsittelyn näkökulmaa ja siinä tutkitaan jo moniin muihinkin ohjelmointikieliin tiensä löytäneet funktionaalista ohjelmointiparadigmaa edustavat funktiot map, filter ja fold (reduce). Edellä mainitut funktiot ovat käytössä myös lukuisissa ei-funktionaalisissa kielissä, joten niiden oppimisesta on hyötyä monen eri ohjelmointikielen ymmärtämisessä.

On myös huomattu, että funktionaalinen ohjelmointi tukee matematiikan oppimista - esimerkkinä algebran ja funktionaalisen ohjelmoinnin välillä havaittu positiivinen siirtovaikutus. Ohjelmointiajattelua väitöskirjassaan ruotinut TkT Pia Niemelä totetaa, että "erityisesti funktionaaliset kielet tuottavat vastavuoroisia hyötyjä matematiikan opetuksen kanssa".^[3]

• Hughes, John: Why Functional Programming Matters
• Koh, Amanda: Imperial College Student Blogs (Arkistoitu – Internet Archive)
• McCarthy, John: ”IV LISP Session”, History of LISP, s. 173-185. (History of Programming Languages) Association for Computing Machinery, Academic Press, 1981. ISBN 0-12-745040-8 Teoksen verkkoversio. (englanniksi)
• Nykänen, Matti: Johdatus funktionaaliseen ohjelmointiin -luentokalvot^{[vanhentunut linkki]}
• Structure and Interpretation of Computer Programs – 2nd ed. (Arkistoitu – Internet Archive)
• Hal Abelsonin & Gerald Jay Sussmanin videoluennot
• Niemelä, Pia: From legos and logos to lambda : a hypothetical learning trajectory for computational thinking. Tampere: Tampere University of Technology, 2018. ISBN 978-952-15-4183-4 Teoksen verkkoversio. (englanniksi)
• Partanen, Tiina: Racket koodiaapinen
• Vuorinen, Juuso: Kanaherkun tuoksuinen johdatus funktionaaliseen ohjelmointiin (Arkistoitu – Internet Archive)

•   Kuvia tai muita tiedostoja aiheesta Funktionaalinen ohjelmointi Wikimedia Commonsissa