Sisällys

• 1 Mitä se on?
  • 1.1 Perusajatus
  • 1.2 Funktionaalinen vs. proseduraalinen ohjelmointi
  • 1.3 Motivointi
  • 2 Peruspiirteitä
    • 2.1 Arvot ja funktiot
    • 2.2 Evaluointimallit
    • 2.3 Currying
    • 2.4 Tyypit
    • 2.5 Arvoalueet
    • 2.6 Useita argumentteja
    • 2.7 Polymorfismi
    • 2.8 Tyyppiluokat
  • 3 Muita ominaisuuksia
    • 3.1 Rekursio
    • 3.2 Listat
    • 3.3 Roskienkeruu
    • 3.4 Koodin uudelleenkäyttö ja tiedon kapselointi
  • 4 Funktionaaliset kielet
  • 5 Kritiikkiä

  • Viitteet ja kirjallisuutta
  • Liite: esimerkkikoodit selityksineen

  ---

  1 Mitä se on?

  Lyhyesti määriteltynä funktionaalinen ohjelmointi on deklaratiivinen ohjelmointiparadigma.

  Ohjelmointiparadigma tarkoittaa, että tapaa ja mallia ohjelmoida. Se on filosofia ja käytäntö mieltää, jäsentää ja esittää ohjelmointiongelma tietyn dogman mukaan. Muita paradigmoja ovat mm. proseduraalinen paradigma ja oliosuuntautunut paradigma. Deklaratiivinen tarkoittaa, että paradigma esittää asiat niiden välisillä suhteilla, relaatioina.

  1.1 Perusajatus

  Perusajatuksena on heittää tilan (state) ja sekvenssoinnin (sequencing) käsiteet harakoille. Ohjelma ei semanttisessa mielessä enää koostukaan sarjasta tietyssä järjestyksessä suoritettavia komentoja ja sijoituksia, joilla muutetaan muistiin varastoitua tietoa ohjelman tilasta.

  Sen sijaan ohjelma muodostuu funktiomäärittelyistä, niiden yhdistämisestä ja niiden soveltamisesta argumentteihin. Argumentit eivät ole eksplisiittisiä viittauksia muistiin, vaan pikemminkin merkintöjä arvoille (denotations of values). Sovellettava funktio puolestaan palauttaa arvonaan tuloksen, joka kuvaa funktion arvoa kyseisillä argumenteilla. Palautettava arvo voi olla myös funktio. Tämä kaikki johtaa siihen, että funktiot ovat sivuvaikutuksettomia. Tällöin funktiot eivät saa muuttaa argumenttiensa arvoja, eivatkä ne siihen pystykään. Käytössähän ei ole mitään tilaa, mitä muuttaa.

  Semanttisesti tämä muistuttaa matematiikasta tuttua funktion käsitettä. Tämä ei ole sattumaa, sillä ajatus funktionaalisesta ohjelmoinnista on aikoinaan syntynyt juuri toiveesta esittää ohjelmat 'matemaattisina' määrittelyinä. Ei liene yllätys, että funktionaaliset ohjelmointikielet lainaavat myös syntaksiaan matemaattisilta funktioilta, mutta ne toki soveltavat säännöt ja merkistöt nykyisille tietokoneille sopiviksi.

  1.2 Funktionaalinen vs. proseduraalinen ohjelmointi

  Edellä oikeastaan tuli jo mainittua tärkein ero funktionaalisen ja proseduraalisen ohjelmoinnin välillä, mutta kerrataan vielä:

  'It is this implicit semantic appeal to the notion of state that marks the difference between functional and imperative programs. Functional programs do not semantically require the the notion of state whereas imperative programs do.'
  [Tur], s. 7.

  Tätä eroa voitaneen havainnollistaa (ehkä hiukan typerällä) esimerkillä, joka kuitenkin kuvaa ajatusmallien eroa aika hyvin [Gla].

  Vaja voitaisiin rakentaa proseduraalisesti seuraavasti:

     Rakentaaksesi vajan
      1) laske perustus,
      2) rakenna seinät,
      3) tee lattia ja 
      4) pystytä katto.
  

  Funktionaalisesti sama määritys voisi olla

     Vaja koostuu
      1) seinistä, joita perustukset tukevat,
      2) lattiasta, jota perustukset tukevat sekä
      3) katosta, jota seinät tukevat
  

  Proseduraalinen määrittely antaa tarkan järjestyksen vajan rakentamiselle , kun taas funktionaalinen määrittely määrää ainoastaan vajan osien suhteet. Tästä nähdään myös toinenkin paradigman ominaispiirre eli funktionaaliset ohjelmat ovat yleensä abstraktiotasoltaan korkeampia kuin proseduraaliset. Mikäli kirvesmies yo. kuvausten perusteella rakentaisi kaksi vajaa, niin ne saattaisivat ulkonäöltään tai rakentamistavaltaan poiketa toisistaan hyvinkin paljon. Funktionaalinen kuvaushan ei ota esim. rakennusjärjestykseen mitään kantaa, mutta oleellisesti niissä kuitenkin olisi samat piirteet. Voidaan sanoa, että proseduraalinen paradigma määrää ohjelman suorituksen eksplisiittisesti, kun taas funktionaalinen paradigma määrää ohjelman suorituksen implisiittisesti.

  Naivisti voisi ajatella onko touhussa mitään mieltä, sillä allahan on kuitenkin von Neumannilainen konearkkitehtuuri. Ohjelmathan käännetään funktionaalisesta kielestä konekielelle, joka perustuu peräkkäin suoritettavaan ja jotain tiettyä muistissa olevaa tilaa modifioivaan järjestelmään, jolloin kaikki hieno funktionaalisuus menetetään. Hommassa on kuitenkin järkeä: villakoiran ydin onkin siinä, että ohjelmamäärityksen laativalle ohjelmoijalle tilanne on semanttisesti läpinäkyvä. Ohjelmoijan ei tarvitse välittää tuon taivaallista siitä, miten ohjelma lopulta käännetyssä muodossa suoritetaan, kunhan itse ohjelman määritys tapahtuu funktionaalisesti.

  1.3 Motivointi

  Miksi sitten funktionaaliseen ohjelmointiin kannattaisi tutustua? Mikä motoivoi sen tutkimisen? Vilkaistaanpa hieman historiaa.

  Ensimmäinen funktionaalinen kieli oli LISP, jonka John McCarthy kehitti 1950-luvun lopulla. McCarthyn tavoitteena oli luoda kieli, joka sopisi paremmin tekoälyohjelmointiin kuin silloiset valtakielet IPL ja FORTRAN. McCarthyn luomus oli jotain todella erilaista aiempiin ohjelmointikieliin verrattuna, ja se säilyi melko pienen piirin työkaluna.

  1960-luvulta alkaen ohjelmistojen tekijät joutuivat vähitellen ongelmalliseen tilanteeseen. Tietokoneita ja niiden ohjelmistoja alettiin käyttää yhä isommassa mittakaavassa mitä erilaisimpiin tarkoituksiin. Tämä johti tilanteeseen, jossa ohjelmistojen koot kasvoivat liian suuriksi, jotta yksi ihminen tai edes pieni ryhmä pystyi hallitsemaan niiden laatimista. Tämän ns. ohjelmistokriisin (software crisis) [Pre] ratkaisemiseksi alettiin kehittää sekä ohjelmointityökaluja että -menetelmiä. Päivänvalon näkivät niin olio-ohjelmointi kuin formaalit menetelmätkin. Yhtenä ratkaisuna tähän nousi esiin ajatus siitä, että voitaisiinko ohjelmat ja ohjelmistot määritellä matemaattisesti jonkin aksiomaattisen järjestelmän mukaan. Tämä sama ajatus oli ollut jo LISPin takana, joten katseet kääntyivät luonnollisesti LISPin takana oleviin matemaattisiin perusteisiin. LISPin pohjana olleet Kleenen funktioteoria ja Churchin lambda-laskenta muodostavatkin nykyään funktionaalisten kielten aksiomaattisen perustan [App]. Funktionaaliset kielet lainaavatkin varsinkin lambda-laskennalta paljon sekä semanttisesti että syntaktisesti. Onkin sanottu, että "funktionaaliset kielet ovat periaatteessa vain saman kielen (lambda-laskennan) murteita, joilla yritetään päästä edes joten kuten luettavaan koodiin" [Rui].

  Funktionaalisen paradigman tavoitteena on tuottaa parempia ohjelmia nopeammin. Ohjelmien oikeellisuuden parantamiseen pyritään käyttämällä matemaattisesti perusteltua aksiomaattista järjestelmää. Tarvittaessa ohjelmat voidaan todistaa oikeiksi helpommin kuin proseduraalisella algoritmilla laaditut ohjelmat. Ohjelmien kehityksen nopeuttamiseen pyritään korkealla abstraktion tasolla.

  2 Peruspiirteitä

  Funktionaalisen paradigman lähtökohtana siis oli esittää asiat matemaattisen funktion käsitteen avulla. Funktion kuvailemiseen liittyy oikeastaan kaksi asiaa. Ensinnäkin tarvitaan funktion 'toiminnallinen' kuvaus. Toiseksi tarvitaan tieto funktion lähtö- ja maalijoukosta eli funktion argumenteille ja arvolle pitää olla jokin tietty tyyppi. Funktioiden arvojen selvittäminen perustuu lauseiden evaluointiin (evaluation of expressions) sovittamalla lauseisiin kaavoja, jotka itsessään ovat lauseita, ja redusoimalla lauseet tiettyjen menetelmien mukaan. Tietyssä mielessä funktiot eivät kuvaa toimintaa, vaan erilaisia arvojen välisiä relaatiota ja assosiaatiota.

  Seuraavassa hieman selvitetään, mistä on kysymys. Esimerkit on kirjoitettu Haskell -kielellä. Haskeliä on viime vuosina kehitty määrätietoisesti tavoitteena luoda standardikieli funktionaaliseksi ohjelmointikieleksi. Haskell on monipuolinen kieli ja se toteuttaa suurimman osan funktionaalisen paradigman 'opeista'. Lisäksi Haskelillä on joitain melko yksilöllisiä piirteitä (joihin tässä ei paljoa puututa).

  2.1 Arvot ja funktiot

  Funktioiden avulla määritellään ohjelman toiminta. Voidaan sanoa, että funktiot ovat 'ensimmäisen luokan kansalaisia', sillä koko paradigma pyörii niiden ympärillä. Kaikki toiminta kuvataan funtioilla ja niiden palauttamilla arvoilla (values).

  Funktiot muodostuvat lauseista (expression) ja muodostavat itse lauseita. Kaikki laskenta tehdään evaluoimalla lauseita. Lauseiden evaluoinnin tuloksina saadaan arvoja. Erilaiset lauseet kuvaavat erilaisia arvoja. Sovittamalla muista lauseista saatuja kaavoja ja sisäänrakennettuja sääntöjä, saadaan kulloinkin evaluoitavana oleva lause tarvittessa redusoitua atomaariseen arvoonsa.

  Esimerkkinä funktion määrittelystä otetaan zip-funktio

          zip (x:xs) (y:ys) = (x,y) : zip xs ys
          zip xs ys = []
  
                      (katso selitys liitteestä)
  

  joka lomittaa toisiinsa kaksi listaa. Tässä nähdään sekä funktion määrittely, että funktion soveltaminen. Koodi määrittelee funktion zip, ja tässä määrittelyssä sovelletaan operaattoria :, jolla listaan liitetään ja erotetaan alkioita. Operaattorin soveltaminen on samalla funktion soveltamista, sillä Haskelissä operaattorit ovat vain funktioita, jotka on tyyppiluokkien avulla ylimääritelty. Ylimäärittelyyn palaamme myöhemmin.

  2.2 Evaluointimallit

  Evaluointimalleja on kaksi: tiukka (strict) ja laiska (lazy, non-strict). Tiukassa mallissa lauseet evaluoidaan aina, tarvittiin niitä sitten tai ei. Tämän seurauksena syntyy virhetilanne, mikäli jokin lause on päättymätön, ts. sitä ei pystytä evaluoimaan. Mallin hyödyt ovat hieman kyseenalaisia. On kyllä totta, että näin saadaan jo käännösvaiheessa havaittua päättymättömät lauseet, mutta toisaalta ohjelmoitaessa pitää olla hyvin tarkka, miten funktiot määritellään. Väärä määrittelyjärjetys saattaa tehdä sinänsä oikeasta ohjelmasta kääntäjälle kelpaamattoman.

  Laiskassa mallissa lauseet evaluoidaan vasta tarvittaessa. Laiskasti evaluoivat kielet ovat yleensä nopeampia, sillä ne eivät turhaan evaluoi argumentteja. Ohjelmoijan ei tarvitse välittää määrittelyjen järjestyksestä. Samalla ne mahdollistavat äärettömien rakenteiden muodostamisen. Esimerkkinä mainittakoon, että Haskell on laiska kieli.

  2.3 Currying

  Funktiot voivat palauttaa arvoinaan funktioita. Tähän liittyy eräs mielenkiintoinen piirre, jota hyödynnetään funktionaalisten kielten toteutuksissa. Jos funktiolle viedään useita argumentteja, niin funktiota sovelletaan niistä ensimmäiseen. Arvona palautetaan uusi funktio, jota sovelletaan seuraavaan argumenttiin ja niin edelleen. Tällaista menettelyä kutsutaan Curryingiksi (curryng) loogikko Haskell Curryn mukaan (harjoitustehtävä: mistä ohjelmointikieli Haskell on saanut nimensä?).

  Tässä ei näytä olevan paljoakaan järkeä, mutta ominaisuus on hyödyllinen tarkasteltaessa funktioiden tyypitystä.

  2.4 Tyypit

  Tyypit (types) määräävät, millaisia arvoja funktiot voivat saada argumentteinaan ja millaisia arvoja ne voivat palauttaa. Tyypin käsite on tärkeä, sillä ilman tyypien eksplisiittistä määräämistä ja sitomista (binding) funktioon ei funktiota ole määritelty kunnolla. Ilman tyyppimäärittelyä voitaisiin joutua esimerkiksi tilanteeseen, jossa yritettäisiin evaluoida lausetta (6 - True), mikä ei liene missään kontekstissa mielekästä.

  Tyypit liittyvät arvoihin siten, että tietyllä arvolla on tietty tyyppi. Tyyppi on arvon ominaisuus, ei siis itsenäinen yksikkö. Tyypit kuvailevat arvoa. Arvon assosiaatiota tyyppiin kutsutaan arvon tyypitykseksi (typing). Haskelin notaatiota lainaten voitaisiin kirjoittaa esim.

          5 :: Int
  

  mikä luettaisiin 'numerolla viisi on tyyppi Int' (tämä tosin on pseudokoodia).

  2.5 Arvoalueet

  Kuten jo peruskoulussa opetettiin, liittyy matemaattisen funktion tyyppiin kaksi osaa: lähtö- ja maalijoukko (domain ja range). Funktion arvot määriteltiin f:A->B, missä A oli lähtöjoukko ja B maalijoukko. Funktionaalinen ohjelmointi perii käsitteet suoraan tuosta määrittelystä. Funktion voidaan sanoa ottavan argumentit A:ssa ja palauttavan arvon B:ssä.

  Esimerkiksi Haskelissä määritellään seuraajafunktio succ

          succ n = n + 1
  

  Funktion tyypitys (type signature declaration) voisi olla

          succ :: Int -> Int
  

  mikä määrittäisi funktion kuvaavan kokonaislukuarvon toiseksi kokonaislukuarvoksi.

  2.6 Useita argumentteja

  Entäpä, jos funktiolla on useampia argumentteja? Currying hoitaa tämän. Koska funktiolla voidaan käsittää olevan vain yksi parametri, tyypitetään se oikein. Arvona saadaan toinen funktio, jota sovelletaan toiseen parametriin jne. Saadaan ketju tyypityksiä, jotka määräävät koko funktion tyypin.

  Esimerkiksi map-funktio voitaisiin Haskelissa tyypittää

          map :: (a->b) -> [a] ->[b]
  

  Nyt ensimmäinen tyyppi (a->b) tyypittää ensimmäisen argumentin olevan funktio tyyppiä a->b. Tämän jälkeen funktion map ja argumentin (a->b) palauttamaa funktiota sovelletaan argumenttiin [a], jolloin palautuu arvo [b]. Ei puututa tässä map-funktion varsinaiseen toteutukseen.

  2.7 Polymorfismi

  Joskus tarvitaan tyyppimäärityksiä, jotka soveltuvat eri tyyppisille argumenteille. Esimerkiksi listaa manipuloivat funktiot eivät useinkaan välitä siitä, minkä tyyppisistä alkioista lista koostuu. Tyypitykset, jotka soveltuvat useammille erityyppisille arvoille, ovat monimuotoisia eli polymorfisia (polymorphic). Toisaalta myös operaatiot voivat olla polymorfisia, jolloin periaatteessa sama operaatio käyttäytyy eri tavalla erityyppisten arvojen kanssa. Operaatioiden polymorfisuutta tarvitaan myös tilanteessa, missä semanttisesti samanlainen operaatio pitää määrittää useille eri tyypeille. Esimerkiksi liukuluvun yhtäsuuruus toisen liukuluvun kanssa on semanttisesti samankaltainen kuin murtolukujen yhtäsuuruus, mutta näiden toteuttaminen samalla tavalla ei onnistu.

  Polymorfismia on siis kahta tyyppiä eli ns. parametrista polymorfismia (ensin mainittu polymorfismi eri tyyppisille arvoille) ja 'ad hoc' -polymorfismia eli lisämäärittelyä (overloadig).

  Funktionaaliset kielet toteuttavat yleisesti parametrisen polymorfismin, muuten esim. listoihin kohdistuvien funktioiden tyypitys tulisi ylen hankalaksi. Esimerkiksi funktio lenght, joka palauttaa listan pituuden, voidaan Haskelissä määritellä

          length        :: [a] -> Int
          length []     =  0
          length [x:xs] =  1 + length xs
  
                      (katso selitys liitteestä)
  

  Tässä tyypitys [a] -> Int kuvaa kokonaisluvuksi listan, jonka alkiot ovat tyyppiä a (a on siis mikä tahansa tyyppi).

  Ylimäärittelyn toteuttavia kieliä ei ole kovin montaa ja niiden kohdalla on syytä olla varovainen hieman harhaanjohtavan terminologin vuoksi. Siitä seuraavassa.

  2.8 Tyyppiluokat

  Usein funktionaalisten kielten yhteydessä kuulee puhuttavan siitä, miten jokin kieli on oliosuuntautunut. Hyvin karkeasti yleistäen olio on joukko proseduureja (metodeja), jotka jakavat yhteisen tilan jatähän tilaan pääsevät vaikuttamaan vain ja ainoastaan nämä metodit.

  Funktionaalisen paradigman tavoitteena oli poistaa tilan käsite, joten puhe oliosuuntautuneesta funktionaalisesta kielestä -- ainakin puhtaasta sellaisesta -- kuullostaa lähinnä humpuukilta. Ja sitähän se onkin. Luokista (ja olioista) puhuttaessa kyseessä ovat yleensä ns. tyyppiluokat, jotka voidaan tietyllä tavalla mieltää olioiden sukulaisiksi. Niitä voidaan luontevimmin kuvata samoilla -- tai ainakin samankaltaisilla -- termeillä kuin olioita, mutta ne eivät sinänsä ole olioita.

  Tyyppiluokkien (type classes) avulla toteutetaan edellä mainittu lisämäärittelytyyppinen polymorfismi. Tutkitaan asiaa esimerkin avulla. Haskelissa lisämäärittely määritellään käyttäen luokkamäärittelyä (class declaration) ja instanssimäärittelyä (instance declaration). Luokkamäärittely määrittelee yleisen tyypin operaatiolle.

  Esimerkiksi yhtäsuuruusluokka voitaisiin määritellä

          class Eq a where
            (==) :: a -> a -> Bool
  
                      (katso selitys liitteestä)
  

  Nyt yhtäsuuruus == on tyypitetty mille tahansa tyypille a. Se pitää vielä toteuttaa eri tyypeille, sillä onhan esim. kokonaislukujen vertaaminen melko erilaista kuin liukulukujen. Tämä tapahtuu käyttämällä instanssimäärittelyä muodossa

          instance Eq Int where
            x == y  = intEq x y
   
          instance Eq Float where
            x == y  = floatEq x y
  
                      (katso selitys liitteestä)
  

  Vielä kun määritellään funktiot intEq ja floatEq, niin operaattoria == voi käyttää sekä kokonais- että liukulukujen vertailuun (itse asiassa nämä funktiot on määritelty kielessä itsessään).

  Edelleen jonkin luokan ominaisuudet voidaan periä toiseen luokkaan:

          class (Eq a) => Neq a where
            (==), (/=) :: a -> a -> Bool
             x /= y    =  not ( x == y )
  

  Tällöin Neq perii Eq:n == -operaattorin, ja koska yhtäsuuruus == oli määritelty kokonaisluvuille ja liukuluvuille, on myös erisuuri määritelty molemmille.

  Tässä ei tosiaankaan ole kysymys mistään olioajattelusta, vaan kyseessä on ylimäärittelytyyppisen polymorfismin soveltaminen. Terminologia ja 'periytyminen' kylläkin hämäävät melko onnistuneesti.

  3 Muita piirteitä

  Edellä mainittujen peruspiirteiden lisäksi funktionaalisissa kielissä on joitain piirteitä, jotka toteutuvat tai korostuvat melkein kaikissa kielten toteutuksissa.

  3.1 Rekursio

  Itse ohjelmointityyliin funktionaalisilla kielillä ohjelmoitaessa liittyy oleellisena osana rekursio. Esimerkiksi joka pojan suosikkialgoritmi lajitteluun voitaisiin määritellä (ja kannattaakin määritellä) muodossa

          quicksort       :: (Ord a) => [a] -> [a]
          quicksort []    =  []
          quicksort (x:xs)=  quicksort [ y | y <- xs, y < x ]
                          ++ quicksort [ x ]
                          ++ quicksort [ y | y <- xs, y >= x ]
  
                      (katso selitys liitteestä)
  

  Tyylikästä, eikö?

  Rekursion runsas käyttö ei sinänsä ole hämmästyttävää, sillä mentäessä paradigman matemaattisissa perusteissa hieman syvemmälle törmätään aika pian rekursiivisten funktioiden teoriaan ja sen soveltamiseen konstruoitaessa funktionaalista paradigmaa.

  3.2 Listat

  Listat ja niiden käsittely kuuluvat myös oleellisena osana funktionaaliseen ohjelmointitapaan. Esimerkiksi LISPissä kielen nimikin tulee sanoista LISt Processing. Useissa funktionaalisissa kielissä -- ehkäpä peräti kaikissa -- listat ovat niin oleellinen tietorakenne, että ne on koodattu kiinni kielen ytimeen. Samoin niiden käyttöön ja muodostamiseen on kiinnitetty paljon huomiota. Esimerkiksi Haskelissa suuri osa ns. syntaktisesta sokerista on laitettu listoihin niin, että niitä olisi helppoa ja vaivatonta käyttää.

  Laiskoissa funktionaalisiin kielissä on lisäksi hauska listoihin liittyvä ominaisuus: päättymättömät listarakenteet. Laiskoissa kielissähän arvoja ei evaluoitu ennen kuin niitä todella tarvittiin. Tämä mahdollistaa sellaisten rakenteiden tehokkaan muotoilun, joiden evaluointi ei pääty koskaan, mutta jotka silti tekevät jotain mielekästä. Lisäksi sama laiska evaluointi mahdollistaa kääntäjien toteuttamisen siten, että tällaiset rakenteet käännetään hyvin tehokkaaksi konekoodiksi.

  Esimerkiksi fibonaccin sarja voitaisiin muotoilla jahtaamaan häntäänsä seuraavasti:

          fib = 1: 1: [ a+b | (a,b) <- zip fib (tail fib) ]
  
                      (katso selitys liitteestä)
  

  Kääntäjässä koodista muodostuisi kuvan mukainen graafi.

  Tämän tapaisilla rakenteilla on jopa ihan oikeaa käyttöä. Esimerkiksi simuloitaessa järjestelmää, johon tulee ulkopuolelta jatkuvasti syötettä, voidaan järjestelmä mallintaa asiakas-palvelin -metaforalla. Asiakas kuvaa ulkopuolelta tulevaa syötettä, ja palvelin prosessoi syötteen. Asikas olisi edullista toteuttaa juuri kuvatunlaisella ikuisella rakenteella, jolloin se ei kuluttaisi paljoakaan koneresursseja.

  3.3 Roskienkeruu

  Yksi funktionaalisten kielten universaali ominaisuus on se, että niiden muistin varaus ja vapauttaminen hoidetaan automaattisesti. Roskien keruu (garbage collection) oikeastaan kuuluu osana paradigmaan. Koska käytössä ei ole muuttujia, ei ohjelman laatija varaa missään vaiheessa muistia. Toisaalta ohjelma kyllä tarvitsee muistia, joten järkevä tapa muistin käyttämiseen on hoitaa homma automaattisesti.

  Sivuhuomatuksena todettakoon, että McCarthy lanseerasi käsitteen LISPin myötä. LISPhän oli ensimmäinen kieli, johon roskien keruu toteutettiin.

  3.4 Koodin uudelleenkäyttö ja tiedon kapselointi

  Koodin uudelleenkäytettävyydessä funktionaalinen ohjelmointi on samalla tasolla kuin proseduraalinen ohjelmointi. Nykyisissä kielissä koodi voidaan jakaa erillisiin moduuleihin, jotka tarpeen vaatiessa tuodaan (import) toisiin moduuleihin. Jotkin kielet toteuttavat myös mekanismit tarpeettoman tiedon kätkemiseen moduuleissa. Esimerkiksi Haskelin moduuleissa on erillinen liittymäosa (interface) ja toteutusosa, jolloin moduulin käyttäjä näkee vain itselleen tarkoitetun, oleellisen osan moduulia.

  4 Funktionaaliset kielet

  Sinänsä ohjelmoinnin funktionaalisuus ei ole kielestä kiinni, vaan funktionaalista ohjelmointia voi harrastaa halutessaan vaikka C:llä, kunhan muistaa ohjelmoidessaan muistaa noudattaa funktionaalisia periaatteita.

  Yleisesti funktionaalisella ohjelmointikielellä tarkoitetaan kuitenkin sellaista kieltä, jossa ohjelman rakenne kuvataan aiemmin esitettyjen periaatteiden mukaan ja joka rohkaisee ohjelmoimaan tällä tyylillä. Tälläisia kieliä on lukuisia. Suurin osa on erilaisia kokeellisia 'laboratoriokieliä', mutta joukkoon mahtuu joitain ihan oikeasti käytettyjä kieliäkin.

  Tunnetuin lienee vanha tuttu LISP, jota on käytetty paljon mm. tekoälytutkimuksessa ja CAD-ohjelmien makrokielenä. LISPistä on useita versioita, joista osa on puhtaasti funktionaalisia ja osa puolestaan vähemmän puhtaita. Esimerkiksi CLOS kuuluu jälkimmäiseen joukkoon, kun taas Sceme edustaa edellistä.

  Toinen tuttu kieli on Mathematican komentokieli, joka myös on luonteeltaan funktionaalinen, vaikka tarjoaakin mahdollisuuden proseduraaliseen ohjelmointiin. Tuntemattomampiin maailmalla käytettyihin funktionaalisiin kieliin kuuluu Erlang, joka on L M Eriksonin kehittämä, lähinnä puhelinkeskusten systeemi- ja varusohjelmistojen ohjelmointiin tarkoitettu ohjelmointikieli. Erlang tarjoaa ns. pehmeän tosi-aikaisuuden.

  Funktionaalisen ohjelmointiyhteisön standardikieleksi on ehdotettu Haskelia. Standardikieleksi standardikielen paikalle haluavat myäs esim. Miranda^(TM), Hope ja erilaiset ML:n johdannaiset, joskaan yksikään niistä ei ole saavuttanut suurempaa suosiota.

  Muista, vähemmän käytetyistä, funktionaalisista kielistä kannattanee mainita Sisal sen numeerisen luonteen vuoksi. Sisal on tarkoitettu tieteelliseen laskentaan rinnakkaisessa ympäristössä, joskin kielestä on myös versiot joillekin ei-rinnakkaisille arkkitehtuureille, esim. HP:lle. Sisal osaa rinnakkaistaa ohjelmat automaattisesti ja generoi kertaluokkaa nopeampaa konekielistä koodia kuin vastaavat automaattisesti rinnakkaistavat FORTRAN-kääntäjät.

  Muutenkin rinnakkaisuus ja nimenomaan automaattinen rinnakkaistaminen ovat funktionaalisten kielten vahvoja alueita. Funktiot ovat sivuvaikutuksettomia, joten periaatteessa mitkä tahansa kaksi erillistä funktiota voidaan laskea toisistaan riippumatta vaikka erillisissä prosessoreissa. Funktionaalisen ohjelmoinnin sanotaankin olevan perinnöllisesti rinnakkainen (perinnöllinen siinä mielessä, että rinnakkaisuus johtuu paradigmasta itsestään).

  Funktionaaliset kielet ovat olleet hitaiden kielten maineessa. Kaikki on kuitenkin suhteellista. Tehokkaita kääntäjiä on alkanut tulla vasta viimeisen kymmenen vuoden aikana. Funktionaalisten kielten nopeusarviot ovat siten perustuneet tulkkeihin, jotka eivät mietenkään ole voineet pärjätä nopeudessa esim. käännetylle C:lle. Lisäksi kääntäjien kehityksessä on otettu huimia askelia viime vuosina ja nykyään funktionaaliset kielet kääntyvät ihan vertailukelpoisiksi muihin kieliin nähden niin nopeudeltaan kuin binäärikoodien koolta.

  5 Kritiikkiä

  Funktionaaliset menetelmät eivät ole tekoälytutkimuksen ulkopuolella saavuttaneet kovin suurta suosiota. LISPiä lukuun ottamatta ei muita paljon käytettyjä kieliä ole ilmestynyt. Proseduraalisella paradigmalla ohjelmoineelle kynnys siirtyä funktionaaliseen ohjelmointiin on melko korkea, sillä ajatusmaailmat ovat niin kovin erilaiset. Toisaalta kunnollista kaupallista/teollista ympäristöä ei ole ollut tarjolla. Akateemiset ympäristöt kyllä ovat toimivia, mutta ne eivät yleensä tue vakavaa ohjelman kehitystä, vaan pikemminkin tarjoavat lähtökohdan omien teoreettisten kokeilujen ja tutkimusten suorittamiseksi.

  Funktionaalinen paradigma on tutustumisen arvoinen. Yleisesti ottaen se tarjoaa paljon proseduraalista ohjelmointia paremmin probleemaorientoituneen metodologian. Tosielämän ohjelmointitilanteissa se kyllä häviää olioparadigmalle, mutta matemaattisiin tehtäviin matematiikasta peräisin oleva formalismi sopii vähintään yhtä hyvin, jos ei paremminkin, kuin oliosuuntautunut paradigma.

  Yksi selkeä heikkous funktionaalisilla kielillä on: syöttö- ja tulsotustoiminnot. Syöttö- ja tulsotustoimintojen käsite ei oikein sovi sivuvaikutuksettomaan ja muuttujattomaan ajatusmalliin. Niinpä kielissä on jouduttu turvautumaan jonkinasteisiin vippaskonsteihin, jotta nämä toiminnot on saatu hoidettua. Esim. Haskelissä on käsite monadi (monad), jonka avulla I/O on tarkoitettu hoidettavaksi.

  Funktionaalisen ohjelmoinnin parhaisiin puoliin kuuluu ohjelmoinnin matemaattisuus, sillä ohjelman määrittäminen on varmalla aksiomaattisella pohjalla. Jos aksiomatiikka on oikein laadittu (niinkuin se näyttää olevan) on ohjelman oikeellinen määrittely todistettavissa huomattavasti helpommin kuin mitä esim. proseduraalisten kielten yhteydessä.

  ---

  Viitteet ja kirjallisuutta

  Viitteet ja muuta luettavaa

  [App] Appleby D.

  "Programming Languages: Paradigm and Practice"
  McGraw-Hill, 1991

  [Bir] Bird R. ja Wadler P.

  "Introduction to Functional Programming"
  Prentice-Hall, 1988

  [Gla] Glaser H., Hankin C. ja Till D.

  "Principles of Functional Programming",
  Prentice-Hall, 1984

  [Has] "Haskell Report"

  URL:http://haskell.cs.yale.edu/haskell-report/haskell-report.html

  [Hen] Henson M. C.

  "Elements of Functional Languages"
  Blackwell, 1987

  [Hud] Hudak P. ja Fasel J. H.

  "Gentle Introduction to Haskell"
  URL:ftp://ftp.dcs.gla.ac.uk/pub/haskell/tutorial/tutorial.ps.Z

  [Hyv] Hyvönen E. ja Seppänen J.

  "LISP-MAAILMA"
  Kirjayhtymä, 1986

  [Pey] Peyton-Jones S. L.

  "The Implementation of Functional Programming Languages"
  Prentice-Hall, 1987

  [Pre] Pressman R. S.

  "Software engineering: Practioner's Approach",
  European 3rd Rev. Ed., McGraw-Hill, 1994

  [Rui] de Ruiter J-P.

  "Not the comp.lang.functional FAQ"

  [Tur] Turner R.

  "Constructive Foundations of Functional Languages",
  McGraw-Hill, 1991

  Joitain resursseja verkossa

  [FAQ] "A Frequently Asked Questions list (FAQ) for comp.lang.functional"

  URL:http://www.cs.nott.ac.uk/Department/Staff/mpj/faq.html

  [New] "Newsgroup: comp.lang.functional"

  URL:news:comp.lang.functional

  [Mou] "Jon Mountjoy's functional languages page"

  URL:http://carol.fwi.uva.nl/~jon/func.html

  ---

  Liite: esimerkkiohjelmat ja niiden selitykset

  zip -funktio

  Funktio zip limittää kaksi listaa toisiinsa vähän samaan tapaan kuin vetoketjun hampaat limittyvät toisiinsa vetoketjua kiinni vedettäessä.

          zip :: [a] -> [b] -> [(a,b)]                    -- rivi 1
          zip (x:xs) (y:ys) = (x,y) : zip xs ys           -- rivi 2
          zip xs ys = []                                  -- rivi 3
  

  Kommenttimerkki -- kommentoi rivin lopun. Tyypitys

          zip :: [a] -> [b] -> [(a,b)]                    -- rivi 1
  

  voitaisiin lukea "zip ottaa argumentteinaan listaa, joiden alkiot ovat tyyppiä a ja b. Nämä listat kuvataan listaksi, jonka alkiot ovat tyyppiä (a,b)."Listan alkiot ovat aina samaa tyyppiä. Kirjaimet a ja b edustavat mitä tahansa tyyppiä. Periaatteessa eo. tyypityksessä a ja b voisivat olla eri tyyppisiä, mutta koska molemmat tyypit kuvautuvat samaan listaan, on niiden oltava samaa tyyppiä.

  Funktiolle siis viedään argumentteina kaksi listaa. Rivillä 1 oleva merkintä x:xs tarkoittaa listan ensimmäistä alkiota x yhdistettynä : loppuun listaan xs. Rivillä 2 oleva merkintä xs tarkoittaa listaa yleensä. Miten sitten voidaan erottaa kumpaa määrittelyä sovelletaan? Mikäli listassa on alkiota -- vaikka vain yksi kappale -- voidaan tehdä ero listan ensimmäisen alkion ja lopun listan kanssa. Tällöin sovelletaan rivin 2 määrittelyä. Mikäli listassa ei ole yhtään alkiota, ei rivin 2 määrittelyä voida soveltaa mutta rivin 3 määrittely sopii myös tähän tilanteeseen. Periaatteessa rivin 3 määritelmät sopisivat minkä tyyppisiin argumentteihin tahansa, mutta tyypitys estää tämän.

  Funktio käyttää rekursiota hyväkseen muodostaessaan yhdistetyn listan kahdesta ei-tyhjästä listasta.

          zip (x:xs) (y:ys) = (x,y) : zip xs ys           -- rivi 2
  

  Listojen ensimmäiset alkiot liitetään arvona palautettavaan listaan. Tämän jälkeen molempien listojen lopuille alkioille xs ja ys tehdään rekursiivisesti sama zip-funktio. Kun listojen alkiot loppuvat, rivin 3 määrittely päättää rekursion palauttamalla arvonaan tyhjän listan

          zip xs ys = []                                  -- rivi 3
  

  Tätä määrittelyä tietysti sovelletaan aiemminkin, jos listat olivat jo alunperinkin tyhjiä.

  succ -funktio

  Funktio succ lisää argumettiinsa 1:n.

          succ :: Int -> Int,
          succ n = n + 1
  

  Tyypitys

          succ :: Int -> Int
  

  kertoo funktion kuvaavan kokonaisluvun toiseksi kokonaisluvuksi.

  Varsinainen funktiomääritelmä

          succ n = n + 1
  

  sitten toteuttaa funktion triviaalilla tavalla. Argumettiin n lisätään ykkönen lauseella n + 1.

  length -funktio

  Funktio length laskee listan alkioiden lukumäärän eli listan pituuden. Funktio määritellään

          length        :: [a] -> Int
          length []     =  0
          lenght [x:xs] =  1 + length xs,
  

  Tyypitys

          length        :: [a] -> Int
  

  kertoo funktion kuvaavan listan mitä tyyppiä tahansa olevia alkiota kokonaisluvuksi.

  Mikäli argumenttina annetaan tyhjä lista, on funktion arvo 0

          length []     =  0
  

  Mikäli lista ei ole tyhjä, on sen pituus 1 + listan pituus ilman ensimmäistä alkiota

          lenght [x:xs] =  1 + length xs
  

  Tämäkin funktio siis käyttää hyväkseen rekursiota. Kun listan alkiot loppuvat, palautaa lenght xs nollan ja rekursio päättyy. Rekursion purkautuessa saadut arvot lasketaan yhteen ja funktio palauttaa arvonaa listan pituuden.

  Ylimäärittely

  Yhtäsuuruustyyppiluokka kokonais- ja liukuluvuille määritellään

          class Eq a where
            (==) :: a-> a-> -> Bool
  
          instance Eq Int where
            x == y  = intEq x y
   
          instance Eq Float where
            x == y  = floatEq x y
  

  Tyyppiluokan määrittelevät yleiselle tyypille a lauseet

          class Eq a where
            (==) :: a-> a-> -> Bool
  

  Määrittely voitaisiin lukea "tyyppiluokka nimeltä Eq mille tahansa tyypille a missä operaattori == ottaa kaksi argumenttia tyyppiä a ja palauttaa arvonaan tyyppiä Bool olevan arvon".

  Seuraavat instanssimäärittelyt puolestaan tarkentavat yhtäsuuruuden koskemaan kokonais- ja liukulukuja

          instance Eq Int where
            x == y  = intEq x y
   
          instance Eq Float where
            x == y  = floatEq x y
  

  Nämä voitaisiin lukea "tyyppiluokan Eq toteustus Int-tyyppisille arvoille missä operaattori == vastaa funktion intEq soveltamista operaattorin argumentteihin x ja y" ja "tyyppiluokan Eq toteutus Float-tyyppisille arvoille missä operaattori == vastaa funktion floatEq soveltamista operaattorin argumentteihin x ja y".

  quicksort -funktio

  Funktio quicksort määritellään

          quicksort       :: (Ord a) => [a] -> [a]
          quicksort []    =  []
          quicksort (x:xs)=  quicksort [ y | y <- xs, y < x ]
                          ++ quicksort [ x ]
                          ++ quicksort [ y | y <- xs, y >= x ]
  

  Tyypitys

          quicksort       :: (Ord a) => [a] -> [a]
  

  voitaisiin lukea "quicksort ottaa argumenttinaan listan, jonka alkiot ovat mitä tahansa Ord-tyyppiluokkaan kuuluvaa tyyppiä, ja arvonaan listan, jonka alkiot ovat samaa tyyppiä". Tyyppiluokkaan Ord kuuluvat kaikki ne tyypit, joille on määritelty järjestys.

  Itse funktion määrittely on taas rekursiivinen

          quicksort []    =  []
          quicksort (x:xs)=  quicksort [ y | y <- xs, y < x ]
                          ++ quicksort [ x ]
                          ++ quicksort [ y | y <- xs, y >= x ]
  

  Quicksort tyhjästä listasta on tyhjä lista, muutoin quicksort on quicksort niistä listan muista alkioista xs, jotka ovat pienempiä kuin listan ensimmäinen alkio x katenoituna listaan, joka sisältää x:n katenoituna quicksortiin listan muista alkioista xs, jotka ovat suurempia tai yhtäsuuria kuin x. Rekursio päättyessä siis katenoidaan yhteen niin monta yhden alkion listaa kuin alkuperäisessä listassa oli alkioita.

  Operaattori ++ on katenaatio. Merkintä | ja <- on listageneraattori, jota on yritetty selittää funtion fib yhteydessä.

  fib -funktio

  Funktio fib generoi Fibonaccin sarjan. Fibonaccin sarja on lukujono, jonka kaksi ensimmäistä termiä ovat ykkösiä. Muut termit ovat aina kahden edellisen summa. Kolmas termi on siten 2, neljäs 3, viides 5, kuudes 8 jne. Funktio on esimerkki päättymättömästä listasta.

  Funktio määritellään

          fib = 1: 1: [ a+b | (a,b) <- zip fib (tail fib) ]
  

  Sarja muodostuu listasta, johon liitetään aluksi kaksi ykköstä 1: 1:. Loput termit luodaan käyttämällä listageneraattoria | ja <-. Generaattori ottaa oikealla puolellaan olevasta listasta kaikki alkiot välissään olevan säännön mukaan, ja tekee niille vasemmalla puolellaan olevan operaation. Lista, josta generaattori ottaa alkiot, muodostetaan zip -funktiolla liittämällä yhteen lista fib (siis sama lista jota ollaan luomassa!) ja listan fib alkiot lukuunottamatta ensimmäistä (listan "häntä", (tail fib)). Koska lista tail fib on yhden alkion "edellä" listaa fib, niin zip liittää yhteen aina kaksi peräkkäistä termiä, jotka generaattori laskee yhteen. Tässä täytyy muistaa, että funktio ja sen arvo voidaan samastaa, jolloin siis fib on sekä funktio, jolla Fibonaccin sarjaa ollaan luomassa että itse luotava lista. Oheinen kuva ehkä selventää hieman asiaa.

  Sinänsä mielenkiintoista on, että ilman tyypitystä tämä funktio on määritelty kaikille tyypeille, joille yhteenlasku on määritelty.

  ---

  ©Matti Heinonen 21.11.1996 contact: majuhe@math.jyu.fi